Table Scan — The Baseline Query Strategy

A full table scan (or sequential scan) reads every single row in a table and evaluates the WHERE clause against each one. It's the simplest query execution strategy and the baseline we'll improve upon with indexes.

How a Table Scan Works

For each row in the table:
    If WHERE clause evaluates to true for this row:
        Include this row in the result set

This is O(n) where n is the number of rows. For a table with 1 million rows and a WHERE clause matching 10 rows, you still read all 1 million.

The .explain Command

Real databases show you their query plan. SQLite uses EXPLAIN QUERY PLAN:

EXPLAIN QUERY PLAN SELECT * FROM users WHERE age > 25;
-- SCAN TABLE users

The word SCAN means full table scan — every row is examined. Later, when we add indexes, you'll see SEARCH instead, which means the engine can skip directly to matching rows.

When Table Scans Are Fine

Table scans aren't always bad:

• Small tables (< 1000 rows): scan is fast enough
• No selective filter: SELECT * FROM users must read everything anyway
• High selectivity: if WHERE matches > 30% of rows, scan may beat an index

When Table Scans Are Terrible

• Large tables with selective filters: SELECT * FROM million_row_table WHERE id = 42 — scanning 1M rows to find 1 is wasteful
• Joins: nested-loop joins with table scans are O(n * m)

Row Counting

A useful diagnostic command is row counting:

.count users → 1000

This itself requires a table scan (unless you maintain a cached count). PostgreSQL maintains an approximate row count in pg_class.reltuples, but for an exact count, even PostgreSQL scans the table.

Cost Estimation

Query planners assign a cost to each strategy. For table scan:

cost = number_of_pages * page_read_cost + number_of_rows * cpu_tuple_cost

SQLite uses a simpler model based on estimated row counts and whether an index is available. We'll build cost-based planning in Chapter 7.

The Volcano Model

Most databases use the Volcano (or iterator) model for query execution. Each operator (scan, filter, project) is a node that produces one row at a time via a next() method:

Project(name, age)
  └── Filter(age > 25)
        └── TableScan(users)

Calling next() on Project calls Filter's next(), which calls TableScan's next(), forming a pull-based pipeline.

Your Task

Implement .explain to show the query plan (always "SCAN TABLE" for now) and .count to show row counts.