如何在Sqlite中使用时间序列，以及快速的时间范围查询？

html5 • • 问答

假设我们使用 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？

回答

第一个解决方案

问题中详述的方法（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 ----]

以上是如何在Sqlite中使用时间序列，以及快速的时间范围查询？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>