分享人：digoal
正文：
所谓多维组合搜索,通俗一点来讲可以把它称为任意字段的组合查询，比如我们的table有很多位字段，有很多个属性的维度，我们的应用可能对这里面的若干属性或者是所有属性的任意组合都有查询的要求。
在这样的情况下,如果企业里面有dba，会对这一类查询非常的头痛。为什么呢？因为在数据库里面我们去做一个查询，它针对你的查询条件去创建索引，然后提升性能，这是非常通用的做法。如果你的这个查询在table里面是任意字段组合，这个时候几乎没有很好的优化方法，最后可能就会选择在每个字段上面都建索引。可能在数据库里面，他会选出一个过滤条件略微比较好的，再去针对某一个查询条件做过滤，其他的条件等这个索引过滤完之后再去做二次过滤，通过过滤其他的条件来提升性能。但是这个性能提升不是很明显，而且要求每个字段都得加一个索引。
所以的多维组合查询也是pg非常擅长的产品，它的解决方法或者优化方法非常的多，并且也具备了跟搜索引擎一样的倒排索引技术，去解决这种任意字段组合查询的业务场景诉求。
那我们今天的内容的话呢会分为四块：
l 任意字段组合查询
l 索引结构和原理
l 数据扫描方法
l 应用实践
一、 任意字段组合查询
任意字段组合查询就像我们刚刚讲的，比如一个这样的查询，x=? and y=? and z>=? or (a=? and b=?) 等等，这里面其实条件它可能是任意的，比如在一些erp系统里面，为了提升产品的竞争力，可能会面向不同的用户，会开种定制化的需求。开放定制化的需求后，不同的行业，不同的用户的诉求可能是千变万化的，就会导致不同的用户甚至同一个用户在不同的时间段，他要搜索的数据维度也是不一样的。所以最后发送到数据库里的请求可能就会变成图中左边的样子，非常的凌乱，或者是没有章程导致在数据库里面很难去做这样的优化。
另外还有一项搜索类的业务，你肯定也不能限定说今天只允许你搜哪几个字段，并且只允许哪几个组合？从功能角度来讲，它就没有什么产品竞争力了。
最后像拖拽式的分析系统也是使用任意维度过滤的一个很典型的业务场景。
1）加速思路
加速思路
针对这样的业务场景有什么样的加速的思路呢？
在数据库里对一个sql的本身，我们要去做加速的话有以下几个思路：
第一，让他扫描最少的索引块，比如这个查询用到了索引扫描，索引是10 g的，那么你一次扫描怎么能够做到访问最少的索引块？比如刚刚说的一个索引1g，这个查询可能访问10个数据块，10个索引的数据块就能找到你要的结果，他也可能访问100个数据块，那么怎么让它访问最少的数据块。这样避免了索引的IO。
第二，最后查询要回表时，怎么让它做到扫描最少的表的数据库，这也是一个非常核心的要点。
第三，过滤最少的不符合条件的记录。比如一个查询，就像我们刚刚说的这个查询x=? and y=? and z>=? or (a=? and b=?) ... ... -- 任意组合，我们有可能在x这个字段上面命中索引，那么剩下的这些条件是不是就无法命中索引呢？比如x条件命中了最后一个表里面， 1000万条记录命中了100万条，加上这其他的条件，最后满足条件的只有一条，那也就意味着说999999条记录都得在y=? and z>=? or (a=? and b=?)里面去做过滤，所以它走的不是索引。因此我们要尽量的避免索引以外的过滤，最好能够在索引里面就直接全部过滤掉。
第四，要尽量避免对大量的记录进行排序。有一些查询如order by c,d desc，如果结果集很小，那可能order by很快；如果结果集特别大，比如结果集上亿，然后order by，去倒排，去取出你要的结果，这个时候可能就得想一想是不是把排序这个动作放在索引里面去做？
那么核心是什么？对于索引来说，最核心的东西是两块，一块是数据组织结构，另外一块是存储结构。对于表来说，它的存储的组织结构，如索引有betree索引，哈希索引、bitmap索引等等；表有堆表。我们查询的时候，比如你要做一个范围查询，命中大量的数据，那么表的这些数据组织形式跟上面我们提到的怎么让它访问最少的表的数据块就形成联系了。如果你要访问的这个范围的数据密集的存在某一些数据块里面，访问的数据块就比较少；如果你要访问的这些数据，它会离散的落在很多个数据块里面，那么虽然索引命中了，但是最后回表时也要访问很多个数据块。
所以核心有三块，索引的数据结构，索引的存储组织和表的存储组织。
对于一个数据库来说，我们要去优化它的这个几个方法，在pg里面刚好都有，这些东西都有对应的场景的优化手段或者有对应的特性来去支撑它。
二、 索引结构和原理
在pg里内置有八种索引，当然它还可以扩展索引，就像阿里的rds扩展了两种向量索引，所以总共是支持十种索引，
1）btree索引结构
btree索引是最简单的，实际上在pg里面它是一个分层结构。
第一个数据页叫meta页也叫原数据页，原数据页里面有一个重要的信息，即这个索引是几层结构，同时它会告诉你根页就是你存根的页在哪里，在你这个索引里面第几个配置。
我们这个是一个四层结构，从根到叶子节点的四层结构。在mate page里就会告诉你，这是个四层结构的索引。在每一层不同的配置之间是一个双向的链表，。一个索引页默认是8k，这个是在我们数字化数据库的时候决定的，在rds里面也是考虑到通用性，我们选择了8k的block。如果一个索引页可以存下285条记录，那么像这样一个4层结构它能存285的四次方，很多很多条记录。所以对于一个索引来说，我们之前就有做过这样的测试，在一个表里面存下1万亿条记录，这个表已经到120 tb了，我们通过索引去访问也只需要扫描几个数据块就能够命中所要的记录。
然后我们去搜索一条记录时，它走的是mate page到root，再根据你的查询条件会路由到对应的branch，去找到leaf节点，然后再回到堆表去找你要的数据。
2)gin索引结构
Gin是个重要的索引，也叫倒排索引。所谓倒排索引，它会用在多值列，比如我们有讲过数组类型，一个值里面有好多个元素；再比如用户画像系统，我们可以给用户定义标签，那么一个用户身上可能有很多个标签，这个标签我们用数值来代表，也就意味着一个用户身上可能在一个数组，里面有很多很多的标签，我们创建索引的时候用到的就是这个数组的倒排索引。
那么倒排索引——倒排树长什么样子呢？
原来我们创建一个普通的btree索引， key即字段的值，每一行的字段值，在倒排索引里面key的值是一个多值列，比如说一个数组里面的某一个元素的值，或者标签=1有100条记录，那么在倒排树里面k=1这个point，就会存储这100行的行号，这100行的行号会连着存在在一起,它可能是一棵树，也可能是一个post list。查询时比如要查询包含1的记录有哪些？实际上就是在这个树里面找到了这个行号post list，然后回表就直接把这100条记录返回给你，这就是倒排树。
那么倒排树除了能用在多值列里面，它也能够一次创建多列的值，比如abcde有好多列，可以针对这些列去创建一个gin的倒排索引，这个时候你在这里面不管用任何的组合查询都会命中gin索引。比如你有10个字段，用这10个字段去创建了一个倒排索引，然后这10个字段里面不管怎么组合，你是查10个字段，查9个字段还是查8个字段，都不需要驱动链因为跟驱动链没有关系，任意一个字段去查都可以命中这个索引，而且效率非常的高。
原因在哪里？在于它存储的是每一个字段作为一个元素，去查询它包含这个元素的值有哪一些，就是它的行号有哪些。当我们查询若干个时，实际上就是在这棵树里面命中了几次，然后做一下位图的合并， post list行号合并之后再回表把结果返回出来，所以它的效率就非常的高。
gin的索引结构我们刚才已经看过了，在pg的官网文档里面也提到了索引结构,跟我们刚才提到的结构就是一样的。那么什么是pendinglist？
因为它是个倒排，我们写入一个value时，有可能在这个索引里面会对应到好多个key，所以一次性会更新很多个key，那也就意味着对于创建了倒排索引的表，我们去写入记录、去更新记录的时候，如果是做索引的同步更新，就会发现一个问题，就是它可能会放大，因为一条记录可能在这个索引里面会对应很多个page，很多个配置，所以就导致本来插入一条记录只需要去修改一个页面，但是创建倒排索引之后，插入一条记录可能要修改很多个页面，因为倒排树里面涉及到多个page。
为了解决这个问题，倒排索引支持pending list这样的一个优化，也就是说你的数据会先写到pending list里面，然后会由后台的进程把pending list里面的内容增量的合并到树里面去。当还没有合完的时候，我们如果查询，它会把pending lis里面的数据和倒排树里面两边的数据合并起来再返回给你，所以如果pending lis里面存在大量的list内容，查询性能可能会受到影响。当然它在后台一直都在做质量的合并，因为有参数可以控制好。
我们可以观察这个倒排索引的内容，比如图中红色方框处，实际上在我们倒排树里面的某一个索引的记录对应到的表里面的记录有哪些？比如蓝色方框这条记录，对应到索引里面是5条记录，那也就印证了我们刚刚说的在倒排树里面一个key对应多个value，每个value都是一个行号。
3）rum索引结构
rum索引结构是一个扩展的索引，实际上是扩展的倒排。我们知道倒排索引里有叶子节点，叶子节点里面应该叫只有一部分内容，这个内容就是我们的多值列元素对应的表里的行号，就是回表之后表里面的行号。
实际上这里会有一个问题，当我们要去查询的数据，比如除了查数组包含某一个元素以外，还要查另外一个字段的值，比如时间戳，我要按时间戳去排序，包含某一个元素=1同时要按照时间戳去做一个排序，并且只返回最新的那一条，那么这个时候用那个倒排索引就必须回表，把所有的记录全部都找到之后然后做排序，再去过滤出那一条你要的记录。而在rum索引里面，叶子节点里面会多存一个东西，回表后每一个行号后面会跟一个addinfo，你就可以把时间戳字段的值放进来，也就是说比如满足条件的iptr1这条记录，这条表里面记录它的时间是addinf1；另外一条ptr2记录的时间是什么？第三条ptr3记录时间是什么？由于有了additional info我们就不需要回表了，可以直接在rum索引里面完成过滤，而且是按顺序排的，即字段additional info可以指定顺序。
实际上它就解决了倒排索引里面只有元素对应的物理行号没有额外的其他字段属性的带来的一定要回表的问题，所以你可以理解为它是一个高级倒排索引。
比如下面这个例子:
这是一个全文检索，包含beautiful或者place两个单词的记录有哪一些？并且要order by，按照rank来去做排序。那么像这一类查询，我们就可以用rum索引去做加速。
在这里可以看得到它的执行是用rum索引。
4)hash索引结构
哈希索引用的是哈希桶去做区分布存储，所以哈希索引是广泛应用于比如我们的字段制做等值查询如文本或者是字符串的等值查询。
如果我们要用btree索引，当然也可以实现同样的场景，但是它会有一个问题，btree索引的key存的是原始值，一个字符串就有可能很长，就会导致btree很大。哈希索引存的不是原始值，它存的是原始值转换成的哈希value。哈希value是一个固定长度的值，所以不管字符串有多长，在哈希索引里面的长度都是有限的且比较小的，而且它的查询效率也是非常高的，包括更新的效率其实也是很高的。因为在pg里面它用了哈希mapping的方法做平滑的bucket的扩展，我们知道当扩展bucket的时候就会涉及到可能把一个pupil从一个bucket移动到另外一个bucket,这样会导致移动的成本包括分裂的成本。这个数据库里面内部已经做了优化了，所以就不存在这个问题。
5)gist索引结构
另外pg还支持了类似于R-tree Indexes bounding box数据分布的索引。它广泛应用在空间类的数据，比如point，polygon或者是经纬度的点等等。
它的搜索支持的是基于空间位置的距离的搜索,包括用户画像里pase的那个插件。
除了那个pase插件以外，还有图像识别的场景。实际上图像识别场景也是向量查询，那么它用的也是这种索引。所以gist索引用在空间类型，范围类型,向量类型。
6）spgist索引结构
spgist实际上就是一个空间分区通用的索引结构。你可以认为是每一个叶子节点，它的层次都是一样的。你访问任何一个目标点，在索引里面搜索的层次是完全一样的，而在这个sp里面访问某一些点，可能要搜索的更深一点。访问另外一些点可能搜索的更快。
实际上它就是一个不平衡的二叉树，它解决的问题就是当你的数据分布非常的不均匀的时候，没有办法做到均衡的切分时，就可以使用它。比如在范围类型这种可能出现不均衡的数据分布的时候，我们可以用spgist这样的索引。
7)brin索引结构
brin是一个范围索引，比如我们在表里面存了一段时序类的数据。
如轨迹数据，那么这个轨迹数据有一个字段是时间字段，就你的轨迹是哪个时间点的,比如我们骑自行车，上传骑的单车轨迹，这个轨迹会有很多个点组成，每一个点会包括经纬度，什么时间到达的这个点，会有时间字段。
而且它是怎么存进去的呢？它是按时间的维度，然后一直apend进去，所以它的数据分布就是数据的某一些数据块，比如在你的堆表里面，你的这个数据块里面的数据,数据块与数据块之间是非常清晰的。比如1号数据块存的可能是早上9点~9:01的,2号数据块可能就是9:01~9:02，也就是说它的据本身的物理存储以及它的时间戳的value，它们两者的线性相关性是趋近于1的。所以当我们去创建这个索引或者是当我们要查询一个范围的数据的时候，这个表里面的数据是挨在一起分布的，就可以用这种索引。
范围索引跟btree索引不一样的地方在于它的value存的是以数据块为单位的， btree索引里面存的是以记录为单位，就是按照记录上面的值去构建这个数。而在brin里面是按照一些连续的数据块，比如最小单位是一个数据块，或者你可以创建索引的时候指定，比如默认128个数据块，每连续128个数据块，在这些数据块里面，你要去创建的那个字段，它在这些数据块里面的最小值是什么？最大值是什么？所以当我们针对一个时序类的数据表去创建时间戳的索引时，我们就可以用brin。比如你告诉我要查某一个时间段的数据时，它就会告诉你，你要的这个时间段的数据是在这个表里面的哪些数据块里面,可以快速的反馈给你，并且这个索引特别小，所以它适用时序类的数据，适用于创建这个字段的数据分布非常清晰的业务场景。
那么同样的在比如oracle一体机里面，它也是有类似的索引。那么在我们这个rdspg里面也支持这样的索引，特别适合于持续类的数据。
8）bloom索引结构
bloomfilter也是一个可以广泛应用于各个字段的组合的等值查询的业务场景。比如我们有i1、i2、i3这三个字段，任意字段组合起来去做等值查询，那我们就可以用bloom filter。
我们可以来看一下bloomfilter的原理：
实际上它存的是一个哈希之后映射到了这个比特位上面的比特值，比如我的一条记录对应的是一个bitmap，这个bitmap的长度是80，那么也就意味着有80个比特位。当这条记录写进来的时候，它会针对每一个创建了索引的这个字段在bloomfilter里面，比如说xyz三个字段加w四个字段创建了索引的时候，我们会把x的值通过一个哈希函数映射到这个比特位的位置上面去，并且把这个比特位的位置设为1。再比如一个字符串,经过哈希函数之后转换映射到了四个比特位，那么它这里面就会找到对应的那个四个比特位，把它设成1；y那个字段的值也是一样的，经过哈希函数之后它也会映射几个字段出来，映射几个比特位的位置出来，然后把这些位置设为1。当我们查询的时候，它同样的也会把你要查的这个字段的条件内容也通过一个哈希函数转换到一个比特位上面，比如说转换到了这几个比特(红色方框处)，这个w是我要查的，那么这几个比特位都是1的，就表示有满足我要的条件的记录；如果这几个比特位里面其中有任何一个不是1，那么就表示我要的这条记录在这个索引的对应的记录上面没有我要的值。所以它是loser的一个索引，就是说当查我们要的记录时，它告诉你不对的时候，那就一定不对。它告诉你对的，就是有你要的结果的时候，有可能你最后去查这个表时这条记录却不是你要的， 然后你再去做二次filter。
为什么会出现这种情况？因为我们的比特位是有限的，哈希函数有可能当我们创建三个字段的联合索引， x虽然没有命中，但是y有可能其中有一个比特跟x那个值映射的那个比特位冲撞了，冲撞之后就有可能虽然x我们没有设为1，但是y对应的这条记录的字段值设为1了，那么有时候当我们来查x的时候实际上它也会把其中可能存在重叠的记录返回给你，因为把y设为1了=x的值。那么这个时候我们来查x=？的时候，它也会把这条记录对应的行号返回给你，最后我们再做二次过滤，把不要的结果给过滤掉。
bloomfilter特别适合我们要搜索大量的记录，去做任意字段的等值过滤的业务场景，大家注意是等值。
9） 其他索引结构
那其他还是很多的索引结构，我们就不一一再讲了，就是说我们讲了一些非常常用的索引结构。
三、数据扫描方法
1) 扫描方法介绍
扫描方法包括全表扫描seqscan，索引index only扫描，还包括bitmap扫描跟行号扫描ctid scan。
l Seqcan
全表扫描比较简单，就从头扫到尾。那么就等于是整张表都得扫，没有索引的情况下才会用全表扫描。
l index only scan
当我们扫描这个索引的时候，它不需要回表，就是说我们要的这个记录在索引里面已经全部包含了，并且这条记录一定对你是可见的，所以就不用回表。判断这条记录对你是不是可见的，取决于你的隔离级别，当前你的这个数据块上面有没有脏页。如果这个数据块上面有脏页，那就必须要回表看一下这个版本号是不是我当前要查询的那个版本？这就是index only scan。
l index scan
index only scan跟index scan唯一的差别就是index only scan的时候它会先判断一下VM的page是不是干净。如果是干净的就不回表，有脏业它就回表。index scan在任何情况下都回表。
l index skip scan
index skip scan目前在pg里面没有支持，但是我们通过递归查询可以做到比如不是驱动列的btree扫描去做补齐。
l Bitmap scan
当我们去查询多个条件的时候或者当我们查询一个条件但是要返回大量的记录的时候，因为每一条记录可能都会回表，这个数据是按索引的顺序组织的，但是在表里面它可能是乱序的。它的信息相关性如果很差，那每一次回表都会访问不同的数据块，就有可能会有数据的换进换出，就会导致性能下降。
为了避免多次回表的问题，在pg里面我们就支持了位图扫描，位图扫描就是说在扫描的时候，先对目标的物理行号的数据块id做一下排序，按顺序去扫描。然后扫描完之后重新做check， check你这条记录是不是满足条件。
那么除了用在消除重复的读heap以外，它还可以用来干嘛呢？基于位图索引，扫描索引之后我们就能够拿到目标表的数据快的id去做排序，排序之后的内容可以做一下block id，基于block id再去做扫描。所以它是一个排序扫描，就是按照堆表的block id做排序扫描。
位图扫描用来消除回表时候的io放大，同时它还可以用来做什么呢？
我们来看下下面的例子，它还可以用来做多个索引的合并扫描。
当有多个索引联合扫描的时候，我们能够拿到目标表的数据块id，它在扫描的时候会根据这个数据块的id去做位图的计算。比如一个and条件，那么也就意味着当我的其中一个索引命中，另外一个索引没有命中的时候，它可以不用回表，因为它会对这个位图进行end操作；如果是一个or条件，那么它的这个位图的操作就是一个or位图的bit的计算了来消除这种一定只能查单个索引的这种情况，就是说它可以做多个索引的合并.
四）应用实践
下面我们来讲一下应用的实践，这里讲到了一些场景。
1）任意字段组合查询设计1
任意字段组合查询会涉及几种场景：
l 我们有等值查询，范围查询，排序的字段，像这种情况我们要用用btree索引。
l 对于空间查询和范围字段的查询我们用的是gist索引.
l 对于多值列、全文检索、jason、模糊查询字段等等，我们用的是gin倒排索引。
针对不同的字段的属性，每一个字段都加一个索引这是第一种设计方法。查询时数据库会自动选择bitma index scan或者index scan。
第一种设计方法最简单，每个字段都创建一个索引。
2）任意字段组合查询设计2
第二种设计方法我们可以使用字典化的方法，把所有要查询的、要组合查询的字段全部揉到一起，放到一个索引里面去，这个索引叫倒排索引或者联合索引。
其他条件不满足倒排索引的或者联合索引，因为这种只有等值查询，它只支持等值，包含、相交这一类查询。
其他像排序、范围大于等于小于等查询都不支持gin索引或者rum索引。
所以非等值查询列选择以下索引：
l 范围、排序字段：btree
l 空间、范围字段：gist
l 多值列、全文检索、json、模糊查询字段：gin
3）任意字段组合查询设计3
第三种设计方法和第一种、第二种设计方法类似，只不过我们把下面这些全部消除掉。怎么消除的呢？把没连续化的范围的操作数组化，或者叫离散化，查询的思路就是离散化的思路。那这个时候你就只需要使用一种索引，rum或者倒排索引。
4）任意字段组合查询设计4
第四个第三个其实是一样的，两种方法：一种是字典化的离散，一种是加前缀的离散加字段名前缀。
5）例子
下面的例子可通过网址进行详细了解，这里就不再一一赘述。
l PostgreSQL 任意字段组合查询 - 含128字段，1亿记录，任意组 合查询
l 大宽表任意字段组合查询索引如何选择(btree, gin, rum)
l ADHoc(任意字段组合)查询(rums索引加速) - 非字典化，普通、 数组等组合字段生成新数组
l ADHoc(任意字段组合)查询 与 字典化 (rum索引加速)
l 空间应用 - 高并发空间位置更新、多属性KNN搜索并测（含空间 索引）末端配送、新零售类项目
