pub enum AccessPath {
TableScan {
root: u32,
},
RowidSeek {
root: u32,
key: BoundExpr,
},
RowidRange {
root: u32,
low: Option<RangeBound>,
high: Option<RangeBound>,
},
IndexSeek {Show 13 fields
table_root: u32,
index_root: u32,
index_name: Vec<u8>,
equalities: Vec<BoundExpr>,
unconverted: Vec<usize>,
low: Option<RangeBound>,
high: Option<RangeBound>,
collations: Vec<Collation>,
descending: Vec<bool>,
columns: Vec<Option<u16>>,
without_rowid: bool,
key_entry_slots: Vec<usize>,
covering: Option<Vec<(u16, usize)>>,
},
RowidSeekUnion {
root: u32,
keys: Vec<BoundExpr>,
},
IndexSeekUnion {
table_root: u32,
index_root: u32,
index_name: Vec<u8>,
branches: Vec<IndexSeekBranch>,
collations: Vec<Collation>,
descending: Vec<bool>,
columns: Vec<Option<u16>>,
without_rowid: bool,
key_entry_slots: Vec<usize>,
covering: Option<Vec<(u16, usize)>>,
dedup: bool,
},
Subquery {
plan: Box<PhysicalPlan>,
width: usize,
correlated: bool,
},
Recursive {
seeds: Vec<(CompoundOp, PhysicalPlan)>,
steps: Vec<(CompoundOp, PhysicalPlan)>,
width: usize,
},
RecursiveSelf {
cte: usize,
},
VectorProbe {
root: u32,
index: Vec<u8>,
probe: Box<BoundExpr>,
depth: usize,
},
VirtualScan {
module: ModuleRef,
offer: Vec<VirtualConstraint>,
order_by: Vec<OrderSpec>,
chosen: Option<VirtualChoice>,
},
}Expand description
How one FROM term’s rows are produced.
Variants§
TableScan
Every row of the table, in rowid order.
RowidSeek
One row, found by rowid.
RowidRange
A contiguous run of rows, by rowid.
Fields
low: Option<RangeBound>The lower bound, when there is one.
high: Option<RangeBound>The upper bound, when there is one.
IndexSeek
Rows found through an index, then fetched from the table.
Fields
unconverted: Vec<usize>The positions in equalities whose value the seek compares without
converting it to the column’s affinity.
The comparison decides this, and only the planner sees the
comparison (task-2083). A seek converts the probe value to the
indexed column’s affinity, except when both sides of the = have
an affinity and neither is numeric: then WHERE converts nothing
and neither may the seek. That is SQLite’s codeAllEqualityTerms.
The executor used to decide it from the probe expression alone,
and a correlated subquery replaces the outer column with a
parameter before planning. The parameter has no affinity, so
(SELECT id FROM h WHERE h.a = s.k) with h.a TEXT and s.k
untyped converted the number 3 to '3' and found a row SQLite
does not.
A list of positions rather than a flag per equality because it is
almost always empty, and an empty Vec does not allocate. A flag per
equality cost two allocations to compile WHERE email = ?1, which
inillucent::budget counts.
low: Option<RangeBound>A range on the column after the equality prefix.
high: Option<RangeBound>The upper end of that range.
columns: Vec<Option<u16>>Which table column each index column holds.
None for a key the index computes: an index on lower(a) holds
a value no column of the table carries, and the probe value takes no
column affinity because there is no column to take it from - which
is SQLite’s rule and the reason this is an Option rather than a
position that would have to be invented.
key_entry_slots: Vec<usize>Where in each entry the row’s primary key sits, for a WITHOUT ROWID table read through a secondary index.
Such an entry ends with the primary key where a rowid table’s would end with a rowid, and that is how the row is then found. Empty for a rowid table, and empty when the index is the table’s own key - then the entry the seek landed on already is the row.
covering: Option<Vec<(u16, usize)>>Where in the index entry every column the query reads sits, when the index holds all of them.
An index entry is the indexed columns followed by the row’s key, so
a query that reads only those columns never has to go to the table
at all - which halves the descents and, on a range, is the whole
difference between a search and a scan. None means the query needs
something the entry does not carry, and the row is fetched.
The pairs are (record slot in the table, slot in the index entry).
The rowid is not in the list: it is always the entry’s last field
for a rowid table, and the compiler reads it with IdxRowid.
RowidSeekUnion
One row per key, found by rowid - several of
RowidSeek, concatenated.
What WHERE rowid IN (a, b, c) plans to on a rowid table: every branch
is the same one-row lookup RowidSeek uses alone, so the union is
nothing more than that lookup run once per key. A rowid is unique by
construction, so the only way two branches can name the same row is a
repeated key - a literal list is de-duplicated once, here, at plan
time; a key that is not a literal (a parameter, a correlated column)
cannot be compared this way, so the executor still checks each key
against the ones already probed before it seeks.
Fields
IndexSeekUnion
Rows found through one index - several seeks over the same tree, concatenated.
The branches are what a disjunction’s terms become once each is
individually seekable: x IN (a, b, c) is every branch a bare
equality on the same column, and a keyset page’s
(a=? AND b>?) OR a>? is two branches over the same composite index,
one an equality followed by a range and the other a range alone. The
fields outside branches describe the one index and table every
branch reads, because those never vary between branches - only the
equality prefix and the range do, which is exactly what a term of a
disjunction can differ in.
Fields
branches: Vec<IndexSeekBranch>One seek per branch, in the order they run.
collations: Vec<Collation>The collation of each index column a branch can reach, in order.
Sized to the deepest branch - the one whose equality prefix and range together reach furthest into the index - because a shallower branch simply does not read the columns past its own depth.
key_entry_slots: Vec<usize>Where in each entry the row’s primary key sits, for a WITHOUT ROWID table read through a secondary index. Empty for a rowid
table, and empty when the index is the table’s own key.
covering: Option<Vec<(u16, usize)>>Where in the index entry every column the query reads sits, when the index holds all of them.
dedup: boolWhether a row this union finds can also be found by a different branch, and so has to be checked against the rows already emitted before it is.
false only when the branches are proven disjoint by
construction - the keyset-range shape, where each branch’s
equality prefix pins a value no other branch’s range can reach -
which is what lets that shape stream straight through a LIMIT
with nothing held back to be deduplicated. An IN list is always
true: a non-literal value (a parameter, a correlated column)
cannot be proven distinct from another at plan time, so the
executor has to check.
Subquery
Rows produced by a nested query, materialised and then scanned.
Fields
plan: Box<PhysicalPlan>The plan that fills the store.
Whether the nested block reads a FROM term outside itself, and so has to be rebuilt for every row of the query that encloses it.
Recursive
Rows produced by a recursive CTE, filled by walking its own queue.
Fields
seeds: Vec<(CompoundOp, PhysicalPlan)>The arms that do not reference the CTE, in order.
steps: Vec<(CompoundOp, PhysicalPlan)>The arms that do.
RecursiveSelf
The one row of a recursive CTE’s queue the fill loop is on.
VectorProbe
The k nearest vectors, from an index a module owns.
A TopN over a distance is a different question from a scan. The
rows are chosen by the index rather than filtered out of a walk, so the
path carries the probe and the depth rather than a range: the module is
asked for k candidates and the plan’s own ORDER BY then rescores
them exactly, over an ORDER BY function matching the index’s metric.
Fields
VirtualScan
Rows produced by a virtual table’s module.
Fields
offer: Vec<VirtualConstraint>The constraints offered to best_index, in the order the module
will see them.
chosen: Option<VirtualChoice>What the module answered, once it has been asked.
It is None while the plan is still the planner’s, and filled in by
a pass that runs before compilation. Keeping the two apart is what
lets the planner stay a pure function of the SQL and one catalog
generation while the program still carries a real plan.
Implementations§
Source§impl AccessPath
impl AccessPath
Sourcepub fn describe(&self, table: &str) -> String
pub fn describe(&self, table: &str) -> String
Returns a one-line description, which is what EXPLAIN QUERY PLAN
renders and what a performance test asserts on.
Sourcepub fn describe_over(&self, table: &str, info: Option<&TableInfo>) -> String
pub fn describe_over(&self, table: &str, info: Option<&TableInfo>) -> String
Returns the same line, naming the columns an index seek compares.
(a=?) rather than (?=?). The reference names the key column, and
it is the one part of the line a reader uses to tell “this index” from
“the other index on the same table”. The declaration is passed in
because an access path carries the index’s name and not its columns -
which is the right thing for a plan to carry, and the wrong thing to
render a description from.
@param table - the name the query calls the term @param info - the table’s declaration, when the caller has it