Wie verwende ich Zeitreihen mit Sqlite mit schnellen Zeitbereichsabfragen?

Question

Angenommen, wir protokollieren Ereignisse in einer SQLite-Datenbank mit einer Unix-Zeitstempelspalte ts:

CREATE TABLE data(ts INTEGER, text TEXT);   -- more columns in reality

und dass wir schnell nach Datums- / Uhrzeitbereichen suchen möchten, zum Beispiel:

SELECT text FROM data WHERE ts BETWEEN 1608710000 and 1608718654;

So EXPLAIN QUERY PLANgibt es SCAN TABLE datawas schlecht ist, also besteht eine naheliegende Lösung darin , einen Index mit zu erstellenCREATE INDEX dt_idx ON data(ts) .

Dann ist das Problem gelöst, aber es ist eher eine schlechte Lösung , einen Index für eine bereits zunehmende Sequenz / bereits sortierte Spalte pflegen zu müssen, tsfür die wir eine B-Baum-Suche in O (log n) direkt verwenden könnten . Intern ist dies der Index:

ts           rowid
1608000001   1
1608000002   2
1608000012   3
1608000077   4

Dies ist eine Verschwendung von DB-Speicherplatz (und CPU, wenn eine Abfrage zuerst im Index suchen muss).

Um es zu umgehen:

• (1) Wir könnten tsals verwenden INTEGER PRIMARY KEY, so tswäre das rowidselbst. Dies schlägt jedoch fehl, da tses nicht eindeutig ist: 2 Ereignisse können in derselben Sekunde (oder sogar in derselben Millisekunde) auftreten.

  Siehe zum Beispiel die Informationen in SQLite Autoincrement .

• (2) Wir könnten rowidals Zeitstempel verwenden, der tsmit einer zunehmenden Anzahl verkettet ist. Beispiel:

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

  Dann rowidist es einzigartig und nimmt streng zu (vorausgesetzt, es gibt weniger als 10.000 Ereignisse pro Sekunde), und es wäre kein Index erforderlich. Eine Abfrage WHERE ts BETWEEN a AND bwürde einfach werden WHERE rowid BETWEEN a*10000 AND b*10000+9999.

  Aber gibt es eine einfache Möglichkeit, Sqlite zu INSERTeinem Artikel zu fragen, dessen rowidWert größer oder gleich einem bestimmten Wert ist? Angenommen, der aktuelle Zeitstempel ist 1608718654und zwei Ereignisse werden angezeigt:

    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
  

Allgemeiner gesagt, wie kann man mit Sqlite Zeitreihen optimal erstellen, um schnelle Abfragen zu haben WHERE timestamp BETWEEN a AND b?

Answer 1

Erste Lösung

Die in der Frage beschriebene Methode (2) scheint gut zu funktionieren. In einem Benchmark erhielt ich:

• naive Methode ohne Index: 18 MB Datenbank, 86 ms Abfragezeit
• naive Methode mit Index: 32 MB Datenbank, 12 ms Abfragezeit
• Methode (2): 18 MB Datenbank, 12 ms Abfragezeit

Der entscheidende Punkt ist hier die Verwendung dtals ein INTEGER PRIMARY KEY, so wird es der Zeilen - ID selbst sein (siehe auch ein Index für einen Primärschlüssel in SQLite benötigt? ), Einen B-Baum verwendet wird , und es wird nicht ein anderer versteckt sein rowidSpalt. Daher vermeiden wir einen zusätzlichen Index, der eine Entsprechung ergeben würde dt => rowid: Hier dt ist die Zeilen-ID.

Wir verwenden auch, AUTOINCREMENTdie intern eine sqlite_sequenceTabelle erstellt, die die zuletzt hinzugefügte ID verfolgt. Dies ist beim Einfügen nützlich: Da es möglich ist, dass zwei Ereignisse in Sekunden den gleichen Zeitstempel haben (es wäre sogar mit Millisekunden- oder Mikrosekunden-Zeitstempeln möglich, dass das Betriebssystem die Genauigkeit abschneidet), verwenden wir das Maximum zwischen timestamp*10000und last_added_ID + 1, um sicherzustellen, dass es eindeutig ist ::

 MAX(?, (SELECT seq FROM sqlite_sequence) + 1)

Code:

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)

---

Verwenden einer WITHOUT ROWIDTabelle

Hier ist eine andere Methode, mit WITHOUT ROWIDder eine Abfragezeit von 8 ms angegeben wird. Wir müssen selbst eine automatisch inkrementierende ID implementieren, da AUTOINCREMENT bei Verwendung nicht verfügbar ist WITHOUT ROWID.
WITHOUT ROWIDist nützlich, wenn wir eine verwenden PRIMARY KEY(dt, another_column1, another_column2, id)und vermeiden möchten, eine zusätzliche rowidSpalte zu haben . Anstatt einen B-Baum für rowidund einen B-Baum für zu haben (dt, another_column1, ...), haben wir nur einen.

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)

---

Grob sortierte UUID

Im Allgemeinen hängt das Problem damit zusammen, dass IDs nach Datum / Uhrzeit "grob sortiert" sind. Mehr dazu:

• ULID (Universally Unique Lexicographically Sortable Identifier)
• Schneeflocke
• MongoDB ObjectId

Alle diese Methoden verwenden eine ID:

[---- timestamp ----][---- random and/or incremental ----]

Answer 2

Ich bin kein Experte für SqlLite, habe aber mit Datenbanken und Zeitreihen gearbeitet. Ich hatte zuvor eine ähnliche Situation und würde meine konzeptionelle Lösung teilen.

Sie haben einen Teil der Antwort in Ihrer Frage, aber nicht die Art und Weise, wie Sie dies tun.

So wie ich es gemacht habe, 2 Tabellen zu erstellen, protokolliert eine Tabelle (main_logs) die Zeit in Sekundeninkrement als Datum als Ganzzahl als Primärschlüssel und die anderen Tabellenprotokolle enthalten alle Protokolle (main_sub_logs), die in dieser bestimmten Zeit erstellt wurden, die in Ihrem Fall möglich ist Es können bis zu 10000 Protokolle pro Sekunde vorhanden sein. Die main_sub_logs verweisen auf main_logs und enthalten für jede Protokollsekunde und X Anzahl der Protokolle, die zu dieser Sekunde gehören, mit einer eigenen Zähler-ID, die von vorne beginnt.

Auf diese Weise beschränken Sie Ihre Zeitreihen-Suche auf Sekunden von Ereignisfenstern anstelle aller Protokolle an einem Ort.

Auf diese Weise können Sie diese beiden Tabellen verbinden. Wenn Sie zwischen zwei bestimmten Zeiten von der ersten Tabelle nachschlagen, werden alle Protokolle dazwischen angezeigt.

Also hier ist, wie ich meine 2 Tabellen erstellt habe:

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)
)

Ich habe einige Dummy-Daten eingefügt:

Jetzt können Sie alle Protokolle zwischen 1608718655 und 1608718656 abfragen

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

Wird dieses Ergebnis erhalten: