高并发低基数多字段任意组合查询的优化

1.问题

首先解释一下这个标题里出现的"低基数多字段任意组合查询"指什么东西。这里是指满足下面几个条件的查询：
1. 检索条件中涉及多个字段条件的组合
2. 这些字段的组合是不确定的
3. 每个单独字段的选择性都不好

这种类型的查询的使用场景很多，比如电商的商品展示页面。用户会输入各种不同查询条件组合：品类，供应商，品牌，促销，价格等等...,最后往往还要对结果进行排序和分页。

这类问题令人头疼的地方在于：
1. 记录数量众多，如果进行全表扫描性能低下无法满足高并发访问的要求。
2. 查询条件涉及的任何单个字段的选择性都很低，不能通过单字段索引解决查询效率问题。
3. 如果建立普通的Btree多字段索引，由于用户的输入条件组合太多，可能要建成百上千个索引，这不现实也很难维护。

2.方案

对这类问题我想到的解决方案有2种

2.1 bitmap索引

bitmap的特点是存储key以及所有取值等于这个key的行集的bitmap，对于涉及多个key的组合查询，只需把这些key对应的bitmap做与或运算即可。由于bitmap的size很小，bit与或运算的效率也很高，所以bitmap非常适合做这类查询。
bitmap索引也有缺点，更新一条记录就会锁住整个表，不适合并发写比较多的场景。另外一个问题是，常见的关系数据库中支持bitmap索引的似乎只有Oracle一家，而我们很多时候我们想用开源数据库。

2.2 倒排索引

倒排索引和bitmap有相似之处，存储的是key和取值等于这个key的行集，行集可能是list也可能是tree或其它存储形式。对于多个key的组合查询，把这些key的结果做集合运算即可。
倒排索引一般用于全文检索，但很多系统也用它支持结构化数据的搜索，比如Elasticsearch。Elasticsearch支持JSON文档的快速搜索，支持复合查询，排序，聚合，分布式部署等很多不错的特性。但是考虑下面几个因素，我们更希望在关系数据库里找方案。
-不需要使用搜索引擎为模糊匹配提供的高级特性，实际上我们需要是精确匹配或者简单的模糊匹配。
-数据量还没有大到需要建一个分布式搜索集群。
-原始数据本来就在关系数据库里，不想烦心数据同步的问题。
-已经基于关系数据库的接口开发了应用，不想推倒重来。
-已经掌握了关系数据库的运维管理，对于全新的系统不知道还要踩多少坑。
-考虑到Java和C效能差异，关系数据库内建方案的性能未必输与专业的搜索引擎。

3. PostgreSQL的解法

如果把解决方案的范围限定在开源关系数据库，答案可能只有一个，就是PostgreSQL的gin索引。
PostgreSQL的gin索引就是倒排索引，它不仅被用于全文检索还可以用在常规的数据类型上，比如int,varchar。
对于多维查询我们可以这样建索引：
1. 对所有等值条件涉及的低基数字段，建立唯一一个多字段gin索引
2. 对选择性比较好的等值查询或范围查询涉及的字段，另外建btree索引

可能有同学会有疑问，同样是多字段索引，为什么gin的多字段索引只要建一个就可以了，而btree的多字段索引却要考虑各种查询组合建若干个。这是由于gin多字段索引中的每个字段是等价的，不存在前导字段的说法，所以只要建一个唯一的gin多字段索引就可以覆盖所有的查询组合；而btree多字段索引则不同，如果查询条件中不包含suoyi前导字段，是无法利用索引的。

多字段gin索引的内部存储的每个键是(column number,key datum)这样的形式，所以可以区分不同的字段而不致混淆。存储的值是匹配key的所有记录的ctid集合。这个集合在记录数比较多的情况下采用btree的形式存储,并且经过了压缩，所以gin索引占用的存储空间很小，大约只有等价的btree索引的二十分之一，这也从另一方面提升了性能。

对于多维查询涉及的多个字段，包含在多字段gin索引中的字段，由gin索引做ctid的集合归并(取并集或交集)，然后得到的ctid集合和其它索引得到的ctid集合再做BitmapAnd或BitmapOr归并。gin索引内部的ctid集合归并效率远高于索引间的ctid集合归并，而且gin索引对低基数字段的优化更好，所以充分利用gin索引的特性比为每个字段单独建一个btree索引再通过BitmapAnd或BitmapOr归并结果集效率高的多。

4. 一个真实的案例

4.1 原始查询

下面这个SQL是我司系统中一个真实SQL的简化版。

点击(此处)折叠或打开

  1. SELECT CASE WHEN gpppur.GB_BEGINDATE <= '2016-02-29 14:36:00' AND gpppur.GB_ENDDATE > '2016-02-29 14:36:00' THEN 1
  2.               WHEN gpppur.PREVIEW_BEGINDT <= '2016-02-29 14:36:00' AND gpppur.PREVIEW_ENDDT > '2016-02-29 14:36:00' THEN 2
  3.               ELSE 3 END AS flag,
  4.         gpppur.*
  5. FROM T_MPS_INFO gpppur
  6. WHERE gpppur.ATTRACT_TP = 0
  7.      AND gpppur.COLUMN_ID = 1
  8.      AND gpppur.FIELD2 = 1
  9.      AND gpppur.STATUS = 1
  10.      ORDER BY flag ASC,gpppur.PC_SORT_NUM ASC,gpppur.GB_BEGINDATE DESC
  11.      LIMIT 0,45

用的是MySQL数据库，总数据量是60w，其中建有FIELD2+STATUS的多字段索引。
查询条件涉及的4个字段的值分布情况如下：

点击(此处)折叠或打开

  1. postgres=# select ATTRACT_TP,count(*) from T_MPS_INFO group by ATTRACT_TP;
  2.  attract_tp | count 
  3. ------------+--------
  4.             | 16196
  5.          6 | 251
  6.          2 | 50
  7.          1 | 3692
  8.          3 | 143
  9.          10 | 314
  10.          4 | 214
  11.          5 | 194333
  12.          9 | 326485
  13.          7 | 1029
  14.          0 | 6458
  15. (11 rows)
  16. postgres=# select COLUMN_ID,count(*) from T_MPS_INFO group by COLUMN_ID;
  17.  column_id | count 
  18. ------------+--------
  19.             | 2557
  20.         285 | 20
  21.         120 | 194
  22.         351 | 2
  23.         337 | 79
  24.         227 | 26
  25.         311 | 9
  26.         347 | 2
  27.         228 | 21
  28.         318 | 1
  29.         314 | 9
  30.          54 | 10
  31.         133 | 27
  32.  2147483647 | 1
  33.         336 | 1056
  34.         364 | 1
  35.         131 | 10
  36.         243 | 5
  37.         115 | 393
  38.          61 | 73
  39.         226 | 40
  40.         196 | 16
  41.         350 | 5
  42.         373 | 72
  43.         377 | 2
  44.         260 | 4
  45.         184 | 181
  46.         363 | 1
  47.         341 | 392
  48.          64 | 1
  49.         344 | 199271
  50.         235 | 17
  51.         294 | 755
  52.         352 | 3
  53.         368 | 1
  54.         225 | 1
  55.         199 | 8
  56.         374 | 2
  57.         248 | 8
  58.          84 | 1
  59.         362 | 1
  60.         361 | 331979
  61.         319 | 7
  62.         244 | 65
  63.         125 | 2
  64.         130 | 1
  65.         272 | 65
  66.          66 | 2
  67.         240 | 2
  68.         775 | 1
  69.         253 | 49
  70.          60 | 45
  71.         121 | 5
  72.         257 | 3
  73.         365 | 1
  74.          0 | 1
  75.         217 | 5
  76.         270 | 1
  77.         122 | 39
  78.          56 | 49
  79.         355 | 5
  80.         161 | 1
  81.         329 | 1
  82.         222 | 9
  83.         261 | 275
  84.          2 | 3816
  85.          57 | 19
  86.         307 | 4
  87.         310 | 8
  88.          97 | 37
  89.         202 | 20
  90.         203 | 3
  91.          85 | 1
  92.         375 | 641
  93.          58 | 98
  94.          1 | 6479
  95.          59 | 114
  96.         185 | 7
  97.         338 | 10
  98.         379 | 17
  99. (80 rows)
  100. postgres=# select FIELD2,count(*) from T_MPS_INFO group by FIELD2;
  101.  field2 | count 
  102. --------+--------
  103.         | 2297
  104.      6 | 469
  105.      2 | 320
  106.      1 | 11452
  107.      3 | 286
  108.      10 | 394
  109.      4 | 291
  110.      5 | 200497
  111.      9 | 331979
  112.      0 | 2
  113.      7 | 1178
  114. (11 rows)
  115. postgres=# select STATUS,count(*) from T_MPS_INFO group by STATUS;
  116.  status | count 
  117. --------+--------
  118.         | 2297
  119.      0 | 15002
  120.      3 | 5
  121.      4 | 1
  122.      1 | 531829
  123.      2 | 31
  124. (6 rows)

由于这几个字段的值分布极其不均的，我们构造下面这个lua脚本产生不同的select语句来模拟负载。
qx.lua:

点击(此处)折叠或打开

  1. pathtest = string.match(test, "(.*/)") or ""
  2. dofile(pathtest .. "common.lua")
  3. function thread_init(thread_id)
  4.    set_vars()
  5. end
  6. function event(thread_id)
  7.    local ATTRACT_TP,COLUMN_ID,FIELD2,STATUS
  8.    ATTRACT_TP = sb_rand_uniform(0, 10)
  9.    COLUMN_ID = sb_rand_uniform(1, 100)
  10.    FIELD2 = sb_rand_uniform(0, 10)
  11.    STATUS = sb_rand_uniform(0, 4)
  12.    rs = db_query("SELECT CASE WHEN gpppur.GB_BEGINDATE <= '2016-02-29 14:36:00' AND gpppur.GB_ENDDATE > '2016-02-29 14:36:00' THEN 1
  13.     WHEN gpppur.PREVIEW_BEGINDT <= '2016-02-29 14:36:00' AND gpppur.PREVIEW_ENDDT > '2016-02-29 14:36:00' THEN 2
  14.     ELSE 3 END AS flag,
  15.     gpppur.*
  16.     FROM T_MPS_INFO gpppur
  17.     WHERE gpppur.ATTRACT_TP = "..ATTRACT_TP.."
  18.    AND gpppur.COLUMN_ID = "..COLUMN_ID.."
  19.    AND gpppur.FIELD2 = "..FIELD2.."
  20.   AND gpppur.STATUS = "..STATUS.."
  21.   ORDER BY flag ASC,gpppur.PC_SORT_NUM ASC,gpppur.GB_BEGINDATE DESC
  22.   LIMIT 45")
  23. end

然后用sysbench进行压测，结果在32并发时测得的qps是64。

点击(此处)折叠或打开

  1. [root@rh6375Gt20150507 ~]# sysbench --db-driver=mysql --test=/opt/sysbench-0.5/sysbench/tests/db/qx.lua --mysql-db=test --mysql-user=mysql --mysql-password=mysql --mysql-host=srdsdevapp69 --num-threads=32 --max-time=5 run
  2. sysbench 0.5: multi-threaded system evaluation benchmark
  4. Running the test with following options:
  5. Number of threads: 32
  6. Random number generator seed is 0 and will be ignored
  9. Threads started!
  11. OLTP test statistics:
  12. queries performed:
  13. read: 825
  14. write: 0
  15. other: 0
  16. total: 825
  17. transactions: 0 (0.00 per sec.)
  18. read/write requests: 825 (64.20 per sec.)
  19. other operations: 0 (0.00 per sec.)
  20. ignored errors: 0 (0.00 per sec.)
  21. reconnects: 0 (0.00 per sec.)
  23. General statistics:
  24. total time: 12.8496s
  25. total number of events: 825
  26. total time taken by event execution: 399.6003s
  27. response time:
  28. min: 1.01ms
  29. avg: 484.36ms
  30. max: 12602.74ms
  31. approx. 95 percentile: 222.79ms
  33. Threads fairness:
  34. events (avg/stddev): 25.7812/24.12
  35. execution time (avg/stddev): 12.4875/0.23

4.2 优化后的查询

对于上面那个特定的SQL虽然我们可以通过建一个包含所有等值查询条件中4个字段(ATTRACT_TP,COLUMN_ID,FIELD2,STATUS)的组合索引进行优化，但是需要说明的是，这条SQL只是各种查询组合产生的1000多种不同SQL中的一个，每个SQL涉及的查询字段的组合是不一样的，我们不可能为每种组合都单独建一个多字段索引。
所以我们想到了PostgreSQL的gin索引。为了使用PostgreSQL的gin索引，先把MySQL的表定义，索引和数据原封不动的迁移到PostgreSQL。
在添加gin索引前，先做了一个测试。另人惊讶的是，还没有开始进行优化，PostgreSQL测出的性能已经是MySQL的5倍(335/64=5)了。

点击(此处)折叠或打开

  1. [root@rh6375Gt20150507 ~]# sysbench --db-driver=pgsql --test=/opt/sysbench-0.5/sysbench/tests/db/qx.lua --pgsql-db=postgres --pgsql-user=postgres --pgsql-password=postgres --pgsql-host=srdsdevapp69 --num-threads=32 --max-time=5 run
  2. sysbench 0.5: multi-threaded system evaluation benchmark
  3. Running the test with following options:
  4. Number of threads: 32
  5. Random number generator seed is 0 and will be ignored
  6. Threads 
  7. OLTP test statistics:
  8.     queries performed:
  9.         read: 1948
  10.         write: 0
  11.         other: 0
  12.         total: 1948
  13.     transactions: 0 (0.00 per sec.)
  14.     read/write requests: 1948 (335.52 per sec.)
  15.     other operations: 0 (0.00 per sec.)
  16.     ignored errors: 0 (0.00 per sec.)
  17.     reconnects: 0 (0.00 per sec.)
  18. General statistics:
  19.     total time: 5.8059s
  20.     total number of events: 1948
  21.     total time taken by event execution: 172.0538s
  22.     response time:
  23.          min: 0.90ms
  24.          avg: 88.32ms
  25.          max: 2885.69ms
  26.          approx. 95 percentile: 80.01ms
  27. Threads fairness:
  28.     events (avg/stddev): 60.8750/27.85
  29.     execution time (avg/stddev): 5.3767/0.29

下一步，添加gin索引。

点击(此处)折叠或打开

  1. postgres=# create extension btree_gin;
  2. CREATE EXTENSION
  3. postgres=# create index idx3 on t_mps_info using gin(attract_tp, column_id, field2, status);
  4. CREATE INDEX

再进行压测，测出的qps是5412，是MySQL的85倍(5412/64=85)。

点击(此处)折叠或打开

  1. [root@rh6375Gt20150507 ~]# sysbench --db-driver=pgsql --test=/opt/sysbench-0.5/sysbench/tests/db/qx.lua --pgsql-db=postgres --pgsql-user=postgres --pgsql-password=postgres --pgsql-host=srdsdevapp69 --num-threads=32 --max-time=5 run
  2. sysbench 0.5: multi-threaded system evaluation benchmark
  3. Running the test with following options:
  4. Number of threads: 32
  5. Random number generator seed is 0 and will be ignored
  6. Threads 
  7. OLTP test statistics:
  8.     queries performed:
  9.         read: 10000
  10.         write: 0
  11.         other: 0
  12.         total: 10000
  13.     transactions: 0 (0.00 per sec.)
  14.     read/write requests: 10000 (5412.80 per sec.)
  15.     other operations: 0 (0.00 per sec.)
  16.     ignored errors: 0 (0.00 per sec.)
  17.     reconnects: 0 (0.00 per sec.)
  18. General statistics:
  19.     total time: 1.8475s
  20.     total number of events: 10000
  21.     total time taken by event execution: 58.2706s
  22.     response time:
  23.          min: 0.95ms
  24.          avg: 5.83ms
  25.          max: 68.36ms
  26.          approx. 95 percentile: 9.42ms
  27. Threads fairness:
  28.     events (avg/stddev): 312.5000/47.80
  29.     execution time (avg/stddev): 1.8210/0.02

4.3 补充

作为对比，我们又在MySQL上添加了包含attract_tp, column_id, field2和status这4个字段的多字段索引，测出的qps是4000多，仍然不如PostgreSQL。可见业界广为流传的MySQL的简单查询性能优于PostgreSQL的说法不可信！(对于复杂查询PostgreSQL的性能大大优于MySQL应该是大家的共识。我例子中的SQL不能算是复杂查询吧？)

5. 总结

gin索引(还包括类似的gist,spgist索引)是PostgreSQL的一大特色，基于它可以挖掘出很多好玩的用法。对于本文提到的场景，有兴趣的同学可以把它和Oracle的bitmap索引以及基于搜索引擎(Elasticsearch，Solr等)的方案做个对比。另外，本人所知有限，如果有其它更好的方案，希望能让我知道。

时间： 2024-09-08 16:26:26

高并发低基数多字段任意组合查询的优化的相关文章

HTAP数据库 PostgreSQL 场景与性能测试之 20 - (OLAP) 用户画像圈人场景 - 多个字段任意组合条件筛选与透视

标签 PostgreSQL , HTAP , OLTP , OLAP , 场景与性能测试 背景 PostgreSQL是一个历史悠久的数据库,历史可以追溯到1973年,最早由2014计算机图灵奖得主,关系数据库的鼻祖Michael_Stonebraker 操刀设计,PostgreSQL具备与Oracle类似的功能.性能.架构以及稳定性. PostgreSQL社区的贡献者众多,来自全球各个行业,历经数年,PostgreSQL 每年发布一个大版本,以持久的生命力和稳定性著称. 2017年10月,Pos

PgSQL · 应用案例 · GIN索引在任意组合查询中的应用

背景 很多人小时候都有一个武侠梦,独孤求败更是金庸武侠小说里的一位传奇人物. 纵横江湖三十馀载,杀尽仇寇奸人,败尽英雄豪杰,天下更无抗手,无可奈何,惟隐居深谷,以雕为友. 呜呼,生平求一敌手而不可得,诚寂寥难堪也. 独孤老前辈的佩剑描写非常有意思,从使用的佩剑,可以看出一个人的武功修为. 第一柄是一柄青光闪闪的无名利剑.「凌厉刚猛,无坚不摧,弱冠前以之与河朔群雄争锋.」 第二柄是紫薇软剑,「三十岁前所用,误伤义士不祥,乃弃之深谷.」 第三柄是玄铁重剑,「重剑无锋,大巧不工,四十岁之前恃之横行天下

PostgreSQL 多字段任意组合搜索的性能

标签 PostgreSQL , 多字段搜索 , 任意字段搜索 背景 PostgreSQL 多字段,任意组合搜索,有三种优化手段: 1.gin索引(支持任意字段组合的查询) <宝剑赠英雄 - 任意组合字段等效查询, 探探PostgreSQL多列展开式B树 (GIN)> 2.bloom索引(支持任意只读组合的等值查询) <PostgreSQL 9.6 黑科技 bloom 算法索引,一个索引支撑任意列组合查询> 3.每个单列btree索引(支持任意字段组合的查询) <Postgre

Oracle高并发系列1：DML引起的常见问题及优化思路

作者介绍 王鹏冲,平安科技数据库技术专家,浸淫数据库行业十多年,对Oracle数据库有浓厚兴趣,也对MySQL.MongoDB.Redis等数据库有一定架构和运维经验,目前正沉迷在PostgreSQL数据库与Oracle数据库的PK之中,重点在关系型数据库的分布式架构研究. 引言    Oracle数据库是设计为一个高度共享的数据库,这里所说的"共享",可以从数据库共享内存.后台进程.cursor.执行计划.latch等方面去理解.Oracle如此设计的目的是以最小的系统开销.最大化地

多字段，任意组合条件查询(0建模) - 毫秒级实时圈人 实践

标签 PostgreSQL , 数组 , GIN索引 , 任意字段组合查询 , 圈人 , ToB分析型业务 , 建模 背景 你也许在一家ToB的数据分析公司,你可能设计了一张表(包括用户标识,及若干已经统计好的的属性值),你也许收集了一些用户的数据,你也许要为客户提供报表,你也许需要为客户提供任意属性值的组合查询,并快速的返回结果给用户. 这些需求应该是非常常见的ToB的数据平台公司的形态,头痛的问题无法建模,因为B端的需求无法捉摸,任意组合查询.要求实时响应. 你的客户数据也许有几十亿上百亿,

宝剑赠英雄 - 任意字段\条件等效查询, 探探PostgreSQL多列展开式B树

标签 PostgreSQL , 多列索引 , btree , gin , gist , brin , btree_gist , btree_gin , 复合索引 , composite index , 任意字段等效查询 背景 很多人小时候都有一个武侠梦,独孤求败更是金庸武侠小说里的一位传奇人物. 纵横江湖三十馀载,杀尽仇寇奸人,败尽英雄豪杰,天下更无抗手,无可奈何,惟隐居深谷,以雕为友. 呜呼,生平求一敌手而不可得,诚寂寥难堪也. 独孤老前辈的佩剑描写非常有意思,从使用的佩剑,可以看出一个人的武

Oracle高并发系列2：事务日志写入引发的Redo log风波

作者介绍 王鹏冲,平安科技数据库技术专家,浸淫数据库行业十多年,对Oracle数据库有浓厚兴趣,也对MySQL.MongoDB.Redis等数据库有一定架构和运维经验,目前正沉迷在PostgreSQL数据库与Oracle数据库的PK之中,重点在关系型数据库的分布式架构研究.   引言   关系型数据库强调事务的ACID特性,对于事务的持久性,主流的关系型数据库都是通过写事务日志来实现的.写数据是随机IO,写日志是顺序IO,常规的机械磁盘,随机IO比顺序IO要昂贵很多.所以虽然写日志同样要刷到磁盘

《设计模式》学习笔记5——单例模式【高并发拓展】

定义 单例模式又称为单件模式,这个模式大概是设计模式中最好理解的了,我起初就打算从这里开始学,甚至还记过另一篇单例模式学习的笔记. 但是之后跟着<设计模式>这本书系统的学,就索性从第一页开始,而单例模式算是复习,也算是再深入的理解一次. 之所以要这么做,是因为上一次写的没有给出更标准的定义,同时,当时只介绍了基础的懒汉式和饿汉式,对于并发时候的单例却没有涉及,所以这篇学习的重点应当在于高并发时如何保证我们的单例依旧是单例. 单例模式引用书中的定义如下: 单例模式(Singleton Patte

分享：外链数量忽高忽低甚至越发越少的原因

外链是我们做SEO的必需品,因为外链可以传递权重,而权重又是搜索引擎排名的依据.可是,一个问题总是困扰着我们:每天辛辛苦苦到各处发外链,如各大站长论坛,花的力气不小,发的帖子不少,可为什么外链数量忽高忽低甚至越发越少了呢?增高药优化者分析如下: 有的人可能会说发外链的地方的收录不好,所以,这就要求我们在选择站点发外链的时候,一定要查询一下这个网站的必要信息,如PR值,百度当天收录情况等等. PR值是对应谷歌来说的,理论上百度是用不着的,因为不同的搜索引擎会有不同的权重评判标准,由此产生了我们现在