Как использовать временные ряды с Sqlite с быстрыми запросами временного диапазона?

Допустим, мы регистрируем события в базе данных Sqlite со столбцом временных меток Unix ts:

CREATE TABLE data(ts INTEGER, text TEXT);   -- more columns in reality

и что нам нужен быстрый поиск диапазонов даты и времени, например:

SELECT text FROM data WHERE ts BETWEEN 1608710000 and 1608718654;

Таким образом, EXPLAIN QUERY PLAN дает SCAN TABLE data, что плохо, поэтому одно из очевидных решений — создать индекс с CREATE INDEX dt_idx ON data(ts).

Тогда проблема решена, но это довольно плохое решение — поддерживать индекс для уже возрастающей последовательности / уже отсортированного столбца ts, для которого мы могли бы использовать поиск B-дерева в O (log n) напрямую. Внутри это будет индекс:

ts           rowid
1608000001   1
1608000002   2
1608000012   3
1608000077   4

что является пустой тратой места в БД (и ЦП, когда запрос должен сначала искать в индексе).

Чтобы избежать этого:

  • (1) мы могли бы использовать ts как INTEGER PRIMARY KEY, поэтому ts было бы самим rowid. Но это не удается, потому что ts не уникален: 2 события могут произойти в одну и ту же секунду (или даже в одну и ту же миллисекунду).

    См., например, информацию, приведенную в Автоинкремент SQLite.

  • (2) мы могли бы использовать rowid как временную метку ts, соединенную с возрастающим числом. Пример:

     16087186540001      
     16087186540002
     [--------][--]
         ts     increasing number 
    

    Тогда rowid уникален и строго возрастает (при условии, что в секунду происходит менее 10 000 событий), и индекс не требуется. Запрос WHERE ts BETWEEN a AND b просто станет WHERE rowid BETWEEN a*10000 AND b*10000+9999.

    Но есть ли простой способ попросить Sqlite INSERT элемент с rowid большим или равным заданному значению? Допустим, текущая отметка времени 1608718654 и появляются два события:

      CREATE TABLE data(ts_and_incr INTEGER PRIMARY KEY AUTOINCREMENT, text TEXT);
      INSERT INTO data VALUES (NEXT_UNUSED(1608718654), "hello")  #16087186540001 
      INSERT INTO data VALUES (NEXT_UNUSED(1608718654), "hello")  #16087186540002
    

В общем, как оптимально создавать временные ряды с помощью Sqlite, чтобы иметь быстрые запросы WHERE timestamp BETWEEN a AND b?

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

Gordon Linoff 23.12.2020 14:09

. . (1) Сколько накладных расходов индекс имеет по отношению к данным, зависит от размера строки. (2) Базы данных просто не занимают много места. Как правило, пользовательский код быстрее и меньше. Конечно, чтобы получить функциональность и надежность базы данных, вашей команде, возможно, придется потратить десятилетия или столетия на написание кода. Базы данных — это инструменты.

Gordon Linoff 23.12.2020 16:03

Вы можете изучить расширение RTree.

Shawn 23.12.2020 18:15

@GordonLinoff См. мой текущий ответ (который может быть улучшен еще больше?): у нас есть улучшение размера базы данных на -44% (при той же скорости запросов во временном диапазоне!), Избегая использования дополнительного индекса, поэтому стоит изучить.

Basj 27.12.2020 21:28

@Shawn У вас есть пример с RTree? Я начал играть с ним, но у него есть несколько требований: CREATE VIRTUAL TABLE data USING rtree(id INTEGER PRIMARY KEY, dt INTEGER, label INTEGER); INSERT INTO data(dt, label) VALUES (1600000000, 2); не работает, вместо этого мы должны работать с парами (min, max) значений и т. д. какие пары вы бы использовали здесь?

Basj 27.12.2020 22:29
ReactJs | Supabase | Добавление данных в базу данных
ReactJs | Supabase | Добавление данных в базу данных
Это и есть ваш редактор таблиц в supabase.👇
Понимание Python и переход к SQL
Понимание Python и переход к SQL
Перед нами лабораторная работа по BloodOath:
23
5
11 031
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Первое решение

Метод (2), подробно описанный в вопросе, работает хорошо. В бенчмарке я получил:

  • наивный метод, без индекса: база данных 18 МБ, время запроса 86 мс
  • наивный метод с индексом: база данных 32 МБ, время запроса 12 мс
  • метод (2): база данных 18 МБ, время запроса 12 мс

Ключевым моментом здесь является использование dt в качестве INTEGER PRIMARY KEY, так что это будет сам идентификатор строки (см. Также Нужен ли индекс для первичного ключа в SQLite?), используя B-дерево, и не будет еще один скрытый столбец rowid. Таким образом, мы избегаем дополнительного индекса, который создавал бы соответствие dt => rowid: здесь dt — идентификатор строки.

Мы также используем AUTOINCREMENT, который внутренне создает sqlite_sequence таблицу, в которой отслеживается последний добавленный идентификатор. Это полезно при вставке: поскольку возможно, что два события имеют одинаковую отметку времени в секундах (это возможно даже с отметками времени в миллисекундах или микросекундах, ОС может обрезать точность), мы используем максимум между timestamp*10000 и last_added_ID + 1, чтобы убедиться, что это уникально:

 MAX(?, (SELECT seq FROM sqlite_sequence) + 1)

Код:

import sqlite3, random, time
db = sqlite3.connect('test.db')
db.execute("CREATE TABLE data(dt INTEGER PRIMARY KEY AUTOINCREMENT, label TEXT);")

t = 1600000000
for i in range(1000*1000):
    if random.randint(0, 100) == 0:  # timestamp increases of 1 second with probability 1%
        t += 1
    db.execute("INSERT INTO data(dt, label) VALUES (MAX(?, (SELECT seq FROM sqlite_sequence) + 1), 'hello');", (t*10000, ))
db.commit()

# t will range in a ~ 10 000 seconds window
t1, t2 = 1600005000*10000, 1600005100*10000  # time range of width 100 seconds (i.e. 1%)
start = time.time()
for _ in db.execute("SELECT 1 FROM data WHERE dt BETWEEN ? AND ?", (t1, t2)): 
    pass
print(time.time()-start)

Использование таблицы WITHOUT ROWID

Вот еще один метод с БЕЗ ROWID, который дает время запроса 8 мс. Мы должны сами реализовать автоинкрементный идентификатор, так как АВТОИНКРЕМЕНТ недоступен при использовании WITHOUT ROWID.
WITHOUT ROWID полезен, когда мы хотим использовать PRIMARY KEY(dt, another_column1, another_column2, id) и избежать дополнительного столбца rowid. Вместо одного B-дерева для rowid и одного B-дерева для (dt, another_column1, ...) у нас будет только одно.

db.executescript("""
    CREATE TABLE autoinc(num INTEGER); INSERT INTO autoinc(num) VALUES(0);

    CREATE TABLE data(dt INTEGER, id INTEGER, label TEXT, PRIMARY KEY(dt, id)) WITHOUT ROWID;
    
    CREATE TRIGGER insert_trigger BEFORE INSERT ON data BEGIN UPDATE autoinc SET num=num+1; END;
    """)

t = 1600000000
for i in range(1000*1000):
    if random.randint(0, 100) == 0: # timestamp increases of 1 second with probabibly 1%
        t += 1
    db.execute("INSERT INTO data(dt, id, label) VALUES (?, (SELECT num FROM autoinc), ?);", (t, 'hello'))
db.commit()

# t will range in a ~ 10 000 seconds window
t1, t2 = 1600005000, 1600005100  # time range of width 100 seconds (i.e. 1%)
start = time.time()
for _ in db.execute("SELECT 1 FROM data WHERE dt BETWEEN ? AND ?", (t1, t2)): 
    pass
print(time.time()-start)

Грубая сортировка UUID

В более общем плане проблема связана с наличием идентификаторов, которые «грубо отсортированы» по дате и времени. Подробнее об этом:

Все эти методы используют идентификатор, который:

[---- timestamp ----][---- random and/or incremental ----]

Это действительно "наивные" методы. Просто откройте file::memory:...

Martin Zeitler 02.01.2021 05:23

Обычно я использую базу данных :memory: для своих тестов, но здесь я моделирую реальную ситуацию (база данных на диске) @MartinZeitler.

Basj 02.01.2021 06:07

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

Martin Zeitler 02.01.2021 06:18

Вы добавляете случайные данные в свою базу данных, поэтому ваш результирующий набор отличается каждый раз, когда вы запускаете этот скрипт. При таком подходе вы не можете получить надежное время, это сравнение яблок с апельсинами. Кроме того, использование транзакции значительно сократило бы продолжительность операторов INSERT. Кроме того, я полностью согласен с утверждением @MartinZeitler «простота равна производительности» - не используйте составные данные в одном столбце. Это плохая практика моделирования данных.

schlamar 14.01.2023 12:17

Кстати, я перенес ваш пример на Rust, который показывает производительность около ~ 700 мкс для запроса. Поэтому я думаю, что вы в основном тестируете Python, повторяя набор результатов, а не время запроса SQLite. gist.github.com/schlamar/d500bec281c22fe6d3a8aee702e0b28d

schlamar 14.01.2023 12:47

Я только что проверил «наивный» подход без индекса с моей реализацией Rust и фиксированным набором результатов, и производительность намного хуже, чем показывают ваши результаты. Время запроса составляет ~ 50 мс по сравнению с ~ 800 мкс в методе (2), поэтому более чем в 60 раз медленнее!

schlamar 14.01.2023 14:09

Кроме того, вы не должны игнорировать время вставки. Подход БЕЗ ROWID примерно в 4 раза медленнее при вставке данных, чем наивный с индексом.

schlamar 14.01.2023 14:20

@schlamar Можете ли вы опубликовать новый ответ со всеми вашими комментариями +, возможно, код, который вы тестировали? Было бы полезно и интересно! (легче читать в новом ответе, чем эти комментарии).

Basj 15.01.2023 22:24

Я не думаю, что мои комментарии можно считать ответом. Я загрузил свой тестовый код на Github, если это поможет: github.com/schlamar/rusqlite-performance-tests

schlamar 22.01.2023 18:16

@schlamar Я думаю, что ваши комментарии + ссылка на ваш Github можно считать ответом. По крайней мере, краткое изложение ваших выводов будет полезно будущим читателям. Даже для нас, когда мы будем читать эту тему через несколько месяцев/лет, резюме будет полезно.

Basj 22.01.2023 21:20

Я не эксперт в SqlLite, но работал с базами данных и временными рядами. У меня была похожая ситуация ранее, и я поделюсь своим концептуальным решением.

У вас есть какая-то часть ответа на ваш вопрос, но не способ сделать это.

Как я это сделал, создав 2 таблицы, одна таблица (main_logs) будет регистрировать время в секундах, увеличивающееся как дата как целое число в качестве первичного ключа, а другие журналы таблицы содержат все журналы (main_sub_logs), которые были сделаны в это конкретное время, которое в вашем случае может быть до 10000 логов в секунду в нем. main_sub_logs имеет ссылку на main_logs и содержит каждую секунду журнала, а количество журналов X принадлежит этой секунде с собственным идентификатором счетчика, который начинается снова.

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

Таким образом, вы можете объединить эти две таблицы, и когда вы просматриваете первую таблицу между двумя конкретными временами, вы получаете все журналы между ними.

Итак, вот как я создал свои 2 таблицы:

CREATE TABLE IF NOT EXISTS main_logs (
  id INTEGER PRIMARY KEY
);

CREATE TABLE IF NOT EXISTS main_sub_logs (
   id INTEGER,
   ref INTEGER,
   log_counter INTEGER,
   log_text text,
   PRIMARY KEY (id), 
   FOREIGN KEY (ref) REFERENCES main_logs(id)
)

Я вставил некоторые фиктивные данные:

Теперь давайте запросим все журналы между 1608718655 и 1608718656.

SELECT * FROM main_logs AS A
JOIN main_sub_logs AS B ON A.id == B.Ref
WHERE A.id >= 1608718655 AND A.id <= 1608718656

Получит этот результат:

Спасибо за ваш ответ и обновление! Маленькие вопросы: 1) В реальных случаях, как вы ВСТАВЛЯЕТЕ строки, особенно о log_counter? Кажется, нам нужно вручную сохранить другую таблицу с последним значением log_counter, не так ли? Можете ли вы привести пример вашего INSERT? --2) Поскольку вы используете две таблицы (поэтому внутри есть две структуры B-деревьев), в чем преимущество этого метода по сравнению с одной таблицей + обычным индексом в столбце меток времени unix? Я запустил некоторые тесты и в настоящее время не вижу, как это улучшается по сравнению с решением «1 таблица + индекс по метке времени».

Basj 27.12.2020 21:03

Другие вопросы по теме