rudb 0.4.13

//! `EXPLAIN`, end to end through the parser, the binder, the optimizer and back out as a result set.
//!
//! These are about the statement being reachable and answering with the plan that would have run.
//! What the estimate for a given shape is belongs in `rudb-opt`'s own tests, and what the plan text
//! looks like belongs in `rudb-plan`'s. What is here is the join between the three.

use rudb::Database;
use rudb_common::{LogicalType, Value};

/// The lines of the plan tree, which is everything above the first blank line.
fn tree(text: &str) -> Vec<&str> {
    text.lines().take_while(|line| !line.is_empty()).collect()
}

/// The explain text for a query against a database with one table of `rows` rows.
fn explained(database: &Database, sql: &str) -> String {
    let result = database.query(sql).expect("the explain ran");
    assert_eq!(result.names(), ["explain_key", "explain_value"], "the shape DuckDB clients expect");
    assert_eq!(result.types(), [LogicalType::Varchar, LogicalType::Varchar]);
    assert_eq!(result.len(), 1, "the whole tree is one value rather than one row per operator");
    match result.value_at(0, 1) {
        Value::Varchar(text) => text,
        other => panic!("the plan came back as {other:?}"),
    }
}

/// A database with a table of the given size, built without a per row `INSERT`.
fn with_rows(count: usize) -> Database {
    let database = Database::new();
    database.execute("CREATE TABLE t (a INTEGER, b VARCHAR)").expect("creates");
    database
        .execute(&format!("INSERT INTO t SELECT r::INTEGER, 'x' FROM range({count}) AS s(r)"))
        .expect("inserts");
    database
}

#[test]
fn explain_answers_with_the_plan_and_an_estimate_on_every_line() {
    let database = with_rows(1000);
    let text = explained(&database, "EXPLAIN SELECT a FROM t WHERE a > 5");
    assert!(text.contains("Get memory.main.t"), "{text}");
    // The scan knows its size because the catalog does, so it is a count rather than a guess, and
    // the filter is a fifth of it, which is a guess and says which guess.
    assert!(text.contains("[1000 rows exact from row count]"), "{text}");
    assert!(text.contains("[~200 rows estimated from default]"), "{text}");
    for line in tree(&text) {
        assert!(line.contains(" rows"), "a line with no estimate on it: {line}");
    }
}

#[test]
fn the_plan_explain_shows_is_the_plan_that_would_have_run() {
    // Not a plan built differently because somebody asked to see it. The optimizer runs over it
    // with the same context, so a pushed down filter is pushed down here too, and an explain that
    // showed the plan before the passes would be showing a plan nothing executes.
    let database = with_rows(100);
    let text = explained(&database, "EXPLAIN SELECT a FROM t WHERE a > 5");
    let ran = database.plan("SELECT a FROM t WHERE a > 5").expect("plans");
    let bare: Vec<&str> = tree(&text)
        .into_iter()
        .map(|line| line.rsplit_once("  [").map_or(line, |(head, _)| head))
        .collect();
    assert_eq!(bare.join("\n"), ran.trim_end(), "{text}\n{ran}");
}

#[test]
fn an_estimate_nobody_can_make_says_so_rather_than_saying_zero() {
    // `range` is a table function and a table function is an open door. Saying nothing here would
    // read as an empty relation, which is the one reading that would be actively misleading.
    let database = Database::new();
    let text = explained(&database, "EXPLAIN SELECT * FROM range(10)");
    assert!(text.contains("rows unknown"), "{text}");
}

#[test]
fn an_ungrouped_count_is_one_row_over_a_table_of_any_size() {
    let database = with_rows(5000);
    let text = explained(&database, "EXPLAIN SELECT count(*) FROM t");
    // One row is a fact about what an ungrouped aggregate does rather than a guess about the data,
    // and it reads as one whatever is under it.
    assert!(text.contains("[1 rows exact from row count]"), "{text}");
    assert!(text.contains("[5000 rows exact from row count]"), "{text}");
}

#[test]
fn explain_prints_the_pipelines_a_plan_breaks_into_and_the_edges_between_them() {
    // The same decomposition the executor numbers its operators with, printed before anything runs.
    // A sort is two pipelines, and the one the answer comes out of cannot start until the other has
    // finished, which is the fact somebody reading a slow query is looking for.
    let database = with_rows(100);
    let text = explained(&database, "EXPLAIN SELECT a FROM t ORDER BY a");
    let lines = tree(&text);
    assert!(lines[0].contains("[pipeline 1]"), "{text}");
    assert!(text.contains("  pipeline 0 waits for 1"), "{text}");
    assert!(text.contains("  pipeline 1 waits for nothing"), "{text}");
}

#[test]
fn explain_marks_every_line_that_is_running_a_reference_implementation() {
    // Which is still every line, because the one seam with implementations defaults to its
    // reference, and that is the point of printing it. A number measured against the simplest
    // correct version of an operator is not a number to quote as the engine's.
    let database = with_rows(100);
    let text = explained(&database, "EXPLAIN SELECT a FROM t WHERE a > 5");
    for line in tree(&text) {
        assert!(line.ends_with("[reference]"), "a line with no marker on it: {line}");
    }
    assert!(text.contains("\nSeams\n"), "{text}");
    assert!(text.contains("  chunk.compaction = never (default)"), "{text}");
    assert!(text.contains("26 seams have nothing registered"), "{text}");
}

/// What a session that has moved off the reference sees.
///
/// The pin is printed, and the filter loses its reference marker while the operators that do not
/// sit on this seam keep theirs. That marker is the whole reason the seam section exists: a number
/// from a pinned run and a number from a default run are different numbers.
#[test]
fn explain_says_when_a_seam_has_been_pinned_off_its_reference() {
    let database = with_rows(100);
    database.execute("SET seam_chunk_compaction = 'learned-gain'").expect("a seam takes a pin");
    let text = explained(&database, "EXPLAIN SELECT a FROM t WHERE a > 5");
    assert!(text.contains("  chunk.compaction = learned-gain (pinned)"), "{text}");
    let lines = tree(&text);
    assert!(lines[0].ends_with("[reference]"), "the projection is not on this seam: {}", lines[0]);
    assert!(!lines[1].ends_with("[reference]"), "the filter is: {}", lines[1]);
}

#[test]
fn explain_analyze_runs_the_query_and_prints_what_each_operator_actually_did() {
    // The estimate stays where it was and the measurement goes beside it, so that the two are read
    // against each other. A filter that kept everything it was told would keep a fifth is the thing
    // this output exists to make obvious.
    let database = with_rows(1000);
    let text = explained(&database, "EXPLAIN ANALYZE SELECT a FROM t WHERE a > 5");
    for line in tree(&text) {
        let estimated = line.contains(" rows exact from row count]")
            || line.contains(" rows estimated from default]");
        assert!(estimated, "a line with no estimate on it: {line}");
        // The filter is the exception, and it says why rather than going quiet. Its comparison
        // happens inside the scan a level down, so the rows and the time are counted there and once.
        let moved = line.contains("[applied by the scan below]");
        assert!(line.contains(" rows") || moved, "a line with no measurement on it: {line}");
    }
    // The scan says the rows it counted are the ones that came out of the filter, because the line
    // above it carries the estimate for them and this line carries the exact count of the table.
    assert!(text.contains("[994 rows after the filter above, "), "{text}");
    assert!(text.contains("[applied by the scan below]"), "{text}");
}

/// A filter no zone map can read goes into the scan all the same, and the output says so.
///
/// `a % 2 = 0` is not a column against a constant, so nothing about it can rule a chunk out, and
/// that used to keep it above the scan. Where the comparison runs and whether a chunk can be
/// skipped are two questions and only the second one needs the predicate to read as a test. So the
/// comparison happens in the scan, on every chunk, which is what it would have done up there, and
/// one operator and the chunk handed across to it are gone.
#[test]
fn explain_analyze_measures_a_filter_no_zone_map_could_read() {
    let database = with_rows(1000);
    let text = explained(&database, "EXPLAIN ANALYZE SELECT a FROM t WHERE a % 2 = 0");
    assert!(text.contains("[applied by the scan below]"), "{text}");
    assert!(text.contains("[500 rows after the filter above, "), "the scan kept half: {text}");
}

#[test]
fn explain_analyze_counts_the_rows_a_pipeline_breaker_finally_handed_out() {
    // A sort produces nothing until it has seen everything, and the rows come back out of the
    // buffer it filled rather than through the operator, so this is the number that goes missing if
    // nobody counts it there. Zero here is what makes the estimate look a thousand times wrong.
    let database = with_rows(1000);
    let text = explained(&database, "EXPLAIN ANALYZE SELECT a FROM t ORDER BY a");
    let sort = tree(&text)[0];
    assert!(sort.starts_with("Sort "), "{text}");
    assert!(sort.contains("[1000 rows, "), "{sort}");
    assert!(!text.contains("q-error"), "a sort that produced every row it was given: {text}");
    // The same buffer sits under a join, so the same number goes missing there if it is only
    // counted in one of the two places.
    let joined = explained(&database, "EXPLAIN ANALYZE SELECT t.a FROM t JOIN t AS u ON t.a = u.a");
    let join = tree(&joined)
        .into_iter()
        .find(|line| line.trim_start().starts_with("Join "))
        .unwrap_or_else(|| panic!("no join on the plan: {joined}"));
    assert!(join.contains("[1000 rows, "), "{join}");
}

#[test]
fn explain_analyze_reports_the_whole_query_under_its_own_key() {
    // A client reading the result back has to be able to tell a plan that ran from a plan that did
    // not, and the key is the only place that distinction shows up.
    let database = with_rows(100);
    let result = database.query("EXPLAIN ANALYZE SELECT a FROM t").expect("the explain ran");
    assert_eq!(result.value_at(0, 0), Value::Varchar("analyzed_plan".to_owned()));
    let plain = database.query("EXPLAIN SELECT a FROM t").expect("the explain ran");
    assert_eq!(plain.value_at(0, 0), Value::Varchar("logical_plan".to_owned()));
    let text = explained(&database, "EXPLAIN ANALYZE SELECT a FROM t");
    assert!(text.contains("\nPipelines\n"), "{text}");
    assert!(text.contains("\nSeams\n"), "{text}");
    assert!(text.contains("\nTotals\n"), "{text}");
    assert!(text.contains(" building the tree, "), "{text}");
    assert!(text.contains(" of cpu, "), "{text}");
}

#[test]
fn explain_analyze_says_what_the_query_spent_planning() {
    // The totals line used to be the build, the run and a total that was the two of them added up,
    // so a reader could see every phase of a query except the one that decided what the query was
    // going to do. An optimizer that has become too expensive is invisible on a line like that, and
    // this is the line somebody reads with their own eyes rather than through the harness.
    let database = with_rows(100);
    let text = explained(&database, "EXPLAIN ANALYZE SELECT a, COUNT(*) FROM t GROUP BY a");
    assert!(text.contains(" planning, "), "{text}");
    // Not a duration: a zero prints as a duration too, and a zero is exactly what this line said
    // before the planner had a clock on it.
    assert!(!text.contains("  0ns planning, "), "{text}");
}

#[test]
fn explaining_something_that_is_not_a_query_is_refused() {
    // Each refusal names the statement it refused, rather than being the generic error a wrong
    // turn somewhere else in this path would also produce.
    let database = with_rows(10);
    let insert = database.query("EXPLAIN INSERT INTO t VALUES (1, 'x')").expect_err("refused");
    assert!(insert.to_string().contains("InsertStatement"), "{insert}");
    let create = database.query("EXPLAIN CREATE TABLE u (a INTEGER)").expect_err("refused");
    assert!(create.to_string().contains("CreateStatement"), "{create}");
    let options = database.query("EXPLAIN (FORMAT JSON) SELECT a FROM t").expect_err("refused");
    assert!(options.to_string().contains("Unimplemented explain type: format"), "{options}");
}

#[test]
fn explain_statistics_says_what_every_number_in_the_plan_was_read_for() {
    // `spec/stats/05-every-query.md` section 5.1.1 asks `EXPLAIN` to print which use happened, and
    // this is the whole of that question asked end to end: a use on each line and the classes
    // counted underneath. Every cardinality the optimizer reads chooses between plans that produce
    // the same rows, so the answer today is decide on every line, and the section says out loud
    // that nothing licensed a rewrite off a number.
    let database = with_rows(1000);
    let text = explained(&database, "EXPLAIN (STATISTICS) SELECT a FROM t WHERE a > 5");
    for line in tree(&text) {
        assert!(line.contains(", read to decide]"), "a line with no use on it: {line}");
    }
    assert!(text.contains("\nStatistics\n"), "{text}");
    assert!(text.contains("read to decide: exact 1, certified 0, estimated"), "{text}");
    assert!(text.contains("nothing was read to answer or to enable"), "{text}");

    // A plain explain is the plan and nothing else, because the use and the class on every line is
    // a second sentence per line for a question most readers are not asking.
    let quiet = explained(&database, "EXPLAIN SELECT a FROM t WHERE a > 5");
    assert!(!quiet.contains("read to"), "{quiet}");
    assert!(!quiet.contains("\nStatistics\n"), "{quiet}");
}

#[test]
fn the_explain_options_this_answers_reach_the_output_and_can_be_asked_for_together() {
    let database = with_rows(100);
    // `ANALYZE` in the option list is the keyword written the other way, so it has to run the query
    // and come back under the analyzed key rather than the logical one.
    let analyzed = explained(&database, "EXPLAIN (ANALYZE) SELECT a FROM t");
    assert!(analyzed.contains("\nTotals\n"), "{analyzed}");
    // `LOGICAL` names the plan this already prints, so it changes nothing.
    let logical = explained(&database, "EXPLAIN (LOGICAL) SELECT a FROM t");
    assert_eq!(tree(&logical), tree(&explained(&database, "EXPLAIN SELECT a FROM t")));
    // And the two that do something can be asked for at once.
    let both = explained(&database, "EXPLAIN (ANALYZE, STATISTICS) SELECT a FROM t");
    assert!(both.contains("\nTotals\n"), "{both}");
    assert!(both.contains("\nStatistics\n"), "{both}");
    assert!(both.contains(", read to decide]"), "{both}");
}

#[test]
fn a_scan_says_how_many_parts_its_statistics_ruled_out() {
    // Two tables with the same rows in them and one of them in order. The predicate keeps the same
    // hundred rows either way, so the row count on the scan line cannot tell them apart and the
    // part count is the only thing that can.
    let database = Database::new();
    database.execute("CREATE TABLE sorted (a INTEGER)").expect("creates");
    database
        .execute("INSERT INTO sorted SELECT r::INTEGER FROM range(200000) AS s(r)")
        .expect("inserts in order");
    database.execute("CREATE TABLE shuffled (a INTEGER)").expect("creates");
    database
        .execute(
            "INSERT INTO shuffled SELECT ((r * 7919) % 200000)::INTEGER FROM range(200000) AS s(r)",
        )
        .expect("inserts out of order");

    let ordered = explained(&database, "EXPLAIN ANALYZE SELECT a FROM sorted WHERE a < 100");
    let scan = tree(&ordered)
        .into_iter()
        .find(|line| line.contains("Get "))
        .expect("the scan is on the tree");
    assert!(scan.contains("parts skipped"), "an ordered column prunes and should say so: {scan}");
    assert!(scan.contains("100 rows"), "{scan}");

    // The same predicate over the same values in no particular order rules nothing out, and the
    // clause is left off rather than printed as a zero.
    let scattered = explained(&database, "EXPLAIN ANALYZE SELECT a FROM shuffled WHERE a < 100");
    let scan = tree(&scattered)
        .into_iter()
        .find(|line| line.contains("Get "))
        .expect("the scan is on the tree");
    assert!(!scan.contains("parts skipped"), "nothing was ruled out here: {scan}");
    assert!(scan.contains("100 rows"), "{scan}");
}