¿Cómo usar series de tiempo con Sqlite, con consultas rápidas de rango de tiempo?

Question

Digamos que registramos eventos en una base de datos Sqlite con una columna de marca de tiempo Unix ts:

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

y que queremos una búsqueda rápida para los rangos de fecha y hora, por ejemplo:

SELECT text FROM data WHERE ts BETWEEN 1608710000 and 1608718654;

Así, EXPLAIN QUERY PLANda SCAN TABLE datacuál es malo, por lo que una solución obvia es crear un índice con CREATE INDEX dt_idx ON data(ts).

Entonces el problema está resuelto, pero es una mala solución tener que mantener un índice para una secuencia ya creciente / columna ya ordenada tspara la cual podríamos usar una búsqueda de árbol B en O (log n) directamente . Internamente, este será el índice:

ts           rowid
1608000001   1
1608000002   2
1608000012   3
1608000077   4

que es una pérdida de espacio de la base de datos (y CPU cuando una consulta tiene que buscar primero en el índice).

Para evitar esto:

• (1) podríamos usar tscomo INTEGER PRIMARY KEY, por tslo que sería el rowidmismo. Pero esto falla porque tsno es único: pueden ocurrir 2 eventos en el mismo segundo (o incluso en el mismo milisegundo).

  Vea, por ejemplo, la información proporcionada en SQLite Autoincrement .

• (2) podríamos usar rowidcomo marca de tiempo tsconcatenada con un número creciente. Ejemplo:

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

  Entonces rowides único y estrictamente creciente (siempre que haya menos de 10k eventos por segundo), y no se requeriría ningún índice. Una consulta WHERE ts BETWEEN a AND bsimplemente se convertiría en WHERE rowid BETWEEN a*10000 AND b*10000+9999.

  Pero, ¿hay una manera fácil de pedirle a Sqlite INSERTun elemento con un valor rowidmayor o igual a un determinado? Digamos que la marca de tiempo actual es 1608718654y aparecen dos eventos:

    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
  

De manera más general, ¿cómo crear series de tiempo de manera óptima con Sqlite, para tener consultas rápidas WHERE timestamp BETWEEN a AND b?

Answer 1

Primera solucion

El método (2) detallado en la pregunta parece funcionar bien. En un benchmark, obtuve:

• método ingenuo, sin índice: base de datos de 18 MB, tiempo de consulta de 86 ms
• método ingenuo, con índice: base de datos de 32 MB, tiempo de consulta de 12 ms
• método (2): base de datos de 18 MB, tiempo de consulta de 12 ms

El punto clave es aquí para usar dtcomo INTEGER PRIMARY KEY, por lo que será la misma fila Identificación (véase también es un índice necesario para una clave principal de SQLite? ), Usando un árbol B, y no habrá no ser otra oculta rowidla columna. Por lo tanto, evitamos un índice adicional que haría una correspondencia dt => rowid: aquí dt está la identificación de la fila.

También usamos AUTOINCREMENTque crea internamente una sqlite_sequencetabla, que realiza un seguimiento del último ID agregado. Esto es útil al insertar: dado que es posible que dos eventos tengan la misma marca de tiempo en segundos (sería posible incluso con marcas de tiempo de milisegundos o microsegundos, el sistema operativo podría truncar la precisión), usamos el máximo entre timestamp*10000y last_added_ID + 1para asegurarnos de que sea único :

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

Código:

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)

---

Usando una WITHOUT ROWIDmesa

Aquí hay otro método con el WITHOUT ROWIDque da un tiempo de consulta de 8 ms . Tenemos que implementar un ID de incremento automático nosotros mismos, ya que AUTOINCREMENT no está disponible cuando se usa WITHOUT ROWID.
WITHOUT ROWIDes útil cuando queremos usar ay PRIMARY KEY(dt, another_column1, another_column2, id)evitar tener una rowidcolumna extra . En lugar de tener un árbol B para rowidy un árbol B para (dt, another_column1, ...), tendremos solo uno.

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 aproximado

De manera más general, el problema está relacionado con tener ID que están "ordenados de forma aproximada" por fecha y hora. Más sobre esto:

• ULID ( Identificador universalmente único ordenable lexicográficamente)
• Copo de nieve
• ObjectId de MongoDB

Todos estos métodos utilizan una identificación que es:

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

Answer 2

No soy experto en SqlLite, pero he trabajado con bases de datos y series de tiempo. He tenido una situación similar anteriormente y compartiría mi solución conceptual.

De alguna manera tiene parte de la respuesta en su pregunta, pero no la forma de hacerlo.

De la forma en que lo hice, creando 2 tablas, una tabla (main_logs) registrará el tiempo en incrementos de segundos como fecha como entero como clave principal y los otros registros de la tabla contienen todos los registros (main_sub_logs) que se hicieron en ese momento particular que en su caso puede estar hasta 10000 registros por segundo en él. Main_sub_logs hace referencia a main_logs y contiene para cada segundo de registro y X número de registros pertenecen a ese segundo con su propio ID de contador, que comienza de nuevo.

De esta manera, limita su búsqueda de series de tiempo a segundos de ventanas de eventos en lugar de a todos los registros en un solo lugar.

De esta manera, puede unir esas dos tablas y cuando busque en la primera tabla entre 2 horas específicas, obtendrá todos los registros intermedios.

Entonces, ¿qué es cómo creé mis 2 tablas?

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

He insertado algunos datos ficticios:

Ahora vamos a consultar todos los registros entre 1608718655 y 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

Obtendrá este resultado: