SQLite 3.35 Query Optimization Issue with UNION ALL Subqueries
SQLite 3.35 Query Performance Degradation Due to UNION ALL Subquery Flattening
The core issue revolves around a significant performance degradation observed in SQLite 3.35 when executing queries involving subqueries with multiple UNION ALL operations. This degradation manifests as excessive CPU usage and query stalling, particularly affecting applications like tracker-miner-fs-3, which rely on such queries for initialization. The problem was traced back to a specific optimization introduced in SQLite 3.35 that allows subqueries using UNION ALL to be flattened, even if the parent query is a join. While this optimization was intended to improve query performance by reducing the complexity of query execution plans, it inadvertently led to an exponential growth in the size of the parse tree when applied repeatedly. This growth results in a substantial increase in computational overhead, causing the query to stall and burn CPU cycles.
The issue was first reported after upgrading from SQLite 3.34.1 to 3.35.0, where queries that previously executed quickly began to exhibit severe performance issues. The problem persisted even in SQLite 3.35.1, indicating that the optimization’s impact was not immediately recognized or addressed in subsequent patches. The specific commit identified as the root cause is de9ed6293de53e89b7c37e7de9a8697d86d7f619, which introduced the UNION ALL flattening optimization. The issue was further bisected and confirmed through detailed analysis, including the provision of a reproducible test case and database schema, which allowed for a deeper investigation into the underlying mechanics of the optimization and its unintended consequences.
Excessive Parse Tree Growth from Repeated UNION ALL Flattening
The primary cause of the performance degradation is the unchecked growth of the parse tree due to the repeated application of the UNION ALL flattening optimization. In SQLite 3.35, the optimization allows subqueries containing UNION ALL operations to be flattened into the parent query, reducing the number of intermediate steps required to execute the query. However, when this optimization is applied repeatedly, particularly in queries with a large number of UNION ALL operations, the parse tree grows exponentially. This growth leads to a significant increase in the computational resources required to process the query, resulting in excessive CPU usage and query stalling.
The parse tree is a data structure used by SQLite to represent the syntactic structure of a SQL query. When a query is parsed, SQLite constructs a parse tree that encapsulates the relationships between different parts of the query, such as joins, subqueries, and UNION operations. The flattening optimization aims to simplify this tree by merging subqueries into the parent query, thereby reducing the depth and complexity of the tree. However, in cases where the query contains a large number of UNION ALL operations, the flattening process can lead to a combinatorial explosion in the size of the parse tree. This explosion occurs because each UNION ALL operation introduces additional branches into the tree, and the flattening optimization compounds these branches, resulting in a tree that is orders of magnitude larger than the original.
The impact of this parse tree growth is particularly pronounced in queries that involve multiple levels of nested subqueries with UNION ALL operations. In such cases, the flattening optimization is applied recursively, causing the parse tree to grow at an exponential rate. This growth not only increases the memory footprint of the query but also significantly extends the time required to generate and optimize the query execution plan. As a result, queries that previously executed in milliseconds can stall for seconds or even minutes, consuming substantial CPU resources in the process.
Mitigating Parse Tree Growth with Query Optimization Limits
To address the issue of excessive parse tree growth, a patch was introduced in SQLite that limits the application of the UNION ALL flattening optimization when the number of subqueries within a statement exceeds a predefined threshold. This threshold, set at 500 subqueries, prevents the optimization from being applied in cases where it would lead to an unacceptable increase in parse tree size. The patch, identified by the check-in 9520bed2bd87dc56, effectively mitigates the performance degradation by disabling the optimization in scenarios where it would cause more harm than good.
The implementation of this limit involves modifying the SQLite query optimizer to track the number of subqueries within a statement as it parses and optimizes the query. When the number of subqueries exceeds the threshold, the optimizer skips the flattening optimization for that statement, reverting to the previous behavior where subqueries are processed as separate entities. This approach ensures that the parse tree remains manageable in size, preventing the exponential growth that leads to performance degradation.
While the introduction of a hard-coded threshold provides an immediate solution to the problem, it is recognized as a temporary measure. The SQLite development team has indicated that further investigation into more robust prevention strategies is planned for future releases. These strategies may include dynamic thresholds based on the complexity of the query, more sophisticated optimization techniques that avoid parse tree growth, or alternative approaches to query flattening that do not rely on recursive application of the optimization.
In addition to the patch, developers experiencing this issue can take several steps to mitigate its impact on their applications. One approach is to refactor queries to reduce the number of UNION ALL operations, thereby minimizing the potential for parse tree growth. This can be achieved by consolidating subqueries, using temporary tables to store intermediate results, or employing other SQL constructs that achieve the same result without the need for multiple UNION ALL operations. Another approach is to monitor query performance and identify queries that are particularly susceptible to the issue, applying the patch or other optimizations as needed.
In conclusion, the performance degradation observed in SQLite 3.35 due to the UNION ALL flattening optimization is a result of unchecked parse tree growth. The introduction of a subquery limit provides an effective short-term solution, while ongoing development efforts aim to deliver more robust and flexible optimization strategies in future releases. By understanding the underlying causes and implementing appropriate mitigations, developers can ensure that their applications continue to perform efficiently even when using complex queries with multiple UNION ALL operations.
