Pith. sign in

REVIEW 4 major objections 5 minor 24 references

The Case for Deep Query Optimisation

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper argues that query optimisers should open up physical operators and optimise the finer-grained subcomponents inside them, because those choices can cut estimated query costs by up to fourfold.

desk verdict A clear position paper with real microbenchmarks, but the DP experiment that headlines DQO does not test subcomponent enumeration; send it out with a referee who will push on Section 5.3. read the letter →

arxiv 1908.08341 v2 pith:PQVCE63E submitted 2019-08-22 cs.DB

Jens Dittrich , Joris Nix This is my paper · ORCID
classification cs.DB
keywords deepqueryoptimisationphysicaloperatorsstaticperfecthashingmaterialisedalgorithmicviewsviewselectionproblemmeta-relationalpropertiesdynamicprogramminggroupingalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that database query optimisers stop too early. Today, a logical join or grouping operator is translated in one step into a black-box "physical operator" such as hash-based grouping, and the optimiser then chooses among such coarse boxes. DQO breaks open those boxes and treats their internals—partitioning, index choice, hash table type, loading and probing loops—as finer-grained query plans that can be enumerated, costed, and materialised. With a concrete grouping benchmark and a dynamic-programming experiment, it shows that adding data density as an optimiser property can select static-perfect-hash implementations that are estimated to be up to four times cheaper than the best shallow plan. A sympathetic reader would take away that the largest remaining optimisation headroom in databases may sit inside operators, not only between them.

What carries the argument

The central object is the unnesting hierarchy of a logical operator into finer physiological subplans, and the key property is the meta-relational plan property (e.g., density and sortedness) used to choose among sub-implementations. Concretely, grouping is recast as: partition the producer's relation by the grouping key into a bundle of independent producers, then aggregate each partition, with each arrow a producer-consumer edge. Static perfect hashing (SPH), used when the key domain is dense, is an array indexed by the grouping key so no hash computation or collision handling is needed; the paper's dynamic-programming experiment extends the cost model with this choice and tracks density as an optimiser property. This machinery carries the argument by making the inside of an operator a first-class planning object.

What would settle it

Run the same join-then-group query end-to-end on dense unsorted data and compare actual wall-clock time of the SPH-based plan (SPHJ plus SPHG) against the classic hash-based plan (HJ plus HG); if the SPH plan is not faster, the paper's headline fourfold advantage does not transfer from estimated costs to execution time.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that a "physical operator" is not the bottom of the optimisation stack; it is a nested query plan in disguise. Hash-based grouping, for example, can be decomposed into partitionBy followed by aggregating independent producers; choosing to implement partitionBy with a hash table, a static perfect hash array, a sort, or a binary-search array locks in very different runtime behaviour depending on whether the input is sorted, dense, or sparse. The paper shows empirically on 100-million-tuple synthetic datasets that no single grouping algorithm wins: static perfect hash-based grouping (SPHG) and order-based grouping are about four times faster than hash-based grouping on sorted-and-dense and unsorted-and-dense data, while hash-based grouping wins on unsorted-and-sparse data. It then demonstrates a DQO-enabled dynamic programming optimiser for a join-group query where the density property selects SPH-based join and grouping plans, giving estimated cost improvements of up to four times over a shallow optimiser that ignores density. The conclusion it draws is that finer-granular optimisation choices, made from data properties, can lead to better query plans.

Load-bearing premise

The headline up-to-fourfold advantage comes from hand-assumed linear cost models (Table 4) and from knowing the key domain is dense, not from measured end-to-end query runtimes; if real static-perfect-hash joins and grouping are not actually several times cheaper than hash-based alternatives, the DQO advantage shrinks or disappears.

Editorial extensions

If this is right

  • If DQO is right, query optimisers should treat operator internals as enumerated plan space: index structures, hash functions and bulk-loading loops become costable choices, not fixed developer code.
  • Data properties beyond sortedness—density first among them—deserve first-class status as plan properties, and optimisers that ignore them leave known speedups on the table, with the paper's estimated factor reaching fourfold.
  • Materialised Algorithmic Views can move some of the new enumeration work offline, reusing preoptimised sub-operator plans at query time just as materialised views reuse query results.
  • The AVSP framing turns the question "which algorithms should be materialised, when, and at which granularity?" into a physical-design problem with workload-dependent tradeoffs.
  • The "physical operator" boundary should be treated as a continuum: naming a plan "physical" is provisional, since compilation and hardware decisions happen underneath.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, dictionary-compressed columns look like the natural first deployment target: their dense key domains make static-perfect-hash grouping nearly free, so a columnar engine could test the DQO mechanism without building a full deep optimiser.
  • The paper's property list includes correlation, cardinality, and null density but does not test them; a natural next experiment is to see whether each new property flips the winning sub-operator on real skewed workloads.
  • If the estimated fourfold cost advantage survives end-to-end measurement, DQO blurs the boundary between query optimisation and code generation: a partial MAV is close to a pre-optimised routine that a compiler could inline.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper makes a case for Deep Query Optimisation (DQO), a proposal to enlarge the query-optimisation search space by breaking the abstraction of physical operators into finer-grained subcomponents and enumerating (sub-)plans over these subcomponents, both offline and at query time. It introduces Materialised Algorithmic Views (MAVs) and the Algorithmic View Selection Problem (AVSP), positions DQO relative to shallow query optimisation and learned optimisers, and sketches a research agenda. The experimental part (Section 5) reports single-threaded microbenchmarks of five grouping implementations on four synthetic uniform datasets, and a dynamic-programming exercise over a two-relation join-and-group query using hand-specified cost models, claiming up to 4x improvement in estimated plan cost.

Significance. The paper is valuable as a vision/position statement: it articulates a plausible research direction, coins useful terminology (physiological operators, MAVs, AVSP), and connects to related work on data-structure synthesis and adaptive indexing. The grouping microbenchmarks are real measurements and the code is available, which is commendable. However, the empirical evidence does not currently establish the central DQO claim. The DP experiment does not enumerate subcomponents, and its reported gains are largely determined by assumed cost constants rather than by measurements or end-to-end query execution. If the authors can supply a cleaner experimental demonstration, the paper would be a useful contribution to the community.

major comments (4)
  1. [§5.3, Table 4, Fig. 7, Appendix A] The experiment does not test the core DQO mechanism. The DP enumeration treats HG, OG, SOG, SPHG, BSG and the corresponding join variants as monolithic physical operators; no operator is internally unnested into subcomponents and no subcomponent-level plans are enumerated. A conventional SQO optimizer that had these five algorithms in its physical-operator catalog and that tracked a density statistic would produce exactly the same plans and the same estimated-cost ratios. Therefore the conclusion in §5.3 that the results 'support our claim that more fine-granular optimisation can lead to better query plans' does not follow from this experiment as designed.
  2. [§5.3, Table 4, Fig. 7] The reported improvement factors are ratios of hand-assumed cost formulas, not measured execution costs. With HJ(R,S)=4(|R|+|S|) and SPHJ(R,S)=|R|+|S|, the maximum possible ratio is exactly 4, so the headline 'up to 4x' is largely built into the constants; similarly, HG(R)=4|R| versus SPHG(R)=|R|. The paper should at least calibrate the cost model against the measured runtimes of Section 5.2, and ideally validate the chosen plans by executing them end-to-end. As it stands, the claimed advantage is self-referential with respect to the cost model.
  3. [§5.2 vs. Table 4] There is an inconsistency between the microbenchmark implementation of SOG and the cost model used in the DP experiment. The microbenchmark always sorts the input (Section 5.1), so SOG pays a sorting cost even on already sorted data (Section 5.2, sorted-dense case). The DP cost model, by contrast, assumes that 'sort and order-based algorithms incur sorting cost only if the input is not sorted' (Appendix A). The measured disadvantage of SOG on sorted inputs would therefore not appear in the DP cost model, so the measured grouping performance cannot be transferred to the planning experiment without an explicit reconciliation.
  4. [§5.2, Fig. 5, §5.1] The grouping microbenchmarks provide no error bars or multiple trials, use only synthetic uniformly distributed data, and assume the number of distinct values is known (Section 5.1). Since the density property is the key enabler of the SPH advantage in Section 5.3, the robustness of that property under realistic cardinality-estimation error and skewed distributions needs to be tested. At minimum, the authors should report variance across runs and discuss how the required density statistic would be obtained in practice.
minor comments (5)
  1. [§2, Fig. 3] The paper does not provide a precise formal definition of 'subcomponent' or 'physiological operator'; Figure 3 is illustrative but not sufficient to specify the DQO search space. Please add a precise definition or at least a concrete example with a fixed set of subcomponents.
  2. [Appendix A, Fig. 8] The figure referred to in the text as 'Table 5' is displayed as 'Figure 8', and the meaning of the property values '3' and '7' in the Dense and Sorted columns is not explained anywhere; please clarify.
  3. [Figure 1] The figure caption contains a typo: 'HashBasedGouping' should be 'HashBasedGrouping'.
  4. [§5.1] The assumption that the number of distinct values is known is strong; even if it can be relaxed with dynamic structures, the paper should state how the density property is classified as dense versus sparse.
  5. [§6] The related work section is quite brief; in particular, prior work on physical operator variants such as radix hash join and partitioned hash join could be cited to better position the claimed novelty.

Circularity Check

1 steps flagged · score 6.0 of 10

The up-to-4x DQO advantage is arithmetically forced by the cost constants in Table 4, which inherit their factor from the Section 5.2 grouping benchmarks; the DP experiment re-imports that factor as its headline result.

  1. fitted input called prediction [Section 5.3, Table 4 and Figure 7]
    "HJ (R, S) = 4· (|R| +|S|) ... SP HJ (R, S) =|R| +|S| ... if at least one input is unsorted, DQO generates plans with an improvement factor of up to 4x."

    The reported 'improvement factor of up to 4x' is the arithmetic ratio of the two hand-set cost formulas in Table 4: HJ(R,S)=4(|R|+|S|) versus SPHJ(R,S)=|R|+|S|, so any DP search that may select SPH will return exactly 4x on the dense unsorted case by construction. Moreover, the constant 4 is already imported from the measured Section 5.2 result that SPHG is 'more than four times faster than HG'. The DP experiment therefore re-labels the same factor as a DQO benefit rather than independently validating it, and it does so using coarse monolithic operators (HJ, SPHJ, HG, SPHG) rather than fine-granular subcomponent enumeration.

full rationale

Aside from the Section 5.3 cost-model loop, the paper is largely self-contained: the Section 5.2 grouping benchmarks are measured runtimes and constitute external evidence; the MAV/AVSP proposals are explicitly described as future work; and self-citations are not load-bearing for the core derivation. The circular component is confined to the headline plan-cost improvement: the factor 4 in Table 4 is taken from the measured grouping speedup in Section 5.2, and the DQO dynamic-programming experiment then returns that same factor as the DQO advantage. Thus the headline number is an arithmetic consequence of the input constants rather than an independent demonstration that enumerating fine-granular subcomponents yields better plans. This matches the rubric for a prediction that reduces by construction, giving a partial-circularity score of 6 rather than a lower score. The conceptual claims about MAVs and AVSP are untested but not circular, and the paper's own wording ('improvement factors for the estimated plan costs') is transparent that no end-to-end runtime measurement is being reported.

Assumptions & free parameters 3 free parameters · 3 assumptions · 2 invented entities

The central claim rests on the assumption that fine-grained algorithmic choices can be modeled with simple additive cost functions and that data properties like density are known and stable. The paper proposes MAVs and AVSP as new concepts but provides no independent validation.

free parameters (3)
  • Hash join cost coefficient = 4
    Assumed in Table 4 as HJ(R,S)=4*(|R|+|S|); affects which join plan the DP selects.
  • Hash grouping cost coefficient = 4
    Assumed in Table 4 as HG(R)=4*|R|; determines the SQO baseline cost.
  • Number of distinct values = assumed known
    Section 5.1 states the number of distinct keys is assumed known, which is required for SPHG and BSG applicability and cost.
assumptions (3)
  • domain assumption The cost formulas in Table 4 are accurate enough to rank plans.
    The DP results in Figure 7 are computed from these formulas without measuring end-to-end runtime.
  • domain assumption Density and sortedness are known a priori and stable across the input.
    Section 2.2 and Section 5.3 treat density as a meta-relational property; no statistics collection cost or uncertainty is modeled.
  • domain assumption Results from 100M-row uniform synthetic data transfer to real workloads.
    All experiments in Section 5 use uniform random integer keys; real data may have skew, correlations, and variable tuple sizes.
invented entities (2)
  • Materialised Algorithmic Views (MAVs)
    purpose: Precomputed, partially or fully optimized subplans below the operator level that can be matched and reused at query time to reduce search space.
    Introduced in Section 3.1. No independent implementation or benchmark validates MAV benefits; it is a proposed concept.
  • Physiological operators
    purpose: Intermediate representations between logical and physical operators that expose sub-operator structure for DQO.
    Introduced in Section 2 and Figure 3 as a conceptual layer; no concrete algebra or system is given.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Case for Deep Query Optimisation." pith.science (2026). https://pith.science/paper/PQVCE63E

@misc{pith2026190808341,
  author       = {Pith},
  title        = {Pith review of: The Case for Deep Query Optimisation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PQVCE63E}},
  note         = {Machine review of arXiv:1908.08341}
}
read the original abstract

Query Optimisation (QO) is the most important optimisation problem in databases. The goal of QO is to compute the best physical plan under a given cost model. In that process, physical operators are used as building blocks for the planning and optimisation process. In this paper, we propose to deepen that process. We present Deep Query Optimisation (DQO). In DQO, we break up the abstraction of a 'physical' operator to consider more fine-granular subcomponents. These subcomponents are then used to enumerate (sub-)plans both offline and at query time. This idea triggers several exciting research directions: (1) How exactly can DQO help to compute better plans than (shallow) QO and at which costs? (2) DQO can be used to precompute and synthesise database operators and any other database component as Materialised Algorithmic Views (MAVs). (3) We identify the Algorithmic View Selection Problem (AVSP), i.e. which MAVs should be materialised when? This paper presents the high-level idea of DQO using an analogy inspired from biology. Then we proceed to question the terms 'physical' and 'physical operator'. We present experiments with a 'physical operator' formerly known as 'hash-based grouping'. We benchmark that operator both independently as well as in the context of DQO-enabled dynamic programming. We conclude by sketching a DQO research agenda.

Figures

Figures reproduced from arXiv: 1908.08341 by the authors.

Figure 1
Figure 1. Textbook-style pseudo-code for hash-based grouping [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Partition-based grouping. Here each ‘line of code’ is written as a producer-consumer [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Standard (‘shallow’) query optimisation (SQO) vs deep query optimisation (DQO) [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Materialised Algorithmic Views (MAVs) in deep query planning and the Algorithmic [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: Grouping performance of four different grouping algorithms on four different input [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: Logical plan of example query. First, we join both input relations R and S and afterwards, we compute the grouping result on the output of the join. However, we want to determine which physical implementations of the join and grouping operators lead to the overall best…
Figure 7
Figure 7. Figure 7: Improvement factors for the estimated plan costs of DQO over SQO. [PITH_FULL_IMAGE:figures/full_fig_p014_7.png]
Figure 8
Figure 8. Figure 8: Dynamic Programming tables for di sively consider static perfect hashbased algorit Figure 8: Dynamic Programming tables for ilidttift hhbd l Figure 8: Dynamic Programming tables for di ilidttift hhbd lit Figure 8: Dynamic Programming tables for ilidttift hhbd l Figure …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    A database system for research

    mu table. A database system for research. https://bigdata.uni-saarland.de/projects/ mutable/. Accessed: 2019-12-16

    work page 2019

  2. [2]

    Baralis et al

    E. Baralis et al. Materialized views selection in a multidimensional database. VLDB, 1997

    work page 1997

  3. [3]

    P. A. Boncz et al. Monetdb/x100: Hyper-pipelining query execution. CIDR, 2005

    work page 2005

  4. [4]

    Dittrich et al

    J. Dittrich et al. Progressive merge join: A generic and non-blocking sort-based join algo- rithm. VLDB, 2002

    work page 2002

  5. [5]

    G. Graefe. Query evaluation techniques for large databases. ACM Comput. Surv. , 25(2), 1993

    work page 1993

  6. [6]

    Graefe et al

    G. Graefe et al. The volcano optimizer generator: Extensibility and efficient search. ICDE, 1993

    work page 1993

  7. [7]

    J. M. Hellerstein et al. Online aggregation. SIGMOD, 1997

    work page 1997

  8. [8]

    Idreos et al

    S. Idreos et al. The data calculator: Data structure design and cost synthesis from first principles and learned cost models. SIGMOD, 2018

    work page 2018

Show all 24 references
  1. [9]

    Idreos et al

    S. Idreos et al. The periodic table of data structures. IEEE Data Eng. Bull. , 41(3), 2018

    2018

  2. [10]

    M. L. Kersten et al. Cracking the database store. CIDR, 2005

    2005

  3. [11]

    Kersten et al

    T. Kersten et al. Everything you always wanted to know about compiled and vectorized queries but were afraid to ask. PVLDB, 11(13), 2018

    2018

  4. [12]

    C. Koch. Abstraction without regret in data management systems. CIDR, 2013

    2013

  5. [13]

    C. Koch. Abstraction without regret in database systems building: a manifesto. IEEE Data Eng. Bull. , 37(1), 2014

    2014

  6. [14]

    Leis et al

    V. Leis et al. The adaptive radix tree: Artful indexing for main-memory databases. ICDE, 2013

    2013

  7. [15]

    Leis et al

    V. Leis et al. Morsel-driven parallelism: a numa-aware query evaluation framework for the many-core age. SIGMOD, 2014

    2014

  8. [16]

    Moerkotte

    G. Moerkotte. Building query compilers. http://pi3.informatik.uni-mannheim.de/ ~moer/querycompiler.pdf. Accessed: 2019-12-16. 16

    2019

  9. [17]

    Moerkotte et al

    G. Moerkotte et al. Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products. VLDB, 2006

    2006

  10. [18]

    Moerkotte et al

    G. Moerkotte et al. Dynamic programming strikes back. SIGMOD, 2008

    2008

  11. [19]

    T. Neumann. Efficiently compiling efficient query plans for modern hardware. PVLDB, 4(9), 2011

    2011

  12. [20]

    Neumann et al

    T. Neumann et al. Adaptive optimization of very large join queries. SIGMOD, 2018

    2018

  13. [21]

    Richter et al

    S. Richter et al. A seven-dimensional analysis of hashing methods and its implications on query processing. PVLDB, 9(3), 2015

    2015

  14. [22]

    F. M. Schuhknecht et al. The uncracked pieces in database cracking. PVLDB, 7(2), 2013

    2013

  15. [23]

    F. M. Schuhknecht et al. Adaptive adaptive indexing. ICDE, 2018

    2018

  16. [24]

    Wang et al

    W. Wang et al. Database meets deep learning: Challenges and opportunities. SIGMOD Record, 45(2), 2016. A Dynamic Programming Results Table 5 shows the dynamic programming tables for the different combinations of input relation properties in a DQO setting, i.e. we consider addit...

    2016

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.