Join Ordering, Part 1: The Shape of the Search Space
Summary
The article provides a deep dive into join ordering for SQL query optimization, focusing on dynamic programming approaches and the concept of csg-cmp-pairs as a fundamental unit of work. It explains how query graphs, bitsets, and cost models are used to enumerate efficient plans and discusses the trade-offs between left-deep and bushy trees, with Rust code snippets illustrating the data structures. It also references classic papers and newer work, framing the problem and opening the door to Part 2.