如何在快速时间范围查询中将时间序列与Sqlite一起使用？

Question

假设我们使用Unix timestamp列将事件记录在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)。

这样就解决了问题，但是要为已经增加的序列/已经排序的列维护索引是一个很 糟糕的解决方案ts，我们可以 直接在O（log n）中 使用
B树搜索 来为其建立索引。在内部，这将是索引：

ts           rowid
1608000001   1
1608000002   2
1608000012   3
1608000077   4

这浪费了数据库空间（和查询必须先在索引中查找时的CPU）。

为了避免这种情况：

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

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

• （2）我们可以将rowid时间戳作为ts与越来越多的数字连接使用的时间戳。例子：

   16087186540001
  

  16087186540002
  [--------][–]
  ts increasing number

然后rowid是唯一且严格增加的（假设每秒事件少于1万次），并且不需要索引。查询WHERE ts BETWEEN a AND b将变成WHERErowid 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

第一个解决方案

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

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

这里的关键点是dt用作INTEGER PRIMARY KEY，因此 它将是行ID本身，使用B树，并且不会 再有其他隐藏rowid列。因此，我们避免了会产生对应关系的额外索引dt => rowid：这dt 是 行ID。

我们还使用AUTOINCREMENT它在内部创建一个sqlite_sequence表，该表跟踪最后添加的ID。插入时，这是非常有用的：因为它是可能的两个事件都在几秒钟内的同一时刻（有可能甚至毫秒或微秒时间戳，操作系统可能会截断精度），我们使用的最大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当我们要使用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)

所有这些方法使用的ID为：

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