inillucent-sql 2.1.1

//! Whether a query's `WHERE` proves a partial index's predicate.
//!
//! Invariant: **an index is chosen only when every row the query wants is in
//! it.** A partial index holds the rows its predicate accepted and no others,
//! so reading one for a query whose rows it does not all hold answers the
//! question with rows missing - and the rows missing are exactly the ones the
//! predicate excludes, which is the hardest kind of wrong answer to notice.
//! Every rule here is therefore sound on its own rather than likely, and a
//! rule nobody could write is an index left unchosen.
//!
//! Here rather than in [`super`] because `plan.rs` is at its recorded size and
//! these two functions are one question its caller asks once.

use super::*;

/// Reports whether a query's `WHERE` implies a partial index's predicate.
///
/// **Two rules, both sound, and nothing that needs a theorem prover.**
///
/// The first is the predicate appearing, unchanged, as a conjunct of the
/// statement's `WHERE`. So an index declared `WHERE b > 5` answers
/// `WHERE b > 5 AND a = 1` and does not answer `WHERE b > 6`, even though the
/// second implies the first. Proving the general implication is a theorem
/// prover in the planner, and every case it got wrong would be a query
/// silently missing exactly the rows the predicate excludes.
///
/// The second is `IS NOT NULL`, and it was measured rather than reasoned about
/// (task-1913). This function's comment used to call the verbatim rule
/// "SQLite's rule"; the pinned 3.53.4 answers `SELECT n FROM t WHERE n = 1`
/// with `SEARCH t USING COVERING INDEX t_n (n=?)` over an index declared
/// `WHERE n IS NOT NULL`, and this engine scanned the table. That index is how
/// SQLite spells "unique among the rows that have one", so the shape is
/// common and the whole point of declaring it was to be searched.
///
/// The rule added is the narrowest one that answers it: a comparison is three
/// valued, so `n = 1` is *true* only when `n` is not NULL - and the same holds
/// for `<`, `<=`, `>`, `>=` and `<>`. A conjunct comparing the operand the
/// predicate asks about therefore proves the predicate. `IS` and `IS NOT` are
/// deliberately not comparisons here: `n IS NULL` is true precisely when `n`
/// is NULL, so reading it as proof of the opposite would choose an index that
/// holds none of the rows the query wants.
///
/// `false` when the index's own predicate could not be bound, which is what
/// leaves an index the planner cannot reason about unchosen rather than chosen
/// on a guess.
///
/// @param computed - the index's bound expressions, when it has them
/// @param terms - the statement's `WHERE` conjuncts
pub(super) fn implies(computed: Option<&crate::dml::BoundIndexExprs>, terms: &[BoundExpr]) -> bool {
    let Some(held) = computed else {
        return false;
    };
    let Some(predicate) = held.predicate.as_ref() else {
        return false;
    };
    if terms.iter().any(|term| term == predicate) {
        return true;
    }
    let BoundExpr::IsNull {
        negated: true,
        operand,
    } = predicate
    else {
        return false;
    };
    terms
        .iter()
        .any(|term| compares_operand(term, operand.as_ref()))
}

/// Returns what a partial index has to hold to cover a query that repeats its predicate.
///
/// Every entry of a partial index satisfies the predicate, so a conjunct that is the predicate
/// itself reads nothing from the row: the pinned release plans `SELECT 1 FROM t WHERE a = ? AND
/// flag = 0` over an index on `(a)` declared `WHERE flag = 0` as a `COVERING INDEX` although
/// `flag` is in no entry. The answer is the columns read outside the `WHERE`, plus the columns
/// of every other conjunct, and the positions of the conjuncts that are the predicate, which the
/// path then does not have to test again. `None` when no conjunct is the predicate.
///
/// @param id - the statement-wide number of the FROM term
/// @param needed - what the whole query reads of the term
/// @param terms - the statement's `WHERE` conjuncts
/// @param computed - the index's bound expressions
pub(super) fn needed_beyond_predicate(
    id: usize,
    needed: &ColumnUse,
    terms: &[BoundExpr],
    computed: Option<&crate::dml::BoundIndexExprs>,
) -> Option<(ColumnUse, Vec<usize>)> {
    let predicate = computed?.predicate.as_ref()?;
    let implied: Vec<usize> = terms
        .iter()
        .enumerate()
        .filter(|(_, term)| *term == predicate)
        .map(|(position, _)| position)
        .collect();
    if implied.is_empty() {
        return None;
    }
    let mut reduced = ColumnUse {
        columns: needed.outside_filter.clone(),
        rowid: needed.rowid,
        opaque: needed.opaque,
        functions: needed.functions.clone(),
        outside_filter: needed.outside_filter.clone(),
    };
    for (position, term) in terms.iter().enumerate() {
        if !implied.contains(&position) {
            term.columns_read(id, &mut reduced);
        }
    }
    Some((reduced, implied))
}

/// Reports whether a conjunct is a comparison that one operand has to be
/// non-NULL to satisfy.
///
/// Only [`BoundExpr::Compare`], and only its six comparison operators. A
/// `Compare` holding an arithmetic operator is not a conjunct the binder
/// produces, and the match is written out rather than defaulted so that an
/// operator added later is a compilation error rather than a wrong answer.
///
/// @param term - one conjunct of the statement's `WHERE`
/// @param operand - the expression the index's predicate asks about
pub(super) fn compares_operand(term: &BoundExpr, operand: &BoundExpr) -> bool {
    let BoundExpr::Compare {
        op, left, right, ..
    } = term
    else {
        return false;
    };
    if !matches!(
        op,
        BinaryOp::Equal
            | BinaryOp::NotEqual
            | BinaryOp::Less
            | BinaryOp::LessEqual
            | BinaryOp::Greater
            | BinaryOp::GreaterEqual
    ) {
        return false;
    }
    left.as_ref() == operand || right.as_ref() == operand
}