This sounds like a fantastic 1.0 costing approach!
I don't think the caveats (at the end) are a huge deal - in fact, we are
thinking we may hold off on exposing cross-pollination in the first release, as
there seem to be other knobs that can be turned (at least from what experiments
have shown so far) to achieve comparable performance in recall and time - so it
doesn't seem justified (at least not yet) to offer that knob. (Fewer knobs is
better from a user experience standpoint. And it seems that there is now an
understanding of what to default the other knob settings to in order to achieve
~90% recall and nice execution time improvement.)
Cheers,
Mike
On 9/11/26 9:08 AM, Rithwik Koul wrote:
DISCUSS
1. The problem
A vector (VTREE) index had no cost. A late rewrite rule looked for the
top-k shape
LIMIT k → ORDER BY ann_distance(field, $q, metric) → [optional WHERE]
→ scan
and took the first index whose vector field matched, whose similarity
metric matched, and whose INCLUDE list covered the predicate fields. It
then used that index, unconditionally. Consequences:
-
An approximate plan ran where an exact one was cheaper.
-
Two eligible indexes were never compared. First match won; the second
candidate was never looked at.
-
The advisor could only recommend by structure. With no cost, "recommend
a vector index" meant "a rule would have matched one", not "it is the
cheapest way to answer this".
The optimizer's existing index costing could not be borrowed as-is, for two
reasons:
-
it is only entered when the leaf carries a filter, so a WHERE-less ANN
query never reached it;
-
the losing candidates it rejects are communicated through a skip
annotation that the ANN rewrite never consulted.
2. What the change does
The vector search becomes a third access method competing on cost in the
same plan registry as the full scan and the secondary-index scan. The
optimizer cost it, compares it against the exact alternatives, keeps the
winner, and tells the ANN rewrite rule which indexes it is no longer
allowed to use.
BEFORE AFTER
cost model cost model
├─ table scan ├─ table scan
└─ index scan (needs a filter) ├─ index scan (needs a filter)
└─ vector scan ◄──
rewrite rule rewrite rule
└─ first matching vector index └─ honours the optimizer's
verdict
(never costed, never compared)
3. The cost model3.1 Why the existing index primitive does not fit
Every other index cost in the model is driven by selectivity: how much of
the collection the predicate keeps. A similarity search does not work that
way. It probes a fixed set of clusters and reranks a fixed number of
candidates, so its cost barely moves with what the predicate selects. What
actually sets it is k, the probe fraction, the rerank multiplier, and the
geometry of the index itself. So the vector plan gets its own primitive,
parameterized by geometry instead of selectivity.
3.2 Search geometry
-
A new, self-contained piece of the cost package answers one question:
how much of one vector index does one similarity search touch? It derives,
per storage partition (each partition searches its own index over its own
rows)
-
Entry width matters only because it decides how many pages a probed
cluster spans, so it is derived from what the index actually stores → its
primary key, its INCLUDE fields, and how the embedding is represented
rather than assumed constant.
3.3 What the vector plan is charged
The optimizer's cost object carries six components and collapses to a
scalar at comparison time. The vector plan contributes:
Charged Component
Description & Formula
Routing evaluations
Charged at one evaluation per centroid encountered while descending the
hierarchy.
Distance evaluations
Charged at one evaluation per entry across all probed clusters.
Page reads
Covers the physical data pages occupied by the probed clusters.
Rerank fetch
Calculated as fetching k × k_multiplier candidates from the primary index,
including the preceding key sort.
3.4 The decision surface
The model was validated over 206 scenarios driven through the real cost
classes
rerank fetch F = k × k_multiplier, relative to collection size N
- F ≲ 0.1·N ──────────────► VECTOR SCAN wins
- F ≳ 0.1·N ──────────────► TABLE SCAN wins
- predicate selectivity ≲ 0.1–0.3 % on a field that has both a
secondary index and an INCLUDE entry ─────► INDEX SCAN wins
4. Selection rules
-
A tie goes to the exact plan. The vector plan replaces the incumbent
only if it is strictly cheaper. An exact answer is never semantically worse
than an approximate one, so equal cost means take the exact one.
-
Between two vector indexes: cheapest first; ties broken by narrower data
entries, then by index name, so compilation is deterministic.
-
Search effort stays user-supplied. The probe fraction and the candidate
multiplier trade cost against recall
5. Known modelling gaps
Stated deliberately, because they bound how much to trust a verdict:
-
The vector search cost model currently under-costs execution by ignoring
factors such as cross-pollination. This intentional adjustment ensures
vector search is generally favored over full scans and B-tree indexes.
-
The candidate count is assumed unchanged — whereas a selective filter
really forces the search to probe further to still return k rows.
