An Extensible and Verifiable Language for Query Rewrite Rules
Sicheng Pan, Shuxian Wang, Wesley Zheng, Zirong Zeng, Vijay Sharma, Alvin Cheung · 2026
Read An Extensible and Verifiable Language for Query Rewrite Rules by Sicheng Pan, Shuxian Wang, Wesley Zheng, Zirong Zeng, Vijay Sharma, Alvin Cheung (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-05536.txt.
Introduction
Database engines rewrite queries into faster equivalent forms, but the rewrite rules are usually hand-coded inside each engine. Sicheng Pan and five co-authors introduce Rulescript, a language for writing those rules once and using them anywhere. Rules split into a matching phase and a transformation phase over a core algebra.
Every rewrite is verified formally, so correctness does not rest on testing alone. The team reimplemented thirty-three rules from Apache Calcite and deployed them to CockroachDB and Apache Data Fusion. Only a light adapter was needed per engine, supporting their write-once claim.
Catalog record
| CREATOR | Sicheng Pan, Shuxian Wang, Wesley Zheng, Zirong Zeng, Vijay Sharma, Alvin Cheung |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.05536
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Extensible and Verifiable Language for Query Rewrite Rules Sicheng Pan, Shuxian Wang, Wesley Zheng, Zirong Zeng, Vijay Sharma, Alvin Cheung Abstract . Logical query plan rewriting transforms a relational database query into an equivalent but more efficient form and is crucial to the performance of database-backed applications. In existing systems, rewrite rules are typically implemented manually, tightly coupled to specific execution engines, and often lack formal correctness guarantees. Consequently, developing a new engine requires reimplementing both legacy and new rules, incurring significant engineering cost, limiting portability, and every new implementation is an opportunity for introducing new bugs. We introduce RuleScript , an engine-agnostic domain-specific language (DSL) for developing query rewrite rules. RuleScript separates rule definition from execution infrastructure via a relational algebra-inspired core language, and an explicit decomposition of rules into matching and transformation phases. Developers express rewrites by pattern-matching query plans using RuleScript ’s core operators and constructing semantically equivalent transformed plans, with all rewrites automatically verified formally to ensure correctness. RuleScript is also extensible: users can define custom operators in terms of the core language to capture engine-specific semantics. To integrate with an existing system, developers need only implement a lightweight adapter that maps RuleScript ’s core and custom operators to the operators implemented in the target engine. We evaluate RuleScript by reimplementing 33 rewrite rules from Apache Calcite and extending the language with several custom operators. To demonstrate portability, we automatically deploy these rules to CockroachDB and Apache Data Fusion, two engines with substantially different backends. Our results show that RuleScript enables “write once, deploy everywhere” paradigm for query plan rewriting, with minimal effort required to deploy previously written rules on a new data engine. † † authors: . PVLDB Reference Format: PVLDB, 18(1): XXX-XXX, 2025. doi:XX.XX/XXX.XX † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 18, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX 1. Introduction Query processing is the task of executing data operations that conform to the semantics specified by a user’s query. Central to this process is query optimization, whose objective is to identify the most efficient execution plan among all plans that are semantically equivalent to the input query. Given the vast search space of possible plans, modern optimizers rely heavily on query transformations to improve performance while preserving correctness. Since the seminal System R project ( 1 ; 15 ) and the development of extensible optimizer frameworks such as Volcano and Cascades ( 8 ; 9 ) , logical plan rewriting has been a foundational technique in relational query optimization. Logical rewriting is driven by query rewrite rules , each of which matches a specific structural pattern in a query plan and transforms it into a semantically equivalent but potentially more efficient plan. For example, a rule may detect a selection operator applied after a join and rewrite the plan by pushing the selection below the join, thereby reducing the size of intermediate results and lowering execution cost. Over time, as optimization techniques have evolved, the number and sophistication of rewrite rules in production systems have also grown substantially. This growth, however, has introduced significant engineering challenges. Modern engines often maintain hundreds of rewrite rules. For instance, Apache Calcite ( 2 ) contains more than one hundred logical rewrite rules, each implemented in imperative Java code and tightly integrated with the optimizer’s internal representation. Similarly, the commercial CockroachDB database ( 18 ) includes more than two hundred rewrite rules expressed in its own domain-specific language (DSL). As the rule base expands, so does the cost of development, maintenance, and portability. When building a new engine or refactoring an existing one, developers must frequently reimplement existing rules against a new backend representation, a process that is both time-consuming and error-prone. A more fundamental issue concerns correctness. Rewrite rules are intended to be semantics-preserving: for every possible database instance, the rewritten plan should produce the same result as the original plan. In practice, however, rewrite rules in major database systems are rarely accompanied by formal proofs of correctness, and subtle bugs have repeatedly arisen from incorrect transformations ( 11 ; 17 ; 13 ; 14 ) . Automated query equivalence solvers, such as Cosette, HoTTSQL, QED, and SPES ( 4 ; 5 ; 26 ; 27 ) , offer a principled way to verify semantic equivalence. One approach is to invoke such solvers on every optimized query, comparing the original and rewritten plans. Unfortunately, this strategy incurs significant runtime overhead, as equivalence checking can be computationally expensive and unsuitable for use within the tight latency constraints of query optimization. A more scalable alternative is to verify the rewrite rules themselves rather than each rewritten query instance , and the HoTTSQL language ( 5 ) represents an important step in this direction. It provides a DSL based on SQL for expressing query semantics and integrates with the Cosette solver ( 4 ) to verify equivalence between plans written in the language. While effective in certain settings, HoTTSQL has notable limitations: incomplete support for SQL features such as Null semantics and integrity constraints restricts its coverage, and it is not integrated with production data engines. As a result, developers must manually translate the verified rules into engine-specific implementations, reintroducing duplication and potential inconsistencies. On the other hand, systems such as CockroachDB provide their own DSLs for specifying rewrite rules and can automatically generate corresponding implementations ( 22 ) . However, these DSLs are tightly coupled to a single engine and lack formal verification guarantees. Rules written in such languages cannot be easily reused across systems, nor can their correctness be formally assured. In this paper, we introduce RuleScript , an extensible, verifiable, and engine-agnostic rule language for logical query plan rewriting. The core syntax of RuleScript is based on relational algebra operators such as projection, selection, and join. Unlike concrete query plans derived from executable SQL statements, RuleScript plans may contain uninterpreted symbols , including uninterpreted relations, functions, and types. These symbols act as typed placeholders that can be instantiated with arbitrary concrete plans or expressions of the appropriate form. For example, an uninterpreted predicate may represent any Boolean expression over a given schema, while an uninterpreted relation may denote any plan that produces tuples of a specified structure. This abstraction enables a single RuleScript rule to succinctly describe an entire family of concrete rewrites. All rewrite rules expressed in RuleScript are formally verified. During verification, the system reasons universally over all valid instantiations of uninterpreted symbols. A rule is accepted only if semantic equivalence holds for every possible assignment, ensuring that no concrete instantiation can violate correctness. In this way, RuleScript provides strong, rule-level correctness guarantees without requiring equivalence checks during query optimization at runtime. To support engine independence, each RuleScript rule consists of two query plans: a match pattern and a transform pattern . Applying a rule to a concrete plan requires identifying an instantiation of uninterpreted symbols under which the match pattern corresponds to a subplan