标题：鹰眼(本文的查询引擎)大象(hadoop)：hadoop中面向分割的索引

编者的总结

1. 本文是基于分布式FS的环境(GFS,Hadoop等)提出的查询索引技术，最重要的是提出，在这种环境上的index，应该以备选partition(split)的削减为主，而不是record-level的索引。
2. 本文基于上述的idea给出的解决方案，是对于每个列(基本类型)都构建索引，有序的做range index，无序的做inverted index，有对inverted index失效的两种情况分别做了优化解决方案(meterialized view + adaptive caching)。

编者的思考

1. 索引的大小还是偏大了，尤其是结构比较复杂的数据，在最多4层嵌套的json数据中，实验中索引大小超过了原数据集的20%。
2. 索引的创建时间在4000s-5000s（800GB），仍偏长。
3. 作者没对index probing time和map-reduce time做一个比例化的实验，但能看到，索引的效果和选择率是强相关的。那么如果index probing time占据较长时间，是否考虑也把index probing做成分布式的map-reduce过程？
4. 对于其他复杂数据类型的索引的处理手段？

ABSTRACT

一个重要的hadoop场景是：在缓慢变化的数据集上，进行特定的group和聚合查询。对于这样的查询优化，传统数据库做了很多措施来避免访问不相关的数据，效果显著。然而照搬到Hadoop上，效果不佳。主要原因是这些措施关注与Record-level的优化，与hadoop设计原则不符，导致没有减少mapper waves，这个mapper waves主要取决于处理的splits的数量（即mapper数量）。另外，基于key的分区要求数据重新组织，这在hadoop上是不现实的。

本文提出的E3框架，主要是为了避免无关的数据分割splits，使用了splits上的倒排索引，域分段，物化视图，自适应缓存技术。效果在小-中型存储负载时，提升高达20倍。

1. INTRODUCTION

query的特征是一会聚集于某个属性的值，之后又是另一属性的值，但是这个顺序是不能先验的。

1.1 Motivating examples

hadoop方便，可用性强。

1.2 The Need for Indexing in Hadoop

query的执行时间主要取决于多少个mapper waves，也就是有多少个split。处理每个split主要的时间是I/O读这个split，以及启动这个mapper，至于处理一两条记录，还是一整个split的记录，差不太多。

1.3 The Need for Improved Indexing

之前基于分区key的集群索引，只能筛选一个属性；
还有就是Hive，如果分区键设置得好还行，如果不先验，也没用；
至于结合索引和partition elimination的，主要是由于HDFS和DB架构不同，文件分块冗余存储，不支持Record-level的读写以及文件appends，都是以文件形式roll in和roll-out的。

1.4 E3 Overview

2. EAGLE-EYED ELEPHANT (E3)

E3用Jaql来处理，所以E3看到的都是flatten json格式的文件（输入可以是csv格式/HDFS sequence file格式）。flatten json就是把嵌套的json格式结构打平，把field_name拼接起来，值只能是基本类型的。
E3用Hadoop InputFormat来创建split。
值得注意的是，E3 index对于同样的数据不同的file descriptor,会生成不同的索引。因此对于每个file，E3会维护一个file descriptor和一个file signature，以保证正确的index用在了查询中。

2.1 Domain Segmentation for Range Indexing

首先就是对于每个可排序的field（数值、日期、包括字符串），在每个split做个极值的summerization，用于eliminate，称为range index。可以用于等值查询和范围查询。
极值来eliminate，太松了。数据的一般分布可能分散于几个距离较远的范围内，如下图。我们想把这种更细节的分布找出来，能够比较紧的收界。作者提供了一个简易算法，提供一个用户参数k，表示将全域分成k段，然后将值排序(distinct)，找出邻近距离最长的k-1个gap，把这k-1个gap挖出去，结合全域的[min,max]，就剩下k个分段了。

image.png

作者顺便提了，如果能先验query workload，也可以用fall in 的概率(频数)，做gap的度量。

2.2 Inverted Index

主要用于String，其他如date,number也可以。
index结构是bitmaps，有多少个distinct的值，就有多少个bitmap，bitmap的bits数由split数决定，一对一的关系。如果对应的split包含该值，其位置就设置为1，否则为0.可以用RLE压缩，还可以通过一个map-reduce过程完成。

2.3 Materialized View

有那么一些nasty的value/atom，在大多数split中都出现，但在每个split里面都出现那么一两次，这让inverted index变得佷低效，因此有了物化视图，把这些value/atom所在的record单独copy出来，放到M个split里面。M相对于总数据集的splits数来说，是非常小的。另外，我们期望物化视图占用的空间，和Dataset size相比，应该就是1%-2%，不希望占太多空间，而nasty的atom相比之下，就很多了。因此这就转换成了在一个大的nasty atoms集合里面，选一些最有价值的问题。

首先定义atom v的价值是，一个atom subset的价值是单个价值的集合，如果有query出现概率可以作为权重。

然后是atom v的代价，一个subset V的代价是。这个值比单纯的加和要大一些，因为不同atom的records之间互相会有overlap，然而为了计算简便，我们就估计成了加和。

那么给定最大Records记录数R作为“背包承重”，这就变成了一个背包问题。为了效率，用改造的贪心算法，得到一个近似结果。
首先定一个宽一点的上界U，作为最多的value/atom数，然后根据profit(v)/cost(v)，作topU问题。得到topU了之后，再对他们降序排序，不断去取前面的atoms，累计它们的atom数，直到近似满了。

还有一个问题就是U如何来确定？首先定一个参数L，用来获取完整的nasty集，nasty atom必须至少出现在L个splits里面。那么一个atom至少贡献L个records，物化视图里最多就有U=R/L个atoms。

完整算法如下，整个过程也可以用一个map-reduce + 一个map完成：

image.png

2.4 Adaptive Caching

主要解决的是组合索引的问题，比如两个atom v,w，每个都非常频繁出现在各个split，但是放在一起，就很少出现了。那么此时inverted index就起不到什么剪枝作用，作者提出了一个缓存技术，adaptive cache。
首先定义缓存命中的收益
有了缓存，肯定要有替换策略，替换一般是LRU，但是LRU只考虑频率和时间上的最近这两个，对于缓存收益，没有考量。本文提出了SFR替换技术(savings-frequency-recency)。
为了保存访问频率和时间，还要保存一个query history，里面只记录query pair的频率时间信息FR。通过FR和收益相乘，得到SFR，用于替换真正的cache table。cache table保存一个bitmap，一个SFR。

首先来看FR的计算，算法刚开始初始化FR为1，每一个新的pair到了之后，会放大倍（受recency影响），如果query history table有这个pair，那么FR就加上这个值（受frequency影响），没有的话就填充一项。为了避免FR无限放大，定期要做下标准化。

作为一个缓存，必然有完整计算的方法，完整算法如下。注意到，为了拿到splits(v,w)，使用了一个hadoop的标准counter：Task.Counter.MAP_OUTPUT_RECORDS，能够count到最终在reduce阶段有输出的mapper是哪些，可以用于cache的bitmap。

image.png
image.png
image.png

2.5 Computational Flow

整个过程可以用一轮半的map-reduce，对原始数据做两轮read就可以完成，而且可以对其中的技术做参数化配置决定是否使用。

3. USING THE INDEXES AT QUERY TIME

物化视图采取和data file同样的hdfs存储即可。range index和inverted index最好进行中心化存储，作者用了RDBMS，这样可以在map之前就筛选好splits。

查询分两种，一种是只有“且”的，一种是更普遍的谓词形式，包含“且”和“或”。
对于第一种，对于等值的条件，range index,inverted index, adapative cache都可以使用（分数据类型）以进行eliminate，非等值的只能用range index了。筛选之后，如果有物化视图，就过一下，比对一下，是筛选后的少，物化视图对应的splits少（因为还要对没有物化视图的属性做mr），选择少的用就行。

对于第二种，首先都转化成“或”的形式，筛选算法基本一致，只不过筛选的结果splits要并起来，对于物化视图，不能草率使用，很有可能会造成重复，因为一条record的两个属性，可能一个有物化视图，从里面选出来了，另一个没有，也选出来了。因此，只有所有属性都有物化视图的时候，才可以使用，否则不可以用。

4. EXPERIMENTS

4.1 query response time

response time和选择率非常相关。

image.png

4.2 Construction & Storage Costs

image.png

结论如下：

1. Range index索引结构不大，受列数影响较大；物化视图控制在1% of dataset size之内，比较稳定。
2. 反转索引受列数和复杂结构影响较大，占用空间不受限制，实验中占到了20%。
3. 组合构建这几种技术，比单纯累加要快得多。800GB的数据，最快也要1-2个小时。

4.3 Effect of Segment Limit on Range Index

range index中k的影响

image.png

4.4 Adaptive Caching

这一部分实验研究了SFR和LRU的比较影响，暂时略过。

5. RELATED WORK

hadoop++需要数据重排，否则Record-level的优化没用；
hadoopDB把数据都给DB来管理了，hadoop的优良性质都被disrupt了；
有做文本索引的，这个本文倒是没什么办法....，只能拆开单词做inverted index；
有很多对聚合和join做优化的，但是本文是对select和where做了优化；
替换策略考虑saving，是之前T Palnans提出的；
range index是之前数仓的思路；partition elimianation是分布式数据库的思路。