Source-linked AI summary
KathDB-FAO: Synthesized Query Plans in a Multimodal DBMS
Guorui Xiao, Douglas Brown, Artur Borycki, Magdalena Balazinska
TL;DR
Multimodal DBMSs lack an agreed query language, data model, and execution engine, while NL query plans can be costly to generate and optimize. KathDB-FAO parses queries into fine-grained actions, establishes contracts, groups actions into synthesized functions, and reuses functions. On SemBench, it cuts execution cost by 58.8% on average versus the next best system at comparable or better quality.
Problem
Multimodal DBMSs have no agreed query language, data model, or execution engine, and general-purpose agents do not optimize plans or reuse work across queries.
Source: §1 · p. 1Method
KathDB-FAO parses NL queries into atomic actions, establishes contracts on inputs and outputs, groups actions into synthesized function operators, and reuses functions across queries.
Source: §1 · p. 2, §2 · p. 3, §8 · p. 12Results
58.8% lower execution cost on average across SemBench scenarios than the next best system, at comparable or better quality.
Source: §8 · p. 13Takeaways & Limitations
The system achieves lower cost at comparable or better quality across SemBench scenarios by optimizing and reusing synthesized functions.
Source: §8 · pp. 12–13The optimizer does not perform logical reordering, such as operator or join reordering.
Source: §4 · p. 5
Abstract
from arXiv · showhide
We design, implement, and evaluate KathDB-FAO, a new query evaluation subsystem for our KathDB multimodal DBMS. KathDB-FAO takes as input a query in natural language (NL) and converts it into a query execution plan where each operator is a function whose body is synthesized during query evaluation, which allows powerful query-specific optimizations. To generate accurate and efficient plans from NL, KathDB-FAO first extracts fine-grained atomic actions for correctness, then establishes contracts on the inputs and outputs of those actions and groups them for efficiency, and finally synthesizes the function for each group on the fly. On SemBench, KathDB-FAO cuts execution cost by 58.8% on average across scenarios compared with the next best system, at comparable or better quality.
1 INTRODUCTION
KathDB-FAO addresses the lack of a settled way to query multimodal data by turning NL queries into optimized plans of synthesized functions. Its evaluation reports lower cost at comparable or better quality, while its approach groups fine-grained actions and reuses generated functions.
1 INTRODUCTION
- Multimodal DBMSs lack an agreed query language, data model, or execution engine, while general-purpose agents neither optimize plans nor reuse work across queries.The paper says these agents are much more expensive than KathDB-FAO at comparable quality.Source: §1 · p. 1
- Multimodal NL queries require semantic operations without canonical relational operators, and effective plans may need cost-aware ordering and early stopping.The uniform example combines price and category filters, image-based classification, per-brand counts, and sentiment extraction; fixed operator sets and bulk semantic steps limit optimization.Source: §1 · p. 2
- NL plan generation incurs per-query token and latency costs, which can dominate total cost on small datasets and repeated, overlapping queries.For example, changing a threshold from five qualifying items to three can require a full new plan if plans are regenerated from scratch.Source: §1 · p. 2
- KathDB-FAO synthesizes each plan operator as a function, groups atomic actions using contracts, and caches functions for reuse across queries.The optimizer can reason about function code, fuse semantic and relational operations, and exploit query-specific rewrites.Source: §1 · p. 2
- 58.8% lower execution cost on average across SemBench scenarios than the next best system, at comparable or better quality.KathDB-FAO achieves the best or tied-best quality in three of four scenarios and is within 0.02 of the best on the fourth.Source: §1 · p. 3
2 SYSTEM ARCHITECTURE AND FUNCTION-AS-OPERATOR (FAO)
KathDB processes NL queries through parsing, optimization, and bottom-up execution. Its FAO plan nodes represent functions over relations, while the optimizer establishes contracts, profiles an initial plan, and groups actions before deferred synthesis and execution.
2 SYSTEM ARCHITECTURE AND FUNCTION-AS-OPERATOR (FAO)
- The parser turns an NL query into a query sketch, the optimizer converts it into a logical DAG of FAOs, and the executor processes that DAG bottom-up.The system first registers and ingests data; the DBContext loads relational data into an RDBMS and registers file paths for multimodal data.Source: §2 · p. 3
- Each FAO is a function that takes one or more relations as input and outputs one or more relations; its components include an action-group ID, logic description, schemas, and implementation.In the prototype, relational data uses DuckDB.Source: §2 · p. 3
- The optimizer maps sketch actions to atomic FAOs, propagates parent input demands as contracts, profiles the initial plan, and groups actions before the executor synthesizes any new FAOs.The executor runs FAOs bottom-up, reusing profiled implementations when available and regenerating code after runtime exceptions.Source: §2 · p. 3
- The architecture raises three design questions: action granularity, action grouping, and caching and reuse of function implementations.Source: §2 · p. 3
3 PARSER: DECOMPOSING NL QUERIES
The Parser turns an NL query into a sequence of natural-language actions, deferring implementation decisions to later stages. It decomposes queries into semantically atomic actions so the Optimizer can decide which actions to group into functions.
3 PARSER: DECOMPOSING NL QUERIES
- A query sketch is a sequence of natural-language actions that captures the transformations needed to answer a query while deferring implementation decisions.The Parser’s action fields include a name, description, input and output relations, action category, and candidate functions relevant to later code generation.Source: §3 · pp. 3–4
- Actions are marked relational when they have standard semantics without model inference, or semantic when they require model-based interpretation of multimodal or unstructured content.The Parser can flag relevant functions, such as batch_inference, for later code generation.Source: §3 · p. 4
- Semantically atomic actions use the finest-grained decomposition that omits implementation details, leaving the Optimizer to choose each function’s scope.Coarser scopes offer more joint optimization but can make code harder to generate efficiently, less reusable, or incorrect.Source: §3 · p. 4
- Atomic actions expose materialized sentiment outputs, allowing generated code to canonicalize observed values with a dictionary and use the LLM only for unknown values.A single function may instead require O(n^2) LLM comparisons because it cannot see the extracted sentiments before generation.Source: §3 · p. 4
- Atomic actions yield the highest quality on hard queries with lower execution cost, but increase planning cost because code is generated per action.The Optimizer groups actions to further reduce execution cost, while the Executor reuses cached functions to lower planning cost.Source: §3 · p. 5
4 OPTIMIZER: OPTIMIZING FAO PLANS
The Optimizer starts from an atomic plan, groups actions to enable code-generation optimizations, and propagates consumer demands to establish contracts between functions. It searches legal groupings using estimated execution token usage as its objective.
4 OPTIMIZER: OPTIMIZING FAO PLANS
- An atomic plan can do unnecessary semantic work and cost up to 7× more than an optimized plan; independently synthesized operators can also produce incompatible values.A consumer may expect a formal/non-formal label while its producer emits free-text descriptions such as “business casual.”Source: §4 · p. 5
- Grouping is the sole rewrite primitive: Plan A shares image-classification prompts, while Plan B also fuses counting and threshold filtering to enable early exit.The design separates which actions to group from how their combined logic is implemented.Source: §4 · p. 5
- The initial design leaves logical reordering, such as operator or join reordering, to future work.Grouping preserves the plan’s logic and avoids the need to check equivalence.Source: §4 · p. 5
- The Optimizer minimizes estimated execution token usage over legal partitions, subject to a group-size cap because larger groups offer more optimization opportunities but are more complex and less reusable.Legal groups are convex in the action DAG; relational-only groups are excluded, while relational actions may join groups containing semantic actions.Source: §4 · p. 5
- The Optimizer profiles an atomic plan on a small uniform sample, then stub-executes candidate groups and scales their sample costs to estimate full-plan costs.This assumes the sample is representative; sample-scale execution may miss savings from control flow such as early exits.Source: §4 · p. 6
- Analytic LLM estimation predicts group call counts from generated code and profiling statistics, but its estimates can vary between runs and change plan rankings.For one group, estimates varied from approximately 30 to 45 calls across runs.Source: §4 · p. 6
- List-rank compares candidate partitions using rendered plans and avoids per-group cost estimates, while numeric estimators use dynamic programming over subsets of actions.Ranking width trades planning cost against ranking quality; DP scores feasible groups, whereas list-rank enumerates legal partitions under the group-size cap.Source: §4 · pp. 6–7
- Top-down demand propagation makes producers satisfy consumers’ schema and value requirements, such as emitting fixed classifier labels that let a count remain relational.The Optimizer starts from requirements on the final output and propagates demands through the DAG to input-producing nodes.Source: §4 · p. 7
5 EXECUTOR: GENERATING AND REUSING FUNCTIONS
The Executor generates and runs implementations for an optimized FAO plan, while caching selected functions for reuse across similar queries. Reuse can occur after parsing or earlier, when cached functions can shape the query sketch.
5 EXECUTOR: GENERATING AND REUSING FUNCTIONS
- Generating plans from scratch is expensive and inconsistent, motivating reuse of implementations across similar queries.On the E-Com scenario at a small scale factor, plan synthesis costs about 7.2× execution; repeated synthesis can also change the implementation.Source: §5 · p. 7
- When an FAO is cached, its query-specific hard-coded values become typed parameters while its function-body logic remains unchanged.The implementation is stored with documentation that is shown progressively to the Parser and Code Generator.Source: §5 · p. 7
- The system starts with an empty function library and uses llm-judge to save functions with non-trivial control flow and token-cutting algorithms.Saving every function is more expensive than selective saving, and prefilled simple operators can cost more in documentation tokens than reuse saves.Source: §5 · pp. 7–8
- Reuse-after saves code-generation cost but still pays for grouping search, whereas reuse-before can replace multiple atomic actions before optimization and reduce the search space.Reuse-before also avoids re-synthesis variance, but risks the Parser selecting a cached function that does not fit.Source: §5 · p. 8
6 EVALUATION
The evaluation tests KathDB-FAO on four SemBench scenarios spanning tabular, text, and image data, then examines action granularity, grouping, demand contracts, and function reuse.
6.1 (Q0) Main Result
- KathDB-FAO matches or exceeds ClaudeCode+ quality on three of four scenarios; on E-Com it trails by 0.02 (0.77 vs. 0.79) while executing at 2.2× lower cost.It achieves higher quality on every shared scenario than Palimpzest and lower execution cost than BigQuery on all three shared scenarios.Source: Table 2 · p. 9, §6.1 · p. 9
- At the largest scale, KathDB-FAO retains the highest quality and is cheapest at every scale, while its total cost grows little.Palimpzest times out on some queries at sf1000 and sf2000.Source: Figure 7 · p. 9, §6.1 · p. 9
6.3 (Q2) Grouping as a Rewrite
- On Additional, list-rank reaches 0.14× atomic execution cost versus 0.48× for llm-guess, while keeping plan-generation cost within 1.72× of atomic.List-rank matches atomic quality across the three scenarios; Figures 9 and 10 report execution and plan-generation costs.Source: Figure 9 · p. 10, Figure 10 · p. 10, §6.3 · pp. 10–11
6.2 (Q1) Action Granularity
- Atomic granularity achieves the highest quality on hard queries, while all three granularities perform similarly on easy queries.Single-action and llm-decided can choose coarse decompositions that hurt quality by hiding intermediate query results.Source: §6.2 · p. 10, Table 3 · p. 10
6.3 (Q2) Grouping as a Rewrite
- With list-rank, ranking width w=10 gives the best trade-off, and generating fused-group code only for the winning plan is cheapest for planning and execution.Generating code for every candidate costs more to plan without reducing execution cost; larger prompts can also lead to less optimized plans.Source: Figure 11 · p. 11, Figure 12 · p. 11, §6.3 · p. 11
6.4 (Q3) Contracts among FAOs
- Demand propagation improves quality and reduces execution cost by letting producers avoid semantic work their consumers do not need.Plan-generation cost remains nearly unchanged because demands are derived for all nodes in a single LLM call.Source: Figure 13 · p. 11, §6.4 · p. 11
6.5 (Q4) Function Reuse
- Reuse-before consistently lowers plan-generation cost on both similar and diverse workloads; it also lowers execution cost on the similar workload but offers little execution benefit on the diverse one.Reuse-before exposes cached functions before optimization, reducing the number of nodes and candidate groupings considered.Source: Figure 14 · p. 11, §6.5 · p. 12
7 RELATED WORK
KathDB-FAO differs from systems built around predefined semantic operators or fixed query plans: it synthesizes functions and searches over how to group them. This distinguishes its plan-level optimization from prior work on operator implementations, rewrites, and code generation.
7 RELATED WORK
- Unlike semantic-operator systems with fixed operator sets, KathDB-FAO synthesizes plan nodes and can express logic no predefined operator covers.Examples of fixed-set systems include LOTUS, Palimpzest, DocETL, and ThalamusDB.Source: §7 · p. 12
- Abacus searches implementations of fixed logical operators, GALOIS applies relational rewrites within a fixed algebra, and MOAR rewrites predefined DocETL pipelines.KathDB-FAO instead searches which actions to merge; unlike MOAR, it processes multimodal data and estimates candidate-plan cost without sample execution.Source: §7 · p. 12
- Unlike prior code-generation systems whose node computations are fixed before code is written, KathDB-FAO estimates alternative function-boundary costs and selects a plan.The passage contrasts this with compiled query engines, CodexDB, CAESURA, XMODE, Aryn, VOCAL-UDF, and Evaporate.Source: §7 · p. 12
8 CONCLUSION
KathDB-FAO parses natural-language queries into atomic actions, groups them into larger functions, and reuses functions across queries. On SemBench, it reduces execution cost while maintaining comparable or better quality.
8 CONCLUSION
- KathDB-FAO parses NL queries into fine-grained atomic actions, establishes input-output contracts, and groups actions into larger functions.The atomic decomposition supports reasoning about actions and their inputs and outputs.Source: §8 · p. 12
- KathDB-FAO reuses functions across queries to reduce plan-generation cost.Source: §8 · p. 12
- 58.8% lower average execution cost across SemBench scenarios than the next-best system, at comparable or better quality.The conclusion reports the average across scenarios.Source: §8 · p. 13