高速な時間範囲クエリで、Sqliteで時系列を使用する方法は？

Question

Unixタイムスタンプ列を使用してSqliteデータベースにイベントを記録するとしますts。

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

また、日時範囲をすばやく検索する必要があります。次に例を示します。

SELECT text FROM data WHERE ts BETWEEN 1608710000 and 1608718654;

このように、EXPLAIN QUERY PLAN与えますSCAN TABLE dataので、1つの明白な解決策をしている、悪いであるインデックスを作成してCREATE INDEX dt_idx ON data(ts)。

その後、問題は解決されますが、O（log n）でBツリー検索を直接使用できる、すでに増加しているシーケンス/すでにソートされている列のインデックスを維持する必要があるのは、かなり貧弱な解決策です。内部的には、これがインデックスになります。ts

ts           rowid
1608000001   1
1608000002   2
1608000012   3
1608000077   4

これはDBスペース（およびクエリが最初にインデックスを調べなければならない場合はCPU）の浪費です。

これを回避するには：

• （1）私たちは使用することができますtsようにINTEGER PRIMARY KEY、そうtsだろうrowidそのもの。ただし、これtsは一意ではないため失敗します。2つのイベントが同じ秒（または同じミリ秒）で発生する可能性があります。

  たとえばで与えられた情報を参照してくださいSQLiteの自動インクリメントを。

• （2）増加する数と連結さrowidれたタイムスタンプとして使用できますts。例：

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

  次にrowid、一意で厳密に増加し（1秒あたりのイベント数が10,000未満の場合）、インデックスは必要ありません。クエリWHERE ts BETWEEN a AND bは単純にになりWHERE rowid BETWEEN a*10000 AND b*10000+9999ます。

  しかし、与えられた値以上のINSERTアイテムをSqliteに要求する簡単な方法はありrowidますか？現在のタイムスタンプがで1608718654、2つのイベントが表示されたとします。

    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
  

より一般的には、高速クエリを実行するために、Sqliteを使用して時系列を最適に作成する方法はWHERE timestamp BETWEEN a AND b？

Answer 1

最初の解決策

質問で詳述されている方法（2）はうまく機能しているようです。ベンチマークでは、次のようになりました。

• 単純な方法、インデックスなし：18 MBデータベース、86ミリ秒のクエリ時間
• 単純な方法、インデックス付き：32 MBデータベース、12ミリ秒のクエリ時間
• 方法（2）：18 MBデータベース、12ミリ秒のクエリ時間

キーポイントが使用するためにここにあるdtようINTEGER PRIMARY KEYに、それは行ID自体であろう（参照？SQLiteの主キーのために必要な指標である）、Bツリーを使用して、そしてそこであろうしない別の隠されたことrowidカラム。したがって、私たちはcorrespondanceになるだろう、余分なインデックスを避けるdt => rowid：ここにdt ある行番号。

また、最後に追加されたIDを追跡AUTOINCREMENTするsqlite_sequenceテーブルを内部的に作成するwhichも使用します。それは（それもミリ秒またはマイクロ秒のタイムスタンプで、OSは精度を切り捨てる可能性が可能になります）2つのイベントが数秒で同じタイムスタンプを持っている可能性があるため、我々は間の最大値を使用します。これは、挿入するときに便利ですtimestamp*10000し、last_added_ID + 1必ずそれはユニークだ作るために：

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

コード：

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)

---

WITHOUT ROWIDテーブルの使用

WITHOUT ROWIDこれは、8ミリ秒のクエリ時間を与える別の方法です。を使用する場合はAUTOINCREMENTを使用できないため、自動インクリメントIDを自分で実装する必要がありますWITHOUT ROWID。
WITHOUT ROWIDを使用しPRIMARY KEY(dt, another_column1, another_column2, id)、余分なrowid列を避けたい場合に便利です。のBツリーrowidとBツリーを1つずつ持つ代わりに、1つ(dt, another_column1, ...)だけにします。

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

より一般的には、この問題は、日時によって「大まかにソート」されたIDを持つことに関連しています。これについての詳細：

• ULID（Universally Unique Lexicographically Sortable Identifier）
• スノーフレーク
• MongoDB ObjectId

これらのメソッドはすべて、次のIDを使用します。

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

Answer 2

私はSqlLiteの専門家ではありませんが、データベースと時系列を扱ってきました。私は以前に同様の状況にありました、そして私は私の概念的な解決策を共有したいと思います。

あなたはあなたの質問の答えの一部を持っていますが、それを行う方法はありません。

私のやり方では、2つのテーブルを作成し、1つのテーブル（main_logs）は、主キーとして整数として日付として秒単位で時間を記録し、他のテーブルログには、その特定の時間に作成されたすべてのログ（main_sub_logs）が含まれます。 1秒あたり最大10000ログになります。main_sub_logsにはmain_logsへの参照があり、ログごとに1秒が含まれ、X個のログが独自のカウンターIDを持つその秒に属し、最初からやり直します。

このようにして、すべてのログを1か所にまとめるのではなく、時系列検索を最大数秒のイベントウィンドウに制限します。

このようにして、これら2つのテーブルを結合し、最初のテーブルから2つの特定の時間の間に検索すると、その間にすべてのログが記録されます。

では、2つのテーブルを作成した方法は次のとおりです。

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

いくつかのダミーデータを挿入しました：

1608718655から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

この結果が得られます：