The Selection Problem in Multi-Query Optimization: a Comprehensive Survey

Denis Ponomaryov; Sergey Zinchenko

REVIEW 4 major objections 7 minor 2 references

The Selection Problem in Multi-Query Optimization: a Comprehensive Survey

T0 review · 4 major / 7 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read A linear tree traversal can replace the exponential optimization step in state-of-the-art view selection algorithms, exponentially accelerating them.

desk verdict A useful survey and a plausible new complexity result, but the headline exponential-acceleration claim rests on a proof that does not handle OR-nodes; referee time is warranted but the theorem needs to be restricted or rewritten. read the letter →

arxiv 2412.11828 v2 pith:HB45J3FX submitted 2024-12-16 cs.DB cs.DM

Sergey Zinchenko , Denis Ponomaryov This is my paper · ORCID

classification cs.DBcs.DM

keywords multi-queryoptimizationviewselectionindexplancachingcandidateproblemexpressionforestintegerprogrammingtreetraversal

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

This survey argues that all major multi-query optimization selection tasks — materialized views, indexes, query result caching, and plan caching — are instances of one Candidate Selection Problem, and that the tree structure shared by candidates in these scenarios is the key to efficient algorithms. The paper's own technical contribution is a method that replaces the exponential integer-programming step in recent state-of-the-art view selection algorithms, BigSubs and RL View, with a linear-time tree traversal that decides reuse of selected candidates. If the method is correct, those algorithms can run many more iterations within the same time budget, improving solution quality, and the relaxation of an overly strict constraint (prohibiting reuse of nested candidates) can even increase the achievable benefit.

What carries the argument

The load-bearing mechanism is the bottom-up recurrence $\operatorname{max\ subtree\ benefit}[node] = \max(\sum_{child} \operatorname{max\ subtree\ benefit}[child],\ node.reuse\ benefit)$ (Algorithm 2). It assumes benefit decomposes as $B'_c \cdot n_{reuses}(c)$ with independent single-reuse benefit $B'_c$, and it converts the selection-usage subproblem from an integer linear program with variables for every query-candidate pair into a tree traversal computing the optimal reuse assignment in linear time.

What would settle it

Build a small expression forest with a shared subexpression reached from two different computation flows (e.g., a diamond-shaped DAG where a filtered node feeds two join branches). Run Algorithm 2 and check whether its computed reuse assignment matches the exhaustive enumeration of all reuse choices for every budget; if the DP overcounts or routes a reuse to both flows, the recurrence fails exactly there.

Watch

Extended reading notes

Core claim

The paper establishes that candidate selection across view materialization, index selection, and query/plan caching is a single framework, the Candidate Selection Problem, in which candidates are tree nodes and benefits and expenses are weights of computation paths. Its main novel result, Theorem 2, states that the per-query step of deciding how to optimally reuse an already-fixed set of selected candidates — previously formulated as an integer linear program in BigSubs and RL View with a constraint forbidding simultaneous reuse of nested candidates — is computable in polynomial time by a single traversal of the expression forest, so that nested candidates may be reused simultaneously within different computation flows. The proof constructs a bottom-up dynamic programming recurrence: for each node the maximum subtree benefit is the maximum of the sum over children's maximum subtree benefits and the node's own reuse benefit, after which a top-down count of accessing computation flows distributes reuse decisions without conflicts.

Load-bearing premise

The linear-time speed-up depends on the assumption that the total benefit of reusing selected candidates is correctly captured by the local recurrence comparing the sum of children's best subtree benefits to the node's own reuse benefit, so that benefits decompose additively over independent computation flows with no more than one reuse per flow.

Editorial extensions

If this is right

The inner optimization loop of BigSubs and RL View, which required solving an exponential ILP with many auxiliary variables, can be replaced by a linear-time tree traversal, yielding an exponential speed-up of each iteration.
Allowing simultaneous reuse of nested candidates (when they lie on different computation flows) can increase the achievable benefit relative to the original ILP-based formulation, which forbade all such pairs.
The same tree-structure argument transfers directly to other Candidate Selection Problem instances, such as index selection under a space budget and plan caching with compressed tree storage, because their candidates are also trees.
More iterations of the selection loop become affordable within a fixed time budget, which improves the quality of the final selected candidate set in the learned and randomized algorithms.

Reading between the lines

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

The linear-time recurrence likely extends well beyond view selection: any selection problem with tree-ordered candidates and additive benefits (index selection over stored plans, compressed plan caches) should inherit the same speed-up with the same local DP, provided an AND-DAG-like flow semantics holds.
A key open point is the correctness boundary of the recurrence on expression forests with shared subexpressions (DAGs) and OR-arcs; if a node can be reached from multiple computation flows, the sum-over-children rule could overcount benefit in ways the paper's sketch does not yet address.
A concrete test would be to implement Algorithm 2 in BigSubs/RL View, compare the final selected-benefit and workload runtime to the ILP version on the original benchmarks: the paper claims the same or better benefit with drastically shorter iteration time.
The paper's claim of exponential acceleration presumes that replacing the ILP step does not change what the flip function and learned model observe; if the stats vector differs materially across iterations, existing RL-policy convergence behavior may shift.

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.

Desk Editor's Note

read the letter

Short version: this is a solid survey with a clean unifying framing, and the NP-hardness result for binary AND-DAGs is a real if tersely proved addition. But the advertised "exponentially accelerate" claim depends on Theorem 2, and as written that theorem overreaches: Algorithm 2 sums benefit over all children, which is only valid for AND nodes. The paper's own framework includes OR nodes (multiple children, alternative paths), and there summing over children overcounts. The minimal counterexample works: an OR node with two alternative children each worth 100 gives a reported 200, while any actual execution gets at most 100. The proof sketch does not distinguish arc types, never states whether node.reuse_benefit is per-use or total, and gives no induction for DAGs or OR-arcs. So the theorem as stated is not established. The good news: the actual BigSubs/RL View use case involves per-query plans that are AND trees/DAGs, so the idea is likely salvageable by restricting the claim to AND-DAGs or by taking a max over OR alternatives. That is a revision, not a fatal blow.

What I liked: the Candidate Selection Problem framing is a genuinely useful organizational abstraction, and the survey covers ML-based selection algorithms that the 2012 Mami and Bellahsene survey misses. The classification is careful, the examples are helpful, and the literature coverage looks honest. Theorem 1's reduction is sketched tightly; the scaling argument for assuming min(w_i)^2 > W is glossed over but can be made rigorous, so I would not call that a load-bearing flaw. There are no experiments, which is normal for a survey, but the acceleration claim is presented as a derived method rather than a hypothesis, and without either a complete proof or a benchmark that is too strong.

For whom: researchers in database physical design or MQO will want this as a reference survey. The technical claims need care before being cited. I would send it to peer review and ask for a corrected Theorem 2 (state the AND restriction or fix OR handling) and ideally a small experiment on BigSubs/RL View to back the speedup claim. The survey alone justifies referee time.

Referee Report

4 major / 7 minor

Summary. The paper proposes a unified 'Candidate Selection Problem' (CSP) covering view materialization, index selection, query caching, and plan caching; it surveys heuristic, randomized, and machine-learning selection algorithms, and it contributes two original formal results: NP-hardness of the View Selection Problem over binary AND-DAGs (Theorem 1) and a polynomial-time bottom-up procedure for the reuse step of the BigSubs/RL View algorithms (Theorem 2), from which the abstract derives a claim of exponential acceleration of some state-of-the-art selection algorithms. The survey portion is broad and well organized, but the original results carry the paper's strongest claims and are not fully established as stated.

Significance. If the theorems were correct, the paper would provide both a useful organizing framework and a substantial algorithmic improvement: the unified CSP formulation and the tree-structure-based benefit analysis could enable technique transfer across view/index selection and caching, and a polynomial-time reuse step would be a real advance over the ILP-based feedback loop in BigSubs/RL View. The survey classification and literature coverage are genuine contributions independent of those claims. I found no circular reasoning or fitted-parameter issues; the new results are presented as derivations from stated definitions and prior complexity results, though with proof gaps. The significance is therefore conditional: the acceleration claim needs either a corrected proof restricted to the cases where it holds, or an explicit downgrade to a conjecture.

major comments (4)

[6.2 (Theorem 2, Algorithm 2)] The recurrence max_subtree_benefit[node] = max(total_child_benefit, node.reuse_benefit) sums benefits over all children. This is only valid for AND nodes. In the paper's own representation (Section 4.1), an eq-node with multiple children represents OR alternatives, so summing child benefits counts benefits from mutually exclusive computation paths. For example, an OR node R with two alternative children A and B, each with a one-use benefit of 100, receives total_child_benefit(R) = 200 and may have both A and B marked for reuse, while any valid execution obtains at most 100. The proof sketch in Section 6.2 does not define arc-type handling, does not state whether node.reuse_benefit is a per-use or total quantity, and gives no induction for DAGs with shared subexpressions; the reverse-topological counting step is described informally. Since Theorem 2 is the basis of the abstract's 'exponentially accelerate' claim, that claim is not established as stated. The theorem should be restricted to AND-DAG/tree inputs, or the recurrence should be revised (e.g., taking a max over OR alternatives), with a formal correctness proof.
[3.6 (Theorem 1)] The proof reduces Knapsack to VSP by constructing a join of n tables with filters and asserting that any candidate other than the filtered tables has size at least min_i(wi)^2, so it cannot fit in the budget W. This relies on an unstated multiplicative (cross-product) model of join output sizes and on specific cost assumptions for reading and filtering. None of these assumptions appears in the theorem statement or in the definition of the View Selection Problem. The theorem statement should include the cost model explicitly, and the scaling argument used to ensure min_i(wi)^2 > W should be shown to preserve the Knapsack optimum. As written, the NP-hardness claim is not fully supported.
[7.1 (Challenges and Open Problems)] The open-problems section states that 'the question of existence of an exact polynomial solution' for AND-DAG is still open, citing Gupta and Mumick (2005) and Karloff and Mihail (1999). This contradicts Theorem 1, which states NP-hardness for binary AND-DAG. Because binary AND-DAG is a subclass of AND-DAG, NP-hardness for the subclass implies NP-hardness for the general class under the same cost model. The authors should either remove this contradiction or explain precisely which restricted variant remains open.
[6.1-6.2 (BigSubs/RL View acceleration)] The paper claims that replacing the ILP feedback in Algorithm 1 with Algorithm 2 'exponentially accelerates' BigSubs and RL View while improving quality. Algorithm 2 computes a maximum subtree benefit and marks nodes where max_subtree_benefit[node] == node.reuse_benefit, but the proof does not show how the per-candidate reuse counts n_reuses_c and the stats vector are derived from this marking, especially for shared nodes, nor does it show that the result is equivalent to the ILP feedback objective used in the original algorithms. No experimental results or benchmarks are presented to substantiate the quality claim. At minimum, the authors should give a formal statement that the DP solves the per-query reuse optimization problem solved by the ILP (with the nesting constraint removed), and ideally an empirical comparison on workloads used by BigSubs and RL View.

minor comments (7)

[3.1] The heading 'Multi-Query Optmization' contains a typo; it should read 'Optimization'.
[3.3] The text contains the duplicated phrase 'Executing a workload workload with all possible sets of selected candidates is infeasible'.
[4.3] The heading 'How are contraints modeled?' contains a typo; it should read 'constraints'.
[4.1 (Example 7)] Example 7 refers to 'a workload of two queries sigma_A(T1) and sigma_B(T1) given in Figure 1', but Figure 1 illustrates the join example from Section 3.1; the intended reference appears to be Figure 7.
[6.2 (Algorithm 2)] Algorithm 2 is declared with 'Input: Tree structure with nodes as candidates', while Theorem 2 refers to an expression forest; the terminology should be aligned, since the correctness issue over DAGs and OR-arcs depends on this distinction.
[5.2.1] The sentence 'the view is not / is selected because without an index its benefit insufficient' appears garbled and should be rewritten.
[6.1 (Algorithm 1)] In the comment inside Algorithm 1, 'flip f unction' has an erroneous space and should be 'flip function'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the new results derive from the paper's stated models and external complexity results; the OR-arc concern is a soundness gap, not a circular step.

full rationale

I found no load-bearing circular step. The paper's principal new technical claims are Theorem 1, which proves AND-DAG VSP NP-hardness by a self-contained knapsack reduction, and Theorem 2, which proposes Algorithm 2 as a polynomial-time substitute for the ILP reuse step. Theorem 2 is not derived by fitting a parameter or by renaming an input; it is an algorithmic claim whose proof sketch relies on the benefit decomposition in Equation (1). That decomposition is stated as a modeling assumption for tree/AND-DAG structures, not as a consequence of Theorem 2. The unified Candidate Selection Problem is an organizational abstraction, not a prediction that is forced by construction. The skeptical objection about OR-arcs is a correctness or generality gap: Algorithm 2 sums benefits over all children, whereas OR-arcs represent alternative computation paths, so the proof does not establish the claimed optimality for general AND-OR-DAGs. But an unproven or even incorrect generalization is not circular reasoning. The paper also contains no self-citations and no fitted values renamed as predictions; all cited complexity and algorithmic results are external (Gupta and Mumick, Karloff and Mihail, Harinarayan et al., Jindal et al., Yuan et al.). A soundness flaw in the proof of Theorem 2 should be reported as a correctness risk, not as circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 2 invented entities

The central claims rely on the benefit-decomposition assumption (Eq. 1) and the tree-structure assumption; the NP-hardness proof contains an unstated cross-product join-size assumption. No free parameters are fitted to data. The introduced entities are algorithmic abstractions without independent falsifiable handles.

assumptions (5)

domain assumption Benefit of a candidate c can be decomposed as B'_c * n_reuses_c(C) (Equation 1).
Used throughout Section 6 to justify Algorithm 2; the paper notes this decomposition is valid only for AND-DAGs without alternative paths (Section 3.3).
domain assumption The nature of candidates is irrelevant; only representation and benefit/expense computation matter.
Core premise of the unified Candidate Selection Problem (Section 3.5); asserted with examples, not formally proven, and limits the framework's guarantees.
domain assumption Candidates can be represented as tree nodes and benefits/expenses as path weights.
Section 3.5 and Figure 5; this is what enables transferring algorithms between VSP, ISP, and caching.
ad hoc to paper Join output sizes in Theorem 1 obey a multiplicative (cross-product) model, so any partial join has size at least min_i(wi)^2.
Implicit in the Theorem 1 proof to prevent large join candidates from fitting in the knapsack budget; not stated or justified in the paper.
standard math Knapsack is NP-hard and greedy approximation bounds (63% and 47%) hold.
Background complexity results cited from Gupta et al. 1997 and Karloff and Mihail 1999, used to position the new NP-hardness and approximation discussion.

invented entities (2)

Candidate Selection Problem (CSP)
purpose: Abstract unified optimization problem for view/index selection and query/plan caching.
A conceptual framework proposed in Section 3.5; it has no falsifiable prediction or independent implementation beyond the paper.
Compressed expression forest F'
purpose: Data structure to preserve topological order among selected candidates for incremental updates.
Proposed in Section 6.2; correctness is argued informally and no independent validation is provided.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Selection Problem in Multi-Query Optimization: a Comprehensive Survey." pith.science (2026). https://pith.science/paper/HB45J3FX

@misc{pith2026241211828,
  author       = {Pith},
  title        = {Pith review of: The Selection Problem in Multi-Query Optimization: a Comprehensive Survey},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HB45J3FX}},
  note         = {Machine review of arXiv:2412.11828}
}

read the original abstract

View materialization, index selection, and plan caching are well-known techniques for optimization of query processing in database systems. The essence of these tasks is to select and save a subset of the most useful candidates (views/indexes/plans) for reuse within given space/time budget constraints. In this paper, we propose a unified view on these selection problems. We make a detailed analysis of the root causes of their complexity and summarize techniques to address them. Our survey provides a modern classification of selection algorithms known in the literature, including the latest ones based on Machine Learning. We provide a ground for reuse of the selection techniques between different optimization scenarios and highlight challenges and promising directions in the field. Based on our analysis we derive a method to exponentially accelerate some of the state-of-the-art selection algorithms.

Figures

Figures reproduced from arXiv: 2412.11828 by the authors.

**Figure 2.** To discover options for computation reuse, a procedure of merging several expression trees [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 3.** When table T1 is updated, the selected candidates must also be updated. And updating candidate c3 can be accelerated by reusing the updated common computation c2, which shows that the expense function may have a complex behaviour. The selected candidates are shown in black rectangles and update operations with the corresponding execution times are shown in green [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Figures from the paper (7 more)

**Figure 4.** Figure 4: To improve the efficiency of plan caching, it is possible to store common parts of plans [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]

**Figure 5.** Figure 5: The key observation in our study is that the tree structure of candidates can be used to [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]

**Figure 6.** Figure 6: On the left: representation of the workload by using AND-OR-DAG depicting alternative [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]

**Figure 7.** Figure 7: Introducing σA∨B enables computation reuse. Despite the potential overhead of creating and maintaining σA∨B, one can achieve an overall speed up of the workload. The additional computation and the way of its reuse are shown in orange. Subexpression space is a good sta…

**Figure 8.** Figure 8: Prohibiting the simultaneous reuse of candidates [PITH_FULL_IMAGE:figures/full_fig_p029_8.png]

**Figure 9.** Figure 9: To keep only the selected candidates from the expression forest [PITH_FULL_IMAGE:figures/full_fig_p029_9.png]

**Figure 10.** Figure 10: In order to add a new candidate c4 to the set of selected candidates {c1, c6, c7, c8}, the compressed forest needs to be rebuilt. To do this, we first find the parents of c4 which involves searching for the lowest vertices x such that is parent(x, c4) = T rue (node c8…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

2 extracted references · 1 canonical work pages

[1994]

In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB ’94)

Fast, Randomized Join-Order Selection - Why Use Transformations?. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB ’94) . Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 85–95. 33 [Ghosh et al.(2002)] Antara Ghosh, Jignashu Parikh, Vibhuti S Sengar, and Jayant R Haritsa. 2002. Plan selection based on query cluste...

arXiv 2002
[2008]

Lecture Notes in Computer Science 5022 (2008), 121–132

Parallel simulated annealing for materialized view selection in data warehousing envi- ronments. Lecture Notes in Computer Science 5022 (2008), 121–132. [Diwan et al.(2006)] AA Diwan, S Sudarshan, and Dilys Thomas. 2006. Scheduling and caching in multi-query optimization. In International Conference on Management of Data COMAD, Delhi, India. [Galindo-Lega...

work page 2008

Pith tools

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

[1] [1994]

In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB ’94)

Fast, Randomized Join-Order Selection - Why Use Transformations?. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB ’94) . Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 85–95. 33 [Ghosh et al.(2002)] Antara Ghosh, Jignashu Parikh, Vibhuti S Sengar, and Jayant R Haritsa. 2002. Plan selection based on query cluste...

arXiv 2002

[2] [2008]

Lecture Notes in Computer Science 5022 (2008), 121–132

Parallel simulated annealing for materialized view selection in data warehousing envi- ronments. Lecture Notes in Computer Science 5022 (2008), 121–132. [Diwan et al.(2006)] AA Diwan, S Sudarshan, and Dilys Thomas. 2006. Scheduling and caching in multi-query optimization. In International Conference on Management of Data COMAD, Delhi, India. [Galindo-Lega...

work page 2008