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

Dec 23 2020

Допустим, мы регистрируем события в базе данных 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?

Ответы

4 Basj Dec 24 2020 at 04:49

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

Метод (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 ----]
2 maytham-ɯɐɥʇʎɐɯ Dec 26 2020 at 16:59

Я не разбираюсь в 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

Получим такой результат: