PostgreSQL WHERE 和 ORDER BY 子句的时间复杂度

Question

假设我们在 PostgteSQL 表 table1 上运行以下查询，其中列 col1 通过 b 树索引...

SELECT * FROM table1 WHERE col1='foo' ORDER BY col2;

查询的时间复杂度是否等于...

O(log(n) + m*log(m))

给定的n是table1中的行数，m是满足where子句的行数？

Answer 1

假设使用 O(n log n) 排序算法...

如果它确实使用索引，那么是的，搜索 B 树的时间复杂度为 O(log n)，排序行的时间复杂度为 O(m log m)。

但是，数据库是一个不能忽略常量的情况。与顺序扫描相比，索引查找的常数相对较高。如果表的大部分与 col1='foo' 匹配，Postgres 可能会认为全表扫描 O(n) 比索引更快，因为它的常数较低。那么就是 O(n + m log m)。

此外，m的大小会影响是否使用文件排序或内存排序，从而极大地影响效率。