Como ejemplo simplificado, supongamos que tengo una tabla como esta:

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

La tabla puede contener cientos de millones de registros, y necesito hacer consultas como esta con frecuencia:

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

Incluso si seqestá indexado, una implementación de base de datos típica recorrerá cada fila para calcular la suma en el mejor de los casos O(n), donde nestá el tamaño del rango.

¿Hay alguna base de datos que pueda hacer esto de manera eficiente, como en O(log(n))cada consulta?

Me he encontrado con una estructura de datos llamada Árbol de segmentos como se describe aquí . También a veces se lo denomina árbol de rango o árbol de intervalos, aunque todos estos nombres a menudo se describen como una variación ligeramente diferente de la estructura de datos.

Sin embargo, no he encontrado ninguna base de datos que implemente dicha estructura de datos. Implementarlo desde cero es fácil para una estructura en memoria, pero se vuelve complicado si tiene que persistir o es demasiado grande para caber en la memoria. Si hay un patrón eficiente para implementar esto sobre una base de datos existente, eso también podría ayudar.

Nota al margen: esta no es una tabla de solo agregar, por lo que una solución como mantener una suma acumulativa no funcionará en este caso.

Uso de índices ColumnStore de SQL Server

Bueno, está bien, solo uno: un índice CS agrupado.

Si quieres leer sobre el hardware en el que hice esto, dirígete aquí . Revelación completa, escribí esa publicación de blog en el sitio web de la empresa para la que trabajo.

¡A la prueba!

Aquí hay un código genérico para construir una tabla bastante grande. La misma advertencia que Evan, esto puede tomar un tiempo para construir e indexar.

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

Bueno, Evan gana por simplicidad, pero ya he hablado de eso antes.

Aquí está la definición del índice. La y dee y dah.

CREATE CLUSTERED COLUMNSTORE INDEX CX_WOAHMAMA ON dbo.t1

Mirando un conteo, cada Id tiene una distribución bastante uniforme:

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

Resultados:

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

...

994 5005005
995 5005005
996 5005005
997 5005005
998 5005005

Con cada Id que tiene ~ 5,005,005 filas, podemos ver un rango bastante pequeño de ID para obtener una suma de 10 millones de filas.

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

Resultado:

Records     Total
10010012    50015062308

Perfil de consulta:

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.

Por diversión, una agregación más grande:

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

Resultados:

Records     Total
500500505   2501989114575

Perfil de consulta:

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.

¡Espero que esto ayude!

PostgreSQL con un índice BRIN

Incluso si seq está indexado, una implementación de base de datos típica recorrerá cada fila para calcular la suma en el mejor de los casos O (n), donde n es el tamaño del rango.

Eso no es cierto. Al menos, ninguna base de datos decente lo hará. PostgreSQL admite la creación de índices BRIN en este tipo de tablas. Los índices BRIN son súper pequeños y pueden caber en ram incluso en tablas tan grandes. Cientos de millones de filas no son nada.

Aquí, 300 millones de filas definidas tal como las ordenó. Advertencia: puede llevar mucho tiempo crearlo (Tiempo: 336057.807 ms + 95121.809 ms para el índice).

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;

Y ahora...

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 segundos para agregar / sumar 5,889,135 filas en el rango dado.

A pesar de que la tabla tiene 10 GB, el índice BRIN es 304 kB.

Aun más rápido

Si todavía no es lo suficientemente rápido, puede almacenar en caché los agregados en 100k filas.

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

Ahora solo necesitará usar las 2(1e5-1)filas brin y agregadas en lugar de 300 millones o lo que sea.

Hardware

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