Допустим, мы регистрируем события в базе данных 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
?
. . (1) Сколько накладных расходов индекс имеет по отношению к данным, зависит от размера строки. (2) Базы данных просто не занимают много места. Как правило, пользовательский код быстрее и меньше. Конечно, чтобы получить функциональность и надежность базы данных, вашей команде, возможно, придется потратить десятилетия или столетия на написание кода. Базы данных — это инструменты.
Вы можете изучить расширение RTree.
@GordonLinoff См. мой текущий ответ (который может быть улучшен еще больше?): у нас есть улучшение размера базы данных на -44% (при той же скорости запросов во временном диапазоне!), Избегая использования дополнительного индекса, поэтому стоит изучить.
@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)
значений и т. д. какие пары вы бы использовали здесь?
Метод (2), подробно описанный в вопросе, работает хорошо. В бенчмарке я получил:
Ключевым моментом здесь является использование 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)
В более общем плане проблема связана с наличием идентификаторов, которые «грубо отсортированы» по дате и времени. Подробнее об этом:
Все эти методы используют идентификатор, который:
[---- timestamp ----][---- random and/or incremental ----]
Это действительно "наивные" методы. Просто откройте file::memory:
...
Обычно я использую базу данных :memory:
для своих тестов, но здесь я моделирую реальную ситуацию (база данных на диске) @MartinZeitler.
Тогда вам, вероятно, не следует жаловаться на узкое место. Если не использовать восходящий индекс, производительность может не сильно улучшиться. Вместо того, чтобы сортировать все это в одну таблицу, может помочь создание оптимизированной таблицы для каждой серии. Это еще можно загрузить в память... а мне такие комбинированные индексы кажутся довольно дрянными. Простота всегда равняется производительности... и если набор записей недостаточно прост, его следует упростить.
Вы добавляете случайные данные в свою базу данных, поэтому ваш результирующий набор отличается каждый раз, когда вы запускаете этот скрипт. При таком подходе вы не можете получить надежное время, это сравнение яблок с апельсинами. Кроме того, использование транзакции значительно сократило бы продолжительность операторов INSERT. Кроме того, я полностью согласен с утверждением @MartinZeitler «простота равна производительности» - не используйте составные данные в одном столбце. Это плохая практика моделирования данных.
Кстати, я перенес ваш пример на Rust, который показывает производительность около ~ 700 мкс для запроса. Поэтому я думаю, что вы в основном тестируете Python, повторяя набор результатов, а не время запроса SQLite. gist.github.com/schlamar/d500bec281c22fe6d3a8aee702e0b28d
Я только что проверил «наивный» подход без индекса с моей реализацией Rust и фиксированным набором результатов, и производительность намного хуже, чем показывают ваши результаты. Время запроса составляет ~ 50 мс по сравнению с ~ 800 мкс в методе (2), поэтому более чем в 60 раз медленнее!
Кроме того, вы не должны игнорировать время вставки. Подход БЕЗ ROWID примерно в 4 раза медленнее при вставке данных, чем наивный с индексом.
@schlamar Можете ли вы опубликовать новый ответ со всеми вашими комментариями +, возможно, код, который вы тестировали? Было бы полезно и интересно! (легче читать в новом ответе, чем эти комментарии).
Я не думаю, что мои комментарии можно считать ответом. Я загрузил свой тестовый код на Github, если это поможет: github.com/schlamar/rusqlite-performance-tests
@schlamar Я думаю, что ваши комментарии + ссылка на ваш Github можно считать ответом. По крайней мере, краткое изложение ваших выводов будет полезно будущим читателям. Даже для нас, когда мы будем читать эту тему через несколько месяцев/лет, резюме будет полезно.
Я не эксперт в 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 таблица + индекс по метке времени».
Вы слишком много думаете о микрооптимизациях. Вероятно, есть и другие места, где вы могли бы потратить свои усилия, которые окупились бы лучше. Каноническим решением является использование индекса или, возможно, использование столбца в качестве первичного ключа (но вам может понадобиться значение в миллисекундах или микросекундах).