Database Query Performance Calculator

Query cost in a relational engine is dominated by how many storage pages must be touched, which is why this model works in pages rather than rows. PostgreSQL uses an 8 KB page by default and InnoDB uses 16 KB, so a 200-byte row packs about 40 rows per 8 KB page and a million-row table occupies roughly 25,000 pages. A sequential scan must read all of them; a B-tree lookup reads only the height of the tree. With a branching factor near 200 keys per node, tree height grows as the logarithm of row count, so a million rows gives a depth of three and a billion rows a depth of four or five. That logarithmic growth is the entire reason indexed lookups on huge tables still return in milliseconds while a full scan of the same table takes minutes. The remaining terms are calibration factors. A random page read costs roughly 0.1 ms on SATA SSD, under 0.1 ms on NVMe, and 5 to 10 ms on spinning disk, where seek time dominates. The buffer pool absorbs most of that cost, and well-tuned production systems hold cache hit rates above 95 percent; sustained readings below 90 percent usually mean insufficient memory or queries touching too much data. The join multiplier of 1.5 raised to the number of joins is a crude stand-in for real join algorithms, which behave very differently: a nested loop join over an unindexed inner table is quadratic, while hash and merge joins are closer to linear. Treat the output as an order-of-magnitude sanity check and use EXPLAIN ANALYZE for anything that matters, since the model ignores the optimizer, sorting, aggregation, data skew and concurrent load.

The index structure at the center of this calculation was invented by Rudolf Bayer and Edward McCreight at Boeing Research Laboratories, published in 1972 as Organization and Maintenance of Large Ordered Indices. Their balanced multi-way tree guaranteed logarithmic access while keeping node sizes matched to disk blocks, and the B-plus-tree variant that stores all records in the leaves became the default index in essentially every relational database that followed. The relational model those systems implement came from Edgar F. Codd at IBM in 1970. Cost-based query planning, the reason a database chooses between a scan and an index at all, was introduced by the System R project at IBM San Jose. Patricia Selinger and colleagues published Access Path Selection in a Relational Database Management System in 1979, describing statistics-driven cost estimation and join ordering by dynamic programming; the paper still describes how modern optimizers work in outline. Berkeley's Ingres, led by Michael Stonebraker in the same decade, produced the other main lineage, running through Postgres from 1986 into PostgreSQL. MySQL appeared in 1995, and the InnoDB storage engine, released in 2001 and acquired by Oracle in 2005, brought B-tree clustered indexes and a configurable buffer pool to the most widely deployed open-source database. The EXPLAIN command that operators still rely on dates from these early systems and remains the primary tool for checking whether the plan matches expectation.