Big-O in Practice: Why Your Database Query Planner Thinks Differently Than You

The gap between asymptotic analysis and real execution Big-O tells you how a cost grows as input grows, in the limit, with constants thrown away. That’s the right tool for comparing two sorting algorithms in a CS class. It’s the wrong tool, on its own, for predicting how a database executes a query. A query…