Making a slow count fast without making it wrong

The problem

I built a data platform for a client that lets users apply a set of filters to a large archive and see how many rows match before committing to the full operation. The archive ran to a few million rows. Users would set up a handful of filters, ask for the count, look at it, adjust one filter and ask again, and they might go round that loop several times before running anything.

The count was taking about 88 seconds. Users noticed. Worse, they noticed twice, because a single run usually meant refining the filters at least once.

Where the time was going

The existing implementation paged rows out of the database in batches, loaded them into the application, and tallied matches in a loop. Filtering happened partly in the query and partly in application code, because some of the filter logic (exclusion lists, mostly) had been written as an in-memory check against rows already fetched. So the database was doing far more I/O than the answer needed. It had to hand over every candidate row so the application could look at it and decide whether to count it.

The fix was to stop moving rows at all. A count doesn't need the rows, it needs an aggregate, so the whole thing became a single query. The filters became WHERE conditions, and the exclusion lists (records that shouldn't be counted because they exist in some other table) became anti-joins instead of a fetch-then-filter step in code.

Here's a simplified version of what that looks like.

SELECT COUNT(*)
FROM records r
WHERE r.status = 'active'
  AND r.region = ANY ($1)
  AND NOT EXISTS (
    SELECT 1 FROM exclusions_a a WHERE a.record_id = r.id
  )
  AND NOT EXISTS (
    SELECT 1 FROM exclusions_b b WHERE b.record_id = r.id
  );

That took the count from 88 seconds to about 3.4. The database could always have answered the question directly, and nothing ever needed paging anywhere.

Keeping it right

The speed wasn't the hard part. After the rewrite there were two ways to answer "how many records match these filters". One was the new SQL path, and the other was the original in-application path, which I hadn't deleted because not every filter had been ported yet. Two engines that can each arrive at an answer to the same question, and can disagree with each other, are a correctness hazard, and I think a wrong count that takes 3.4 seconds is worse than a right one that takes 88, because nobody double-checks a number that looks plausible. The fast one gets trusted immediately, and the slow one at least gave people time to be suspicious.

So the design problem I actually had to solve was how to let the fast path grow to cover more filters over time without ever letting it produce a wrong answer for a filter it doesn't fully understand yet.

The answer I landed on is a whitelist rather than a blacklist. The SQL builder doesn't try to detect filters it can't handle and special-case them. It only recognises the exact set of filters it's been explicitly taught to translate. Anything outside that set (including a brand new filter type added later by someone who has never seen this code) makes the whole query fall back automatically to the slower, application-level path. That path is known to be correct because it's the same logic that shipped before any of this existed.

That's what makes it safe to keep extending. A new filter is slow until someone adds it to the SQL builder, but it's never wrong. If you forget to teach the SQL builder about a new filter, the failure mode is "it's slow again for that one case," which someone will notice and fix. The failure mode of a blacklist approach (try to translate everything, catch the cases you know are hard) is "it's fast and wrong," which nobody notices until someone acts on a number that was never right.

Why the NOT EXISTS clauses are separate

I kept the two NOT EXISTS clauses above separate on purpose. The alternative is one subquery with an OR inside it, something like this.

-- slower
AND NOT EXISTS (
  SELECT 1 FROM exclusions_a a
  WHERE a.record_id = r.id
     OR a.record_id IN (SELECT record_id FROM exclusions_b)
)

-- faster
AND NOT EXISTS (SELECT 1 FROM exclusions_a a WHERE a.record_id = r.id)
AND NOT EXISTS (SELECT 1 FROM exclusions_b b WHERE b.record_id = r.id)

Logically these are identical, but the query planner doesn't treat them the same. The combined form with an OR inside a single subquery can stop the planner using an index efficiently on either branch, because it has to evaluate a compound condition instead of a simple equality against one indexed column. Splitting it into two independent NOT EXISTS clauses lets each one be satisfied by its own index lookup. That change on its own accounted for roughly half of the remaining time after the move to an aggregate query.

Neither of these fixes is exotic, and finding the faster query didn't take much judgement. Most of the work was making sure the fast version could never give a wrong count, even briefly, even for one commit.