A 45-Minute PostgreSQL Query Reduced to 100ms: A Reproducible Builds Case Study

The Reproducible Builds project, an initiative to make software compilation deterministic so that identical source code always produces identical binaries, relies on a PostgreSQL database to track whether packages across various distributions—including Alpine, Debian, Fedora, NixOS, and many others—reproduce correctly. Rebuilds are triggered periodically, and the scheduling logic depends on SQL queries to determine which packages to test next.

When a fellow Debian Developer reported that one such scheduling query was taking roughly 45 minutes to complete, the root cause turned out to be a well-known PostgreSQL anti-pattern.

Anatomy of the Problem

The slow query, which was already identified in the project's scheduler code, had to determine which packages were candidates for testing. When the execution plan was examined using the provided database dump, it revealed an estimated plan cost in the nine digits—a clear sign of O(N²) behavior stemming from two SubPlan nodes in the query.

The core issue was the use of NOT IN (subquery). As PostgreSQL's own documentation notes, this construct is discouraged: performance may look acceptable in small-scale tests, but once the data volume crosses a certain threshold, the query can slow down by five or more orders of magnitude. The database optimizer cannot rewrite NOT IN (subquery) into a more efficient form because doing so would alter the query semantics when NULL values are involved.

The Fix: NOT EXISTS Instead of NOT IN

Because the application does not deal with NULLs in this context, the semantics of the query were safe to preserve with a manual rewrite. The recommended approach is to replace NOT IN (subquery) with NOT EXISTS (subquery). In this scenario, variables from the outer query can be referenced directly inside the subquery, allowing PostgreSQL to use a more efficient execution strategy.

After rewriting the query to use NOT EXISTS, the runtime dropped from 45 minutes to 100 milliseconds—a speedup of roughly 27,000 times. The change was then integrated into the production scheduler script, and the job that runs this query now completes far more quickly than before.

"Don't use NOT IN" — PostgreSQL Wiki

This case serves as a practical reminder that the choice between NOT IN and NOT EXISTS is not merely stylistic; it can have profound performance implications in real-world workloads. When NULLs are not a concern, converting to NOT EXISTS allows PostgreSQL's planner to avoid the quadratic cost of repeated subquery evaluation, which is especially critical as table sizes grow.