Comment utiliser des séries temporelles avec Sqlite, avec des requêtes rapides sur la plage de temps?
Disons que nous enregistrons les événements dans une base de données Sqlite avec la colonne d'horodatage Unix ts
:
CREATE TABLE data(ts INTEGER, text TEXT); -- more columns in reality
et que nous voulons une recherche rapide des plages de date / heure, par exemple:
SELECT text FROM data WHERE ts BETWEEN 1608710000 and 1608718654;
Comme ça, EXPLAIN QUERY PLAN
donne SCAN TABLE data
ce qui est mauvais, donc une solution évidente est de créer un index avec CREATE INDEX dt_idx ON data(ts)
.
Ensuite, le problème est résolu, mais c'est plutôt une mauvaise solution d'avoir à maintenir un index pour une séquence déjà croissante / une colonne déjà triée ts
pour laquelle nous pourrions utiliser directement une recherche d'arbre B dans O (log n) . En interne, ce sera l'indice:
ts rowid
1608000001 1
1608000002 2
1608000012 3
1608000077 4
ce qui est un gaspillage d'espace de base de données (et de CPU lorsqu'une requête doit d'abord chercher dans l'index).
Pour éviter cela:
(1) nous pourrions utiliser
ts
commeINTEGER PRIMARY KEY
, il ents
serait derowid
même pour le lui - même. Mais cela échoue car cets
n'est pas unique: 2 événements peuvent se produire à la même seconde (voire à la même milliseconde).Voir par exemple les informations fournies dans l' auto-incrémentation SQLite .
(2) nous pourrions utiliser
rowid
comme horodatagets
concaténé avec un nombre croissant. Exemple:16087186540001 16087186540002 [--------][--] ts increasing number
Ensuite
rowid
est unique et strictement croissant (à condition qu'il y ait moins de 10k événements par seconde), et aucun index ne serait requis. Une requêteWHERE ts BETWEEN a AND b
deviendrait simplementWHERE rowid BETWEEN a*10000 AND b*10000+9999
.Mais existe-t-il un moyen simple de demander à Sqlite
INSERT
un élément avec une valeurrowid
supérieure ou égale à une valeur donnée? Disons que l'horodatage actuel est1608718654
et que deux événements apparaissent: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
Plus généralement, comment créer des séries chronologiques de manière optimale avec Sqlite, pour avoir des requêtes rapides WHERE timestamp BETWEEN a AND b
?
Réponses
Première solution
La méthode (2) détaillée dans la question semble bien fonctionner. Dans un benchmark, j'ai obtenu:
- méthode naïve, sans index: base de données de 18 Mo, temps de requête de 86 ms
- méthode naïve, avec index: base de données de 32 Mo, temps de requête de 12 ms
- méthode (2): base de données 18 Mo, temps de requête 12 ms
Le point clé est ici à utiliser dt
comme un INTEGER PRIMARY KEY
, donc ce sera l'ID de ligne lui-même (voir aussi Un index est-il nécessaire pour une clé primaire dans SQLite? ), En utilisant un arbre B, et il n'y aura pas d' autre rowid
colonne cachée . Nous évitons ainsi un indice supplémentaire qui ferait une correspondance dt => rowid
: ici dt
est l'identifiant de ligne.
Nous utilisons également AUTOINCREMENT
qui crée en interne une sqlite_sequence
table, qui garde la trace du dernier ID ajouté. Ceci est utile lors de l'insertion: puisqu'il est possible que deux événements aient le même horodatage en secondes (ce serait possible même avec des horodatages en millisecondes ou en microsecondes, le système d'exploitation pourrait tronquer la précision), nous utilisons le maximum entre timestamp*10000
et last_added_ID + 1
pour nous assurer qu'il est unique :
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)
Utiliser une WITHOUT ROWID
table
Voici une autre méthode WITHOUT ROWIDqui donne un temps de requête de 8 ms . Nous devons implémenter nous-mêmes un identifiant auto-incrémenté, car AUTOINCREMENT n'est pas disponible lors de l'utilisation WITHOUT ROWID
.
WITHOUT ROWID
est utile lorsque l'on veut utiliser a PRIMARY KEY(dt, another_column1, another_column2, id)
et éviter d'avoir une rowid
colonne supplémentaire . Au lieu d'avoir un arbre B pour rowid
et un arbre B pour (dt, another_column1, ...)
, nous n'en aurons qu'un seul.
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 grossièrement trié
Plus généralement, le problème est lié au fait d'avoir des identifiants «grossièrement triés» par date / heure. En savoir plus:
- ULID (identifiant lexicographiquement triable universellement unique)
- Flocon de neige
- ObjectId MongoDB
Toutes ces méthodes utilisent un identifiant qui est:
[---- timestamp ----][---- random and/or incremental ----]
Je ne suis pas expert en SqlLite, mais j'ai travaillé avec des bases de données et des séries chronologiques. J'ai déjà eu une situation similaire et je partagerais ma solution conceptuelle.
Vous avez une partie de la réponse dans votre question, mais pas la façon de le faire.
La façon dont je l'ai fait, en créant 2 tables, une table (main_logs) enregistrera le temps en secondes incrémentation en tant que date en tant que clé primaire et les autres journaux de table contiennent tous les journaux (main_sub_logs) créés à ce moment particulier qui, dans votre cas, peuvent être jusqu'à 10000 journaux par seconde. Le main_sub_logs fait référence à main_logs et il contient pour chaque seconde de journal et un nombre X de journaux appartient à cette seconde avec son propre identifiant de compteur, qui recommence.
De cette façon, vous limitez la recherche de séries chronologiques à quelques secondes de fenêtres d'événements au lieu de tous les journaux au même endroit.
De cette façon, vous pouvez joindre ces deux tables et lorsque vous recherchez dans la première table entre 2 heures spécifiques, vous obtenez tous les journaux entre les deux.
Alors, voici comment j'ai créé mes 2 tables:
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)
)
J'ai inséré des données factices:

Interroge maintenant tous les journaux entre 1608718655 et 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
Obtiendra ce résultat:
