inillucent_sql/bind/column_use.rs
1//! What a query reads of one FROM term, which decides whether an index covers it.
2//!
3//! Invariant: **a `ColumnUse` that cannot list every read says so with `opaque`, and an opaque
4//! answer is never covered.** The planner reads an index instead of the table only when every
5//! slot the query needs is in the index, so a read missed here is a column read from an index
6//! that does not hold it.
7
8use super::BoundExpr;
9
10/// Which of one FROM term's columns a query reads.
11#[derive(Clone, Debug, Default, PartialEq)]
12pub struct ColumnUse {
13 /// The record slots read, ascending and without duplicates.
14 pub columns: Vec<u16>,
15 /// Whether the term's rowid is read.
16 pub rowid: bool,
17 /// Whether something was met whose column reads cannot be enumerated.
18 ///
19 /// An opaque use is never coverable. It is set rather than ignored because
20 /// the whole value of this answer is that it is complete: a covering path
21 /// that turned out not to cover a column would read it from an index that
22 /// does not hold it.
23 pub opaque: bool,
24 /// The module's auxiliary functions this term is asked for, in the order
25 /// they were met, as a folded name and the arguments after the table.
26 ///
27 /// `score(t)` and `bm25(t)` read the *cursor* rather than a column, so they
28 /// are neither a column read nor an opaque one: the module can answer them
29 /// per row, and a materialised virtual scan carries the answers beside the
30 /// columns. Recorded here because this is already the answer to "what does
31 /// this term have to produce", and a second list would be a second thing
32 /// that can disagree with it.
33 /// **The arguments, not their count.** `highlight(t, 0, '[', ']')` and
34 /// `bm25(t, 10.0, 1.0)` are answered by the module from the cursor, and the
35 /// module cannot answer either without the values - which used to be
36 /// dropped here and replaced with an empty list at the call, so every
37 /// auxiliary function saw no arguments at all. Two calls of one name with
38 /// different arguments are also two different answers, so the arguments are
39 /// part of what identifies a slot rather than a detail hanging off one.
40 pub functions: Vec<(Vec<u8>, Vec<BoundExpr>)>,
41 /// The record slots read by anything other than the block's `WHERE` clause.
42 ///
43 /// A partial index whose predicate the `WHERE` repeats holds that predicate true for every
44 /// entry, so a column the `WHERE` reads only for that test does not have to be in the index
45 /// for the index to cover the query. This is the part of `columns` that is read for other
46 /// reasons.
47 pub outside_filter: Vec<u16>,
48}
49
50impl ColumnUse {
51 /// Records that one slot is read.
52 pub fn add(&mut self, slot: u16) {
53 if let Err(position) = self.columns.binary_search(&slot) {
54 self.columns.insert(position, slot);
55 }
56 }
57
58 /// Records that one of the module's auxiliary functions is read.
59 ///
60 /// @param name - the function's folded name
61 /// @param arguments - the arguments after the table
62 pub fn add_function(&mut self, name: &[u8], arguments: &[BoundExpr]) {
63 let held = (name.to_vec(), arguments.to_vec());
64 if !self.functions.contains(&held) {
65 self.functions.push(held);
66 }
67 }
68
69 /// Folds another use into this one.
70 pub fn merge(&mut self, other: &ColumnUse) {
71 for slot in &other.columns {
72 self.add(*slot);
73 }
74 self.rowid |= other.rowid;
75 self.opaque |= other.opaque;
76 for slot in &other.outside_filter {
77 if let Err(position) = self.outside_filter.binary_search(slot) {
78 self.outside_filter.insert(position, *slot);
79 }
80 }
81 for (name, arguments) in &other.functions {
82 self.add_function(name, arguments);
83 }
84 }
85}
86
87impl super::BoundSelect {
88 /// Adds what a `WHERE` reads of one FROM term, leaving out the term's own
89 /// table function arguments.
90 ///
91 /// **An argument is the function's input, not a column it hands back.**
92 /// `json_each(j.doc)` is bound as `json = j.doc` on the hidden `json`
93 /// column, and the module applies it. Counting it as a read made the scan
94 /// ask the cursor for `json` on every row, which is the whole document:
95 /// a 20,000 element array was copied 20,000 times, and `SELECT count(*)
96 /// FROM j, json_each(j.doc)` took seven seconds where SQLite takes a tenth.
97 /// An argument the module does not apply is offered back as a recheck, and
98 /// the scan reads the column for that.
99 ///
100 /// @param filter - the block's `WHERE`
101 /// @param source - the statement-wide number of the FROM term
102 /// @param into - the reads found so far
103 pub(super) fn filter_columns_read(
104 &self,
105 filter: &BoundExpr,
106 source: usize,
107 into: &mut ColumnUse,
108 ) {
109 let table = self
110 .sources
111 .iter()
112 .find(|term| term.id == source)
113 .map(|term| term.table.as_ref())
114 .filter(|table| table.kind == crate::catalog_view::TableKind::Virtual);
115 let Some(table) = table else {
116 filter.columns_read(source, into);
117 return;
118 };
119 let mut conjuncts = Vec::new();
120 crate::plan::split_conjunction(filter, &mut conjuncts);
121 for conjunct in &conjuncts {
122 let argument = match conjunct {
123 BoundExpr::Compare {
124 op: crate::ast::BinaryOp::Equal,
125 left,
126 ..
127 } => match left.as_ref() {
128 BoundExpr::Column {
129 source: owner,
130 column,
131 ..
132 } => {
133 *owner == source
134 && table
135 .columns
136 .get(usize::from(*column))
137 .is_some_and(|declared| declared.hidden)
138 }
139 _ => false,
140 },
141 _ => false,
142 };
143 if argument {
144 // The value side may still read another term, which is that
145 // term's read, not this one's.
146 if let BoundExpr::Compare { right, .. } = conjunct {
147 right.columns_read(source, into);
148 }
149 continue;
150 }
151 conjunct.columns_read(source, into);
152 }
153 }
154}