State-of-the-art Text-to-SQL models rely on fine-tuning or few-shot prompting to help LLMs learn from training datasets containing mappings from natural language (NL) queries to SQL statements. Consequently, the quality of the dataset can greatly affect the accuracy of these Text-to-SQL models. Unlike other NL tasks, Text-to-SQL datasets are prone to errors despite extensive manual efforts due to the subtle semantics of SQL. Our study has found a non-negligible (>30%) portion of incorrect NL to SQL mapping cases exists in popular datasets Spider and BIRD. This paper aims to improve the quality of Text-to-SQL training datasets and thereby increase the accuracy of the resulting models. To do so, we propose a necessary correctness condition called execution consistency. For a given database instance, an NL to SQL mapping satisfies execution consistency if the execution result of an NL query matches that of the corresponding SQL. We develop SQLDriller to detect incorrect NL to SQL mappings based on execution consistency in a best-effort manner by crafting database instances that likely result in violations of execution consistency. It generates multiple candidate SQL predictions that differ in their syntax structures. Using a SQL equivalence checker, SQLDriller obtains counterexample database instances that can distinguish non-equivalent candidate SQLs. It then checks the execution consistency of an NL to SQL mapping under this set of counterexamples. The evaluation shows SQLDriller effectively detects and fixes incorrect mappings in the Text-to-SQL dataset, and it improves the model accuracy by up to 13.6%.

Effectively rewriting a wide range of complex and diverse queries is critical for database systems. Huawei GaussDB has been experiencing limited extensibility of its existing query rewriter. The problem is rooted in the need for one-size-fits-all rewrites by its pipelined rewrite workflow and the source code-level coupling of rewrite logic. This makes it not only difficult to identify generic, broadly applicable rewrites but also engineering-intensive to program them into the system. This paper presents GRewriter, GaussDB's new bolt-on extensible query rewriter powered by automated rewrite rule discovery. GRewriter sits atop the existing optimizer stack to explore useful rewrites, allowing a variety of rules to coexist and be selected on a per-query basis. A new rule language, G-DSL, is used to express rewrite rules so that the rewrite engine is not coupled with specific rules. To improve rewrite efficiency, a new rule index structure and a rewrite history cache are introduced. Rules in GRewriter are produced by an offline rule generator. With novel enumeration techniques and a new equivalence theorem, our rule generator can efficiently discover formally verified rules that are much more expressive than prior research prototypes. For operational convenience, GRewriter also supports manual rule authoring and interactive management of rules through familiar SQL interfaces. GRewriter has been integrated into GaussDB and is gradually rolling out to customers. GRewriter equips GaussDB with over a hundred rules while maintaining negligible overhead (<1%). These new rewrite rules have enhanced query performance for two key customer applications, an ERP system and a Banking transaction system, reducing production query latency by up to 99.9%—from 26 seconds to just 17 milliseconds.

Buffer management is critical for DBMSs but often suffers from scalability bottlenecks and poor cache locality, which stems from centralized reference counting in page access and intensive locking in page-to-buffer translation. However, prior radical approaches like pointer swizzling or optimistic lock can hardly be adopted in production-grade DBMSs due to its inherent complexity and incompatibility. This paper proposes ScaleCache , a scalable, highly-efficient and production-grade buffer management system with three key designs. ScaleCache first incorporates a novel compact per-group buffer reference counting technique, which enables scalable buffer pinning and unpinning by concurrent threads on many-core servers. It then devised a novel read-write lock based on copy-on-write and per-group reference counting, which is suitable for B-link tree. At last, we propose an optimistic, CPU-cache friendly and SIMD-accelerated hash table for fast and scalable page-to-buffer translation, which eliminates most contention on modern many-core hardware. ScaleCache has been adopted in Huawei GaussDB , a commercial high-performance DBMS. Evaluation on a 128-core server demonstrates that ScaleCache exhibits near-linear scalability and can significantly improve index query throughput of both classic B-link tree index and complex graph-based vector index.

Today, the wide adoption of distributed service-oriented applications has rendered multi-database transactions increasingly important. They protect cross-service workflows that access multiple database systems from concurrency anomalies and failures. This paper presents Sonata, a new multi-database transaction system that provides high performance, global serializability, and seamless integration with existing applications and database systems. Sonata builds on the theory of commitment ordering to ensure global serializability and uses two-phase commit for atomicity and durability. Instead of treating database systems as black box storage, Sonata reuses existing database systems' concurrency control yet refrains from exposing or modifying their internals. It performs additional non-blocking coordination only at prepare time via application-level shim layers, allowing applications to incorporate Sonata without changing their existing queries or database systems. Evaluation using TPC-C shows that Sonata incurs 7.1% coordination overhead on average and outperforms prior work by up to 1114.3%.

Modern web applications use databases to store their data. When processing user requests, these applications retrieve and store data in the database server, which incurs network round trips. These round trips significantly increase the application's latency. Previous approaches have attempted to reduce these round trips by prefetching query results or batching database accesses. However, neither method can efficiently reduce the latency when some queries depend on previous queries' results. In real-world applications, nearly 50% of the queries depend on the result of other queries. This paper presents WeBridge, the first system capable of synthesizing stored procedures for large-scale real-world web applications. First, WeBridge employs concolic execution technique to analyze the applications and generate stored procedures for hot program paths. Then, it seamlessly integrates the stored procedures into the application by extending the database access library. Finally, it improves the efficiency of the stored procedures with speculative execution. Evaluation using real-world web applications and workloads show that WeBridge achieves up to 79.8% median latency reduction and up to 2× peak throughput.

Many transactions in web applications are constructed ad hoc in the application code. For example, developers might explicitly use locking primitives or validation procedures to coordinate critical code fragments. We refer to database operations coordinated by application code as ad hoc transactions . Until now, little is known about them. This paper presents the first comprehensive study on ad hoc transactions. By studying 91 ad hoc transactions among eight popular open-source web applications, we found that (i) every studied application uses ad hoc transactions (up to 16 per application), 71 of which play critical roles; (ii) compared with database transactions, concurrency control of ad hoc transactions is much more flexible; (iii) ad hoc transactions are error-prone—53 of them have correctness issues, and 33 of them are confirmed by developers; and (iv) ad hoc transactions have the potential for improving performance in contentious workloads by utilizing application semantics such as access patterns. Based on these findings, we discuss the implications of ad hoc transactions to the database research community.

Today, most database-backed web applications depend on the database to handle deadlocks. At runtime, the database monitors the progress of transaction execution to detect deadlocks and abort affected transactions. However, this common detect-and-recover strategy is costly to performance as aborted transactions waste CPU resources.To avoid deadlock-induced performance degradation, developers aim to reorganize the application code to remove deadlocks. Unfortunately, doing so is difficult for web applications. Not only do their implementations include hundreds of thousands of LoCs, but they also use third-party object-relational mapping (ORM) frameworks which hide database access details. Consequently, it is hard for developers to accurately diagnose deadlocks.We propose WeSEER, a deadlock diagnosis tool for web applications. To overcome the opacity of ORMs, WeSEER performs concolic execution on unit tests to extract a web application’s transactions as a sequence of template statements with symbolic inputs as well as path conditions that enable the sequence. WeSEER then analyzes the extracted transactions based on fine-grained lock modeling to identify potential deadlocks and report the code locations that cause them. We implement WeSEER for Java-based (OpenJDK) web applications, and use it to analyze two popular open-source e-commerce applications, Broadleaf and Shopizer. WeSEER has successfully identified 18 potential deadlocks in Broadleaf and Shopizer. Eliminating these identified deadlocks can result in up to 39.5× and 4.5× throughput improvement for Broadleaf and Shopizer, respectively.

Proving the equivalence between SQL queries is a fundamental problem in database research. Existing solvers model queries using algebraic representations and convert such representations into first-order logic formulas so that query equivalence can be verified by solving a satisfiability problem. The main challenge lies in "unbounded summations", which appear commonly in a query's algebraic representation in order to model common SQL features, such as projection and aggregate functions. Unfortunately, existing solvers handle unbounded summations in an ad-hoc manner based on heuristics or syntax comparison, which severely limits the set of queries that can be supported. This paper develops a new SQL equivalence prover called SQLSolver, which can handle unbounded summations in a principled way. Our key insight is to use the theory of LIA^*, which extends linear integer arithmetic formulas with unbounded sums and provides algorithms to translate a LIA^* formula to a LIA formula that can be decided using existing SMT solvers. We augment the basic LIA^* theory to handle several complex scenarios (such as nested unbounded summations) that arise from modeling real-world queries. We evaluate SQLSolver with 359 equivalent query pairs derived from the SQL rewrite rules in Calcite and Spark SQL. SQLSolver successfully proves 346 pairs of them, which significantly outperforms existing provers.

Distributed transaction systems incur extensive cross-node communication to execute and commit serializable OLTP transactions. As a result, their performance greatly suffers. Caching data at nodes that execute transactions can cut down remote reads. Batching transactions for validation and persistence can amortize the communication cost during committing. However, caching and batching can significantly increase the likelihood of conflicts, causing expensive aborts. In this paper, we develop Hackwrench to address the challenge of caching and batching. Instead of aborting conflicted transactions, Hackwrench tries to repair them using fine-grained re-execution by tracking the dependencies of operations among a batch of transactions. Tracked dependencies allow Hackwrench to selectively invalidate and re-execute only those operations necessary to "fix" the conflict, which is cheaper than aborting and executing an entire batch of transactions. Evaluations using TPC-C and other micro-benchmarks show that Hackwrench can outperform existing commercial and research systems including FoundationDB, Calvin, COCO, and Sundial under comparable settings.

Many transactions in web applications are constructed ad hoc in the application code. For example, developers might explicitly use locking primitives or validation procedures to coordinate critical code fragments. We refer to database operations coordinated by application code as ad hoc transactions. Until now, little is known about them. This paper presents the first comprehensive study on ad hoc transactions. By studying 91 ad hoc transactions among 8 popular open-source web applications, we find that (i) every studied application uses ad hoc transactions (up to 16 per application), 71 of which play critical roles; (ii) compared with database transactions, concurrency control of ad hoc transactions is much more flexible; (iii) ad hoc transactions are error-prone-53 of them have correctness issues, and 33 of them are confirmed by developers; and (iv) ad hoc transactions have the potential to improve performance in contentious workloads by utilizing application semantics such as access patterns. Based on the findings, we discuss the implications of ad hoc transactions to the database research community.

Query rewriting transforms a relational database query into an equivalent but more efficient one, which is crucial for the performance of database-backed applications. Such rewriting relies on pre-specified rewrite rules. In existing systems, these rewrite rules are discovered through manual insights and accumulate slowly over the years. In this paper, we present WeTune, a rule generator that automatically discovers new rewrite rules. Inspired by compiler superoptimization, WeTune enumerates all valid logical query plans up to a certain size and tries to discover equivalent plans that could potentially lead to more efficient rewrites. The core challenge is to determine which set of conditions (aka constraints) allows one to prove the equivalence between a pair of query plans. We address this challenge by enumerating combinations of "interesting" constraints that relate tables and their attributes between each pair of queries. We also propose a new SMT-based verifier to verify the equivalence of a query pair under different enumerated constraints. To evaluate the usefulness of rewrite rules discovered by WeTune, we apply them on the SQL queries collected from the 20 most popular open-source web applications on GitHub. WeTune successfully optimizes 247 queries that existing databases cannot optimize, resulting in substantial performance improvements.

Multicore in-memory databases often rely on traditional con- currency control schemes such as two-phase-locking (2PL) or optimistic concurrency control (OCC). Unfortunately, when the workload exhibits a non-trivial amount of contention, both 2PL and OCC sacrifice much parallel execution op- portunity. In this paper, we describe a new concurrency control scheme, interleaving constrained concurrency con- trol (IC3), which provides serializability while allowing for parallel execution of certain conflicting transactions. IC3 combines the static analysis of the transaction workload with runtime techniques that track and enforce dependencies among concurrent transactions. The use of static analysis simplifies IC3's runtime design, allowing it to scale to many cores. Evaluations on a 64-core machine using the TPC- C benchmark show that IC3 outperforms traditional con- currency control schemes under contention. It achieves the throughput of 434K transactions/sec on the TPC-C bench- mark configured with only one warehouse. It also scales better than several recent concurrent control schemes that also target contended workloads.

This paper describes a map generalization program we submitted to the ACM SIGSPATIAL Cup 2014. In this competition, the goal is to remove as many points in a set of polygonal lines as quickly as possible with respect to two constraints. The topological relationships among the lines must not change, and the relationships between a set of control points and the lines must not change. Inspired by Visvalingam-Whyatt Algorithm, we iteratively examine successive triplets along each line, and remove the middle point if no control point or point of other lines is in the associated triangle. Based on the features of the training datasets, we further introduce many optimization techniques to speed up the computation.

This paper describes a point-polygon query program we submitted to the ACM SIGSPATIAL Cup 2013. Point-polygon topological relationship query is one of the core functions for commercial spatial databases, and also an active research topic in academia. Spatial indices are the key to achieve top performance. However, different datasets or query patterns require different indices for optimal performance. Based on the patterns of the training dataset, we build a hierarchy of indices, including polygon index, edge index, and interval index, which help find polygons near a point, calculate the distance from a point to a polygon, and determine whether a point is inside a polygon, respectively. Using the provided training dataset, these three indices reduce the computation time of "WITHIN n" query by 90%, 10%, and 50%, respectively. We build a large dataset with more than 1 million samples and 520 polygons by cloning and offsetting the training dataset 15 and 13 times, respectively. Our program finishes the "WITHIN 1000" query in only one second on a 4-core 3.3GHz Xeon Processor.