Nehmen wir als vereinfachtes Beispiel an, ich habe eine Tabelle wie diese:

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

Die Tabelle kann Hunderte Millionen Datensätze enthalten, und ich muss häufig folgende Abfragen durchführen:

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

Selbst wenn seqes indiziert ist, durchläuft eine typische Datenbankimplementierung jede Zeile, um die Summe im besten Fall zu berechnen O(n), wobei ndie Größe des Bereichs ist.

Gibt es eine Datenbank, die dies effizient durchführen kann, wie in der O(log(n))Abfrage angegeben?

Ich bin auf eine Datenstruktur gestoßen, die als Segmentbaum bezeichnet wird, wie hier beschrieben . Wird manchmal auch als Bereichsbaum oder Intervallbaum bezeichnet, obwohl alle diese Namen häufig als geringfügig unterschiedliche Variation der Datenstruktur beschrieben werden.

Ich bin jedoch auf keine Datenbank gestoßen, die eine solche Datenstruktur implementiert. Die Implementierung von Grund auf ist für eine In-Memory-Struktur einfach, wird jedoch schwierig, wenn sie beibehalten werden muss oder zu groß ist, um in den Speicher zu passen. Wenn es ein effizientes Muster gibt, um dies zusätzlich zu einer vorhandenen Datenbank zu implementieren, könnte dies ebenfalls hilfreich sein.

Randnotiz: Dies ist keine Nur-Anhängen-Tabelle, daher funktioniert eine Lösung wie das Beibehalten einer kumulativen Summe in diesem Fall nicht.

Verwenden von SQL Server ColumnStore- Indizes

Okay, nur einer - ein Cluster-CS-Index.

Wenn Sie mehr über die Hardware erfahren möchten, auf der ich dies getan habe, klicken Sie hier . Vollständige Offenlegung, ich schrieb diesen Blog-Beitrag auf der Website des Unternehmens, für das ich arbeite.

Auf zum Test!

Hier ist ein allgemeiner Code zum Erstellen einer ziemlich großen Tabelle. Dieselbe Warnung wie bei Evan, das Erstellen und Indizieren kann eine Weile dauern.

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

Nun, gewinnt Evan der Einfachheit halber, aber ich habe darüber gesprochen , dass vor.

Hier ist die Indexdefinition. La und dee und dah.

CREATE CLUSTERED COLUMNSTORE INDEX CX_WOAHMAMA ON dbo.t1

Bei einer Zählung hat jede ID eine ziemlich gleichmäßige Verteilung:

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

Ergebnisse:

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

...

994 5005005
995 5005005
996 5005005
997 5005005
998 5005005

Mit jeder ID mit ~ 5.005.005 Zeilen können wir uns einen ziemlich kleinen Bereich von IDs ansehen, um eine Summe von 10 Millionen Zeilen zu erhalten.

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

Ergebnis:

Records     Total
10010012    50015062308

Abfrageprofil:

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.

Zum Spaß eine größere Aggregation:

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

Ergebnisse:

Records     Total
500500505   2501989114575

Abfrageprofil:

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.

Hoffe das hilft!

PostgreSQL mit einem BRIN-Index

Selbst wenn seq indiziert ist, durchläuft eine typische Datenbankimplementierung jede Zeile, um die Summe im besten Fall O (n) zu berechnen, wobei n die Größe des Bereichs ist.

Das ist nicht wahr. Zumindest wird das keine anständige Datenbank tun. PostgreSQL unterstützt das Erstellen von BRIN-Indizes für diese Art von Tabellen. BRIN-Indizes sind sehr klein und passen sogar in so große Tabellen. Hunderte Millionen Zeilen sind nichts.

Hier werden 300 Millionen Zeilen so definiert, wie Sie sie bestellt haben. Die Erstellung kann lange dauern (Zeit: 336057.807 ms + 95121.809 ms für den Index).

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;

Und nun...

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 Sekunden, um 5.889.135 Zeilen im angegebenen Bereich zu aggregieren / zu summieren.

Obwohl die Tabelle 10 GB umfasst, beträgt der BRIN-Index 304 kB.

Noch schneller

Wenn dies immer noch nicht schnell genug ist, können Sie die Aggregate in 100.000 Zeilen zwischenspeichern.

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

Jetzt müssen Sie nur noch die 2(1e5-1)Zeilen " Brin" und "Aggregate" verwenden, anstatt 300 Millionen oder was auch immer.

Hardware

Lenovo x230, i5-3230M, 16 GB RAM, 1 TB Samsung 840 SSD.