cs.DBSep 23, 2026
SaveKathDB-FAO: Synthesized Query Plans in a Multimodal DBMS
Organizations: University of Washington · Teradata
Abstract
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.
Figures & tables
Figure 1 . KathDB-FAO achieves the best overall quality at the lowest or matching overall cost, including plan generation cost, across all systems, despite taking NL input and generating query plans on the fly, whereas BigQuery and Palimpzest require that the user write SQL or procedural plan code.
Figure 2 . Architecture of KathDB . DBContext registers and ingests data. Parser takes an NL query and produces a query sketch. Optimizer converts the sketch into a logical plan. Executor processes the DAG bottom-up, interleaving code generation with query evaluation, optionally using candidate functions registered in the Function Manager (Fn. Mgr.) .
Figure 3 . Example of a Function-as-Operator (FAO).
Figure 4 . Parser decomposes an NL query into a query sketch.
| Symbol | Meaning |
| , , | an atomic action; the set of atomic actions; |
| action category: RELATIONAL or SEMANTIC | |
| , | a group of actions fused into one FAO; its size |
| legal groups with at least one semantic action | |
| , , | a partition of ; all legal partitions; the one minimizing Eq. 1 |
| the function synthesized for group |
Table 1. Notation used in § 4 .
Figure 5 . The Optimizer in KathDB performs plan rewrites.
Figure 6 . Top-down demand propagation in Example 1 .
| Additional (sf1000, 400) | MMQA (excl. Q5, sf200) | E-Com (excl. Q14, sf500) | Movie (sf2000) | |||||||||||||||||
| System | plan t | plan \downarrow$ | exec t | exec \downarrow$ | qual. | plan t | plan \downarrow$ | exec t | exec \downarrow$ | qual. | plan t | plan \downarrow$ | exec t | exec \downarrow$ | qual. | plan t | plan \downarrow$ | exec t | exec \downarrow$ | qual. |
| KathDB-FAO | 125.2 | 0.73 | 119.4 | 0.030 | 0.92 | 53.6 | 0.34 | 134.3 | 0.031 | 0.85 | 96.1 | 0.57 | 399.1 | 0.079 | 0.77 | 63.3 | 0.38 | 217.6 | 0.004 | 0.81 |
| CAESURA + | OOM | 69.4 | 0.89 | 252.1 | 0.154 | 0.53 | 54.5 | 0.83 | 187.9 | 0.174 | 0.20 | 28.7 | 0.48 | 147.5 | 0.003 | 0.44 | ||||
| ClaudeCode | N/A | N/A | 238.6 | 4.399 | 0.86 | N/A | N/A | 343.0 | 34.676 | 0.70 | N/A | N/A | 370.6 | 10.520 | 0.72 | N/A | N/A | 85.5 | 1.402 | 0.81 |
| ClaudeCode + | 70.5 | 1.33 | 713.2 | 0.201 | 0.92 | 82.3 | 1.49 | 295.4 | 0.065 | 0.69 | 56.4 | 1.19 | 851.1 | 0.176 | 0.79 | 33.8 | 1.01 | 312.2 | 0.007 | 0.77 |
| Palimpzest | not implemented | N/A | N/A | 5646.9 ∗ | 7.161 | 0.78 | N/A | N/A | 2848.8 | 2.402 | 0.66 | N/A | N/A | 13547.6 ∗ | 1.309 | 0.52 | ||||
Table 2. Per-scenario results on SemBench (serial execution, except BigQuery). Each number is averaged over three runs per query, then over queries. Bold =best, underline =2nd, ranked among the generative systems only. ∗ =includes at least one query that timed out at the 12h cap, scored . OOM means a system fails due to out-of-memory in the current setup. BigQuery averages exclude the E-Com queries it cannot express (Q10, Q11).
Figure 7 . E-Com scalability: mean quality (left) and total cost (right, log-scaled), at three scale factors. means at least one query timed out at the 12h cap.
| Easy Queries | Hard Queries | |||
| Granularity | exec \downarrow$ | qual. | exec \downarrow$ | qual. |
| atomic | 0.080 | 0.873 | 0.099 | 0.453 |
| single-action | 0.078 | 0.846 | 0.272 | 0.433 |
| llm-decided | 0.101 | 0.878 | 0.117 | 0.408 |
Table 3. Impact of action granularity ( Additional , E-Com and MMQA scenarios). Each number is averaged over three runs. Bold =best, underline =2nd within each group.
Figure 8 . Quality for different plan cost comparison methods. Mean over three repetitions; whiskers show the range.
Figure 9 . Execution cost, relative to the atomic plan, for the same configurations and scenarios as Figure 8 . The horizontal reference line marks the atomic plan; bars beyond the y-axis range are marked with their rounded ratio.
Figure 10 . Plan-generation cost, relative to the atomic plan, for the same configurations as Figure 8 . Bars beyond the y-axis range are marked with their rounded ratio.
Figure 11 . The ranking width of list-rank: execution cost (left) and plan-generation cost (right), relative to the atomic plan (horizontal reference line). Quality varies by at most 0.04 across the knob settings and is skipped for space.
Figure 12 . The fused-group code-generation timing of list-rank: execution cost (left) and plan-generation cost (right), relative to the atomic plan (horizontal reference line).
Figure 13 . Effect of demands propagation evaluated over Additional scenario.
Figure 14 . Effect of letting cached functions steer the Parser. Library policy fixed to llm-judge.