inillucent_sql/

cost.rs

//! What a plan costs, and which order to visit the FROM terms in.
//!
//! Invariant: cost is measured in the same currency SQLite measures it in - the
//! base-2 logarithm of the number of rows a step touches, scaled - so that a
//! plan comparison means the same thing in both engines. That is not a stylistic
//! choice. The acceptance test for this phase compares which *plan* each engine
//! picks, and two engines using different currencies disagree on ties for
//! reasons that are not defects.
//!
//! Absent statistics the numbers are SQLite's own guesses: a table holds about
//! a million rows, an equality selects a tenth of them, a range a quarter, and a
//! unique index exactly one. Those defaults are what make an unanalysed plan
//! match the reference's, so they are written out here rather than being
//! whatever seemed reasonable.

/// The row count assumed for a table nothing has measured.
///
/// SQLite's `SQLITE_DEFAULT_ROWEST`. It is deliberately large: with a small
/// guess every index looks pointless, and the plan for an unanalysed schema
/// would be a full scan of everything.
pub const DEFAULT_ROWS: f64 = 1_048_576.0;

/// The share of a table an equality on an indexed column is assumed to select.
///
/// Used only where no index is involved. An equality *on an index* is estimated
/// by [`default_equality_rows`] instead, which is an absolute count rather than
/// a share - see the note there for why the difference matters.
pub const EQUALITY_SHARE: f64 = 10.0;

/// How many rows an equality on an unmeasured index is assumed to match.
///
/// SQLite's `sqlite3DefaultRowEst` fills an unanalysed index's estimates with
/// these, as LogEst 33, 32, 30, 28, 26, 23 - about twenty rows for the first
/// equality column, falling to ten and staying there. They are *counts*, not
/// fractions of the table, and that distinction is the whole point: somebody
/// who indexed a column and then compared it for equality was pinning down a
/// row, not selecting a tenth of the table, and the bigger the table the more
/// true that is.
///
/// Getting this wrong is not a rounding error, it reverses join orders. With a
/// tenth-of-the-table estimate the planner priced a seek into a 25,000 row
/// table at 2,500 rows, decided the seek was not worth it, and scanned that
/// table once per outer row instead - which took a benchmark round from seconds
/// to the better part of an hour, and put a `SCAN` where the reference had a
/// `SEARCH ... USING INDEX`.
const DEFAULT_EQUALITY_ROWS: [f64; 6] = [20.0, 18.0, 15.0, 13.0, 11.0, 10.0];

/// Returns how many rows an equality on an unmeasured index is assumed to match.
///
/// Never more than the table holds: a two-row table cannot return twenty.
/// @param equalities - how many leading index columns the search pins down
/// @param rows - how many rows the table is estimated to hold
pub fn default_equality_rows(equalities: usize, rows: f64) -> f64 {
    let at = equalities.max(1).saturating_sub(1);
    let estimate = DEFAULT_EQUALITY_ROWS
        .get(at)
        .copied()
        .unwrap_or_else(|| DEFAULT_EQUALITY_ROWS.last().copied().unwrap_or(10.0));
    estimate.min(rows.max(1.0))
}

/// The share a range on an indexed column is assumed to select.
pub const RANGE_SHARE: f64 = 4.0;

/// What it costs to fetch a table row once an index has found its key.
///
/// A second descent of a second B-tree, so it is charged per matching row and
/// is what makes a covering index worth having.
pub const FETCH_PENALTY: f64 = 3.0;

/// What sorting a row costs relative to visiting one.
pub const SORT_FACTOR: f64 = 3.0;

/// Returns how much of a row's width one index entry is.
///
/// An entry holds the indexed columns and the row's key; a row holds every
/// column. Cost here is bytes touched, so the ratio of the two is what a
/// covering path saves over reading the rows - and it is what makes a covering
/// scan of a narrow index beat a scan of a wide table when neither has a
/// predicate to narrow it.
///
/// The floor stops a one-column index over a fifty-column table from looking
/// fifty times cheaper than it is: pages, not just bytes, are what a scan
/// touches, and a b-tree of any width has a per-entry cost that does not shrink
/// with the entry.
/// @param index_columns - how many columns the index is over
/// @param table_columns - how many the table has
pub fn entry_share(index_columns: usize, table_columns: usize) -> f64 {
    let entry = index_columns.saturating_add(1) as f64;
    let row = table_columns.max(1) as f64;
    (entry / row).clamp(ENTRY_SHARE_FLOOR, 1.0)
}

/// The least a covering entry is allowed to be worth relative to a row.
pub const ENTRY_SHARE_FLOOR: f64 = 0.25;

/// Returns the estimated cost of visiting a number of rows through a scan.
///
/// One visit per row, and no descent per row: a scan walks the leaves in order
/// and each step is to the next entry rather than from the root. Charging it a
/// descent per row - the obvious reading of "reading a row costs a descent" -
/// makes a scan of a thousand rows cost ten thousand, and then an index search
/// that returns *every* row of the table still looks cheaper than reading the
/// table. Nothing would ever choose a scan again.
pub fn scan_cost(rows: f64) -> f64 {
    rows.max(1.0)
}

/// Returns the estimated cost of a search that returns some of the rows.
///
/// One descent to find the first match, then one visit per match, plus a second
/// descent per match when the index does not carry the columns the query wants.
pub fn search_cost(rows: f64, matches: f64, covering: bool) -> f64 {
    let rows = rows.max(1.0);
    let matches = matches.max(1.0);
    let fetch = if covering { 0.0 } else { FETCH_PENALTY };
    log2(rows) + matches * (1.0 + fetch)
}

/// Returns the estimated cost of sorting a number of rows.
///
/// This one *is* `n log n`, because a sort really does compare each row against
/// a logarithmic number of others.
pub fn sort_cost(rows: f64) -> f64 {
    let rows = rows.max(1.0);
    rows * log2(rows) * SORT_FACTOR
}

/// Returns a base-2 logarithm that never goes below one.
///
/// A B-tree of one row still costs a descent, and a cost of zero would make a
/// search over an empty table free - which is how a planner ends up preferring
/// a path over a table it has not measured to one it has.
pub fn log2(rows: f64) -> f64 {
    rows.max(2.0).log2()
}

/// Returns SQLite's estimate of how wide one column's values are.
///
/// SQLite's `szEst`: 1 for a column with no declared type and for every numeric
/// affinity, 16 for a `TEXT` or `BLOB` declaration, and for `CHAR(n)`-style
/// declarations `n / 4 + 1`, at most 255. Only the comparison between a table
/// and an index matters, so the numbers are the ones SQLite compares.
///
/// @param column - the column as declared
pub fn column_width(column: &crate::catalog_view::ColumnInfo) -> u32 {
    use inillucent_value::Affinity;
    if column.declared_type.is_empty() {
        return 1;
    }
    if !matches!(column.affinity, Affinity::Text | Affinity::Blob) {
        return 1;
    }
    let lowered = column.declared_type.to_ascii_lowercase();
    let Some(start) = lowered.windows(4).position(|word| word == b"char") else {
        return 16;
    };
    let digits: Vec<u8> = lowered
        .iter()
        .skip(start)
        .skip_while(|byte| !byte.is_ascii_digit())
        .take_while(|byte| byte.is_ascii_digit())
        .copied()
        .collect();
    let length = String::from_utf8_lossy(&digits).parse::<u32>().unwrap_or(0);
    (length / 4 + 1).clamp(1, 255)
}

/// Reports whether an index entry is narrower than a row of its table, which is
/// the only reason SQLite walks an index in place of the table when nothing
/// else decides.
///
/// **A covering index that is no narrower is not walked.** `SELECT * FROM t` on
/// `t(id INTEGER PRIMARY KEY, u UNIQUE)` returns the rows in rowid order in
/// SQLite, because the index entry (`u` and the rowid) is as wide as the row.
/// Walking it anyway returned them in `u` order, and an application that reads
/// a table without an `ORDER BY` gets rowid order.
///
/// @param table - the table
/// @param index - an index over it that holds every column the query reads
pub fn index_is_narrower(
    table: &crate::catalog_view::TableInfo,
    index: &crate::catalog_view::IndexInfo,
) -> bool {
    if table.without_rowid {
        return true;
    }
    let row: u32 = table
        .columns
        .iter()
        .map(column_width)
        .sum::<u32>()
        .saturating_add(u32::from(table.rowid_alias.is_none()));
    let entry: u32 = index
        .columns
        .iter()
        .map(|key| {
            key.plain_column()
                .and_then(|at| table.columns.get(usize::from(at)))
                .map_or(1, column_width)
        })
        .sum::<u32>()
        .saturating_add(1);
    entry < row
}

#[cfg(test)]
mod tests {
    use super::*;

    /// A search that returns one row of a million beats a scan, and by a lot.
    #[test]
    fn a_selective_search_beats_a_scan() {
        let rows = 1_000_000.0;
        assert!(search_cost(rows, 1.0, false) < scan_cost(rows) / 1000.0);
    }

    /// A search that returns every row does not - it pays a second descent per
    /// row for the privilege of reading the same table.
    #[test]
    fn an_unselective_search_does_not() {
        let rows = 1_000.0;
        assert!(search_cost(rows, rows, false) > scan_cost(rows));
    }

    /// The crossover is where it should be: a search that returns a fifth of a
    /// table is still worth it, and one that returns half is not.
    #[test]
    fn the_crossover_is_a_fraction_of_the_table() {
        let rows = 10_000.0;
        assert!(search_cost(rows, rows / 5.0, false) < scan_cost(rows));
        assert!(search_cost(rows, rows / 2.0, false) > scan_cost(rows));
    }

    /// A covering index is cheaper than the same search that has to fetch.
    #[test]
    fn covering_is_cheaper_than_fetching() {
        assert!(search_cost(1_000.0, 100.0, true) < search_cost(1_000.0, 100.0, false));
    }

    /// An empty table still costs a descent, so nothing is free.
    #[test]
    fn nothing_costs_nothing() {
        assert!(scan_cost(0.0) > 0.0);
        assert!(search_cost(0.0, 0.0, true) > 0.0);
    }
}