{"id":"cec40483-e1a3-4ffa-8f32-d41843bdbdd7","arxiv_id":"1908.08341","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Database query optimisation can be pushed below physical operators into index and loop internals, and early experiments show data density changes which grouping algorithm is fastest.","lead":"This paper proposes Deep Query Optimisation, or DQO, a framework that optimizes query plans below the level of physical operators, tuning internals like index structures and load loops. The idea could make database query optimizers adapt to data properties such as density, though the reported evidence is still early and mostly estimated.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 5.3's DP experiment compares monolithic SPH operators against standard ones with hand-set cost constants, so it tests SQO with a larger operator catalog, not DQO's subcomponent enumeration; the up-to-4x gain is largely built into the cost model.","rationale":"The reader's verdict (CONDITIONAL) is reasonable: the paper is a position paper that openly defers validation. My stress-test does not change that verdict but sharpens why the current experimental section cannot carry the central claim. The reader focused on the hand-assumed cost formulas in Table 4; that is a real problem, but an even more basic one is that Section 5.3 is not a DQO experiment at all. It compares five whole-operator implementations chosen by a dynamic program, which is exactly what a shallow optimizer would do if its operator catalog were extended with SPH alternatives and its statistics included density. No subcomponent is enumerated, no operator is opened up, and no MAV is used. Thus even a perfect measurement of those five implementations would only demonstrate that more physical alternatives plus better statistics help, not that breaking the physical-operator abstraction helps. The 4x factor is additionally a direct consequence of the chosen cost constants. I therefore agree with the reader's conditional posture but locate the load-bearing weakness one level deeper: the experiment lacks construct validity for the DQO claim. The proposed test—running the same DP with an SQO baseline that knows SPH operators and density—would settle whether the reported advantage is due to 'deep' optimization or merely to an expanded operator set.","tokens_in":24769,"tokens_out":7693,"duration_ms":80225,"concrete_test":"Re-run the Section 5.3 dynamic program with a baseline optimizer that has the same five grouping/join implementations (including SPHG and SPHJ) as ordinary physical operators and the same density statistic, i.e., an SQO optimizer with an extended operator catalog. If that baseline selects the identical plans and identical cost ratios as the DQO DP, then the experiment provides no evidence that sub-operator-level enumeration is what produces the better plans; the claimed DQO advantage would reduce to 'more operator choices are available'.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim needs evidence that enumerating fine-granular subcomponents yields better plans than enumerating coarse physical operators. Section 5.3 does not provide that evidence. Its DP tables treat HG, OG, SOG, SPHG, BSG and the corresponding join algorithms as monolithic alternatives with the simple cost formulas of Table 4; no operator is ever unnested and no plan inside an operator is 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 'improvement factors'. The only element presented as DQO-specific is the density property, which is an input statistic rather than a subcomponent. Moreover, the reported up-to-4x improvement is largely built into the assumed constants: with HJ(R,S)=4(|R|+|S|) and SPHJ(R,S)=|R|+|S|, the maximum possible ratio is exactly 4. The measured grouping benchmarks in Section 5.2 show that a specialized implementation can be faster, but they do not show that the advantage requires optimization at a finer granularity than SQO already uses. The Section 5.3 conclusion that this 'supports our claim that more fine-granular optimisation can lead to better query plans' therefore does not follow from the experiment as designed.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24999,"tokens_out":8243,"duration_ms":76776,"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":[{"comment":"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.","section":"§5.3, Table 4, Fig. 7, Appendix A"},{"comment":"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.","section":"§5.3, Table 4, Fig. 7"},{"comment":"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.","section":"§5.2 vs. Table 4"},{"comment":"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.","section":"§5.2, Fig. 5, §5.1"}],"minor_comments":[{"comment":"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.","section":"§2, Fig. 3"},{"comment":"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.","section":"Appendix A, Fig. 8"},{"comment":"The figure caption contains a typo: 'HashBasedGouping' should be 'HashBasedGrouping'.","section":"Figure 1"},{"comment":"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.","section":"§5.1"},{"comment":"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.","section":"§6"}],"recommendation":"major_revision","confidential_remarks":"This is essentially a vision/position paper with early experiments. The experimental claims as they stand are not supported because the DP experiment does not isolate the DQO mechanism and the improvement factors are artifacts of the assumed cost model. I would not be comfortable accepting the paper in its current form. If the venue values vision papers, a major revision that either (a) adds an experiment comparing subcomponent enumeration against monolithic operator enumeration with measured runtimes, or (b) substantially rewrites the evaluation as illustrative rather than supporting, is the right path. The conceptual contributions (MAVs, AVSP, the taxonomy) are reasonable and should be preserved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: a readable position paper with a real observation and honest early experiments, but its headline evidence for DQO doesn't test what it claims. I'd send it to review anyway; the idea deserves airing and the experiments are a useful first step.\n\nWhat's new: DQO as a framing, MAVs/AVSP vocabulary, and the 'physiological operator' middle ground. The observation that physical operators are not atomic and their internals carry optimizable choices is not new—Idreos and Koch, plus the group's own hashing study, already point that way—but the paper packages it cleanly and gives a concrete research agenda. The grouping benchmarks in Section 5.2 are real measurements, with code on GitHub, and they do show density and sortedness flip which algorithm wins. That is reproducible evidence, and it motivates the central claim better than the DP exercise does.\n\nWhere it wobbles: Section 5.3 does not demonstrate deep optimisation in the sense defined earlier. The DP tables enumerate monolithic implementations—HG, OG, SOG, SPHG, BSG and their join counterparts—with cost formulas from Table 4. No operator is unnested, no subcomponent plan is enumerated. A conventional SQO optimizer with a richer operator catalog and a density statistic would produce the same plans and the same improvement factors. The up-to-4x improvement is also baked into the constants: HJ(R,S)=4(|R|+|S|) versus SPHJ(R,S)=|R|+|S| makes 4x the maximum possible ratio by construction. So the section supports 'a specialized implementation can be much cheaper' but not 'finer-granular enumeration beats coarser enumeration.' That is a real gap, and the paper half-admits it by repeatedly deferring validation in Sections 3.4 and 7. Minor complaints: uniform synthetic data, no error bars, single-threaded microbenchmarks. Fine for a pilot, but not enough to push significance. The density assumption is stated, which I appreciate; it matters for SPH applicability.\n\nBottom line: the load-bearing experimental claim is under-supported, but the conceptual point holds up and the paper is honest about what is missing. Whoever picks this up should either run the comparison as stated (same operator set, SQO vs DQO enumeration) or compare end-to-end queries. I'd cite it as a position statement if writing about operator synthesis or adaptive indexing. Send it for review; a good referee will push hard on Section 5.3.","headline":"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.","tokens_in":25572,"tokens_out":1850,"would_cite":true,"duration_ms":18344,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["deep query optimisation","physical operators","static perfect hashing","materialised algorithmic views","algorithmic view selection problem","meta-relational properties","dynamic programming","grouping algorithms"],"falsifier":"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.","tokens_in":24516,"feed_emoji":"🔍","tokens_out":9616,"duration_ms":83690,"temperature":0.7,"pith_summary":"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.","feed_headline":"Peering inside database operators can cut query costs fourfold","feed_subtitle":"DQO treats operator internals as mini query plans, letting density pick static-perfect-hash algorithms for fourfold gains.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Documents that hash-table dimensions strongly influence performance, motivating sub-operator algorithm choices beyond coarse operator selection.","marker":"[21]"},{"why":"Presents the periodic table of data structures and synthesised data structures, the closest prior work that DQO generalises into materialised algorithmic views.","marker":"[9]"},{"why":"Shows cost-based synthesis of data-structure designs from first principles; DQO extends this to optimisation both offline and at query time.","marker":"[8]"},{"why":"Argues for deconstructing database systems into first principles and synthesising/composing algorithms, which DQO applies inside query operators.","marker":"[13]"},{"why":"Represents learned query optimisation, the approach DQO contrasts with by relying on rules and enumeration over fine-grained building blocks.","marker":"[24]"},{"why":"Provides the materialised-view-selection problem that the Algorithmic View Selection Problem (AVSP) is modelled on.","marker":"[2]"},{"why":"Supplies the dynamic-programming plan-enumeration technique that the DQO experiments extend with the density property.","marker":"[18]"},{"why":"Analyses dynamic-programming algorithms for bushy join trees, the fallback enumeration methods DQO cites for large search spaces.","marker":"[17]"},{"why":"Introduces interesting orders and physical properties in the Volcano generator, the property concept DQO generalises to meta-relational properties.","marker":"[6]"},{"why":"Defines the volcano-style operator/iterator abstraction whose boundaries DQO proposes to break.","marker":"[5]"}],"fun_headline_variants":["Splitting database operators in two cuts query costs 4x","Deep Query Optimisation: operator internals as mini query plans","Look inside operators: subcomponent choices yield 4x gains","Rethinking physical operators gives fourfold speedups","DQO: design choices inside operators can quadruple performance"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Splitting database operators in two cuts query costs 4x","Deep Query Optimisation: operator internals as mini query plans","Look inside operators: subcomponent choices yield 4x gains","Rethinking physical operators gives fourfold speedups","DQO: design choices inside operators can quadruple performance"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000733,"raw_usage":{"total_tokens":3324,"prompt_tokens":1039,"completion_tokens":2285,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":655,"completion_tokens_details":{"reasoning_tokens":2202}},"tokens_in":655,"tokens_out":2285,"duration_ms":15344,"temperature":1.0,"reasoning_tokens":2202,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:41:10.109990+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Richter et al","cited_arxiv_id":null,"evidence_quote":"Documents that hash-table dimensions strongly influence performance, motivating sub-operator algorithm choices beyond coarse operator selection."},{"cited_title":"Idreos et al","cited_arxiv_id":null,"evidence_quote":"Presents the periodic table of data structures and synthesised data structures, the closest prior work that DQO generalises into materialised algorithmic views."},{"cited_title":"Idreos et al","cited_arxiv_id":null,"evidence_quote":"Shows cost-based synthesis of data-structure designs from first principles; DQO extends this to optimisation both offline and at query time."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Argues for deconstructing database systems into first principles and synthesising/composing algorithms, which DQO applies inside query operators."},{"cited_title":"Wang et al","cited_arxiv_id":null,"evidence_quote":"Represents learned query optimisation, the approach DQO contrasts with by relying on rules and enumeration over fine-grained building blocks."},{"cited_title":"Baralis et al","cited_arxiv_id":null,"evidence_quote":"Provides the materialised-view-selection problem that the Algorithmic View Selection Problem (AVSP) is modelled on."},{"cited_title":"Moerkotte et al","cited_arxiv_id":null,"evidence_quote":"Supplies the dynamic-programming plan-enumeration technique that the DQO experiments extend with the density property."},{"cited_title":"Moerkotte et al","cited_arxiv_id":null,"evidence_quote":"Analyses dynamic-programming algorithms for bushy join trees, the fallback enumeration methods DQO cites for large search spaces."},{"cited_title":"Graefe et al","cited_arxiv_id":null,"evidence_quote":"Introduces interesting orders and physical properties in the Volcano generator, the property concept DQO generalises to meta-relational properties."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the volcano-style operator/iterator abstraction whose boundaries DQO proposes to break."}],"review_version":1}