数据库 性能优化案例分析之二:时间区域查询的性能优化

quakewang · 发布于 2017年11月14日 · 最后由 sharpx 回复于 2017年11月17日 · 749 次阅读
162
本帖已被设为精华帖!

背景

我们在项目中经常会遇到把事件显示在日历上的需求,在项目管理,事件追踪,预约等相关功能中很常见,界面通常类似这样:

常见的做法是给对应表添加开始时间和结束时间的栏位:start_time and end_time,然后构建一个查询得到这个时间段内的数据,示意如下:

            |---给定时间段---|
|---A---| |---B---|  |-C-|   |---D---|

查询要排除掉A和D这种数据,也就是结束时间小于给定的开始时间,或者开始时间大于给定的结束时间:not (end_time <= :start or start_time >= :end)

从 NOT (A OR B) 可以得到 (NOT A) AND (NOT B),最终的查询语句是这样:

select * from events where end_time > :start and start_time < :end

考虑到这是一个范围查找,通常都会给这2个栏位加上索引,数据量小的时候,这个查询效率很高,但在数据增加到百万级别之后,在慢查询日志里面经常会发现这个查询耗时超过几百毫秒,随着数据量的增加,甚至超过3000毫秒。

分析过程

继续用慢查询的分析过程套路

第一步:EXPLAIN

有时候相同的查询语句,只是查询参数少许不同,会导致预估的IO Cost不同,执行计划也会改变,我们可以看到,这个查询有时候会用start_time的索引,有时候会用end_time的索引:

explain select * from events where end_time > '2017-05-01 00:00:00' and start_time < '2017-06-01 00:00:00'\G

  select_type: SIMPLE
        table: events
   partitions: NULL
         type: range
possible_keys: index_events_on_start_time,index_events_on_end_time
          key: index_events_on_start_time
      key_len: 5
          ref: NULL
         rows: 799704
     filtered: 50.00
        Extra: Using index condition; Using where; Using MRR


explain select * from events where end_time > '2017-08-01 14:00:00' and start_time < '2017-09-01 00:00:00'\G

  select_type: SIMPLE
        table: events
   partitions: NULL
         type: range
possible_keys: index_events_on_start_time,index_events_on_end_time
          key: index_events_on_end_time
      key_len: 5
          ref: NULL
         rows: 946430
     filtered: 50.00
        Extra: Using index condition; Using where; Using MRR

第二步:理解执行计划

从执行计划其实已经可以看到这个慢查询的原因:需要检查的行数太多了,预估在79万和94万。但保险起见,还是从INFORMATION_SCHEMA.OPTIMIZER_TRACE表中获取信息来确认我们的猜测:

{
  "index": "index_events_on_start_time",
  "ranges": [
    "start_time < 0x999d02f000"
  ],
  "rows": 3147211,
  "cost": 2.73e6,
  "chosen": false
},
{
  "index": "index_events_on_end_time",
  "ranges": [
    "0x999d02e000 < end_time"
  ],
  "rows": 946430,
  "cost": 826083,
  "chosen": true
}

这个查询相当于构建了 无穷小 <= start_time <= ?? <= end_time <= 无穷大 这样2个开放区间查询。在这里由于前者的开放区间内有超过300万的数据需要检查,所以执行计划选择了后者相对比较小的94万作为索引。

第三步:分析数据

这个表有超过600万的数据:

show table status like 'events'\G

           Name: events
         Engine: InnoDB
           Rows: 6294423

所有的数据开始时间和结束时间均匀分布,索引也没有问题,而且查询除了按月,也有按其他维度(天,日,小时,指定范围)来进行查询,通过添加辅助字段也无法减少开放区间的查询数据量,好像进入了一个死胡同...

解决方案

遇到现有知识无法解决的问题,那就Google吧,经过尝试不同的关键字(关于如何选择关键字解决日常搬砖遇到的问题,可以留个坑,以后再写)发现了一篇很详细的文章,和我们遇到的情况是一模一样: https://explainextended.com/2009/07/01/overlapping-ranges-mysql/

文章提到了将时间区间变成二维线段,然后利用R-Tree (spatial) 索引,通过范围重叠来解决这个性能问题。看起来很不错,那就开动吧。

添加一个辅助字段并添加索引:

alter table events add column time_range linestring;
create spatial index index_events_on_time_range on events(time_range);

然后把时间区间转换成线段更新到这个字段:

update events set time_range = LineString(Point(-1, UNIX_TIMESTAMP(start_time)), Point(1,UNIX_TIMESTAMP(end_time)));

用MBRIntersects函数来查询重叠:

select * from events where MBRIntersects(time_range, LineString(Point(0, UNIX_TIMESTAMP('2017-08-01 00:00:00')), Point(0, UNIX_TIMESTAMP('2017-09-01 00:00:00'))));

80 毫秒! 相同的查询之前需要2410毫秒:

select * from events where end_time >= '2017-07-01 00:00:00' and start_time <= '2017-08-01 00:00:00';

给数据库再加个trigger,当更新和插入数据时,自动更新time_range这个字段:

CREATE TRIGGER events_insert_time_range BEFORE INSERT ON events
FOR EACH ROW
BEGIN
  SET NEW.time_range = LineString(Point(-1, UNIX_TIMESTAMP(NEW.start_time)), Point(1, UNIX_TIMESTAMP(NEW.end_time)));
END

CREATE TRIGGER events_update_time_range BEFORE UPDATE ON events
FOR EACH ROW
BEGIN
  IF ((NEW.start_time != OLD.start_time) OR (NEW.end_time != OLD.end_time)) THEN
    SET NEW.date_range = LineString(Point(-1, UNIX_TIMESTAMP(NEW.start_time)), Point(1, UNIX_TIMESTAMP(NEW.end_time)));
  END IF;
END

问题解决收工!

扩展

这个问题有很多可以扩展的问题:

我们之前只会将R-Tree用在地理位置的查询,从这个问题可以扩展到时间,IP地址等其他类似的查询,除了这些范围查询还有其他适合应用的场景吗?

文章中构建的线段是(-1,start_time)到(1,end_time)的一条斜线,用位于X等于0的线段去查询重叠。为什么不能用更直观的方式(类似文章开头的线段示意图),构建一个(start_time, 0)到(end_time,0)一条线段,然后用Y等于0的线段去查询重叠呢?

如果不用数据库trigger,在rails里面有什么方法能够自动更新这个辅助字段呢?甚至更进一步,是否可以删除掉start_time和end_time这2个字段,只用time_range这一个字段来满足所有的查询需求呢?

下篇占坑 性能优化案例分析之三:N:M的用户动态优化

共收到 10 条回复
27

赞!以前从没用过 R-Tree 的索引, 居然还可以这样用,看来以后优化区间查询的,都可以用 R-Tree 来试一下

96

👍, 期待后续更多精彩

1 Rei 将本帖设为了精华贴 11月14日 12:32
775

PG有tsrange类型,今天看文档才知道PG可以在数据库判断有没有overlap https://www.postgresql.org/docs/9.3/static/rangetypes.html#RANGETYPES-CONSTRAINT

162
775nouse 回复

对,ActiveRecord的PG支持有range这个类型,Mysql就比较落后了,得自己去实现,就是提到的扩展问题3: http://edgeguides.rubyonrails.org/active_record_postgresql.html#range-types

910

如果用integer存储时间,是不是就会好很多呢?

1a9967

写得真棒,谢谢分享。

5984
775nouse 回复

之前做日历的类似需求用的就是pg的overlap函数,不知道这个有性能问题吗。

24422

赞,很有启发,谢谢分享

C5fc5e

王老师的东西都是精品

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册