One-sentence Summary

Researchers from TUM and CWI introduce the Join Order Benchmark (JOB) to experimentally revisit the main components of classic query optimizer architectures on realistic multi-join queries, finding that cardinality estimators routinely produce large errors, cost models exert much less influence on performance than cardinality estimates, and exhaustive plan enumeration still improves performance despite sub-optimal estimates.

Key Contributions

• The paper introduces the Join Order Benchmark (JOB), built on the highly correlated IMDB real-world data set and realistic multi-join queries, and provides a methodology for measuring cardinality estimation accuracy to evaluate query optimizer quality.

• Experiments revisiting the classic query optimizer architecture show that industrial-strength cardinality estimators routinely produce large errors that grow as the number of joins increases, while the cost model has much less influence on performance in the tested main-memory setting.

• A comparison of plan enumeration techniques finds that exhaustive dynamic programming produces better plans than heuristic algorithms and improves query performance even when cardinality estimates are sub-optimal.

Introduction

In database systems, choosing an efficient join order is central to query optimization because poor plans can make analytical queries orders of magnitude slower. Traditional cost-based optimizers rely on cardinality estimates and simplifying assumptions such as uniformity and independence, which often break on real, highly correlated data, especially in multi-join queries and richly indexed main-memory databases. Prior work has often studied cardinality estimation or plan enumeration in isolation, or used synthetic queries and simplified settings, leaving uncertainty about how each optimizer component affects end-to-end performance. The authors leverage the IMDB dataset to build the public Join Order Benchmark and run a novel end-to-end evaluation of major PostgreSQL-style optimizer components. Their main contribution is a realistic framework for measuring how cardinality estimation, cost models, and plan enumeration interact, showing that cardinality errors are the dominant problem, simple cost models can be enough in main memory, and exhaustive enumeration can avoid many disastrous plans.

Dataset

• The authors build the dataset from the Internet Movie Database (IMDB), a real-world relational data set released as text files for noncommercial use.

• They convert the IMDB text files into a relational database with 21 tables using the open-source imdbpy package.

• The IMDB snapshot is from May 2013 and occupies 3.6 GB when exported to CSV files.

• The two largest tables are cast_info, with 36 million rows, and movie_info, with 15 million rows.

• The authors use IMDB because it contains realistic correlations and non-uniform distributions, unlike synthetic benchmarks such as TPC-H, TPC-DS, and SSB.

• On top of the IMDB database, they construct the Join Order Benchmark (JOB) query workload.

• The JOB query set contains 33 query structures, each with 2 to 6 variants that differ only in their selection predicates, for a total of 113 queries.

• The queries are analytical select-project-join queries with between 3 and 16 joins, averaging 8 joins per query.

• The query join graphs include both key-to-foreign-key edges and foreign-key-to-foreign-key edges caused by transitive join predicates.

• Some query variants include more complex selection predicates such as disjunctions and LIKE substring search.

• The authors intentionally avoid overly adversarial predicates, such as extreme correlations, inequality join predicates, and non-surrogate-key predicates.

• They use the data to evaluate cardinality estimation and join ordering, rather than to train a model.

• For cardinality extraction, they load IMDB into multiple relational database systems and run each system’s default statistics gathering procedure.

• They then extract cardinality estimates for all intermediate results of the JOB queries using each system’s native plan or estimation commands.

• They also compute true cardinalities for each intermediate result by executing SELECT COUNT queries.

• When indexes on foreign keys can affect intermediate result sizes, they additionally collect cardinality estimates for results before and after selection predicates are applied.

Method

The authors construct a controlled query optimizer analysis framework that treats cardinality estimation, cost modeling, and plan enumeration as separate but interacting modules. PostgreSQL is used as the representative baseline optimizer because it implements a conventional optimizer architecture: join order enumeration through dynamic programming, a cost model over physical plans, and a statistics based cardinality estimator. The optimizer enumerates join orders, including bushy trees but excluding trees that contain cross products, and then compares alternative physical plans by estimating their cost. At execution time, the engine uses Volcano style interpretation over a selected physical operator plan, with access paths such as full table scans and unclustered B+Tree index lookups, and join implementations including nested loops, index nested loops, in memory hash joins, and sort merge joins. The choice of physical join algorithm is fixed by the optimizer rather than being decided dynamically during execution.

The cardinality estimator forms a central module in this framework. PostgreSQL estimates base table cardinalities from sampled per attribute statistics, including quantile histograms, most common values and their frequencies, and domain cardinalities, which represent the number of distinct values. For predicates that cannot be handled by histograms, the system falls back to ad hoc assumptions that are not formally grounded. When several predicates on the same table must be combined, PostgreSQL assumes independence and multiplies the individual selectivity estimates. Join cardinalities are estimated using the standard size based formula

where $T_1$T1​ and $T_2$T2​ are arbitrary expressions and $\operatorname{dom}(x)$dom(x) is the domain cardinality of attribute $x$x. This formula embeds the assumptions used by the baseline estimator, namely uniformity over non frequent values, independence across predicates and join attributes, and the principle of inclusion, where the smaller join domain is assumed to be covered by the larger one.

The framework also includes a dedicated extraction and injection workflow for cardinality estimates. The authors first load a dataset into multiple database systems and run each system’s statistics gathering command with default settings. They then issue the queries used in the experiments and retrieve optimizer estimates for every intermediate result produced by the original query. For a chain query of the form

the intermediate results include the selection result, the first join result, the second join result, and the final join result. The workflow further recognizes that physical access methods introduce additional intermediate results that are not always visible in the logical plan. When an index nested loop join uses a non unique index on a foreign key, the system may first produce the result of the index lookup before applying a selection from the opposite side. Therefore, cardinalities must be captured for both the pre selection and post selection intermediate results. To establish a ground truth for evaluation, the framework also executes count based queries to obtain the true cardinality of each intermediate result.

To evaluate the effect of different cardinality estimates inside a single execution engine, the authors modify PostgreSQL so that the optimizer can accept injected cardinalities for arbitrary join expressions. This module allows PostgreSQL to use estimates produced by other database systems, or the true cardinalities measured directly from the data, instead of generating its own estimates. This design is more general than merely specifying predicate selectivities because cardinality injection can represent correlations across relations and arbitrary expression trees, rather than only the selectivity of individual predicates.

The cost model module is handled separately from the enumeration module. PostgreSQL’s default disk oriented model computes operator costs as a weighted combination of sequential disk pages, random disk pages, and in memory data processing, and the total cost of a plan is the sum of operator costs. Because the default cost variables are difficult to calibrate accurately, the framework also introduces a simplified in memory cost model used for controlled evaluation. This model does not model disk I/O explicitly. Instead, it counts the number of tuples processed by operators and assigns relative weights to table scans, hash joins, and index nested loop joins:

Here, $R$R is a base relation, $\tau$τ discounts the cost of scanning a base table relative to joins, and $\lambda$λ approximates the relative expense of an index lookup compared with a hash table lookup. The implementation uses $\lambda = 2$λ=2 and $\tau = 0.2$τ=0.2, and it disables nested loop joins when the inner relation is not accessed through an index lookup.

For plan space exploration, the authors use a standalone query optimizer that can receive injected cardinality estimates from any source and can enumerate plans using dynamic programming and heuristic algorithms. Rather than executing the large number of generated plans directly, the framework evaluates each plan by recomputing its cost with the true cardinalities using the simplified in memory cost model. This creates a surrogate execution cost that approximates runtime without requiring the system to run every candidate plan. The design therefore separates the impact of the enumeration algorithm, the accuracy of cardinality estimation, and the influence of the cost model, allowing the framework to isolate how each optimizer component contributes to final query performance.

Experiment

The experiments evaluate cardinality estimation, plan performance, cost models, and join order enumeration using a main-memory PostgreSQL setup and a realistic IMDB workload, with additional comparisons against TPC-H. Base table estimates are generally good for sampling-based systems, but join estimates degrade sharply and often underestimate true cardinalities, especially in correlated queries and complex physical designs. The work shows that cardinality accuracy dominates cost model sophistication and that risky join choices can cause severe slowdowns, whereas robust plan selection and runtime parameter adjustment can mitigate poor estimates. Exhaustive enumeration provides useful benefits, but improving cardinality estimation remains the most important path to better query optimization.

Most systems estimate the majority of base table selections well, with q-errors close to the optimal value in the median. Tail errors differ strongly across systems, with sampling-based systems generally performing better on complex predicates than histogram-based systems. Large errors often arise from very low selectivity cases or from estimates that cannot capture attribute correlations. Medians are near one, so typical selections are estimated correctly. DBMS A and HyPer are strongest for complex predicates, likely because they use table sampling. Histogram-based systems show much worse tail errors, especially for correlated or complex predicates.

Restricting join order search to specific tree shapes can increase query cost relative to the optimal plan that allows bushy trees. Zig-zag trees usually remain close to optimal and show only moderate worst-case slowdown, while left-deep trees are somewhat worse but still reasonable. Right-deep trees perform far worse, especially when more indexes are available, because they create large intermediate hash tables and limit index lookup opportunities. Zig-zag trees preserve most of the optimal plan quality and degrade only modestly in difficult cases. Left-deep trees lose some performance compared with zig-zag trees but still give acceptable plans. Right-deep trees can cause severe slowdowns and are not suitable as a general-only search space.

Exhaustive dynamic programming produces plans closest to the normalized optimal cost across index configurations, while Quickpick-1000 and Greedy Operator Ordering give slightly higher costs. The heuristics are more competitive when few indexes are available, and less reliable in richer index settings, especially when plans are chosen from estimated cardinalities. The results suggest that estimation quality can dominate the practical difference between exhaustive search and restricted heuristics. Dynamic programming remains the most reliable algorithm under both primary key only and richer index settings. Quickpick-1000 and Greedy Operator Ordering show larger cost loss in index-rich settings and under poorer cardinality estimates.

The experiments evaluate cardinality estimation, join-order search space restrictions, and join-order algorithm quality across different index settings. Typical base table selections are estimated accurately, but tail errors vary widely, with sampling-based approaches generally handling complex or correlated predicates better than histogram-based methods. Join-order experiments show that zig-zag and left-deep trees remain reasonably close to optimal, while right-deep trees can cause severe cost increases. Exhaustive dynamic programming produces the most reliable plans, whereas heuristic search methods degrade more noticeably when many indexes are available or cardinality estimates are poor.