Как использовать временные ряды с 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)
.
Тогда проблема решена, но поддерживать индекс для уже увеличивающейся последовательности / уже отсортированного столбца, для которого мы могли бы напрямую использовать поиск B-дерева в O (log n), - довольно плохое решение . Внутренне это будет индекс:ts
ts rowid
1608000001 1
1608000002 2
1608000012 3
1608000077 4
что является пустой тратой пространства БД (и ЦП, когда запрос должен сначала искать в индексе).
Чтобы этого избежать:
(1) мы могли бы использовать
ts
какINTEGER PRIMARY KEY
, такts
иrowid
саму себя. Но это не удается, потому чтоts
это не уникально: 2 события могут произойти в одну секунду (или даже в одну и ту же миллисекунду).См., Например, информацию, приведенную в SQLite Autoincrement .
(2) мы могли бы использовать
rowid
как временную метку,ts
объединенную с увеличивающимся числом. Пример:16087186540001 16087186540002 [--------][--] ts increasing number
Then
rowid
является уникальным и строго возрастает (при условии, что количество событий менее 10 тыс. В секунду), и индекс не требуется. Запрос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
?
Ответы
Первое решение
Метод (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
таблицы
Вот еще один метод, WITHOUT ROWIDкоторый дает время запроса 8 мс . Мы должны реализовать автоматически увеличивающийся идентификатор самостоятельно, поскольку функция AUTOINCREMENT недоступна при использовании 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
В более общем плане проблема связана с наличием идентификаторов, которые «грубо отсортированы» по дате и времени. Подробнее об этом:
- ULID (универсальный уникальный лексикографически сортируемый идентификатор)
- Снежинка
- MongoDB ObjectId
Все эти методы используют идентификатор:
[---- timestamp ----][---- random and/or incremental ----]
Я не разбираюсь в 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
Получим такой результат:
