用于有效范围聚合查询的数据库？

Question

作为一个简化的例子，假设我有一个这样的表：

seq | value
----+------
102 | 11954
211 | 43292
278 | 19222
499 |  3843

该表可能包含数亿条记录，我需要经常做这样的查询：

SELECT sum(value) WHERE seq > $a and seq < $b

即使seq被索引，典型的数据库实现也会遍历每一行以计算最佳情况下的总和O(n)，其中n是范围的大小。

是否有任何数据库可以像O(log(n))每个查询一样有效地执行此操作？

我所遇到的数据结构称为段树所描述这里。有时也称为范围树或区间树，尽管所有这些名称通常被描述为数据结构的略微不同的变体。

但是，我还没有遇到任何实现这种数据结构的数据库。对于内存结构来说，从头开始实现它很容易，但如果它必须持久化或太大而无法放入内存，则变得棘手。如果有一种在现有数据库之上实现这一点的有效模式，那也会有所帮助。

旁注：这不是仅附加表，因此在这种情况下，诸如保留累积总和之类的解决方案将不起作用。

Answer 1

使用 SQL Server ColumnStore索引

好吧，只有一个——一个聚集的 CS 索引。

如果您想了解我所做的硬件，请前往此处。完全披露，我在我工作的公司的网站上写了那篇博文。

进入测试！

这里有一些通用代码来构建一个相当大的表。与 Evan 相同的警告，这可能需要一段时间来构建和索引。

USE tempdb

CREATE TABLE t1 (Id INT NOT NULL, Amount INT NOT NULL)

;WITH T (N)
AS ( SELECT X.N
     FROM ( 
      VALUES (NULL), (NULL), (NULL),
             (NULL), (NULL), (NULL),
             (NULL), (NULL), (NULL), 
             (NULL) ) AS X (N) 
           ), NUMS (N) AS ( 
            SELECT TOP ( 710000000 ) 
                    ROW_NUMBER() OVER ( ORDER BY ( SELECT NULL )) AS N
            FROM   T AS T1, T AS T2, T AS T3, 
                   T AS T4, T AS T5, T AS T6, 
                   T AS T7, T AS T8, T AS T9, 
                   T AS T10 )
INSERT dbo.t1 WITH ( TABLOCK ) (
    Id, Amount )
SELECT NUMS.N % 999 AS Id, NUMS.N % 9999 AS Amount
FROM   NUMS;

--(705032704 row(s) affected) --Aw, close enough

那么，埃文赢得了简化，但我已经谈到了这之前。

这是索引定义。啦啦啦啦啦啦啦啦啦

CREATE CLUSTERED COLUMNSTORE INDEX CX_WOAHMAMA ON dbo.t1

查看计数，每个 Id 都有一个非常均匀的分布：

SELECT t.Id, COUNT(*) AS [Records]
FROM dbo.t1 AS t
GROUP BY t.Id
ORDER BY t.Id

结果：

Id  Records
0   5005005
1   5005006
2   5005006
3   5005006
4   5005006
5   5005006

...

994 5005005
995 5005005
996 5005005
997 5005005
998 5005005

每个 Id 大约有 5,005,005 行，我们可以查看非常小的 ID 范围，以获得 1000 万行总和。

SELECT COUNT(*) AS [Records], SUM(t.Amount) AS [Total]
FROM   dbo.t1 AS t
WHERE  t.Id > 0
       AND t.Id < 3;

结果：

Records     Total
10010012    50015062308

查询个人资料：

Table 't1'. Scan count 6, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 2560758, lob physical reads 0, lob read-ahead reads 0.
Table 't1'. Segment reads 4773, segment skipped 0.
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

 SQL Server Execution Times:
   CPU time = 564 ms,  elapsed time = 106 ms.

为了好玩，一个更大的聚合：

SELECT COUNT(*) AS [Records], SUM(CONVERT(BIGINT, t.Amount)) AS [Total]
FROM   dbo.t1 AS t
WHERE  t.Id > 0
       AND t.Id < 101;

结果：

Records     Total
500500505   2501989114575

查询个人资料：

Table 't1'. Scan count 6, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 2560758, lob physical reads 0, lob read-ahead reads 0.
Table 't1'. Segment reads 4773, segment skipped 0.
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

 SQL Server Execution Times:
   CPU time = 1859 ms,  elapsed time = 321 ms.

希望这可以帮助！

Answer 2

带有BRIN 索引的 PostgreSQL

即使 seq 已建立索引，典型的数据库实现也会循环遍历每一行来计算最佳情况下的总和 O(n)，其中 n 是范围的大小。

这不是真的。至少，没有像样的数据库可以做到这一点。PostgreSQL 支持在此类表上创建BRIN 索引。BRIN 索引非常小，即使在这么大的表上也可以放入内存中。数亿行不算什么。

在这里，3 亿行的定义与您所订购的一样。警告创建它可能需要很长时间（时间：336057.807 毫秒 + 索引 95121.809 毫秒）。

CREATE TABLE foo
AS
  SELECT seq::int, trunc(random()*100000)::int AS v
  FROM generate_series(1,3e8) AS gs(seq);

CREATE INDEX ON foo USING BRIN (seq);

ANALYZE foo;

现在...

EXPLAIN ANALYZE SELECT sum(v) FROM foo WHERE seq BETWEEN 424242 AND 6313376;
                                                                QUERY PLAN                                                                 
-------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=1486163.53..1486163.54 rows=1 width=4) (actual time=1493.888..1493.888 rows=1 loops=1)
   ->  Bitmap Heap Scan on foo  (cost=58718.12..1471876.19 rows=5714938 width=4) (actual time=12.565..1035.153 rows=5889135 loops=1)
         Recheck Cond: ((seq >= 424242) AND (seq <= 6313376))
         Rows Removed by Index Recheck: 41105
         Heap Blocks: lossy=26240
         ->  Bitmap Index Scan on foo_seq_idx  (cost=0.00..57289.38 rows=5714938 width=0) (actual time=10.378..10.378 rows=262400 loops=1)
               Index Cond: ((seq >= 424242) AND (seq <= 6313376))
 Planning time: 0.125 ms
 Execution time: 1493.948 ms
(9 rows)

1.4 秒聚合/求和给定范围内的 5,889,135 行。

尽管表有 10 GB，但 BRIN 索引为 304 kB。

甚至更快

如果这仍然不够快，您可以缓存 100k 行的聚合。

CREATE MATERIALIZED VIEW cache_foo
AS
  SELECT seq/1e5::int AS grp, sum(v)
  FROM foo GROUP BY seq/1e5::int
  ORDER BY 1;

现在您只需要使用 brin 和聚合2(1e5-1)行，而不是 3 亿行或其他行。

硬件

联想 x230、i5-3230M、16GB RAM、1tb 三星 840 SSD。