作為一個簡化的例子，假設我有一個這樣的表：

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))每個查詢一樣？

我遇到了一種稱為 Segment Tree 的資料結構，如此處所述。有時也稱為範圍樹或區間樹，儘管所有這些名稱通常被描述為資料結構的略有不同的變體。

但是，我還沒有遇到任何實現這種資料結構的數據庫。對於記憶體中的結構來說，從頭開始實現它很容易，但如果它必須被持久化或太大而無法放入記憶體中，就會變得很棘手。如果有一種有效的模式可以在現有數據庫之上實現這一點，那也會有所幫助。

旁注：這不是一個僅追加的表，因此在這種情況下，諸如保持累積總和之類的解決方案將不起作用。

使用 SQL Server列儲存索引

好吧，只有一個——一個聚集的 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

好吧，Evan 是因為簡單而獲勝，但我之前已經談過了。

這是索引定義。拉和迪和達。

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.

希望這可以幫助！

帶有BRIN 索引的 PostgreSQL

即使 seq 被索引，典型的數據庫實現將遍歷每一行以計算最佳情況下的總和 O(n)，其中 n 是范圍的大小。

這不是真的。至少，沒有像樣的數據庫可以做到這一點。PostgreSQL 支持在這些類型的表上創建BRIN 索引。BRIN 索引非常小，即使在這麼大的表上也可以放入記憶體中。數億行不算什麼。

在這裡，定義了 3 億行，就像您訂購它們一樣。警告創建它可能需要很長時間（時間：336057.807 ms + 95121.809 ms 用於索引）。

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。

引用自：https://dba.stackexchange.com/questions/174086