如何理解 sqlite 查询计划？

Question

我在 SQLite 上执行了一个查询，计划部分是

0|1|5|SCAN TABLE edges AS e1 (~250000 rows)
0|0|0|EXECUTE CORRELATED SCALAR SUBQUERY 2
2|0|0|SEARCH TABLE dihedral USING AUTOMATIC
COVERING INDEX (TYPE=? AND EDGE=?) (~7 rows)
0|0|0|EXECUTE CORRELATED SCALAR SUBQUERY 3
3|0|0|SEARCH TABLE bounds USING AUTOMATIC
COVERING INDEX (FACE=? AND EDGE=?) (~7 rows)

WHERE 中的查询是

exists (select dihedral.edge from dihedral where ihedral.type=2 and dihedral.edge=e1.edge) and
exists (select bounds.edge from bounds where bounds.face=f1.face and bounds.edge=e1.edge) and

我知道这不是一个高效的查询，Ｉ只是想提高性能。

这是我的猜测：

没有子查询展平，对吧？
这两个exist subquery引入了correlated subquery，实际上是作为indexed nested loop执行的，对吧？
阅读查询，因为table二面角和边界是独立的，都与外边相关table，所以计算复杂度为O(n^2)没有索引。不过，既然有覆盖索引，性能应该会好很多吧？我在 wiki 上发现，索引的性能 O(log(N)) 甚至更好，所以整体性能应该是 O(n*log(N))，对吗？

谁能帮助我了解发生了什么事？谢谢。

Answer 1

SQLite 确实支持 subquery flattening，但是对于像这里这样的 EXISTS 子查询来说这是不可能的。

AUTOMATIC 表明数据库专门为此查询创建了一个临时索引。这强烈表明您应该永久创建这些索引：

CREATE INDEX dihedral_type_edge ON dihedral(type, edge);
CREATE INDEX bounds_face_edge ON bounds(face, edge);

外部查询遍历所有 edge 行，并针对每一行在索引中进行搜索。这将导致 O(edge * (log(dihedral) + log(bounds)))。临时索引的创建需要对这些表进行排序，所以整个运行时间最终是O(dihedral*log(dihedral) + bounds*log(bounds) + edge*(log(dihedral)+log(bounds))).

如何理解 sqlite 查询计划？

How can I understand the sqlite query plan?

sqlite

sql-execution-plan