Jako uproszczony przykład, załóżmy, że mam taką tabelę:

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

Tabela może zawierać setki milionów rekordów i muszę często zadawać takie zapytania:

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

Nawet jeśli seqjest indeksowane, typowa implementacja bazy danych zapętla każdy wiersz, aby w najlepszym przypadku obliczyć sumę O(n), gdzie njest wielkość zakresu.

Czy istnieje baza danych, która może to zrobić skutecznie, tak jak w O(log(n))zapytaniu?

Natknąłem się na strukturę danych o nazwie Drzewo segmentów, jak opisano tutaj . Czasami nazywany także drzewem zakresu lub drzewem interwałów, chociaż wszystkie te nazwy są często opisywane jako nieco inna odmiana struktury danych.

Jednak nie spotkałem żadnej bazy danych, która implementowałaby taką strukturę danych. Wdrożenie go od zera jest łatwe dla struktury w pamięci, ale staje się trudne, jeśli trzeba ją utrwalić lub jest zbyt duża, aby zmieściła się w pamięci. Jeśli istnieje skuteczny wzorzec implementacji tego na istniejącej bazie danych, może to również pomóc.

Uwaga dodatkowa: nie jest to tabela tylko do dołączania, więc rozwiązanie takie jak utrzymanie sumy łącznej nie będzie działać w tym przypadku.

Korzystanie z indeksów SQL Server ColumnStore

No dobra, tylko jeden - klastrowany indeks CS.

Jeśli chcesz przeczytać o sprzęcie, na którym to zrobiłem, zajrzyj tutaj . Pełne ujawnienie, napisałem ten post na blogu na stronie internetowej firmy, dla której pracuję.

Do testu!

Oto ogólny kod do zbudowania całkiem dużego stołu. Takie samo ostrzeżenie jak Evan, kompilacja i indeksowanie może trochę potrwać.

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

Cóż, Evan wygrywa dla uproszczenia, ale mówiłem o tym wcześniej.

Oto definicja indeksu. La i dee i dah.

CREATE CLUSTERED COLUMNSTORE INDEX CX_WOAHMAMA ON dbo.t1

Patrząc na liczbę, każdy identyfikator ma dość równomierny rozkład:

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

Wyniki:

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

...

994 5005005
995 5005005
996 5005005
997 5005005
998 5005005

Z każdym Id o ~ 5,005,005 wierszy, możemy spojrzeć na dość mały zakres identyfikatorów, aby uzyskać sumę 10 milionów wierszy.

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

Wynik:

Records     Total
10010012    50015062308

Profil zapytania:

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.

Dla zabawy większa agregacja:

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

Wyniki:

Records     Total
500500505   2501989114575

Profil zapytania:

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.

Mam nadzieję że to pomoże!

PostgreSQL z indeksem BRIN

Nawet jeśli sekwencja jest indeksowana, typowa implementacja bazy danych zapętla się przez każdy wiersz, aby obliczyć sumę w najlepszym przypadku O (n), gdzie n jest rozmiarem zakresu.

To nieprawda. Przynajmniej żadna przyzwoita baza danych tego nie zrobi. PostgreSQL obsługuje tworzenie indeksów BRIN na tego rodzaju tabelach. Indeksy BRIN są bardzo małe i mogą zmieścić się w pamięci ram nawet na tak dużych stołach. Setki milionów rzędów to nic.

Tutaj zdefiniowano 300 milionów wierszy dokładnie tak, jak je zamówiłeś. Ostrzeżenie: utworzenie go może zająć dużo czasu (czas: 336057.807 ms + 95121,809 ms dla indeksu).

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;

I teraz...

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 sekundy na agregację / zsumowanie 5 889 135 wierszy w danym zakresie.

Mimo że tabela wynosi 10 GB, indeks BRIN wynosi 304 kB.

Nawet szybciej

Jeśli nadal nie jest to wystarczająco szybkie, możesz buforować agregaty o 100 000 wierszy.

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

Teraz będziesz potrzebować tylko 2(1e5-1)wiersza solanki i agregacji zamiast 300 milionów lub cokolwiek innego.

Sprzęt komputerowy

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