{"id":"c9ba2d30-c081-4e47-9295-903fd7ee72a0","arxiv_id":"2412.11828","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A survey unifying view, index, and plan selection into one candidate selection problem, adding an NP-hardness proof and a claimed polynomial-time reuse optimization for RL View and BigSubs.","lead":"This paper surveys how databases choose which shared computations (views, indexes, plans) to save and reuse, and bundles them into one 'candidate selection' problem. It also claims a tree-based method that can replace an exponential optimization step in two leading view selection algorithms with linear-time work, but provides no experiments.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's Algorithm 2 sums benefits over all children, but OR-arcs are alternative computation paths; on an OR-DAG it can report twice the obtainable benefit, so the exponential-acceleration claim is unproven in the stated generality.","rationale":"Read in good faith: the paper is a survey with a new unified CSP framework, a new NP-hardness result, and a proposed linear-time replacement for the ILP step in BigSubs/RL View. The most load-bearing piece is Theorem 2, because the abstract's exponential-acceleration claim rests on it. The proof of Theorem 2 is only a sketch, and Algorithm 2's recurrence treats every child additively. Section 4.1 explicitly introduces OR-DAGs and AND-OR-DAGs, where an eq-node's children are alternative computation paths; for such nodes the correct local operation is max over children, not sum. A two-branch OR node with one high-benefit candidate per branch gives Algorithm 2 a benefit of 2x while only one branch can execute, so the theorem is false in the generality stated. This is an internal inconsistency, not a disagreement with consensus: the paper's own definitions imply OR semantics. The same failure can occur for AND-OR-DAGs with shared subexpressions. I did not find a concrete failure for pure AND-DAGs; the recurrence appears defensible there, so the correction may be simply to scope Theorem 2 to AND-DAG/tree expression forests and to prove it with an explicit per-use induction. The survey's classification and the algorithmic idea remain valuable, and the absence of experiments already justifies caution. Hence the reader's conditional verdict stands, with the requested revision made more precise.","tokens_in":27658,"tokens_out":22992,"duration_ms":226085,"concrete_test":"Construct a single-query AND-OR-DAG: an OR eq-node R with two alternative op-children A and B; A has a selected eq-node cA with reuse benefit 100, and B has selected eq-node cB with reuse benefit 100. Run Algorithm 2's MaxBenefitFromSubtree(R). It computes total_child_benefit = 100 + 100 = 200 and can mark both cA and cB for reuse. Enumerate all valid reuse plans under OR semantics (choose exactly one alternative path per OR node): the optimum is 100. If the implementation returns 200, Theorem 2 as stated is false. Then re-run the same test on the same DAG after replacing the OR node with an AND node, or restrict the theorem to AND-DAGs; if the DP then matches exhaustive search on randomly generated AND-DAGs with shared subexpressions, the corrected scope is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing assertion is Theorem 2: the second step of Algorithm 1 is solvable in polynomial time by the bottom-up recurrence in Algorithm 2, max(total_child_benefit, node.reuse_benefit). This recurrence is only correct for AND nodes, where every child is required. In the paper's own representation framework (Section 4.1), eq-nodes with multiple children are OR nodes: the children are alternative computation paths, and only one is chosen per execution. Algorithm 2 sums over all children, so for an OR node it counts benefits from alternatives that can never be realized together. Minimal counterexample: an OR node R with two alternative children A and B; suppose reusing the selected candidate under A is worth 100 and under B is worth 100. Algorithm 2 reports total_child_benefit(R) = 200 and may mark both for reuse, but any valid execution of R uses exactly one alternative, so the maximum obtainable benefit is 100. The proof sketch in Section 6.2 does not define how arc types are handled, does not state whether node.reuse_benefit is a per-use or total quantity, and gives no induction for DAGs or OR-arcs. Therefore Theorem 2's generality, and with it the abstract's \"exponentially accelerate\" claim, is not established for AND-OR-DAG expression forests; the theorem should be restricted to AND-DAGs/trees or revised to handle OR nodes by taking a max over alternatives. The survey and the acceleration idea for BigSubs/RL View may survive such a revision, but as stated the central claim overreaches.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":27968,"tokens_out":13301,"duration_ms":130915,"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":[{"comment":"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.","section":"6.2 (Theorem 2, Algorithm 2)"},{"comment":"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.","section":"3.6 (Theorem 1)"},{"comment":"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.","section":"7.1 (Challenges and Open Problems)"},{"comment":"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.","section":"6.1-6.2 (BigSubs/RL View acceleration)"}],"minor_comments":[{"comment":"The heading 'Multi-Query Optmization' contains a typo; it should read 'Optimization'.","section":"3.1"},{"comment":"The text contains the duplicated phrase 'Executing a workload workload with all possible sets of selected candidates is infeasible'.","section":"3.3"},{"comment":"The heading 'How are contraints modeled?' contains a typo; it should read 'constraints'.","section":"4.3"},{"comment":"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.","section":"4.1 (Example 7)"},{"comment":"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.","section":"6.2 (Algorithm 2)"},{"comment":"The sentence 'the view is not / is selected because without an index its benefit insufficient' appears garbled and should be rewritten.","section":"5.2.1"},{"comment":"In the comment inside Algorithm 1, 'flip f unction' has an erroneous space and should be 'flip function'.","section":"6.1 (Algorithm 1)"}],"recommendation":"major_revision","confidential_remarks":"The survey portion is solid and likely citable on its own. The main risk is that the original algorithmic contribution is overstated: Theorem 2 is not proved for the AND-OR-DAG setting that the paper itself introduces, and the abstract's exponential-acceleration claim depends directly on that theorem. The internal contradiction between Theorem 1 and the open-problems section should be resolved. A revised version that fixes or properly restricts Theorem 2, states the cost model for Theorem 1, and either proves or removes the equivalence claim with the ILP feedback step would be publishable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nFor 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.","headline":"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.","tokens_in":28500,"tokens_out":6640,"would_cite":true,"duration_ms":67472,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A linear tree traversal can replace the exponential optimization step in state-of-the-art view selection algorithms, exponentially accelerating them.","keywords":["multi-query optimization","view selection","index selection","plan caching","candidate selection problem","expression forest","integer programming","tree traversal"],"falsifier":"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.","tokens_in":27418,"feed_emoji":"🌲","tokens_out":2911,"duration_ms":23473,"temperature":0.7,"pith_summary":"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.","feed_headline":"One tree traversal replaces exponential ILP in view selection","feed_subtitle":"A unified candidate-selection framework lets BigSubs and RL View reuse nested candidates in linear time per iteration, exponentially…","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Describes the BigSubs algorithm whose inner ILP step is the target of the acceleration, and whose flip-function iteration Algorithm 1 generalizes.","marker":"[Jindal et al.(2018a)]"},{"why":"Describes the RL View algorithm, the other state-of-the-art approach whose per-iteration ILP step is replaced by the tree traversal.","marker":"[Yuan et al.(2020)]"},{"why":"Supplies the benefit decomposition and the correctness context (OR-DAG/AND-DAG framework) that the recurrence relies on.","marker":"[Gupta et al.(1997)]"},{"why":"Defines the AND/OR-DAG representation frameworks and the known complexity results that locate the VSP and the new polynomial step.","marker":"[Gupta and Mumick(2005)]"},{"why":"The benefit decomposition $B(C)=\\sum_c B'_c\\cdot n_{reuses}(c)$ is the premise that makes the local recurrence valid.","marker":"Equation (1)"}],"fun_headline_variants":["Polynomial fix for exponential view selection","One tree pass replaces ILP in view selection","Reuse nested views in linear time per query","Survey unifies selection, cuts ILP to linear"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial fix for exponential view selection","One tree pass replaces ILP in view selection","Reuse nested views in linear time per query","Survey unifies selection, cuts ILP to linear"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000138,"raw_usage":{"total_tokens":1108,"prompt_tokens":851,"completion_tokens":257,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":467,"completion_tokens_details":{"reasoning_tokens":199}},"tokens_in":467,"tokens_out":257,"duration_ms":3435,"temperature":1.0,"reasoning_tokens":199,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T14:32:54.946699+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}