Skip to content

transform: detect index lookups from the filter as written - #38717

Draft
frankmcsherry wants to merge 2 commits into
MaterializeInc:mainfrom
frankmcsherry:literal-constraints-key-bounds
Draft

frankmcsherry wants to merge 2 commits into
MaterializeInc:mainfrom
frankmcsherry:literal-constraints-key-bounds

Conversation

@frankmcsherry

Copy link
Copy Markdown
Contributor

LiteralConstraints decides whether a filter over an indexed relation can be served by looking up literal key values in the index. Today that decision is made on a disjunctive normal form of the filter, prepared first and undone afterwards, and the preparation stops at a size guard. Past the guard the transform finds no lookup: a long IN list combined with another disjunction, a multi-column IN list, or an IN list on one indexed column next to an unrelated list on another, all plan as full scans (database-issues#1924).

This PR makes detection read the filter as written. key_bounds.rs is an exact analysis of what a predicate implies about a list of key expressions: a disjunction of boxes, each bounding every key field to a set of literals or leaving it unbounded; AND intersects boxes pairwise, OR unions them. match_index asks it whether the predicates pin every field of a candidate key and for which values. Nothing is approximated: a predicate the analysis cannot read leaves the key unbounded, and the only limit is on the number of values enumerated for a lookup, tied to FOLD_CONSTANTS_LIMIT, the size of constant collection a plan may carry.

Everything else in the transform is unchanged. Preparation, dropping contradictory disjuncts, undo_preparation, and the DNF-based removal of constraints from the filter are the same code and produce the same expressions. One consequence is stated in the module doc: detection now has more reach than removal, so a filter can yield a lookup whose constraints removal cannot take out, and the filter then stays whole above the lookup. Removal used to assert that every disjunct carried a key constraint; that held only because the old detection never let such a shape through (a = NULL OR a = 2 now looks up (2)), and it now declines instead.

What changes in plans

Against main's literal_constraints.slt, one plan differs: WHERE a = NULL OR a = 2 becomes a lookup of (2) with the filter kept. The new tests in that file are the shapes the transform previously scanned: IN lists past the old size guard, pair lists on a two-column index, a covered list alongside uncovered ones, a cross product of two covered lists, and two disjoint pair lists (empty result, asserted on rows). The datadriven transform specs are unchanged.

Relation to #38515

The analysis is that PR's; the box budget, widening, the widened bit, the contradiction-pruning pass and the removal by per-predicate exactness are deliberately not carried over, so that the transform's simplification and removal behaviour is untouched and the PR has no thresholds or heuristics beyond the existing constant-size limit. Moving contradiction simplification into the fixpoint loop, and deleting the DNF machinery, are follow-ups.

frankmcsherry and others added 2 commits September 8, 2026 13:45
LiteralConstraints decided which index to use, and with which values, on a
disjunctive normal form of the filter, prepared first and undone afterwards,
and the preparation stops at a size guard. Past the guard no lookup was
found. Detection now reads the filter as it is: KeyBounds is an exact
analysis of the key values a predicate admits, as a disjunction of boxes
that AND intersects and OR unions, with no approximation and no budget. Its
one limit is on the values enumerated for a lookup, tied to the constant
size limit a plan already observes.

Preparation, contradictory-disjunct removal, undo_preparation and the
DNF-based constraint removal are unchanged and produce the same
expressions. Detection therefore has more reach than removal, and a filter
can yield a lookup whose constraints removal cannot take out; the filter
then stays whole above the lookup. Removal asserted that every disjunct
carries a key constraint, which held only because the old detection never
let such a shape through; it now declines instead.

Co-Authored-By: Claude Fable 5.1 <[email protected]>
Long IN lists, pair lists on a two-column index, a covered list alongside
uncovered ones, a cross product of two covered lists, and two disjoint pair
lists (empty, asserted on rows). One existing plan changes: a = NULL OR
a = 2 now looks up (2) with the filter kept.

Co-Authored-By: Claude Fable 5.1 <[email protected]>
@ggevay

ggevay commented Sep 10, 2026

Copy link
Copy Markdown
Contributor

leedqin added a commit that referenced this pull request Oct 28, 2026
…ects (#40306)

### Motivation

Closes: [CNS-186](https://linear.app/materializeinc/issue/CNS-186)

A production cluster with about 2,000 objects pinned `mz_catalog_server`
at roughly 99% CPU while people viewed it in the Console. Turning off
`console-freshness-2855` for that organization brought it down to about
32%.

The Console sent every object id on the cluster as a literal `object_id
IN (...)` list. Past 330 entries, Materialize stops planning that list
as an index lookup. It scans the whole index instead and evaluates one
`OR` term per id on every row. #38717 is the optimizer-side fix. This PR
removes the Console's exposure without waiting for a release.

### What changes

- New `buildIdListQuery` (`console/src/api/materialize/idList.ts`): the
ids as an `unnest`ed array, joined against the indexed relation. It
drops repeated ids, since a join would repeat their rows and double
`GROUP BY` counts.
- These builders now join that list instead of a literal `IN`:
- `buildObjectLagHistoryQuery`, `buildLatestLagQuery`,
`buildHydrationCountsQuery` (Freshness card, Freshness page, critical
path, object freshness panel)
- `buildMaterializationLagQuery` (Indexes, Materialized Views, Largest
maintained, workflow graph, Shell plan insights)
- `buildObjectHydrationTimesQuery`, `buildObjectCreationTimesQuery`
(cluster page hydration timeline)
- `buildMaterializationLagQuery` no longer joins `mz_objects`. It only
supplied `type`, which none of its cluster-page callers read.
- The Shell's plan insights take each import's type, source type and
cluster from `useAllObjects`. `buildBlockedDependenciesQuery` and its
five catalog joins are gone.

### Plans on `mz_catalog_server`

`EXPLAIN` of the compiled queries, on v26.48 with the Console's
`search_path` and serializable isolation, reading the real relations.
The cells show the `Used Indexes` footer at 2,000 ids.

| Query | `main` | This PR |
| -- | -- | -- |
| Lag series (1h and 24h) | lag index full scan | lag index differential
join |
| Latest lag | lag index full scan | lag index differential join |
| Materialization lag | lag index full scan, `mz_objects` full scan |
lag index differential join |
| Hydration times (30s poll) | hydration times full scan | hydration
times lookup by replica |
| Creation times | object lifetimes full scan | object lifetimes
differential join |
| Hydration counts | full scan | full scan |

Up to 330 ids, `main` reads each of these by `lookup`. Hydration counts
scan in both versions, because `mz_hydration_statuses_ind` is keyed on
`(object_id, replica_id)`. The scan no longer evaluates a per-row `OR`
over every id.

### Timings

Compiled queries run on a local `mz_catalog_server` (v26.48-dev) with
the Console's session, reading the real catalog relations. Median of 5
runs:

| Query | ids | `main` | This PR |
| -- | -- | -- | -- |
| Latest lag | 400 | 2,632 ms | 11 ms |
| Materialization lag | 400 | 2,954 ms | 55 ms |
| Materialization lag | 2,000 | 14,766 ms | 255 ms |
| Hydration counts | 400 | 49 ms | 9 ms |
| Creation times | 400 | 27 ms | 11 ms |
| Hydration times | 400 | 25 ms | 10 ms |

At 20 ids both versions were within a millisecond of each other. That
includes hydration times and creation times, which took the fast path on
`main` and now build a dataflow.

At production scale, on a one-worker bench cluster. Copies of the
catalog relations carry production's indexes, with 3,000 objects, 24h of
per-minute lag readings (4.32M rows) and 63k object lifetime events.
Sequential runs, median of 9 (3 for `main` at 2,000 ids). Both versions
returned the same rows at 300 ids.

| Query | 50 ids | 300 ids | 2,000 ids |
| -- | -- | -- | -- |
| Lag series 1h | 30 → 28 ms | 163 → 144 ms | 169.7 s → 0.9 s |
| Lag series 24h | 56 → 48 ms | 285 → 267 ms | 170.5 s → 1.8 s |
| Latest lag | 21 → 19 ms | 110 → 92 ms | 169.9 s → 0.6 s |
| Hydration counts | 17 → 5 ms | 86 → 11 ms | 552 → 60 ms |
| Materialization lag | 83 → 32 ms | 450 → 128 ms | 170.8 s → 0.8 s |
| Hydration times | 16 → 7 ms | 80 → 14 ms | 450 → 67 ms |
| Creation times | 4.6 → 5.1 ms | 19 → 11 ms | 4.3 s → 61 ms |

The one slower cell is creation times at 50 ids, where `main` took the
fast path. Latest lag at 2,000 ids returned no rows on either version,
because by then the bench readings had aged past its two-minute window,
so `main`'s time there is the scan alone.

### Behavior changes

- `buildMaterializationLagQuery` returns a row for an id with no catalog
object, with null hydration and lag. Before, the `mz_objects` join
dropped it. Its callers look rows up by their own ids, so nothing
renders differently.
- Shell plan insights wait for the `allObjects` snapshot before
publishing. If that subscribe errors, they publish without the
blocked-dependency insights.

### Tests

- SQL plan tests that `EXPLAIN` each changed query at 400 ids on
`mz_catalog_server`. They fail on `main`'s builders and pass here.
- SQL result tests for the newest reading at 400 ids, and for a repeated
id in hydration counts. The latter fails if `buildIdListQuery` keeps
repeated ids.
- Unit tests for `toBlockedDependencies`, and for
`useBlockedDependencies` staying in loading until `allObjects` has its
snapshot.
- The `buildBlockedDependenciesQuery` SQL test is removed along with the
builder.

### Release notes

This release will reduce `mz_catalog_server` load from the Console on
clusters with more than 330 objects.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

This branch has not been deployed

No deployments
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants