Indexes: SCAN Becomes SEARCH

An index is a separate, sorted data structure the engine keeps alongside a table, mapping a column's values to the rows that have them — conceptually the same as a book's index letting you jump straight to a page instead of reading the whole book to find a topic. Without one, an unindexed filter forces the engine to read every single row (a SCAN) just to check whether it matches; an index on the filtered/joined column lets the engine jump straight to matching rows instead (a SEARCH). EXPLAIN QUERY PLAN (SQLite's syntax; every platform has an equivalent) shows you which one is actually happening, rather than requiring you to guess. Three common anti-patterns quietly defeat an index even when one exists: SELECT * (the engine often still has to read the full row even after finding it via the index), a function wrapped around the indexed column in WHERE like WHERE UPPER(city) = 'TORONTO' (the index is built on the raw column, not the function's output), and implicit type conversion (comparing a text column to a numeric literal forces a conversion on every row, which usually blocks index use too).

SQL · EXPLAIN QUERY PLAN, before an index (measured output, this exact seed data)

EXPLAIN QUERY PLAN
SELECT c.name, SUM(oi.quantity * oi.unit_price) AS spend
FROM customers c
JOIN orders o       ON o.customer_id = c.id
JOIN order_items oi ON oi.order_id   = o.id
WHERE c.city = 'Toronto'
GROUP BY c.name;

--  id  parent  detail
--   8       0  SCAN oi                                          -- reads ALL 80 order_items rows
--  10       0  SEARCH o USING INTEGER PRIMARY KEY (rowid=?)
--  13       0  SEARCH c USING INTEGER PRIMARY KEY (rowid=?)
--  18       0  USE TEMP B-TREE FOR GROUP BY
--
-- The cost is on line 1: with no index to start from customers, the engine has no
-- cheaper entry point than order_items, so it SCANs all 80 rows and only checks the
-- city filter afterward, per row -- the city filter isn't reducing any work yet.

SQL · the fix

CREATE INDEX idx_customers_city       ON customers(city);
CREATE INDEX idx_orders_customer_id   ON orders(customer_id);
CREATE INDEX idx_order_items_order_id ON order_items(order_id);

SQL · EXPLAIN QUERY PLAN, after (measured output, same query, same data)

--  id  parent  detail
--  10       0  SEARCH c  USING INDEX idx_customers_city (city=?)
--  15       0  SEARCH o  USING COVERING INDEX idx_orders_customer_id (customer_id=?)
--  19       0  SEARCH oi USING INDEX idx_order_items_order_id (order_id=?)
--  24       0  USE TEMP B-TREE FOR GROUP BY
--
-- Every SCAN became a SEARCH. The engine now starts from the city index, so it only
-- ever touches rows that can possibly qualify.

Cost, before vs. after (measured against this exact 25-customer / 40-order / 80-order_item dataset)

Before: 1 full scan  = all 80 order_items rows touched, regardless of the Toronto filter
After:  7 customers -> 13 orders -> 26 order_items rows touched via the three indexes

-- ~3x fewer rows touched on a toy dataset this small -- the same SCAN-to-SEARCH change
-- on a production table with millions of rows is the difference between a query that
-- times out and one that returns instantly, because the gap scales with table size,
-- not with the shape of the query.

Partition Pruning, for Real

Partitioning physically splits a table's data into separate files or segments based on a column's value — almost always a date, since "which rows are from March" is the single most common filter in analytics. Partition pruning is what an engine does when a query filters on that same column: it skips reading the partitions that can't possibly match, instead of scanning the whole table and then discarding rows that don't qualify. Clustering is the complementary, finer-grained idea — sorting the rows within each partition by a second, frequently-filtered column, so even a scan within one partition can skip ahead efficiently. The companion repo's Part 9 notebook writes a real Hive-style partitioned Parquet dataset with DuckDB, then shows an actual EXPLAIN plan scanning 1 of 3 partition files after filtering on the partition column — not a claim, a measured result. See Partitioning & Clustering for the platform-architecture version of the same idea (BigQuery partition+cluster, Snowflake micro-partitions, Delta Z-order).

SQL / Python · DuckDB partition pruning (measured, not claimed)

# Write a dataset partitioned by year, Hive-style -- mirrors a production lake table
duckdb.sql("""
    COPY (SELECT *, EXTRACT(year FROM order_date) AS order_year FROM orders_big)
    TO '/tmp/orders_partitioned' (FORMAT PARQUET, PARTITION_BY (order_year))
""")

-- No filter on the partition column: EXPLAIN shows ~91,617 rows read (all 3 years)
EXPLAIN SELECT COUNT(*) FROM read_parquet('/tmp/orders_partitioned/*/*.parquet', hive_partitioning=true);

-- Filtered on the partition column: EXPLAIN shows "Scanning Files: 1/3"
EXPLAIN SELECT COUNT(*) FROM read_parquet('/tmp/orders_partitioned/*/*.parquet', hive_partitioning=true)
WHERE order_year = 2023;

Views vs. Materialized Views

A plain view (Part 1) always re-runs its underlying query in full, every time it's selected from — always fresh, since it reflects the current data instantly, but never cached, so the cost of the query is paid again on every single read. A materialized view computes the query once and stores the result physically, like a real table, trading that freshness for speed: reading it is now just reading a stored result, no re-computation, but the data is only as current as the last refresh. It needs an explicit or scheduled refresh to catch up with changes in the underlying tables. Decide your staleness tolerance up front — how out-of-date is acceptable, and on what schedule it gets refreshed — not after someone in a meeting notices a number that doesn't match what they expected.

SQL · simulating a materialized view

-- "Materializing" a view: compute once, store as a real table
CREATE TABLE mv_customer_spend AS
SELECT c.id, c.name, SUM(oi.quantity * oi.unit_price) AS lifetime_spend
FROM customers c
JOIN orders o ON o.customer_id = c.id
JOIN order_items oi ON oi.order_id = o.id
GROUP BY c.id, c.name;

-- To "refresh": DROP TABLE mv_customer_spend, then re-run the CREATE TABLE AS above.
-- Snowflake/BigQuery/Databricks/Fabric all offer real materialized views with
-- automatic, incremental refresh -- see Part 12.

JOIN Order & CTE Materialization

Modern query optimizers reorder JOINs for you based on table statistics — in most engines, listing the smallest table first in a JOIN chain doesn't matter the way it did on older, simpler optimizers; the engine works out a good order on its own. What you do still control, and what varies by engine, is whether a CTE (Part 4) is inlined (recomputed every place it's referenced, exactly like a view) or materialized (computed once, stored temporarily, then reused). Modern SQLite (3.35+) decides per-query based on cost, the same way PostgreSQL has since version 12 (older PostgreSQL materialized every CTE unconditionally, unless a subquery was clearly cheaper); Snowflake/BigQuery/Databricks make the same kind of cost-based call automatically. The practical rule holds regardless of engine: if a CTE is expensive and referenced more than once, don't assume it's computed once — check the actual plan, or materialize it into a temp table explicitly if you need that guarantee.

SQL · checking whether a CTE ran once or twice

-- A CTE referenced twice -- check the plan to see if it's computed once or twice
EXPLAIN QUERY PLAN
WITH category_totals AS (
    SELECT p.category, SUM(oi.quantity * oi.unit_price) AS revenue
    FROM order_items oi JOIN products p ON p.id = oi.product_id
    GROUP BY p.category
)
SELECT a.category, a.revenue
FROM category_totals a
JOIN category_totals b ON a.category = b.category
WHERE a.revenue > 500;
-- Measured result: "MATERIALIZE category_totals" appears ONCE, with its own SCAN/GROUP BY
-- subtree computed once; the two outer references (SCAN a, SEARCH b) both reuse that single
-- result -- SQLite chose to materialize here, not inline. Don't assume either way: check.

A Cost Note

Every technique on this page — indexing, partition pruning, materialized views, avoiding a redundant CTE recomputation — ultimately reduces bytes scanned, and on a cloud warehouse, bytes scanned is very often the literal unit you're billed on. BigQuery charges per byte scanned by the query, full stop, so a partition-pruned query that reads 1 file instead of 3 costs roughly a third as much, not just runs roughly three times faster. Snowflake and Databricks bill per-second of compute instead, but scanning less data still means the query finishes sooner, so the same optimizations still shrink the bill, just indirectly through time rather than bytes. The habit this should build: before running an expensive-looking query against a cloud warehouse for the first time, check what it will cost, not just whether it will return the right answer.

CLI · checking cost before you run (reference)

-- BigQuery: estimate bytes scanned WITHOUT running/billing for the query
bq query --dry_run --use_legacy_sql=false 'SELECT * FROM orders WHERE order_year = 2023'

-- Snowflake: shows the partitions/micro-partitions a query would scan, before running it
EXPLAIN USING TEXT SELECT * FROM orders WHERE order_year = 2023;