433
多字段，任意组合条件查询(0建模) - 毫秒级实时圈人 实践
标签
PostgreSQL , 数组 , GIN索引 , 任意字段组合查询 , 圈人 , ToB分析型业务 , 建模
背景
你也许在一家ToB的数据分析公司，你可能设计了一张表（包括用户标识，及若干已经统计好的的属性值），你也许收集了一些用户的数据，你也许要为客户提供报表，你也许需要为客户提供任意属性值的组合查询，并快速的返回结果给用户。
这些需求应该是非常常见的ToB的数据平台公司的形态，头痛的问题无法建模，因为B端的需求无法捉摸，任意组合查询、要求实时响应。
你的客户数据也许有几十亿上百亿，客户数据也许有几百个属性，用户可能需要的是任意属性组合的结果。
如果要快速响应，你的第一反应是不是对查询条件建立索引呢？
比如
where col1=? and col2=? and col3<>? or col4=?;
这样的SQL，你准备怎么做到实时响应呢？(col1,col2)建立索引，col4建立索引，这样是吗？
但是用户下次的请求肯又换条件了
where col3=1 or col100=?
是不是又要建col3, col100的索引呢？
你会发现根本没有办法优化，因为对应查询的索引组合可能是成千上万的。
PostgreSQL 对付任意字段检索的黑科技
我在之前写过一些关于任意字段查询的实践文章，广泛应用于广告营销平台的圈人，ToB的圈人，前端页面的任意组合筛选等场景。
方法1，GIN复合索引
对需要参与查询的字段，建立GIN的复合索引。
CASE如下：
《任意组合字段等效查询, 探探PostgreSQL多列展开式B树 (GIN)》
这个场景针对任意字段匹配的场景，PostgreSQL对于多个查询条件，内部会使用索引+bitmapAnd或bitmapOr来筛选BLOCK，得到中间结果。
+---------------------------------------------+
|100000000001000000010000000000000111100000000| bitmap 1
|000001000001000100010000000001000010000000010| bitmap 2
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
|000000000001000000010000000000000010000000000| Combined bitmap
+-----------+-------+--------------+----------+
| | |
v v v
Used to scan the heap only for matching pages:
+---------------------------------------------+
|___________X_______X______________X__________|
+---------------------------------------------+
这种方法为什么快呢？
原因是GIN索引实现了内部bitmapAnd or bitmapOr，实际上等效于对每个字段建立单独的B-Tree索引（PostgreSQL对多个B-Tree索引也支持bitmapAnd, bitmapOr的合并）。
bitmapand,or原理如下：
《PostgreSQL bitmapAnd, bitmapOr, bitmap index scan, bitmap heap scan》
GIN的复合索引这种方法可以满足以上需求，但是，当数据量非常庞大或者列非常多时，GIN索引会比较大。
方法1 优化技巧
建议可以拆成多张表（例如随机拆分，或者按强制条件拆分）。降低GIN索引的大小，同时还可以利用PostgreSQL 10的多表并行特性，提升查询性能。
PostgreSQL并行计算特性
PostgreSQL支持单表多核并行，也支持多表的并行查询
单表并行，指一条SQL，在处理单张表的数据时，可以使用多个CPU进行运算。
多表并行，指的是一条SQL涉及到多张表的处理（例如APPEND SCAN）时，可以并行的处理多个表的SCAN。
多表并行是在PG 10版本加入的，PostgreSQL 10 append scan 并行
《PostgreSQL 10.0 preview sharding增强 - 支持Append节点并行》
方法2，行级全文检索
将整行记录转换为一个大大的字符串，然后对整行记录建立全文索引（PostgreSQL内置了全文索引的功能），搜索时即覆盖了任意字段任意匹配的场景。
《PostgreSQL 如何高效解决 按任意字段分词检索的问题 - case 1》
此方法适用于不限定列，但是限定查询条件的场景。
比如搜索 迪奥香水 ， 可以在表的任意字段匹配，（例如 店铺名字、商品名字、用户名字）。
方法3，bloom过滤
bloom方法过滤的效果有限，目前算是一种预览特性，建议观察使用。
《PostgreSQL 9.6 黑科技 bloom 算法索引，一个索引支撑任意列组合查询》
方法4，数组化（同类应用 1 - 电商圈人）
每个用户对应若干个标签，商家根据标签的组合筛选人群。这是广告商的惯用手法。
主要利用了PostgreSQL的数组类型、倒排索引，性能也是杠杠的。
《万亿级营销(圈人)潇洒的迈入毫秒时代 - 万亿user_tags级实时推荐系统数据库设计》
这种方法为什么快呢？
它采用了ARRAY元素倒排的方法，在查询时，对查询条件进行块级BITMAP筛选，筛选后的数据落到少量的数据块，再进行recheck选出最终结果。
本案例（多字段，任意组合条件 毫秒级实时圈人） 方法4 实践
实际上文章开头提到的场景，和电商圈人非常相似，所以也能使用电商圈人的方法。
怎么实现呢？
1 多个字段转换为数组
首先，将多个字段，转换为一个数组字段。
例如
create table test(uid int8 primary key, tag1 int, tag2 text, tag3 int, tag4 text, tag5 timestamp, tag6 date, ...);
转换为
create table test(uid int8 primary key, tag text[]);
例子
1, 1, 'man', 1023, 'football', '2017-01-01 10:00:00', '1989-09-01'
转换为
1, array['tag1:1', 'tag2:man', 'tag3:1023', 'tag4:football', 'tag5:...', tag6:...']
2 阶梯化（可选）
如果查询中包含 =， <> 以外的查询（如某些字段为年龄、销售额、收入等，那么可能有大于，小于的范围查询需求），那么我们需要阶梯化对应TAG的VALUE，阶梯化的方法请参考
《恭迎万亿级营销(圈人)潇洒的迈入毫秒时代 - 万亿user_tags级实时推荐系统数据库设计》
3 拆表（可选）
拆表的目的是并行，保持每个表的体量。
拆表的方法很多，可以随机，可以按UID进行哈希。
拆表后，扫描所有的分区表，聚合结果即可。
拆表可以是本地拆分、也可以是跨库拆分。本地拆分，实际上就是分区表。跨库拆分则涉及到数据分发、聚合的过程。
跨库分发和聚合的方法也很多：例如postgres_fdw+pg_pathman, plproxy, 程序实现等方法。请参考如下文档
《PostgreSQL 9.6 sharding based on FDW & pg_pathman》
《PostgreSQL 最佳实践 - 水平分库(基于plproxy)》
《阿里云ApsaraDB RDS for PostgreSQL 最佳实践 - 2 教你RDS PG的水平分库》
《阿里云ApsaraDB RDS for PostgreSQL 最佳实践 - 3 水平分库 vs 单机 性能》
《阿里云ApsaraDB RDS for PostgreSQL 最佳实践 - 4 水平分库 之 节点扩展》
4 建立数组GIN索引
对数组字段建立GIN索引，建立GIN索引实际上就是倒排索引，数组元素作为KEY，行号作为VALUE的B树。
例如搜索包含某个TAG的用户，从GIN索引得到HEAP表行号，然后获取记录即可，速度非常快。
多个TAG组合查询时，内部进行BITMAP and/or的合并，过滤到数据块级别，然后通过数据块获取记录，通过查询条件FILTER，得到最终结果，速度也非常快。
关于GIN，多个TAG组合查询的原理，可以参考这篇文档。
《电商内容去重\内容筛选应用(实时识别转载\盗图\侵权?) - 文本、图片集、商品集、数组相似判定的优化和索引技术》
5 圈人 <=> 数组组合查询
将多个字段数组化后，圈人就变成了数组的操作，例如
where tag1=? and tag2=? or tag3=?
转换为数组操作如下：
where arraycol @> array[tag1:?, tag2:?] or arraycol && [tag3:?]
数组查询会走GIN索引扫描，速度快得惊人。
方法5，bitmap化（同类应用 2 - 圈人(基于阿里云 RDS PostgreSQL varbitx)）
这个用到的是bit的方法，当所有属性的VALUE可以被穷举时，例如可以穷举到100万或者多少，那么我们可以使用这样的方法来优化圈人的应用。
BIT相比数组的方法，BIT空间下降25倍左右，性能稳定。
但是BIT方法要求数据的写入是合并式的，最好使用UDF完成，实际案例如下（包含数据合并的DEMO代码）。
《阿里云RDS for PostgreSQL varbitx插件与实时画像应用场景介绍》
《基于 阿里云 RDS PostgreSQL 打造实时用户画像推荐系统》
varbitx这种方法与bitmap数据库pilosa如出一辙，但是PG有更强大的功能背景，推荐使用PG。
https://www.pilosa.com/docs/introduction/
小结
在PostgreSQL中，圈人业务场景的优化方法非常多，得益于PostgreSQL强大的功能。下面小结一下每一种方法，
1. gin 复合索引，对需要参与查询的列，构建GIN复合索引即可。PostgreSQL内部会对GIN的多个条件使用bitmapAnd, bitmapOr进行合并。
这种方法的使用最为简便，但是当数据量或列非常多时，GIN索引会很大，GIN索引很大带来一个问题，建立索引的速度较慢，将来维护索引的速度也较慢。
使用这种方法，建议对表进行本地分区、或者垮库分区，将单表的数据量降低。(多列展开后的记录数建议在1亿左右，例如10列，则单表记录数控制在1000万)（经验值，随着硬件发展，以后可能更多）
同时GIN建议使用fastupdate和延迟合并的特性，加速插入、删除、更新操作。
2. 独立B-tree索引，需要参与查询的列，每列单独建立B-Tree索引(或者对应类型的其他索引例如brin, gin, gist, sp-gist, hash)，PostgreSQL内部会对多个索引查询的结果使用bitmapAnd, bitmapOr进行合并。
这种方法使用也非常便捷，使用这种方法，建议对表进行本地分区、或者垮库分区，将单表的数据量降低。单表记录数建议控制在1亿左右（经验值，随着硬件发展，以后可能更多）。
3. 数组化+GIN，类似与电商的圈人场景，查询时使用数组的包含，相交操作符，实现索引检索。
这种方法特别适合于已经构建好标签（使用PostgreSQL数组）的场景，直接使用数组索引、数组的操作即可实现圈人。
万亿user_tags级，毫秒响应。
《恭迎万亿级营销(圈人)潇洒的迈入毫秒时代 - 万亿user_tags级实时推荐系统数据库设计》
4. bit化，当标签可以穷举时，可以将标签作为KEY，将USERID作为bit进行存储，使用BIT的方法相比ARRAY，空间需求下降25倍，效率可以保持平稳。
这种方法将用户和标签做了一次倒转，好处很明显，支持任意组合的高效圈人。但是比较烧脑，也需要更多的开发工作量（这部分已经有UDF DEMO）。
建议
1. 省钱、高效、不怕烧脑
bit化。
2. 有钱、高效、能折腾
数组化+GIN
3. 有钱、高效、不能折腾
独立B-Tree， GIN复合索引
最后更新：2017-06-08 11:32:06