前言
大数据发展至今，各大公司的数据量已经是非常庞大了，虽然通用计算框架Spark/Presto等已经能满足用户的很多查询需求，但是更快的查询还是大家向往的。OLAP框架Doris/StarRocks/Clickhouse等在业界已经很火了，虽然有着非常强的计算层，但是在存储层的优化也是非常多的，不仅有特殊的编码、压缩还有一大堆的可配置索引，例如BitMap/HLL维度类型可以快速的计算去重的场景等，ZSTD算法等极致压缩，倒排索引点查等等。
当然各个数仓引擎也会去做预计算，毕竟数据算完放在那里直接查当然是更快的，但是成本也不低，目前业界的物化视图功能基本上都是基于论文《Optimizing Queries Using Materialized Views: A Practical, Scalable Solution》实现的。
从存储层看，索引、缓存、物化视图都可以提供加速，也有很多团队在尝试使用自适应算法来生成，本文详细描述了各类主流的索引与预计算技术，让大家有个宏观的认知，本文提到的数据都为二维行列模型。
索引
排序索引
图1 排序索引对表里的几列进行排序，就可以获得O(lgn)的搜索效率，可以在范围查询时性能得到很好的提升；在很多列式存储的数据库引擎中还会进行稀疏索引，因为列式存储本来就有块（block）的概念，那么我们可以根据用户需要查询的范围快速定位到对应上下界的块（block），然后读取范围内所有的块（block）内找到符合条件的行，将结果返回。
一般类LSM的存储引擎例如Hbase，Clickhouse等都会使用排序索引，通过后台线程的compaction来合并小文件，最后可以剩下几个有序的大文件，在查询时速度可以得到保证。
当然数据在写入时进行排序肯定会影响数据的写入性能，如果业务场景完全没有扫描的需求，也可以不排序写入，减少写入性能的损耗，例如一下倒排索引也可以compaction，但是数据可以不进行排序。
倒排索引
图2 倒排索引倒排索引一般是针对搜索场景，对表里的列做倒排，那么就可以根据某几列的值，快速定位到对应的行，然后将对应的行读取返回，搜索性能可以到O(1)。在进行排序索引后，把没有索引的列进行倒排也是业界常用的一个方案，这样在过滤没有索引的列时，可以不用扫全表，对查询性能也有很大的提升，可以参考Apache Druid等引擎。
业界基于Lucene的知名查询引擎ES就是主要基于倒排索引实现的，基于倒排还会做很多优化，例如对拆出来的分词加排序索引优化范围查询，做hash索引提升点查性能等。
同样，倒排索引的生成对数据的写入吞吐影响也是比较大，许多基于倒排存储引擎的数据库产品的数据可见性都是分钟级。
哈希索引
图3 哈希索引哈希索引可能是我们日常最长接触到的一个索引了，主要解决我们快速定位到某个值的映射关系，哈希算法的碰撞率对查询性能的影响是比较大的。
业界场景的哈希索引BitMap、BloomFilter、HashMap，字典等等。
在大数据领域，可能是在对某一列做字典时（位索引），会直接使用。
B 树索引
图4 B 树其实B 树和排序索引还是有一些类似的，只是不需要对原始数据进行排序，在查询命中索引树之后，会找到对应的行把数据读取出来。
目前B 树一般用在TP型数据库，对查询少量在磁盘上的数据还是比较有优势的。
在大数据领域还是很少使用B 树的，大部分场景都是在写入时进行排序，当前Hudi 有实现在数据写入时，分区分桶后的Block数据进行B 树索引，主要解决点查场景。
地理信息索引
图5 基于希伯特空间曲线的索引在涉及到多个维度的同时进行过滤时，大概率是要对全量数据进行扫描的，当然我们可以基于倒排来解决一部分问题，但是在高基数（连续值）场景的范围过滤还是比较头疼，那么我们可以使用GEO索引。
目前PG数据库对GEO索引支持的比较好，还有数据湖框架Hudi/Iceberg等也实实现了Zoder等进行多列过滤。
大数据领域在解决多列过滤的场景，有很大概率会考虑使用该索引来减少数据扫描。
预计算
上卷（Roll Up）
图6 上卷如图6，我们在对数据进行上卷时，一般指的是对某几列进行Group By操作，也就是预聚合；当我们在对原始数据进行聚合后，那么我们的数据量一般就会少很多，而且数据也已经计算过了，在响应用户的查询时，可以大大优化计算和IO的效率。
业界比较出名的基于上卷的引擎有Apache Druid，Google Mesa，Doris/Starrocks等，一般都是单表场景。
单次上卷的性能在预计算场景中其实还好，而且大部分用户的监控等场景没有非常复杂的查询需求，所以在业界使用的也比较广泛。
物化视图
图7 物化视图物化视图是一个概念比较大的词，粗略来讲所有根据原始表通过SQL计算出来的结果都可以物化成一张新表则该表即为物化视图表，但是如果不能做到如图7的自动改写用户的SQL进行提速，那么用户如果需要对非常多的物化视图表进行管理是一个非常头疼的问题，所以业界的SQL引擎一般都会基于论文Optimizing Queries Using Materialized Views: A Practical, Scalable Solution来实现改写SQL优化。
业界大量的数据库其实都有物化视图功能，各类TP数据库，Hive，Drois/Starrocks，Presto，Calcite等等。
物化视图可以是多表的关联也可以是单表，一般也是对数据的上卷计算，不然数据不减少的物化，利用价值不会太高。
星树（Star-Tree）
图8 Star-Tree星树的star（*）表示所有情况，即用户要创建一个A,B,C三列的星树，那么就会生成A,B,C/B,C/C的上卷组合，其实在Kylin的Cube中也有类似的组合关系，其实就是根据列多次上卷，根据用户的SQL找到最优的组合进行回答，可以得到极致的性能。
星树是由Apache Pinot提出来的，还可以根据列的性价比进行优化，选择最优的组合方式。不过还是基于单表。
目前国内也有一些公司使用Apache Pinot，但是更多的公司还在使用Apache Druid。
数据立方体（Cube）
图9 数据立方体关系
图10 数据立方体图形数据立方体是数据仓库领域的一个重要概念，数据仓库中一般会基于维度建模生成数据模型，然后根据数据模型的各个维度的排列组合进行预聚合，这样用户在对数据模型（星型模型，雪花模型，星座模型）进行查询时，可以得到一个非常极致的查询体验，因为各种场景的数据都被预计算好了（但是现实世界没那么简单）。
业界在Cube场景做的最好的产品是Apache Kylin，商业版本Kyligence在用户体验上也做的非常好。基于Cube的一些优化，例如一些组合的减支、Cube推荐等也会让用户在某些场景下得到相对合适的解决方案。
Cube一般在解决用户指标维度的报表平台是非常好的，但是在考虑计算和存储（膨胀率）成本和灵活性上，很多用户其实会更倾向于使用类似Clickhouse/Doris/Starrocks这种实时性更好的Olap引擎。
索引 VS 预计算
图11 索引和预计算在计算延迟和存储空间上的关系预计算要使用的存储空间一般都会比索引高很多，极端场景数据的基数非常低例外。
一般情况下用户也不会使用高基数的列进行上卷，如果用了用户本身做的一些统计信息也没法看，行数太多了。
其实索引也会收到基数影响，例如倒排的时候基数过高，等于一列存储了两次。位图索引的空间也会非常高，在扫描范围时性能也很差。
图12 索引与预计算优劣势对比如图12 我们可以看出索引和预计算各自的优势，没有一种方案可以解决所有问题，我们在日常工作中需要为场景找到合适的解决方案。
总结
索引是大数据日常肯定要用到的一种数据组织方法，有效的提高查询速度，减少扫描数据的IO。
预计算会损失一部分信息，但是提高了我们的计算速度，在固定报表等场景肯定是非常有用的。
缓存的话参考Alluxio框架，从内存、NVME SSD到HDD的多级缓存可以提供更加速，后续可以发个文章讲讲缓存。
参考
Google Mesa: https://storage.googleapis.com/pub-tools-public-publication-data/pdf/42851.pdf
Materialized View: https://arxiv.org/pdf/1802.10233.pdf
Star-Tree: https://docs.pinot.apache.org/basics/indexing/star-tree-index
Data Cube: https://arxiv.org/pdf/cs/0701155.pdf
https://courses.cs.washington.edu/courses/cse591d/01sp/opt_views.pdf
