Como usar a série temporal com Sqlite, com consultas rápidas de intervalo de tempo?

Question

Digamos que registramos eventos em um banco de dados Sqlite com coluna de carimbo de data / hora Unix ts:

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

e que queremos uma pesquisa rápida para intervalos de data e hora, por exemplo:

SELECT text FROM data WHERE ts BETWEEN 1608710000 and 1608718654;

Assim, EXPLAIN QUERY PLANdá o SCAN TABLE dataque é ruim, então uma solução óbvia é criar um índice com CREATE INDEX dt_idx ON data(ts).

Então o problema está resolvido, mas é uma solução bastante pobre ter que manter um índice para uma sequência já crescente / coluna já classificada tspara a qual poderíamos usar uma pesquisa de árvore B em O (log n) diretamente . Internamente, este será o índice:

ts           rowid
1608000001   1
1608000002   2
1608000012   3
1608000077   4

o que é um desperdício de espaço do banco de dados (e CPU quando uma consulta precisa primeiro olhar o índice).

Para evitar isso:

• (1) poderíamos usar tscomo INTEGER PRIMARY KEY, o mesmo tsseria o rowidpróprio. Mas isso falha porque tsnão é único: 2 eventos podem acontecer no mesmo segundo (ou mesmo no mesmo milissegundo).

  Veja, por exemplo, as informações fornecidas em SQLite Autoincrement .

• (2) poderíamos usar rowidcomo carimbo de data / hora tsconcatenado com um número crescente. Exemplo:

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

  Então, rowidé exclusivo e estritamente crescente (desde que haja menos de 10k eventos por segundo), e nenhum índice seria necessário. Uma consulta WHERE ts BETWEEN a AND bsimplesmente se tornaria WHERE rowid BETWEEN a*10000 AND b*10000+9999.

  Mas existe uma maneira fácil de solicitar ao Sqlite INSERTum item com um valor rowidmaior ou igual a um determinado valor? Digamos que o carimbo de data / hora atual seja 1608718654e dois eventos apareçam:

    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 forma mais geral, como criar séries temporais de forma otimizada com Sqlite, para ter consultas rápidas WHERE timestamp BETWEEN a AND b?

Answer 1

Primeira solução

O método (2) detalhado na pergunta parece funcionar bem. Em um benchmark, obtive:

• método ingênuo, sem índice: banco de dados de 18 MB, tempo de consulta de 86 ms
• método ingênuo, com índice: banco de dados de 32 MB, tempo de consulta de 12 ms
• método (2): banco de dados de 18 MB, tempo de consulta de 12 ms

O ponto chave está aqui para usar dtcomo um INTEGER PRIMARY KEY, então isso será o próprio id de linha (ver também é um índice necessário para uma chave primária em SQLite? ), Usando uma B-tree, e haverá não ser outra escondida rowidcoluna. Assim, evitamos um índice extra que faria uma correspondência dt => rowid: aqui dt está o id da linha.

Também usamos o AUTOINCREMENTque cria internamente uma sqlite_sequencetabela, que mantém o controle do último ID adicionado. Isso é útil ao inserir: como é possível que dois eventos tenham o mesmo carimbo de data / hora em segundos (seria possível mesmo com carimbos de data / hora em milissegundos ou microssegundos, o sistema operacional poderia truncar a precisão), usamos o máximo entre timestamp*10000e last_added_ID + 1para garantir que seja ú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 uma WITHOUT ROWIDmesa

Aqui está outro método com o WITHOUT ROWIDqual fornece um tempo de consulta de 8 ms . Temos que implementar um id de auto-incremento nós mesmos, uma vez que AUTOINCREMENT não está disponível ao usar WITHOUT ROWID.
WITHOUT ROWIDé útil quando queremos usar um PRIMARY KEY(dt, another_column1, another_column2, id)e evitar ter uma rowidcoluna extra . Em vez de ter uma árvore B para rowide uma árvore B para (dt, another_column1, ...), teremos apenas uma.

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 aproximadamente classificado

De maneira mais geral, o problema está relacionado ao fato de ter IDs "classificados de maneira aproximada" por data e hora. Mais sobre isso:

• ULID ( identificador universalmente único classificável lexicograficamente)
• Floco de neve
• MongoDB ObjectId

Todos esses métodos usam um ID que é:

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

Answer 2

Não sou especialista em SqlLite, mas trabalhei com bancos de dados e séries temporais. Eu tive situação semelhante anteriormente e gostaria de compartilhar minha solução conceitual.

Você tem alguma parte da resposta em sua pergunta, mas não a maneira de fazê-lo.

Do jeito que eu fiz, criando 2 tabelas, uma tabela (main_logs) irá registrar o tempo em segundos de incremento como data como inteiro como chave primária e os outros logs da tabela contêm todos os logs (main_sub_logs) que feitos naquele tempo particular que no seu caso podem ter até 10.000 logs por segundo. O main_sub_logs tem referência a main_logs e contém para cada segundo de log e um número X de logs pertencentes a esse segundo com o próprio contador de id, que começa novamente.

Dessa forma, você limita a consulta de séries temporais a segundos de janelas de eventos, em vez de todos os registros em um só lugar.

Desta forma, você pode unir essas duas tabelas e quando você procurar na primeira tabela entre 2 horários específicos, obterá todos os logs intermediários.

Então, aqui está como criei minhas 2 tabelas:

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

Inseri alguns dados fictícios:

Agora vamos consultar todos os registros entre 1608718655 e 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

Obterá este resultado: