Verification of Query Weak Equivalence in OLAP Databases
Yuxuan Wang, Peilei He · 2024
Modern database applications operate on massive data and support a range of complex queries, especially OLAP queries which are time-consuming. To accelerate query processing, a variety of methods for automatically verifying query equivalence have been proposed to avoid redundant executions of equivalent queries, mainly in a semantic sense. However, we have observed some queries that are not semantically equivalent also return the same tuples under the specific data distribution, which cannot be detected by most current automated verification of query equivalence. To deal with this issue, this paper proposes weak equivalence for identifying queries that are not semantically equivalent but produce the same results under the read-mostly scenarios such as OLAP. Specifically, for posed queries, we extract their filter condition expressions, which are then transformed into symbolic representations, namely first-order logic formulae. In terms of their partial order, i.e., containment relationship, we introduce Query Lattice, a novel structure that is constructed as a lattice that is partitioned into equivalence classes that are convex to answer queries if we determine they belong to the classes. The equivalence class enables stored queries to respond to future queries so that redundant generation of query plan and execution can be bypassed. Experimental evaluation of Query Lattice built on top of PostgreSQL shows that the maximum speedup that Query Lattice can achieve is 44.95% over the original PostgreSQL, when running on the datasets of both TPC-H and TPC-H Skew benchmarks.