À titre d'exemple simplifié, supposons que j'ai un tableau comme celui-ci:

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

La table peut contenir des centaines de millions d'enregistrements, et je dois fréquemment effectuer des requêtes comme celle-ci:

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

Même si elle seqest indexée, une implémentation de base de données typique parcourra chaque ligne pour calculer la somme dans le meilleur des cas O(n), où nest la taille de la plage.

Y a-t-il une base de données qui peut le faire efficacement, comme dans O(log(n))la requête?

J'ai rencontré une structure de données appelée un arbre de segment comme décrit ici . Parfois également appelé arbre de plage ou arbre d'intervalle, bien que tous ces noms soient souvent décrits comme une variation légèrement différente de la structure des données.

Cependant, je n'ai rencontré aucune base de données qui implémente une telle structure de données. L'implémentation à partir de zéro est facile pour une structure en mémoire, mais devient délicate si elle doit être persistante ou trop grande pour tenir dans la mémoire. S'il existe un modèle efficace pour l'implémenter au-dessus d'une base de données existante, cela pourrait également aider.

Note latérale: Ce n'est pas un tableau à ajouter uniquement, donc une solution telle que conserver une somme cumulée ne fonctionnera pas dans ce cas.

Utilisation des index SQL Server ColumnStore

Eh bien, d'accord, un seul - un index CS en cluster.

Si vous voulez en savoir plus sur le matériel sur lequel j'ai fait cela, rendez-vous ici . Divulgation complète, j'ai écrit ce billet de blog sur le site Web de la société pour laquelle je travaille.

À l'épreuve!

Voici du code générique pour construire une assez grande table. Même avertissement que Evan, cela peut prendre un certain temps pour construire et indexer.

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

Eh bien, Evan gagne pour la simplicité, mais j'ai parlé de ce auparavant.

Voici la définition de l'index. La et dee et dah.

CREATE CLUSTERED COLUMNSTORE INDEX CX_WOAHMAMA ON dbo.t1

En regardant un décompte, chaque ID a une distribution assez uniforme:

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

Résultats:

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

...

994 5005005
995 5005005
996 5005005
997 5005005
998 5005005

Chaque identifiant ayant environ 5 005 005 lignes, nous pouvons examiner une assez petite plage d'identifiants pour obtenir une somme de 10 millions de lignes.

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

Résultat:

Records     Total
10010012    50015062308

Profil de requête:

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.

Pour le plaisir, une agrégation plus importante:

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

Résultats:

Records     Total
500500505   2501989114575

Profil de requête:

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.

J'espère que cela t'aides!

PostgreSQL avec un index BRIN

Même si seq est indexé, une implémentation de base de données typique parcourra chaque ligne pour calculer la somme dans le meilleur des cas O (n), où n est la taille de la plage.

Ce n'est pas vrai. Au moins, aucune base de données décente ne fera cela. PostgreSQL prend en charge la création d' index BRIN sur ces types de tables. Les index BRIN sont super petits et peuvent tenir dans un bélier même sur des tables aussi grandes. Des centaines de millions de rangées ne sont rien.

Ici, 300 millions de lignes définies comme vous les avez commandées. Attention, sa création peut prendre un certain temps (durée: 336057.807 ms + 95121.809 ms pour l'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;

Et maintenant...

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 seconde pour agréger / additionner 5 889 135 lignes dans la plage donnée.

Bien que le tableau soit de 10 Go, l'indice BRIN est de 304 kB.

Même plus vite

Si ce n'est toujours pas assez rapide, vous pouvez mettre en cache les agrégats par 100k lignes.

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

Maintenant, vous n'aurez plus qu'à utiliser les 2(1e5-1)lignes de saumure et d'agrégation plutôt que 300 millions ou autre.

Matériel

Lenovo x230, i5-3230M, 16 Go de RAM, 1 To SSD Samsung 840.