Skip to main content

sqlive/
scope_order.rs

1//! A statement that orders by columns of its tables, or expressions over one
2//! table's columns, and has a LIMIT with no OFFSET, whose full run depends
3//! only on the rows that sort at or before its last row (ยง4).
4//!
5//! When a run returns as many rows as its LIMIT, a row that sorts after its
6//! last row can't appear in the result: every result row it would give sorts
7//! after the rows already there. So the run's scopes also require a row to
8//! sort at or before the last row, in the ORDER BY's directions, and the next
9//! run sets that bound again from its own last row. A row equal to the last
10//! one could sort before it, so it passes. A run that returned fewer rows
11//! than its LIMIT holds every row its WHERE allows, and keeps its scopes.
12//!
13//! The ORDER BY's terms fall into runs, each of consecutive terms over one
14//! table. A result row sorts at or before the last row when its values of
15//! the first run sort before the last row's, or equal them and the rest sort
16//! at or before. So the first run's table takes the rows whose own terms sort
17//! at or before the last row's values of that run. A later run's table takes
18//! those rows too, and the rows that join, for some earlier run, a row of
19//! that run's table that sorts before the last row's values of that run,
20//! which a write looks up as it looks up a join (`scope_lookup.rs`). A table
21//! that takes no value from each earlier run's table has no bound.
22//!
23//! sqlive takes the last row's values from the result columns that return
24//! them, so each ORDER BY term is a result column of the statement's only
25//! SELECT, written as the term writes it, with no COLLATE and no NULLS FIRST
26//! or LAST. Each term reads one table of that SELECT: a stored column of
27//! BINARY collation, whose values sqlive compares as SQLite does; or an
28//! expression over such columns that SQLite can evaluate row by row, or a
29//! generated column whose expression names only such columns, whose value in
30//! a changed row a write asks SQLite to compare with the last row's
31//! (`scope_row.rs`). No such table is the right side of a LEFT JOIN. There,
32//! when a write adds a row that matches a left row that had no match, SQLite
33//! no longer returns the row of NULLs it returned for that left row, and that
34//! row of NULLs can sort before the last row. The SELECT has no GROUP BY and
35//! calls no aggregate or window function in its result columns, since there
36//! one result row's values depend on many table rows.
37
38use std::cmp::Ordering;
39use std::sync::Arc;
40
41use crate::from_item::ColumnValue;
42use crate::row_scope::RowScope;
43use crate::scope_plan::{is_name, Membership, Planner};
44use crate::scope_row::{item_row_term, RowCondition, RowExpression, RowTerm, RowTest};
45use crate::scope_term::{operand, Affinity, Operand};
46use crate::select_syntax::{order_term, parts, Functions, OrderTerm, Part};
47use crate::sql::unparenthesized;
48use crate::sql_value::SqlValue as Value;
49use rusqlite::Connection;
50use sqlite3_parser::ast::{
51    Distinctness, Expr, OneSelect, ResultColumn, Select, SortOrder, SortedColumn,
52};
53
54/// A statement's order and LIMIT, which a full run's last row bounds.
55pub(crate) struct SortedLimit {
56    /// The ORDER BY's terms, in runs of consecutive terms over one source.
57    runs: Vec<SortRun>,
58    limit: RunLimit,
59}
60
61/// A LIMIT whose value a run's parameters can give.
62#[derive(Clone, Debug)]
63pub(crate) struct RunLimit(Operand);
64
65impl RunLimit {
66    /// The LIMIT's value for a run bound to `parameters`, or `None` when it
67    /// is not a positive integer.
68    pub(crate) fn value(&self, parameters: &[Value]) -> Option<usize> {
69        let Value::Integer(limit) = self.0.value(parameters) else {
70            return None;
71        };
72        usize::try_from(*limit).ok().filter(|limit| *limit > 0)
73    }
74}
75
76/// One SELECT that keeps the first rows of its ORDER BY by a LIMIT with no
77/// OFFSET, each of whose rows comes of one row of its tables: no GROUP BY,
78/// HAVING or WINDOW clause, and no aggregate or window function in its
79/// result columns.
80pub(crate) struct OrderedLimit<'a> {
81    pub(crate) columns: &'a [ResultColumn<'a>],
82    pub(crate) where_clause: Option<&'a Expr<'a>>,
83    pub(crate) distinct: bool,
84    pub(crate) order_by: &'a [SortedColumn<'a>],
85    pub(crate) limit: RunLimit,
86}
87
88/// `select` as an `OrderedLimit`, when it is one; the connection's
89/// `functions` tell an aggregate call.
90pub(crate) fn ordered_limit<'a>(
91    connection: &Connection,
92    functions: &Functions,
93    select: &'a Select<'a>,
94) -> rusqlite::Result<Option<OrderedLimit<'a>>> {
95    let (Some(limit), Some(order_by)) = (select.limit, select.order_by) else {
96        return Ok(None);
97    };
98    if limit.offset.is_some() || select.body.compounds.is_some() {
99        return Ok(None);
100    }
101    let OneSelect::Select {
102        distinctness,
103        columns,
104        where_clause,
105        group_by: None,
106        having: None,
107        window_clause: None,
108        ..
109    } = &select.body.select
110    else {
111        return Ok(None);
112    };
113    let mut found = Vec::new();
114    for column in columns.iter() {
115        if let ResultColumn::Expr(expr, _) = column {
116            crate::select_syntax::parts(expr, &mut found);
117        }
118    }
119    if found.iter().any(|part| part.many_rows(functions)) {
120        return Ok(None);
121    }
122    let Some(limit) = operand(connection, &limit.expr, Affinity::Blob)? else {
123        return Ok(None);
124    };
125    Ok(Some(OrderedLimit {
126        columns,
127        where_clause: *where_clause,
128        distinct: matches!(distinctness, Some(Distinctness::Distinct)),
129        order_by,
130        limit: RunLimit(limit),
131    }))
132}
133
134/// Consecutive ORDER BY terms over one source.
135struct SortRun {
136    /// The source whose rows the terms sort.
137    source: usize,
138    terms: Vec<SortTerm>,
139}
140
141/// One ORDER BY term of a sorted source.
142struct SortTerm {
143    /// What it sorts the source's rows by.
144    key: SortKey,
145    /// Whether it sorts in descending order.
146    descending: bool,
147    /// The result column, from zero, that returns its value.
148    position: usize,
149}
150
151/// What an ORDER BY term sorts its source's rows by.
152enum SortKey {
153    /// A stored column, lowercase, whose values sqlive compares itself.
154    Column(String),
155    /// An expression over the source's stored columns, whose value in a
156    /// changed row a write asks SQLite for: a generated column's, or one the
157    /// ORDER BY writes.
158    Expression(RowExpression),
159}
160
161impl SortKey {
162    /// The rows whose key is NULL, or isn't when `not`, for a run bound to
163    /// `parameters`.
164    fn null(&self, not: bool, parameters: &[Value]) -> RowScope {
165        match self {
166            Self::Column(column) => RowScope::Null { column: column.clone(), not },
167            Self::Expression(RowExpression { term, .. }) => {
168                row(term, parameters, RowTest::Null { not })
169            }
170        }
171    }
172
173    /// The rows whose key compares with `value`, which isn't NULL, as
174    /// `ordering`, for a run bound to `parameters`.
175    fn compare(&self, value: &Value, ordering: Ordering, parameters: &[Value]) -> RowScope {
176        match self {
177            Self::Column(column) => RowScope::Compare {
178                column: column.clone(),
179                value: value.clone(),
180                ordering,
181                inclusive: false,
182            },
183            Self::Expression(RowExpression { term, affinity }) => row(
184                term,
185                parameters,
186                RowTest::Compare { ordering, value: value.clone(), affinity: *affinity },
187            ),
188        }
189    }
190}
191
192/// The rows a write asks SQLite whether `test` holds of `term` for.
193fn row(term: &Arc<RowTerm>, parameters: &[Value], test: RowTest) -> RowScope {
194    RowScope::Row(Arc::new(RowCondition {
195        term: Arc::clone(term),
196        parameters: parameters.to_vec(),
197        test,
198    }))
199}
200
201/// Where a run finds the row its scope ends at.
202pub struct LastRow {
203    /// How many rows the run must return for its last row to bound its
204    /// scope: the LIMIT.
205    pub limit: usize,
206    /// The result columns, from zero, that return the ORDER BY's values, in
207    /// its order.
208    positions: Vec<usize>,
209}
210
211impl LastRow {
212    /// The ORDER BY's values in `row`, in its order.
213    pub fn values(&self, row: &rusqlite::Row<'_>) -> rusqlite::Result<Vec<Value>> {
214        self.positions.iter().map(|position| Ok(row.get_ref(*position)?.into())).collect()
215    }
216}
217
218impl SortedLimit {
219    /// Where a run bound to `parameters` finds its last row, or `None` when
220    /// the LIMIT's value is not a positive integer.
221    pub(crate) fn last_row(&self, parameters: &[Value]) -> Option<LastRow> {
222        Some(LastRow {
223            limit: self.limit.value(parameters)?,
224            positions: self
225                .runs
226                .iter()
227                .flat_map(|run| &run.terms)
228                .map(|term| term.position)
229                .collect(),
230        })
231    }
232
233    /// The bound of `source`'s rows for a run bound to `parameters` whose
234    /// last row's ORDER BY values are `last`, when the order sorts it: its
235    /// first run's terms at or before their values, or, for each earlier
236    /// run, a row it joins of that run's source that sorts before that run's
237    /// values. `memberships` are its own, and `looked_up` gives the rows
238    /// whose membership finds a row of its partner that passes the given
239    /// scope too. `None` when it takes no value from an earlier run's source.
240    pub(crate) fn bound(
241        &self,
242        source: usize,
243        last: &[Value],
244        parameters: &[Value],
245        memberships: &[Membership],
246        looked_up: impl Fn(&Membership, RowScope) -> RowScope,
247    ) -> Option<RowScope> {
248        let mut earlier = Vec::new();
249        let mut values = last;
250        for run in &self.runs {
251            let (own, rest) = values.split_at(run.terms.len());
252            values = rest;
253            if run.source == source {
254                let at_or_before = sorted_before(&run.terms, own, parameters, Some(RowScope::All))
255                    .expect("a tied row passes, so some row does");
256                return Some(
257                    earlier
258                        .into_iter()
259                        .rev()
260                        .fold(at_or_before, |later, sooner: RowScope| sooner.or(later)),
261                );
262            }
263            let membership = memberships.iter().find(|found| found.partner == run.source)?;
264            if let Some(before) = sorted_before(&run.terms, own, parameters, None) {
265                earlier.push(looked_up(membership, before));
266            }
267        }
268        None
269    }
270}
271
272/// The order and LIMIT of `select`, the statement whose only core is `core`,
273/// when a full run's last row can bound its scope.
274pub(crate) fn sorted_limit(
275    connection: &Connection,
276    planner: &Planner,
277    select: &Select<'_>,
278    core: usize,
279) -> rusqlite::Result<Option<SortedLimit>> {
280    let Some(OrderedLimit { columns, order_by, limit, .. }) =
281        ordered_limit(connection, planner.functions, select)?
282    else {
283        return Ok(None);
284    };
285    let mut runs: Vec<SortRun> = Vec::new();
286    for term in order_by.iter() {
287        if term.nulls.is_some() {
288            return Ok(None);
289        }
290        let Some((position, item, key)) = sort_term(planner, core, columns, &term.expr) else {
291            return Ok(None);
292        };
293        let from = &planner.items[item];
294        if from.core != core || from.source.table.is_none() || from.left_on.is_some() {
295            return Ok(None);
296        }
297        let term = SortTerm { key, descending: term.order == Some(SortOrder::Desc), position };
298        match runs.last_mut() {
299            Some(run) if run.source == item => run.terms.push(term),
300            _ => runs.push(SortRun { source: item, terms: vec![term] }),
301        }
302    }
303    Ok((!runs.is_empty()).then_some(SortedLimit { runs, limit }))
304}
305
306/// The result column that returns the ORDER BY term `expr`, the source whose
307/// rows it sorts and what it sorts them by, when a run's last row can bound
308/// them. A bare name that matches a result column's alias means that result
309/// column, as SQLite reads an ORDER BY; any other name means the column it
310/// resolves to, and any other expression the result column that writes it
311/// the same way.
312fn sort_term(
313    planner: &Planner,
314    core: usize,
315    columns: &[ResultColumn<'_>],
316    expr: &Expr<'_>,
317) -> Option<(usize, usize, SortKey)> {
318    let (position, sorted) = match order_term(columns, expr) {
319        OrderTerm::Alias(position, listed) => (position, listed),
320        OrderTerm::Expr(expr) => {
321            let resolved = is_name(expr).then(|| planner.resolve(core, expr)).flatten();
322            // sqlive doesn't know how many columns a `*` adds, so it can't
323            // tell the position of a column after one.
324            let position = columns
325                .iter()
326                .map_while(|column| match column {
327                    ResultColumn::Expr(expr, _) => Some(expr),
328                    ResultColumn::Star | ResultColumn::TableStar(_) => None,
329                })
330                .position(|listed| match &resolved {
331                    Some(resolved) => {
332                        is_name(listed) && planner.resolve(core, listed).as_ref() == Some(resolved)
333                    }
334                    None => unparenthesized(listed) == expr,
335                })?;
336            (position, expr)
337        }
338        OrderTerm::Position(_) | OrderTerm::Unknown => return None,
339    };
340    if is_name(sorted) {
341        let (item, column) = planner.resolve(core, sorted)?;
342        let from = &planner.items[item];
343        let key = match from.columns.value(&column)? {
344            ColumnValue::Compared(_) => SortKey::Column(column),
345            ColumnValue::Generated(generated) => SortKey::Expression(generated.clone()),
346            ColumnValue::Unknown | ColumnValue::Hidden => return None,
347        };
348        return Some((position, item, key));
349    }
350    let mut found = Vec::new();
351    parts(sorted, &mut found);
352    // A COLLATE gives the ORDER BY its collation, by which sqlive doesn't
353    // compare the last row's value.
354    if found.iter().any(|part| matches!(part, Part::Collation)) {
355        return None;
356    }
357    let mut items = found.iter().filter_map(|part| match part {
358        Part::Name(name) => Some(planner.resolve(core, name).map(|(item, _)| item)),
359        _ => None,
360    });
361    let item = items.next()??;
362    if !items.all(|other| other == Some(item)) {
363        return None;
364    }
365    let term = item_row_term(planner, core, item, sorted, &found)?;
366    Some((position, item, SortKey::Expression(RowExpression { term, affinity: Affinity::Blob })))
367}
368
369/// The rows that sort before `last`, the last row's values of the terms
370/// `terms`, or equal it and pass `tied`, for a run bound to `parameters`:
371/// lexicographically, each term in its direction, NULL first in ascending
372/// order and last in descending, as SQLite sorts. `None`, for `tied` too,
373/// passes no row.
374fn sorted_before(
375    terms: &[SortTerm],
376    last: &[Value],
377    parameters: &[Value],
378    tied: Option<RowScope>,
379) -> Option<RowScope> {
380    let mut scope = tied;
381    for (term, value) in terms.iter().zip(last).rev() {
382        let key = &term.key;
383        let equal = match value {
384            Value::Null => key.null(false, parameters),
385            _ => key.compare(value, Ordering::Equal, parameters),
386        };
387        // No value sorts before NULL in ascending order.
388        let before = match (term.descending, value) {
389            (false, Value::Null) => None,
390            (false, _) => {
391                Some(key.null(false, parameters).or(key.compare(value, Ordering::Less, parameters)))
392            }
393            (true, Value::Null) => Some(key.null(true, parameters)),
394            (true, _) => Some(key.compare(value, Ordering::Greater, parameters)),
395        };
396        let tied = scope.map(|scope| equal.and(scope));
397        scope = match (before, tied) {
398            (Some(before), Some(tied)) => Some(before.or(tied)),
399            (before, None) => before,
400            (None, tied) => tied,
401        };
402    }
403    scope
404}