Abstract

Rule-based query optimizers dominated the open-source analytics stack for most of the past decade. Hive and early Spark shipped with optimizers that applied a fixed sequence of rewrites - predicate pushdown, projection pruning, filter reordering - without reference to data statistics. The shift to cost-based optimization (CBO) that major engines have completed or are completing changes the planning model fundamentally: join order, join strategy, and partitioning decisions are now informed by cardinality estimates and cost models rather than position in the query tree. This post examines how DuckDB, Apache Datafusion, and Velox approach CBO in early 2026, and what the differences mean for workloads that straddle the interactive and batch boundary.

Cardinality Estimation and Statistics Collection

CBO is only as good as its statistics. DuckDB maintains column statistics automatically during ingestion - distinct count (HyperLogLog), min/max, and histogram sketches are computed on every write without a separate ANALYZE step. Datafusion, used as the execution layer in tools like Ballista and various cloud query services, exposes a statistics trait that data sources implement; file-format-level statistics from Parquet row-group metadata feed directly into the optimizer without scanning rows. Velox, Facebook’s vectorized execution engine, relies on statistics provided by the calling system (Presto, Spark) rather than maintaining its own, which puts the burden on the integration layer.

Join Order and Strategy Selection

For queries with more than three tables, the number of possible join orderings grows factorially. Practical CBO implementations use dynamic programming with memoization to prune the search space, treating the join graph as a hypergraph where each table is a node and predicates are edges. DuckDB’s join order optimizer uses a hybrid approach: dynamic programming for up to eight relations, greedy heuristics beyond that. The join strategy choice - hash join, nested loop, merge join - is cost-modeled against the estimated cardinalities: a hash join on a small probe side with a large build table is expensive; a nested loop join can outperform it when one side is very small. DuckDB introduced adaptive join strategy selection in 0.10 that switches from hash to nested loop at runtime when one side resolves to fewer rows than estimated.

Partition Pruning and File Skipping

Columnar formats expose file-level and row-group-level statistics that the optimizer can use to skip entire files or row groups before a single byte of data is read. Iceberg’s partition spec and column statistics, combined with a CBO-aware planner, allow the optimizer to compute a lower bound on the number of rows a scan will return, which propagates into join cost estimates upstream. In practice, this means that a filter on a date-partitioned Iceberg table not only skips non-matching partition directories but also feeds a tighter cardinality estimate into any subsequent join. Datafusion’s TableProvider trait carries this information natively; Spark’s Statistics API provides the same surface area but is more commonly populated by manual ANALYZE TABLE runs.

Limitations and Calibration

CBO does not eliminate bad plans - it shifts the failure mode from structural plan errors to miscalibrated cost models. Cardinality estimates based on independent column assumption fail on correlated predicates, a known weakness that column-group statistics partially address. Adaptive query execution (AQE) in Spark and the runtime re-optimization in Velox provide a backstop: if cardinality estimates turn out to be wrong during execution, the plan can be revised mid-flight. The combination of static CBO for initial planning and adaptive execution for mid-flight correction is the design direction most major engines are converging on.