cockroachdb / cockroachdb/cockroach

opt: use inverted statistics to estimate selectivity of containment filters with non-constant operands

Open
#175,529 0 comments 0 reactions 0 assignees View on GitHub
A-sql-optimizer A-sql-table-stats C-enhancement C-performance O-agent O-support T-sql-queries
Dominant language
Go
Stars
32.5k
Forks
4.1k
PR merge metrics
PR metrics pending

Description

**Is your feature request related to a problem? Please describe.**

Follow-on to #62835, which covers the constant-operand form of the same predicates; this issue covers the non-constant (placeholder and column) operands that #62835's histogram-filtering approach cannot reach.

When a containment predicate on an inverted-indexed column has a non-constant
right-hand side, the statistics builder falls back to fixed default
selectivities, even when an inverted statistic (with a histogram over the
inverted keys) exists for the column:

- `col @> ARRAY[$1]` in a `Select` with a placeholder operand: the RHS has no
enumerable paths, so it counts as one unknown conjunct and gets
`unknownFilterSelectivity` = 1/3
([statistics_builder.go#L3623-L3637](https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/opt/memo/statistics_builder.go#L3623-L3637)).
- `t.col @> ARRAY[u.v]` as an inverted join condition gets
`unknownInvertedJoinSelectivity` = 1/100
([statistics_builder.go#L5137-L5141](https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/opt/memo/statistics_builder.go#L5137-L5141)).
- For comparison, a constant operand in a `Select` counts as two unknown
conjuncts (1/9), and only the `Scan` with an `InvertedConstraint` consults
the histogram (#62835).

So the same predicate is estimated at 1/3, 1/9, or 1/100 of the table
depending on which form it happens to be in, and none of those numbers come
from the data. An inverted statistic already records the number of inverted
entries and the number of distinct keys, which together give the average
number of rows containing any given key. For array columns holding
identifiers (tags, ancestor paths, memberships) that average is typically in
the single or double digits, several orders of magnitude below the defaults.

This matters most for prepared statements, where the operand is always a
placeholder. A generic plan can only use the inverted index through a
parameterized inverted join followed by a lookup join that re-applies the
original filter, and that re-applied filter takes the 1/3 estimate. The
result is that a join against a large table is planned as a hash join with a
full scan rather than a lookup join, purely because of the default.

Reproduction (opt tester, `pkg/sql/opt/xform`):

```
exec-ddl
CREATE TABLE parent (id UUID PRIMARY KEY, ref UUID, INDEX parent_ref_idx (ref))
----

exec-ddl
CREATE TABLE child (id UUID PRIMARY KEY, tags UUID[], INVERTED INDEX child_tags_idx (tags))
----

exec-ddl
ALTER TABLE parent INJECT STATISTICS '[
{"columns": ["id"], "created_at": "2026-01-01 1:00:00.00000+00:00", "row_count": 10000000, "distinct_count": 10000000},
{"columns": ["ref"], "created_at": "2026-01-01 1:00:00.00000+00:00", "row_count": 10000000, "distinct_count": 1000000}
]'
----

exec-ddl
ALTER TABLE child INJECT STATISTICS '[
{"columns": ["id"], "created_at": "2026-01-01 1:00:00.00000+00:00", "row_count": 1000000, "distinct_count": 1000000}
]'
----

opt format=show-stats
SELECT p.id FROM parent AS p
INNER JOIN (SELECT c.id FROM child AS c WHERE c.tags @> ARRAY[$1::uuid]) AS s
ON p.ref = s.id
ORDER BY p.id LIMIT 1000
----
```

Relevant part of the output (placeholders kept, i.e. the generic plan):

```
inner-join (hash)
├── scan parent [as=p] <-- full scan, 1e+07 rows
└── inner-join (lookup child [as=c])
├── stats: [rows=333333] <-- 1/3 of child
└── inner-join (inverted child@child_tags_idx,inverted [as=c])
├── stats: [rows=10000] <-- 1/100 of child
└── values (placeholder $1)
```

The lookup join's output estimate is the `Select` group's estimate, not a
function of its 10,000-row input (see #104096). Folding the placeholder to a
constant instead produces a `Select` estimate of 1/9 of the table above an
inverted scan, and that plan chooses the lookup join into `parent`, but with
a narrow cost margin. Sweeping the default selectivity showed that any value
at or below ~0.2 chooses the lookup join in both forms.

**Describe the solution you'd like**

When a containment filter has a non-constant RHS and the inverted column has
an inverted statistic, estimate the selectivity pessimistically from the
inverted histogram, mirroring the max-frequency estimate already used for
placeholder equality (`selectivityFromMaxFrequencies`): assume the runtime
operand is the heaviest key the histogram knows about.

```
rows = max over relevant histogram buckets of numEq
selectivity = rows / tableRowCount
```

"Relevant" follows the span set the operator would probe if the operand were
a constant, so the estimator never has to guess which keys are plausible:

- `col @> ARRAY[$1]` (and JSON `@>` with a non-empty operand shape) probes
only element keys. The empty-array and empty-JSON marker keys are never in
its span set, so they are excluded from the max. This matters in practice:
in ancestor-path style data the empty array is often the single heaviest
key, and it can never satisfy `@>` for a non-empty operand. This is the
same kind of exclusion the equality estimate makes when it ignores the NULL
bucket.
- `col <@ ARRAY[$1]` always probes the empty-array key in addition to the
element keys, so the marker's frequency is included (added to the heaviest
element key); such queries really do read every empty row.
- A whole-value placeholder (`col @> $1`) could be empty at runtime and match
every row. Treat it as a non-empty single-key operand, which is the
assumption the constant path's path-counting already makes, rather than
estimating the whole table.

For a RHS with `n` leaf paths (e.g. `ARRAY[$1, $2]`, or a JSON object with
two leaves) apply the per-key selectivity once per path, matching how
constant operands are counted today.

Apply it in both places so the `Select` group and the join alternatives agree:

- `applyFiltersItem`, in the `ContainsOp` branch when `countPaths` returns 0
(placeholder or column operand), and for `isInvertedJoinCond` filters.
- `selectivityFromInvertedJoinCondition`, replacing the flat 1/100 when the
statistic is available.

Fall back to the existing defaults when there is no inverted statistic, and
gate the new behavior behind a session setting so it can be disabled if a
workload regresses.

The histogram is available exactly when it is needed: the generic memo is
optimized once with the table statistics in hand, and the resulting row
counts are baked into the cached plan until a statistics change makes the
memo stale and forces a rebuild, so no additional state has to be retained.

**Describe alternatives you've considered**

- **Average key** (`entries / distinctKeys`), or a model of one heavy hitter
plus an average over the rest. For typical identifier arrays these land at
a handful of rows per key, several orders of magnitude below the heaviest
key, and for skewed data the two barely converge no matter how many heavy
hitters are trimmed. The average describes the typical lookup; the maximum
describes the worst one. Generic plans must be acceptable for every
argument, which is why the pessimistic estimate is proposed here, and why
the equality estimate already made the same choice.
- **Histogram filtering in the `Select` (#62835).** Carrying an
`InvertedConstraint` in scalar props would fix the constant-operand case
properly, but it needs a constant to filter the histogram with, so it does
not help placeholders, generic plans, or inverted join conditions. The two
are complementary; this issue is the non-constant half.
- **Lowering the constants.** A smaller default fixes this shape but is wrong
for every other one, and the join path's 1/100 already shows that picking
constants per operator does not compose.
- **Parameter-sensitive plan selection.** Build the generic plan for the
typical key and register the histogram's heavy keys as a guard checked at
bind time, routing heavy arguments to a custom plan. This is the principled
answer for data with a genuinely ubiquitous real key, where no single plan
fits, but it is a separate mechanism that depends on this estimate being
fixed first.

**Additional context**

- Related: #62835 (constant-operand containment in `Select`), #104096 (index
join over inverted scan inherits the `Select` estimate), #88626 (unknown
selectivity backoff).
- Because the estimate depends on the predicate's normalization form, the
generic plan's re-check estimate (1/3) is worse than the custom plan's
(1/9) for the same query, which is why generic plans are disproportionately
affected.

Jira issue: CRDB-68434

Contributor guide

Open the contributing guide

Research direction

Start in pkg/sql/opt/memo/statistics_builder.go, reading applyFiltersItem and selectivityFromInvertedJoinCondition alongside the linked selectivity code. Run the opt tester reproduction in pkg/sql/opt/xform and compare generic-plan estimates for non-constant containment operands. Done means relevant inverted histograms are used for both select and join estimates, existing defaults remain available without statistics, and the behavior can be disabled through a session setting.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
backend, databases
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.