Hands-on lab — Day 89: Indexes and Query Performance

"""When the index is there and the planner will not touch it.

    python3 blocked.py events.db

This is the part people get wrong, because the index exists, the column
is indexed, the query mentions the column, and the query is still slow.
An index is a sorted copy of the COLUMN'S VALUES. Anything that asks a
question about something other than those exact values — a function
applied to them, a match that does not start at the beginning, a
condition the index cannot bracket — puts the answer outside what the
sorted order can find.

Five cases, each with the fix where a fix exists:

  1. A function wrapping the column          -> an expression index
  2. An expression on the column             -> store or index the expression
  3. LIKE with a leading wildcard            -> no fix; a different tool
  4. LIKE with a trailing wildcard           -> a range, or case_sensitive_like
  5. OR across two columns                   -> index both, or write UNION

Watch the plan line, not just the milliseconds. `SCAN events USING
COVERING INDEX ...` still contains the word SCAN, and that is the word
that matters: the planner decided the index was a cheaper thing to walk
end-to-end than the table, which is not the same as finding anything.
"""

from __future__ import annotations

import sqlite3
import sys
from pathlib import Path

from timing import drop_all_indexes, fmt, plan, time_query

RULE = "-" * 78


def verdict(plan_text: str) -> str:
    """The one word that decides everything.

    If any step of the plan says SCAN, something is being walked end to
    end — the table, or an index used as a narrower table. Only SEARCH
    means the engine descended a tree to the rows it wanted.
    """
    return "SCAN" if "SCAN" in plan_text else "SEEK"


def show(connection, label, sql, params=()):
    plan_text = plan(connection, sql, params)
    measurement = time_query(connection, sql, params)
    print(f"  {label}")
    print(f"    plan : [{verdict(plan_text)}] {plan_text}")
    print(f"    time : {fmt(measurement)}   rows: {len(measurement['result']):,}")
    return plan_text, measurement


def section(title: str) -> None:
    print()
    print(RULE)
    print(title)
    print(RULE)


def main(argv: list[str]) -> int:
    path = Path(argv[1]) if len(argv) > 1 else Path("events.db")
    if not path.exists():
        print(f"{path} does not exist. Run: python3 generate.py {path}", file=sys.stderr)
        return 2

    connection = sqlite3.connect(path)
    drop_all_indexes(connection)
    connection.execute("CREATE INDEX ix_trace ON events(trace_id)")
    connection.execute("CREATE INDEX ix_run ON events(run_id)")

    total = connection.execute("SELECT count(*) FROM events").fetchone()[0]
    trace = connection.execute(
        "SELECT trace_id FROM events WHERE event_id = 123456"
    ).fetchone()[0]
    print(f"{path.name}: {total:,} rows")
    print("Indexes present for all of the below: ix_trace(trace_id), ix_run(run_id)")
    print(f"The value being looked for: trace_id = {trace!r}")

    # ---------------------------------------------------------------- 0
    section("0. The baseline: plain equality on an indexed column")
    baseline = show(
        connection,
        "WHERE trace_id = ?",
        "SELECT event_id FROM events WHERE trace_id = ?",
        (trace,),
    )[1]

    # ---------------------------------------------------------------- 1
    section("1. A function wrapping the column")
    show(
        connection,
        "WHERE lower(trace_id) = ?   — the index holds trace_id, not lower(trace_id)",
        "SELECT event_id FROM events WHERE lower(trace_id) = ?",
        (trace.lower(),),
    )
    connection.execute("CREATE INDEX ix_lower_trace ON events(lower(trace_id))")
    show(
        connection,
        "the fix: CREATE INDEX ix_lower_trace ON events(lower(trace_id))",
        "SELECT event_id FROM events WHERE lower(trace_id) = ?",
        (trace.lower(),),
    )
    connection.execute("DROP INDEX ix_lower_trace")
    print()
    print("  An expression index stores the answer to lower(trace_id) for every")
    print("  row and sorts THAT. The rule is exact: the expression in the query")
    print("  must match the expression in the index, character for character in")
    print("  meaning. upper() will not use an index built on lower().")

    # ---------------------------------------------------------------- 2
    section("2. An expression on the column")
    show(
        connection,
        "WHERE substr(trace_id, 4) = ?   — asking about part of the value",
        "SELECT event_id FROM events WHERE substr(trace_id, 4) = ?",
        (trace[3:],),
    )
    print()
    print("  Same cause, and the same two fixes: an expression index, or —")
    print("  usually better — store the part you actually query as its own")
    print("  column. If you keep asking half a question, keep half a column.")

    # ---------------------------------------------------------------- 3
    section("3. LIKE with a leading wildcard")
    show(
        connection,
        f"WHERE trace_id LIKE '%{trace[-6:]}'",
        "SELECT event_id FROM events WHERE trace_id LIKE ?",
        (f"%{trace[-6:]}",),
    )
    print()
    print("  There is no fix, and that is worth saying plainly. A B-tree finds")
    print("  things by their beginning; '%abc' says the beginning is unknown.")
    print("  If you genuinely need it: index a reversed copy of the column when")
    print("  the wildcard is always leading, or reach for full-text search —")
    print("  SQLite ships FTS5 for exactly this. Do not add an ordinary index")
    print("  and hope.")

    # ---------------------------------------------------------------- 4
    section("4. LIKE with a trailing wildcard")
    prefix = trace[:8]
    show(
        connection,
        f"WHERE trace_id LIKE '{prefix}%'   — a prefix, which a B-tree could find",
        "SELECT event_id FROM events WHERE trace_id LIKE ?",
        (f"{prefix}%",),
    )
    upper_bound = prefix[:-1] + chr(ord(prefix[-1]) + 1)
    show(
        connection,
        f"the rewrite: WHERE trace_id >= '{prefix}' AND trace_id < '{upper_bound}'",
        "SELECT event_id FROM events WHERE trace_id >= ? AND trace_id < ?",
        (prefix, upper_bound),
    )
    connection.execute("PRAGMA case_sensitive_like = ON")
    show(
        connection,
        "or: PRAGMA case_sensitive_like = ON, then the same LIKE",
        "SELECT event_id FROM events WHERE trace_id LIKE ?",
        (f"{prefix}%",),
    )
    connection.execute("PRAGMA case_sensitive_like = OFF")
    print()
    print("  This one surprises people, so read the three plans above together.")
    print("  A prefix LIKE is bracketable in principle, but SQLite's LIKE is")
    print("  case-insensitive by default while the index is sorted in binary")
    print("  order — and a case-insensitive match cannot be answered from a")
    print("  case-sensitive ordering. Turn LIKE case-sensitive and the planner")
    print("  rewrites it into exactly the range shown above, all by itself.")

    # ---------------------------------------------------------------- 5
    section("5. OR across different columns")
    show(
        connection,
        "WHERE run_id = ? OR trace_id = ?   — BOTH columns indexed",
        "SELECT event_id FROM events WHERE run_id = ? OR trace_id = ?",
        (200, trace),
    )
    show(
        connection,
        "WHERE run_id = ? OR score > ?      — score has no index",
        "SELECT event_id FROM events WHERE run_id = ? OR score > ?",
        (200, 0.999999),
    )
    show(
        connection,
        "the rewrite: UNION of two indexed halves",
        "SELECT event_id FROM events WHERE run_id = ?"
        " UNION SELECT event_id FROM events WHERE trace_id = ?",
        (200, trace),
    )
    print()
    print("  The honest version of the folklore: OR is not automatically fatal.")
    print("  When EVERY branch has an index, SQLite runs each one and merges —")
    print("  that is the MULTI-INDEX OR plan above. One unindexed branch and the")
    print("  whole thing collapses to a scan, because a row failing the indexed")
    print("  test might still pass the other one. An OR is only as indexed as")
    print("  its worst branch.")

    # ---------------------------------------------------------------- end
    section("What the five cases have in common")
    print("  In every failing case the index was present and the column was")
    print("  named. What was missing was that the query asked about something")
    print("  the sorted order does not contain: a transformed value, a match")
    print("  with an unknown beginning, or a condition that cannot be bracketed.")
    print()
    print(f"  For scale, the plain indexed lookup at the top: {fmt(baseline)}")
    print("  Everything in sections 1 to 3 was hundreds of times slower than")
    print("  that, with the index sitting right there unused.")

    drop_all_indexes(connection)
    connection.commit()
    connection.close()
    print()
    print(RULE)
    print("Indexes dropped. The table is back to how generate.py left it.")
    return 0


if __name__ == "__main__":
    raise SystemExit(main(sys.argv))

"""Composite indexes, the leftmost prefix, covering, ORDER BY, partial.

    python3 composite.py events.db

Five experiments, each of which answers one question with a plan and a
measurement rather than a rule of thumb.

  1. LEFTMOST PREFIX. One index on (run_id, status). Four queries: both
     columns, the leading column alone, the trailing column alone, and
     the two conditions written in the other order. Two of those four can
     use the index for a seek and two cannot, and which two is not
     negotiable — it follows from the index being sorted by run_id first.

  2. COVERING. A query whose columns all appear in the index never has to
     open the table at all. The planner says so in one word: COVERING.

  3. ORDER BY. An index is sorted, so a query that wants rows in that
     order can take them straight off it. Watch USE TEMP B-TREE FOR ORDER
     BY disappear.

  4. PARTIAL. An index with a WHERE clause covers only the rows that
     match it. It is smaller, cheaper to maintain, and usable only by
     queries the planner can prove fall inside it.

  5. ANALYZE. Statistics in sqlite_stat1 are how the planner knows which
     of two usable indexes is the more selective one.

Every experiment starts by dropping every index, so no result here
depends on the order you ran things in.
"""

from __future__ import annotations

import sqlite3
import sys
from pathlib import Path

from timing import drop_all_indexes, file_pages, fmt, plan, time_query

RULE = "-" * 78


def verdict(plan_text: str) -> str:
    """The one word that decides everything.

    If any step of the plan says SCAN, something is being walked end to
    end — the table, or an index used as a narrower table. Only SEARCH
    means the engine descended a tree to the rows it wanted.
    """
    return "SCAN" if "SCAN" in plan_text else "SEEK"


def section(title: str) -> None:
    print()
    print(RULE)
    print(title)
    print(RULE)


def show(connection, label, sql, params=()):
    plan_text = plan(connection, sql, params)
    measurement = time_query(connection, sql, params)
    print(f"  {label}")
    print(f"    plan : [{verdict(plan_text)}] {plan_text}")
    print(f"    time : {fmt(measurement)}")
    return plan_text, measurement


def main(argv: list[str]) -> int:
    path = Path(argv[1]) if len(argv) > 1 else Path("events.db")
    if not path.exists():
        print(f"{path} does not exist. Run: python3 generate.py {path}", file=sys.stderr)
        return 2

    connection = sqlite3.connect(path)
    total = connection.execute("SELECT count(*) FROM events").fetchone()[0]
    print(f"{path.name}: {total:,} rows")

    # ---------------------------------------------------------------- 1
    section("1. The leftmost-prefix rule: one index on (run_id, status)")
    drop_all_indexes(connection)
    connection.execute("CREATE INDEX ix_run_status ON events(run_id, status)")
    print("  The index holds every row's (run_id, status) pair, sorted by")
    print("  run_id first and by status only within one run_id.")
    print()
    show(
        connection,
        "a) both columns, leading first  WHERE run_id = ? AND status = ?",
        "SELECT count(*) FROM events WHERE run_id = ? AND status = ?",
        (200, "failed"),
    )
    show(
        connection,
        "b) the leading column alone     WHERE run_id = ?",
        "SELECT count(*) FROM events WHERE run_id = ?",
        (200,),
    )
    show(
        connection,
        "c) the trailing column alone    WHERE status = ?",
        "SELECT count(*) FROM events WHERE status = ?",
        ("failed",),
    )
    show(
        connection,
        "d) both columns, order swapped  WHERE status = ? AND run_id = ?",
        "SELECT count(*) FROM events WHERE status = ? AND run_id = ?",
        ("failed", 200),
    )
    print()
    print("  (a), (b) and (d) seek. (c) cannot.")
    print("  The order you write conditions in WHERE does not matter — (d)")
    print("  is (a) rearranged and gets the same plan. The order of COLUMNS")
    print("  IN THE INDEX is what decides, because a sorted list of pairs is")
    print("  only sorted by the second value inside one value of the first.")
    print("  A phone book sorted by surname then forename cannot find every")
    print("  Ada without reading all of it.")

    # ---------------------------------------------------------------- 2
    section("2. Covering: the index answers, and the table is never opened")
    drop_all_indexes(connection)
    query = "SELECT score FROM events WHERE run_id = ?"
    connection.execute("CREATE INDEX ix_run ON events(run_id)")
    show(connection, "index on (run_id) — seek, then fetch the row for score", query, (200,))
    connection.execute("DROP INDEX ix_run")
    connection.execute("CREATE INDEX ix_run_score ON events(run_id, score)")
    show(connection, "index on (run_id, score) — score is already in the index", query, (200,))
    print()
    print("  The second plan says COVERING INDEX. Every column the query")
    print("  named is in the index, so there is no reason to touch the table.")
    print("  This is the fastest an index gets — and the reason to widen an")
    print("  index is sometimes the columns you SELECT, not the ones you filter.")

    # ---------------------------------------------------------------- 3
    section("3. ORDER BY: an index is already sorted, so the sort disappears")
    drop_all_indexes(connection)
    ordered = "SELECT event_id, created_on FROM events ORDER BY created_on LIMIT 20"
    show(connection, "no index on created_on", ordered)
    connection.execute("CREATE INDEX ix_created ON events(created_on)")
    show(connection, "with an index on created_on", ordered)
    print()
    print("  USE TEMP B-TREE FOR ORDER BY means SQLite built a throwaway tree")
    print("  to sort 400,000 rows so it could hand back the first 20. With the")
    print("  index it walks the first 20 entries and stops. Nothing was sorted.")

    # ---------------------------------------------------------------- 4
    section("4. Partial: index only the rows anybody asks about")
    drop_all_indexes(connection)
    failures = (
        "SELECT count(*) FROM events"
        " WHERE status = 'failed' AND created_on >= '2025-06-01'"
    )
    show(connection, "no index at all", failures)

    pages_before, page_size = file_pages(connection)
    connection.execute("CREATE INDEX ix_created_full ON events(created_on)")
    pages_full, _ = file_pages(connection)
    connection.execute("DROP INDEX ix_created_full")

    pages_reset, _ = file_pages(connection)
    connection.execute(
        "CREATE INDEX ix_failed_created ON events(created_on) WHERE status = 'failed'"
    )
    pages_partial, _ = file_pages(connection)
    show(connection, "with a partial index, WHERE status = 'failed'", failures)

    failed_rows = connection.execute(
        "SELECT count(*) FROM events WHERE status = 'failed'"
    ).fetchone()[0]
    print()
    print(f"  rows in the table        : {total:,}")
    print(f"  rows the partial covers  : {failed_rows:,}"
          f" ({failed_rows / total * 100:.1f}%)")
    print(f"  a full index on created_on costs {pages_full - pages_before:,} pages"
          f" ({(pages_full - pages_before) * page_size:,} bytes)")
    print(f"  the partial index costs          {pages_partial - pages_reset:,} pages"
          f" ({(pages_partial - pages_reset) * page_size:,} bytes)")
    print()
    print("  The catch: the planner will only use it for a query it can prove")
    print("  falls inside the WHERE clause. Drop `status = 'failed'` from the")
    print("  query and this index becomes unusable, not merely unhelpful:")
    show(
        connection,
        "the same date range without status = 'failed'",
        "SELECT count(*) FROM events WHERE created_on >= '2025-06-01'",
    )

    # ---------------------------------------------------------------- 5
    section("5. ANALYZE: what the planner knows about your data")
    drop_all_indexes(connection)
    connection.execute("CREATE INDEX ix_run ON events(run_id)")
    connection.execute("CREATE INDEX ix_status ON events(status)")
    both = "SELECT count(*) FROM events WHERE run_id = ? AND status = ?"
    before_plan, _ = show(connection, "two usable indexes, no statistics", both, (200, "failed"))
    connection.execute("ANALYZE")
    after_plan, _ = show(connection, "the same query after ANALYZE", both, (200, "failed"))
    print()
    print("  sqlite_stat1 — one row per index, written by ANALYZE:")
    for row in connection.execute(
        "SELECT tbl, idx, stat FROM sqlite_stat1 WHERE idx IS NOT NULL ORDER BY idx"
    ):
        rows_in_index, average_per_key = row[2].split()[:2]
        print(
            f"    {row[1]:<12} {int(rows_in_index):>9,} rows,"
            f" about {int(average_per_key):>7,} rows per distinct value"
        )
    print()
    print("  That second number is SELECTIVITY: how many rows the average")
    print("  distinct value matches. An index whose average key matches 100")
    print("  rows is worth seeking; one whose average key matches 130,000 is")
    print("  usually worse than reading the table, because every match costs")
    print("  a jump back into the table for the rest of the row.")
    print()
    if before_plan == after_plan:
        print("  Note what did NOT happen here: the plan is unchanged.")
        print("  SQLite's built-in guess had already picked the more selective")
        print("  of the two indexes on this data, and ANALYZE only replaced the")
        print("  guess with a measured number. That is the usual outcome on a")
        print("  small, evenly distributed table, and pretending otherwise would")
        print("  be inventing a result. ANALYZE earns its keep on skewed data")
        print("  and on tables that changed shape after the index was built —")
        print("  so run it after a big load, and check whether anything moved.")
    else:
        print("  The plan CHANGED once the planner had real numbers:")
        print(f"    before : {before_plan}")
        print(f"    after  : {after_plan}")

    drop_all_indexes(connection)
    connection.execute("ANALYZE")
    connection.commit()
    connection.close()
    print()
    print(RULE)
    print("Indexes dropped. The table is back to how generate.py left it.")
    return 0


if __name__ == "__main__":
    raise SystemExit(main(sys.argv))

"""Build the table this lab measures: 400,000 evaluation events.

    python3 generate.py events.db            # 400,000 rows, the default
    python3 generate.py small.db 25000       # any other size

Three properties matter more than the contents.

**It is deterministic.** Every value comes from `random.Random(SEED)` or
from arithmetic on the row number, so two runs of this script produce
byte-identical data. Reproducible numbers are the whole point of a lab
about measurement: if your rows differ from mine, your timings and mine
cannot be compared at all.

**It is big enough that the difference is unmistakable.** On fifty rows an
index and a scan are both instant and you will conclude, reasonably and
wrongly, that indexes do not matter. Four hundred thousand rows is the
smallest size at which a laptop stops hiding the difference.

**It is deliberately un-indexed.** The table is created with nothing but
its implicit rowid index. Every index in this lab is one you add, after
you have measured what life is like without it.

The shape is an evaluation log, because that is where you will meet this
problem in AI work: one row per model call, a run id grouping the calls of
one experiment, a trace id identifying a single call, a status, a score,
and a date.
"""

from __future__ import annotations

import random
import sqlite3
import sys
import time
from pathlib import Path

SEED = 20260816
DEFAULT_ROWS = 400_000
EVENTS_PER_RUN = 100

MODELS = [
    "atlas-7b",
    "atlas-13b",
    "beacon-3b",
    "beacon-9b",
    "cinder-1b",
    "cinder-4b",
    "delta-mini",
    "delta-large",
]
STATUSES = ["ok"] * 8 + ["failed", "timeout"]

SCHEMA = """
CREATE TABLE events (
    event_id   INTEGER PRIMARY KEY,
    run_id     INTEGER NOT NULL,
    trace_id   TEXT    NOT NULL,
    model      TEXT    NOT NULL,
    status     TEXT    NOT NULL,
    score      REAL    NOT NULL,
    created_on TEXT    NOT NULL,
    note       TEXT    NOT NULL
);
"""


def scramble(event_id: int) -> int:
    """Spread trace ids so they carry no hint of insertion order.

    Multiplying by a large odd constant and taking a modulus is the
    cheapest way to get a fixed, reproducible permutation. It is not a
    hash and it is not secret; it exists only so that trace_id order and
    rowid order are unrelated, the way they would be in a real system.
    """
    return (event_id * 2_654_435_761) % 999_983


def rows(count: int):
    """Yield `count` fully determined rows. One generator, no surprises."""
    rng = random.Random(SEED)
    for event_id in range(1, count + 1):
        run_id = (event_id - 1) // EVENTS_PER_RUN + 1
        day = 1 + (run_id * 7) % 28
        month = 1 + (run_id // 4) % 12
        year = 2024 + (run_id // 48) % 2
        yield (
            event_id,
            run_id,
            f"tr-{scramble(event_id):06d}-{event_id % 97:02d}",
            MODELS[event_id % len(MODELS)],
            STATUSES[rng.randrange(len(STATUSES))],
            round(rng.random(), 6),
            f"{year:04d}-{month:02d}-{day:02d}",
            f"run {run_id} step {(event_id - 1) % EVENTS_PER_RUN + 1}",
        )


def build(path: Path, count: int) -> None:
    if path.exists():
        path.unlink()
    connection = sqlite3.connect(path)
    connection.executescript(SCHEMA)
    started = time.perf_counter()
    with connection:
        connection.executemany(
            "INSERT INTO events"
            " (event_id, run_id, trace_id, model, status, score, created_on, note)"
            " VALUES (?, ?, ?, ?, ?, ?, ?, ?)",
            rows(count),
        )
    elapsed = time.perf_counter() - started

    total = connection.execute("SELECT count(*) FROM events").fetchone()[0]
    distinct_runs = connection.execute(
        "SELECT count(DISTINCT run_id) FROM events"
    ).fetchone()[0]
    page_size = connection.execute("PRAGMA page_size").fetchone()[0]
    page_count = connection.execute("PRAGMA page_count").fetchone()[0]
    index_names = [
        row[0]
        for row in connection.execute(
            "SELECT name FROM sqlite_schema WHERE type = 'index' ORDER BY name"
        )
    ]
    connection.close()

    print(f"built {path.name}")
    print(f"  rows:            {total:,}")
    print(f"  distinct run_id: {distinct_runs:,} ({EVENTS_PER_RUN} events each)")
    print(f"  distinct model:  {len(MODELS)}")
    print(f"  page size:       {page_size:,} bytes")
    print(f"  pages:           {page_count:,}")
    print(f"  file size:       {path.stat().st_size:,} bytes")
    print(f"  named indexes:   {index_names if index_names else 'none — that is on purpose'}")
    print(f"  insert took:     {elapsed * 1000:,.0f} ms")
    print()
    print("A scan of this table has to read every one of those pages.")
    print("Nothing here is indexed yet except the implicit rowid B-tree.")


def main(argv: list[str]) -> int:
    path = Path(argv[1]) if len(argv) > 1 else Path("events.db")
    count = int(argv[2]) if len(argv) > 2 else DEFAULT_ROWS
    build(path, count)
    return 0


if __name__ == "__main__":
    raise SystemExit(main(sys.argv))

"""The same lookup, before and after one CREATE INDEX, at four sizes.

    python3 lookup.py events.db

This is the measurement the whole lab is built on. One query —

    SELECT event_id, model, score FROM events WHERE run_id = ?

— is asked of tables of 25,000, 100,000, 200,000 and 400,000 rows, first
with no index on `run_id` and then with one. Every timing is a best-of-7
with the median printed beside it, and `EXPLAIN QUERY PLAN` is captured
in both states so you can see the planner change its mind.

The row counts are checked. The unindexed and indexed runs must return
exactly the same rows, and the script exits non-zero if they do not.

Two honest notes, because a measurement you cannot criticise is not a
measurement.

**These milliseconds are from one machine on one day.** Yours will
differ, possibly by a lot. What generalises is the SHAPE: the scan column
grows roughly in proportion to the table, and the seek column barely
moves. Read the columns, not the digits.

**The indexed run has an advantage the scan did not.** By the time it
runs, the pages it needs are already in the operating system's cache
because the scan just read them. That makes this comparison friendly to
the index rather than hostile — so the script drops the index and
re-measures the scan at the end, and reports whether the scan came back
to where it started.
"""

from __future__ import annotations

import shutil
import sqlite3
import sys
import tempfile
from pathlib import Path

from generate import build
from timing import drop_all_indexes, file_pages, fmt, plan, ratio, time_query

SIZES = [25_000, 100_000, 200_000, 400_000]
QUERY = "SELECT event_id, model, score FROM events WHERE run_id = ?"
TARGET_RUN = 200  # exists at every size above: 25,000 rows / 100 = 250 runs


def measure_one(path: Path, size: int) -> dict:
    connection = sqlite3.connect(path)
    drop_all_indexes(connection)

    pages_before, page_size = file_pages(connection)
    scanned = time_query(connection, QUERY, (TARGET_RUN,))
    scan_plan = plan(connection, QUERY, (TARGET_RUN,))

    connection.execute("CREATE INDEX ix_events_run ON events(run_id)")
    pages_after, _ = file_pages(connection)
    sought = time_query(connection, QUERY, (TARGET_RUN,))
    seek_plan = plan(connection, QUERY, (TARGET_RUN,))

    if sorted(scanned["result"]) != sorted(sought["result"]):
        raise AssertionError("the index changed the answer — that must never happen")

    connection.execute("DROP INDEX ix_events_run")
    rescanned = time_query(connection, QUERY, (TARGET_RUN,))
    connection.close()

    return {
        "size": size,
        "rows": len(scanned["result"]),
        "scan": scanned,
        "seek": sought,
        "rescan": rescanned,
        "scan_plan": scan_plan,
        "seek_plan": seek_plan,
        "index_pages": pages_after - pages_before,
        "page_size": page_size,
        "table_pages": pages_before,
    }


def main(argv: list[str]) -> int:
    source = Path(argv[1]) if len(argv) > 1 else Path("events.db")
    if not source.exists():
        print(f"{source} does not exist. Run: python3 generate.py {source}", file=sys.stderr)
        return 2

    workspace = Path(tempfile.mkdtemp(prefix="day089-lookup-"))
    results = []
    try:
        print("One lookup, with and without an index on run_id.")
        print(f"Query: {QUERY}   (run_id = {TARGET_RUN})")
        print("Every figure is milliseconds, best and median of 7 runs.")
        print()
        header = (
            f"{'rows':>9} | {'scan best':>10} | {'seek best':>10} | {'faster':>8} |"
            f" {'scan median':>12} | {'seek median':>12} | {'matched':>7}"
        )
        print(header)
        print("-" * len(header))

        for size in SIZES:
            path = workspace / f"events-{size}.db"
            if size == 400_000 and source.exists():
                shutil.copyfile(source, path)
            else:
                build_quiet(path, size)
            row = measure_one(path, size)
            results.append(row)
            print(
                f"{row['size']:>9,} | {row['scan']['best_ms']:>10.2f} |"
                f" {row['seek']['best_ms']:>10.3f} |"
                f" {ratio(row['scan'], row['seek']):>7.0f}x |"
                f" {row['scan']['median_ms']:>12.2f} |"
                f" {row['seek']['median_ms']:>12.3f} |"
                f" {row['rows']:>7,}"
            )

        biggest = results[-1]
        print()
        print("The planner's own words, on the largest table:")
        print(f"  without the index : {biggest['scan_plan']}")
        print(f"  with the index    : {biggest['seek_plan']}")
        print()
        print("SCAN means every row. SEARCH means a descent to the rows that match.")
        print("That one word is the whole difference, and it costs nothing to check.")
        print()
        print("What the index cost, on the largest table:")
        print(
            f"  table pages before : {biggest['table_pages']:,}"
            f" ({biggest['table_pages'] * biggest['page_size']:,} bytes)"
        )
        print(
            f"  index added        : {biggest['index_pages']:,} pages"
            f" ({biggest['index_pages'] * biggest['page_size']:,} bytes,"
            f" {biggest['index_pages'] / biggest['table_pages'] * 100:.0f}% of the table)"
        )
        print()
        print("And the scan, re-measured after the index was dropped again:")
        for row in results:
            print(
                f"  {row['size']:>9,} rows: first {row['scan']['best_ms']:>8.2f} ms"
                f" | after dropping the index {row['rescan']['best_ms']:>8.2f} ms"
            )
        print()
        print("If those two columns are close, the scan figures were not a")
        print("cold-cache artefact and the comparison above is a fair one.")
        print()
        print("Same rows every time. Only the work changed.")
        return 0
    finally:
        shutil.rmtree(workspace, ignore_errors=True)


def build_quiet(path: Path, size: int) -> None:
    """generate.build prints a report; here only the file is wanted."""
    import contextlib
    import io

    with contextlib.redirect_stdout(io.StringIO()):
        build(path, size)


if __name__ == "__main__":
    raise SystemExit(main(sys.argv))

-- Day 089 — reading query plans in the sqlite3 shell.
--
--   sqlite3 events.db < plans.sql
--
-- Everything here is EXPLAIN QUERY PLAN. It costs nothing, changes nothing,
-- and is the only honest way to find out what the engine intends to do.
-- Run it before you optimise anything, and again afterwards.
--
-- Dot-commands are instructions to the shell, not SQL: no semicolon, and
-- never a trailing comment on the same line.
.headers on
.mode box

.print ''
.print '=== 0. What indexes exist right now ==='
-- sqlite_schema is an ordinary table. Your indexes are rows in it.
SELECT name, tbl_name, sql FROM sqlite_schema WHERE type = 'index';

.print ''
.print '=== 1. A lookup with no index: SCAN means every row ==='
EXPLAIN QUERY PLAN
SELECT event_id, model, score FROM events WHERE run_id = 200;

.print ''
.print '=== 2. The same lookup, with an index ==='
CREATE INDEX IF NOT EXISTS ix_run ON events(run_id);
EXPLAIN QUERY PLAN
SELECT event_id, model, score FROM events WHERE run_id = 200;

.print ''
.print '=== 3. And the answers are identical, which is the point ==='
SELECT count(*) AS rows_found, round(avg(score), 4) AS mean_score
FROM events WHERE run_id = 200;

.print ''
.print '=== 4. Covering: every column the query wants is in the index ==='
CREATE INDEX IF NOT EXISTS ix_run_score ON events(run_id, score);
EXPLAIN QUERY PLAN
SELECT score FROM events WHERE run_id = 200;

.print ''
.print '=== 5. ORDER BY with no usable index builds a temporary tree ==='
DROP INDEX IF EXISTS ix_created;
EXPLAIN QUERY PLAN
SELECT event_id, created_on FROM events ORDER BY created_on LIMIT 20;

.print ''
.print '=== 6. ORDER BY served straight off the index: no sort at all ==='
CREATE INDEX IF NOT EXISTS ix_created ON events(created_on);
EXPLAIN QUERY PLAN
SELECT event_id, created_on FROM events ORDER BY created_on LIMIT 20;

.print ''
.print '=== 7. The leftmost prefix, in three plans ==='
DROP INDEX IF EXISTS ix_run;
DROP INDEX IF EXISTS ix_run_score;
DROP INDEX IF EXISTS ix_created;
CREATE INDEX ix_run_status ON events(run_id, status);
.print '--- both columns: SEARCH'
EXPLAIN QUERY PLAN
SELECT count(*) FROM events WHERE run_id = 200 AND status = 'failed';
.print '--- leading column only: SEARCH'
EXPLAIN QUERY PLAN
SELECT count(*) FROM events WHERE run_id = 200;
.print '--- trailing column only: SCAN, because the index is sorted by run_id first'
EXPLAIN QUERY PLAN
SELECT count(*) FROM events WHERE status = 'failed';

.print ''
.print '=== 8. A function on the column puts the answer out of reach ==='
DROP INDEX IF EXISTS ix_run_status;
CREATE INDEX ix_trace ON events(trace_id);
.print '--- plain equality: SEARCH'
EXPLAIN QUERY PLAN
SELECT event_id FROM events WHERE trace_id = 'tr-407080-72';
.print '--- wrapped in lower(): SCAN, with the index sitting right there'
EXPLAIN QUERY PLAN
SELECT event_id FROM events WHERE lower(trace_id) = 'tr-407080-72';
.print '--- the fix: an index on the expression itself'
CREATE INDEX ix_lower_trace ON events(lower(trace_id));
EXPLAIN QUERY PLAN
SELECT event_id FROM events WHERE lower(trace_id) = 'tr-407080-72';

.print ''
.print '=== 9. What ANALYZE writes down ==='
ANALYZE;
SELECT tbl, idx, stat FROM sqlite_stat1 WHERE idx IS NOT NULL ORDER BY idx;

.print ''
.print '=== 10. Tidy up, so the next script starts from a bare table ==='
DROP INDEX IF EXISTS ix_trace;
DROP INDEX IF EXISTS ix_lower_trace;
ANALYZE;
SELECT count(*) AS named_indexes_remaining
FROM sqlite_schema WHERE type = 'index' AND sql IS NOT NULL;

"""The whole idea, in plain Python, before any database is involved.

    python3 scan_vs_bisect.py

An index is a second, sorted copy of some values that lets you find a row
by halving the search space instead of walking it. You do not need SQLite
to see what that buys — you need a list.

Two functions find the same value in the same data:

  * `scan`   walks from the front, comparing every element until it hits
             the one it wants. This is what a table scan is.
  * `seek`   uses `bisect`, the standard library's binary search, which
             halves the remaining range on every comparison. This is what
             an index seek is.

Both answer identically. Every lookup below is checked against the other
implementation and the script exits non-zero if they ever disagree, so
what follows is a difference in COST and never in ANSWER — which is the
single most important property of an index.

Two kinds of number are printed, and they are not equally trustworthy:

  * STEPS are counted, not timed. They are the same on every machine, in
    every year, in any language. This is the shape.
  * MICROSECONDS are measured on whatever computer you are sitting at.
    They will not match mine and are not supposed to.

Watch the steps column. Ten times the data costs the scan ten times the
work and costs the binary search about three more comparisons, because
three comparisons is what it takes to halve something ten times over.
"""

from __future__ import annotations

import bisect
import math
import random
import sys
import time

SEED = 20260816
SIZES = [
    (1_000, 2_000),
    (10_000, 500),
    (100_000, 100),
    (1_000_000, 20),
]


def scan(data, target):
    """A table scan: look at every element until you find it."""
    for position, value in enumerate(data):
        if value == target:
            return position
    return -1


def seek(data, target):
    """An index seek: binary search over the same values, kept sorted."""
    position = bisect.bisect_left(data, target)
    if position < len(data) and data[position] == target:
        return position
    return -1


def scan_steps(data, target):
    """How many comparisons the scan actually performed."""
    steps = 0
    for value in data:
        steps += 1
        if value == target:
            break
    return steps


def seek_steps(data, target):
    """How many comparisons a binary search performs. Hand-written so the
    count is visible rather than hidden inside bisect."""
    low, high, steps = 0, len(data), 0
    while low < high:
        steps += 1
        middle = (low + high) // 2
        if data[middle] < target:
            low = middle + 1
        else:
            high = middle
    return steps


def measure(size, lookups):
    data = list(range(0, size * 3, 3))  # sorted, with gaps, no duplicates
    rng = random.Random(SEED)
    targets = [data[rng.randrange(size)] for _ in range(lookups)]

    started = time.perf_counter()
    scan_answers = [scan(data, target) for target in targets]
    scan_us = (time.perf_counter() - started) / lookups * 1e6

    started = time.perf_counter()
    seek_answers = [seek(data, target) for target in targets]
    seek_us = (time.perf_counter() - started) / lookups * 1e6

    if scan_answers != seek_answers:
        raise AssertionError("scan and seek disagreed — an index changed an answer")

    return {
        "size": size,
        "lookups": lookups,
        "scan_us": scan_us,
        "seek_us": seek_us,
        "scan_steps": sum(scan_steps(data, t) for t in targets) / lookups,
        "seek_steps": sum(seek_steps(data, t) for t in targets) / lookups,
    }


def main() -> int:
    print("Finding one value among n, two ways. Same answers, different cost.")
    print(f"Seeded with {SEED}, so the targets are the same on every run.")
    print()
    header = (
        f"{'n':>11} | {'scan us':>9} | {'bisect us':>9} | {'faster':>8} |"
        f" {'scan steps':>11} | {'bisect steps':>12} | {'log2(n)':>7}"
    )
    print(header)
    print("-" * len(header))

    results = []
    for size, lookups in SIZES:
        row = measure(size, lookups)
        results.append(row)
        print(
            f"{row['size']:>11,} | {row['scan_us']:>9.2f} | {row['seek_us']:>9.3f} |"
            f" {row['scan_us'] / row['seek_us']:>7.0f}x |"
            f" {row['scan_steps']:>11,.0f} | {row['seek_steps']:>12.1f} |"
            f" {math.log2(row['size']):>7.1f}"
        )

    print()
    first, last = results[0], results[-1]
    growth = last["size"] / first["size"]
    print(f"The data grew {growth:,.0f}x between the first row and the last.")
    print(
        f"  scan steps grew   {last['scan_steps'] / first['scan_steps']:>8,.0f}x"
        "   — the same shape as the data. This is O(n)."
    )
    print(
        f"  bisect steps grew {last['seek_steps'] / first['seek_steps']:>8,.1f}x"
        "   — ten comparisons became twenty. This is O(log n)."
    )
    print()
    print("Every scan answer matched every bisect answer. Sorting the data")
    print("changed the work and not the result. That is what an index is.")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

"""Timing helpers shared by every measuring script in the Day 089 lab.

One number is not a measurement. A single run of a query on a real machine
competes with your browser, your editor, the operating system's own
housekeeping and whatever the page cache happens to be holding, so the
first number you see is worth roughly nothing on its own.

Everything here therefore runs the same work several times and reports
three figures:

  * BEST     — the fastest run. The closest you get to "the work itself",
               because it is the run that was interrupted least.
  * MEDIAN   — the middle run. What you would typically wait.
  * SPREAD   — worst minus best. How noisy the machine was while you asked.

Read best and median together. If they are close, the number means
something. If the spread is larger than the difference you are trying to
demonstrate, you have not demonstrated anything and you need more rows,
not more repeats.

Nothing here is a benchmark suite. It is the smallest honest thing.
"""

from __future__ import annotations

import statistics
import time

REPEATS = 7
"""Odd, so the median is a real sample rather than an average of two."""


def time_call(work, repeats=REPEATS):
    """Run `work` `repeats` times and report best, median, worst and spread.

    `work` must be callable with no arguments. Its return value from the
    LAST run is kept, so a caller can both time a query and use its rows.
    """
    samples = []
    result = None
    for _ in range(repeats):
        started = time.perf_counter()
        result = work()
        samples.append((time.perf_counter() - started) * 1000.0)
    return {
        "best_ms": min(samples),
        "median_ms": statistics.median(samples),
        "worst_ms": max(samples),
        "spread_ms": max(samples) - min(samples),
        "repeats": repeats,
        "result": result,
    }


def time_query(connection, sql, params=()):
    """Time a query, fetching every row.

    fetchall() matters. Without it you would time only how long SQLite
    takes to PREPARE the statement and produce the first row, which for a
    scan is misleadingly quick — the work happens as you step through.
    """
    return time_call(lambda: connection.execute(sql, params).fetchall())


def fmt(measurement):
    """One aligned line: best, median and how noisy the machine was."""
    return (
        f"best {measurement['best_ms']:9.3f} ms"
        f" | median {measurement['median_ms']:9.3f} ms"
        f" | spread {measurement['spread_ms']:7.3f} ms"
    )


def plan(connection, sql, params=()):
    """The planner's own description of how it intends to answer.

    EXPLAIN QUERY PLAN returns one row per step. The last column is the
    human-readable detail — "SCAN events", "SEARCH events USING INDEX ...".
    Joined with " / " so a multi-step plan fits on one line.
    """
    rows = connection.execute("EXPLAIN QUERY PLAN " + sql, params).fetchall()
    return " / ".join(str(row[-1]) for row in rows)


def drop_all_indexes(connection):
    """Remove every index you created, leaving the implicit ones alone.

    `sql IS NULL` in sqlite_schema marks an index SQLite made for itself —
    the one behind a UNIQUE or PRIMARY KEY constraint. Those cannot be
    dropped and should not be. Everything with a `sql` value is one
    somebody typed, and this lab types a lot of them.

    Every measuring script calls this first, so each one starts from the
    same bare table no matter what the previous script left behind.
    """
    names = [
        row[0]
        for row in connection.execute(
            "SELECT name FROM sqlite_schema WHERE type = 'index' AND sql IS NOT NULL"
        ).fetchall()
    ]
    for name in names:
        connection.execute(f'DROP INDEX "{name}"')
    return names


def file_pages(connection):
    """Pages actually in use, and the page size, so index cost can be
    reported in bytes.

    `page_count` alone would lie after a DROP INDEX: the pages are handed
    to the database's free list and the file does not shrink. Subtracting
    `freelist_count` gives the pages holding real data, which is the
    figure that goes back up when you create the next index.
    """
    page_size = connection.execute("PRAGMA page_size").fetchone()[0]
    page_count = connection.execute("PRAGMA page_count").fetchone()[0]
    free = connection.execute("PRAGMA freelist_count").fetchone()[0]
    return page_count - free, page_size


def ratio(slow, fast):
    """How many times faster, on the best-of-N figure. Never divide by zero."""
    if fast["best_ms"] <= 0:
        return float("inf")
    return slow["best_ms"] / fast["best_ms"]

"""The other half of the trade: what indexes cost on the way in.

    python3 write_cost.py

Every lesson about indexes shows the read getting faster. This is the
half that decides whether you should have added it.

An index is a second sorted structure holding the same values. Every
INSERT has to put a new entry in the right place in every one of them.
Every DELETE has to take one out of each. Every UPDATE that changes an
indexed column has to do both. None of that work exists on a table with
no indexes.

The experiment: build two identical tables of 100,000 rows in a temporary
directory. Give one of them five indexes. Insert the same further 100,000
rows into each and time it, three times per configuration so the numbers
are not a single sample. Report the time and the space.

The rows are the deterministic ones from generate.py, so this is the same
data every run, on any machine.
"""

from __future__ import annotations

import shutil
import sqlite3
import statistics
import sys
import tempfile
import time
from pathlib import Path

from generate import SCHEMA, rows
from timing import file_pages

BASE_ROWS = 100_000
ADDED_ROWS = 100_000
TRIALS = 3

INSERT = (
    "INSERT INTO events"
    " (event_id, run_id, trace_id, model, status, score, created_on, note)"
    " VALUES (?, ?, ?, ?, ?, ?, ?, ?)"
)

INDEXES = [
    "CREATE INDEX ix_run ON events(run_id)",
    "CREATE INDEX ix_trace ON events(trace_id)",
    "CREATE INDEX ix_created ON events(created_on)",
    "CREATE INDEX ix_model_status ON events(model, status)",
    "CREATE INDEX ix_status_score ON events(status, score)",
]


def one_trial(directory: Path, label: str, index_sql: list[str], base, extra):
    path = directory / f"{label}.db"
    if path.exists():
        path.unlink()
    connection = sqlite3.connect(path)
    connection.executescript(SCHEMA)
    with connection:
        connection.executemany(INSERT, base)
    for statement in index_sql:
        connection.execute(statement)
    connection.commit()

    pages_before, page_size = file_pages(connection)

    started = time.perf_counter()
    with connection:
        connection.executemany(INSERT, extra)
    elapsed_ms = (time.perf_counter() - started) * 1000.0

    pages_after, _ = file_pages(connection)
    connection.close()
    path.unlink()
    return {
        "ms": elapsed_ms,
        "pages_before": pages_before,
        "pages_after": pages_after,
        "page_size": page_size,
    }


def run(directory: Path, label: str, index_sql: list[str], base, extra):
    trials = [one_trial(directory, label, index_sql, base, extra) for _ in range(TRIALS)]
    times = [trial["ms"] for trial in trials]
    last = trials[-1]
    return {
        "label": label,
        "indexes": len(index_sql),
        "best_ms": min(times),
        "median_ms": statistics.median(times),
        "worst_ms": max(times),
        "pages_before": last["pages_before"],
        "pages_after": last["pages_after"],
        "page_size": last["page_size"],
    }


def main() -> int:
    print("What indexes cost on the way in.")
    print(
        f"Each configuration: build {BASE_ROWS:,} rows, add the indexes,"
        f" then insert {ADDED_ROWS:,} more."
    )
    print(f"{TRIALS} trials each, in a temporary directory. Same rows every time.")
    print()

    batch = list(rows(BASE_ROWS + ADDED_ROWS))
    base, extra = batch[:BASE_ROWS], batch[BASE_ROWS:]

    workspace = Path(tempfile.mkdtemp(prefix="day089-write-"))
    try:
        bare = run(workspace, "bare", [], base, extra)
        indexed = run(workspace, "indexed", INDEXES, base, extra)
    finally:
        shutil.rmtree(workspace, ignore_errors=True)

    header = (
        f"{'configuration':<16} | {'indexes':>7} | {'best ms':>9} |"
        f" {'median ms':>10} | {'worst ms':>9}"
    )
    print(header)
    print("-" * len(header))
    for result in (bare, indexed):
        print(
            f"{result['label']:<16} | {result['indexes']:>7} |"
            f" {result['best_ms']:>9.1f} | {result['median_ms']:>10.1f} |"
            f" {result['worst_ms']:>9.1f}"
        )

    slowdown = indexed["best_ms"] / bare["best_ms"]
    print()
    print(
        f"Inserting the same {ADDED_ROWS:,} rows took {slowdown:.1f}x longer"
        " with five indexes."
    )
    print(
        f"Per row: {bare['best_ms'] / ADDED_ROWS * 1000:.2f} microseconds bare,"
        f" {indexed['best_ms'] / ADDED_ROWS * 1000:.2f} microseconds indexed."
    )
    print()

    for result in (bare, indexed):
        page_size = result["page_size"]
        print(
            f"{result['label']:<16} pages {result['pages_before']:>7,}"
            f" -> {result['pages_after']:>7,}"
            f"  ({result['pages_after'] * page_size:>12,} bytes on disk)"
        )
    space = indexed["pages_after"] / bare["pages_after"]
    print()
    print(f"The indexed database is {space:.1f}x the size of the bare one for the")
    print("same rows. Five indexes are five more sorted copies of five more")
    print("column sets, and they live in the same file.")
    print()
    print("Read this next to the read measurements, not instead of them. An")
    print("index that turns a 9 ms scan into a 0.03 ms seek on a query you run")
    print("a thousand times an hour is obviously worth a slower insert. An")
    print("index nothing queries is pure cost, paid on every single write,")
    print("forever, and it will not show up in any timing you are looking at.")
    return 0


if __name__ == "__main__":
    raise SystemExit(main())

lesson_id: D089
day: 89
kind: guided-build
languages: [sql, python, bash]
setup_commands:
  - cd labs/sections/programming-with-python/day-089-indexes-and-query-performance
  - sqlite3 --version
  - 'python3 -c "import sqlite3; print(sqlite3.sqlite_version)"'
  - mkdir -p scratch && cp examples/* scratch/
run_commands:
  - cd scratch && python3 scan_vs_bisect.py
  - cd scratch && python3 generate.py events.db
  - cd scratch && python3 lookup.py events.db
  - cd scratch && python3 composite.py events.db
  - cd scratch && python3 blocked.py events.db
  - cd scratch && python3 write_cost.py
  - cd scratch && sqlite3 events.db < plans.sql
  - cd starter && python3 ../examples/generate.py mine.db 200000
  - cd starter && sqlite3 mine.db < indexes.sql
  - cd starter && python3 measure.py mine.db
test_commands:
  - bash tests/run_tests.sh
cleanup_commands:
  - rm -rf scratch
  - rm -f starter/mine.db starter/events.db
  - find . -type d -name __pycache__ -prune -exec rm -rf -- {} +
  - 'git checkout -- starter/  # optional: reset your work'
requires_network: false
requires_api_key: false
estimated_minutes: 30
last_executed: '2026-08-16'
executed_on: 'macOS 26.5.2 (Apple Silicon, arm64), Python 3.14.0, bash 3.2.57, sqlite3 shell 3.51.0, SQLite 3.53.3 as linked into Python — bash tests/run_tests.sh -> 40 checks, 0 failure(s), exit 0'

# What this lab needs, and where it comes from

Nothing to install. Same as Day 85: SQLite is not a service you run, it is
a library already inside the tools you have.

## The two things you need

| Thing | Where it comes from | Cost | How to check |
| --- | --- | --- | --- |
| The `sqlite3` command-line shell | Preinstalled on macOS. On Debian or Ubuntu, `sudo apt install sqlite3`; on Fedora, `sudo dnf install sqlite`. On Windows, use WSL, or download the precompiled shell from the SQLite website | Free; public domain | `sqlite3 --version` |
| The `sqlite3` Python module | Part of the Python standard library since Python 2.5. You already have it | Free; part of Python | `python3 -c "import sqlite3; print(sqlite3.sqlite_version)"` |

Python **3.11 or newer** is what the captures were taken on (3.14.0).
Nothing here needs a feature newer than that.

## Two SQLite versions on one machine is normal

```bash
sqlite3 --version
python3 -c "import sqlite3; print(sqlite3.sqlite_version)"
```

On the authoring machine these print **3.51.0** and **3.53.3**. The shell
is a program that links its own copy of SQLite; the Python module is a
different program that links its own. Both read and write the same file
format. `tests/run_tests.sh` reports both and asserts only that each is
readable — it deliberately does not require them to be equal.

It matters slightly more today than it did on Day 85. The query planner is
part of the library, so two versions can legitimately choose two different
plans for the same query on the same data. If a plan in
`expected-output/` differs from yours, check which SQLite you are running
before assuming anything is wrong.

## What the lab deliberately does not use

- **No benchmarking framework.** `timeit`, `pytest-benchmark` and the rest
  are good tools, and all of them would put a layer between you and the
  thing being measured. `examples/timing.py` is thirty lines you can read
  in a minute: run it seven times, report best, median and spread.
- **No third-party package at all.** `tests/run_tests.sh` greps every
  Python file for an import of `requests`, `httpx`, `urllib3`, `pandas`,
  `numpy` or `sqlalchemy` and fails if it finds one. On a lab about
  timings, an unexpected import is an unexpected variable.
- **No network.** The same suite fails if any executable lab file contains
  a URL. There is nothing to download.
- **No ORM.** You need to see the SQL to see the plan.

## Disk and time

`generate.py` builds a 400,000-row table of about **30 MB**. The write-cost
experiment builds several smaller databases, the largest about **35 MB**,
all inside a temporary directory that is removed when it finishes. The
full test suite took about **12 seconds** on the authoring machine and
leaves nothing behind.

If disk space is genuinely tight, every script takes a row count:

```bash
python3 generate.py events.db 100000
```

The shapes still show at 100,000 rows. Below about 50,000 the differences
start hiding inside the noise, which is itself worth seeing once.

## If the shell is missing

Everything except `plans.sql` and `starter/indexes.sql` can be done from
Python alone, because the module carries its own copy of the engine.
`tests/run_tests.sh` needs the shell and says so rather than silently
skipping checks; point it at one you have with
`SQLITE=/path/to/sqlite3 bash tests/run_tests.sh`.

# Day 089 — Make It Fast
#
# This file is deliberately empty of packages.
#
# There is nothing to install. The lab needs Python 3.11 or newer and the
# sqlite3 command-line shell, and both `sqlite3` the shell and `sqlite3`
# the Python module ship with their respective tools. No pip install, no
# virtual environment, no network.
#
# It matters more than usual here that no third-party package is involved.
# This is a lab about measurement, and every package you add is another
# thing that could be doing work you did not ask for while you are timing
# something. The only imports are sqlite3, time, statistics, bisect,
# random, tempfile and pathlib — all standard library.
#
# It exists so that `pip install -r requirements/requirements.txt`
# succeeds and does nothing, and so that the absence of dependencies is a
# written-down decision rather than an omission somebody has to guess at.
#
# See requirements/README.md for what the lab uses and where each piece
# comes from.

-- YOUR WORK — the indexes, written by you.
--
--   python3 ../examples/generate.py mine.db 200000
--   sqlite3 mine.db < indexes.sql
--
-- Six numbered exercises. The file APPLIES AS SHIPPED: run it now and it
-- will print the plans for the queries below, all of them scans, because
-- you have not created anything yet. Add one index per exercise and run it
-- again; each plan should change from SCAN to SEARCH.
--
-- Never guess. EXPLAIN QUERY PLAN costs nothing and is right.
.headers on
.mode box
.print ''
.print '=== The queries this file is about, and how they are answered now ==='

-- ---------------------------------------------------------------------------
-- EXERCISE 1 — the plain lookup.
--
-- Query A finds the events of one run. Write an index that turns its plan
-- from "SCAN events" into "SEARCH events USING INDEX ...".
--
-- Name it ix_run. One column.
-- Checked by: "exercise 1: a single-column index turns the run lookup into a seek"
-- >>> WRITE YOUR CREATE INDEX HERE <<<

.print '--- A: the events of one run'
EXPLAIN QUERY PLAN
SELECT event_id, model, score FROM events WHERE run_id = 200;

-- ---------------------------------------------------------------------------
-- EXERCISE 2 — the composite index, and the leftmost-prefix rule.
--
-- Query B filters on run_id AND status. Query C filters on status alone.
-- Write ONE index, named ix_run_status, on (run_id, status).
--
-- Predict both plans BEFORE you run it, and write your prediction down.
-- One of B and C will seek and the other will not, and the reason is that
-- an index on (run_id, status) is sorted by run_id first — so status is
-- only in order inside a single run_id.
-- Checked by: "exercise 2: the composite index serves B and cannot serve C"
-- >>> WRITE YOUR CREATE INDEX HERE <<<

.print '--- B: one run, failures only'
EXPLAIN QUERY PLAN
SELECT count(*) FROM events WHERE run_id = 200 AND status = 'failed';
.print '--- C: failures across every run'
EXPLAIN QUERY PLAN
SELECT count(*) FROM events WHERE status = 'failed';

-- ---------------------------------------------------------------------------
-- EXERCISE 3 — the covering index.
--
-- Query D asks only for score. Write an index named ix_run_score that lets
-- SQLite answer it WITHOUT OPENING THE TABLE AT ALL. You will know you have
-- it when the plan says COVERING INDEX.
--
-- The trick is not a special kind of index. It is putting every column the
-- query mentions into an ordinary one.
-- Checked by: "exercise 3: the covering index answers without touching the table"
-- >>> WRITE YOUR CREATE INDEX HERE <<<

.print '--- D: just the scores for one run'
EXPLAIN QUERY PLAN
SELECT score FROM events WHERE run_id = 200;

-- ---------------------------------------------------------------------------
-- EXERCISE 4 — an index that removes a sort.
--
-- Query E wants the twenty oldest events. Without help the plan contains
-- USE TEMP B-TREE FOR ORDER BY: SQLite sorted every row to hand back twenty.
--
-- Write an index named ix_created that makes that line disappear. An index
-- is already in order; a query that wants that order can just walk it.
-- Checked by: "exercise 4: ORDER BY no longer builds a temporary B-tree"
-- >>> WRITE YOUR CREATE INDEX HERE <<<

.print '--- E: the twenty oldest events'
EXPLAIN QUERY PLAN
SELECT event_id, created_on FROM events ORDER BY created_on LIMIT 20;

-- ---------------------------------------------------------------------------
-- EXERCISE 5 — the partial index.
--
-- Query F asks about failures in a date range. About one row in ten is a
-- failure, so an index over all 200,000 rows is mostly dead weight.
--
-- Write an index named ix_failed_created on events(created_on) with a
-- WHERE clause restricting it to status = 'failed'. Then check the last
-- query in this file: the planner will not use a partial index for a query
-- it cannot prove falls inside that WHERE clause, and that is correct
-- behaviour rather than a disappointment.
-- Checked by: "exercise 5: the partial index serves the failure query only"
-- >>> WRITE YOUR CREATE INDEX HERE <<<

.print '--- F: recent failures'
EXPLAIN QUERY PLAN
SELECT count(*) FROM events
WHERE status = 'failed' AND created_on >= '2025-06-01';

-- ---------------------------------------------------------------------------
-- EXERCISE 6 — the query the index cannot help, and the rewrite that can.
--
-- Query G wraps the indexed column in lower(), so ix_trace below cannot be
-- used: the index holds trace_id, and the query asks about lower(trace_id),
-- which is a different set of values.
--
-- Write a second index, named ix_lower_trace, ON THE EXPRESSION, so that G
-- seeks. The syntax is CREATE INDEX ... ON events(lower(trace_id)).
--
-- Then answer this in a comment, in your own words: when would you rather
-- store lower(trace_id) as its own column instead?
-- Checked by: "exercise 6: an expression index rescues the wrapped column"
CREATE INDEX IF NOT EXISTS ix_trace ON events(trace_id);
-- >>> WRITE YOUR SECOND CREATE INDEX HERE <<<

.print '--- G: a trace id, matched case-insensitively'
EXPLAIN QUERY PLAN
SELECT event_id FROM events WHERE lower(trace_id) = 'tr-407080-72';

-- ---------------------------------------------------------------------------
.print ''
.print '=== What you have built ==='
SELECT name FROM sqlite_schema WHERE type = 'index' AND sql IS NOT NULL ORDER BY name;

.print ''
.print '=== And what it cost: pages in use, and rows per distinct key ==='
ANALYZE;
SELECT idx AS index_name, stat AS rows_and_average_per_key
FROM sqlite_stat1 WHERE idx IS NOT NULL ORDER BY idx;

"""YOUR WORK — the measuring tool, built from nothing.

    python3 ../examples/generate.py events.db 200000
    python3 measure.py events.db

Five numbered exercises. The file runs as shipped: it will tell you which
exercise is next and exit non-zero, so an unfinished lab can never look
finished. Complete them in order and the last run prints a table of
measurements and exits 0.

The rule for this whole lab: you are not allowed to believe anything you
did not time. That includes believing that indexes help.

Each exercise names the check in tests/run_tests.sh that confirms it.
"""

from __future__ import annotations

import sqlite3
import statistics
import sys
import time
from pathlib import Path

REPEATS = 7
QUERY = "SELECT event_id, model, score FROM events WHERE run_id = ?"
TARGET_RUN = 200


def next_exercise(number: int, what: str):
    """Stop with the next exercise named, rather than with a traceback."""
    print(f"EXERCISE {number} is not done yet: {what}")
    print(f"Open {Path(__file__).name} and look for '# EXERCISE {number}'.")
    raise SystemExit(1)


# EXERCISE 1 — best and median.
#
# Given a list of durations in milliseconds, return a dict with keys
# "best_ms", "median_ms" and "spread_ms" (worst minus best).
#
# Why both: the BEST run is the closest you get to the work itself, because
# it is the run the operating system interrupted least. The MEDIAN is what
# you would typically wait. If they are far apart, the machine was busy and
# the number means less than it looks like it does.
#
# `statistics.median` is imported for you.
# Checked by: "best, median and spread are computed from the samples"
def summarise(samples):
    next_exercise(1, "compute best, median and spread from a list of durations")


# EXERCISE 2 — time a query properly.
#
# Run `connection.execute(sql, params).fetchall()` REPEATS times, timing
# each run with `time.perf_counter()`, and return summarise(...) of the
# durations in MILLISECONDS, plus the rows from the last run under the key
# "result".
#
# fetchall() is not optional. Without it you time how long SQLite takes to
# prepare the statement and produce the first row — which for a full scan
# is misleadingly fast, because the scanning happens as you step.
#
# Checked by: "the timing helper runs the query more than once"
def time_query(connection, sql, params=()):
    next_exercise(2, "run the query REPEATS times and summarise the durations")


# EXERCISE 3 — ask the planner what it intends to do.
#
# Run "EXPLAIN QUERY PLAN " + sql and return the last column of every row,
# joined with " / ". That last column is the human-readable detail:
# "SCAN events", "SEARCH events USING INDEX ix_run (run_id=?)", and so on.
#
# Checked by: "the plan helper returns the planner's own description"
def plan(connection, sql, params=()):
    next_exercise(3, "return EXPLAIN QUERY PLAN's detail column, joined with ' / '")


# EXERCISE 4 — the one word that decides everything.
#
# Return True if the plan text describes a seek, and False if anything in
# it is a scan.
#
# Be careful here, because this is the trap the lesson is about: a plan can
# name your index and still be a scan. "SCAN events USING COVERING INDEX
# ix_trace" means the engine walked every entry of the index instead of
# every row of the table — narrower, still linear, still not a seek. Only
# SEARCH means a descent to the matching rows.
#
# Checked by: "a plan naming an index is still a scan unless it says SEARCH"
def is_seek(plan_text):
    next_exercise(4, "return True only when no step of the plan is a SCAN")


def show(connection, label, sql, params=()):
    measurement = time_query(connection, sql, params)
    plan_text = plan(connection, sql, params)
    verdict = "SEEK" if is_seek(plan_text) else "SCAN"
    print(f"  {label}")
    print(f"    plan : [{verdict}] {plan_text}")
    print(
        f"    time : best {measurement['best_ms']:8.3f} ms"
        f" | median {measurement['median_ms']:8.3f} ms"
        f" | spread {measurement['spread_ms']:6.3f} ms"
        f" | rows {len(measurement['result']):,}"
    )
    return plan_text, measurement


def main(argv: list[str]) -> int:
    path = Path(argv[1]) if len(argv) > 1 else Path("events.db")
    if not path.exists():
        print(f"{path} does not exist. Build it first:", file=sys.stderr)
        print(f"  python3 ../examples/generate.py {path} 200000", file=sys.stderr)
        return 2

    connection = sqlite3.connect(path)
    for row in connection.execute(
        "SELECT name FROM sqlite_schema WHERE type = 'index' AND sql IS NOT NULL"
    ).fetchall():
        connection.execute(f'DROP INDEX "{row[0]}"')

    # A one-line self-check, so the exercises are reported in the order you
    # are meant to build them rather than the order the code happens to
    # reach them.
    summarise([3.0, 1.0, 2.0])

    total = connection.execute("SELECT count(*) FROM events").fetchone()[0]
    print(f"{path.name}: {total:,} rows, no indexes of your own yet")
    print(f"Query: {QUERY}   (run_id = {TARGET_RUN})")
    print()

    before_plan, before = show(connection, "before any index", QUERY, (TARGET_RUN,))

    # EXERCISE 5 — create the index, then measure again.
    #
    # Create an index named ix_run on events(run_id), then delete the line
    # below. One statement. This is the entire intervention.
    #
    # Checked by: "the starter creates an index and re-measures"
    next_exercise(5, "CREATE INDEX ix_run ON events(run_id), then remove this line")

    after_plan, after = show(connection, "after CREATE INDEX", QUERY, (TARGET_RUN,))

    same = sorted(before["result"]) == sorted(after["result"])
    faster = before["best_ms"] / after["best_ms"]
    print()
    print(f"  same rows both times : {same}")
    print(f"  faster by            : {faster:.0f}x on the best-of-{REPEATS} figure")
    print(f"  plan changed         : {before_plan}  ->  {after_plan}")
    print()
    print("  Those milliseconds are yours, from this machine, today. The shape")
    print("  is what travels: one column grows with the table and one does not.")

    connection.execute("DROP INDEX ix_run")
    connection.commit()
    connection.close()

    if not same:
        print("FAIL: the index changed the answer. That must never happen.")
        return 1
    if not is_seek(after_plan):
        print("FAIL: the plan after CREATE INDEX is still a scan.")
        return 1
    return 0


if __name__ == "__main__":
    raise SystemExit(main(sys.argv))

#!/usr/bin/env bash
# Tests for the Day 089 lab. Run from the lab directory:
#   bash tests/run_tests.sh
#
# This suite is about measurements, which makes writing it a lesson in
# itself. There is exactly one rule and it is worth stating before the
# first check:
#
#   NO CHECK HERE ASSERTS A MILLISECOND FIGURE.
#
# A test that says "the indexed lookup takes under 0.05 ms" passes on the
# machine it was written on and fails on a busy laptop, a slower disk, a
# continuous-integration container or the same machine next year. It would
# not be measuring the lab; it would be measuring the computer. Every
# check below asserts a SHAPE instead:
#
#   * the plan changed from SCAN to SEARCH
#   * the two results contain exactly the same rows
#   * the indexed lookup is at least 20x faster than the scan
#   * inserting with five indexes is at least 1.5x slower than without
#   * a composite index serves these query shapes and cannot serve that one
#
# The two ratio thresholds are deliberately far below what the authoring
# machine measured — 20x against roughly 300x, and 1.5x against roughly
# 12x — so that a slow or noisy machine still passes while a genuinely
# broken lab still fails. That gap is the whole craft of testing around a
# measurement: assert the direction and an order of magnitude, never the
# number.
#
# Everything runs offline. No server, no network call, no third-party
# package: the standard library and the sqlite3 shell. Every database is
# built inside a temporary directory removed by a trap, so a completed run
# leaves nothing behind.
set -u

export PYTHONDONTWRITEBYTECODE=1

lab_dir="$(cd "$(dirname "${BASH_SOURCE[0]}")/.." && pwd)"
failures=0
checks=0
work_root=""

check() {
  local label="$1" ok="$2"
  checks=$((checks + 1))
  if [ "${ok}" = "yes" ]; then
    echo "  ok: ${label}"
  else
    echo "  FAIL: ${label}"
    failures=$((failures + 1))
  fi
}

cleanup() {
  [ -n "${work_root}" ] && [ -d "${work_root}" ] && rm -rf "${work_root}"
}
trap cleanup EXIT INT TERM

resolve_tool() {
  local tool="$1" override="$2"
  if [ -n "${override}" ] && [ -x "${override}" ]; then echo "${override}"; return 0; fi
  if command -v "${tool}" >/dev/null 2>&1; then command -v "${tool}"; return 0; fi
  return 1
}

python_bin="$(resolve_tool python3 "${PYTHON:-}")" || {
  echo "FAIL: python3 not found on PATH." >&2
  echo "  Install Python 3.11 or newer and try again." >&2
  exit 1
}
sqlite_bin="$(resolve_tool sqlite3 "${SQLITE:-}")" || {
  echo "FAIL: the sqlite3 shell was not found on PATH." >&2
  echo "  macOS ships it. On Debian or Ubuntu: sudo apt install sqlite3" >&2
  echo "  Or point this suite at one: SQLITE=/path/to/sqlite3 bash tests/run_tests.sh" >&2
  exit 1
}

work_root="$(mktemp -d "${TMPDIR:-/tmp}/day089-XXXXXX")"
work="${work_root}/lab"
mkdir -p "${work}"
cp "${lab_dir}/examples/"*.py "${lab_dir}/examples/"*.sql "${work}/"

echo "Day 089 — Make It Fast"
echo

# ===========================================================================
echo "1. The tools report themselves, and they do not have to agree"
# ===========================================================================
shell_version="$("${sqlite_bin}" --version 2>/dev/null | awk '{print $1}')"
module_version="$("${python_bin}" -c 'import sqlite3; print(sqlite3.sqlite_version)' 2>/dev/null)"
echo "     sqlite3 shell library:  ${shell_version:-unknown}"
echo "     python3 module library: ${module_version:-unknown}"
case "${shell_version}" in
  3.*) check "the sqlite3 shell reports a SQLite 3 library version" "yes" ;;
  *)   check "the sqlite3 shell reports a SQLite 3 library version" "no" ;;
esac
case "${module_version}" in
  3.*) check "python3 can import sqlite3 and report its library version" "yes" ;;
  *)   check "python3 can import sqlite3 and report its library version" "no" ;;
esac
# Deliberately not an equality assertion: two programs, two copies of the
# library. On the authoring machine they differ, and that is not a fault.
if [ "${shell_version}" = "${module_version}" ]; then
  echo "     the two agree on this machine"
else
  echo "     the two DIFFER on this machine — this is normal, not a fault"
fi

# ===========================================================================
echo
echo "2. The table is built the same way every time"
# ===========================================================================
if (cd "${work}" && "${python_bin}" generate.py events.db 400000 >/dev/null 2>&1); then
  check "generate.py builds a 400,000-row table" "yes"
else
  check "generate.py builds a 400,000-row table" "no"
fi

rows="$("${sqlite_bin}" "${work}/events.db" "SELECT count(*) FROM events;" 2>/dev/null)"
check "the table holds exactly 400,000 rows" \
  "$([ "${rows}" = "400000" ] && echo yes || echo no)"

named="$("${sqlite_bin}" "${work}/events.db" \
  "SELECT count(*) FROM sqlite_schema WHERE type='index' AND sql IS NOT NULL;" 2>/dev/null)"
check "and no indexes of its own — every one in this lab is added by you" \
  "$([ "${named}" = "0" ] && echo yes || echo no)"

fingerprint="$("${sqlite_bin}" "${work}/events.db" \
  "SELECT trace_id||'|'||model||'|'||status||'|'||score FROM events WHERE event_id=123456;" 2>/dev/null)"
echo "     row 123456: ${fingerprint}"
if (cd "${work}" && "${python_bin}" generate.py again.db 5000 >/dev/null 2>&1 \
    && "${python_bin}" generate.py again2.db 5000 >/dev/null 2>&1); then
  sum_a="$("${sqlite_bin}" "${work}/again.db" "SELECT sum(score), sum(run_id), group_concat(trace_id) FROM events;" 2>/dev/null)"
  sum_b="$("${sqlite_bin}" "${work}/again2.db" "SELECT sum(score), sum(run_id), group_concat(trace_id) FROM events;" 2>/dev/null)"
  check "two builds of the same size are identical — the data is seeded" \
    "$([ -n "${sum_a}" ] && [ "${sum_a}" = "${sum_b}" ] && echo yes || echo no)"
else
  check "two builds of the same size are identical — the data is seeded" "no"
fi
rm -f "${work}/again.db" "${work}/again2.db"

# ===========================================================================
echo
echo "3. The idea in plain Python: a scan grows with n, a search does not"
# ===========================================================================
if (cd "${work}" && "${python_bin}" - <<'PY' >/dev/null 2>&1
import sys
sys.argv = ["scan_vs_bisect.py"]
from scan_vs_bisect import measure

small = measure(1_000, 200)
large = measure(100_000, 50)

# Answers must be identical — that is asserted inside measure(), which
# raises if the two ever disagree.
scan_growth = large["scan_steps"] / small["scan_steps"]
seek_growth = large["seek_steps"] / small["seek_steps"]

# 100x the data. A linear walk must cost far more; a binary search must
# cost barely more. Generous bounds: the shape, not the number.
assert scan_growth > 20, scan_growth
assert seek_growth < 3, seek_growth
assert small["seek_steps"] <= 12, small["seek_steps"]
assert large["seek_steps"] <= 20, large["seek_steps"]
sys.exit(0)
PY
); then
  check "100x the data costs the scan far more steps and bisect barely any" "yes"
else
  check "100x the data costs the scan far more steps and bisect barely any" "no"
fi

if (cd "${work}" && "${python_bin}" - <<'PY' >/dev/null 2>&1
import sys
from scan_vs_bisect import scan, seek, seek_steps

data = list(range(0, 3_000, 3))
for target in (0, 3, 1_500, 2_997, 1, 4_000, -1):
    assert scan(data, target) == seek(data, target), target
# A binary search over 1,000 sorted values takes at most 10 comparisons.
assert seek_steps(data, 1_500) <= 10
sys.exit(0)
PY
); then
  check "the hand-written scan and the binary search never disagree" "yes"
else
  check "the hand-written scan and the binary search never disagree" "no"
fi

if (cd "${work}" && "${python_bin}" scan_vs_bisect.py 2>/dev/null | grep -q "This is O(log n)"); then
  check "scan_vs_bisect.py runs end to end and reports both growth shapes" "yes"
else
  check "scan_vs_bisect.py runs end to end and reports both growth shapes" "no"
fi

# ===========================================================================
echo
echo "4. One CREATE INDEX: same rows, different plan, far less work"
# ===========================================================================
scan_plan="$("${sqlite_bin}" "${work}/events.db" \
  "EXPLAIN QUERY PLAN SELECT event_id, model, score FROM events WHERE run_id = 200;" 2>/dev/null)"
echo "     before: ${scan_plan}"
case "${scan_plan}" in
  *SCAN*) check "with no index the planner reports SCAN" "yes" ;;
  *)      check "with no index the planner reports SCAN" "no" ;;
esac

"${sqlite_bin}" "${work}/events.db" "CREATE INDEX ix_run ON events(run_id);" >/dev/null 2>&1
seek_plan="$("${sqlite_bin}" "${work}/events.db" \
  "EXPLAIN QUERY PLAN SELECT event_id, model, score FROM events WHERE run_id = 200;" 2>/dev/null)"
echo "     after:  ${seek_plan}"
case "${seek_plan}" in
  *"SEARCH events USING INDEX ix_run"*)
    check "with the index it reports SEARCH ... USING INDEX ix_run" "yes" ;;
  *)
    check "with the index it reports SEARCH ... USING INDEX ix_run" "no" ;;
esac
"${sqlite_bin}" "${work}/events.db" "DROP INDEX ix_run;" >/dev/null 2>&1

if (cd "${work}" && "${python_bin}" - <<'PY' >/dev/null 2>&1
"""Same rows, and a margin big enough to survive a slow machine."""
import sqlite3
import sys

from timing import drop_all_indexes, ratio, time_query

QUERY = "SELECT event_id, model, score FROM events WHERE run_id = ?"
MINIMUM_SPEEDUP = 20  # measured about 300x here; 20 leaves room for anything

connection = sqlite3.connect("events.db")
drop_all_indexes(connection)

scanned = time_query(connection, QUERY, (200,))
connection.execute("CREATE INDEX ix_run ON events(run_id)")
sought = time_query(connection, QUERY, (200,))

assert sorted(scanned["result"]) == sorted(sought["result"]), "the index changed the answer"
assert len(sought["result"]) == 100, len(sought["result"])
speedup = ratio(scanned, sought)
assert speedup >= MINIMUM_SPEEDUP, f"only {speedup:.1f}x faster"

drop_all_indexes(connection)
connection.commit()
connection.close()
sys.exit(0)
PY
); then
  check "the indexed lookup returns identical rows and is at least 20x faster" "yes"
else
  check "the indexed lookup returns identical rows and is at least 20x faster" "no"
fi

if (cd "${work}" && "${python_bin}" - <<'PY' >/dev/null 2>&1
"""The scan must grow with the table. That is the shape being taught."""
import sqlite3
import sys
import tempfile
from pathlib import Path

from generate import build
from timing import time_query

QUERY = "SELECT event_id, model, score FROM events WHERE run_id = ?"

with tempfile.TemporaryDirectory() as directory:
    timings = {}
    for size in (50_000, 400_000):
        path = Path(directory) / f"s{size}.db"
        import contextlib
        import io
        with contextlib.redirect_stdout(io.StringIO()):
            build(path, size)
        connection = sqlite3.connect(path)
        timings[size] = time_query(connection, QUERY, (200,))["best_ms"]
        connection.close()

# 8x the rows. A scan should cost several times more. Asserting "more than
# 3x" rather than "8x" leaves room for cache effects and a noisy machine
# while still failing if the cost stopped growing at all.
growth = timings[400_000] / timings[50_000]
assert growth > 3, f"a scan of 8x the table was only {growth:.1f}x the cost"
sys.exit(0)
PY
); then
  check "8x the rows costs the scan several times more — the cost grows with n" "yes"
else
  check "8x the rows costs the scan several times more — the cost grows with n" "no"
fi

# ===========================================================================
echo
echo "5. The leftmost-prefix rule, query shape by query shape"
# ===========================================================================
"${sqlite_bin}" "${work}/events.db" "CREATE INDEX ix_run_status ON events(run_id, status);" >/dev/null 2>&1

prefix_plan() {
  "${sqlite_bin}" "${work}/events.db" "EXPLAIN QUERY PLAN $1" 2>/dev/null | tr '\n' ' '
}

both="$(prefix_plan "SELECT count(*) FROM events WHERE run_id = 200 AND status = 'failed';")"
lead="$(prefix_plan "SELECT count(*) FROM events WHERE run_id = 200;")"
trail="$(prefix_plan "SELECT count(*) FROM events WHERE status = 'failed';")"
swapped="$(prefix_plan "SELECT count(*) FROM events WHERE status = 'failed' AND run_id = 200;")"

case "${both}" in *SEARCH*ix_run_status*) a=yes ;; *) a=no ;; esac
check "an index on (run_id, status) serves WHERE run_id = ? AND status = ?" "${a}"
case "${lead}" in *SEARCH*ix_run_status*) a=yes ;; *) a=no ;; esac
check "and serves the leading column alone" "${a}"
case "${trail}" in *SEARCH*) a=no ;; *SCAN*) a=yes ;; *) a=no ;; esac
check "and CANNOT seek on the trailing column alone — this is the rule" "${a}"
case "${swapped}" in *SEARCH*ix_run_status*) a=yes ;; *) a=no ;; esac
check "the order of conditions in WHERE is irrelevant; column order in the index is not" "${a}"
"${sqlite_bin}" "${work}/events.db" "DROP INDEX ix_run_status;" >/dev/null 2>&1

# ===========================================================================
echo
echo "6. Covering, ORDER BY and partial indexes"
# ===========================================================================
"${sqlite_bin}" "${work}/events.db" "CREATE INDEX ix_run_score ON events(run_id, score);" >/dev/null 2>&1
covering="$(prefix_plan "SELECT score FROM events WHERE run_id = 200;")"
case "${covering}" in
  *"COVERING INDEX ix_run_score"*) a=yes ;; *) a=no ;;
esac
check "a query whose columns are all in the index reports COVERING INDEX" "${a}"
"${sqlite_bin}" "${work}/events.db" "DROP INDEX ix_run_score;" >/dev/null 2>&1

order_before="$(prefix_plan "SELECT event_id, created_on FROM events ORDER BY created_on LIMIT 20;")"
case "${order_before}" in
  *"USE TEMP B-TREE FOR ORDER BY"*) a=yes ;; *) a=no ;;
esac
check "ORDER BY with no usable index builds a temporary B-tree" "${a}"

"${sqlite_bin}" "${work}/events.db" "CREATE INDEX ix_created ON events(created_on);" >/dev/null 2>&1
order_after="$(prefix_plan "SELECT event_id, created_on FROM events ORDER BY created_on LIMIT 20;")"
case "${order_after}" in
  *"USE TEMP B-TREE"*) a=no ;; *ix_created*) a=yes ;; *) a=no ;;
esac
check "and the temporary B-tree disappears once an index supplies the order" "${a}"
"${sqlite_bin}" "${work}/events.db" "DROP INDEX ix_created;" >/dev/null 2>&1

if (cd "${work}" && "${python_bin}" - <<'PY' >/dev/null 2>&1
"""A partial index is usable only where the planner can prove it applies,
and it costs a fraction of the pages a full one would."""
import sqlite3
import sys

from timing import drop_all_indexes, file_pages, plan

FAILURES = ("SELECT count(*) FROM events"
            " WHERE status = 'failed' AND created_on >= '2025-06-01'")
DATES_ONLY = "SELECT count(*) FROM events WHERE created_on >= '2025-06-01'"

connection = sqlite3.connect("events.db")
drop_all_indexes(connection)

before, _ = file_pages(connection)
connection.execute("CREATE INDEX ix_full ON events(created_on)")
full, _ = file_pages(connection)
connection.execute("DROP INDEX ix_full")

reset, _ = file_pages(connection)
connection.execute(
    "CREATE INDEX ix_failed_created ON events(created_on) WHERE status = 'failed'")
partial, _ = file_pages(connection)

assert "SEARCH" in plan(connection, FAILURES), plan(connection, FAILURES)
assert "SEARCH" not in plan(connection, DATES_ONLY), plan(connection, DATES_ONLY)

full_pages = full - before
partial_pages = partial - reset
assert full_pages > 0 and partial_pages > 0, (full_pages, partial_pages)
assert partial_pages * 3 < full_pages, (partial_pages, full_pages)

drop_all_indexes(connection)
connection.commit()
connection.close()
sys.exit(0)
PY
); then
  check "a partial index serves the query it covers, refuses the one it does not, and costs far fewer pages" "yes"
else
  check "a partial index serves the query it covers, refuses the one it does not, and costs far fewer pages" "no"
fi

# ===========================================================================
echo
echo "7. When an index is present and the planner will not use it"
# ===========================================================================
if (cd "${work}" && "${python_bin}" - <<'PY' >/dev/null 2>&1
import sqlite3
import sys

from timing import drop_all_indexes, plan

connection = sqlite3.connect("events.db")
drop_all_indexes(connection)
connection.execute("CREATE INDEX ix_trace ON events(trace_id)")
trace = connection.execute(
    "SELECT trace_id FROM events WHERE event_id = 123456").fetchone()[0]

plain = plan(connection, "SELECT event_id FROM events WHERE trace_id = ?", (trace,))
wrapped = plan(connection,
               "SELECT event_id FROM events WHERE lower(trace_id) = ?",
               (trace.lower(),))
assert "SEARCH" in plain, plain
assert "SCAN" in wrapped, wrapped

connection.execute("CREATE INDEX ix_lower_trace ON events(lower(trace_id))")
rescued = plan(connection,
               "SELECT event_id FROM events WHERE lower(trace_id) = ?",
               (trace.lower(),))
assert "SEARCH" in rescued, rescued

drop_all_indexes(connection)
connection.commit()
connection.close()
sys.exit(0)
PY
); then
  check "a function around the column forces a scan; an expression index fixes it" "yes"
else
  check "a function around the column forces a scan; an expression index fixes it" "no"
fi

if (cd "${work}" && "${python_bin}" - <<'PY' >/dev/null 2>&1
import sqlite3
import sys

from timing import drop_all_indexes, plan

connection = sqlite3.connect("events.db")
drop_all_indexes(connection)
connection.execute("CREATE INDEX ix_trace ON events(trace_id)")
trace = connection.execute(
    "SELECT trace_id FROM events WHERE event_id = 123456").fetchone()[0]

leading = plan(connection, "SELECT event_id FROM events WHERE trace_id LIKE ?",
               (f"%{trace[-6:]}",))
assert "SCAN" in leading, leading

prefix = trace[:8]
upper = prefix[:-1] + chr(ord(prefix[-1]) + 1)
ranged = plan(connection,
              "SELECT event_id FROM events WHERE trace_id >= ? AND trace_id < ?",
              (prefix, upper))
assert "SEARCH" in ranged, ranged

# And the rewrite must not change the answer.
by_like = sorted(connection.execute(
    "SELECT event_id FROM events WHERE trace_id LIKE ?", (f"{prefix}%",)).fetchall())
by_range = sorted(connection.execute(
    "SELECT event_id FROM events WHERE trace_id >= ? AND trace_id < ?",
    (prefix, upper)).fetchall())
assert by_like == by_range, (len(by_like), len(by_range))

drop_all_indexes(connection)
connection.commit()
connection.close()
sys.exit(0)
PY
); then
  check "a leading wildcard forces a scan; the range rewrite seeks and returns the same rows" "yes"
else
  check "a leading wildcard forces a scan; the range rewrite seeks and returns the same rows" "no"
fi

if (cd "${work}" && "${python_bin}" - <<'PY' >/dev/null 2>&1
import sqlite3
import sys

from timing import drop_all_indexes, plan

connection = sqlite3.connect("events.db")
drop_all_indexes(connection)
connection.execute("CREATE INDEX ix_trace ON events(trace_id)")
connection.execute("CREATE INDEX ix_run ON events(run_id)")
trace = connection.execute(
    "SELECT trace_id FROM events WHERE event_id = 123456").fetchone()[0]

both_indexed = plan(connection,
                    "SELECT event_id FROM events WHERE run_id = ? OR trace_id = ?",
                    (200, trace))
one_missing = plan(connection,
                   "SELECT event_id FROM events WHERE run_id = ? OR score > ?",
                   (200, 0.999999))
assert "SCAN" not in both_indexed, both_indexed
assert "SCAN" in one_missing, one_missing

drop_all_indexes(connection)
connection.commit()
connection.close()
sys.exit(0)
PY
); then
  check "an OR whose branches are all indexed avoids the scan; one bare branch does not" "yes"
else
  check "an OR whose branches are all indexed avoids the scan; one bare branch does not" "no"
fi

# ===========================================================================
echo
echo "8. The other half of the trade: what indexes cost to write"
# ===========================================================================
if (cd "${work}" && "${python_bin}" - <<'PY' >/dev/null 2>&1
"""Writes must get slower and the file must get bigger. Direction and a
loose ratio, never a millisecond figure."""
import shutil
import sys
import tempfile
from pathlib import Path

from generate import rows
from write_cost import ADDED_ROWS, BASE_ROWS, INDEXES, one_trial

MINIMUM_SLOWDOWN = 1.5  # measured about 12x here

batch = list(rows(BASE_ROWS + ADDED_ROWS))
base, extra = batch[:BASE_ROWS], batch[BASE_ROWS:]

directory = Path(tempfile.mkdtemp(prefix="day089-writetest-"))
try:
    bare = min(one_trial(directory, "bare", [], base, extra)["ms"] for _ in range(2))
    indexed_trial = one_trial(directory, "indexed", INDEXES, base, extra)
    indexed = min(indexed_trial["ms"],
                  one_trial(directory, "indexed", INDEXES, base, extra)["ms"])
finally:
    shutil.rmtree(directory, ignore_errors=True)

slowdown = indexed / bare
assert slowdown >= MINIMUM_SLOWDOWN, f"only {slowdown:.2f}x slower"
sys.exit(0)
PY
); then
  check "inserting the same rows with five indexes is at least 1.5x slower" "yes"
else
  check "inserting the same rows with five indexes is at least 1.5x slower" "no"
fi

if (cd "${work}" && "${python_bin}" - <<'PY' >/dev/null 2>&1
"""And it costs disk. An index is a second copy of the data it covers."""
import sqlite3
import sys

from timing import drop_all_indexes, file_pages

connection = sqlite3.connect("events.db")
drop_all_indexes(connection)
bare_pages, _ = file_pages(connection)
connection.execute("CREATE INDEX ix_trace ON events(trace_id)")
connection.execute("CREATE INDEX ix_run ON events(run_id)")
connection.execute("CREATE INDEX ix_created ON events(created_on)")
indexed_pages, _ = file_pages(connection)
drop_all_indexes(connection)
connection.commit()
connection.close()

assert indexed_pages > bare_pages, (bare_pages, indexed_pages)
# Three indexes over a table this shape cost a real fraction of it, not a
# rounding error. 10% is a floor, not a prediction.
assert (indexed_pages - bare_pages) > bare_pages * 0.10, (bare_pages, indexed_pages)
sys.exit(0)
PY
); then
  check "three indexes add a real fraction of the table's pages to the file" "yes"
else
  check "three indexes add a real fraction of the table's pages to the file" "no"
fi

# ===========================================================================
echo
echo "9. The examples all run, and the SQL walkthrough leaves nothing behind"
# ===========================================================================
if (cd "${work}" && "${python_bin}" lookup.py events.db 2>/dev/null | grep -q "Same rows every time"); then
  check "lookup.py measures four table sizes and finishes" "yes"
else
  check "lookup.py measures four table sizes and finishes" "no"
fi

if (cd "${work}" && "${python_bin}" composite.py events.db 2>/dev/null | grep -q "COVERING INDEX"); then
  check "composite.py demonstrates the leftmost prefix and a covering index" "yes"
else
  check "composite.py demonstrates the leftmost prefix and a covering index" "no"
fi

if (cd "${work}" && "${python_bin}" blocked.py events.db 2>/dev/null | grep -q "MULTI-INDEX OR"); then
  check "blocked.py reaches the OR case and reports a multi-index plan" "yes"
else
  check "blocked.py reaches the OR case and reports a multi-index plan" "no"
fi

if (cd "${work}" && "${python_bin}" write_cost.py 2>/dev/null | grep -q "longer with five indexes"); then
  check "write_cost.py measures the insert cost both ways" "yes"
else
  check "write_cost.py measures the insert cost both ways" "no"
fi

if (cd "${work}" && "${sqlite_bin}" events.db < plans.sql >/dev/null 2>&1); then
  check "plans.sql runs in the sqlite3 shell" "yes"
else
  check "plans.sql runs in the sqlite3 shell" "no"
fi

leftover="$("${sqlite_bin}" "${work}/events.db" \
  "SELECT count(*) FROM sqlite_schema WHERE type='index' AND sql IS NOT NULL;" 2>/dev/null)"
check "and every example puts the table back the way it found it — no indexes left" \
  "$([ "${leftover}" = "0" ] && echo yes || echo no)"

# ===========================================================================
echo
echo "10. The starter is runnable, and carries its exercises"
# ===========================================================================
starter_work="${work_root}/starter"
mkdir -p "${starter_work}"
cp "${lab_dir}/starter/"* "${starter_work}/"
cp "${lab_dir}/examples/generate.py" "${starter_work}/"
(cd "${starter_work}" && "${python_bin}" generate.py mine.db 25000 >/dev/null 2>&1)

if (cd "${starter_work}" && "${sqlite_bin}" mine.db < indexes.sql >/dev/null 2>&1); then
  check "the starter SQL applies as shipped, before you have written a line" "yes"
else
  check "the starter SQL applies as shipped, before you have written a line" "no"
fi

sql_exercises="$(grep -c "^-- EXERCISE" "${lab_dir}/starter/indexes.sql" || true)"
check "the starter SQL carries its 6 numbered exercises" \
  "$([ "${sql_exercises}" = "6" ] && echo yes || echo no)"

py_exercises="$(grep -c "^# EXERCISE\|^    # EXERCISE" "${lab_dir}/starter/measure.py" || true)"
check "the starter measuring tool carries its 5 numbered exercises" \
  "$([ "${py_exercises}" = "5" ] && echo yes || echo no)"

if (cd "${starter_work}" && "${python_bin}" measure.py mine.db 2>/dev/null | grep -q "EXERCISE 1"); then
  check "running the unfinished starter names the next exercise instead of a traceback" "yes"
else
  check "running the unfinished starter names the next exercise instead of a traceback" "no"
fi

starter_exit=0
(cd "${starter_work}" && "${python_bin}" measure.py mine.db >/dev/null 2>&1) || starter_exit=$?
check "and exits non-zero, so an unfinished lab cannot look finished" \
  "$([ "${starter_exit}" -ne 0 ] && echo yes || echo no)"

# ===========================================================================
echo
echo "11. Nothing here reaches the network or needs anything installed"
# ===========================================================================
if "${python_bin}" - "${lab_dir}" <<'PY' >/dev/null 2>&1
import re
import sys
from pathlib import Path

root = Path(sys.argv[1])
banned = re.compile(r"https?://(?!\S*\.invalid)", re.IGNORECASE)
offenders = []
for directory in ("examples", "starter", "tests"):
    for path in (root / directory).rglob("*"):
        if path.is_file() and path.suffix in {".py", ".sql", ".sh"}:
            if banned.search(path.read_text(encoding="utf-8", errors="ignore")):
                offenders.append(path.name)
for name in offenders:
    print(name, file=sys.stderr)
sys.exit(1 if offenders else 0)
PY
then
  check "no executable lab file contains a network address of any kind" "yes"
else
  check "no executable lab file contains a network address of any kind" "no"
fi

if "${python_bin}" - "${lab_dir}" <<'PY' >/dev/null 2>&1
import re
import sys
from pathlib import Path

root = Path(sys.argv[1])
third_party = re.compile(
    r"^\s*(import|from)\s+(requests|httpx|urllib3|pandas|numpy|sqlalchemy)\b", re.M)
offenders = []
for directory in ("examples", "starter", "tests"):
    for path in (root / directory).rglob("*.py"):
        if third_party.search(path.read_text(encoding="utf-8", errors="ignore")):
            offenders.append(path.name)
for name in offenders:
    print(name, file=sys.stderr)
sys.exit(1 if offenders else 0)
PY
then
  check "no lab file imports a third-party package — standard library only" "yes"
else
  check "no lab file imports a third-party package — standard library only" "no"
fi

check "every database this run created lives under a temporary directory" \
  "$([ ! -e "${lab_dir}/events.db" ] && [ ! -e "${lab_dir}/starter/mine.db" ] \
     && [ ! -e "${lab_dir}/tests/events.db" ] && echo yes || echo no)"

echo
echo "${checks} checks, ${failures} failure(s)."
[ "${failures}" -eq 0 ]