Feasible Plan Generation with Ambiguity-Boundedness in Cross-Model Query Processing
arXiv:2605.19197v1 [cs.DB] 18 May 2026
Subhasis Dasgupta1[0000−0002−0754−0515] and Amarnath Gupta1[0000−0003−0897−120X] University of California San Diego, La Jolla, CA, USA [email protected], [email protected]
Abstract. Natural language (NL) interfaces to databases broaden access to heterogeneous data but often yield many ambiguous intermediate logical plans (ILPs) due to uncertain operator scope and predicate semantics. Many candidates are infeasible because of type mismatches, missing bindings, or engine-specific constraints. We address this challenge with feasibility constraints for detecting local inconsistencies and introduce the Packed Plan Forest (PPF)—a polynomially bounded structure that compactly encodes all feasible ILPs while pruning infeasible ones early. Extending packed parse forest ideas to multi-model settings, PPF supports efficient feasibility analysis through annotated operators. Formal results show polynomial size under bounded arity and annotation vocabularies, and experiments confirm that PPFs capture exponentially many ILPs with minimal overhead, establishing a scalable foundation for NL-to-DB query planning across heterogeneous systems. Keywords: Query Processing · Heterogeneous Data · Ambiguous Query · Intermediate Logical Plan (ILP).
1
Introduction
Modern analytical infrastructures are shifting toward multi-model, heterogeneously managed data systems, also known as data lakes (e.g., Apache Hudi, Lakehouse, DuckLak), where relational, graph, vector, and spatial layers coexist and interoperate through a unified query interface [2, 16]. These systems power domains such as data , supply-chain traceability, health informatics, and scientific knowledge networks and many more, where users express semantic queries in natural language over multi-engine backends. Traditional NL2DB pipelines [4] typically assume a homogeneous data setting governed by a single logical model, where ambiguity resolution and plan generation are treated as separate stages. In contrast, heterogeneous data ecosystems introduce a deeper coupling between semantic interpretation and execution feasibility. However, a syntactically valid interpretation may prove infeasible in execution due to missing entity bindings, coordinate reference inconsistencies, or
2
S. Dasgupta and A. Gupta
absent vector embeddings across heterogeneous engines. Such interdependence demands joint reasoning over semantics, feasibility, and cost. Running Example: Imagine a Sustainable Supply Chain Intelligence (SSCI) system that traces the lifelines of global production—tracking suppliers, parts, projects, and the web of sustainability documents that bind them—across a constellation of semantically interconnected engines: Relational Data: Suppliers(sid, name, address, docid) Parts(pid, name, category) Projects(projid, name, address) Property Graph: Supplier, Part, Project nodes with edges Supplies(Supplier→Part), UsedIn(Part→Project) Vector Store: Documents(docid, text, embedding) Geospatial: AdminBoundaries(geom, country, crs), geocoding/CRS transforms These components span: (i) a relational engine (e.g., PostgreSQL) for base records, (ii) a graph engine (e.g., Neo4j) for supply relationships, (iii) a vector store (e.g., Qdrant) for sustainability documents, and (iv) spatial services (e.g., PostGIS) for geometries and coordinate transforms. With a natural language interface, a user may pose: “Find suppliers of parts used in projects in Germany with documents discussing sustainability.” NL-to-DB systems [11, 14, 1, 7] typically generate multiple candidate logical forms (intermediate logical plans, ILPs), which are then ranked or pruned. In a heterogeneous setting, however, many of these candidate ILPs are infeasible due to type inconsistencies, unbound entities, coordinate reference misalignments, or missing vector embeddings. Importantly, semantic ambiguity and planning variation are intertwined operator placement and annotation choices jointly determine feasibility. Thus, it becomes necessary to eliminate infeasible branches at an early stage while still retaining all viable interpretations. How can we compactly represent this large space of candidate query plans, enforce heterogeneous feasibility constraints early, and efficiently decide whether any feasible execution plan exists? We address this challenge with the Packed Plan Forest (PPF), a compact representation inspired by parse forests in NLP and AND–OR DAGs in query optimization. The PPF collapses exponentially many ILPs into polynomial space by sharing common subplans across relational, graph, spatial, and vector operators. Feasibility is defined via local constraints on types, bindings, CRS alignment, engine placement, and uncertainty. A bottom-up labeling algorithm checks feasi-
Title Suppressed Due to Excessive Length
3
bility or diagnoses infeasibility in polynomial time. In summary, this work makes the following key contributions: 1. An annotated-operator framework for heterogeneous feasibility constraints (types, bindings, CRS, engine placement, uncertainty) across relational, graph, vector, and spatial models. 2. An algorithmic framework that bridges natural language ambiguity and systematically generates candidate intermediate logical plans across heterogeneous data models, including relational, graph, vector, and spatial systems. 3. The Packed Plan Forest (PPF): a polynomial-space structure that compactly encodes all feasible ILPs via shared subplans and early infeasibility pruning. 4. Formal polynomial bounds on the PPF size and feasibility-checking complexity, with experimental evidence of near-linear scaling and exponential compression. We next survey related work on feasibility reasoning in polystores, compact plan representations, and NL interfaces.
2
Related Work
The problem of joint reasoning over ambiguity and feasibility in heterogeneous query planning spans three research areas. Feasibility in polystores. Early work (Information Manifold, TSIMMIS [10, 8]) formalized the answerability of the query under source bindings as logical dependencies. Benedikt et al. [3] treated execution as constraint satisfaction over functional dependencies. BigDAWG [13], AWESOME [5], and CloudMdsQL[9] extend this to multi-model settings but lack formal infeasibility witnesses. Our approach makes feasibility declarative: local annotations capture types, bindings, CRS alignment, and engine placement, and failures yield structured certificates. Compact plan representations. Volcano/Cascades [6] use memo structures and AND-OR DAGs to share equivalent subplans. Packed parse forests [?] adapt this to NLP ambiguity. PPF extends these to multi-model settings: annotated operator nodes and feasibility-constraint edges give PPF a dual role as both a memoization structure and a symbolic encoding of the constraint space (Section 3). NL interfaces and ambiguity. Handling multiple interpretations of user intent has been a persistent theme in NLIDB research, which enumerates alternative logical forms and uses interaction to resolve scope [12]. Probabilistic and neural text-to-SQL systems [17, 15] replace rule-based enumeration with ranking over candidate SQL programs. However, they target homogeneous schemas and treat feasibility as type consistency. Our work extends the ambiguity to the operator-model and engine-placement choices, making feasibility integral to plan generation.
3
Intermediate Logical Plans
Classical logical plans built on a single algebra are inadequate for our setting, while Natural language (NL) queries over heterogeneous data involve operators
4
S. Dasgupta and A. Gupta
Table 1: Operator families for Intermediate Logical Plans (ILPs). Notation: R=rel, V =nodes, E=edges, P =paths, D=docs, G=geom. Op
Sig.
Brief Description
σθ πA R1 ▷◁θ R2 γA,f
R→R R→R R2 → R R→R
Filter tuples by θ. Project attrs A. Join on θ. Group by A, agg. f .
Relational
Graph Traverse via edges E. Match pattern π. Text / Vector κT D→D Keyword filter T . ϕE D→D Full-text / ranked expr. νqk D→D Top-k similar to q. ςq D2 → R Pair docs by sim. thresh. Spatial / GIS S σϕ G→G Select geom. by ϕ. 2 G1 ▷◁S Spatial join. ϕ G2 G → G ρCRS G →G Reproject CRS. c→c′ κS G→G k-NN query. nn Semantic / LLM ηtype D→R Extract entities. ρtype D→E Extract relations. χlabel D→R Classify docs. LLM ςtask D→D LLM enrich (embed/sum). Cross-Model ξR→V R→V Tuples→graph. ξV →R (V, E) → R Graph→table. ξR→D R→D Add text/embeds. ξD→R D→R Sim. join / IDs. ξR→G R→G Geocode addr. ξG→R G→R Extract coords. τE µπ
V →V V →P
from multiple models. Their feasibility depends on constraints not expressible in relational signatures alone. We therefore introduce the Intermediate Logical Plan (ILP) as a unifying representation. ILPs generalize logical plans in two ways: (i) they draw operators from relational, graph vector, spatial, and semantic domains, linked by explicit cross-model casts, and (ii) they carry annotations recording typing, bindings, coordinate systems, placement, uncertainty, and semantic tags. ILPs form the algebraic objects over which we reason about feasibility (Section 3.4) and construct compact representations (Section 4).
3.1
Operator Algebra
An ILP is an expression over a family of typed operators. Each operator has a signature o : (I1 , . . . , Im ) → (O1 , . . . , On ), where inputs Ij and outputs Oℓ are typed objects such as, relations, graph nodes/edges, paths, documents, embeddings or geometries. ILPs are composed into directed acyclic graphs (DAGs) where nodes are operators, and edges represent typed data flow.
Title Suppressed Due to Excessive Length
5
Relational: σ, π, ▷◁, γ for selection, projection, joins, aggregation. Graph: τ for traversals and µ for path/pattern matching. Vector/Text: κ, ϕ, ν, ς for keyword search, full-text, k-NN embedding search, and similarity joins. Spatial/GIS: σ S , ▷◁S , ρCRS for spatial filters, joins, and CRS reprojections. Cross-model: ξ operators (e.g., ξD→R , ξR→G ) provide bridges across domains. Semantic/LLM: optional enrichment operators (η, ρ, χ, ς LLM ) extend the algebra without changing core feasibility analysis. Cross-model operators are especially critical. For example, ξR→V casts relational tuples into graph nodes, while ξR→G geocodes addresses into geometries. Without such operators, ILPs remain confined to a single model, and feasibility analysis would be trivial. Example 1. “List projects that use parts supplied by companies with documents similar to the sustainability report.” πprojid, name ▷◁ / τUsedIn
\ P rojects
τSupplies ξD→R νqksust (Docs) The ILP retrieves sustainability-related documents with νqksust , maps them back to suppliers using ξD→R , traverses the supply chain through τSupplies and τUsedIn , and finally joins with the Projects relation. Annotations drive feasibility at each step: schema metadata declares that ξD→R must resolve docid to sid, the system catalog places ν k in Qdrant and τ operators in Neo4j, and the operator template propagates the ϵ-approximate semantics of ν k so that joins expecting deterministic identifiers remain valid. If the catalog mapping docid 7→ sid is missing, or if Qdrant does not support the required embedding index, infeasibility is reported with a certificate. Otherwise, the plan is retained for further packing and optimization. Example 2. “Which suppliers connected to projects in Europe have documents similar to the EU sustainability guidelines?”
6
S. Dasgupta and A. Gupta
πsid, name ▷◁ ▷◁
ξD→R S σwithin(Europe)
▷◁ τSupplies (Suppliers)
τUsedIn (P arts)
νqkEU (Docs)
ξR→G (P roject)
The ILP first retrieves EU-related documents via νqkEU , casts matches to supplier/project IDs with ξD→R , traverses the supply chain in the graph (τSupplies , S τUsedIn ), and filters projects spatially after geocoding (ξR→G followed by σwithin ). Feasibility follows from the three annotation sources: (a). schema metadata expose and repair CRS misalignment (details in section 3.2) (b). the system catalog binds each operator to a supporting engine, and (c). the operator template ensures that ϵ-approximate semantics from ν k are propagated safely through ξD→R and downstream joins. If any offaile cTheks fails, the plan is rejected with a localized witness; otherwise, the plan remains in the candidate set for packing (Section 4) and cost-based selection. Example 3. “List suppliers that provide components to projects whose funding documents are semantically similar to EU policy guidelines, and whose project timelines overlap with FY2024.” πsid, name ▷◁
▷◁ ξD→R
▷◁
T σoverlap(FY2024)
τUsedIn (P arts)
ξR→T (P rojects)
τSupplies (Suppliers)
νqkEU (F undingDocs) This ILP combines vector similarity, graph traversals, and temporal filters. The operator νqkEU retrieves funding documents aligned with EU policy embeddings; annotations here come from operator templates (error bounds and embedding domain) and catalog entries (engine = Qdrant). The cross-model operator ξD→R maps document identifiers back to suppliers, requiring schema metadata that de-
Title Suppressed Due to Excessive Length
7
fines the docid 7→ sid mapping. The graph traversals τSupp and τUsedIn consume suppliers and parts, annotated with node and edge types from the schema and placement in the Neo4j engine. Finally, ξR→T (P roj) produces temporal intervals, T with schema metadata providing date domains, and the operator σoverlap(FY2024) applies a fiscal-year filter whose semantics are drawn from the operator template. Feasibility depends on consistent alignment across these domains: (i) whether the embeddings for funding documents are tagged as compatible with EU policy guidelines, (ii) whether temporal annotations calendar vs. fiscal align or require normalization, and (iii) whether the catalog confirms that each operator is supported on its designated engine. If any of these checks fail, infeasibility certificates isolate the violation (e.g., embedding domain mismatch or fiscal vs. calendar misalignment); otherwise, the plan is retained as a feasible candidate. 3.2
Annotations
Besides the operators, metadata annotations of the nodes are a key factor in determining feasibility. We therefore enrich each node with an annotation vector α(o) capturing. Hence, the operator metadata profile is as follows: Type profile: schema, graph label, geometry type Binding status: query inputs bound/unbound Reference system: CRS, temporal granularity, units Placement: Postgres, Neo4j, Qdrant, PostGIS Uncertainty: deterministic or ϵ-bounded Semantic tags: embedding/domain annotations Annotations are populated from three sources: schema metadata (types, CRS), system catalogs (engine placement), and operator templates (uncertainty). Some semantic tags may be derived by lightweight enrichment or user hints. Consider Example 2 where annotations are populated from three distinct sources: Schema metadata: The operator ξR→G (P roj) produces geometries [geom : P oint, crs = EP SG : 4326] , while the Europe polygon is stored as [geom : P oint, crs = EP SG : 3857] A CRS misalignment is detected directly from schema annotations, requiring the insertion of a reprojection operator : ρCRS 4326→3857 . S System catalogs: The join operator ▷◁ and the spatial filter σwithin must be mapped to execution engines that support them. The catalog records that σ S is admissible only in PostGIS, while τSupplies and τUsedIn require Neo4j. This ensures distribution constraints are enforced during planning.
Operator templates: The vector similarity operator νqkEU is annotated with an ϵ-approximate uncertainty profile by template. The downstream cross-model operator ξD→R checks that approximate identifiers can be propagated safely, preserving error bounds in subsequent joins. Some operators expose continuous parameters (e.g., vector similarity thresholds, spatial distances, or temporal overlap tolerances). In such cases, annota-
8
S. Dasgupta and A. Gupta
tion domains can be discretized into a finite representative set following established practices in query optimizers, spatial indexing, and approximate nearestneighbor search. Thresholds may be rounded into system-defined bins, distance predicates mapped to index-specific radii, and embedding similarity cutoffs approximated using quantized score intervals. This abstraction preserves the finiteness assumption required for polynomial feasibility checking, while aligning with real-world execution semantics. 3.3
Candidate ILPs and Attachments
A natural language query seldom maps to a single ILP. Instead, parsers produce families of candidates differing in where predicates attach, how they are interpreted, and which operators are chosen. Attachment: We define attachment as the locus in the ILP where a predicate from the NL query is bound. For instance, “documents similar to the sustainability report” may attach to the Supplier relation (supplier-level documents) or to Projects (project-level documents). Each attachment yields a different ILP structure. Sources of multiplicity: Source multiplicity arises from the scope and interpretation of source predicates under semantic mappings. Such mappings may involve value transformations (e.g., normalization or scaling), reinterpretation of predicate semantics, or alternative operator realizations. Consequently, multiplicity manifests along several dimensions: (i) attachment scope, where data may be associated with different entities (e.g., supplier- vs. project-level documents); (ii) predicate interpretation, where a condition such as “in Europe” may be realized via a spatial join, a country-level filter, or a nearest-neighbor approximation; and (iii) operator alternatives, where semantic intent (e.g., “sustainability”) may be evaluated using keyword-based retrieval or vector similarity. These dimensions collectively expand the space of valid execution plans. The ILP algebra and annotations jointly enable us to represent, compare, and filter candidate plans. Ambiguity arises from attachment, predicate semantics, and operator choice. Feasibility analysis (next section) builds directly on these annotations. 3.4
Infeasible Plans and Certificates
Candidate ILPs generated from NL queries often include plans that cannot be executed because one or more constraint families from Section 4.2 are violated. We model infeasibility as a constraint satisfaction problem (CSP) over operator annotations, and we provide infeasibility certificates 1 as verifiable explanations of failure. 1
We use the term certificate in the complexity-theoretic sense of a verifiable witness: a minimal explanation of infeasibility that can be checked in polynomial time. In the database literature, analogous notions are often referred to as “diagnostics” or “witnesses.”
Title Suppressed Due to Excessive Length
9
Witnesses: We use the term witness to denote the local evidence trace π extracted from operator annotations that shows why a particular constraint failed (e.g., CRS mismatch, type incompatibility, or missing binding). A witness is the atomic unit of evidence, typically expressed as a tuple of conflicting annotation values. Witnesses are attached incrementally during plan construction or pruning. Certificates: An infeasibility certificate aggregates witnesses into a structured tuple: C = (P ′ , o, C, π), where P ′ ⊆ P is the minimal subplan exhibiting the violation, o is the operator at which infeasibility manifests, C ∈ F is the violated constraint family, and π is the witness. Minimality means that no proper subplan of P ′ is infeasible with respect to C. Thus, certificates formalize infeasibility by pairing a violating operator and constraint with its local evidence trace. Now let’s see what this means for the examples we looked at earlier: Type incompatibility. In Example 1 (sustainability report), ξD→R expects a mapping docid 7→ sid. If the catalog lacks this mapping, the witness is π = {docid ̸7→ sid}. The certificate is ({Supplier, Documents, ξD→R }, ξD→R , TYPE, π). Semantic misalignment. In Example 2 (EU guidelines), supplier nodes in the graph are typed Company, while the edge pattern expects Organization. The witness is π = {Company ̸⊆ Organization}. The certificate is ({Suppliers, τSupplies }, τSupplies , ALIGN, π). Binding failure. In Example 2, if νqkEU is unbound, the witness is π = {qEU missing}, yielding the certificate (νqkEU , νqkEU , BOUND, π). Composite failure. In Example 3 (funding timelines), two independent witnesses arise: π1 = {embedding domains mismatch} and π2 = {FiscalQ ̸= CalendarW}. These form two certificates, one for semantic tags and one for temporal alignment. Minimality and locality. Certificates are localized: they identify the smallest subplan and operator responsible, and the witness provides the exact evidence trace. This supports incremental pruning: during plan generation, as soon as a partial ILP produces a witness, that branch can be pruned. Minimality ensures non-redundancy: removing any operator from P ′ eliminates the violation. Complexity. Since constraints are local predicates over operator annotations and their adjacencies, infeasibility checking is polynomial in |O|+|E|. Certificate generation scales linearly with the number of operators, because witnesses are recorded as constant-size evidence traces. This tractability underpins the packed representation of Section 5. Role in planning. Certificates, built from witnesses, serve two roles. First, they prune infeasible ILPs early, avoiding wasted optimization effort. Second, they provide diagnostic feedback. For Example 2, the system may report: “Traversal infeasible: Supplier nodes typed as Company, but edge WorksOn expects Organization”. Unlike traditional query optimizers that reject invalid queries silently, certificates provide verifiable and human-readable explanations of why a plan cannot execute.
10
4
S. Dasgupta and A. Gupta
Plan Generation and Validation: Packed Plan Forest Algorithm & Feasibility Checking Algorithm
The previous section established how feasibility can be determined locally via annotations on operators. However, natural language queries usually generate not a single ILP but a combinatorially large set of candidate ILPs, often growing exponentially with the length of the query. As a result, listing each ILP one by one is impractical. The Packed Plan Forest (PPF) is our compact representation of this candidate space. It encodes all feasible ILPs in polynomial space by sharing equivalent subplans and pruning infeasible ones early. Consider a collection of candidate ILPs {P1 , . . . , Pm }. A straightforward encoding would list each plan as its own DAG. When each of the n predicates in the query has k possible operator choices, the total number of plans is m = O(k n ). The PPF prevents this combinatorial explosion by merging equivalent subplans: any sub-DAGs that use the same operator symbols and have compatible annotations are represented only once in the PPF and are shared among all derivations. The PPF combines ideas from memoization structures in query optimizers and packed parse forests in NLP. Like an AND–OR DAG, it represents multiple derivations compactly by factoring common subexpressions. Like a parse forest, it stores multiple syntactic alternatives in shared nodes. Our extension is to incorporate annotated operators and feasibility constraints across heterogeneous models. This means that merging is annotation-sensitive: operators are shared only if their annotation vectors (types, CRS, uncertainty, engine placement, semantic tags) are jointly feasible. Definition 1 (Packed Plan Forest). Given a query Q, the Packed Plan Forest (PPF) is a triple P = (N, E, ≡), where N is a set of nodes, each corresponding to an operator o with an equivalence class of annotations α(o) that are jointly feasible; E ⊆ N × N is a set of directed edges such that (n1 , n2 ) ∈ E iff the output of n1 can feed the input of n2 and all constraints in Section 3.2 are satisfied; and ≡ is an equivalence relation that identifies nodes representing the same operator semantics and compatible annotations, regardless of upstream derivations. 4.1
Construction Algorithm
The PPF is built incrementally from the set of candidate ILPs or from an incremental NL parse. Algorithm 1 outlines the construction. Construction of the Packed Plan Forest (PPF) from a set of candidate Intermediate Logical Plans (ILPs). The algorithm iteratively computes annotation vectors, applies local feasibility checks, and merges equivalent annotated operators via hash-consing to build a compact AND–OR representation. Infeasible branches are pruned early, and the resulting forest P = (N, E, ≡) encodes all feasible ILPs in polynomial space. The procedure uses the constraint families of Section 3.2 as an oracle for early pruning: infeasible operators never enter the forest. The lookup-or-create
Title Suppressed Due to Excessive Length
11
Require: {P1 , . . . , Pm } Ensure: P = (N, E, ≡) 1: N, E ← ∅ 2: for each plan Pi do 3: for each operator o ∈ Pi do 4: α ← α(o) 5: if feasible(o, α) then 6: n ← lookup-or-create(o, α, N, ≡) 7: add n to N and connect to compatible predecessors in E 8: else 9: prune branch and record witness 10: end if 11: end for 12: end for 13: return (N, E, ≡)
Algorithm 1: PPF construction from candidate ILPs. Require: P = (N, E, ≡), constraints F Ensure: L(n) for all n ∈ N 1: L(n) ← Λ(n) ∀n 2: repeat 3: for n ∈ N (rev. topo) do 4: L(n) ← {λ ∈ L(n) | ∀(m, n) ∈ E, ∃µ ∈ L(m) : F (µ, λ)} 5: end for 6: until fixed point 7: return {L(n)}
Algorithm 2: PPF feasibility labeling.
routine ensures that semantically equivalent subplans are shared, but only if their annotations are compatible. For instance, two vector similarity nodes using different embedding domains (EUguidelines vs.FundingDocs) remain distinct, while two variants differing only in placement (e.g., both supported by Qdrant) can merge. Complexity analysis: Let Q be a query with n predicates, each yielding at most k operator candidates. Let |A| denote the size of the annotation vocabulary (types, CRS codes, semantic tags, etc.). Algorithm 1 processes each candidate operator once, computing its annotation vector and performing feasibility checks. Since feasibility constraints are local predicates, each check runs in O(1) time relative to the size of the annotation vector. Node lookup-or-create is performed via hash-consing and can be implemented in O(1) expected time. Thus the cost of PPF construction is O(n · k · |A|). For generating nodes, plus O(n · k · d · |A|2 ), and for connecting edges, where d is the maximum operator arity. Both terms are polynomial in n and |A|, even though the PPF encodes up to O(k n ) distinct ILPs. This formalizes the claim that infeasibility detection and plan packing are tractable. Polynomial Boundedness:Size of PPF: Let Q be a query with n predicates. Suppose each predicate admits at most k operator choices, each operator has arity at most d, and the annotation vocabulary A has size |A|. Then the size of the PPF is bounded by : |N | ≤ O(n · k · |A|), |E| ≤ O(n · k · d · |A|2 ). Feasibility Checking Algorithm (over PPF): The PPF provides a compact representation of all possible ILP formulations. Feasibility can be determined directly on this structure using a bottom-up labeling procedure that operates in
12
S. Dasgupta and A. Gupta
Table 2: Packed Plan Forest Evaluation. Abbrev.: #P = candidate plans; N = avg. nodes per plan; UniqA = unique nodes (no pruning); UniqF = unique feasible nodes; PkA = packing ratio (pre-prune); PkF = packing ratio (postprune); PrU = pruned unique nodes; tms = runtime (ms) with pruning; MemK = peak memory (KB).
Scen
#P
N UniqA UniqF PkA PkF
S1 S2 S3 S4 S5 S6
100 100 100 100 100 1000
25 25 25 25 25 50
2290 2359 2208 2400 2389 25882
1690 1749 1656 693 1755 16600
0.92 0.94 0.88 0.96 0.96 0.52
PrU
tms MemK
0.68 600 27.5 0.70 610 43.2 0.66 552 24.2 0.28 1707 21.3 0.70 634 25.8 0.33 9282 808.5
6301 6409 6310 2708 6366 84961
polynomial time and, when no valid plan is present, yields formal certificates of infeasibility. Labeling Algorithm: Each node n ∈ N receives a feasibility label set L(n) ⊆ Λ(n) of annotation configurations for which n can participate in a feasible ILP. Algorithm 2 propagates these labels bottom-up, pruning configurations inconsistent with any predecessor; sink nodes with L(n) = ∅ certify infeasibility. Polynomial feasibility checking : Let P = (N, E, ≡) be a PPF with |N | nodes, maximum operator arity d, and per-node annotation domain size K. Then Algorithm 2 decides feasibility in time O(|N | · K d ). This is crucial for determining plan space, even though the PPF can represent an exponential number of ILPs, feasibility can still be checked efficiently. Upon termination, every sink node maintains a nonempty label set; consequently, the PPF represents only consistent ILPs, while infeasibility witnesses are associated with discarded annotations. Infeasibility Certificates: Whenever a label λ ∈ L(n) is pruned, the algorithm records a witness explanations (e.g., “Embedding domain mismatch”, “Temporal granularity mismatch”) bridging structural feasibility and diagnostic feedback. Tractability holds under bounded arity, finite annotation domains, and localonly constraints; extending to global constraints requires SAT/SMT reasoning.
5
Experimental Evaluation
We evaluated PPF construction (Algorithm 1) on six synthetic scenarios varying in structural overlap (ρs ), feasibility ratio (ρf ), and engine diversity (ρe ), measuring redundancy reduction, pruning efficiency, and witness correctness. In Table 2 Each scenario models a specific operational condition under which the algorithm is expected to perform differently. Together, they capture realistic workloads encountered during federated query optimization and planning for heterogeneous systems. The overall goal is to measure how efficiently the
Title Suppressed Due to Excessive Length
(a)
(b)
(c)
(d)
(e)
(f)
13
Fig. 1: Performance metrics across multiple parameters. Each subplot shows pairwise correlation (r)
between key variables. (a) pruned vs. feasible nodes, (b) runtime vs. feasible nodes, (c) throughput vs. total unique nodes, (d) runtime vs. total unique nodes, (e) feasible vs. total unique nodes, (f) runtime vs. total nodes.
algorithm can (a) reduce redundancy through node packing, (b) prune infeasible branches early, and (c) maintain correctness through witness tracking. Below we summarize the six scenarios that were used to generate the workloads for the experiments presented in Table 2. Experimental Methodology and Analysis: Fig. 1 confirms near-linear scaling: unique_feasible and pruned_unique strongly predict runtime (|r|>0.7); packed_ratio improves with diversity before plateauing. Together, unique_feasible, unique_all, and total_nodes guide pruning and scheduling. PPF compresses candidate plans by 4.2–11.7×; feasibility pruning removes 21–63% of alternatives in 7.1–24.6 ms per query, confirming its role as a practical front-end for NL-driven heterogeneous query processing. Baseline Comparison : To contextualize the benefits of the PPF, we compare against two baselines that represent common approaches to handling multiple candidate plans in multimodel systems. Baseline A: Naïve Enumeration. The naïve strategy constructs each ILP
14
S. Dasgupta and A. Gupta
Table 3: Comparison to baseline memoization without annotations. Query Memo merges Incorrect merges (%) Q1 18 33% Q2 21 38% Q3 26 46% Q4 11 28% Q5 23 41%
independently and evaluates feasibility only at execution time. Given n predicates with k alternatives per predicate, this produces O(k n ) candidate ILPs. In Example 3, eight ILPs contain more than 40 total operators, whereas the PPF contains only nine distinct nodes. Across the NL workload in Table 3, naïve enumeration produced between 150 and 870 total operator instances per query, whereas the PPF reduced this to 5–12 nodes. Baseline B: Memoization Without Annotations. A second baseline is a Volcano-style memo structure that merges operators based solely on their symbol and schema-level signature. This approach incorrectly merges nodes that are semantically incompatible (e.g., vector similarity computed over different embedding domains), leading to false feasible plans and delayed runtime failures. To quantify this effect, we disabled annotation-aware merging in our PPF implementation. Table 3 reports the number of “incorrect merges” (i.e., merges undone later by infeasibility checks). Between 28% and 46% of merged nodes in the annotation-agnostic memo were invalid, demonstrating that annotationsensitive feasibility reasoning is necessary for correctness. Together, these comparisons show that annotation-aware feasibility is crucial: PPF cuts plan sizes by up to 11×, while memo structures without annotations yield 28–46% incorrect merges.
6
Discussion and Conclusion:
We presented the Packed Plan Forest (PPF), a polynomially bounded structure that compactly encodes all feasible ILPs across heterogeneous query engines, supporting efficient feasibility checking via a bottom-up labeling algorithm. Experiments confirm polynomial scaling and exponential compression ratios. The PPF acts as a feasibility filter that precedes traditional rule-based or cost-based optimization. Once feasibility labeling completes, the remaining annotation configurations form a constraint-consistent search space that can be passed directly into a polystore cost-based optimizer (which is outside our scope). Feasibility certificates can further guide optimization by identifying operators that are infeasible for certain engines, suggesting early placement-based pruning.
Title Suppressed Due to Excessive Length
15
References 1. Affolter, K., Stockinger, K., Bernstein, A.: A survey of natural language interfaces to databases. VLDB Journal 28(5), 709–751 (2019). https://doi.org/10.1007/s00778-019-00557-9 2. Barret, N., Ebel, S., Galizzi, T., Manolescu, I., Mohanty, M.: User-friendly exploration of highly heterogeneous data lakes. In: International Conference on Cooperative Information Systems. pp. 488–496. Springer (2023) 3. Benedikt, M., Konstantinou, N., Ley-Wild, R., Murlak, F., Vrgoc, D.: Querying with access patterns and integrity constraints. In: Proceedings of the 20th International Conference on Extending Database Technology (EDBT). pp. 231–242 (2017) 4. Dar, H.S., Lali, M.I., Din, M.U., Malik, K.M., Bukhari, S.A.C.: Frameworks for querying databases using natural language: a literature review. arXiv preprint arXiv:1909.01822 (2019) 5. Dasgupta, S., Coakley, K., Gupta, A.: Analytics-driven data ingestion and derivation in the awesome polystore. In: 2016 IEEE International Conference on Big Data (Big Data). pp. 2555–2564. IEEE (2016) 6. Graefe, G., McKenna, W.J.: The volcano optimizer generator: Extensibility and efficient search. Proceedings of ICDE pp. 209–218 (1993) 7. Guo, J., Zhan, Z., Gao, Y., Xiao, Y., Lou, J.G., Liu, T., Zhang, D.: Towards complex text-to-SQL in cross-domain databases. In: Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (ACL). pp. 4524–4535. ACL (2019). https://doi.org/10.18653/v1/P19-1443, https://aclanthology.org/P19-1443 8. Halevy, A.Y.: Answering queries using views: A survey. VLDB Journal 10(4), 270– 294 (2001) 9. Kolev, B., Bondiombouy, C., Valduriez, P., Jiménez-Peris, R., Pau, R., Pereira, J.: The cloudmdsql multistore system. In: Proceedings of the 2016 International Conference on Management of Data. pp. 2113–2116 (2016) 10. Levy, A.Y., Rajaraman, A., Ordille, J.J.: Answering queries using views: A survey. VLDB Journal 10(4), 270–294 (1996) 11. Li, F., Jagadish, H.V.: Constructing an interactive natural language interface for relational databases. Proceedings of the VLDB Endowment 8(1), 73–84 (2014). https://doi.org/10.14778/2735461.2735468 12. Li, F., Jagadish, H.: Constructing natural language interfaces to databases. In: Proceedings of the VLDB Endowment. vol. 8, pp. 73–84 (2014) 13. Stonebraker, M., Balazinska, M., Cetintemel, U., Cherniack, M., Zdonik, S.: Bigdawg: A polystore system for analytics on heterogeneous data. Proceedings of the VLDB Endowment 11(7), 819–831 (2018) 14. Yaghmazadeh, N., Wang, Y., Dillig, I., Dillig, T.: SQLizer: Query synthesis from natural language. In: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL). pp. 63–76. ACM (2017). https://doi.org/10.1145/3009837.3009879 15. Yaghmazadeh, N., Wang, Y., Dillig, I., Dillig, T.: Sqlizer: query synthesis from natural language. In: Proceedings of POPL. pp. 63–79 (2017) 16. Yuan, Q., Yuan, Y., Wen, Z., Wang, H., Tang, S.: An effective framework for enhancing query answering in a heterogeneous data lake. In: Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 770–780 (2023) 17. Zhong, V., Xiong, C., Socher, R.: Seq2sql: Generating structured queries from natural language using reinforcement learning. In: Proceedings of ACL (2017)