7 min

September 27, 2026

TPC-H Query 16 - Estimating String Filters

Today's TPC-H query is the first one to use a COUNT(DISTINCT).

It also contains an interesting estimation challenge.

Query 16

Here is the query:

SELECT p_brand,
       p_type,
       p_size,
       COUNT(DISTINCT ps_suppkey) AS supplier_cnt
FROM partsupp
INNER JOIN part
    ON ps_partkey = p_partkey
WHERE p_brand <> 'Brand#42'
  AND p_type NOT LIKE 'STANDARD ANODIZED%'
  AND p_size IN (3, 7, 11, 29, 31, 37, 41, 49)
  AND ps_suppkey NOT IN (SELECT s_suppkey
                         FROM supplier
                         WHERE s_comment LIKE '%Customer%Complaints%')
GROUP BY p_brand,
         p_type,
         p_size
ORDER BY supplier_cnt DESC,
         p_brand,
         p_type,
         p_size

Estimation and Join Order

The query has several filters with two of them being tricky:

Notice how we have two filters that look at substrings of values.

The direct one: p_type NOT LIKE 'STANDARD ANODIZED%' and then the more indirect subquery with s_comment LIKE '%Customer%Complaints%'.

The filter on p_type is significantly easier to estimate than the filter on s_comment. The p_type filter is a prefix match: there is no wildcard at the start of the pattern. A prefix match can be rewritten to a range:

p_type >= 'STANDARD ANODIZED' AND p_type < 'STANDARD ANODIZEE'

A range like this can be estimated from an ordinary histogram, the same way we estimate p_size BETWEEN 10 AND 20.

The s_comment filter is a substring match: the pattern starts with a wildcard. The words we look for can appear anywhere in the string, so the sort order of the values tells us nothing. The ranges in a histogram are of almost no use for such an estimation.

Optimal Join Order

The largest table by far is partsupp (at 800K rows in SF1). Any optimisation we do will need to filter this table quickly to reduce rowcount.

But first, we have to realise that the NOT IN (SELECT s_suppkey) is actually a join in disguise. This is what is called an anti join: find things that are not in a hash table (assuming hash join strategy).

A good query optimiser will realise this and rewrite to:

SELECT ...
FROM partsupp
INNER JOIN part
    ON ps_partkey = p_partkey
LEFT JOIN (SELECT s_suppkey
             FROM supplier
            WHERE s_comment LIKE '%Customer%Complaints%') AS anti_rewrite
    ON ps_suppkey = s_suppkey 
WHERE p_brand <> 'Brand#42'
  AND p_type NOT LIKE 'STANDARD ANODIZED%'
  AND p_size IN (3, 7, 11, 29, 31, 37, 41, 49)
  AND anti_rewrite.s_suppkey IS NULL -- ANTI join part

Picking the right join order now comes down to one question: "Which filter reduces the stream of partsupp the most: the join to part or the one to supplier?"

From our filter analysis, we can clearly see that the best reduction is by joining part before supplier. The optimal join order becomes: partsupp ⨝ part ▷ supplier. Where we use ▷ to mean: anti join with build on the right side, and probe with the left for non matches.

But here is the catch: How can the query optimiser know that the filter on part is much better than the one coming from supplier?

Estimating a string filter

If we look at SQL Arena for Query 16, we can see estimation varies wildly for the filter s_comment LIKE '%Customer%Complaints%'.

The correct value is 4 rows out of 10000. Here is what databases estimate:

In the case of DuckDB and Apache DataFusion - we observe a classic database fallback: When you can't estimate something, fall back to a constant. This constant appears to be 20% in DuckDB and DataFusion (it's 30% in SQL Server).

Fortunately, even with an estimate this wrong - the final estimation of the part filter still indicates that it is better to join with part before supplier.

The only engine that decides to join supplier before part is Databricks, which appears to estimate that both joins do nothing! This makes no sense at all when you consider that the anti join estimates 10.000 supplier rows.

How do PostgreSQL, SQL Server and CedarDB do such a fine job of estimating this filter?

PostgreSQL Filter Estimation

PostgreSQL estimates LIKE in patternsel_common (in src/backend/utils/adt/like_support.c). It does not use the histogram as ranges. Instead, it runs the LIKE pattern against the actual values stored in the histogram and in the most common values (MCV) list in pg_stats.

The histogram part works like this:

• With the default statistics target, the histogram has 101 boundary values.
• histogram_selectivity (in selfuncs.c) skips the first and last value and tests the pattern against the remaining 99.
• The selectivity is the fraction of those 99 values that match.
• If the histogram has fewer than 100 entries, PostgreSQL blends in a heuristic where every fixed character in the pattern multiplies the selectivity by 0.2.
• Values in the MCV list are tested one by one, and their exact frequencies are added on top.

For example, this query is well estimated in PostgreSQL:

SELECT COUNT(*)
FROM supplier
WHERE s_comment LIKE '%the%'

-- estimate: 6666, actual: 6642

66 of the 99 histogram values contain "the", and 66/99 × 10000 ≈ 6667.

For '%Customer%Complaints%', none of the 99 values match, so the histogram selectivity is 0. PostgreSQL does not believe an estimate of zero, and the code clamps it:

/* In any case, don't believe extremely small or large estimates. */
if (selec < 0.0001)
    selec = 0.0001;

0.0001 × 10000 rows = 1 row. Purely by luck, this selectivity floor happens to be a good estimate for a 10000 row table.

SQL Server Filter Estimation

SQL Server uses something called a "string summary" containing common substrings in the data. I suspect from poking around its estimates, but do not know for sure, that it is some kind of trie data structure.

• Statistics Used by the Query Optimizer in Microsoft SQL Server 2005 describes the string summary and how it estimates prefix, suffix and infix LIKE patterns.

The filter '%Customer%Complaints%' can be estimated (roughly) by looking at the occurrence of the word "Customer" and the "Complaints" substring and scaling it to the total size of the supplier table. SQL Server does a good job due to this string summary structure.

CedarDB

I unfortunately do not know how CedarDB estimates substrings. If any of my readers know, I would be very curious to hear from you.

Running Distinct Count

Let's switch focus to this part of the query:

SELECT p_brand,
       p_type,
       p_size,
       /* DISTINCT ... */
       COUNT(DISTINCT ps_suppkey) AS supplier_cnt
FROM <rest of query>

Most aggregates, like MIN/MAX/SUM/COUNT/AVG, can be calculated with a loop like this:

aggregate = dict()
for row in agg_input:
    if row.group_key not in aggregate:
        aggregate[row.group_key] = row.aggregate_value
        continue
    # group key was already there, aggregate it
    aggregate[row.group_key] = agg_func(row.aggregate_value, aggregate[row.group_key])

# Emit the aggregate
for group_key, aggregate_value in aggregate.items():
    emit(group_key, aggregate_value)

Every row just updates the value of the existing aggregate value using a function.

But COUNT DISTINCT is different. To aggregate a new value into an existing aggregate row we have to track every unique value we have seen. This leads to aggregate code that looks like this:

aggregate = dict()
for row in agg_input:
    if row.group_key not in aggregate:
        # The aggregate value is a set
        aggregate[row.group_key] = {row.aggregate_value}
        continue

    # add to the set
    aggregate[row.group_key].add(row.aggregate_value)

# Emit the aggregate
for group_key, aggregate_value in aggregate.items():
    emit(group_key, len(aggregate_value)) # The aggregate is the size of the set!

Some databases, like PostgreSQL and DuckDB, implement a special COUNT DISTINCT aggregate.

But there is another way to execute COUNT DISTINCT. Consider again this query:

SELECT p_brand,
       p_type,
       p_size,
       /* DISTINCT ... */
       COUNT(DISTINCT ps_suppkey) AS supplier_cnt
FROM <rest of query>

This is the same as:

SELECT p_brand,
       p_type,
       p_size,
       COUNT(ps_suppkey) AS supplier_cnt
FROM (
    SELECT 
       p_brand,
       p_type,
       p_size,
       ps_suppkey 
    FROM <rest of query>
    GROUP BY p_brand,
             p_type,
             p_size,
             ps_suppkey
) as partial_agg
GROUP BY p_brand,
         p_type,
         p_size

In other words, a COUNT DISTINCT can be rewritten to a GROUP BY that removes duplicates, followed by a regular COUNT aggregate. This allows reuse of the same aggregation code that is used for regular, cumulative aggregates.

For example, here is Trino doing exactly that for Query 16:

Operator
PROJECT p_brand, p_type, p_size, count AS supplier_cnt
SORT count, p_brand, p_type, p_size
AGGREGATE COUNT(count_9) AS count GROUP BY HASH p_brand, p_type, p_size
DISTRIBUTE HASH ON p_brand, p_type, p_size
AGGREGATE COUNT(ps_suppkey) AS count_9 GROUP BY PARTIAL p_brand, p_type, p_size
GROUP BY HASH p_brand, p_type, p_size, ps_suppkey
DISTRIBUTE HASH ON p_brand, p_type, p_size, ps_suppkey
GROUP BY PARTIAL p_brand, p_type, p_size, ps_suppkey
LEFT ANTI JOIN HASH ON ps_suppkey = s_suppkey

Of course, doing this rewrite raises the question: What happens if there is more than one COUNT DISTINCT in a query?

One approach is to broadcast the stream entering the aggregate: Have multiple agg nodes consume the same data! To do that, you need an execution engine that can treat execution like a DAG - not just a tree.

Alternatively, you can scan the same stream multiple times.

Summary

Today, we saw how string filters can be estimated with data structures and that only a few databases do this.

I also showed you two different ways for databases to evaluate COUNT(DISTINCT) queries.