sql - 为什么 SELECT * WHERE id=1 ORDERBY at LIMIT 1 不像简单的二进制搜索那样在 O(log n) 中执行？

Question

答案:它确实在 O(log n) 中执行，就像简单的二进制搜索

前言:这实际上应该是 错误报告(针对所有 SQL 数据库实现) ，因为我发现了极端情况(这很常见， 应该很快 ，但不是)，我想确定一下。到目前为止，事实证明我是正确的，查询优化器不是最优的。

我对 SQL 完全陌生，但我知道数据结构和算法是如何工作的。我期待 查找所选单位/用户的最新记录/事件必须非常快，因为数据库正在使用 B-Tree(索引)并且该查询非常 类似于在排序数组中查找插入点 用于记录某些单位/用户 ID 和最大时间(或 id+1,time=0)。

SQL Fiddle Example

像这样创建表和索引:

create table t (
    id int, at time, id2 int
);

create unique index i on t (id, at);
create unique index i2 on t (id2);

insert into t (id, at, id2) values
    (1, '12:00', 1001200),
    (1, '12:30', 1001230),
    (2, '12:00', 2001200),
    (2, '13:00', 2001300);

并尝试以下查询:

select * from t
where id=1
order by at desc
limit 1;

select * from t
where id2<2000000
order by id2 desc
limit 1

当您分析这两个查询时，您会发现它首先获取与 where 匹配的所有行。条件(获取多行)，然后选择第一个( limit 1) 而不是直接搜索我想要的唯一一条记录 (到目前为止证明，这不是最佳的)。我整天都在搜索和询问，但找不到任何可以真正快速完成所需操作的查询。

可以通过编写正确的 SQL 查询来完成吗？ ....到目前为止的回答:否

原则上可以通过优化查询(计划)来完成吗？ ......到目前为止的回答:是的!

我的第二个查询说明了优化搜索应该如何工作: id2 = id*10000+at , 找到最高的 id2小于某个值( id2 <= 199999 与 id2 < 2000000 相同，并且有效 - 找到 1001230 这意味着 id=1, at="12:30" )。

我知道如何使用 binary_search (搜索 2000000 将返回插入点，它就在我想要的记录之后)我确信它可以用 B-Tree 完成，但为什么在 SQL 中不可能呢？如此有用的查询!

编辑 - 对评论的回应:
不幸的是，我现在无法在真实数据库上执行查询，但结果与 SQL Fiddle Example 完全相同。 :

Limit (cost=0.15..3.73 rows=1 width=16)  
      -> Index Scan Backward using i on t (cost=0.15..32.31 rows=9 width=16)   
         Index Cond: (id = 1)

唯一的区别是 最大估计成本 因为“向后索引扫描”是巨大的。查询本身以秒为单位(100 毫秒，取决于 ID 和该单元有多少记录)。无论如何，它应该做直接索引搜索，没有别的更快。我今天在 SE (SO+DBA) 中搜索了类似的示例，所有查询的工​​作方式都相同——索引扫描(可能是位图)和之后的 FETCH FIRST。

Answer 1

In any case, it should do direct index search, nothing else is faster.

它确实 正是 那。如果您使用 explain (analyze, buffers) 运行说明你会看到:

Limit  (cost=0.15..1.49 rows=1 width=16) (actual time=0.018..0.018 rows=1 loops=1)
  Buffers: shared hit=2
  ->  Index Scan Backward using i on t  (cost=0.15..12.19 rows=9 width=16) (actual time=0.015..0.015 rows=1 loops=1)
        Index Cond: (id = 1)
        Buffers: shared hit=2
Planning time: 0.184 ms
Execution time: 0.049 ms

(以上是在我调整 postgresql.conf 的安装中生成的 - 这就是为什么成本估算低于您的示例的原因)
Buffers: shared hit=2意味着 Postgres 恰好需要两次 I/O 操作(从缓存中提供服务)来获得结果——而且它的速度是最快的。

第一个 I/O 操作是在索引 Index Cond: (id = 1) 中查找行.但是由于索引只包含 ID 并且查询想要 全部 数据库必须执行另一个 I/O 操作才能获取所有列。

这就是为什么 select * 的原因之一。被认为是糟糕的编码风格——它给了规划者更少的选择来让它正确。

删除第二个 I/O 操作的唯一方法是放置 全部 列到索引中，那么您可能会看到 Index Only Scan Backwards - 但只有 4 行，这不太可能发生。

表中只有三列并且所有列都在索引中，理论上可以一起摆脱表并只保留索引。不幸的是，Postgres 不(还？)支持这一点。这在其他 DBMS 中可用。例如，在 Oracle 中，这被称为“仅索引表”。微软称其为“聚集索引”——如果这可能是对 Postgres 如何处理此类查询的唯一批评的话。

The only difference is that max estimated cost for that "Index Scan Backward" was huge

首先:“32”一点也不大。它甚至不是“大”。如果你仔细观察这个计划，你会发现外部节点的成本实际上是 减 (3.73) 那么内部的成本 Index Scan Backwards节点 - 因为计划者看到 limit子句并且知道它永远不会扫描整个索引 - 它会在第一行之后停止。

为 Index Scan Backwards 报告的成本如果节点需要完全执行，节点是理论总成本。

从聊天:

I know that searching for "highest smaller than" in sorted array (and B-tree) is simple and fast - O(log n) - just like finding exact value or insertion point. But when we did try to use SQL the result was useless, lasted too long.

好吧，当然是使用编程语言对内存结构进行 B-Tree 搜索，而无需考虑并发访问和事务 将更快。关系数据库必须处理 批号更多的东西然后是遍历 B 树的 C++ 程序。

关系数据库并不是解决所有问题的工具。如果您不需要事务一致性、并发控制和关系数据库(和 SQL)提供的所有其他功能，那么关系数据库很可能不是适合您的工具。

It usually is around 100ms which is not that bad, but sometimes becomes a bottleneck

您需要确定该查询是否受 I/O 限制或 CPU 限制，您可以使用 explain (analyze, timing, buffers) .如果它受 I/O 限制，那么您可能会考虑使用更多更快的 (=SSD) 硬盘。非常使用高端SSD
经常打 巨大的差异 - 特别是如果数据集不适合内存(如果您谈论的是 1530 亿行，这似乎是您的情况)

我用 1400 万行填充了示例表:每个 ID 有 10,000 个唯一 ID 和 1400 个“at”值。然后当我运行语句来查找单个 ID ( where id=1) 时，计划并没有真正改变:

Limit  (cost=0.56..1.23 rows=1 width=20) (actual time=0.026..0.027 rows=1 loops=1)
  Output: id, at, id2
  Buffers: shared hit=5
  ->  Index Scan Backward using i1 on stuff.t  (cost=0.56..1001.81 rows=1501 width=20) (actual time=0.024..0.024 rows=1 loops=1)
        Output: id, at, id2
        Index Cond: (t.id = 1)
        Buffers: shared hit=5
Planning time: 0.158 ms
Execution time: 0.054 ms

如您所见:与表仅包含 4 行时采用的第一个执行计划相比， Index Scan Backwards 的成本估算是 批号现在更高了，但运行时根本没有改变， 的成本外 节点还是一样的。所以不要取 LIMIT 所在的内部节点的成本。被用作计划是否“正确”的标准。

但是，我不确定这 5 个共享点击数来自哪里。也许是因为索引结构现在更大了。