Comment utiliser des séries temporelles avec Sqlite, avec des requêtes rapides sur la plage de temps?

Dec 23 2020

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 PLANdonne SCAN TABLE datace 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 tspour 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 tscomme INTEGER PRIMARY KEY, il en tsserait de rowidmême pour le lui - même. Mais cela échoue car ce tsn'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 rowidcomme horodatage tsconcaténé avec un nombre croissant. Exemple:

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

    Ensuite rowidest unique et strictement croissant (à condition qu'il y ait moins de 10k événements par seconde), et aucun index ne serait requis. Une requête WHERE ts BETWEEN a AND bdeviendrait simplement WHERE rowid BETWEEN a*10000 AND b*10000+9999.

    Mais existe-t-il un moyen simple de demander à Sqlite INSERTun élément avec une valeur rowidsupérieure ou égale à une valeur donnée? Disons que l'horodatage actuel est 1608718654et 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

4 Basj Dec 24 2020 at 04:49

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 dtcomme 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 rowidcolonne 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 AUTOINCREMENTqui crée en interne une sqlite_sequencetable, 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*10000et last_added_ID + 1pour 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 ROWIDtable

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 ROWIDest utile lorsque l'on veut utiliser a PRIMARY KEY(dt, another_column1, another_column2, id)et éviter d'avoir une rowidcolonne supplémentaire . Au lieu d'avoir un arbre B pour rowidet 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 ----]
2 maytham-ɯɐɥʇʎɐɯ Dec 26 2020 at 16:59

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: