如何在SQLite中以O(log(N))时间查询与指定区间相交的区间

问题分析 #

原表存储半开时间戳区间[start_time_us; stop_time_us)，原查询通过start_time_us < :stop_time_us AND :start_time_us < stop_time_us筛选相交区间，但SQLite仅会单方向扫描interval_start_idx索引，遍历近半棵B树，时间复杂度为O(N)，无法满足性能要求。

优化思路 #

将区间相交的条件拆分为两个互斥的索引友好子条件，分别利用已创建的两个覆盖索引做高效范围扫描，再合并结果：

• 表区间的起始时间落在查询区间内：start_time_us >= :start_time_us AND start_time_us < :stop_time_us —— 可通过interval_start_idx快速定位
• 表区间起始早于查询区间，但结束时间晚于查询区间起始：start_time_us < :start_time_us AND stop_time_us > :start_time_us —— 可通过interval_stop_idx高效筛选

由于两个子条件互斥，用UNION ALL合并结果（避免UNION的去重开销），最后按要求排序。

实现代码 #

-- 可选但推荐：添加CHECK约束保证数据合法性
ALTER TABLE interval ADD CHECK (start_time_us < stop_time_us);

-- 优化后的区间相交查询
SELECT * FROM (
    -- 子查询1：区间起始落在查询范围内
    SELECT * FROM interval
    WHERE start_time_us >= :start_time_us
      AND start_time_us < :stop_time_us
    UNION ALL
    -- 子查询2：区间起始早于查询起始，但未在查询起始前结束
    SELECT * FROM interval
    WHERE stop_time_us > :start_time_us
      AND start_time_us < :start_time_us
) AS combined_intervals
ORDER BY start_time_us;

执行计划验证 #

运行EXPLAIN QUERY PLAN可看到：

• 第一个子查询会使用interval_start_idx索引做范围扫描，仅遍历符合start_time_us范围的行
• 第二个子查询会使用interval_stop_idx索引，先定位stop_time_us > :start_time_us的行，再过滤start_time_us < :start_time_us的记录
• 整体时间复杂度为O(logN + K)，其中K为匹配的区间数量，当K远小于总数据量N时，接近O(logN)的性能。

内容的提问来源于stack exchange，提问作者yuri kilochek