Navigating Runtime Dynamism in Semantic Query Serving

Navigating Runtime Dynamism in Semantic Query Serving Hengrui Zhang

Tsinghua University Beijing, China zhanghen22@mails.tsinghua.edu.cn

arXiv:2611.04248v1 [cs.DB] 3 Nov 2026

ABSTRACT LLM-powered semantic queries increasingly combine relational processing with multiple LLM-based operators over unstructured data. Efficiently serving such queries is challenging due to runtime dynamism at two coupled levels. Across queries, dynamic arrivals and heterogeneous resource demands continuously change scheduling priorities. Within a query, heterogeneous characteristics across fine-grained input batches cause operator costs and selectivities to vary throughout execution, making a statically optimized plan unreliable. These two forms of dynamism create a circular dependency: inter-query scheduling requires estimates of remaining LLM work, while the remaining work depends on runtime plan choices whose costs become observable only during execution. We present SeqoFlow, a runtime framework that jointly adapts query plans and schedules concurrent semantic queries. SeqoFlow enumerates equivalence-preserving plan alternatives under operator dependencies and decomposes queries into fine-grained units, enabling safe plan adaptation and query preemption at batch boundaries. To support both decisions without exhaustively profiling candidate plans on the target LLM, SeqoFlow uses lightweight speculative estimation to capture runtime costs. These estimates jointly guide plan adaptation and inter-query scheduling, closing the loop between query optimization and LLM inference. Experiments across diverse query structures, data distributions, and arrival rates show that SeqoFlow substantially reduces end-to-end latency compared to existing semantic query systems, adaptive query processing techniques, and conventional scheduling policies.

Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/Seurgul/SeqoFlow/tree/main.

1

INTRODUCTION

LLM-powered data analytics has emerged as a new paradigm, attracting growing interest from both academia and industry [3, 4, 6, 24, 36, 37, 43]. By incorporating LLM-powered semantic operators into analytical queries, these systems allow users to express ad hoc intents such as semantic filtering, information extraction, entity matching, ranking, and summarization. Modern data platforms are consequently evolving from monolithic query engines into hybrid systems that tightly couple relational query execution with GPU-backed LLM inference. Efficiently serving concurrent semantic queries, however, is complicated by pervasive runtime dynamism at two levels. At the inter-query level, online query arrivals, completions, and heterogeneous LLM demands continuously alter which query should

Xupeng Miao

Peking University Beijing, China xupeng.miao@pku.edu.cn be served next. At the intra-query level, heterogeneous characteristics across fine-grained input batches, together with contentdependent model behavior, cause operator costs and selectivities to vary throughout query execution. For example, the following semantic query assesses antibiotic usage in infectious diseases among Asian pediatric departments by combining two medical research paper datasets [17]. At runtime, the selectivity of natural-language predicates can vary substantially, making downstream cost estimation unreliable. Moreover, several operators consume outputs generated by upstream LLM operators, introducing cost correlations that are difficult to predict and detect. Executing such queries with a fixed run-to-completion plan can therefore lead to suboptimal latency and unnecessarily delay other concurrent queries sharing the same LLM inference resources. SELECT t2.antibio FROM (SELECT fulltext_1 FROM table_1 WHERE sem_filter('{affiliations_1} is an Asian institution.') AND sem_filter('{abstract_1} comes from Pediatrics.')) t1 sem_join (SELECT sem_map('Assess antibiotic use in {drugs_2}') antibio, sem_map('List the drugs studied in {abstract_2}') drugs_2 FROM table_2 WHERE sem_filter('{abstract_2} studies infectious diseases.')) t2 ON '{drugs_2} is studied in {fulltext_1}';

Crucially, these two forms of runtime dynamism cannot be addressed independently. Inter-query scheduling requires an estimate of each active query’s remaining LLM work. Existing query scheduling techniques typically assume that query execution costs can be estimated or provided before execution and optimize scheduling decisions based on such information [22]. However, the remaining work of a semantic query depends on the execution plan selected for its unprocessed input batches. Changing the order or placement of semantic operators may substantially alter intermediate cardinalities and the number and token volume of subsequent LLM invocations. Selecting an efficient plan, in turn, requires operator costs and selectivities that are difficult to predict accurately using static statistics and may become observable only during execution. A runtime plan change therefore revises the query’s remainingwork estimate and may alter its scheduling priority relative to other active queries. Subsequent execution exposes new runtime observations that may trigger further plan and scheduling decisions. This creates a circular dependency among runtime observation, intraquery plan adaptation, remaining-work estimation, and inter-query scheduling. Existing techniques address individual parts of this cycle but do not close it end to end. Research on expensive predicates and UDFs studies cost-aware operator placement, while adaptive query processing revises execution decisions using runtime statistics. Recent LLM-powered data systems provide logical and physical optimizations for LLM-powered operators [37, 43, 62]. Separately, database and LLM serving systems support query preemption [22], request scheduling [32], and GPU resource management [25]. However,

query optimizers generally select a plan for each query in isolation, without considering how that choice changes the query’s remaining work relative to other active queries, whereas LLM schedulers treat inference requests or entire queries as scheduling units without reasoning about alternative query plans. Applying these techniques independently leaves the scheduler with stale remaining-work estimates whenever a query plan changes, and drives each query to commit to a plan before its operator costs become observable. In this paper, we argue that navigating runtime dynamism in semantic query serving requires coordinating two individually distinct but mutually dependent decisions: adapting query plans to intra-query data heterogeneity and scheduling concurrent queries under inter-query workload dynamics. This coordination raises two key challenges. C1: Scheduling under Inter-Query Dynamism. As semantic queries arrive, complete, or expose updated estimates of their remaining work, their relative scheduling priorities continuously change. Run-to-completion execution can cause severe head-of-line blocking, whereas scheduling individual LLM requests discards the query structure needed to estimate downstream work. The system therefore needs a scheduling unit that supports timely preemption while retaining sufficient execution context. This raises the first question: How can the system efficiently switch among concurrent semantic queries and schedule them according to dynamically changing estimates of their remaining work? C2: Plan Adaptation under Intra-Query Dynamism. Finegrained input batches within a query may exhibit heterogeneous characteristics and execution behavior, causing operator costs and selectivities to vary throughout execution. A statically selected plan may therefore not remain efficient for every batch. However, runtime adaptation must account for input batches that have already passed through parts of the plan, as well as attribute dependencies, operator semantics, and blocking boundaries. This raises the second question: How can the system safely adapt the execution plan for a query’s remaining input batches while preserving equivalence and operator dependencies? To address these challenges, we present SeqoFlow, a unified runtime framework that jointly adapts query plans and schedules concurrent semantic queries. SeqoFlow constructs equivalencepreserving plan alternatives under explicit operator dependencies and decomposes query execution into batch-level Subquery Execution Units (SEUs). SEUs provide safe boundaries at which SeqoFlow can incorporate runtime statistics, select a compatible plan for the remaining input batches, preempt an active query, and switch to another query without discarding completed work. SeqoFlow coordinates plan adaptation and inter-query scheduling through lightweight speculative profiling. It profiles a representative subquery using a smaller language model, collects operator-level selectivity and token-processing costs, and propagates these statistics across compatible plan alternatives to estimate their remaining execution costs. The same estimates guide the global scheduler in reprioritizing active queries, thereby closing the runtime optimization– scheduling loop without exhaustively profiling every candidate plan on the target LLM. We implement SeqoFlow as an end-toend semantic query serving system integrated with a GPU-based

LLM backend. Experiments across diverse query structures, batchlevel data characteristics, operator dependencies, and arrival rates demonstrate that SeqoFlow substantially reduces end-to-end latency compared with existing semantic query systems, adaptive query processing techniques, and conventional scheduling policies. In summary, this paper makes the following contributions: • We propose SeqoFlow, a unified framework to support efficient serving of semantic queries under runtime dynamism. • We present a runtime adaptation mechanism to capture and select better plans while preserving logical equivalence. • We introduce a fine-grained, structure-aware execution abstraction that exposes safe preemption boundaries and enables dynamic scheduling across concurrent semantic queries.

2 PRELIMINARY AND RELATED WORK 2.1 Optimizing LLM-powered Data Systems Recent data systems (e.g., [37, 43]) increasingly rely on LLMs as the primary workhorse over unstructured data. These systems provide declarative interfaces that allow users to program using semantic operators or more general LLM pipelines [51]. In practice, a semantic query is executed by applying each semantic operator to its input data through one or more LLM calls. Previous work has mainly focused on physical optimization of semantic queries, including accelerating individual operators [26, 27, 43, 47], prompt rewriting [51], and extending the Cascades optimizer [48]. Regarding logical optimizations, [36–38, 53] directly apply rule-based rewrites, such as operator pull-up, while [62] prompt LLMs to perform logical rewrites guided by human-written heuristics. Overall, this literature reflects a shift from treating LLM calls as black-box functions toward principled query models and optimizers for LLM-augmented analytics. Notably, existing approaches optimize individual, shared-nothing workloads in isolation, while production environment faces more limitations from contentions for bounded resources [22, 55], including LLM inference service. A unified abstraction for expressive semantic querying that coordinates query optimization with preemptive, query-level scheduling remains open.

2.2

General Serving and Scheduling

Existing LLM serving systems adopt general-purpose scheduling policies such as FCFS [32] or MLFQ [57], which treat each incoming request as a monolithic unit. Some systems improve scheduling by leveraging techniques like chunked prefill [7], disaggregation [44], preemption [57], migration [52], and output length prediction [45]. While these approaches are effective for homogeneous inference workloads, they do not directly support semantic queries. A semantic query is a structured operator graph whose execution cost depends on operator costs, ordering, and intermediate data sizes. From a scheduling perspective, this introduces two challenges. First, policies such as SRTF require reliable estimates of remaining query time, yet semantic query costs are content-dependent and evolve during execution. Second, request-level schedulers also ignore query progress and plan structure. Effective scheduling must therefore account for both query-level and operator-level costs. 2

2.3

Plan Enumeration

Logical Optimizations in Relational DBMS

Beyond the techniques described in § 2.1, logical query optimization has a rich history, particularly for expensive operators and UDFs that invalidate simple optimization heuristics. Early work [13, 21, 34] studies the cost-based placement of predicates and joins, showing that rules such as eager predicate evaluation can become suboptimal when operator costs are non-negligible. Other work [40, 41] develops dynamic-programming (DP) algorithms that identify optimal partial plans under known cost and selectivity estimates. These approaches provide promising correctness within their respective settings, but rely on predefined operator semantics and sufficiently stable cost information. They therefore do not directly accommodate fluctuating costs, new query language extensions [51, 58], and latent correlations among operators [30, 35, 60]. Another line of work studies adaptive query processing, which revises execution decisions using observations collected at runtime. For example, Eddies [8, 25] are adopted in ML-powered data systems. However, Eddies do not provide a general mechanism for enforcing expressive dependencies among operators, and they require sophisticated implementations and support limited semantics (e.g., blocking operators such as aggregation cannot be easily translated into Eddies’ scheme). Meanwhile, query re-optimization [23, 61] mainly considers adapting to a new plan after partial execution of individual queries by re-running the optimization algorithms. Therefore, it cannot directly address the highly dynamic characteristics in analyzing unstructured data. Our goal is to combine the logical optimization’s equivalence preserving with the runtime responsiveness of adaptive query processing.

Query Scheduling & Execution Scheduler [Batch ID, Plan ID] [0, 1]

[1, 2]

LLM Backend

Query Arrival

[0, 9]

[0, 2]

[1, 4]

[0, 8]

[1, 8]

t

Figure 1: System Architecture – SeqoFlow consists of two stages: A plan enumeration stage that captures equivalent logical plans, and a runtime that schedules and executes batch-level jobs and dynamically selects plan alternatives for batch-level execution.

Despite such volatility, current frameworks fail to exploit the batch-level state granularity that co-optimize all the dimensions. Instead, they treat queries as monolithic tasks bound to a run-tocompletion execution model. This motivates the need for a unified framework capable of dynamically estimating the cost of each transient 𝑠𝑡𝑎𝑡𝑒, unifying both mid-flight query optimization and fine-grained batch-level scheduling.

3.2

System Design

Figure 1 provides a high-level overview of SeqoFlow’s architecture. The framework consists of two primary components: a static preprocessor that enumerates all equivalent physical plans for a given query 𝑞 (§4), and a dynamic execution engine that orchestrates adaptive query processing and inter-query scheduling based on the instantaneous system 𝑠𝑡𝑎𝑡𝑒 (§5). Upon query arrival, the pre-process generates and memoizes a comprehensive search space of equivalent query plans. This allows the runtime engine to rapidly retrieve and evaluate alternative execution strategies without re-parsing the query. During execution, the runtime processes queries in discrete batch-level preemption units. This fine-grained architecture enables the global scheduler to safely context-switch and prioritize queries based on dynamic cost metrics, resolving C1. Simultaneously, to address the intra-query data dynamism in C2, SeqoFlow leverages these units to continuously evaluate the pre-computed search space. By monitoring the current state, SeqoFlow dynamically migrates to the most cost-effective logical plan. The effectiveness of SeqoFlow’s co-design hinges on the ability to accurately estimate costs mid-flight without severely blocking query execution. To bridge this gap, we introduce a novel speculative cost estimation mechanism. By utilizing a lightweight Small Language Model (SLM) to profile transient batch latencies, the system captures real-time costs with high fidelity. This speculative feedback loop continuously guides the decisions in scheduling and plan adaptation with bounded computational overhead.

3 OVERVIEW 3.1 Workload Formulation We consider an online scenario where analytical queries arrive ad hoc at the system frontend. Each query request 𝑞 can be formulated as a set of logical operators comprising both traditional relational operators (e.g., filters, joins) and LLM-based semantic operators. Upon arrival, the frontend queues these requests and dispatches them to a centralized backend execution engine, which then interacts with both structured and unstructured data. Established works that integrate ML/LLM inference within relational data systems [24, 29, 43] as well as production standards [2, 5] fetch and process data in fixed-size batches (i.e., multiple rows/tuples) to improve hardware utilization. Batches naturally discretize continuous query execution into a sequence of measurable states. Formally, we define the execution state at any given moment as 𝑠𝑡𝑎𝑡𝑒 = (𝑞, {𝑜𝑝𝑖 }, 𝐵 𝑗 ), representing the query served 𝑞, the active physical operators {𝑜𝑝𝑖 }, and the current data batch 𝐵 𝑗 . The continuous interplay of these three components creates a dynamic and complex execution landscape. Because the computational cost of semantic operators depends heavily on the semantic content and input distribution of 𝐵 𝑗 , the optimal execution strategy can shift drastically mid-flight. From our observations, a query plan applied to {𝑜𝑝𝑖 } that was optimal for an early batch may become a severe bottleneck for subsequent batches, requiring dynamic plan mutation. Similarly, the execution time of queries 𝑞 fluctuates as batches are processed, demanding dynamic scheduler adjustments.

4

INTRA-QUERY PLAN ENUMERATION

The optimal execution order of semantic operators is not deterministic with simple rule-based heuristics. Execution performance is largely dependent on the physical cost of LLM-centric procedures and data characteristics, which are not known a priori and can vary 3

𝐼𝑛𝑝𝑢𝑡 𝑃𝑙𝑎𝑛

𝑀𝑎𝑥𝑖𝑚𝑎𝑙𝑙𝑦 𝑃𝑟𝑜𝑚𝑜𝑡𝑒𝑑

3

1

2

1

𝑆𝑒𝑡 𝑜𝑝

3

3

through a step-by-step swap between parent and child operators, namely 𝑜𝑝 𝑝𝑎𝑟𝑒𝑛𝑡 and 𝑜𝑝𝑐ℎ𝑖𝑙𝑑 . However, to enforce lossless execution, certain swaps are prohibited as they violate the commutativity rules. Specifically, two rules are considered to determine commutativity: Rule 1: Data Dependency If 𝑜𝑝 𝑝𝑎𝑟𝑒𝑛𝑡 consumes a new attribute produced by 𝑜𝑝𝑐ℎ𝑖𝑙𝑑 , the swap is not allowed as it would raise data dependency error. Rule 2: Semantic Integrity Certain operator commutations fundamentally alter intermediate relations, violating the exact semantic equivalence of the query. For example, pushing a selection predicate upstream of an aggregation prematurely filters rows, resulting in an incomplete aggregate computation. To guarantee correctness in plan transformations, we categorize operators into three distinct classes: row-wise (e.g., filters, projections), set-wise (e.g., aggregations, sorts), and joins. Provided the data dependency constraints of Rule 1 are met, a swap can be applied safely between two consecutive row-wise operators, or a row-wise operator and a join, because these operations evaluate individual rows independently. To prevent semantic corruption, commutations involving any other class combinations are strictly prohibited. It’s noteworthy that the rules are sufficient rather than necessary, as commutations such as pushing a filter on a grouping or sort key also preserve equivalence but lie outside the enumerated space. Such cases are eliminated to simplify the algorithms’ corner cases as it’s hardly profitable to inflate a blocking operator’s massive gathered input in favor of saving cost from a filter. Equivalence Guarantee By strictly following the commutativity rules above, each swap can be considered as an equivalencepreserving operation. An admissible swap changes the order in which operators apply, and hence intermediate cardinalities and cost, but never the output bag. Formally, plans 𝑇 ≡ 𝑇 ′ if they produce the same output bag for every valid input. A row-wise operator 𝜔 = (𝑝, 𝑓 ) applies a predicate 𝑝 and projection 𝑓 : 𝜔 (𝑅) = {{ 𝑓 (𝑡) | 𝑡 ∈ 𝑅, 𝑝 (𝑡) }}. Here 𝑅 is an input bag. Let Rd(𝜔) be the attributes read by 𝑝 or 𝑓 , and Md(𝜔) the attributes created by 𝑓 .

𝑅𝑒𝑎𝑑𝑦

1

1

3

2

2

1

𝑅𝑜𝑤 𝑜𝑝 𝐽𝑜𝑖𝑛 𝑜𝑝 𝐷𝑒𝑝𝑒𝑛𝑑𝑒𝑛𝑐𝑦 𝑃𝑢𝑠ℎ𝑢𝑝 𝐹𝑎𝑖𝑙

2

Figure 2: Operator Pushup Phase. 𝑃𝑢𝑠ℎ𝑑𝑜𝑤𝑛 𝑖𝑛 𝑃! & 𝑃𝑒𝑟𝑚𝑢𝑡𝑒

𝐿𝑎𝑦𝑒𝑟 𝑘

1

3

2

4

𝑆𝑒𝑒𝑑𝑠

𝑃𝑢𝑠ℎ𝑑𝑜𝑤𝑛 𝑎𝑐𝑟𝑜𝑠𝑠 𝑃!

1

…

𝐿𝑎𝑦𝑒𝑟 𝑘 𝐿𝑎𝑦𝑒𝑟 𝑘 + 1

…

4 2

3

…

𝑃𝑢𝑠ℎ𝑑𝑜𝑤𝑛 𝑎𝑙𝑙 𝑃! 𝑖𝑛 𝐿𝑎𝑦𝑒𝑟 𝑘

𝐿𝑎𝑦𝑒𝑟 𝑘 + 1

Figure 3: Operator Pushdown Phase. substantially. This introduces significant challenges for transformation schemes applying the predefined set of rules, as they often fail to capture optimal plans falling outside the static patterns. Unlike prior systems [15, 38, 48, 51] that optimize queries by exploring quality–cost trade-offs, we restrict ourselves to lossless optimization and consider only plan transformations that preserve semantic equivalence1 . In this section, we discuss the algorithms towards an enumeration of equivalent logical plans, enabling the discovery of the best candidate plan structures.

4.1

Problem Formulation

4.1.1 Logical Plans. In prevalent relational query models, a logical plan 𝑇 = {𝑜𝑝} is a directed tree structure. Each node in the tree represents a logical operator 𝑜𝑝 with at most two children, while edges denote the flow of data between operators. Leaf nodes correspond to scan operators over base relations (tables), fetching batches of data into physical processing. The root node produces the final output of the query. Binary operators (join and sem_join) are the only operators with two children, computing the product of two subtree relation2 . Therefore, they serve as anchors to the plan topology space, which defines the unique tree structure and will not be modified during the transformation process when join reordering is not considered.

Lemma 1 (Swap Eqivalence). (i) Two row-wise operators 𝜔 1, 𝜔 2 commute if Rd(𝜔𝑖 ) ∩Md(𝜔 𝑗 ) = ∅ for 𝑖 ≠ 𝑗 and Md(𝜔 1 ) ∩Md(𝜔 2 ) = ∅. (ii) A row-wise operator 𝜔 can move from above 𝑅 ⊲⊳𝜃 𝑆 to the 𝑅 branch if it reads only attributes of 𝑅 and changes no attribute of 𝑆 or any attribute used by the join predicate 𝜃 . The symmetric condition applies to 𝑆. Proof. In case (i), the conditions give 𝑝𝑖 (𝑓 𝑗 (𝑡)) = 𝑝𝑖 (𝑡) for 𝑖 ≠ 𝑗 and 𝑓1 (𝑓2 (𝑡)) = 𝑓2 (𝑓1 (𝑡)) for every row 𝑡. Both orders therefore retain exactly the same rows satisfying 𝑝 1 (𝑡) ∧ 𝑝 2 (𝑡) and map each to 𝑓1 (𝑓2 (𝑡)) = 𝑓2 (𝑓1 (𝑡)). In case (ii), for rows 𝑟 ∈ 𝑅 and 𝑠 ∈ 𝑆, let 𝑟 ◦ 𝑠 concatenate 𝑟 and 𝑠. The conditions give 𝑝 (𝑟 ◦ 𝑠) = 𝑝 (𝑟 ), 𝑓 (𝑟 ◦ 𝑠) = 𝑓 (𝑟 ) ◦ 𝑠, and 𝜃 (𝑓 (𝑟 ) ◦ 𝑠) = 𝜃 (𝑟 ◦ 𝑠), which preserve each joined pair and its output row. □

Definition 1. For each join 𝑗, the source partition 𝑃 + ( 𝑗) consists of 𝑗 and the operators above it up to the next join or the root. The sink partition 𝑃 − ( 𝑗) consists of 𝑗 and the operators below it down to the next joins or scans. A plan without joins forms a single partition. The source and sink partitions act as the unit of transformations in the divide-and-conquer strategy for plan enumeration in §4.2.

By transitivity of 𝑇 ≡ 𝑇 ′ , every plan reachable from the seed plan through a sequence of admissible swaps is equivalent to it, which underpins the correctness of the algorithms in §4.2. The cost of transformations and the size of the plan space are bounded as follows, with proofs in Appendix A. Let 𝑁 be the number of operators and 𝐽 the number of joins. The hook length ℎ 𝐹 (𝑜𝑝) counts 𝑜𝑝 and its descendants in its constructed Hasse graph 𝐹 .

4.1.2 Transformation. The optimizer enumerates equivalent plans by iteratively transforming from a seed plan 𝑇 to a new plan 𝑇 ′ 1 Note that such equivalence is defined with respect to the deterministic semantics of

LLM operator intent, ignoring stochastic variation in LLM outputs. 2While we only discuss binary operators in this paper, the discussion can be extended to any 𝑛 -ary operators without loss of generality.

4

Algorithm 1 Operator Pushup

Proposition 1 (Plan Space). The number of plans reachable through admissible swaps is at most 2 𝐽 ·Î 𝑁ℎ! (𝑜𝑝 ) . 𝑜𝑝

1: Input: Plan 𝑇

𝐹

2: function Pushup(𝑃)

Proposition 2 (MECE). Every plan memoized by Alg. 1 and Alg. 2 is equivalent to the seed plan and stored once. Without pruning, the memoized plans are mutually exclusive and collectively exhaustive (MECE) over the equivalence-preserving closure defined by rules in §4.1.2. With pruning, for every cost setting, they include a plan of minimum cost.

4.2

3: 4: 5: 6: 7: 8:

(𝑃𝑙 , 𝑃𝑟 ) ← GetChildrenSinkPartition(𝑃) Pushup(𝑃𝑙 ) Pushup(𝑃𝑟 ) 𝑃 ′ ← PushupInSinkPartition(𝑃) 𝑇 ′ ← Merge(𝑇 , 𝑃 ′ ) return 𝑇 ′

9: function PushupInSinkPartition(𝑃)

Plan Enumeration

10:

The plan enumeration strategy organizes the generation of different plans by first finding an initial state and then spawning equivalent variants from it recursively. We choose the maximally promoted tree as the initial state. It refers to the topology that all operators cannot be further swapped up with their parents. The process first leverages the Operator Pushup phase to reach this state, which is unique up to the order of commutative operators within each partition, then tries spawning equivalent plans by pushing down operators from the initial state, i.e. the Operator Pushdown phase. The procedure is summarized in Figure 2 and Figure 3. Operator Pushup The goal and intuition of the pushup phase is to promote all row-wise operators to partitions of higher levels until they cannot be promoted anymore. The recursive procedure as present in Algorithm 1 and Figure 2 starts by promoting operators in the bottom-most sink partitions to the top. Each sink partition is a subtree rooted at join operators. The transformation takes each step by selecting a ready operator (denoted active in Alg. 1) from the children branches and swapping it up to above the root, or terminating with a failed swap due to commutativity constraints. This is orchestrated inside subroutine PushupInSinkPartition, determining whether all operators in the current partition can no longer be emitted to the parent partition above. If so, the transformed partition can be safely merged into the original plan (line 7 in Alg. 1), and the parent partition starts emitting its operators upward in the next recursion. Note that pushup mainly operates on partition granularity, and we do not count for the exact order of chained, commutative operators (e.g., the order of operators 2 and 3 in the final state of Figure 2) in the same partition. Different orderings of these chained operators are enumerated in the pushdown phase. The pushup phase is only used to arrive at a starting point for enumerating all admissible plans later. Therefore, no intermediate state needs to be cached. Operator Pushdown After the pushup phase, we enumerate the full transitive set under Rules 1 and 2’s equivalence guarantee by gradually pushing operators down the maximally promoted state. A source partition can be considered as a chain of operators with one join at the source (upstream). We assign each partition with its layer in top-down order. Algorithm 2 and Figure 3 describes a top-down transformation that pushes operators down to source partitions in lower layers. Operators migrate down (upstream) via swaps, with a memoizer capturing each unique intermediate state along the way. Intuitively, partitions can spawn variants through two subroutines: (1) Reordering operators within the same partition, and (2) Pushing operators below the source join into lower partitions,

11: 12: 13: 14: 15: 16: 17: 18:

𝑃′ ← 𝑃 𝑎𝑐𝑡𝑖𝑣𝑒 ← 𝑃 .𝑠𝑖𝑛𝑘.𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛 while 𝑎𝑐𝑡𝑖𝑣𝑒 ≠ ∅ do for 𝑣 ∈ 𝑎𝑐𝑡𝑖𝑣𝑒 do if CanSwap(𝑣.𝑝𝑎𝑟𝑒𝑛𝑡, 𝑣) then 𝑃 ′ ← Swap(𝑣.𝑝𝑎𝑟𝑒𝑛𝑡, 𝑣) UpdateDep(𝑃 ′ ) 𝑎𝑐𝑡𝑖𝑣𝑒 ← GetActiveOps() return 𝑃 ′

namely PdInSrcPtt (Alg. 3) and PdAcrossSrcPtt (Alg. 4). The first subroutine permutes chained operators within each parallel layer-𝑘 partitions (e.g., in Figure 3, there exist two partitions in layer 𝑘 with two chained operators in each). The Cartesian product of parallel partitions’ variants is merged into the plan and memoized. These variants then seed the second subroutine, which records a new variant whenever an operator is pushed below a join. Again, the Cartesian product of these second-stage variants is merged and memoized. They become the starting plans in the next iteration on layer-𝑘 + 1 partitions. During this stage, ApplyPruneHeuristic (line 26, Alg. 3) applies conventional rules, such as predicate pushdown of regular filter, to eliminate dominated candidates. A regular filter costs negligibly compared with an LLM call and never increases cardinality. Any candidate placing it above an LLM operator is therefore dominated by one placing it below, and pruning such candidates never removes the cheapest plan. After iterating over each layer top-down, Alg. 2 is completed with all operators opportunistically pushed-down in the lowest layer and all equivalent plans memoized, except dominated plans removed by pruning. Without pruning, the enumeration is mutually exclusive and collectively exhaustive (Appendix A). Running Example. For the query presented in §1, the two filters on table_1 lie in the left sink partition of sem_join; operators above the join form its source partition. Pushup promotes eligible row-wise operators toward the join, but the map producing drugs_2 cannot cross it because the join predicate reads that attribute. Pushdown enumerates both orders of the independent left filters and admissible placements of other row-wise operators. Every candidate keeps drug extraction before the join and before the map producing antibio. 5

Subquery Execution Units

Scheduler

Q1

State 1

Q2 Q3

State

sem_aggr

sem_aggr

sem_aggr

⋈

σ ⋈

⋈

σ ⋈ π R S T

R

Profile (cost, sel)

Total Cost = 800

2

State

π T

S

Populate Cost

4

Profile-related

⋈

σ R

S

Driver Program 3

Physical Operators

π ⋈ T

Total Cost = 100

Q1 ⋈ π σ

Cache

Q2 ⋈ π σ

Cache

Q3 ⋈ π σ

Cache

Subquery Group (Ready)

Exec-related

LLM

SLM

Subquery Group

Figure 4: One Complete Iteration of SpecAQP – The workflow consists of 4 stages: 1. The Scheduler picks the next query to be executed and its current ready subquery group; 2. SEU profiles the subqueries to get costs; 3. SEU executes the cheapest subquery in the group; 4. Scheduler updates its internal states for the next iteration. Algorithm 2 Operator Pushdown

Algorithm 3 Pushdown in Source Partition

1: Input: Plan 𝑇 , Memoizer 𝑀

1: function PushdownRowWiseOps(𝑃, 𝑜𝑝_𝑡𝑦𝑝𝑒)

2: function Pushdown(𝑇 , 𝑘) 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19:

5

UpdateDep(𝑃) 𝑜𝑝𝑒𝑟𝑎𝑡𝑜𝑟𝑠 ← GetOpsBottomUp(𝑃 .𝑠𝑟𝑐, 𝑜𝑝_𝑡𝑦𝑝𝑒) 4: for 𝑜𝑝 ∈ 𝑜𝑝𝑒𝑟𝑎𝑡𝑜𝑟𝑠 do 5: while CanSwap(𝑜𝑝, 𝑜𝑝.𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛) and 𝑜𝑝.𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛 is not ⊲⊳ do 6: UpdateDep(𝑃) 7: 𝑃 ← Swap(op, op.children) 8: return 𝑃 9: function FuseDependencyGroup(𝑃) 10: 𝑑𝑒𝑝_𝑔𝑟𝑝𝑠 ← ∅ 11: 𝑜𝑝_𝑝𝑡𝑟 ← 𝑃 .𝑠𝑟𝑐.𝑝𝑎𝑟𝑒𝑛𝑡 12: 𝑎𝑛𝑐ℎ𝑜𝑟 ← 𝑜𝑝_𝑝𝑡𝑟 13: 𝑐𝑢𝑟𝑟𝑒𝑛𝑡_𝑔𝑟𝑝 ← {𝑜𝑝_𝑝𝑡𝑟 } 14: while 𝑜𝑝_𝑝𝑡𝑟 ∉ {⊲⊳, stateful ops} do 15: if CanSwap(𝑜𝑝_𝑝𝑡𝑟, 𝑎𝑛𝑐ℎ𝑜𝑟 ) or 𝑜𝑝_𝑝𝑡𝑟 = 𝑎𝑛𝑐ℎ𝑜𝑟 then 16: 𝑐𝑢𝑟𝑟𝑒𝑛𝑡_𝑔𝑟𝑝 ← 𝑐𝑢𝑟𝑟𝑒𝑛𝑡_𝑔𝑟𝑝 ∪ {𝑜𝑝_𝑝𝑡𝑟 } 17: else 18: 𝑑𝑒𝑝_𝑔𝑟𝑝𝑠 ← 𝑑𝑒𝑝_𝑔𝑟𝑝𝑠 ∪ {𝑐𝑢𝑟𝑟𝑒𝑛𝑡_𝑔𝑟𝑝} 19: 𝑎𝑛𝑐ℎ𝑜𝑟 ← 𝑜𝑝_𝑝𝑡𝑟 20: 𝑐𝑢𝑟𝑟𝑒𝑛𝑡_𝑔𝑟𝑝 ← {𝑜𝑝_𝑝𝑡𝑟 } 21: 𝑜𝑝_𝑝𝑡𝑟 ← 𝑜𝑝_𝑝𝑡𝑟 .𝑝𝑎𝑟𝑒𝑛𝑡 22: return 𝑑𝑒𝑝_𝑔𝑟𝑝𝑠 2:

P ← GetAllKthLayerPartition(𝑇 , 𝑘) 𝑠𝑒𝑒𝑑𝑠 ← ∅ for 𝑃𝑖 ∈ P do 𝑠𝑒𝑒𝑑𝑠 ← 𝑠𝑒𝑒𝑑𝑠 ∪ {PdInSrcPtt(𝑃𝑖 )} 𝑠𝑒𝑒𝑑𝑠 2 ← ∅ for 𝑐𝑜𝑚𝑏 ∈ CartesianProduct(𝑠𝑒𝑒𝑑𝑠) do 𝑇 ′ ← Merge(𝑇 , 𝑐𝑜𝑚𝑏) 𝑀 ← 𝑀 ∪ {𝑇 ′ } 𝑠𝑒𝑒𝑑𝑠 2 ← 𝑠𝑒𝑒𝑑𝑠 2 ∪ {𝑐𝑜𝑚𝑏} 𝑝𝑙𝑎𝑛𝑠_𝑛𝑒𝑥𝑡 ← ∅ for 𝑐𝑜𝑚𝑏 ∈ 𝑠𝑒𝑒𝑑𝑠 2 do Î for 𝑐𝑜𝑚𝑏 ′′ ∈ 𝑃 ′ ∈𝑐𝑜𝑚𝑏 PdAcrossSrcPtt(𝑃𝑖′ ) do 𝑖 𝑇 ′′ ← Merge(𝑇 , 𝑐𝑜𝑚𝑏 ′′ ) 𝑝𝑙𝑎𝑛𝑠_𝑛𝑒𝑥𝑡 ← 𝑝𝑙𝑎𝑛𝑠_𝑛𝑒𝑥𝑡 ∪ {𝑇 ′′ } ′′ for 𝑇 ∈ 𝑝𝑙𝑎𝑛𝑠_𝑛𝑒𝑥𝑡 do Pushdown(𝑇 ′′, 𝑘 + 1) return 𝑀

3:

INTER-QUERY SERVING

This section presents the serving infrastructure supporting online arrivals of semantic queries. The middleware exposes a backendindependent execution interface, allowing it to integrate with different inference engines and storage systems. Backend independence concerns the interface rather than the absence of execution feedback. The feedback is obtained at batch boundaries (i.e., execution costs) without relying on engine-specific internals. As discussed in §1, the effectiveness hinges on overcoming both C1 and C2. First, it requires support for low-level preemption of in-flight queries, enabling an external scheduler to respond to inter-query dynamism. Second, it can adapt to intra-query data dynamism within individual queries by choosing the best candidate plan with respect to varying data input. In §5.1, we first introduce the problem of Speculative Adaptive Query Processing (SpecAQP) and the system architecture that resolves both challenges with a unified abstraction of Subquery Execution Unit (SEU). In §5.2, we discuss the details in

23: function PdInSrcPtt(Partition 𝑃) 24: 25: 26: 27: 28:

𝑃 ← PushdownRowWiseOps(𝑃, {𝜎, 𝜋, . . . }) 𝑑𝑒𝑝_𝑔𝑟𝑝𝑠 ← FuseDependencyGroup(𝑃) 𝑑𝑒𝑝_𝑔𝑟𝑝𝑠 ← ApplyPruneHeuristic(𝑑𝑒𝑝_𝑔𝑟𝑝𝑠) 𝑠𝑒𝑒𝑑𝑠 ← ∪ApplyPermute(𝑑𝑒𝑝_𝑔𝑟𝑝𝑠) return 𝑠𝑒𝑒𝑑𝑠

SEU, the lowest-level preemptible units in the system. Finally, we demonstrate the framework enabling a Shortest Remaining Time First (SRTF) policy in §5.3.

5.1

Speculative Inter-Query AQP

While recent works [24, 37, 43] actively attempt to adopt on-GPU ML/LLM operators into query processing, they largely overlook 6

Algorithm 4 Pushdown across Source Partitions

to the root and safely yield execution upon preemption. The root operator can preserve its state simply by buffering the incoming batches upon preemption, incurring no extra memory overhead. Once all batches are buffered, the root evaluates the blocking operation and materializes the result for downstream use. Subqueries are preemptible at batch-level granularity. Consequently, the original logical plan can be decomposed into an 𝑛-ary tree hierarchy (i.e. subquery trees) of these preemptible subqueries by partitioning on blocking operators. As discussed in §4.1, blocking operators are strictly non-commutative, serving as rigid boundaries against the relocation of other operators. Because of this structural constraint, the equivalent plans enumerated in §4.2 share an isomorphic subquery tree topology. Consequently, each topological slot maps to a localized space of equivalent subquery variants from the plans, i.e. subquery groups. The subqueries in a group share the same set of local operators. Subquery Execution Unit (SEU) Subquery group seamlessly supports SpecAQP’s disaggregated execution. It enables intra-query AQP where a cost model evaluates subquery variants per batch and picks the best one to execute. It also supports inter-query dynamism, allowing execution to be preempted and later resumed using any equivalent subquery in the group. To manage this duallevel flexibility, SpecAQP assigns each group an SEU, which we detail in §5.2. Workflow Figure 4 illustrates the architecture of SpecAQP in a complete scheduler iteration during execution. The scheduler is responsible of keeping track of all query requests from users and deciding the query to be executed in the next iteration. The whole workflow consists of the following four steps. (1) Select the ready subquery group. After the scheduler has selected the current query through its scheduling algorithm, we identify the subquery group in it that is ready to be executed. This is computed by traversing the 𝑛-ary tree of groups in depth-first order to find the rightmost subquery group that is not completed yet with all its children groups marked as completed. Once the ready group is found, we create an SEU for it. (2) SEU profiles subquery group with SLM. Before an SEU starts execution of a subquery group, it needs to determine which subquery variant in it is the cheapest without causing serious execution blocking. Inspired by prior works on speculative inference [33, 39] and proxy approximation [27, 28], we run a representative subquery for the next batch using the physical operators on a speculative small language model (SLM). The SLM is efficient and incurs minimal cost compared to the LLM used for execution, but it offers an estimate for per-operator cost and statistics (e.g., token counts, latency, fan-in/out). SEU then populates all subqueries in the group, computing their costs using the operator profiles. (3) SEU executes subquery group with LLM. Once all subqueries’ costs can be determined, the SEU selects the cheapest one to be executed on the LLM, which fetches exactly one batch, processes it and suspends. If this is the last batch, the SEU marks the current group as completed and evaluates the root operator to yield the final result. It then creates a mock scan operator upon the materialized result, and inserts it into the downstream subquery group as the source of input.

1: function PdAcrossSrcPtt(Partition 𝑃) 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:

𝑜𝑝_𝑝𝑡𝑟 ← 𝑃 .𝑠𝑟𝑐.𝑝𝑎𝑟𝑒𝑛𝑡 𝑠𝑒𝑒𝑑𝑠 ← {𝑃 } while 𝑜𝑝_𝑝𝑡𝑟 ∉ {⊲⊳, stateful ops} do if CanSwap(𝑜𝑝_𝑝𝑡𝑟, 𝑃 .𝑠𝑟𝑐) then 𝑃 ← Swap(𝑜𝑝_𝑝𝑡𝑟, 𝑃 .𝑠𝑟𝑐) 𝑠𝑒𝑒𝑑𝑠 ← 𝑠𝑒𝑒𝑑𝑠 ∪ {𝑃 } 𝑜𝑝_𝑝𝑡𝑟 ← 𝑃 .𝑠𝑟𝑐.𝑝𝑎𝑟𝑒𝑛𝑡 else 𝑠𝑒𝑒𝑑𝑠 ← 𝑠𝑒𝑒𝑑𝑠 ∪ {𝑃 } break return 𝑠𝑒𝑒𝑑𝑠

Algorithm 5 SpecAQP 1: Input: Scheduler scheduler, Profiler profiler 2: function InitQuery(𝑞) 3: 4: 5: 6:

𝑞.𝑠𝑢𝑏𝑞_𝑔𝑟𝑝_𝑡𝑟𝑒𝑒 ← GroupSubqery(𝑞.𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒_𝑝𝑙𝑎𝑛𝑠) 𝑝ℎ𝑦𝑠𝑖𝑐𝑎𝑙_𝑜𝑝𝑠 ← InitAllPhysicalOps(𝑞) Add(scheduler.queries, q) return 𝑝ℎ𝑦𝑠𝑖𝑐𝑎𝑙_𝑜𝑝𝑠

7: function Execute() 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19:

while 𝑠𝑐ℎ𝑒𝑑𝑢𝑙𝑒𝑟 .𝑞𝑢𝑒𝑟𝑖𝑒𝑠 ≠ ∅ do 𝑐𝑢𝑟 _𝑞 ← Step(𝑠𝑐ℎ𝑒𝑑𝑢𝑙𝑒𝑟 ) 𝑐𝑢𝑟 _𝑠𝑢𝑏𝑞_𝑔𝑟𝑝 ← GetReadySubq(𝑐𝑢𝑟 _𝑞.𝑠𝑢𝑏𝑞_𝑔𝑟𝑝_𝑡𝑟𝑒𝑒) 𝑟𝑒𝑝𝑟 _𝑠𝑢𝑏𝑞 ← GetProfileSubq(𝑐𝑢𝑟 _𝑠𝑢𝑏𝑞_𝑔𝑟𝑝) 𝑑𝑟𝑖𝑣𝑒𝑟 ← GetDriver(𝑟𝑒𝑝𝑟 _𝑠𝑢𝑏𝑞) 𝑝𝑟𝑜 𝑓 𝑖𝑙𝑒 ← Run(𝑑𝑟𝑖𝑣𝑒𝑟, 𝑟𝑒𝑝𝑟 _𝑠𝑢𝑏𝑞, 𝑝ℎ𝑦𝑠𝑖𝑐𝑎𝑙_𝑜𝑝𝑠) for 𝑠𝑢𝑏𝑞 ∈ 𝑐𝑢𝑟 _𝑠𝑢𝑏𝑞_𝑔𝑟𝑝.𝑠𝑢𝑏𝑞𝑢𝑒𝑟𝑖𝑒𝑠 do PopulateProfile(subq, profile) 𝑏𝑒𝑠𝑡_𝑠𝑢𝑏𝑞 ← GetBestSubq(𝑐𝑢𝑟 _𝑠𝑢𝑏𝑞_𝑔𝑟𝑝) 𝑑𝑟𝑖𝑣𝑒𝑟 ← GetDriver(𝑏𝑒𝑠𝑡_𝑠𝑢𝑏𝑞) 𝑟𝑒𝑠𝑢𝑙𝑡, 𝑠𝑡𝑎𝑡𝑠 ← Run(𝑑𝑟𝑖𝑣𝑒𝑟, 𝑏𝑒𝑠𝑡_𝑠𝑢𝑏𝑞, 𝑝ℎ𝑦𝑠𝑖𝑐𝑎𝑙_𝑜𝑝𝑠) Update(scheduler, result, stats)

system-level integration with the model-serving backend. The gap makes performances highly dependent on hardware-scaling choices and therefore impractical to real-world scenarios. Aero [25] studies adaptive solutions on analytical queries over video databases with respect to GPU-side optimizations, but still assumes uninterrupted execution of individual queries with exclusive GPU occupancy. Handling concurrent arrival and execution of queries is nontrivial mainly due to two complexities. First, the orchestration inside individual query’s execution is often sophisticated (e.g., [25] applies a specialized implementation of Eddies [8] to only resolve filter reordering). Second, the presence of stateful operators (e.g., aggregation requires access to all possible data before producing any output) blocks streaming execution and requires additional state-preserving and recovering. Subquery Groups SpecAQP tackles both challenges via disaggregated execution over subqueries. Subqueries are defined as logical subtrees rooted at a single blocking operator with all descendant nodes being non-blocking (e.g., filters, joins). A subquery is the maximal unit that allows non-blocking operators to stream batches 7

(4) Update scheduler state. After execution over one batch is completed, the information used in the scheduling algorithm is updated with the current execution statistics, and the scheduler makes the decision for the next iteration.

5.2

preemption mid-flight. Because the SEU processes data and materializes costs at the granularity of individual batches, the scheduler can possess an accurate and dynamically updated estimate of the remaining execution time for all active subquery groups (line 18 in Alg.5). This fine-grained, cost-aware context switching allows our system to natively support SRTF.

Subquery Execution Unit

A Subquery Execution Unit (SEU) manages the execution of a single data batch once the scheduler activates its corresponding subquery group. The SEU serves as the basic granularity for cost profiling and execution in the adaptive framework. Upon instantiation by the external scheduler, the SEU retrieves the subquery group’s operator pool. A driver program then links these operators into a physical subquery plan, streaming batch inputs from scan operators or upstream subquery yields through the plan in a depth-first order. To facilitate both speculative execution and actual processing, the SEU interfaces with both the SLM and the LLM. During cost estimation, it employs Speculative Profiling, where it streams a single batch through the SLM to materialize the physical costs of each operator. During actual execution, the SEU processes the batch identically, but routes it through the LLM. Populating Costs While runtime profiling captures highly accurate execution metrics, exhaustively profiling the exponential search space of equivalent operator topology within a subquery group is prohibitively expensive even with the SLM. To address this, the SEU profiles only a single representative plan topology (repr_subq in line 11 of Alg.5), and derives the costs of all alternative equivalent plans via a virtual cost evaluator. We select the topology with the maximum pushdown of row-level operators (e.g., filters and projections) as the representative plan. During speculative profiling, each operator evaluates the full batch instead of the rows that pass the previous filtering. The SEU records per-row outcomes of filters and joins as bitmaps and faithfully evaluates the bitwise operations to estimate the intermediate cardinalities of each candidate plan. The evaluator then aggregates the corresponding operator costs according to each candidates’ topology. We detail the profiler design in Appendix B. After doing so, within the SEU, the topology with lowest cost and execute its physical plan is picked, as described in line 13-16 of Alg.5. Notably, this full-batch profiling can lead to substantially more work as it forgoes reduction of input cardinality from upstream operators. Ideally, using a fast yet performative SLM helps mitigate this profiling overhead. To further control profiling cost, SeqoFlow supports both periodic profiling and profiling triggered by a large mismatch between estimated and observed execution costs.

5.3

6

IMPLEMENTATION

We built SeqoFlow with 6K lines of Python code. We implement the semantic operators following [43] and adopt Pandas DataFrame [42] as the base relational data model. In this section, we discuss several implementation details. Materialized Nested-Loop Join. Streaming joins such as the Symmetric Hash Join [56] and Ripple Join [19] maintain symmetric state for both inputs and require complex eviction policies at scale. To support batch-level yielding, we instead implement a materialized nested-loop join [18, 50], consistent with existing semantic join implementations [43, 54]. It caches only the active outer batch while progressively materializing the inner relation, so a preempted join resumes without refetching its inner input. Caching, Broadcasting, and Fingerprinting. Mid-flight plan changes alter the state buffered inside joins: once an operator moves across a join, the cached inner relation cannot be replayed blindly without redundant or missing semantic processing. Each batch therefore carries lineage metadata maintained by three primitives. Caching buffers per-batch results of row-wise operators for reuse. Broadcasting evaluates an operator only on rows with distinct values in its input columns (e.g., a filter’s predicate key) and copies the results to duplicate rows. Fingerprinting records the set of operators each batch has visited, similar to Eddies [8]. Scheduler Cost Modeling The execution cost of each operator is formulated as a weighted sum of its prefill and decode tokens. To support SRTF scheduling, the system maps this cost to remaining time using dynamically profiled scaling factors. Specifically, at scheduling step 𝑘 and wall time 𝑡, SRTF selects argmin𝑖 score𝑖 (𝑡)-th query to be executed in the next step. The score is defined by:

𝑟𝑖,𝑘 = 𝜉 · (𝛾 1 · prefill + 𝛾 2 · decode + 𝛾 3 ) , 𝜙𝑘 = 1 [𝑘 > 0] h
i 𝑅ˆ𝑖,𝑘 = 𝜙𝑘 (1 − 𝛽) 𝑅ˆ𝑖,𝑘 −1 − (𝑠𝑖,𝑘 − 𝑠𝑖,𝑘 −1 ) + 𝛽 𝜙𝑘 𝑟𝑖,𝑘
score𝑖 (𝑡) = 𝑅ˆ𝑖 (𝑡) − 𝛼 𝑡 − 𝑎𝑖 − 𝑠𝑖 (𝑡)

SRTF Scheduling 𝑟𝑖,𝑘 estimates token costs. 𝑅ˆ𝑖,𝑘 models actual remaining work by applying a residual smoothing factor 𝛽. 𝑠𝑖,𝑘 or 𝑠𝑖 (𝑡) is the total attained service of the 𝑖-th query at 𝑡 (step 𝑘), 𝑎𝑖 is the arrival time. To prevent starvation of long-running queries in SRTF, we apply an aging factor 𝛼 penalizing long waits with deficient attained service. After step 𝑘, only 𝜉 is updated to match newly completed work 𝑅ˆ𝑖,𝑘 −1 − 𝑟𝑖,𝑘 with 𝑠𝑖,𝑘 − 𝑠𝑖,𝑘 −1 , i.e. the newly attained service. This online calibration allows remaining-time estimates to reflect the backend’s observed execution performance, incorporating changes in inference conditions into subsequent scheduling decisions.

Shortest Remaining Time First (SRTF) scheduling is a simple yet theoretically optimal algorithm to minimize latency when serving ad hoc arrival requests. It reduces the cumulative queue waiting time of each request by always serving the one with the shortest remaining time to completion first. In most existing frameworks like LOTUS, query execution is non-preemptive, and once a complex physical query plan is dispatched, it must run to completion. This creates severe head-of-line blocking, where newly arrived and short queries are forced to wait for long-running, active queries to finish. Our system overcomes this limitation by enabling batch-level 8

SeqoFlow:SRTF SeqoFlow:MLFQ SeqoFlow:PDB Patent 1e2 BioDEX - (0.2, H) 1e3

3.0

P50 Latency (s)

2.0 1.0 0.0

0.005 0.010 0.015 1e2 BioDEX - (0.8, L)

6.0 4.5 3.0 1.5 0.0 8.0

Static-1:SRTF 3.2

1.2

0.005 0.010 1e2 BioDEX - (0.8, H)

0.8

1.5

0.0

0.0

0.0 1.6

0.002 0.004 Legal 1e3

0.006

3.2

4.0

0.8

1.6

1.5

2.0

0.4

0.0

0.0

0.0

0.003 0.005 0.007 0.010 0.013

0.9

0.3

3.0

Throughput (queries/s)

1.2

3.0

1.6

1.2

0.015

4.5

0.6

6.0

0.010

LOTUS:FCFS Eddies:FCFS 1e3 BioDEX - (0.2, H) 1e4

2.4

4.5

0.005

Static-2:SRTF

1e3 BioDEX - (0.2, L)

0.9

P99 Latency (s)

SeqoFlow:FCFS

4.0 1e2 BioDEX - (0.2, L)

0.002

0.004

0.006

0.005 0.010 0.015 1e3 BioDEX - (0.8, L)

0.6 0.3 0.005 0.010 1e4 BioDEX - (0.8, H)

1.2

2.4

0.0 8.0 4.0

0.8

0.4

2.0

0.0

0.0

0.010

0.015

0.002 0.004 Legal 1e3

0.006

6.0

0.8

0.005

Static-Best:SRTF* Patent

0.003 0.005 0.007 0.010 0.013

Throughput (queries/s)

0.0

0.002

0.004

0.006

Figure 5: Latency vs Throughput in continuous arrivals – P50 and P99 of completed queries after certain cutoff in continuous runs. Runtime settings are denoted as {Method : Scheduler}. Geometric means across 10 runs are reported with min–max span. execution and scheduling, we disable LOTUS’s model cascading feature, ensuring a strictly lossless execution using the identical underlying LLM. For query evaluation, the LOTUS baseline executes the default static logical topology provided by the initial query inputs, as it does not natively support mid-flight plan optimization. Eddies [8]. This approach proposes an Eddy operator, a runtime router that forwards data to different operators according to their respective cost statistics. It allows adaptively reordering the operators during execution. We implement Eddies on top of LOTUS with additional support for batch-by-batch processing. Since the architecture does not consider operator dependencies, we manually bind operators with dependency constraints into fused operators, and leverage existing approaches [9, 11, 25, 46] to decide the score of each operator as 𝑐𝑜𝑠𝑡/(1 − 𝑠𝑒𝑙𝑒𝑐𝑡𝑖𝑣𝑖𝑡𝑦) for routing. Static-1/2. We implement these baselines in SeqoFlow by applying rule-based optimizations adopted from [38, 53] and humancurated operator-ordering heuristics [21] to reorder operators. We use these plans as strong, workload-specific heuristic baselines. Specifically, Static-1 uses predicate pushdown and Static-2 pushes semantic operators up to the root of the plan. Static-Best*. This baseline executes a single fixed plan throughout, namely the best plan in hindsight among all enumerated candidates, or the first plan selected by SeqoFlow when the plan space is too large to execute exhaustively. All baseline implementations adopt related techniques mentioned in §6 to ensure a fair comparison. We use Qwen3-4B and Qwen3-32B [59] for speculative profiling and execution, respectively. We serve them on two separate vLLM [32] instances colocated on an 8×A100 NVIDIA GPU server with tensor parallelism (TP=8), and enable chunked prefill [7] with ≤4096 tokens per chunk. SeqoFlow issues LLM calls at the query level and makes no assumption about how the LLM is deployed. We include profiling overhead throughout the reported results.

7 EVALUATION 7.1 Experiment Setup Workload Generation To our knowledge, no existing benchmark stress-tests the runtime dynamism in semantic queries. We therefore develop a configurable testbed that generates diverse settings. We utilize BioDEX [17], a semantically rich, high-dimensional biomedical dataset to construct controlled, representative and holistic evaluation. First, 9 representative query templates from the TPC-H [14] benchmark covering a wide range of common patterns in plan topology are selected as base plans, while we replace parts of their regular operators with LLM-based operators. We then configure these workloads with 2 parameters: the variances of selectivities 𝛿 (𝜎𝑜𝑝 ) and sequence lengths 𝛿 (𝑠𝑒𝑞_𝑙𝑒𝑛) among individual operators. Additionally, the selectivity of the entire query S is used to control the feasible space of the two parameters. For input (or prefill) sequence lengths, we partition the input space into 3 tiers: High, Medium and Low 𝛿 (𝑠𝑒𝑞_𝑙𝑒𝑛). A workload is constructed by sampling sequence lengths uniformly, with 50% of operators drawn from the lower interval and 50% from the upper interval of the selected tier. Then, given 𝛿 (𝜎𝑜𝑝 ), the selectivities of selective operator (filters and joins) are randomly generated by the testbed to produce a target end-to-end query selectivity S. We consider (1) 𝛿 (𝜎𝑜𝑝 ) = 0.2 and (2) 𝛿 (𝜎𝑜𝑝 ) = 0.8, reflecting queries with more or less discrepant selectivity ranges respectively. In the following sections, unless otherwise noted, controlled settings are denoted as (𝛿 (𝜎𝑜𝑝 ), 𝛿 (𝑠𝑒𝑞_𝑙𝑒𝑛))3 . To test the system against real-world scenarios, we extend the selected query templates to 2 additional corpora with only the definition (i.e., instructions to the LLM) changed within each operator, namely Legal [12] and Patent [1]. However, in these workloads, no configuration is attached. The cost and selectivity of each operator are determined solely by the actual semantics. Baselines We compare system performance with the following equivalence-preserving baselines for comparison. LOTUS [43]. This baseline features a declarative system with predefined semantic operators. To isolate the performance of query

7.2

End-to-end Performance

7.2.1 Effectiveness of Inter-Query Scheduling. Figure 5 compares SeqoFlow with run-to-completion baselines under continuous arrivals, using several scheduling policies implemented in SeqoFlow. Randomized queries arrive as a Poisson process with rate 𝜆 =

3We present results under High and Low settings due to space constraints. For all

experiments in §7 without specifying testbed configurations, we use BioDEX-(0.2, H).

9

Relative Performance

LOTUS

BioDEX - (0.2, L)

3.0 2.5 2.0 1.5 1.0 0.5 0.0

BioDEX - (0.8, L)

3.0 2.5 2.0 1.5 1.0 0.5 0.0

3.96x 5.12x

Q0

Q1

Q2

Q3

Q4

Q5

Q6

Q7

Q8

Eddies

Static-2

Static-1

BioDEX - (0.2, H)

3.0 2.5 2.0 1.5 1.0 0.5 0.0

3.68x

3.0 2.5 2.0 1.5 1.0 0.5 0.0

4.41x

BioDEX - (0.8, H)

Q0

Q1

Q2

Q3

Q4

Q5

Q6

SeqoFlow 7.21x

3.0 2.5 2.0 1.5 1.0 0.5 0.0

6.57x

3.0 2.5 2.0 1.5 1.0 0.5 0.0

Q7

Q8

Legal

4.90x

Patent

Q0

Q1

Q2

Q3

Q4

Q5

Q6

Q7

Q8

Query Figure 6: Single-query optimization – SeqoFlow can optimize a single query via plan enumeration and adaptively selecting the best plan at runtime. Relative performance is calculated as 𝑚𝑖𝑛(𝑆𝑡𝑎𝑡𝑖𝑐1, 𝑆𝑡𝑎𝑡𝑖𝑐2)/𝑙𝑎𝑡𝑒𝑛𝑐𝑦, i.e. higher is better. Geometric means across 10 runs are reported with min–max span and 25th/75th percentiles on whiskers. SF:SRTF SF:FCFS

Latency (s)

1.6

1e4

SF:MLFQ SF:PDB

Static-1:SRTF Static-2:SRTF

BioDEX - (0.2, H) P50

3.2

1.2

2.4

0.8

1.6

0.4

0.8

0.0 3.2

0.0

Legal P50

1e4

1e4

BioDEX - (0.2, H) P99

1e4

Legal P99

6.0

2.4

4.5

1.6

3.0

0.8 0.0 4 10

even one chosen by an oracle, reaches the capacity that SeqoFlow attains by adapting its plan at runtime, and the advantage is largest on Patent and Legal, where operator costs vary most across inputs. SRTF contributes to lower P50 latencies at varying loads. Within SeqoFlow, SRTF reduces P50 latency by 2.5–4× compared to FCFS, MLFQ, and PreemptDB near saturation, while matching them at low load. This isolates the scheduler’s contribution. With the plan held fixed, a scheduling policy can only reorder queued work. Its benefit gradually grows with queueing delay as load increases. As load approaches system capacity, FCFS, MLFQ, and PDB rise sharply, while SRTF is more resistant in queuing inflation. This behavior matched the theoretical expectation of SRTF minimizing mean response time, as serving short queries first keeps most queries from waiting even close to saturation. SRTF supported by SeqoFlow surpasses run-to-completion baselines in P50 and P99 latencies. Although SRTF is known for inflating tail latency by starving long jobs, SeqoFlow with SRTF sustains 1.9× more load than LOTUS and Eddies with FCFS before P99 latency inflates. It also stays within 1.4× of SeqoFlow with FCFS. First, as SeqoFlow reduces per-query service time, it lowers the entire latency distribution, including the tail. Second, SeqoFlow’s SRTF ages waiting queries (§6), which bounds how long a long query can be deferred and limits the queueing delay that starvation would otherwise add to the tail. Selecting efficient plans combined with bounded deferral thus outperforms the baselines, even though they use FCFS which prefers reducing tail latency. SeqoFlow speeds up job completions in finite workloads. Figure 7 shows latency against offered arrival rate in a simulated run with 200 arrivals of real traces collected from individual queries. Beyond saturation, latency plateaus because each run issues a finite query stream, SeqoFlow with SRTF achieves the lowest P50 latency on both workloads, which is 3.6× and 3.5× lower on both datasets than LOTUS with FCFS. SeqoFlow’s P99 plateau is also 2× below LOTUS. This confirms that even under sustained overload, aging keeps SRTF’s tail latency comparable to FCFS.

LOTUS:FCFS Eddies:FCFS

1.5 10 3

10 2

10 1

100

0.0 4 10

10 3

10 2

10 1

100

Arrival Rate (queries/s) Figure 7: Finite arrivals with varying arrival rates – SF stands for SeqoFlow.

load/𝐸 [latency], where 𝐸 [latency] is the mean latency of queries run in isolation across all approaches and random seeds. After a fixed-time warmup, 1,000 queries arrive in a sufficient window as the main cohort. The final completion window then measures the whole cohort to complete while allowing new arrivals. Results therefore exhibit a 1,000-job stream in the middle of a continuous arrival. Since SeqoFlow supports most preemption-based schedulers, we also implement PreemptDB (PDB) [22]’s policy for comparison. SeqoFlow boosts system throughput at fixed latency budget as well as system capacity. Under the same SRTF scheduler, SeqoFlow sustains more load at a given latency and has higher capacity than static plans. With the scheduler held fixed at SRTF, SeqoFlow sustains up to 1.9× higher throughput than Static-1 and up to 4.3× higher than Static-2 at the same P50 latency, and it saturates at a strictly higher load on every workload. Saturation of system capacity can be solely attributed to per-query execution cost, as the scheduler cannot change the total work the system must perform. SeqoFlow also exceeds Static-Best*, which picks the best fixed plan per workload with hindsight. No single static plan, 10

Speedup

Eddies 2

Static-Best

1.90× 1.43×

1.77× 1.37×

10%

30%

1 0

(a) Numbers indicate the percentage of (b) The overhead of static plan enuE2E system latency attributed to spec- meration with different equivalent ulative profiling overhead. plan search space cardinality.

SeqoFlow

1.78× 1.34×

50% Fluctuation

1.75× 1.32×

70%

Raw Execution

1.76× 1.32×

90%

Figure 10: Speedup over Eddies under fluctuations.

Figure 8: Latency breakdown in SeqoFlow speculative profiling. As both components depend on the cardinality of the equivalent plan space, we evaluate their overhead under varying search space sizes in Figure 8. Figure 8a shows that speculative profiling introduces less than 10% overhead for most queries. Similarly, Figure 8b demonstrates that plan enumeration contributes negligible compilation overhead in typical cases. Even for extreme cases with plan spaces containing over 1,000 equivalent plans, the optimization overhead remains justified by the resulting execution time reduction. For the most challenging case (Q8), speculative profiling accounts for 41.6% of execution time. However, SeqoFlow still achieves substantial performance improvements compared to executing without optimization. This efficiency is enabled by SeqoFlow’s compact plan enumeration strategy and lightweight profiling mechanism, which avoid exhaustive evaluation of all equivalent plans while preserving accurate cost estimation.

(a) Random continuous fluctuation

7.3

Adaptiveness to Intra-Query Dynamism

To further test SeqoFlow’s adaptiveness to dynamism, the costs and selectivities of selected operators are flipped in a portion (10%– 90%) of batches. For instance, a filter that is originally cheap and selective becomes expensive and non-selective, so the plan that is best for the first batch loses its advantage on the flipped batches. Figure 9 demonstrates the per-batch latency of a representative query under both random continuous and highly dynamic fluctuation. SeqoFlow switches to a cheaper plan and returns once the flip in the injected fluctuation windows. In Figure 10, as the flipped portion grows, Static-Best* steadily degrades and falls below Eddies, since no fixed plan remains optimal once operator costs shift across batches. SeqoFlow re-selects plans batch by batch and outperforms both at every portion, achieving 1.32–1.43× speedups over Eddies end to end. Meanwhile, we show that SeqoFlow can be more effective when only considering execution cost (Raw Execution). This means SeqoFlow’s sensitivity to runtime dynamism can be restrained by the SLM when cost drifts are detected frequently, triggering more profiling dispatched to capture the latest costs.

(b) Highly dynamic fluctuation

Figure 9: Adaptiveness to fluctuations in workloads – SeqoFlow consistently converges to lower-cost candidate plans when fluctuation happens. Each step processes one batch. 7.2.2 Single-Query Optimization. We further validate SeqoFlow in terms of automatically deriving a plan with near-optimal performance when data characteristics are relatively controlled during runtime. As illustrated in Figure 6, SeqoFlow consistently outperforms LOTUS across all evaluated settings, achieving speedups of up to 7×. Crucially, it reliably matches the best performance of the human-curated baselines (Static-1 and Static-2) and even surpasses them in several configurations. This reveals that plan enumeration (§4) discovers optimization opportunities that rigid static rules miss, while our cost-based selection (§5.2) correctly picks a competitive topology. Furthermore, for complex plans with highly variable semantic execution costs, SeqoFlow manifests a promising advantage over simple and localized data-routing like Eddies. Eddies also lacks native support for inter-operator data dependencies and restricts reordering to a limited operator subset, making it struggle to optimize such settings.

7.4

Validation of Cost Modeling

SeqoFlow relies on speculative cost estimates both to select plans within an SEU (§5.2) and to prioritize queries under SRTF (§5.3). We validate the estimates against each decision. Speculative profiling on the SLM reliably selects the best plans for the LLM. Plan selection consumes the estimated cost of each candidate, which compounds operator selectivities with token counts and per-call latency. We therefore measure the relative error between the predicted cost from SLM profiling and the actual cost

7.2.3 Latency Breakdown. We further analyze the runtime overhead introduced by SeqoFlow, including plan enumeration and 11

CDF

Q0

Q1

Q2

Q3

Q4

Q5

1.00

1.00

0.75

0.95

0.50

0.90

0.25

0.85

0.00 ≤0.01%

1%

0.80

100%

Q6

1

(a) Cost estimate error

Q7

3

Q8

with few admissible candidates, and it primarily tests whether plan transformations preserve the query result. It therefore leaves little headroom for improvement from discovering the best plan candidate, while speculative profiling can also add overhead. In contrast, Q1 and Q6 contain multiple semantic filters, projections and joins, yielding more admissible plan candidates with respect to dependency constraints. An early selective filter can avoid downstream projection calls, whereas a costly filter that retains most rows may be better delayed. The favorable order depends on runtime selectivity and token cost, which fixed pushdown or pushup rules cannot determine in advance, making them highly profitable. SeqoFlow uses its runtime estimates to select among these plans, leading to larger gains on these settings.

All

10

30

(b) Chosen plan rank

Figure 11: Accuracy of speculative cost estimation – (a) Relative cost error of each batch, with the dashed line at 10%. (b) Rank of the chosen plan among all candidates by actual cost. Table 1: Ranking quality of estimated against actual remaining time across active queries under 90% input load. Spearman 𝜌 SLM/LLM

w/o Age

Age

w/o Age

Age

4B/32B 4B/DeepSeek-Flash 4B/gpt-6-luna

0.748 0.897 0.923

0.714 0.705 0.755

84.6% 93.9% 94.5%

74.8% 88.2% 94.1%

P50 Latency (s)

SeqoFlow:SRTF 1.6

1e3

4B/DS-Flash 3.0

0.8

2.0

0.4

1.0

0.0 0.003

1e2

4.0

0.005

0.0

4B/32B

3.2 2.4 1.6 0.8 0.002

0.003

0.0

0.008

0.012

Throughput (queries/s)

Figure 12: End-to-end performance across SLM/LLM combinations under SRTF.

on the LLM, over all batches of all queries with 70% of batches flipped (§7.3). Over 80% of batches are estimated within 10% error (Figure 11a). For over 95% of batches, SeqoFlow executes one of the top-2 plans under actual costs (Figure 11b). Speculative estimates rank concurrent queries accurately for SRTF. SRTF depends only on the relative order of remaining times, which SeqoFlow preserves with high fidelity. Without aging, SeqoFlow orders up to 94.5% of query pairs correctly, with Spearman 𝜌 up to 0.92 (Table 1). Aging deliberately trades part of this order for bounded waiting, yet keeps at least 74.8% of pairs correctly ordered. Together, accurate plan selection and query ranking deliver consistent end-to-end gains across models. Pairing the same 4B SLM with official APIs of DeepSeek-Flash [16], and GPT-6 Luna, SeqoFlow sustains higher throughput than Static-Best* under every combination, whether the LLM is self-hosted or served through an API (Figure 12). Since Static-Best* fixes the best plan in hindsight under the same scheduler, this advantage stems from per-batch plan selection guided by speculative estimates.

7.5

DISCUSSION AND FUTURE WORK

Concurrency Control. SeqoFlow naturally supports concurrent OLAP workloads by isolating memory spaces of relevant data structures and cache buffers. However, extending the system to handle concurrent data modifications and associated consistency challenges remains an interesting direction. Search Space Pruning. SeqoFlow captures equivalent logical plans to adapt to runtime operator behavior. As with exhaustive plan enumeration, the search space can grow combinatorially. In the extreme case of fully independent operators, the number of equivalent orderings can reach 𝑂 (𝑁 !). Developing principled pruning techniques that preserve runtime adaptivity while reducing exploration overhead is an important trade-off for future work. With exact costs, exhaustive enumeration guarantees the best plan within the supported space, but finding that plan in practice need not require retaining every candidate. Besides the well-known pruning heuristics in §4.2, advanced runtime pruning could discard plans that are observably poor on current batches and retain promising ones, revisiting them if costs shift. System Integration. SeqoFlow is designed for storage backends with batch support as discussed in §3. It is compatible with existing physical optimizations and orthogonal to the design spaces of LLM serving systems and operator implementations. Cross-query computation reuse. Although SeqoFlow improves efficiency in serving multiple semantic queries concurrently, it does not assume any shared operators across different queries as well as the actual LLM calls from them. Exploiting shared work among concurrent queries is previously covered by works such as [10, 49], and can be further addressed as a materialized view problem [20] in the multi-query setting.

Static-Best:SRTF

1e3 4B/gpt-6-luna

1.2

8

𝐴𝑐𝑐 𝑃𝑎𝑖𝑟

9

CONCLUSION

In this work, we present SeqoFlow, a unified framework that jointly addresses different types of runtime dynamism. By modeling operator constraints and equivalence boundaries, enabling fine-grained, structure-aware execution, and introducing lightweight speculative cost estimation, our approach effectively adapts to dynamic workloads. Experimental results show that SeqoFlow significantly outperforms existing methods. Overall, this work highlights the importance of co-designing optimization and scheduling for AIpowered data systems and provides a foundation for future semantic query processing engines.

Case Studies

Figure 6 has shown that the benefit of SeqoFlow varies across different workloads. We present a brief study on SeqoFlow’s best and worst performances. In the bad cases, Q0 has only 4 operators 12

Myna Prasanna Kalluraya, Subrata Mitra, Ali Payani, Yao Lu, Umakishore Ramachandran, and Joy Arulraj. 2023. EVA: An End-to-End Exploratory Video Analytics System. In Proceedings of the Seventh Workshop on Data Management for End-to-End Machine Learning (Seattle, WA, USA) (DEEM ’23). Association for Computing Machinery, New York, NY, USA, Article 8, 5 pages. https://doi.org/10.1145/3595360.3595858 [25] Gaurav Tarlok Kakkar, Jiashen Cao, Aubhro Sengupta, Joy Arulraj, and Hyesoon Kim. 2025. Aero: Adaptive Query Processing of ML Queries. Proc. ACM Manag. Data 3, 3, Article 174 (June 2025), 27 pages. https://doi.org/10.1145/3725408 [26] Daniel Kang, Peter Bailis, and Matei Zaharia. 2018. Blazeit: Optimizing declarative aggregation and limit queries for neural network-based video analytics. arXiv preprint arXiv:1805.01046 (2018). [27] Daniel Kang, Edward Gan, Peter Bailis, Tatsunori Hashimoto, and Matei Zaharia. [n.d.]. Approximate Selection with Guarantees using Proxies. Proceedings of the VLDB Endowment 13, 11 ([n. d.]). [28] Daniel Kang, John Guibas, Peter Bailis, Tatsunori Hashimoto, Yi Sun, and Matei Zaharia. 2021. Accelerating approximate aggregation queries with expensive predicates. Proceedings of the VLDB Endowment 14, 11 (2021), 2341–2354. [29] Konstantinos Karanasos, Matteo Interlandi, Doris Xin, Fotis Psallidas, Rathijit Sen, Kwanghyun Park, Ivan Popivanov, Supun Nakandal, Subru Krishnan, Markus Weimer, et al. 2019. Extending relational query processing with ML inference. arXiv preprint arXiv:1911.00231 (2019). [30] Fisnik Kastrati and Guido Moerkotte. 2016. Optimization of conjunctive predicates for main memory column stores. Proceedings of the VLDB Endowment 9, 12 (2016). [31] Donald E Knuth. 1998. The Art of Computer Programming: Sorting and Searching, volume 3. Addison-Wesley Professional. [32] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th symposium on operating systems principles. 611–626. [33] Yaniv Leviathan, Matan Kalman, and Yossi Matias. 2023. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning. PMLR, 19274–19286. [34] Alon Y Levy, Inderpal Singh Mumick, and Yehoshua Sagiv. 1994. Query optimization by predicate move-around. In VLDB, Vol. 94. 12–15. [35] Guoliang Li, Ji Sun, Lijie Xu, Shifu Li, Jiang Wang, and Wen Nie. 2024. Gaussml: An end-to-end in-database machine learning system. In 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 5198–5210. [36] Paweł Liskowski, Benjamin Han, Paritosh Aggarwal, Bowei Chen, Boxin Jiang, Nitish Jindal, Zihan Li, Aaron Lin, Kyle Schmaus, Jay Tayade, Weicheng Zhao, Anupam Datta, Nathan Wiegand, and Dimitris Tsirogiannis. 2026. Cortex AISQL: A Production SQL Engine for Unstructured Data. In Companion of the International Conference on Management of Data (India) (SIGMOD Companion ’26). Association for Computing Machinery, New York, NY, USA, 400–412. https://doi.org/10.1145/3788853.3803093 [37] Chunwei Liu, Matthew Russo, Michael Cafarella, Lei Cao, Peter Baile Chen, Zui Chen, Michael Franklin, Tim Kraska, Samuel Madden, Rana Shahout, et al. 2025. Palimpzest: Optimizing ai-powered analytics with declarative query processing. In Proceedings of the Conference on Innovative Database Research (CIDR). 2. [38] Qiuyang Mang, Yufan Xiang, Hangrui Zhou, Runyuan He, Jiaxiang Yu, Hanchen Li, Aditya Parameswaran, and Alvin Cheung. 2026. Horrila: Cost-Based Placement of Semantic Operators in Hybrid Query Plans. arXiv:2604.09944 [cs.DB] https://arxiv.org/abs/2604.09944 [39] Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, et al. 2024. Specinfer: Accelerating large language model serving with treebased speculative inference and verification. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3. 932–949. [40] Thomas Neumann, Sven Helmer, and Guido Moerkotte. 2005. On the optimal ordering of maps and selections under factorization. In 21st International Conference on Data Engineering (ICDE’05). IEEE, 490–501. [41] Thomas Neumann, Sven Helmer, and Guido Moerkotte. 2006. On the optimal ordering of maps, selections, and joins under factorization. In Proceedings of the 23rd British National Conference on Databases, Conference on Flexible and Efficient Information Handling (Belfast, Northern Ireland, UK) (BNCOD’06). SpringerVerlag, Berlin, Heidelberg, 115–126. https://doi.org/10.1007/11788911_10 [42] The pandas development team. 2020. pandas-dev/pandas: Pandas. https://doi. org/10.5281/zenodo.3509134 [43] Liana Patel, Siddharth Jha, Melissa Pan, Harshit Gupta, Parth Asawa, Carlos Guestrin, and Matei Zaharia. 2025. Semantic Operators and Their Optimization: Enabling LLM-Based Data Processing with Accuracy Guarantees in LOTUS. Proc. VLDB Endow. 18, 11 (July 2025), 4171–4184. https://doi.org/10.14778/3749646. 3749685 [44] Pratyush Patel, Esha Choukse, Chaojie Zhang, Aashaka Shah, Íñigo Goiri, Saeed Maleki, and Ricardo Bianchini. 2024. Splitwise: Efficient generative llm inference using phase splitting. In 2024 ACM/IEEE 51st Annual International Symposium on

REFERENCES [1] [n.d.]. allenai/us-patents · Datasets at Hugging Face. https://huggingface.co/ datasets/allenai/us-patents [2] [n.d.]. Data Types and In-Memory Data Model — Apache Arrow v25.0.0. https: //arrow.apache.org/docs/python/data.html [3] [n.d.]. Enrich data using AI Functions. https://docs.databricks.com/aws/en/largelanguage-models/ai-functions [4] [n.d.]. Machine learning and AI functions in GoogleSQL. https://docs.cloud. google.com/spanner/docs/reference/standard-sql/ml-functions [5] [n.d.]. pyspark.sql.DataFrame. https://spark.apache.org/docs/latest/api/python/ reference/pyspark.sql/api/pyspark.sql.DataFrame.html [6] [n.d.]. SQL reimagined for the AI era with BigQuery AI functions. https://cloud.google.com/blog/products/data-analytics/sql-reimaginedfor-the-ai-era-with-bigquery-ai-functions [7] Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav Gulavani, Alexey Tumanov, and Ramachandran Ramjee. 2024. Taming { Throughput-Latency } tradeoff in { LLM } inference with { Sarathi-Serve } . In 18th USENIX symposium on operating systems design and implementation (OSDI 24). 117–134. [8] Ron Avnur and Joseph M. Hellerstein. 2000. Eddies: continuously adaptive query processing. In SIGMOD 2000. 261–272. https://doi.org/10.1145/342009.335420 [9] Shivnath Babu, Pedro Bizarro, and David DeWitt. 2005. Proactive re-optimization. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data (Baltimore, Maryland) (SIGMOD ’05). Association for Computing Machinery, New York, NY, USA, 107–118. https://doi.org/10.1145/1066157.1066171 [10] Fu Bang. 2023. GPTCache: An Open-Source Semantic Cache for LLM Applications Enabling Faster Answers and Cost Savings. In Proceedings of the 3rd Workshop for Natural Language Processing Open Source Software (NLP-OSS 2023), Liling Tan, Dmitrijs Milajevs, Geeticka Chauhan, Jeremy Gwinnup, and Elijah Rippeth (Eds.). Association for Computational Linguistics, Singapore, 212–218. https://doi.org/10.18653/v1/2023.nlposs-1.24 [11] Pedro Bizarro, Shivnath Babu, David DeWitt, and Jennifer Widom. 2005. Contentbased routing: different plans for different data. In Proceedings of the 31st International Conference on Very Large Data Bases (Trondheim, Norway) (VLDB ’05). VLDB Endowment, 757–768. [12] Umar Butler. 2025. Open Australian Legal Corpus. https://doi.org/10.57967/hf/ 2784 [13] Surajit Chaudhuri and Kyuseok Shim. 1999. Optimization of queries with userdefined predicates. ACM Transactions on Database Systems (TODS) 24, 2 (1999), 177–228. [14] Transaction Processing Performance Council. 2026. TPC-H Benchmark. https: //www.tpc.org/tpch/ [15] Hanjun Dai, Bethany Y Wang, Xingchen Wan, Bo Dai, Sherry Yang, Azade Nova, Pengcheng Yin, Phitchaya M Phothilimthana, Charles Sutton, and Dale Schuurmans. 2024. Uqe: A query engine for unstructured databases. Advances in Neural Information Processing Systems 37 (2024), 29807–29838. [16] DeepSeek-AI. 2026. DeepSeek-V4.1-Flash Technical Report. https: //huggingface.co/deepseek-ai/DeepSeek-V4.1-Flash/blob/main/DeepSeek_ V41_Tech_Report.pdf. [17] Karel D’Oosterlinck, François Remy, Johannes Deleu, Thomas Demeester, Chris Develder, Klim Zaporojets, Aneiss Ghodsi, Simon Ellershaw, Jack Collins, and Christopher Potts. 2023. BioDEX: Large-Scale Biomedical Adverse Drug Event Extraction for Real-World Pharmacovigilance. In Findings of the Association for Computational Linguistics: EMNLP 2023, Houda Bouamor, Juan Pino, and Kalika Bali (Eds.). Association for Computational Linguistics, Singapore, 13425–13454. https://doi.org/10.18653/v1/2023.findings-emnlp.896 [18] Goetz Graefe. 1994. Volcano - an extensible and parallel query evaluation system. IEEE Transactions on Knowledge and Data Engineering 6, 1 (1994), 120–135. [19] Peter J Haas and Joseph M Hellerstein. 1999. Ripple joins for online aggregation. In Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data. 287–298. [20] Oktie Hassanzadeh and Dharmashankar Subramanian. 2026. Semantic Views: Certified Reuse of LLM Labels Across Semantic Queries. arXiv preprint arXiv:2610.12768 (2026). [21] Joseph M Hellerstein and Michael Stonebraker. 1993. Predicate migration: Optimizing queries with expensive predicates. In SIGMOD 1993. 267–276. [22] Kaisong Huang, Jiatang Zhou, Zhuoyue Zhao, Dong Xie, and Tianzheng Wang. 2025. Low-Latency Transaction Scheduling via Userspace Interrupts: Why Wait or Yield When You Can Preempt? Proc. ACM Manag. Data 3, 3, Article 182 (June 2025), 25 pages. https://doi.org/10.1145/3725319 [23] Navin Kabra and David J DeWitt. 1998. Efficient mid-query re-optimization of sub-optimal query execution plans. In Proceedings of the 1998 ACM SIGMOD international conference on Management of data. 106–117. [24] Gaurav Tarlok Kakkar, Jiashen Cao, Pramod Chunduri, Zhuangdi Xu, Suryatej Reddy Vyalla, Prashanth Dintyala, Anirudh Prabakaran, Jaeho Bang, Aubhro Sengupta, Kaushik Ravichandran, Ishwarya Sivakumar, Aryan Rajoria, Ashmita Raju, Tushar Aggarwal, Abdullah Shah, Sanjana Garg, Shashank Suman, 13

Computer Architecture (ISCA). IEEE, 118–132. [45] Haoran Qiu, Weichao Mao, Archit Patke, Shengkun Cui, Saurabh Jha, Chen Wang, Hubertus Franke, Zbigniew Kalbarczyk, Tamer Başar, and Ravishankar K Iyer. 2024. Power-aware deep learning model serving with {𝜇 -Serve } . In 2024 USENIX Annual Technical Conference (USENIX ATC 24). 75–93. [46] Francisco Romero, Johann Hauswald, Aditi Partap, Daniel Kang, Matei Zaharia, and Christos Kozyrakis. 2022. Optimizing Video Analytics with Declarative Model Relationships. Proc. VLDB Endow. 16, 3 (Nov. 2022), 447–460. https: //doi.org/10.14778/3570690.3570695 [47] Matthew Russo, Tatsunori Hashimoto, Daniel Kang, Yi Sun, and Matei Zaharia. 2023. Accelerating Aggregation Queries on Unstructured Streams of Data. Proceedings of the VLDB Endowment 16, 11 (2023), 2897–2910. [48] Matthew Russo, Chunwei Liu, Sivaprasad Sudhir, Gerardo Vitagliano, Michael Cafarella, Tim Kraska, and Samuel Madden. 2025. Abacus: A Cost-Based Optimizer for Semantic Operator Systems. arXiv preprint arXiv:2505.14661 (2025). [49] Luis Gaspar Schroeder, Aditya Desai, Alejandro Cuadron, Kyle Chu, Shu Liu, Mark Zhao, Stephan Krusche, Alfons Kemper, Matei Zaharia, and Joseph E Gonzalez. 2025. vcache: Verified semantic prompt caching. arXiv preprint arXiv:2502.03771 (2025). [50] P. Griffiths Selinger, Morton M Astrahan, Donald D Chamberlin, Raymond A Lorie, and Thomas G Price. 1979. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data. 23–34. [51] Shreya Shankar, Tristan Chambers, Tarak Shah, Aditya G Parameswaran, and Eugene Wu. 2025. DocETL: Agentic Query Rewriting and Evaluation for Complex Document Processing. Proceedings of the VLDB Endowment 18, 9 (2025), 3035– 3048. [52] Biao Sun, Ziming Huang, Hanyu Zhao, Wencong Xiao, Xinyi Zhang, Yong Li, and Wei Lin. 2024. Llumnix: Dynamic scheduling for large language model serving. In 18th USENIX symposium on operating systems design and implementation (OSDI 24). 173–191. [53] Ji Sun, Guoliang Li, Peiyao Zhou, Yihui Ma, Jingzhe Xu, and Yuan Li. 2025. Agenticdata: An agentic data analytics system for heterogeneous data. arXiv preprint arXiv:2508.05002 (2025). [54] Immanuel Trummer. 2025. Implementing Semantic Join Operators Efficiently. arXiv preprint arXiv:2510.08489 (2025). [55] Midhul Vuppalapati, Justin Miron, Rachit Agarwal, Dan Truong, Ashish Motivala, and Thierry Cruanes. 2020. Building an elastic query engine on disaggregated storage. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20). 449–462. [56] Annita N Wilschut and Peter MG Apers. 1991. Dataflow query execution in a parallel main-memory environment. In Proceedings of the First International Conference on Parallel and Distributed Information Systems (PDIS). IEEE, 68–77. [57] Bingyang Wu, Yinmin Zhong, Zili Zhang, Shengyu Liu, Fangyue Liu, Yuanhang Sun, Gang Huang, Xuanzhe Liu, and Xin Jin. 2023. Fast distributed inference serving for large language models. arXiv preprint arXiv:2305.05920 (2023). [58] Renzhi Wu, Pramod Chunduri, Ali Payani, Xu Chu, Joy Arulraj, and Kexin Rong. 2024. SketchQL: Video Moment Querying with a Visual Query Interface. Proc. ACM Manag. Data 2, 4, Article 204 (Sept. 2024), 27 pages. https://doi.org/10. 1145/3677140 [59] An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, et al. 2025. Qwen3 technical report. arXiv preprint arXiv:2505.09388 (2025). [60] Zhihui Yang, Zuozhi Wang, Yicong Huang, Yao Lu, Chen Li, and X Sean Wang. 2022. Optimizing machine learning inference queries with correlative proxy models. arXiv preprint arXiv:2201.00309 (2022). [61] Junyi Zhao, Huanchen Zhang, and Yihan Gao. 2023. Efficient query reoptimization with judicious subquery selections. Proceedings of the ACM on Management of Data 1, 2 (2023), 1–26. [62] Junhao Zhu, Lu Chen, Xiangyu Ke, Ziquan Fang, Tianyi Li, Yunjun Gao, and Chrisitian S Jensen. 2026. Beyond Relational: Semantic-Aware Multi-Modal Analytics with LLM-Native Query Optimization. Proceedings of the ACM on Management of Data 4, 1 (SIGMOD (2026), 1–25.

14

A

Lemma 3 (Join multiplicity). Every reachable plan 𝑄 with 𝐽 joins satisfies |L (𝑄)| ≥ 2 𝐽 .

PROOFS OF PLAN ENUMERATION PROPERTIES

Fix a plan 𝑇 with operator set 𝑉 , |𝑉 | = 𝑁 , and 𝐽 joins. Operators are labeled; read sets are nonempty and origin-qualified, so each admissible join crossing selects a unique input branch. Let R (𝑇 ) be its closure under admissible swaps and E0 (𝑇 ) its memoized plan set without pruning.

A.1

Proof. Fix 𝜆 ∈ L (𝑄) ⊆ L (𝑃) and a join 𝑗 with nonempty input subtrees 𝑄 𝐿 , 𝑄 𝑅 . Let 𝜆𝐿 , 𝜆𝑅 be the restrictions of 𝜆 to their operators. These branches are incomparable, so every shuffle preserving 𝜆𝐿 and 𝜆𝑅 represents the same join with unchanged inputs. In particular, 𝜆 𝐿 𝜆 𝑅 ≠ 𝜆𝑅 𝜆 𝐿 .

Plan Space

Replace the branch subsequence of 𝜆 by either concatenation, choosing one different from the original subsequence and keeping all other positions unchanged. This gives a distinct member of L (𝑄) representing the same plan. More generally, writing 𝑎 = |𝑄 𝐿 |, 𝑏 = |𝑄 𝑅 |, and 𝑒 (𝑄) = |L (𝑄)|,   𝑎 +𝑏 𝑒 (𝑄 𝑗 ) = 𝑒 (𝑄 𝐿 )𝑒 (𝑄 𝑅 ) ≥ 2𝑒 (𝑄 𝐿 )𝑒 (𝑄 𝑅 ). 𝑎

Proposition 1 (Plan Space). For the forest 𝐹 defined below, 𝑁! |R (𝑇 )| ≤ 𝐽 Î . 2 𝑣 ∈𝑉 ℎ 𝐹 (𝑣) Dependency poset. Write 𝑢 ≺𝐷 𝑣 for transitive producer–consumer dependence and 𝑢 ≺𝑄 𝑣 when 𝑢 is a proper descendant of 𝑣 in plan 𝑄. Let 𝐵 contain the precedence constraints imposed by the fixed skeleton and noncrossable boundaries. Retaining these constraints from 𝑇 gives 𝑃 = (𝑉 , ≺𝑃 ),

A unary root leaves 𝑒 unchanged. Induction over the plan tree therefore gives one factor of at least two per join, hence 𝑒 (𝑄) ≥ 2𝐽 . □

≺𝑃 = tc(≺𝐷 ∪𝐵),

with ≺𝑃 ⊆≺𝑄 for every 𝑄 ∈ R (𝑇 ), where tc denotes transitive closure. Let 𝐻 = Cov(𝑃) be its Hasse edges, directed from smaller to larger elements. For any poset 𝐴, write L (𝐴) for its linear extensions and 𝑒 (𝐴) = |L (𝐴)|. Uniform hook construction. Let 𝑃 = 𝑃1 ⊔ · · · ⊔ 𝑃𝑚 , where each component 𝑃𝑖 has a tree Hasse diagram and a unique maximal or unique minimal element 𝑟𝑖 . Dualize precisely the reverse-rooted components: ( 𝑚 Ä 𝑃𝑖 , 𝑟𝑖 is maximal, 𝐹𝑖 = 𝑜𝑝 𝐹= 𝐹𝑖 . 𝑃𝑖 , 𝑟𝑖 is minimal, 𝑖=1

Proof of Proposition 1. First, distinct reachable plans have disjoint linear-extension sets. Contracting row-wise paths leaves the same fixed skeleton in every plan; each row-wise operator’s admissible positions lie on one path because join crossings select a unique branch. Thus 𝑄 ≠ 𝑄 ′ either orders two operators oppositely within a row-wise path, or places a row-wise operator on opposite sides of a fixed operator. In either case, some 𝑢, 𝑣 satisfy 𝑢 ≺𝑄 𝑣,

so L (𝑄) ∩ L (𝑄 ′ ) = ∅. Since L (𝑄) ⊆ L (𝑃), the preceding lemmas give ∑︁ |L (𝑄)| 2 𝐽 |R (𝑇 )| ≤

For a singleton, either choice agrees. Each 𝐹𝑖 is a rooted tree with unique maximum 𝑟𝑖 . Its hook is uniformly the subtree size ℎ 𝐹 (𝑣) = |{𝑢 ∈ 𝑃𝑖 : 𝑣 lies on the path from 𝑢 to 𝑟𝑖 }|.

𝑄 ∈ R (𝑇 )

Equivalently, using reflexive orders, ( |{𝑢 : 𝑢 ⪯𝑃𝑖 𝑣 }|, 𝑟𝑖 is maximal, ℎ 𝐹 (𝑣) = |{𝑢 : 𝑣 ⪯𝑃𝑖 𝑢}|, 𝑟𝑖 is minimal.

=

Ø

L (𝑄)

𝑄 ∈ R (𝑇 )

≤ 𝑒 (𝑃) = Î

Lemma 2 (Uniform hook formula). With this construction, 𝑁! 𝑒 (𝑃) = 𝑒 (𝐹 ) = Î . (1) 𝑣 ∈𝑉 ℎ 𝐹 (𝑣)

𝑁! . 𝑣 ∈𝑉 ℎ 𝐹 (𝑣)

Dividing by 2 𝐽 proves |R (𝑇 )| ≤ 2 𝐽 Î 𝑁 ! ℎ (𝑣) . 𝑣 ∈𝑉

A.2

Proof. Given 𝜆 ∈ L (𝑃), reverse its subsequence on each dualized component, leaving the positions occupied by that component unchanged. This involution gives a bijection L (𝑃) ←→ L (𝐹 ). Let 𝑛𝑖 = |𝑃𝑖 |. Applying Knuth’s formula [31] to each rooted 𝐹𝑖 and interleaving the components gives  Ö 𝑚 𝑁 𝑒 (𝑃) = 𝑒 (𝐹 ) = 𝑒 (𝐹𝑖 ) 𝑛 1, . . . , 𝑛𝑚 𝑖=1

𝐹

□

MECE

Proposition 2 Every memoized plan is equivalent to 𝑇 and memoized once, and E0 (𝑇 ) = R (𝑇 ). Ð Memoization Algorithm 3 and Algorithm 4 use set operation to iteratively include newly enumerated partitions into a set of seeds while making each member in the set unique. Then it calls the Merge operation to overwrite the current position in the plan 𝑇 with the new partition(s). It is obvious that, when the merged partitions are different, the resulting full plan 𝑇 ′ after Merge is also different. In actual implementation, to prevent duplicates in plan enumeration, we leverage a compact position vector to flag whether the algorithms have generated the same partition before. Position vector. Given an anchor join 𝑗 and a labeled operator list 𝑊 = (𝜔 1, . . . , 𝜔𝑚 ) covering the local transformation. Number the

𝑚 𝑛𝑖 ! 𝑁! Ö Î =Î 𝑖 𝑛𝑖 ! 𝑖=1 𝑣 ∈𝑃𝑖 ℎ 𝐹 (𝑣)

=Î

𝑣 ≺𝑄 ′ 𝑢,

𝑁! . 𝑣 ∈𝑉 ℎ 𝐹 (𝑣) □ 15

Algorithm 6 Cost Propagation

three arms of 𝑗 by 0 (above), 1 (left), and 2 (right). For each 𝜔𝑖 , let 𝑏𝑖 be its arm and 𝑟𝑖 ≥ 1 its rank counting outward from 𝑗. Define p 𝑗 (𝑃) = (𝑝 1, . . . , 𝑝𝑚 ),

Require: {𝐾𝑜𝑝 , 𝑟𝑜𝑝 }𝑜𝑝 ∈𝑇 from the preceding SLM profiling 1: function PopulateProfile(𝑇 , {𝐾𝑜𝑝 , 𝑟𝑜𝑝 , 𝐶𝑎𝑐ℎ𝑒𝑜𝑝 }) 2: 𝐶←0 3: 𝛼𝑜𝑝 ← 1 for all 𝑜𝑝 ∈ 𝑇 4: for all joins 𝑗 ∈ 𝑇 do 5: (𝐿 𝑗 , 𝑅 𝑗 ) ← outer and inner source-batch counts, each at least 1 6: 𝛼𝑜𝑝 ← 𝛼𝑜𝑝 /𝑅 𝑗 for 𝑜𝑝 ∈ 𝑜𝑢𝑡𝑒𝑟 ( 𝑗) 7: 𝛼𝑜𝑝 ← 0 if the inner side is materialized; otherwise 𝛼𝑜𝑝 /(𝐿 𝑗 𝑅 𝑗 ), for 𝑜𝑝 ∈ 𝑖𝑛𝑛𝑒𝑟 ( 𝑗)

𝑝𝑖 = 3(𝑟𝑖 − 1) + 𝑏𝑖 + 1.

Each entry uniquely determines its arm and rank; hence, for fixed 𝑗,𝑊 , p 𝑗 (𝑃) = p 𝑗 (𝑃 ′ ) ⇔ 𝑃 = 𝑃 ′ . Lemma 4 (Coverage). Starting from the promoted seed, unpruned within- and across-partition pushdown visits every admissible partition configuration through its layer-by-layer decomposition, possibly repeatedly.

return 𝐶

10: 11: 12: 13: 14: 15:

(i) Assume 𝑄 is missing. Since the promoted seed is compatible, there is a first failure: F𝑘+1 (𝑄) = ∅.

(ii) Choose 𝑆 ∈ F𝑘 (𝑄). In each current chain 𝑊 , let 𝐷 contain the operators placed below the join in 𝑄 and set 𝑈 = 𝑊 \ 𝐷. Validity of 𝑄 implies

B

SPECULATIVE PROFILING

We specify the propagation of costs in speculative profiling. For subquery plan 𝑇 , 𝐶 is the estimated cost. Operator 𝑜𝑝 has input and output tuples 𝐼𝑜𝑝 , 𝑅𝑜𝑝 , result mask 𝐾𝑜𝑝 , cost per evaluation 𝑟𝑜𝑝 , amortization factor 𝛼𝑜𝑝 , and uncached evaluation count 𝑛𝑜𝑝 . The evaluation-key map 𝜋𝑜𝑝 uses relevant source-row identities for filters and projections, full tuple identities for joins or unknown dependencies. The cache 𝐶𝑎𝑐ℎ𝑒𝑜𝑝 maps these keys to filter decisions or projected values and is empty for uncached operators. Let dom(𝐶𝑎𝑐ℎ𝑒𝑜𝑝 ) be the cache key set. For join 𝑗, 𝐿 𝑗 , 𝑅 𝑗 ≥ 1 count outer and inner source batches, outer( 𝑗), inner( 𝑗) are its child subtrees, and 𝑜𝑝 𝐿 , 𝑜𝑝 𝑅 denote the two children of a join. Algorithm 6 details the PropulateProfile function from line 15 of Algorithm 5, where the obtained full-batch masks of each operator is used to compute the exact cost of each candidate plan 𝑇 . By applying intersection to the per-operator masks, we can compute costs with any ordering of the set of profiled operators.

𝑥 ∈ 𝑊 , 𝑦 ∈ 𝐷, 𝑥 ≺𝐷 𝑦 =⇒ 𝑥 ∈ 𝐷. (iii) Thus 𝐷 is an order ideal. For a topological order 𝜋𝐷 and 𝜋𝑈 = 𝑄 |𝑈 , 𝜋𝐷 𝜋𝑈 ∈ ApplyPermute(𝑑𝑒𝑝_𝑔𝑟𝑝𝑠). (iv) Target validity makes every operator in 𝐷 crossable, with producers crossing first. Across-partition pushdown emits the prefix |𝐷 |, fixing 𝑈 and transferring 𝐷 to its target branches. Cartesian products of these choices give 𝑆 ′ ∈ F𝑘+1 (𝑄), contradicting (i). At terminal chains, 𝐷 = ∅ and permutation alone fixes their order. Therefore no admissible 𝑄 is missing. □ Proof of Proposition 2. By Lemma 4, every partition contributes all admissible variants. Cartesian products and Merge assemble every compatible full plan and recursion covers all layers. Since every transformation is admissible,   supp 𝑉 𝑖𝑠𝑖𝑡𝑒𝑑 (𝑇 ) = R (𝑇 ). The complete tuple of labeled partition position vectors uniquely determines the merged plan. Memoizing only unseen tuples retains exactly one copy of each visited plan. Hence E0 (𝑇 ) = R (𝑇 ), with every member stored once, establishing MECE.

17:

9:

F𝑘 (𝑄) = V𝑘 ∩ C𝑘 (𝑄).

F𝑘 (𝑄) ≠ ∅,

16:

for all operators 𝑜𝑝 in 𝑇 , children before parents do if 𝑜𝑝 is a scan then 𝑅𝑜𝑝 ← 𝐾𝑜𝑝 else 𝐼𝑜𝑝 ← 𝑅𝑜𝑝 𝐿 × 𝑅𝑜𝑝 𝑅 for a join; otherwise 𝑅𝑐ℎ𝑖𝑙𝑑 (𝑜𝑝 ) 𝑅𝑜𝑝 ← ApplyMask(𝐼𝑜𝑝 , 𝐾𝑜𝑝 , 𝐶𝑎𝑐ℎ𝑒𝑜𝑝 ) if 𝑜𝑝 is semantic then 𝑛𝑜𝑝 ← |𝜋𝑜𝑝 (𝐼𝑜𝑝 ) \ dom(𝐶𝑎𝑐ℎ𝑒𝑜𝑝 )| 𝐶 ← 𝐶 + 𝛼𝑜𝑝 𝑟𝑜𝑝 𝑛𝑜𝑝

8:

Proof. For a target 𝑄, let V𝑘 be the states visited at layer 𝑘. Let C𝑘 (𝑄) require agreement with 𝑄 on processed chains and placement of each remaining operator in its highest unprocessed chain on its path to 𝑄. Set

□ 16

Related documents

• The Stretto Execution Engine for Semantic Data Systems#1298044
• Natural Language Knowledge Graph Query Execution: Leveraging Controlled Semantics in the LLM Context Window#1084587
• Natural Language Knowledge Graph Query Execution: Leveraging Controlled Semantics in the LLM Context Window#919517
• NL2SQLBench: A Modular Benchmarking Framework for LLM-Enabled NL2SQL Solutions#120627
• SemPlan: Benchmarking Structured Semantic Planning for LLM-Based Queries over Enterprise Data#458353