When you run a SELECT on a table with millions of rows, something quite sophisticated happens underneath: the database does not “search” row by row, but orchestrates indexes, tree structures and a query planner to answer in milliseconds. Let’s look at what happens inside a relational engine (PostgreSQL, MySQL or SQLite) between the moment you write the query and the moment you get the result.
The query planner: your SQL is not executed as written
The first step is for the engine to translate your SELECT into an execution plan. A component called the planner breaks the query down, rewrites it algebraically, and evaluates different strategies for retrieving the data: reading the whole table (a full table scan) or jumping straight to the relevant rows using an index. Each strategy has an estimated cost in disk accesses, and the engine picks the cheapest one. That plan is what you see with EXPLAIN in PostgreSQL or EXPLAIN QUERY PLAN in SQLite.
Indexes and the B-tree: the key to speed
Without an index, finding a row by its primary key means scanning the whole table, a linear O(n) cost. Indexes exist to avoid that. The most common one is the B-tree, a balanced data structure where each node can have many children (unlike a binary tree).
A B-tree stores keys in sorted order and points to the records. Because it is balanced, its height grows very slowly: a tree of height 4 can index millions of rows. To search, the engine starts at the root, compares the key and descends along the right branch, at O(log n) cost. Each node fits in a disk “page”, so very few physical reads reach the data. Indexes also enable ordered scans, useful for ranges (WHERE price BETWEEN 10 AND 20) and for ORDER BY without re-sorting anything.
Composite indexes and the cost of indexing
An index can cover several columns, forming a composite index. Order matters: an index on (a, b) serves queries by a or by a and b, but not queries that filter only on b. Also, indexes are not free: every INSERT, UPDATE or DELETE must update the tree, and they take up disk space. That is why a good schema design balances read speed against write cost.
Transactions and the WAL log
Databases guarantee ACID (Atomicity, Consistency, Isolation, Durability). Durability is achieved with the WAL (Write-Ahead Log): before modifying the actual data, the engine writes the change to a sequential log and only then applies it to the data files. If the system crashes mid-way, on restart it replays the log and recovers a consistent state.
Isolation between concurrent transactions is handled by mechanisms such as MVCC (Multi-Version Concurrency Control): each transaction sees a consistent “snapshot” of the data, so readers and writers do not block each other. That is why PostgreSQL can read and write at the same time without waiting.
Why sometimes “it’s faster to call the API again”
Knowing this changes how you write queries. A WHERE on an indexed column, a JOIN that leverages indexed foreign keys, or a SELECT that only requests the columns it needs (covering indexes) make the difference between milliseconds and seconds. And once a table grows past a certain size, the planner decides on its own to use an index. The engine is not magic: it is very finely tuned data-structure engineering.
