Real World: Database Query Optimization

Math for CS · Axiom Academy

REAL WORLD Database Query Optimization Set theory, relational algebra, and the difference between a 30-millisecond query and a 30-second one. 1. SQL Is Set Theory in Disguise A relational table is a set of tuples (rows), and SQL operations correspond directly to set-theoretic and relational-algebra operations: That last row is the biggest mathematical idea in databases. An inner join is defined as a Cartesian product followed by a selection. If A has |A| rows and B has |B| rows, the Cartesian product has rows. For two million-row tables, that's a trillion intermediate rows. No database is going to materialize that. The whole job of the query optimizer is to avoid doing the join naively. 2. The Cost of an Unoptimized Join Imagine an e-commerce site with two tables: The join itself produces only 5 million rows (each order has exactly one customer). But the naive nested-loop algorithm a database might use to compute it is: That's comparisons. At a billion comparisons per second, this is roughly 20 minutes . The same query, with a single index on customers.id , takes about 30 seconds. With both tables sorted on the join key (a "merge join"), it takes 5 seconds. Same answer, three different complexities. An index is a separate sorted data structure that maps a column value to the disk location of the row. The classic implementation is a B-tree : a balanced tree where every internal node has many children (typically 100–1000) and every leaf is at the same depth.

This is the written version of the interactive lesson above. See the full Math for CS course.