База данных для эффективных запросов агрегированных диапазонов?

В качестве упрощенного примера предположим, что у меня есть таблица вроде этого:

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)) за запрос?

Я столкнулся с структурой данных, называемой деревом сегментов, как описано . Также иногда называют деревом диапазона или деревом интервалов, хотя все эти имена часто описываются как несколько отличающиеся изменения структуры данных.

Однако я не сталкивался с какой-либо базой данных, которая реализует такую ​​структуру данных. Реализация этого с нуля легко для структуры в памяти, но становится сложной, если она должна быть сохранена или слишком велика, чтобы вписаться в память. Если существует эффективная модель для реализации этого поверх существующей базы данных, это также может помочь.

Боковое примечание. Это не таблица только для добавления, поэтому решение, такое как сохранение суммарной суммы, не будет работать в этом случае.

11 голосов | спросил Ralf 20 Mayam17 2017, 00:30:08

2 ответа


7

Использование SQL Server ColumnStore индексы

Хорошо, хорошо, только один - кластерный индекс CS.

Если вы хотите прочитать об оборудовании, на котором я это сделал, запустите здесь . Полное раскрытие, я написал это сообщение в блоге на веб-сайте компании, в которой я работаю.

На тест!

Вот общий код для создания довольно большой таблицы. Такое же предупреждение, как Эван, это может занять некоторое время, чтобы строить и индексировать.

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

Ну, Эван побеждает для простоты, но я говорил о , который ранее.

Вот определение индекса. La и dee и dah.

CREATE CLUSTERED COLUMNSTORE INDEX CX_WOAHMAMA ON dbo.t1

Рассматривая счет, каждый идентификатор имеет довольно ровное распределение:

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

С каждым идентификатором, имеющим ~ 5,005,005 строк, мы можем посмотреть довольно маленький диапазон идентификаторов, чтобы получить сумму в 10 миллионов строк.

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.

Надеюсь, это поможет!

ответил sp_BlitzErik 20 Mayam17 2017, 02:27:06
2

PostgreSQL с индексом BRIN

  

Даже если seq индексируется, типичная реализация базы данных будет циклически проходить каждую строку, чтобы вычислить сумму в лучшем случае O (n), где n - размер диапазона.

Это неправда. По крайней мере, ни одна достойная база данных не сделает этого. PostgreSQL поддерживает создание индексов BRIN для этих таблиц. индексы BRIN являются очень маленькими и могут поместиться в ram даже на столах это большое. Сотни миллионов строк - ничто.

Здесь 300 миллионов строк определены так же, как вы их заказывали. Предупреждение, что это может занять много времени (время: 336057.807 мс + 95121.809 мс для индекса).

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 ГБ, индекс BRIN составляет 304 кБ.

Еще быстрее

Если это еще не достаточно быстро, вы можете кэшировать агрегаты на 100 тыс. строк.

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 и aggregate 2(1e5-1), а не 300 миллионов или что-то еще.

Оборудование

Lenovo x230, i5-3230M, 16 ГБ оперативной памяти, 1 тб Samsung 840 SSD.

ответил Evan Carroll 20 Mayam17 2017, 00:52:27

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132