Jak używać szeregów czasowych w Sqlite, z szybkimi zapytaniami o przedziały czasowe?
Powiedzmy, że rejestrujemy zdarzenia w bazie danych Sqlite za pomocą uniksowej kolumny timestamp ts
:
CREATE TABLE data(ts INTEGER, text TEXT); -- more columns in reality
i że chcemy szybkiego wyszukiwania zakresów dat i godzin, na przykład:
SELECT text FROM data WHERE ts BETWEEN 1608710000 and 1608718654;
W ten sposób EXPLAIN QUERY PLAN
daje, SCAN TABLE data
co jest złe, więc jednym oczywistym rozwiązaniem jest utworzenie indeksu z rozszerzeniemCREATE INDEX dt_idx ON data(ts)
.
Wtedy problem jest rozwiązany, ale raczej kiepskim rozwiązaniem jest utrzymywanie indeksu dla już rosnącej sekwencji / już posortowanej kolumny, ts
dla której moglibyśmy bezpośrednio użyć wyszukiwania B-drzewa w O (log n) . Wewnętrznie będzie to indeks:
ts rowid
1608000001 1
1608000002 2
1608000012 3
1608000077 4
co jest stratą miejsca w bazie danych (i procesora, gdy zapytanie musi najpierw zajrzeć do indeksu).
Uniknąć tego:
(1) moglibyśmy użyć
ts
jakoINTEGER PRIMARY KEY
, tak samots
byłobyrowid
. Ale to się nie udaje, ponieważts
nie jest unikalne: 2 zdarzenia mogą wystąpić w tej samej sekundzie (lub nawet w tej samej milisekundie).Zobacz na przykład informacje podane w SQLite Autoincrement .
(2) możemy użyć
rowid
jako znacznika czasuts
połączonego z rosnącą liczbą. Przykład:16087186540001 16087186540002 [--------][--] ts increasing number
Wtedy
rowid
jest unikalny i ściśle rosnący (pod warunkiem, że jest mniej niż 10 000 zdarzeń na sekundę) i żaden indeks nie byłby wymagany. ZapytanieWHERE ts BETWEEN a AND b
stałoby się po prostuWHERE rowid BETWEEN a*10000 AND b*10000+9999
.Ale czy istnieje łatwy sposób, aby poprosić Sqlite
INSERT
o element o wartościrowid
większej lub równej danej wartości? Załóżmy, że aktualna sygnatura czasowa to1608718654
i pojawiają się dwa zdarzenia: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
Mówiąc bardziej ogólnie, jak optymalnie tworzyć szeregi czasowe za pomocą Sqlite, aby mieć szybkie zapytania WHERE timestamp BETWEEN a AND b
?
Odpowiedzi
Pierwsze rozwiązanie
Metoda (2) opisana w pytaniu wydaje się działać dobrze. W benchmarku uzyskałem:
- metoda naiwna, bez indeksu: baza danych 18 MB, czas zapytania 86 ms
- metoda naiwna, z indeksem: baza danych 32 MB, czas zapytania 12 ms
- metoda (2): Baza danych 18 MB, czas zapytania 12 ms
Kluczowym punktem jest tu użyć dt
jako INTEGER PRIMARY KEY
, więc będzie to samo id rząd (patrz też jest indeksem potrzebne do klucza podstawowego w SQLite? ), Za pomocą B-tree, i tam nie być kolejnym ukryte rowid
kolumny. W ten sposób unikamy dodatkowego indeksu, który byłby odpowiedni dt => rowid
: tutaj dt
jest id wiersza.
Używamy również, AUTOINCREMENT
które wewnętrznie tworzy sqlite_sequence
tabelę, która śledzi ostatnio dodany identyfikator. Jest to przydatne przy wstawianiu: ponieważ możliwe jest, że dwa zdarzenia mają ten sam znacznik czasu w sekundach (byłoby to możliwe nawet przy milisekundach lub mikrosekundach, system operacyjny mógłby skrócić precyzję), używamy maksimum między timestamp*10000
i, last_added_ID + 1
aby upewnić się, że jest unikalny :
MAX(?, (SELECT seq FROM sqlite_sequence) + 1)
Kod:
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)
Korzystanie ze WITHOUT ROWID
stołu
Oto inna metoda, WITHOUT ROWIDktóra daje 8 ms czas zapytania. Musimy samodzielnie zaimplementować identyfikator automatycznie zwiększający się, ponieważ funkcja AUTOINCREMENT nie jest dostępna podczas używania WITHOUT ROWID
.
WITHOUT ROWID
jest przydatne, gdy chcemy użyć a PRIMARY KEY(dt, another_column1, another_column2, id)
i uniknąć dodatkowej rowid
kolumny. Zamiast jednego drzewa B dla rowid
i jednego drzewa B dla (dt, another_column1, ...)
, będziemy mieć tylko jedno.
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)
Zgrubnie posortowany UUID
Mówiąc bardziej ogólnie, problem jest związany z posiadaniem identyfikatorów, które są „z grubsza posortowane” według daty i godziny. Więcej na ten temat:
- ULID (uniwersalnie unikalny identyfikator sortowalny leksykograficznie)
- Płatek śniegu
- MongoDB ObjectId
Wszystkie te metody używają identyfikatora, który jest:
[---- timestamp ----][---- random and/or incremental ----]
Nie jestem ekspertem w SqlLite, ale pracowałem z bazami danych i szeregami czasowymi. Miałem wcześniej podobną sytuację i podzieliłbym się moim koncepcyjnym rozwiązaniem.
Masz pewną część odpowiedzi na swoje pytanie, ale nie sposób, w jaki to zrobisz.
Sposób, w jaki to zrobiłem, tworząc 2 tabele, jedną tabelę (main_logs) będzie rejestrować czas w sekundach jako datę jako liczbę całkowitą jako klucz podstawowy, a inne dzienniki tabel zawierają wszystkie dzienniki (main_sub_logs), które utworzyły się w tym konkretnym czasie, który w twoim przypadku może być w nim do 10000 logów na sekundę. Main_sub_logs ma odniesienie do main_logs i zawiera dla każdej sekundy dziennika oraz X dzienników należących do tej sekundy z własnym identyfikatorem licznika, który zaczyna się od nowa.
W ten sposób ograniczasz wyszukiwanie serii czasowych do kilku sekund okien zdarzeń zamiast wszystkich dzienników w jednym miejscu.
W ten sposób możesz dołączyć do tych dwóch stołów, a kiedy spojrzysz w górę z pierwszej tabeli między dwoma określonymi czasami, otrzymasz wszystkie logi pomiędzy.
Oto jak utworzyłem moje 2 tabele:
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)
)
Wstawiłem fikcyjne dane:

Teraz pozwala wysyłać zapytania do wszystkich dzienników od 1608718655 do 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
Otrzyma ten wynik:
