SQLite Index Misuse in Transitive WHERE Clause Optimization

Transitive WHERE Clause Optimization Leading to Incorrect Index Usage

In SQLite, the query planner is designed to optimize query performance by leveraging indexes and simplifying WHERE clauses. However, a specific scenario involving transitive WHERE clauses can lead to incorrect index usage, resulting in suboptimal or even incorrect query results. This issue arises when SQLite attempts to use an index on one column to optimize a condition on another column due to transitive equality conditions in the WHERE clause.

Consider the following example schema and query:

CREATE TEMPORARY TABLE t0(c0 INT);
CREATE TEMPORARY TABLE t1(c0 INT, c1 INT);
CREATE INDEX t1_c0 ON t1(c0);
INSERT INTO t0(c0) VALUES (1), (-1), (2);
INSERT INTO t1(c0, c1) VALUES (1, 2), (2, -1), (-1, 1);

SELECT * FROM t0 CROSS JOIN t1 ON t1.c0 == t0.c0 AND t1.c1 == t0.c0;

In this query, the WHERE clause contains two conditions: t1.c0 == t0.c0 and t1.c1 == t0.c0. Due to the transitive property of equality, SQLite infers that t1.c0 == t1.c1 and attempts to use the index on t1.c0 to optimize both conditions. This leads to a situation where the index on t1.c0 is incorrectly used to optimize the condition on t1.c1, which can result in incorrect query results.

Transitive Equality Inference and Index Compatibility

The core issue lies in how SQLite handles transitive equality conditions in the WHERE clause. When SQLite encounters a WHERE clause of the form t1.c0 == t0.c0 AND t1.c1 == t0.c0, it infers that t1.c0 == t1.c1 due to the transitive property of equality. This inference is generally correct, but it can lead to incorrect index usage when the index on t1.c0 is used to optimize the condition on t1.c1.

The function whereScanInit in SQLite is responsible for scanning the WHERE clause for terms that can be optimized using indexes. The function looks for terms of the form X <op> <expr>, where X is a column of a table or an index. If the WHERE clause contains terms of the form X = Y, the function may also return terms of the form Y <op> <expr>. This behavior is intended to handle common SQL statements, but it can lead to incorrect index usage when the index on X is not compatible with the column Y.

In the example query, X is t1.c0, and Y is t0.c0. The function whereScanNext returns the term t1.c1 == t0.c0 because it infers that t1.c0 == t1.c1. However, the index on t1.c0 is not compatible with the column t1.c1, leading to incorrect index usage.

Correcting Query Plans and Ensuring Index Compatibility

To address this issue, it is essential to ensure that indexes are only used to optimize conditions on compatible columns. In the example query, the index on t1.c0 should only be used to optimize the condition t1.c0 == t0.c0, not the condition t1.c1 == t0.c0. This can be achieved by modifying the query planner to check the compatibility of the index with the column in the WHERE clause before using the index to optimize the condition.

One approach to correcting this issue is to modify the function whereLoopAddBtreeIndex to ensure that the index is only used to optimize conditions on the column it is defined on. This can be done by adding a check to verify that the column in the WHERE clause matches the column in the index before applying the index to optimize the condition.

For example, the following code snippet shows how to modify the function whereLoopAddBtreeIndex to ensure that the index is only used to optimize conditions on the column it is defined on:

function whereLoopAddBtreeIndex()
{
  ...
  // Check if the index column matches the WHERE clause column
  if(pProbe->aiColumn[saved_nEq] != pTerm->u.x.leftColumn) {
    // Do not use the index if the columns do not match
    return SQLITE_OK;
  }
  ApplyCostMultiplier(pNew->rRun, pProbe->pTable->costMult);
  nOutUnadjusted = pNew->nOut;
  pNew->rRun += nInMul + nIn;
  pNew->nOut += nInMul + nIn;
  whereLoopOutputAdjust(pBuilder->pWC, pNew, rSize);
  rc = whereLoopInsert(pBuilder, pNew);
  ...
}

This modification ensures that the index on t1.c0 is only used to optimize the condition t1.c0 == t0.c0, not the condition t1.c1 == t0.c0. By adding this check, the query planner will avoid using the index on t1.c0 to optimize the condition on t1.c1, preventing incorrect query results.

Additionally, it is important to consider the impact of NULL values on transitive equality conditions. In SQL, the result of a comparison involving NULL is unknown, which can affect the correctness of query optimizations. In the example query, if t0.c0 is NULL, the condition t1.c0 == t0.c0 will not hold, and the inference that t1.c0 == t1.c1 will be incorrect. Therefore, the query planner must handle NULL values carefully when optimizing transitive equality conditions.

To summarize, the issue of incorrect index usage in SQLite arises from the query planner’s handling of transitive equality conditions in the WHERE clause. By ensuring that indexes are only used to optimize conditions on compatible columns and carefully handling NULL values, it is possible to correct the query plan and prevent incorrect query results. The modifications to the function whereLoopAddBtreeIndex provide a practical solution to this issue, ensuring that the query planner generates correct and efficient query plans.