As the world’s first version-controlled SQL database and with 24.6k (and counting) stars on GitHub, Dolt has received a lot of interest from academic researchers over the years. In the past couple of weeks, I have been writing about the research with Dolt done by the TEST Lab at National University of Singapore. Last week, I wrote about Suyang Zhong’s work on SQLancer++. Today, I will be reviewing “Detecting Join Bugs in Database Engines via Join Implication Reasoning” by Zhaokun Xiang. This paper was published earlier this year as part of Proceedings of the ACM on Management of Data and presented at SIGMOD. Some of y’all may know Zhaokun Xiang as theoristcoder on GitHub – last year, I wrote about the changes made to zero time due to a bug found by Zhaokun. Now, let’s dive into the paper.
Join Implication Reasoning#
One of the biggest reasons to choose relational databases over their non-relational counterparts is the support for complex joins. In order to execute a join query as efficiently as possible, SQL query analyzers apply a series of optimization rules, including filter pushdowns, join reordering, memoization, and cost analysis. Many of these optimization rules have been implemented in go-mysql-server, the SQL query engine that powers Dolt. However, fast doesn’t always mean correct if the rules are not applied properly – after all, piping to /dev/null is fast as hell.
Join implication reasoning (JIR) is a testing technique implemented as an extension of SQLancer that focuses on join correctness. Oftentimes, a join query can be rewritten to use different join types and still produce the same result – this is the motivation for join reordering during query optimization. JIR takes these logically equivalent join queries and uses them as test oracles, making sure that a database actually returns the same result for both queries. The paper outlines six join-equivalence rules as well as proofs for each rule. For example, a left outer join can be rewritten as a combination of an inner join and an anti-join with appropriate null-padding. Another example is that a right outer join is the same as a left outer join with the sides of the join swapped and vice versa.
The implementation of JIR involves generating random join queries represented by abstract syntax trees (ASTs) and randomly generated boolean join predicates (also known as join conditions). More queries are subsequently generated by replacing the join types at each node of the ASTs. Equivalent queries are generated as well using the join-equivalence rules. Each pair of equivalent queries is run against the database and the results are compared.
JIR was implemented in both SQLancer and SQLancer++. While SQLancer was already able to generate joins, JIR extended it by generating joins with subqueries and adding randomly generated join conditions.
To compare the efficacy of JIR, databases were run with both JIR and differential query plan (DQP) extensions of SQLancer or SQLancer++, and the number of bugs found by each method were compared to each other. DQP is an earlier project from the TEST Lab which was published in 2024.
So does it use AI?#
Similar to SQLancer++, JIR uses rule-based generation and does not use a large language model (LLM) or generative neural network, so it does not use “generative AI” in the 2026 colloquial sense of the term. Someone 20 years ago might call it AI, but it’s unlikely that someone today would.
Impact on Dolt#
The paper claims to have found 12 unique bugs in Dolt via JIR and 3 unique bugs via DQP; at the time the paper was written, 10 out of 12 of the JIR-found bugs were fixed and all of the DQP-found bugs were fixed. From my perspective, I’m not able to identify via our issues queue whether a bug was found by JIR or DQP and what criterion for uniqueness was used, but Zhaokun did file 19 bugs between November 2025 and February 2026. As of February 10, 2026, every single bug has been fixed.
The majority of these bugs involved anti-joins. This makes sense since anti-joins often involve subqueries, which were previously not supported for join queries in SQLancer. There were also several bugs involving left joins and a few bugs involving how inner joins were optimized into other join types during join planning.
Correctness in Dolt is something we really value, and we are really appreciative of the work Zhaokun has done to ensure the correctness in joins. As mentioned in the paper, join bugs can be tricky to identify due to the number of optimization rules applied and they can get especially complex when multiple joins are involved.
Are you an academic researcher working on a project with Dolt or another DoltHub database? Join our Discord community – we’d love to hear from you.