Bagaimana cara menggunakan deret waktu dengan Sqlite, dengan kueri rentang waktu cepat?

Question

Katakanlah kita mencatat peristiwa dalam database Sqlite dengan kolom stempel waktu Unix ts:

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

dan kami ingin pencarian cepat untuk rentang waktu, misalnya:

SELECT text FROM data WHERE ts BETWEEN 1608710000 and 1608718654;

Seperti ini, EXPLAIN QUERY PLANmemberikan SCAN TABLE datayang buruk, jadi salah satu solusi yang jelas adalah untuk membuat indeks dengan CREATE INDEX dt_idx ON data(ts).

Kemudian masalah terpecahkan, tetapi ini adalah solusi yang buruk untuk mempertahankan indeks untuk kolom urutan / yang sudah diurutkan yang sudah meningkat tssehingga kita dapat menggunakan pencarian B-tree di O (log n) secara langsung . Secara internal, ini akan menjadi indeks:

ts           rowid
1608000001   1
1608000002   2
1608000012   3
1608000077   4

yang merupakan pemborosan ruang DB (dan CPU saat kueri harus melihat indeks terlebih dahulu).

Untuk menghindari ini:

• (1) bisa kita gunakan tssebagai INTEGER PRIMARY KEY, begitu tsjuga dengan rowiddirinya sendiri. Tetapi ini gagal karena tstidak unik: 2 peristiwa dapat terjadi pada detik yang sama (atau bahkan pada milidetik yang sama).

  Lihat misalnya info yang diberikan dalam SQLite Autoincrement .

• (2) bisa kita gunakan rowidsebagai stempel waktu yang tsdigabungkan dengan jumlah yang meningkat. Contoh:

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

  Kemudian rowidunik dan meningkat tajam (asalkan ada kurang dari 10k peristiwa per detik), dan tidak ada indeks yang diperlukan. Sebuah kueri WHERE ts BETWEEN a AND bakan menjadi WHERE rowid BETWEEN a*10000 AND b*10000+9999.

  Tetapi apakah ada cara mudah untuk meminta Sqlite ke INSERTitem dengan nilai rowidlebih dari atau sama dengan nilai tertentu? Misalkan stempel waktu saat ini adalah 1608718654dan dua peristiwa muncul:

    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
  

Secara lebih umum, bagaimana cara membuat deret waktu secara optimal dengan Sqlite, agar memiliki kueri yang cepat WHERE timestamp BETWEEN a AND b?

Answer 1

Solusi pertama

Metode (2) yang dirinci dalam pertanyaan tampaknya bekerja dengan baik. Sebagai patokan, saya memperoleh:

• metode naif, tanpa indeks: database 18 MB, waktu kueri 86 ms
• metode naif, dengan indeks: database 32 MB, waktu kueri 12 ms
• metode (2): database 18 MB, waktu kueri 12 ms

Titik kunci di sini untuk menggunakan dtsebagai INTEGER PRIMARY KEY, sehingga itu akan menjadi id baris itu sendiri (lihat juga Apakah indeks diperlukan untuk kunci utama dalam SQLite? ), Menggunakan B-pohon, dan akan tidak ada lagi yang tersembunyi rowidkolom. Dengan demikian kita menghindari indeks ekstra yang akan membuat correspondance sebuah dt => rowid: di sini dt adalah baris id.

Kami juga menggunakan AUTOINCREMENTyang secara internal membuat sqlite_sequencetabel, yang melacak ID yang ditambahkan terakhir. Ini berguna saat memasukkan: karena ada kemungkinan bahwa dua peristiwa memiliki stempel waktu yang sama dalam hitungan detik (bahkan dengan stempel waktu milidetik atau mikrodetik, OS dapat memotong presisi), kami menggunakan maksimum antara timestamp*10000dan last_added_ID + 1untuk memastikannya unik :

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

Kode:

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)

---

Menggunakan WITHOUT ROWIDmeja

Berikut adalah metode lain WITHOUT ROWIDyang memberikan waktu kueri 8 ms . Kita harus menerapkan id auto-incrementing sendiri, karena AUTOINCREMENT tidak tersedia saat menggunakan WITHOUT ROWID.
WITHOUT ROWIDberguna ketika kita ingin menggunakan a PRIMARY KEY(dt, another_column1, another_column2, id)dan menghindari memiliki rowidkolom tambahan . Alih-alih memiliki satu pohon-B untuk rowiddan satu pohon-B (dt, another_column1, ...), kita hanya akan memiliki satu.

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 yang diurutkan secara kasar

Secara lebih umum, masalah terkait dengan memiliki ID yang "diurutkan secara kasar" menurut tanggal waktu. Lebih lanjut tentang ini:

• ULID ( Pengenal yang Dapat Diurutkan Secara Leksikografis Unik Secara Universal)
• Kepingan salju
• ObjectId MongoDB

Semua metode ini menggunakan ID yaitu:

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

Answer 2

Saya bukan ahli dalam SqlLite, tetapi telah bekerja dengan database dan deret waktu. Saya pernah mengalami situasi serupa sebelumnya, dan saya akan membagikan solusi konseptual saya.

Anda memiliki beberapa bagian jawaban dalam pertanyaan Anda, tetapi bukan cara melakukannya.

Cara saya melakukannya, membuat 2 tabel, satu tabel (main_logs) akan mencatat waktu dalam hitungan detik sebagai tanggal sebagai integer sebagai kunci utama dan log tabel lainnya berisi semua log (main_sub_logs) yang dibuat dalam waktu tertentu yang dalam kasus Anda dapat hingga 10.000 log per detik di dalamnya. Main_sub_logs memiliki referensi ke main_logs dan berisi untuk setiap detik log dan nomor X log milik detik itu dengan id penghitung sendiri, yang dimulai dari awal lagi.

Dengan cara ini Anda membatasi pencarian deret waktu Anda hingga detik dari jendela peristiwa alih-alih semua log di satu tempat.

Dengan cara ini Anda dapat menggabungkan kedua tabel tersebut dan ketika Anda mencari dari tabel pertama antara 2 waktu tertentu Anda mendapatkan semua log di antaranya.

Jadi apa di sini adalah cara saya membuat 2 tabel saya:

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

Saya telah memasukkan beberapa data dummy:

Sekarang mari menanyakan semua log antara 1608718655 dan 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

Akan mendapatkan hasil ini: