如何在 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哪个不好，所以一个明显的解决方案是创建一个带有CREATE INDEX dt_idx ON data(ts).

然后问题就解决了，但是对于一个已经增加的序列/已经排序的列维护一个索引，我们可以直接在 O(log n) 中使用B 树搜索，这是一个相当糟糕的解决方案。在内部，这将是索引：ts

ts           rowid
1608000001   1
1608000002   2
1608000012   3
1608000077   4

这浪费了数据库空间（当查询必须首先查看索引时浪费 CPU）。

为避免这种情况：

• （1）我们可以使用ts的INTEGER PRIMARY KEY，所以ts会是rowid自己。但这失败了，因为ts它不是唯一的：2 个事件可以在同一秒（甚至在同一毫秒）发生。

  例如，参见SQLite Autoincrement 中给出的信息。

• (2) 我们可以使用rowid作为ts与递增数字连接的时间戳。例子：

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

  然后rowid是唯一且严格递增的（假设每秒事件数少于 10k），并且不需要索引。查询WHERE ts BETWEEN a AND b将简单地变为WHERE rowid BETWEEN a*10000 AND b*10000+9999.

  但有一个简单的方法来问SQLite的到INSERT的项目有rowid大于或等于给定值？假设当前时间戳是1608718654并且出现两个事件：

    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

我不是 SqlLite 方面的专家，但曾使用过数据库和时间序列。我以前也遇到过类似的情况，我会分享我的概念解决方案。

您在问题中找到了答案的一部分，但没有找到解决方法。

我这样做的方式是，创建 2 个表，一个表（main_logs）将以秒为单位记录时间增量，作为日期作为整数作为主键，其他表日志包含在该特定时间生成的所有日志（main_sub_logs），在您的情况下可以每秒最多可处理 10000 个日志。main_sub_logs 引用了 main_logs，它包含每个日志秒和属于该秒的 X 条日志，具有自己的计数器 id，并重新开始。

通过这种方式，您可以将时间序列查找限制为事件窗口的几秒，而不是将所有日志集中在一个位置。

通过这种方式，您可以连接这两个表，当您在两个特定时间之间从第一个表中查找时，您将获得其间的所有日志。

这是我创建两张表的方法：

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

会得到这样的结果：

Answer 2

第一个解决方案

问题中详述的方法（2）似乎运作良好。在基准测试中，我获得了：

• 天真的方法，没有索引：18 MB 数据库，86 ms 查询时间
• naive 方法，带索引：32 MB 数据库，12 ms 查询时间
• 方法（2）：18MB数据库，12ms查询时间

关键点在这里dt用作INTEGER PRIMARY KEY，因此它将是行 id 本身（另请参阅SQLite 中的主键是否需要索引？），使用 B 树，并且不会有另一个隐藏rowid列。因此，我们避免了会产生对应关系的额外索引dt => rowid：这dt 是行 ID。

我们还使用AUTOINCREMENTwhich 在内部创建一个sqlite_sequence表，它跟踪最后添加的 ID。插入时，这是非常有用的：因为它是可能的两个事件都在几秒钟内的同一时刻（有可能甚至毫秒或微秒时间戳，操作系统可能会截断精度），我们使用的最大timestamp*10000和last_added_ID + 1，以确保它的独特：

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

代码：

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

使用WITHOUT ROWID表格

这是另一种WITHOUT ROWID提供8 毫秒查询时间的方法。我们必须自己实现一个自动递增的 id，因为 AUTOINCREMENT 在使用时不可用WITHOUT ROWID。
WITHOUT ROWID当我们想使用 aPRIMARY KEY(dt, another_column1, another_column2, id)并避免有额外的rowid列时很有用。我们将只有一个，而不是一个 B 树rowid和一个 B 树(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（通用唯一字典可排序标识符）
• 雪花
• MongoDB 对象 ID

所有这些方法都使用一个 ID，它是：

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