<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Tapesh Chandra Das on Medium]]></title>
        <description><![CDATA[Stories by Tapesh Chandra Das on Medium]]></description>
        <link>https://medium.com/@tapeshdas2002?source=rss-3e724af182c1------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*JT7GjxNO2TF4fW_aGNby9Q@2x.jpeg</url>
            <title>Stories by Tapesh Chandra Das on Medium</title>
            <link>https://medium.com/@tapeshdas2002?source=rss-3e724af182c1------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 19:35:38 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@tapeshdas2002/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Teaching DuckDB to Remember: Building a Query Recycler Extension]]></title>
            <link>https://medium.com/@tapeshdas2002/teaching-duckdb-to-remember-building-a-query-recycler-extension-e14d90b658e5?source=rss-3e724af182c1------2</link>
            <guid isPermaLink="false">https://medium.com/p/e14d90b658e5</guid>
            <category><![CDATA[dbms]]></category>
            <category><![CDATA[duckdb]]></category>
            <category><![CDATA[caching]]></category>
            <dc:creator><![CDATA[Tapesh Chandra Das]]></dc:creator>
            <pubDate>Fri, 20 Nov 2026 16:31:51 GMT</pubDate>
            <atom:updated>2026-11-20T16:31:51.596Z</atom:updated>
            <content:encoded><![CDATA[<h3><em>How we cut a repeated analytical workload from 35.7 ms to 6.4 ms per query, and why the biggest single win wasn’t caching at all.</em></h3><p>Half of all Amazon Redshift clusters see 80% of their queries repeat an earlier one (<a href="https://www.vldb.org/pvldb/vol17/p3694-saxena.pdf">Saxena et al., VLDB 2024</a>). Dashboards refresh. BI tools re-issue the same query with a different filter. Data agents explore a dataset one small step at a time. Yet the standard benchmarks, TPC-H and TPC-DS, contain no repeats at all, so most engines are not tuned for this.</p><p>For a Data System Architecture course, my team built <a href="https://github.com/td-02/duckdb-recycler">duckdb-recycler</a>: a DuckDB 1.5.5 extension that notices when a query repeats all or part of an earlier one and serves that part from memory. The workload was 149 queries over the IMDB (Join Order Benchmark) dataset, run in order, twice. The one rule above all others: every answer must match vanilla DuckDB exactly. A wrong answer ranked below the slowest correct solution.</p><p>Here’s where we ended up:</p><p>ConfigurationGeomean per queryTotalVanilla DuckDB 1.5.535.7 ms24.4 sEXISTS rewrite only16.8 ms6.4 sResult cache only9.5 ms12.9 sBoth6.4 ms4.4 s</p><p>The rest of this post is how we got there, including the parts that went wrong.</p><h3>Step 0: our first version was slower than doing nothing</h3><p>Our first extension cached whole query results and intermediate subtrees. It measured 35.0 ms against vanilla’s 30.7 ms. It was paying to store results and almost never reused them.</p><p>The cause: most queries in the workload contain a correlated EXISTS, which DuckDB plans as a <em>delim join</em>. A delim join&#39;s two sides refer to each other, so you can&#39;t lift a subtree out of one side and cache it on its own. Our code bailed out whenever it saw one, which meant it bailed out almost everywhere, after already paying the overhead.</p><p>Lesson one: measure the hit rate before you measure the speed. A cache with no hits is pure overhead.</p><h3>How the recycler works</h3><p>The extension plugs into DuckDB’s optimizer through two hooks and adds two physical operators: RECYCLER_SCAN, which reads a cached result, and RECYCLER_MATERIALIZE, which stores a result while passing it through to the rest of the query.</p><h3>1. Signatures: deciding “is this the same thing?”</h3><p>Everything depends on recognizing that two plans compute the same rows. Each bound plan gets a canonical structural signature: table indexes renumbered in a fixed order, every operator and expression field rendered, and anything the code doesn’t understand refused rather than guessed. A query that repeats an earlier one, or contains an earlier query as a nested block, is answered straight from the cache.</p><h3>2. Subtree reuse</h3><p>After DuckDB’s own optimizers have run, joins, aggregates, DISTINCTs and CTE definitions become candidates. An exact match becomes a RECYCLER_SCAN. A miss is stored only if it looks worth it: a large input, a much smaller output, within size limits. We treat a whole delim join as one atomic unit, which fixed the bail-out problem from Step 0.</p><h3>3. Predicate subsumption</h3><p>Real workloads rarely repeat a query exactly. More often they narrow it: production_year IS NOT NULL first, then production_year BETWEEN 1998 AND 2003. We give each multi-table block a <em>shape</em> (its structure with the range predicates lifted out), store the block&#39;s rows the first time a shape appears, and serve any later block whose predicates are implied by the stored ones, adding a filter on top for the difference.</p><h3>4. Ordered pagination</h3><p>ORDER BY ... LIMIT 50 OFFSET 5000, then OFFSET 5050, then OFFSET 5100... Each page normally re-sorts the whole input. We cache a sorted prefix once and serve later pages from it, growing it when a page needs more. This only applies when the sort order is provably total (a primary key or group key is among the sort keys); otherwise two runs could legitimately return ties in different orders.</p><h3>The biggest win wasn’t caching</h3><p>After all of that, our geomean was good but our <em>total</em> time on the hidden query set was poor: lots of queries were slow the first time they ran, and a cache can’t help the first run.</p><p>Digging in, the slow first runs were nearly all correlated EXISTS queries. Two decisions inside DuckDB 1.5.5 combine badly:</p><ol><li>DuckDB only turns a delim join into an ordinary join when nothing inside it filters. Almost every real subquery filters.</li><li>The join order optimizer never reorders a delim join, nor any join tree that contains one.</li></ol><p>So one EXISTS anywhere in a query froze the join order of the whole FROM clause in the order it was written, and materialized all of it before evaluating the subquery, even when the subquery would have discarded 999 rows in 1,000.</p><p>We wrote our own decorrelation pass for the one common shape where it is exactly equivalent: WHERE [NOT] EXISTS (... inner.k = outer.c ...) with bare columns on both sides. It turns the delim join into a plain MARK join that the join order optimizer can place by cost, and moves it through LEFT joins itself, since the optimizer can&#39;t. One query went from 1.2 s to 0.19 s.</p><p>On its own, with no caching at all, the rewrite took the workload from 35.7 ms to 16.8 ms geomean and from 24.4 s to 6.4 s total. Lesson two: before building something clever on top of a system, check whether the system is doing something avoidable underneath.</p><h3>Correctness: the bugs that taught us the most</h3><p>A cache that returns a stale or partial result is worse than no cache. Two bugs stand out.</p><p>Runtime filters. A join above a subtree can push a runtime filter down into that subtree’s scans, so the scans skip rows the join would throw away anyway. That’s fine for the current query. But if you cache that subtree, you’ve stored a <em>pruned</em> result under a key that promises <em>all</em> rows. The next query that reuses it silently loses rows. The fix: strip those join-owned runtime filters from a subtree before storing it.</p><p>Filters sliding under markers. The EXISTS rewrite at first placed a new filter directly above one of our own storage markers. DuckDB’s join optimizer passes through single-child operators it doesn’t know about and pushed the filter <em>below</em> the marker, so the stored block missed rows its key promised: 89 rows instead of 178. The fix: refuse the rewrite when the subquery already contains a recycler operator.</p><p>Both bugs passed casual testing. They were caught by a differential checker that replays the whole workload in several orders and compares every result with vanilla DuckDB, plus the rule that nothing ships until every answer matches.</p><p>The full list of things the cache refuses to touch is long and deliberate: volatile functions, parameters, table functions, temporary tables, attached non-DuckDB databases, LIMIT without ORDER BY, functions that read session state like current_setting(), and any statement inside a transaction that has written. Any statement that changes data or the schema clears the cache. Session settings that change results at run time (TimeZone, Calendar, sort-order defaults) are part of every key.</p><h3>What I’d tell someone starting this</h3><ul><li>Hit rate first, speed second. Instrument what the cache stores and serves before tuning anything.</li><li>Look under the feature you’re building. Our largest gain came from fixing a planning limitation, not from the cache.</li><li>Make correctness mechanical. A differential checker against the unmodified system, run in several query orders, found bugs no one would have spotted by reading code.</li><li>Refuse what you don’t understand. Every construct the signature code doesn’t recognize is treated as uncacheable. That costs a few hits and saves you from wrong answers.</li></ul><p>The code, tests and design notes are on GitHub: <a href="https://github.com/td-02/duckdb-recycler">td-02/duckdb-recycler</a>. Questions and feedback welcome.</p><p><em>References</em></p><ul><li>Saxena et al., <em>Why TPC Is Not Enough: An Analysis of the Amazon Redshift Fleet</em>, PVLDB 2024.</li><li>Nagel, Boncz, Viglas, <em>Recycling in Pipelined Query Evaluation</em>, ICDE 2013.</li><li>Dursun et al., <em>Revisiting Reuse in Main Memory Database Systems</em>, SIGMOD 2017.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e14d90b658e5" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>