SQLite EXPLAIN解读与无索引查询优化相关问题咨询

背景信息 #

我正在编写一份在线SQL小指南，用于讲解索引的相关知识。所用表结构如下：

CREATE TABLE fdic (id integer primary key autoincrement,
                   primitive text,
                   v text,
                   v_a text)

该表约有300万行数据：

• v列：包含带大写字母和变音符号的词汇，无索引
• v_a列：v列词汇的小写且移除变音符号的版本，已建立非唯一索引

案例1：使用已建索引的查询 #

执行以下查询（查找存在正序和逆序形式但非回文的词汇）：

SELECT a.v originale,b.v contrario
FROM fdic a
INNER JOIN fdic b ON a.v_a=rev(b.v_a) 
WHERE length(a.v_a)>3 
AND a.v_a<>rev(a.v_a)

注：rev()是自定义字符串反转函数，仅用于v_a列（不支持多字节字符）

查询耗时2.7秒，对应的EXPLAIN结果：

addr    opcode  p1  p2  p3  p4  p5  comment
0   Init    0   27  0       0   
1   Integer 10000   1   0       0   
2   OpenRead    1   2   0   4   0   
3   OpenRead    0   2   0   4   0   
4   OpenRead    2   38110   0   k(2,,)  2   
5   Rewind  1   26  0       0   
6   Column  1   3   3       0   
7   Function    0   3   2   rev(1)  0   
8   IsNull  2   25  0       0   
9   Affinity    2   1   0   B   0   
10  SeekGE  2   25  2   1   0   
11  IdxGT   2   25  2   1   0   
12  DeferredSeek    2   0   0       0   
13  Column  2   0   4       64  
14  Function    0   4   3   length(1)   0   
15  Le  5   24  3       80  
16  Column  2   0   3       0   
17  Column  2   0   6       0   
18  Function    0   6   4   rev(1)  0   
19  Eq  4   24  3   BINARY-8    82  
20  Column  0   2   7       0   
21  Column  1   2   8       0   
22  ResultRow   7   2   0       0   
23  DecrJumpZero    1   26  0       0   
24  Next    2   11  1       0   
25  Next    1   6   0       1   
26  Halt    0   0   0       0   
27  Transaction 0   0   5   0   1   
28  Integer 3   5   0       0   
29  Goto    0   1   0       0   

第11行的IdxGT显示查询使用了v_a列的预建索引，符合预期。

案例2：使用无索引列的意外高效查询 #

将关联条件改为使用无索引的v列，执行以下查询：

SELECT a.v originale,b.v contrario
FROM fdic a
INNER JOIN fdic b ON a.v=rev(b.v) 
WHERE length(a.v)>3 
AND a.v<>rev(a.v)

预期会出现O(n²)时间复杂度，但实际仅耗时12秒，远快于预期。对应的EXPLAIN结果：

addr    opcode  p1  p2  p3  p4  p5  comment
0   Init    0   40  0       0   
1   Integer 10000   1   0       0   
2   OpenRead    1   2   0   3   0   
3   OpenRead    0   2   0   4   0   
4   Rewind  1   39  0       0   
5   Once    0   19  0       0   
6   OpenAutoindex   2   3   0   k(3,B,,)    0   
7   Blob    10000   2   0       0   
8   Rewind  0   19  0       0   
9   Column  0   3   4       64  
10  Function    0   4   3   length(1)   0   
11  Le  5   18  3       80  
12  Column  0   2   6       0   
13  Column  0   3   7       0   
14  Rowid   0   8   0       0   
15  MakeRecord  6   3   3       0   
16  FilterAdd   2   0   6   1   0   
17  IdxInsert   2   3   0       16  
18  Next    0   9   0       3   
19  Column  1   2   3       0   
20  Function    0   3   9   rev(1)  0   
21  IsNull  9   38  0       0   
22  Affinity    9   1   0   B   0   
23  Filter  2   38  9   1   0   
24  SeekGE  2   38  9   1   0   
25  IdxGT   2   38  9   1   0   
26  Column  2   1   4       64  
27  Function    0   4   3   length(1)   0   
28  Le  5   37  3       80  
29  Column  2   1   3       0   
30  Column  2   1   10      0   
31  Function    0   10  4   rev(1)  0   
32  Eq  4   37  3   BINARY-8    82  
33  Column  2   0   11      0   
34  Column  1   2   12      0   
35  ResultRow   11  2   0       0   
36  DecrJumpZero    1   39  0       0   
37  Next    2   25  0       0   
38  Next    1   5   0       1   
39  Halt    0   0   0       0   
40  Transaction 0   0   5   0   1   
41  Integer 3   5   0       0   
42  Goto    0   1   0       0   

第25行出现IdxGT，以下是针对相关问题的解析：

问题解答 #

1. 第二个查询是否使用了索引？ #

是，但并非预建的持久化索引，而是SQLite自动创建的临时内存索引（Autoindex）。从EXPLAIN结果的第6行OpenAutoindex可以看出，SQLite在执行前会扫描全表，将符合length(a.v)>3条件的v列值和对应行ID存入临时索引，后续关联查询时通过这个临时索引快速查找匹配项，避免了全表扫描的嵌套循环。

2. 如何触发O(n²)复杂度的查询，以便讲解索引的作用？ #

要强制SQLite不使用自动临时索引，可以通过以下方式：

• 执行PRAGMA optimize=0;关闭查询优化器的自动索引功能
• 使用NO INDEX提示，明确指定不使用任何索引

示例改写后的查询（强制禁用索引）：

PRAGMA optimize=0;
SELECT a.v originale,b.v contrario
FROM fdic a NO INDEX
INNER JOIN fdic b NO INDEX ON a.v=rev(b.v) 
WHERE length(a.v)>3 
AND a.v<>rev(a.v);

此时SQLite会退化为嵌套循环全表扫描，时间复杂度变为O(n²)，查询耗时会显著增加（可能达到数分钟甚至更久）。

3. SQLite进行了哪些优化来避免O(n²)复杂度？ #

SQLite通过以下优化避免了O(n²)的嵌套循环：

• 自动临时索引（Autoindex）：当查询中存在无索引列的等值关联时，SQLite会自动扫描符合过滤条件的数据集，将关联键和行ID存入内存临时索引，把后续的嵌套循环查询转换为索引查找，时间复杂度从O(n²)降低到O(n log n)
• 提前过滤数据：在创建临时索引前，先通过length(a.v)>3过滤掉不符合条件的行，减少临时索引的大小，进一步提升效率
• 执行计划成本评估：查询优化器会对比嵌套循环、临时索引等不同执行路径的成本，自动选择最优方案，而非直接采用低效的全表扫描

内容的提问来源于stack exchange，提问作者San Pei