Jak używać szeregów czasowych w Sqlite, z szybkimi zapytaniami o przedziały czasowe?

Dec 23 2020

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 PLANdaje, SCAN TABLE dataco 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, tsdla 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ć tsjako INTEGER PRIMARY KEY, tak samo tsbyłoby rowid. Ale to się nie udaje, ponieważ tsnie 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ć rowidjako znacznika czasu tspołączonego z rosnącą liczbą. Przykład:

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

    Wtedy rowidjest unikalny i ściśle rosnący (pod warunkiem, że jest mniej niż 10 000 zdarzeń na sekundę) i żaden indeks nie byłby wymagany. Zapytanie WHERE ts BETWEEN a AND bstałoby się po prostu WHERE rowid BETWEEN a*10000 AND b*10000+9999.

    Ale czy istnieje łatwy sposób, aby poprosić Sqlite INSERTo element o wartości rowidwiększej lub równej danej wartości? Załóżmy, że aktualna sygnatura czasowa to 1608718654i 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

4 Basj Dec 24 2020 at 04:49

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ć dtjako 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 rowidkolumny. W ten sposób unikamy dodatkowego indeksu, który byłby odpowiedni dt => rowid: tutaj dt jest id wiersza.

Używamy również, AUTOINCREMENTktóre wewnętrznie tworzy sqlite_sequencetabelę, 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*10000i, last_added_ID + 1aby 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 ROWIDstoł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 ROWIDjest przydatne, gdy chcemy użyć a PRIMARY KEY(dt, another_column1, another_column2, id)i uniknąć dodatkowej rowidkolumny. Zamiast jednego drzewa B dla rowidi 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 ----]
2 maytham-ɯɐɥʇʎɐɯ Dec 26 2020 at 16:59

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: