GraftDB: Dynamic Folding of Concurrent Analytical Queries Genki Kimura
Kazuo Goda
The University of Tokyo Tokyo, Japan [email protected]
The University of Tokyo Tokyo, Japan [email protected] time
arXiv:2606.04303v1 [cs.DB] 3 Jun 2026
ABSTRACT Analytical database systems serve as foundational infrastructure for knowledge discovery across many domains. Day after day, researchers, practitioners, and increasingly AI-driven agents issue analytical queries, inspect their results, and refine their inquiries. An analytical database system thus receives and processes diverse analytical queries that arrive over time and execute concurrently. Such workloads can create redundant execution work across independently issued queries. Exploiting this overlap to optimize query processing as a whole is a critical technical challenge. This paper presents GraftDB, a multi-query execution engine that dynamically folds a later-arriving query into a running execution, reusing previously performed work and sharing subsequently performed work. GraftDB achieves dynamic folding with statecentric execution, which treats operator state accumulated during execution not as owned by a single query, but as shared state that any compatible query can observe or contribute to. Each query observes shared state through a per-query state lens, which lets the query observe that state only after the relevant input has been incorporated and receive only rows or state fragments valid under the query’s semantics. For an arriving query, query grafting identifies operator state that already satisfies part of the query’s requirements and work that can still be shared to satisfy the rest. Together, these mechanisms let GraftDB share work across overlapping analytical queries and reduce redundant execution work. Experiments using TPC-H-derived instances of dynamic concurrent workloads show that GraftDB achieves up to 2.17 times higher throughput than a same-engine isolated-execution baseline. Under overloaded open-loop arrivals, GraftDB reduces P95 response time to as low as 0.17 times the same baseline’s P95 response time.
Artifact Availability: Artifact materials are available at https://github.com/dbc-utokyoiis/GraftDB.
1
INTRODUCTION
Analytical database systems support many forms of data analysis. Human analysts, applications, and AI-driven agents independently issue analytical queries over shared data [38, 70]. Together, these sources create dynamic concurrent workloads, in which analytical queries arrive over time, query executions overlap, and the active query set changes while the system is running [51, 67]. A central opportunity in such workloads is to reduce redundant work across queries that coexist in time. An arriving query may differ from already-running queries in parameters, predicates, and arrival time, but it may still require much of the same underlying computation. If each query runs in isolation, the system repeats parts of that computation across concurrent executions.
QA
QE
Isolated Execution
QB QC
QD time
Dynamic Folding
{QA} {QA,QB} {QA,QB,QC}
{QB,QC} {QB} {QB,QD} {QB,QD,QE} {QD,QE} leave QA
leave QC
leave QB
Figure 1: Dynamic folding integrates arriving analytical queries into an evolving shared execution. In isolated execution, overlapping queries run separately. In dynamic folding, the shared execution carries the current set of attached queries and changes that set as queries arrive and complete.
Prior systems reduce such redundancy in several ways. Some systems reuse a stored result, a materialized view, or an intermediate result saved before the query runs [27, 30, 39, 49]. Other systems optimize a known set of queries and create shared plans before execution [22, 24, 25, 41, 56, 58, 71]. Runtime-sharing systems coordinate scans, operator pipelines, or shared joins while queries are running [4, 9, 29, 63, 72]. These approaches share work through saved results, known query sets, scans, pipelines, or join structures. Dynamic concurrent workloads create another opportunity inside a running execution. While a query is executing, its stateful operators accumulate operator state such as hash tables and aggregate accumulators. When a later query arrives, part of that operator state may already satisfy part of the query’s requirements, and the running execution may still have work remaining that can contribute the rest to the same state. The challenge is to make this partially accumulated, still-changing state safely usable across queries with different predicates, parameters, and arrival times. Dynamic folding is an execution strategy for dynamic concurrent workloads. Rather than executing an arriving query in isolation, it folds the query into a running execution: the query reuses compatible operator state already accumulated there, shares subsequent computation that contributes to the same state, and leaves when its own work completes. Figure 1 illustrates the difference between conventional isolated execution, where overlapping queries run separately, and dynamic folding, where arriving queries attach to an evolving shared execution and leave when their work completes. We present GraftDB, a multi-query execution engine for dynamic concurrent workloads. GraftDB achieves dynamic folding with state-centric execution, which treats the state of stateful operators, such as hash joins and aggregations, not as state owned by the query that first produced it, but as shared state that any compatible query can observe or contribute to. Two runtime mechanisms make this practical. A per-query state lens lets each query
Genki Kimura and Kazuo Goda
observe shared state under that query’s semantics: it determines which part of the state is complete for the query and which rows or state fragments the query may receive. Query grafting attaches an arriving query to compatible shared state by identifying both the state already present and the producer work that can still contribute to it. Together, per-query state lenses and query grafting let GraftDB share state across queries while preserving each query’s semantics. This paper makes the following contributions. (1) We introduce state-centric execution for dynamic concurrent workloads. It treats operator state as shared state and makes that state the unit of sharing. (2) We design the runtime mechanisms that support dynamic folding over shared state. Per-query state lenses use coverage metadata and per-query visibility metadata to define what each query may observe, while query grafting attaches arriving queries to compatible shared state. (3) We implement GraftDB and evaluate it on dynamic concurrent workloads generated from TPC-H templates. GraftDB achieves up to 2.17 times higher throughput than the isolated baseline and, under overloaded open-loop arrivals, reduces P95 response time to as low as 0.17 times the isolated baseline’s P95 response time. The remainder of the paper is organized as follows. Section 2 discusses prior ways to share analytical work and motivates shared state as the unit of sharing. Section 3 introduces GraftDB’s execution model and illustrates dynamic folding over shared state. Section 4 defines per-query state lenses over shared state. Section 5 describes query grafting and the runtime scheduling of folded queries. Section 6 evaluates GraftDB on dynamic concurrent workloads and separates the effects of its dynamic-folding mechanisms. Section 7 discusses related work, and Section 8 concludes.
2
BACKGROUND AND MOTIVATION
Prior analytical work sharing reuses work through stored results, known query sets, and scans, pipelines, or joins coordinated during execution. Dynamic concurrent workloads further expose partially produced operator state as a sharing unit. Existing mechanisms reduce redundant analytical work by choosing a unit that can be shared. Stored-result and materialized-view approaches share saved artifacts once compatible work has been completed and recorded [27, 30, 39, 49]. Multi-query optimization and batched shared-execution approaches share plans, subplans, or execution cycles chosen for a known query set before that shared unit runs [22, 24, 25, 41, 56, 58]. Runtime-sharing systems move the sharing decision into execution by coordinating scans, operator pipelines, shared joins, or data-routing paths while queries are running [4, 9, 29, 63, 72]. Together, these mechanisms show that the sharing unit matters: saved artifacts, planned query sets, and running execution structures expose different places where redundant analytical work can be reduced. Stateful operators expose another unit of reuse inside a running execution. A hash table records build-side work that later probes need, and aggregate state records groups and results that later aggregate computations need. When concurrent analytical queries require overlapping state, state built for one query may also be
useful to a later query. If that state remains private to the query that first created it, the later query must rebuild overlapping work. This state differs from both a stored result and a single logical result. It may still be incomplete and changing when a later query arrives, so the query must know what is already present and what the running execution can still add. It may also have different meanings for different queries because each query may need a different logical slice of the same physical state. These properties motivate state-centric execution, where sharing is organized around shared state already produced by a running execution and the work that can still contribute to it.
3
GRAFTDB OVERVIEW: STATE-CENTRIC EXECUTION FOR DYNAMIC FOLDING 3.1 State-centric Execution Architecture State-centric execution is GraftDB’s execution model for dynamic folding. It organizes a dynamic concurrent workload as one evolving shared execution over shared state. Stateful operators maintain hash tables and aggregate states as shared state that multiple queries can observe or contribute to. This organization lets a later-arriving query attach to the running execution by observing compatible state already built there and sharing producer work that can still contribute to it. Figure 2 shows the execution architecture of state-centric execution. First, GraftDB represents arriving queries as ordinary single-query plans. It then attaches those plans to the shared execution DAG, which records the operator work that remains in the shared execution. The DAG contains ordinary operator work, work that can contribute to shared states, and state-lens observations that depend on those states. As the shared execution advances, the ready-fragment extractor uses the DAG and the current status of shared states and input sources to select fragments whose requirements are satisfied. The executor advances those fragments by scanning base tables, contributing to shared hash tables and aggregate states, and applying per-query state lenses to shared state to produce each query’s result. A query does not observe the whole physical contents of a shared state. Instead, a per-query state lens selects the entries or state fragments visible under that query’s semantics, without materializing a separate per-query copy. Different queries can therefore share the same physical state while receiving only the state fragments visible through their own state lenses.
3.2
Query Scope and Sharing Units
GraftDB targets finite analytical SELECT queries that can be represented as acyclic relational operator plans built from base-table scans, selections, projections, hash joins, and aggregations. In this paper, a query is eligible to fold into a shared execution only when it reads the same read-only database snapshot as that execution. Coverage metadata therefore describes completeness over one stable input version. Queries may differ in predicates, constants, and surrounding operator structure within this plan class. Dynamic folding uses compatible stateful boundaries as the comparison unit, so different query plans can still share state where their stateful requirements are compatible.
GraftDB: Dynamic Folding of Concurrent Analytical Queries
GraftDB
Ready Fragment
Shared Execution DAG
Agg
Agg Query Q1
Single-Query Plan P1
Probe Agg
Query Q2
Readyfragment Extractor
Build
Scan
Result Q1
Scan Result Q2
Shared States - Hash Tables - Aggregate States
Build Scan
Probe
shared-state status
Probe
Single-Query Plan P2
Build
Scan
contribute Executor
scan Base Tables
observe
Figure 2: State-centric execution architecture. GraftDB first represents arriving queries as ordinary single-query plans and attaches them to a shared execution DAG. GraftDB extracts ready fragments using the current status of shared states and input sources, then executes those fragments by scanning base tables, contributing to shared hash tables and aggregate states, and observing shared state through per-query state lenses.
3.3
Folding a Later Query into Shared State
Dynamic folding becomes concrete when an arriving query can observe state maintained by the shared execution. At each stateful boundary, GraftDB compares the query’s required state-side input with a compatible shared state and partitions that input into three extents. The represented extent is already complete in the selected state; the residual extent can still be contributed to that state by an admitted producer path; and the unattached extent remains ordinary-plan work. This partition lets a later query observe state built before it arrived and share producer work performed after it arrived. For a hash join, the attachment decision concerns the build-side rows represented by the hash table. The probe rows have a different role. They do not contribute build entries to the hash table; they drive lookups into it. A folded hash-probe step can therefore run only after the shared hash table represents the represented and residual build-side extents assigned to the query, and after the probe rows for that query are available. We use two TPC-H Q3-derived queries as a running hash-join instance. Figure 3 focuses on the order-side hash table and the per-query state lenses over it. The instance isolates one hash-join
(earlier)
Build
observe
contribute
Lens for QA
represented
Probe
o_orderdate
1995-03-20
QA
1995-03-15
The current design shares two kinds of operator state: hashbuild state and aggregate state. For hash joins, a later query may observe represented build-side extents through a per-query state lens, while admitted producer work contributes residual build-side extents to the same hash-build state. Probe-side input remains a consumer-side data-flow requirement and does not itself define residual build-side work. For aggregations, sharing is admitted only under exact aggregate identity: the aggregate input, per-query input condition, grouping keys, aggregate functions, and distinct-argument semantics must match. When this identity holds, compatible queries may share aggregate production or observe a completed aggregate state. A completed aggregate state remains tied to that identity; different predicates or grouping rules produce separate aggregate states.
Shared Hash Table
residual
Lens for QB
QB (later)
Build arrives later
contribute
observe
Probe
Figure 3: Folding a later query into a shared order-side hash table. 𝑄 𝐴 arrives first and constructs the initial order-date range. When 𝑄 𝐵 arrives later with a broader order-date predicate, GraftDB lets 𝑄 𝐵 observe the already-built range as its represented extent and contributes the missing date band through residual producer work to the same hash table. Each query receives only the entries selected by its state lens.
boundary so that already-present state-side input, residual producer work, and probe rows are visible in one place. Both queries use the following parameterized SQL skeleton: SELECT l_orderkey, sum(l_extendedprice * (1 - l_discount)) AS revenue, o_orderdate, o_shippriority FROM customer, orders, lineitem WHERE c_mktsegment = :segment AND c_custkey = o_custkey AND o_orderdate < :date AND l_orderkey = o_orderkey AND l_shipdate > :date
Genki Kimura and Kazuo Goda
GROUP BY o_orderdate, o_shippriority, l_orderkey
Both queries use :segment = ’BUILDING’. Query 𝑄 𝐴 arrives first with :date = DATE ’1995-03-15’, and query 𝑄 𝐵 arrives later with :date = DATE ’1995-03-20’. In this example, 𝑄 𝐵 therefore has a broader order-side build predicate than 𝑄 𝐴 but a narrower lineitem probe predicate. For exposition, assume a fixed hash-join plan. The plan builds customer-side state for customers satisfying c_mktsegment = ’BUILDING’, builds order-side state for orders that match the customer state and satisfy o_orderdate < :date, and then probes the order-side hash table with lineitem rows satisfying l_shipdate > :date. On the order build side, 𝑄 𝐵 has the broader date predicate. Every order row satisfying 𝑄 𝐴 ’s bound, o_orderdate < DATE ’1995-03-15’, also satisfies 𝑄 𝐵 ’s bound, o_orderdate < DATE ’1995-03-20’. The range already constructed for 𝑄 𝐴 is therefore part of 𝑄 𝐵 ’s represented extent and is visible through 𝑄 𝐵 ’s state lens. The remaining order-date band for 𝑄 𝐵 , from DATE ’1995-03-15’ to before DATE ’1995-03-20’, belongs to 𝑄 𝐵 ’s residual extent if the current shared execution can still produce those order rows and add them to the same order-side hash table. Rows at or after DATE ’1995-03-20’ are outside 𝑄 𝐵 ’s build requirement. They are outside both 𝑄 𝐵 ’s represented and residual extents. 𝑄 𝐵 ’s state lens therefore excludes them even if another query later adds such rows to the same hash table. The lineitem side is different because it drives lookups into the order-side hash table rather than contributing entries to that table. Since 𝑄 𝐵 uses the later ship-date bound, only lineitem rows with l_shipdate > DATE ’1995-03-20’ drive 𝑄 𝐵 ’s hash-probe step. Rows with ship dates after DATE ’1995-03-15’ and at or before DATE ’1995-03-20’ can drive 𝑄 𝐴 ’s hash-probe step, but they are not part of 𝑄 𝐵 ’s residual extent because they are not missing order-side build rows. Shared scans and filters tag rows with the queries whose predicates they satisfy. 𝑄 𝐵 ’s shared hash-probe step becomes ready when the order-side hash table contains the build rows assigned to 𝑄 𝐵 and the lineitem rows for 𝑄 𝐵 are available.
4
STATE-LENS OBSERVATION OVER SHARED STATE
A state-lens observation is the point at which one query observes shared physical state under that query’s semantics. The lens combines two checks. Coverage metadata identifies when the selected state represents the relevant input, including the absence information needed for valid no-match results. Per-query visibility metadata identifies which materialized rows or state fragments may be emitted to the query.
4.1
Lens Descriptors and Extent Assignment
At a stateful boundary 𝑏 of query 𝑞, GraftDB considers a candidate shared state 𝑆. The candidate check uses three objects: a lens descriptor that describes the operator state needed by 𝑞, the state-side input that 𝑆 must represent, and any consumer-side input needed to drive the state-consuming operator. For a hash-probe step, the lens descriptor names the build relation, build keys, build-side predicates, payload layout, and required upstream state. For aggregate state, the lens descriptor records the
aggregate identity used to decide whether the state can support the query. The state-side input is the set of input occurrences that 𝑆 must represent for 𝑞. GraftDB identifies an occurrence by its derivation, not only by its payload value. Two equal-valued tuples therefore remain distinct when they come from different base rows or join derivations. This keeps duplicate-sensitive row identity explicit when multiple per-query state-lens observations share one state. After selecting 𝑆, GraftDB partitions the attached state-side input into three disjoint extents. The represented extent 𝐸 rep is the portion already represented by 𝑆 and assigned for observation through the state lens. The residual extent 𝐸 res is not yet represented, but an admitted producer path can produce those occurrences into 𝑆 before 𝑞 observes the state. The unattached extent 𝐸 un is not assigned to that lens and is executed as ordinary-plan work. The state-lens observation through 𝑆 is defined over 𝐸 rep ∪ 𝐸 res . This assignment applies only to state-side input. Hash-probe steps also require probe-side input. The hash table represents buildside input, while probe rows drive lookups into that table. A hash table may therefore be ready for a query’s build-side requirement before the corresponding probe-side input is available.
4.2
Predicate and Visibility Checks
Predicate compatibility is treated as containment rather than syntactic equality. The prototype stores state-side predicates in lens descriptors and the predicate component of coverage metadata as normalized predicate ASTs. For predicates 𝑃 and 𝑄 over comparable state-side attributes, GraftDB writes Prove(𝑃 ⇒ 𝑄) for a conservative proof that every occurrence satisfying 𝑃 also satisfies 𝑄. For hash-build state, let 𝑃𝑅 describe the predicate of a candidate represented extent 𝑅, let 𝐵𝑞 be query 𝑞’s required build-side predicate, and let 𝐶𝑆 describe an extent that state 𝑆’s coverage metadata records as complete. Assigning 𝑅 to the represented extent requires proving both Prove(𝑃𝑅 ⇒ 𝐵𝑞 ) and Prove(𝑃𝑅 ⇒ 𝐶𝑆 ). The checker is sound but incomplete. It implements Prove(𝑃 ⇒ 𝑄) by simplifying ¬𝑃 ∨𝑄 within a supported deterministic predicate fragment. The implemented cases cover conjunctions of deterministic comparisons between retained attributes and constants, together with limited Boolean simplifications introduced by the implication check. The checker canonicalizes equality predicates and lower and upper bounds on each retained attribute, then applies per-attribute range-containment rules independently over comparable scalar domains. Constant arithmetic already normalized into the predicate AST is handled as part of the same check. Predicate forms outside this fragment, including unsupported NULL-sensitive predicate forms, are treated as unproven. Unproven obligations are not used to classify an extent as represented: the corresponding input is considered for residual production, or left as ordinary-plan work if no admitted producer path can supply it. Thus failing to prove a valid implication may reduce sharing, but it cannot make an unsafe state-lens observation admissible. A visibility check also requires the relevant lens predicates to be evaluable on the retained state. Each predicate AST records the attributes it references, written FV(𝑃). A lens predicate 𝑃 is evaluable on entries of state 𝑆 only when FV(𝑃) ⊆ RetainedAttrs(𝑆),
GraftDB: Dynamic Folding of Concurrent Analytical Queries Shared Hash-build State S Base Signature: Orders by o_orderkey
Coverage Metadata
Hash Table Entries
Build-side Condition: c_mktsegment = 'BUILDING' AND o_orderdate < '1995-03-20' Covered Input: Orders[0...k] in scan order Requires: Customer-side state covered
key
derivation visible-to
payload (o_orderdate, o_shippriority)
o1
r17
{A, B}
(1995-03-10, 0)
o2
r48
{A, B}
(1995-03-12, 0)
o3
r88
{B}
(1995-03-18, 1)
Candidate-set Completeness
Visible Rows State Lens for QA
Predicate: c_mktsegment = 'BUILDING' AND o_orderdate < '1995-03-15'
Returns: Entries whose visible-to set contains A No-match is valid only within complete coverage
Figure 4: Shared hash-build state separates coverage from entry visibility. Coverage metadata describes the build-side predicate, processed input range, and upstream requirement that make a candidate set complete. Hash entries store concrete materialized rows together with per-query visibility metadata. A per-query state lens uses coverage metadata to determine where complete match sets and no-match results are meaningful, and visibility metadata to select the rows visible to that query.
where retained attributes include attributes stored with state entries and derivation metadata. If a later query requires an additional narrower predicate whose referenced attributes are not retained, GraftDB does not classify that part of the state-side extent as already represented. It belongs to the residual extent if an admitted producer path can supply it, or to the unattached extent otherwise. Rows and state entries carry per-query visibility metadata. Filters update that metadata according to each query’s predicate, and projections preserve derivation identity and visibility. A per-query state lens is therefore a visibility boundary rather than a separate physical copy of state. A physical producer or consumer step may serve several queries, provided each emitted row or state entry passes the corresponding visibility check.
4.3
Hash Tables as Shared Build State
A shared hash-build state contains a hash-table signature, coverage metadata, and hash entries. The hash-table signature fixes the build relation, build keys, payload layout, and required upstream state. Coverage metadata records the build-side extent for which the table is complete, while hash entries store keys, payload values, derivation identifiers, and entry-level visibility metadata. Figure 4 shows this separation on the order-side table. The table’s coverage metadata describes the represented order input, the buildside condition, and the required customer-side state. It does not enumerate returned rows. Instead, it records where the build-side extent is complete for compatible queries. Hash entries provide positive matches, while coverage metadata makes absence meaningful. For a probe occurrence visible to query 𝑞, the hash-probe step computes the probe key, finds candidate entries, and keeps only entries visible through 𝑞’s state lens. A visible entry can justify an output row because the matching entry
is present and visible. If no visible matching entry exists, the hashprobe step may report no match only when coverage metadata records the relevant build-side extent as complete for 𝑞. When a probe row is visible to several queries and the lookup target is shared, one physical hash-probe step can test candidate entries once and route each matching entry to the queries for which the visibility check succeeds. The same visibility discipline applies on the build path. When a produced build row is visible to several queries and targets the same hash table, GraftDB stores one build entry and records the visibility needed by those queries. The visibility sets in Figure 4 are logical notation: the runtime need not maintain a mutable set in every hash entry or rewrite existing entries when a later query is admitted. If a later query observes an already represented extent, GraftDB may record visibility at the state level for that extent. This state-level visibility is extent-scoped: it does not make every entry in the hash table visible to the query. Residual build-side extents for several admitted queries can therefore pass through the same physical producer path when the path and target table are shared, while each query later receives only the entries visible through its state lens. Before opening a hash-probe step, GraftDB first checks exact non-predicate compatibility: the relation, keys, payload layout, and required upstream state must match the candidate table. Predicate containment and evaluability are checked as described in Section 4.2. When the selected table represents the assigned build-side extent and the probe-side input is available, the state-lens observation runs as a per-query hash-probe step and emits joined rows allowed by the query’s predicates and join rule.
4.4
Residual Production through Shared Scans
Residual production contributes to a selected state through an admitted state-producing path. The path must be compatible with the selected state’s descriptor and operator rule. The residual extent for a boundary is the state-side portion not yet represented by the selected state that an admitted path can contribute to that state. The path determines the granularity at which the residual extent can be contributed to the selected state. Shared scans determine which admitted paths can still receive base input. GraftDB’s shared scans run in cycles over their input. Depending on the current scan state, the runtime may register a path that receives rows remaining in the current cycle, or a path that waits for a later cycle to deliver rows to the selected state. Rows before the current scan position do not belong to the residual extent merely because the scan will revisit input. They belong to the residual extent only when the attachment records a path that will deliver them to the selected state. An admitted scan path can contribute residual input for several queries when their paths target the same selected state. As the scan produces a row, filters update per-query visibility, and the shared execution routes the row once through the common producer path while preserving the visibility needed by each state lens. Scan progress and coverage metadata answer different questions. Scan progress determines when base rows can next be delivered by the shared scan, whereas coverage metadata determines which state-side extent the selected state already represents and where
Genki Kimura and Kazuo Goda Sum {QB}
complete match sets or no-match results are meaningful. A statelens observation opens only after the selected state represents the observation’s represented and residual extents.
4.5
HashBuild QA: x < 20
Aggregate Sharing
Aggregation follows the same rule with a stricter identity requirement. A query may observe completed aggregate state only when the aggregate input, per-query input condition, grouping keys, aggregate functions, and distinct-argument semantics match. Under this exact aggregate identity, the query observes a completed aggregate state with the identity recorded in the lens descriptor. Active queries can also share aggregate production when the current shared execution admits live sharing under the same aggregate identity. In that case, all compatible queries for that identity share one aggregate producer and one aggregate state. Aggregate sharing is exact-match active sharing: the aggregate descriptor fixes this identity, and compatible aggregate work contributes to the same state. Different aggregate definitions remain separate aggregate states. Unlike hash-build state, aggregate state collapses input occurrences into group accumulators, so a completed aggregate cannot be repartitioned under a different predicate or grouping rule without additional provenance or partial-aggregate state. This boundary preserves exact aggregate identity while still allowing compatible aggregate work to share one state.
4.6
Count {QA}
Opening State-Lens Observations
A state-lens observation is admitted for a query when the state-side occurrences for the selected state have a single assignment and a defined per-query state lens. The represented extent contains occurrences already represented by the selected state. The residual extent contains admitted occurrences that are produced into the same state before the observation opens. This condition keeps duplicate-sensitive row identity explicit. Occurrences identified by derivation remain distinct, and GraftDB does not duplicate them across represented and residual extents. It also restricts no-match results because absence is used only within the complete extent described by coverage metadata. If descriptor compatibility, extent completeness, aggregate identity, or an admitted path for a missing extent cannot be established, that extent is not assigned to the selected state lens. The admission condition is stated per query, but it does not require per-query physical state or per-query physical execution. The shared execution may satisfy several per-query admission conditions through one scan step, one admitted state-producing step, or one probe step, as long as visibility metadata routes each row and state entry to its allowed queries. A state-lens observation becomes state-ready when the selected state covers that lens’s represented and residual extents. The stateconsuming operator is scheduled only after ready-fragment extraction finds a data-flow path that supplies the required consumer-side input. It then emits rows for the assigned state-side input through that state lens. The boundary combines those rows with outputs produced by ordinary-plan work for the unattached extent.
{QA}
Scan R {QA}
Count {QA}
HashProbe {QA}
HashBuild QA: x < 20 QB: x < 10 {QA, QB}
Scan S {QA}
Scan R {QA,QB}
(a) Before.
QB Gate
HashBuild {QB}
HashProbe {QB}
HashProbe {QA,QB}
Scan S {QA,QB}
Scan T {QB}
(b) After attachment.
Figure 5: Shared execution DAG update for two non-identical queries. Solid edges carry row flow, dashed edges carry stateref dependencies, and the 𝑄 𝐵 gate labels the state-readiness condition on 𝑄 𝐵 ’s state-ref edge.
5
QUERY GRAFTING AND SCHEDULING
Query grafting installs DAG work for an admitted boundary. When a query arrives, GraftDB compares each stateful boundary in its single-query DAG with shared state maintained by the running execution. For an admitted boundary, the runtime turns the boundary’s state-side extent into three assignments: a state-ref edge over the represented and residual extents, producer edges that contribute the residual extent to the selected state, and ordinary-plan work for the unattached extent. The same DAG update installs a state-readiness gate on the state-ref edge. This gate records when the selected state is ready for that edge; the consumer-side input that drives the operator remains part of the DAG’s data flow, and ready-fragment extraction handles that input.
5.1
The Shared Execution DAG
The shared execution DAG records the work that can still advance in the running execution. A node represents an operator instance together with the queries assigned to that instance. A data edge carries rows between operators. A state-ref edge connects a stateconsuming operator to shared state through a query-specific statereadiness gate. For a DAG 𝐺, we write DataEdge(𝐺) for its data edges, StateRefEdge(𝐺) for its state-ref edges, and DepEdge(𝐺) for their union. The DAG also records the attachment decisions made for arriving queries: residual producer edges, ordinary-plan assignments, and state-ref edges guarded by per-query state lenses. Figure 5 illustrates one DAG update. When 𝑄 𝐵 arrives with a narrower 𝑥 < 10 requirement and a 𝑇 -side suffix, GraftDB attaches its compatible prefix to the existing hash-build state, records a 𝑄 𝐵 -specific statereadiness condition on the state-ref edge, and leaves the 𝑄 𝐵 -only suffix as separate operator work. The gate label denotes readiness of the selected shared state, not a physical operator and not the availability of the probe-side input.
5.2
Query-grafting Admission
Admission is local to a stateful boundary. GraftDB first compiles the arriving query 𝑞 into an ordinary single-query DAG. For each
GraftDB: Dynamic Folding of Concurrent Analytical Queries
stateful boundary 𝑏, it forms a lens descriptor 𝑑 = (𝑎, 𝜌), where the lens signature 𝑎 records state-side identity and lens conditions: relations, keys, predicates, grouping attributes, aggregate identity, and required upstream state. The operator rule 𝜌 records which matches, groups, or outputs 𝑞 can derive from a compatible state. A candidate shared state 𝑆 can be selected only when it provides a compatible signature and the metadata needed to form 𝑞’s perquery state lens. For each stateful boundary, the prototype derives a canonical state signature and uses the shared execution’s signature index to select a corresponding live or retained shared state when the state-ref reuse checks pass. Algorithm 1 then applies coverage and visibility checks to assign the boundary’s state-side input to represented, residual, and unattached extents. For an admissible candidate, GraftDB partitions the state-side extent required by 𝑏. The represented extent 𝑅rep is already represented by 𝑆. For hash-build state, this means that the table’s coverage metadata describes the corresponding build-side extent as complete. For aggregate state, this means that the aggregate state has the exact aggregate identity and the physical aggregate state binding used by the shared DAG. Missing occurrences that an admitted producer path can still deliver to 𝑆 become the residual extent 𝑅res ; the rest becomes the unattached extent 𝑅un . The partition is over derivation-identified occurrences, so equal payload tuples are not merged by the assignment. The partition has direct operational effects in the DAG: GraftDB installs a state-ref edge for 𝑅rep ∪ 𝑅res , installs residual producer edges targeting 𝑆, and records 𝑅un as ordinary-plan work before the state-consuming work is scheduled. Because the assignment is made per boundary, one query can observe shared state at one operator, contribute a residual extent for another, and keep unrelated work as ordinary-plan work for that query. Algorithm 1 shows the query-grafting admission decision for one boundary and one candidate state. The function either rejects the candidate, leaves the boundary as ordinary-plan work, or installs a state-ref edge whose state dependency is open immediately or gated. Consumer-side data availability is represented by data edges and checked during ready-fragment extraction. The first two blocks make the admission test operational. Line 2 checks the exact non-predicate conditions needed for 𝑆 to support 𝑞’s state lens at boundary 𝑏, including state kind, relation, key and payload layout, aggregate identity when applicable, and required upstream state. It also records the predicate-containment and evaluability obligations for that lens. If this check fails, the rejection is local to this candidate state (lines 3–4). The partition step then evaluates those obligations using the predicate-containment and evaluability checks from Section 4.2. Line 20 places only extents whose obligations are proven in 𝑅rep . A missing extent is placed in 𝑅res only when AdmissibleProducerPaths finds a path that can still deliver it into 𝑆 (lines 22–23). All other occurrences are placed in 𝑅un (line 24). AdmitBoundary records the unattached extent as ordinary-plan work before installing any state-ref edge (line 7). Thus Algorithm 1 treats unsupported predicate reasoning as lost sharing rather than unsafe sharing. The final block installs the runtime obligations. If no represented or residual extent is assigned to the selected state, the boundary
Algorithm 1 Query-grafting admission for one boundary and one candidate state. 1: function AdmitBoundary(𝑞, 𝑏, 𝑆, 𝐺, 𝑡) 2: 𝑣 ← CheckLensCompatibility(𝑞, 𝑏, 𝑆, 𝐺) 3: if 𝑣 = ⊥ then 4: return NoAttachment(𝑆) 5: 𝑋 ← PartitionStateExtent(𝑞, 𝑏, 𝑆, 𝐺, 𝑣) 6: (𝑅rep , 𝑅res , 𝑅un, Pres ) ← 𝑋 7: AssignOrdinarySource(𝑞, 𝑏, 𝑅un, 𝐺) 8: if 𝑅rep ∪ 𝑅res = ∅ then 9: return OrdinaryOnly(𝑞, 𝑏) 10: if 𝑅res ≠ ∅ then 11: InstallResidualProducers(𝑞, 𝑏, 𝑆, 𝑅res , Pres, 𝐺) 12: 𝑟 ← (𝑞, 𝑏, 𝑣) 13: 𝑂 ← InstallStateRef(𝑟, 𝑆, 𝑅rep ∪ 𝑅res , 𝐺) 14: if Open(𝑂, 𝑡) then 15: return OpenStateRef(𝑟, 𝑂) 16: else 17: return GatedStateRef(𝑟, 𝑂) 18: function PartitionStateExtent(𝑞, 𝑏, 𝑆, 𝐺, 𝑣) 19: 𝑅 ← StateExtent(𝑞, 𝑏) 20: 𝑅rep ← 𝑅 ∩ RepresentedExtent(𝑆, 𝑣, 𝐺) 21: 𝑅miss ← 𝑅 \ 𝑅rep 22: Pres ← AdmissibleProducerPaths(𝑅miss , 𝑆, 𝐺, 𝑣) 23: 𝑅res ← 𝑅miss ∩ Extent(Pres ) 24: 𝑅un ← 𝑅miss \ 𝑅res 25: return (𝑅rep , 𝑅res , 𝑅un, Pres )
remains ordinary-only (lines 8–9). Otherwise, GraftDB installs producer obligations for a nonempty residual extent into 𝑆 (lines 10–11), and the admitted boundary installs a state-ref edge over 𝑅rep ∪ 𝑅res (lines 12–13). The final branch reports whether that state dependency is already open or still gated (lines 14–17). Consumer-side input is not part of this admission gate; it is enforced later by dataedge reachability during ready-fragment extraction.
5.3
State-readiness Gates
A state-readiness gate records the state dependency of an admitted state-ref edge. For an admitted state-ref 𝑟 = (𝑞, 𝑏, 𝑣) through shared state 𝑆, the gate 𝑂 = (𝑟, 𝑆, 𝑅) records the selected state and the assigned state-side extent. For a hash-probe step, 𝑅 is the build-side extent that the hash table must represent. The probe-side input remains on the DAG’s data-flow edges. At scheduling time 𝑡, the gate is open when the selected shared state is ready for the assigned state-side extent: open𝑡 (𝑂) ≡ stateReady𝑡 (𝑆, 𝑟, 𝑅). For hash-build state, the selected state’s coverage metadata describes the assigned build-side extent as complete. For aggregate state, readiness follows exact aggregate identity, the physical aggregate state binding used by the shared DAG, and completion of the required aggregate state. An open state-ref edge may still wait for data-flow reachability before it appears in a ready fragment.
Genki Kimura and Kazuo Goda
Algorithm 2 Extracting ready fragments from active assignments. 1: function ExtractReadyFragments(𝐺, 𝑡)
𝑃←∅ for all 𝑛 ∈ Nodes(𝐺) do 4: for all 𝑞 ∈ ActiveAtNode(𝑛, 𝐺, 𝑡) do 5: 𝑃 ← 𝑃 ∪ {(𝑛, 𝑞)} 6: 𝐺 𝑃 ← RestrictToPairs(𝐺, 𝑃) 7: 𝐺 𝑅 ← PruneByDataReachability(𝐺 𝑃 , 𝑡) 8: F ←∅ 9: for all 𝐶 ∈ WeakComponents(𝐺 𝑅 , DepEdge(𝐺𝑅 )) do 10: 𝐹 ← TopologicalOrder(𝐶, DataEdge(𝐶)) 11: F ← F ∪ {𝐹 } 12: return F 13: function ActiveAtNode(𝑛, 𝐺, 𝑡) 14: 𝐴←∅ 15: for all 𝑞 ∈ AssignedQueries(𝑛) do 16: if ProducerInactive(𝑛, 𝑞, 𝐺, 𝑡) then 17: continue 18: if StateConsumerBlocked(𝑛, 𝑞, 𝐺, 𝑡) then 19: continue 20: 𝐴 ← 𝐴 ∪ {𝑞} 21: return 𝐴 22: function ProducerInactive(𝑛, 𝑞, 𝐺, 𝑡) 23: if not ProducesState(𝑛) then 24: return False 25: return not ProducerWorkPending(n,q,G,t) 26: function StateConsumerBlocked(𝑛, 𝑞, 𝐺, 𝑡) 27: if not ConsumesState(𝑛) then 28: return False 29: for all 𝑂 ∈ Refs(𝑛, 𝑞, 𝐺) do 30: if not Open(O,t) then 31: return True 32: return False 2: 3:
5.4
Ready Fragment Scheduling
Scheduling operates on active node-query pairs, not on whole nodes. For a state-producing node, query 𝑞 is active while producer work assigned to 𝑞 remains pending. For a state-consuming node, 𝑞 passes the state-dependency filter when every state-ref gate for that nodequery pair is open. The node-query pair still appears in a ready fragment only if it remains on a ready data-flow path after graph pruning. Ordinary nodes keep the assigned queries recorded by their source assignments. Algorithm 2 extracts ready work from the current DAG at scheduling time 𝑡. It first computes active node-query pairs using producer obligations and state-ref gates, then prunes the resulting graph by data-edge reachability. The extractor first constructs active node-query pairs (lines 2–5). ActiveAtNode starts from the node’s assigned queries. A producer node-query pair is removed by the test at line 16; the helper in lines 23–25 keeps state producers active only while producer work is pending. A state-consuming node-query pair is removed by the test at line 18; the helper in lines 27–32 passes it only when all state-ref gates entering that node-query pair are open.
The extractor then restricts the DAG to active node-query pairs (line 6) and prunes the restricted graph by data-edge reachability (line 7). This pruning step is where consumer-side input availability is enforced. The remaining graph is grouped over data and stateref dependencies (line 9), ordered along data edges (line 10), and emitted as ready fragments (lines 11–12). Together, admission and ready-fragment extraction maintain one assignment for each state-side occurrence: it belongs to the represented extent, is contributed to the selected state through residual producer work, or belongs to the unattached extent executed as ordinary-plan work. The state-ref gate and data-flow pruning then ensure that state-ref edges open only after the selected state is ready and the consumer-side input is available. These conditions give the core correctness argument for the state-lens observations described in Section 4: each derivation-identified state-side occurrence is accounted for exactly once, state-lens observations open only after the assigned state extent is complete, and per-query visibility checks filter state entries and emitted rows.1 When a query completes, GraftDB removes that query’s assignments from the DAG. Referenced shared state remains available; unreferenced state can be released according to the runtime’s retention policy.
6
EXPERIMENTAL EVALUATION
We evaluate GraftDB on TPC-H-derived dynamic concurrent workloads [61]. The experiments measure performance across concurrency, arrival, workload-skew, and data-scale settings, and separate the throughput effect of the main dynamic-folding mechanisms.
6.1
Experimental Setup
We evaluate a Rust prototype of GraftDB. A query instance is a parameterized TPC-H template with concrete parameter values. Unless otherwise stated, workloads sample Q1 and Q3–Q10,2 from a Zipf distribution with parameter 𝛼 = 1. Template parameters are sampled uniformly from large benchmark domains. Exact duplicate query instances are therefore rare; overlap mainly comes from related templates and compatible operator requirements. The prototype is available at https://github.com/dbc-utokyoiis/ GraftDB. Experiments use a server with two Intel Xeon Gold 6132 CPUs at 2.60 GHz, 96 GB RAM, and 29 TB RAID-6 HDD storage. All Rust variants use one thread. The evaluation therefore focuses on inter-query concurrency under a single-worker execution model. Extending the prototype to intra-query parallel execution remains future work. In the evaluated prototype, the runtime releases operator state once no query in the shared execution references it, so the reported gains reflect temporal overlap with running shared executions. The main comparisons are within the Rust prototype. Isolated is the same engine with sharing disabled. QPipe-OSP is a same-engine implementation of QPipe’s on-demand simultaneous pipelining policy [29]. It shares scans and in-flight operator instances under identical operator profiles, including predicates and pre-filters, without GraftDB’s coverage-based observation of already-built state. PostgreSQL 16.13 provides an external reference point. PostgreSQL 1 A full formalization of this argument requires a separate treatment. 2We omit TPC-H Q2 because it requires a correlated subquery, which is outside the
prototype’s current SQL support.
GraftDB: Dynamic Folding of Concurrent Analytical Queries
QPipe-OSP
GraftDB
20 10 0
build CUSTOMER build ORDERS
0.0
2.5
probe LINEITEM
after QA completes (no QA overlap)
3000
2000
1000
is pinned to one CPU core, with JIT compilation and parallel query execution disabled, and joins restricted to hash joins. For each TPCH query template, the prototype uses a fixed physical plan whose join order and operator sequence match PostgreSQL’s EXPLAIN plan under this configuration; workload parameters change only predicates and constants. All Rust variants start from this plan before any sharing decision is applied. Throughput is completed queries per hour.
Isolated
GraftDB
QPipe-OSP
PostgreSQL
0
5.0 7.5 10.0 12.5 15.0 17.5 QB Arrival Offset (s)
Figure 6: Elapsed time for two TPC-H Q3-derived queries as 𝑄 𝐵 ’s arrival is delayed after 𝑄 𝐴 . Phase arrows show which part of 𝑄 𝐴 is running when 𝑄 𝐵 arrives. GraftDB shortens completion while 𝑄 𝐴 ’s order-side state is live, then converges toward the baselines once 𝑄 𝐵 no longer overlaps with 𝑄 𝐴 .
6.2
4000
1
2
4
8
16
32
Concurrent Users
Figure 7: Closed-loop throughput as concurrency increases. GraftDB stays close to Isolated at one client, then reaches 2.17 times higher throughput than Isolated at 32 clients as more arrivals overlap with ongoing shared executions.
Query Latency (s)
Elapsed Time (s)
30
5000
Queries / Hour
Isolated
10
2
10
1
10
0
Isolated
GraftDB
QPipe-OSP
PostgreSQL
Dynamic Folding on TPC-H Q3 1
2
4
8
16
32
Figure 6 uses the Q3-derived pair from Section 3.3 at TPC-H SF10 Concurrent Users and sweeps 𝑄 𝐵 ’s arrival offset after 𝑄 𝐴 . The two queries use the same SQL skeleton and the same fixed parameters as in Section 3.3: Figure 8: Workload-level query latency as closed-loop conboth use :segment = ’BUILDING’, 𝑄 𝐴 uses :date = DATE ’1995-03-15’,currency increases. Each point is one query execution, and and 𝑄 𝐵 uses :date = DATE ’1995-03-20’. The y-axis is elapsed thick marks show the median on a logarithmic y-axis. Statetime from the start of 𝑄 𝐴 until both queries complete. lens observations reduce repeated work at high concurrency, Isolated executes independent physical plans. Changing 𝑄 𝐵 ’s lowering median latency to 0.48 times the Isolated median at arrival time changes temporal overlap between the two executions, 32 clients. but it does not change the work assigned to either query. While the two executions still overlap, the total elapsed time stays close to one independent pair of Q3 executions. After 𝑄 𝐴 finishes, the total can still contribute it to the order-side state. The lineitem predicate elapsed time rises with the non-overlapped suffix. moves in the opposite direction: 𝑄 𝐵 ’s later date narrows the probeQPipe-OSP shares scans and, for nearly simultaneous arrivals, side input, so rows needed only by 𝑄 𝐴 are not part of 𝑄 𝐵 ’s residual the customer build because both queries have the same customerextent. At zero offset, elapsed time falls from 28.4 s under Isolated build profile, including c_mktsegment = ’BUILDING’. After that to 15.4 s under GraftDB. After 𝑄 𝐴 completes, GraftDB converges phase, the order-side build and lineitem/probe profiles differ due to toward the same no-overlap range as the baselines. the different date bounds, so QPipe-OSP mainly benefits from scan sharing. Its elapsed time therefore stays below Isolated but remains 6.3 Closed-loop Concurrency almost flat over most arrival offsets. GraftDB shares the same customer-build opportunity and also The closed-loop run set uses TPC-H SF1 data and the default Zipf folds 𝑄 𝐵 into the order-side state when that state can provide a reptemplate distribution over Q1 and Q3–Q10. Each client executes resented extent for 𝑄 𝐵 ’s build-side requirement. For this pair, 𝑄 𝐵 ’s 20 generated query instances and has at most one outstanding order predicate is broader than 𝑄 𝐴 ’s. The order hash table produced query: it submits the next query after its previous query completes. for 𝑄 𝐴 already represents the prefix of 𝑄 𝐵 ’s state-side extent shared We vary the number of clients over {1, 2, 4, 8, 16, 32}. All systems by both queries, and GraftDB registers the still-missing date band use the same per-client query-instance sequences. Figure 7 shows as the residual build-side extent when the current shared execution closed-loop throughput as concurrency increases.
Genki Kimura and Kazuo Goda
1
2
4
8
16
Concurrent Users (a) Throughput
32
+Residual Production Represented Observation 76.4 154 310 616
60 40 20 0
1
2
4
8
16 32
+Represented-Extent Attachment Rows (% of Isolated)
2.0 1.5 1.0 0.5 0.0
+Scan Sharing Residual Build Scan Input (GiB)
Normalized Throughput
Isolated Ordinary Build
100% 75% 50% 25% 0%
Concurrent Users (b) Scan input
1
2
4
8
16 32
Concurrent Users (c) Hash-build demand
Figure 9: Mechanism breakdown on the closed-loop SF1 workload. Variants cumulatively enable scan sharing, residual production, and represented-extent attachment across throughput, scan input, and hash-build demand. (a) At 32 clients, the variants reach 1.23 times, 1.97 times, and 2.17 times Isolated throughput. (b) Scan sharing cuts scan input from 616 GiB to 60.7 GiB, and the two state-centric variants keep scan input near 50 GiB. (c) Represented-extent attachment reduces exposed hash-build demand from 82.3% to 50.3% of Isolated. At one client, GraftDB stays close to Isolated at 0.99 times its throughput. At 8, 16, and 32 clients, GraftDB achieves 1.43, 1.85, and 2.17 times higher throughput than Isolated. In absolute terms, GraftDB rises from 3.0K to 5.0K queries/hour across the sweep, while Isolated falls from 3.0K to 2.3K and PostgreSQL from 2.8K to 1.9K. The improvement grows with concurrency because more query executions overlap with running shared executions. Figure 8 plots every measured closed-loop query execution and marks the scenario median. At 32 clients, GraftDB reduces median latency from 44.4 s to 21.3 s, or to 0.48 times the Isolated median. QPipe-OSP reaches 34.5 s at the same point. At 16 clients, median latency falls from 21.6 s to 11.9 s. The one-client median is similar across systems.
6.4
Mechanism Breakdown
The mechanism experiments build up GraftDB cumulatively on the same closed-loop SF1 run set. +Scan Sharing shares base-table scans but does not expose shared operator state to later-arriving queries. +Residual Production lets admitted producer paths contribute residual extents to common shared state. +RepresentedExtent Attachment additionally lets a later-arriving query observe a compatible extent that the shared execution has already represented. Figure 9 reports throughput, scan input, and hash-build demand under this cumulative breakdown. Figure 9(a) and Figure 9(b) show that scan sharing removes most scan input but not most of the throughput gain. At 32 clients, +Scan Sharing reduces scan input from 616 GiB to 60.7 GiB, or 0.099 times Isolated, and reaches 1.23 times Isolated throughput. The statecentric variants keep scan input low, ending at 0.081 times Isolated, while raising throughput to 1.97 times and 2.17 times Isolated. Figure 9(c) decomposes hash-build demand normalized to the build-side rows that Isolated would feed to hash-build state boundaries. Ordinary Build rows are unattached state-side input that remains ordinary-plan work. Residual Build rows are residual extents inserted into shared state. Represented Observation rows are
satisfied at the same boundary by observing a represented extent through a state lens, rather than by inserting those rows on behalf of the query. When a bar does not reach 100%, the unfilled portion represents isolated-plan hash-build demand for upstream state that is no longer constructed for that query in the folded execution after query grafting attaches the query at a downstream shared state. At 32 clients, +Residual Production leaves 82.3% of Isolated hashbuild demand exposed to hash-build state boundaries: 4.2% ordinary builds, 71.1% residual builds, and 7.0% represented observations. With +Represented-Extent Attachment, the exposed demand falls to 50.3%: 6.2% ordinary builds, 39.0% residual builds, and 5.1% represented observations. The remaining 49.7% is upstream hash-build demand eliminated by downstream state-lens observations. Thus represented-extent attachment helps both directly, by observing represented extents, and indirectly, by avoiding upstream hashbuild work for attached queries.
6.5
Open-loop Arrivals
Figure 10 evaluates the same SF1 template set under open-loop Poisson arrivals. Each run first warms up the system for 120 s at 1K queries/hour. The measurement phase then submits queries for 60 s at the offered load shown on the x-axis. After the measurement phase, no new queries are submitted, and the run waits until all submitted queries complete. For each offered load, scheduled arrival times are sampled from a Poisson process and paired with query instances from the default template distribution. The x-axis sets the mean arrival rate of that process, from 1K to 10K queries/hour. All systems replay the same scheduled arrival trace and query-instance sequence for a given offered load. Response time is measured from scheduled arrival time to query completion. At 1K offered queries/hour, all systems keep P95 response time near 2.5 s. As offered load increases, GraftDB maintains lower P95 response time than the baselines. The largest relative reduction appears at 5K offered queries/hour, where P95 response time falls
102
102
Isolated QPipe-OSP 1K
2.5K
5K
GraftDB PostgreSQL 7.5K
Offered Load (queries/hour)
10K
Figure 10: P95 response time under Poisson open-loop arrivals as offered load increases. GraftDB delays the queueing growth seen in the baselines, with the largest relative reduction at 5K offered queries/hour, where P95 response time falls to 0.17 times Isolated’s P95 response time.
4000
Queries / Hour
QPipe-OSP
GraftDB
101
101
3000
2000
1000 Isolated
GraftDB
PostgreSQL
0 0.0
0.4
0.8
1.2
1
3
10
TPC-H Scale Factor
30
Figure 12: Elapsed time to complete the fixed eight-client workload as TPC-H scale factor increases. GraftDB remains faster than both baselines across SF1–SF30, staying between 0.72 and 0.74 times the Isolated completion time.
domains keep exact duplicate query instances rare. The resulting overlap is mainly overlap in operator requirements among related but non-identical queries. Figure 12 varies data scale using the same eight-client closed-loop workload shape at TPC-H SF1, SF3, SF10, and SF30. It reports workload completion time on logarithmic axes. GraftDB completes faster than Isolated throughout the sweep. At SF30, completion time falls from 150.5 minutes under Isolated to 110.4 minutes under GraftDB. QPipe-OSP completes the same workload in 117.9 minutes. Across SF1–SF30, GraftDB stays between 0.72 and 0.74 times the Isolated completion time.
1.6
Query Skew
Figure 11: Throughput at fixed eight-client concurrency as query skew increases. Higher skew concentrates arrivals on fewer templates and increases overlap in operator requirements, raising GraftDB from 1.34 to 1.60 times higher throughput than Isolated.
from 148.0 s under Isolated to 24.6 s under GraftDB, or to 0.17 times the Isolated P95 response time. QPipe-OSP reaches 87.8 s at the same point. At 10K offered queries/hour, GraftDB reduces P95 response time from 305.7 s to 86.0 s, or to 0.28 times the Isolated P95 response time, while QPipe-OSP reaches 205.0 s.
6.6
Isolated
Elapsed Time (min)
p95 Response Time (s)
GraftDB: Dynamic Folding of Concurrent Analytical Queries
Sensitivity to Skew and Scale
Figure 11 varies workload concentration by changing the Zipf parameter of the template distribution from 𝛼 = 0.0 to 𝛼 = 1.6 at fixed eight-client concurrency on the SF1 run set. Each client follows the same 20-query closed-loop rule. Parameter values within each template are still sampled uniformly from the same large domains. At 𝛼 = 0.0, which gives uniform template selection, GraftDB achieves 1.34 times higher throughput than Isolated. At 𝛼 = 1.6, the throughput ratio grows to 1.60 times. Higher template skew concentrates arrivals on fewer templates, while the large parameter
7
RELATED WORK
GraftDB shares analytical work at the arrival-time boundary of a dynamic concurrent workload. When a query arrives, the runtime can attach it to operator state that a running execution has already produced, while producer work that can still receive source input can contribute to that state. This decision differs from sharing over a saved artifact, a preselected query set, a running scan or pipeline, or maintained streaming state. The shared object is partially produced operator state; the admission test asks whether the represented extent can be observed through a per-query state lens and whether remaining source input can still feed producer work that contributes the residual extent to the same state. Result reuse and materialized-view systems make completed work available to later queries. A query can use a materialized view, recycled intermediate, or MapReduce job result when that artifact matches the query or can answer it [12, 14, 21, 27, 30, 37, 39, 45, 49]. Hybrid MQO work combines materialized-view reuse with shared subexpression reuse in a batched optimization setting [28]. Semantic caching, internal data-structure reuse, reactive caching, and intermittent query processing preserve reusable extents, structures, or operator state across related computations [6, 16, 19, 60]. GraftDB instead keeps partially produced state inside a running shared execution and controls each query’s observation through a per-query state lens. Multi-query optimization and batched shared-execution systems move the decision earlier: they reason over a known or
Genki Kimura and Kazuo Goda
admitted query set and construct shared plans, subplans, or execution cycles before that shared unit runs [15, 20, 22, 24, 25, 41, 50, 56, 58, 62, 65, 71]. GraftDB uses a different boundary. It admits a query after execution has already changed operator state, then partitions the query’s state-side extent into represented, residual, and unattached extents. Runtime-sharing systems make sharing decisions while execution is in progress. Shared scans coordinate concurrent access to base tables [53, 55, 72], QPipe shares operator pipelines across concurrent queries [29], and CJoin, Crescando, DataPath, and studies of concurrent analytical work sharing coordinate joins, data-centric paths, or global query plans under changing workloads [4, 9, 51, 52, 63]. These systems share running work through scan policies, operator pipelines, tuple routing, or shared join structures. Hash teams similarly organize join and group-by execution around hash structures inside a plan [35]. GraftDB also makes an online decision, but the decision is made at a stateful boundary after earlier work has produced state. A folded hash-probe step is admitted only when coverage metadata describes the relevant build-side extent as complete, source availability can contribute the residual build-side extent to the selected state, and the data-flow path can supply the probe-side input. Adaptive query processing also exposes or manipulates execution state while a query is running. SteMs decompose join processing into state modules, and STAIRs make join state explicitly modifiable and migratable during adaptive execution [17, 54]. Tukwila, proactive re-optimization, progressive optimization, and AQP surveys use runtime feedback or adaptive routing to change execution decisions [7, 8, 18, 31, 42]. GraftDB instead uses partially produced operator state as an inter-query sharing unit for laterarriving finite analytical queries. Stream and continuous-query systems maintain computation across changing inputs or changing query sets. STREAM, CQL, Aurora, and Borealis define semantics or architectures for data stream management and continuous queries [1–3, 47]. CACQ [40], TelegraphCQ [10], and PSoup [11] provide adaptive or shared continuous-query processing structures, and AStream and AJoin support ad-hoc stream queries that can be created and deleted while the system runs [33, 34]. Flux repartitions continuous-query state, and MJoin optimizes multi-way stream joins [59, 64]. Shared arrangements make indexed arrangement state available across concurrent streaming dataflows [43], and timely dataflow and recent stream-join systems optimize progress tracking, join models, or join orders under streaming updates [48, 66, 69]. These systems make state shareable under stream time, windows, maintained versions, or continuous updates. GraftDB targets finite analytical executions. For hash-build state, coverage metadata describes which finite build-side extent the shared state represents; for aggregate state, exact aggregate identity determines which completed state can be observed. These conditions let a later one-shot query observe only the state-side extent that is complete for that query’s state lens and wait only for residual producer work admitted to the same state. Other systems optimize adjacent execution boundaries. DynQ reuses compiled-query artifacts in a polyglot runtime [57], and Lemo uses cached subquery and intermediate results in learned optimization for concurrent queries [46]. DBToaster, Differential Dataflow, and Noria maintain results or dataflow state as inputs
change, with Noria also sharing state across related application queries [26, 36, 44]. Pipeline group optimization, sideways information passing, predicate transfer, Eddies, and NiagaraCQ improve execution through pipeline placement, prefiltering, adaptive routing, or dynamic continuous-query grouping [5, 13, 23, 32, 68]. GraftDB instead makes partially produced operator state the unit of dynamic folding for analytical queries that arrive over time. Per-query state lenses restrict what each query may observe from that state, and query grafting turns the compatible part of the arriving query into shared-execution work.
8
CONCLUSION
GraftDB shows that dynamic concurrent analytical workloads can share work through operator state accumulated by a running execution. Hash-build and aggregate states become shared objects that later-arriving queries can attach to while preserving per-query semantics. Per-query state lenses define what each query may observe, while query grafting assigns state-side input to represented, residual, and unattached extents. Experiments on TPC-H-derived dynamic concurrent workloads show that this execution model reduces redundant work across overlapping analytical queries. GraftDB achieves up to 2.17 times higher throughput than the isolated baseline and, under overloaded open-loop arrivals, reduces P95 response time to as low as 0.17 times the isolated baseline’s P95 response time. The mechanism breakdown shows that scan sharing alone does not explain these gains: residual production and represented-extent attachment reduce hash-build demand after scan input has largely been removed. The result is a runtime sharing unit for dynamic concurrent workloads: partially accumulated operator state. Future work will extend dynamic folding to multi-threaded execution. This extension must coordinate concurrent state producers and per-query statelens observations while preserving the completeness and visibility conditions used by the single-threaded prototype.
ACKNOWLEDGMENTS This work was supported in part by JSPS Grant-in-Aid for Research Fellows JP24KJ0769 and JSPS Grant-in-Aid for Scientific Research (B) JP26K02915.
REFERENCES [1] Daniel J. Abadi, Yanif Ahmad, Magdalena Balazinska, Ugur Çetintemel, Mitch Cherniack, Jeong-Hyon Hwang, Wolfgang Lindner, Anurag Maskey, Alex Rasin, Esther Ryvkina, Nesime Tatbul, Ying Xing, and Stanley B. Zdonik. 2005. The Design of the Borealis Stream Processing Engine. In Proceedings of the Conference on Innovative Data Systems Research. 277–289. [2] Daniel J. Abadi, Donald Carney, Ugur Çetintemel, Mitch Cherniack, Christian Convey, Sangdon Lee, Michael Stonebraker, Nesime Tatbul, and Stanley B. Zdonik. 2003. Aurora: a new model and architecture for data stream management. The VLDB Journal 12, 2 (2003), 120–139. [3] Arvind Arasu, Shivnath Babu, and Jennifer Widom. 2006. The CQL Continuous Query Language: Semantic Foundations and Query Execution. The VLDB Journal 15, 2 (2006), 121–142. [4] Subi Arumugam, Alin Dobra, Christopher M. Jermaine, Niketan Pansare, and Luis Leopoldo Perez. 2010. The DataPath System: A Data-Centric Analytic Processing Engine for Large Data Warehouses. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 519–530. [5] Ron Avnur and Joseph M. Hellerstein. 2000. Eddies: Continuously Adaptive Query Processing. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 261–272.
GraftDB: Dynamic Folding of Concurrent Analytical Queries
[6] Tahir Azim, Manos Karpathiotakis, and Anastasia Ailamaki. 2017. ReCache: Reactive Caching for Fast Analytics over Heterogeneous Data. Proceedings of the VLDB Endowment 11, 3 (2017), 324–337. [7] Shivnath Babu and Pedro Bizarro. 2005. Adaptive Query Processing in the Looking Glass. In Proceedings of the Conference on Innovative Data Systems Research. 238–249. [8] Shivnath Babu, Pedro Bizarro, and David J. DeWitt. 2005. Proactive Reoptimization. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 107–118. [9] George Candea, Neoklis Polyzotis, and Radek Vingralek. 2009. A Scalable, Predictable Join Operator for Highly Concurrent Data Warehouses. Proceedings of the VLDB Endowment 2, 1 (2009), 277–288. [10] Sirish Chandrasekaran, Owen Cooper, Amol Deshpande, Michael J. Franklin, Joseph M. Hellerstein, Wei Hong, Sailesh Krishnamurthy, Samuel Madden, Vijayshankar Raman, Frederick Reiss, and Mehul A. Shah. 2003. TelegraphCQ: Continuous Dataflow Processing for an Uncertain World. In Proceedings of the Conference on Innovative Data Systems Research. 12 pages. [11] Sirish Chandrasekaran and Michael J. Franklin. 2002. Streaming Queries over Streaming Data. In Proceedings of the International Conference on Very Large Data Bases. 203–214. [12] Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, and Kyuseok Shim. 1995. Optimizing Queries with Materialized Views. In Proceedings of the IEEE International Conference on Data Engineering. 190–200. [13] Jianjun Chen, David J. DeWitt, Feng Tian, and Yuan Wang. 2000. NiagaraCQ: A Scalable Continuous Query System for Internet Databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 379–390. [14] Rada Chirkova and Jun Yang. 2012. Materialized Views. Foundations and Trends in Databases 4, 4 (2012), 295–405. [15] Nilesh N. Dalvi, Sumit K. Sanghai, Prasan Roy, and S. Sudarshan. 2001. Pipelining in Multi-Query Optimization. In Proceedings of the ACM SIGMOD-SIGACTSIGART Symposium on Principles of Database Systems. 59–70. [16] Shaul Dar, Michael J. Franklin, Björn Thór Jónsson, Divesh Srivastava, and Michael Tan. 1996. Semantic Data Caching and Replacement. In Proceedings of the International Conference on Very Large Data Bases. 330–341. [17] Amol Deshpande and Joseph M. Hellerstein. 2004. Lifting the Burden of History from Adaptive Query Processing. In Proceedings of the International Conference on Very Large Data Bases. 948–959. [18] Amol Deshpande, Zachary G. Ives, and Vijayshankar Raman. 2007. Adaptive Query Processing. Foundations and Trends in Databases 1, 1 (2007), 1–140. [19] Kayhan Dursun, Carsten Binnig, Ugur Çetintemel, and Tim Kraska. 2017. Revisiting Reuse in Main Memory Database Systems. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 1275–1289. [20] Amr El-Helw, Venkatesh Raghavan, Mohamed A. Soliman, George C. Caragea, Zhongxian Gu, and Michalis Petropoulos. 2015. Optimization of Common Table Expressions in MPP Database Systems. Proceedings of the VLDB Endowment 8, 12 (2015), 1704–1715. [21] Iman Elghandour and Ashraf Aboulnaga. 2012. ReStore: Reusing Results of MapReduce Jobs. Proceedings of the VLDB Endowment 5, 6 (2012), 586–597. [22] Sheldon J. Finkelstein. 1982. Common Expression Analysis in Database Applications. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 235–245. [23] Andreas Geyer, Alexander Krause, Dirk Habich, and Wolfgang Lehner. 2023. Pipeline Group Optimization on Disaggregated Systems. In Proceedings of the Conference on Innovative Data Systems Research. 7 pages. [24] Georgios Giannikis, Gustavo Alonso, and Donald Kossmann. 2012. SharedDB: Killing One Thousand Queries With One Stone. Proceedings of the VLDB Endowment 5, 6 (2012), 526–537. [25] Georgios Giannikis, Darko Makreshanski, Gustavo Alonso, and Donald Kossmann. 2014. Shared Workload Optimization. Proceedings of the VLDB Endowment 7, 6 (2014), 429–440. [26] Jon Gjengset, Malte Schwarzkopf, Jonathan Behrens, Lara Timbó Araújo, Martin Ek, Eddie Kohler, M. Frans Kaashoek, and Robert Morris. 2018. Noria: Dynamic, Partially-Stateful Data-Flow for High-Performance Web Applications. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation. 213–231. [27] Jonathan Goldstein and Per-Åke Larson. 2001. Optimizing Queries Using Materialized Views: A Practical, Scalable Solution. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 331–342. [28] Bala Gurumurthy, Vasudev Raghavendra Bidarkar, David Broneske, Thilo Pionteck, and Gunter Saake. 2024. Exploiting Shared Sub-Expression and Materialized View Reuse for Multi-Query Optimization. Information Systems Frontiers (2024), 16 pages. [29] Stavros Harizopoulos, Vladislav Shkapenyuk, and Anastassia Ailamaki. 2005. QPipe: A Simultaneously Pipelined Relational Query Engine. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 383–394. [30] Milena Ivanova, Martin L. Kersten, Niels J. Nes, and Romulo Goncalves. 2009. An Architecture for Recycling Intermediates in a Column-Store. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 309–320.
[31] Zachary G. Ives, Daniela Florescu, Marc T. Friedman, Alon Y. Levy, and Daniel S. Weld. 1999. An Adaptive Query Execution System for Data Integration. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 299–310. [32] Zachary G. Ives and Nicholas E. Taylor. 2008. Sideways Information Passing for Push-Style Query Processing. In Proceedings of the IEEE International Conference on Data Engineering. 774–783. [33] Jeyhun Karimov, Tilmann Rabl, and Volker Markl. 2019. AJoin: Ad-hoc Stream Joins at Scale. Proceedings of the VLDB Endowment 13, 4 (2019), 435–448. [34] Jeyhun Karimov, Tilmann Rabl, and Volker Markl. 2019. AStream: Ad-hoc Shared Stream Processing. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 607–622. [35] Alfons Kemper, Donald Kossmann, and Christian Wiesner. 1999. Generalised Hash Teams for Join and Group-by. In Proceedings of the International Conference on Very Large Data Bases. 30–41. [36] Christoph Koch, Yanif Ahmad, Oliver Kennedy, Milos Nikolic, Andres Nötzli, Daniel Lupei, and Amir Shaikhha. 2014. DBToaster: Higher-Order Delta Processing for Dynamic, Frequently Fresh Views. The VLDB Journal 23, 2 (2014), 253–278. [37] Yannis Kotidis and Nick Roussopoulos. 1999. DynaMat: A Dynamic View Management System for Data Warehouses. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 371–382. [38] Fangyu Lei, Jixuan Chen, Yuxiao Ye, Ruisheng Cao, Dongchan Shin, Hongjin Su, Zhaoqing Suo, Hongcheng Gao, Wenjing Hu, Pengcheng Yin, Victor Zhong, Caiming Xiong, Ruoxi Sun, Qian Liu, Sida Wang, and Tao Yu. 2025. Spider 2.0: Evaluating Language Models on Real-World Enterprise Text-to-SQL Workflows. In Proceedings of the International Conference on Learning Representations. [39] Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, and Divesh Srivastava. 1995. Answering Queries Using Views. In Proceedings of the ACM SIGACT-SIGMODSIGART Symposium on Principles of Database Systems. 95–104. [40] Samuel Madden, Mehul A. Shah, Joseph M. Hellerstein, and Vijayshankar Raman. 2002. Continuously Adaptive Continuous Queries over Streams. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 49–60. [41] Darko Makreshanski, Georgios Giannikis, Gustavo Alonso, and Donald Kossmann. 2016. MQJoin: Efficient Shared Execution of Main-Memory Joins. Proceedings of the VLDB Endowment 9, 6 (2016), 480–491. [42] Volker Markl, Vijayshankar Raman, David E. Simmen, Guy M. Lohman, and Hamid Pirahesh. 2004. Robust Query Processing through Progressive Optimization. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 659–670. [43] Frank McSherry, Andrea Lattuada, Malte Schwarzkopf, and Timothy Roscoe. 2020. Shared Arrangements: Practical Inter-Query Sharing for Streaming Dataflows. Proceedings of the VLDB Endowment 13, 10 (2020), 1793–1806. [44] Frank McSherry, Derek Gordon Murray, Rebecca Isaacs, and Michael Isard. 2013. Differential Dataflow. In Proceedings of the Conference on Innovative Data Systems Research. 12 pages. [45] Hoshi Mistry, Prasan Roy, S. Sudarshan, and Krithi Ramamritham. 2001. Materialized View Selection and Maintenance Using Multi-Query Optimization. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 307–318. [46] Songsong Mo, Yile Chen, Hao Wang, Gao Cong, and Zhifeng Bao. 2023. Lemo: A Cache-Enhanced Learned Optimizer for Concurrent Queries. Proceedings of the ACM on Management of Data 1, 4 (2023), 247:1–247:26. [47] Rajeev Motwani, Jennifer Widom, Arvind Arasu, Brian Babcock, Shivnath Babu, Mayur Datar, Gurmeet Singh Manku, Chris Olston, Justin Rosenstein, and Rohit Varma. 2003. Query Processing, Approximation, and Resource Management in a Data Stream Management System. In Proceedings of the Conference on Innovative Data Systems Research. [48] Derek Gordon Murray, Frank McSherry, Rebecca Isaacs, Michael Isard, Paul Barham, and Martín Abadi. 2013. Naiad: a timely dataflow system. In Proceedings of the ACM Symposium on Operating Systems Principles. 439–455. [49] Fabian Nagel, Peter A. Boncz, and Stratis Viglas. 2013. Recycling in Pipelined Query Evaluation. In Proceedings of the IEEE International Conference on Data Engineering. 338–349. [50] Tomasz Nykiel, Michalis Potamias, Chaitanya Mishra, George Kollios, and Nick Koudas. 2010. MRShare: Sharing Across Multiple Queries in MapReduce. Proceedings of the VLDB Endowment 3, 1 (2010), 494–505. [51] Iraklis Psaroudakis, Manos Athanassoulis, and Anastasia Ailamaki. 2013. Sharing Data and Work Across Concurrent Analytical Queries. Proceedings of the VLDB Endowment 6, 9 (2013), 637–648. [52] Iraklis Psaroudakis, Manos Athanassoulis, Matthaios Olma, and Anastasia Ailamaki. 2014. Reactive and Proactive Sharing Across Concurrent Analytical Queries. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 889–892. [53] Lin Qiao, Vijayshankar Raman, Frederick Reiss, Peter J. Haas, and Guy M. Lohman. 2008. Main-Memory Scan Sharing for Multi-Core CPUs. Proceedings of the VLDB Endowment 1, 1 (2008), 610–621.
Genki Kimura and Kazuo Goda
[54] Vijayshankar Raman, Amol Deshpande, and Joseph M. Hellerstein. 2003. Using State Modules for Adaptive Query Processing. In Proceedings of the IEEE International Conference on Data Engineering. 353–364. [55] Vijayshankar Raman, Garret Swart, Lin Qiao, Frederick Reiss, Vijay Dialani, Donald Kossmann, Inderpal Narang, and Richard Sidle. 2008. Constant-Time Query Processing. In Proceedings of the IEEE International Conference on Data Engineering. 60–69. [56] Prasan Roy, S. Seshadri, S. Sudarshan, and Siddhesh Bhobe. 2000. Efficient and Extensible Algorithms for Multi Query Optimization. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 249–260. [57] Filippo Schiavio, Daniele Bonetta, and Walter Binder. 2023. DynQ: a dynamic query engine with query-reuse capabilities embedded in a polyglot runtime. The VLDB Journal 32, 5 (2023), 1111–1135. [58] Timos K. Sellis. 1988. Multiple-Query Optimization. ACM Transactions on Database Systems 13, 1 (1988), 23–52. [59] Mehul A. Shah, Joseph M. Hellerstein, Sirish Chandrasekaran, and Michael J. Franklin. 2003. Flux: An Adaptive Partitioning Operator for Continuous Query Systems. In Proceedings of the IEEE International Conference on Data Engineering. 25–36. [60] Dixin Tang, Zechao Shang, Aaron J. Elmore, Sanjay Krishnan, and Michael J. Franklin. 2019. Intermittent Query Processing. Proceedings of the VLDB Endowment 12, 11 (2019), 1427–1441. [61] Transaction Processing Performance Council. 2022. TPC Benchmark H (Decision Support) Standard Specification, Revision 3.0.1. https://www.tpc.org/TPC_ Documents_Current_Versions/pdf/TPC-H_v3.0.1.pdf Accessed: 2026-06-01. [62] Yicheng Tu, Mehrad Eslami, Zichen Xu, and Hadi Charkhgard. 2022. Multi-Query Optimization Revisited: A Full-Query Algebraic Method. In Proceedings of the IEEE International Conference on Big Data. 252–261. [63] Philipp Unterbrunner, Georgios Giannikis, Gustavo Alonso, Dietmar Fauser, and Donald Kossmann. 2009. Predictable Performance for Unpredictable Workloads.
Proceedings of the VLDB Endowment 2, 1 (2009), 706–717. [64] Stratis D. Viglas, Jeffrey F. Naughton, and Josef Burger. 2003. Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources. In Proceedings of the International Conference on Very Large Data Bases. 285–296. [65] Liang Wang and Chee-Yong Chan. 2013. Multi-Query Optimization in MapReduce Framework. Proceedings of the VLDB Endowment 7, 3 (2013), 145–156. [66] Qihang Wang, Decheng Zuo, Zhan Zhang, Yanjun Shu, Xin Liu, and Mingxuan He. 2024. Low-Latency Adaptive Distributed Stream Join System Based on a Flexible Join Model. Proceedings of the ACM on Management of Data 2, 3 (2024), 150:1–150:27. [67] Wentao Wu, Yun Chi, Hakan Hacigümüs, and Jeffrey F. Naughton. 2013. Towards Predicting Query Execution Time for Concurrent and Dynamic Database Workloads. Proceedings of the VLDB Endowment 6, 10 (2013), 925–936. [68] Yifei Yang, Hangdong Zhao, Xiangyao Yu, and Paraschos Koutris. 2024. Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries. In Proceedings of the Conference on Innovative Data Systems Research. 8 pages. [69] Xinyi Ye, Xiangyang Gou, Lei Zou, and Wenjie Zhang. 2025. AJOSC: Adaptive Join Order Selection for Continuous Queries. Proceedings of the ACM on Management of Data 3, 3 (2025), 126:1–126:27. [70] Wenqi Zhang, Yongliang Shen, Weiming Lu, and Yueting Zhuang. 2024. DataCopilot: Bridging Billions of Data and Humans with Autonomous Workflow. In Proceedings of the ICLR 2024 Workshop on Large Language Models for Agents. [71] Jingren Zhou, Per-Åke Larson, Johann Christoph Freytag, and Wolfgang Lehner. 2007. Efficient Exploitation of Similar Subexpressions for Query Processing. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 533–544. [72] Marcin Zukowski, Sándor Héman, Niels J. Nes, and Peter A. Boncz. 2007. Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS. In Proceedings of the International Conference on Very Large Data Bases. 723–734.