摘要

索引提供了一个非歧视性的导航来定位关注的元组。维护的代价是在数据库更新的时候产生的。本文提出了一种补充方法，用连续的物理重组把索引维护作为查询处理的一部分，也就是cracking数据库成可管理的pieces。动机是按照用户要求的方式自动组织数据。

介绍

一种全新的数据库结构，Database cracking，基于这样的假设：索引维护是查询处理的副产品，而不是更新的副产品。每个查询不仅是对特定结果集的请求，也是crack the physical database store into smaller pieces的建议。每个piece用查询来描述，这些pieces组成一个cracker索引，用来加速未来的搜索。cracking索引取代原先的非歧视索引(B+树，哈希表之类的)。只有过去感兴趣的部分才能够快速的定位。剩下的在查询感兴趣之前保持非索引状态。

用cracking，数据的物理存储方式根据查询workload自组织。即便是很大的数据集上，只有有兴趣的元组会被碰到，在查询性能上有巨大提升。如果焦点转移到数据的不同部分，Cracking索引会自动调整到该位置。因此将数据库拆分为多个部分，可以使特定的查询针对的数据集不相交。这对高速分布式和多核查询很有意义。

Cracking

MonetDB是一个列存储数据库
下面看如何对一个面向列的数据库进行Cracking，具体如下：

• 第一次对属性A进行范围查询的时候，Cracker数据库会对列A进行复制。副本叫作A_CRK。
• 基于在属性A上的查询持续地对A_CRK进行物理重组。

基于在属性A上的查询q的Cracking就是说把A中满足查询q的值存在连续的空间中这样一种方式对A_CRK进行重组。

在副本上进行Crack能保证原始列的完整，从而允许通过插入顺序快速重建records.
在原始的面向列的存储中，不同的属性是不同的列，但是属于同一个元组的不同属性在各自的列中是同一个位置(得到一个列中的位置之后，不用在查找其他列的属性)。但是在Crack列中，元组的原始位置(插入序列，也是id)因为物理重组被破坏。因此用crack列进行进行快速的查找，用原始列进行高效地投影，基于元组id进行位置的查找。

随着查询，crack列被分成越来越多的pieces。因此，需要一种方式能快速本地化cracker列中关注的部分。为此，为每一个cracker列c引入了一个cracker索引，维护在c中值是如何分布的。这里的cracker索引用的平衡二叉树。树的每个节点存一个值v，也就是存一个位置p(referring to the cracker column)所有比p小的都在左边，所有比p大的都在右边。

这个信息能够显著加速后续的查询，即对于请求和索引已知值完全匹配的范围查询，只用在索引上的搜索的代价。

如图1，所示，对于列A，查询Q1会创建一个A_CRK，根据Q1的查询谓词把原先的数据分成了三段(,10] (10,14) [14, )。然后Q2对Q1之后的A_CRK继续进行切片。
Cracking究竟在做什么？现在看起来就像是根据查询一步步对数据进行了排序，就像是快速排序，这有什么用呢？但几乎所有索引都是有序的或者节点间有序啊

几个问题：
比起排序如何，为什么不预先排序
每次物理重组(或部分物理重组)代价多大
Cracking之后如何适应现代DBMS的查询计划
Cracking一个面向行的数据库：面向行的数据库需要为Cracked的属性创建一个cracker列。可以是一个二元关系存的是reference-value对(r, v)，v是值，r指向v所在的record的地址。

Cracking VS. 排序 VS. 索引

一个主要问题是cracking与排序和索引怎么比。在这一节，把cracking作为特定环境中的一个替换策略，无法通过排序或者索引进行有效处理的时候。

cracking会在cracker列中的pieces之间保持顺序。piece p中的每个值都比p_i(在p前面)中的值大。而对比排序，它就是事先进行了排序，然后进行二分查找。

假设实现知道要查哪(几)个属性，因此应该确定元组的物理顺序；再假设查询之前有足够的时间和资源俩创建物理顺序，并且没有更新，或者在任何更新或者查询前的时间差足够维持这个物理顺序(或者维护提供顺序的索引，如B树索引)，如果这些假设都满足，排序当然很好。
当然上面的假设不能都满足，所以crack可以用在下面的环境中：

• 不知道要用哪部分数据，什么属性，什么范围
• 在更新后没有足够的时间进行物理重组或者维护物理顺序

另外，crack允许每个属性维护独立的物理顺序。与排序相比，crack是一种轻量级的操作，crack不需要事先了解就可以进行快速的数据访问。

同样的论点也适用于索引，或任何试图通过巧妙的将关注的数据聚集起来。对于索引，workload的知识是必须的来区分关注的数据(首先得知道在哪个属性上查询才能在这个属性上建立索引吧)。另外，需要提前的时间和资源来准备数据(创建索引)。

Cracking 算法

物理重组或crack是对整个列或在列的一个切片上进行的操作。
两个算法

这个是用med把一个片段分成两半，和快速查找的合并是一样的。从左边找一个大于med的，从右边找一个小于med的，两者交换。

算法2是把(low, high)之间的数据连续存储。

两个算法都是碰尽可能少的数据。核心思想是用两个或三个指针读对列进行遍历，辨别两个元组交换的情况。Cracking算法是缓存敏感的，总是尽可能用最近读过的元组。

两段crack比三段crack更常用。只有当select请求范围内所有元组都在cracker列的同一个piece的时候采用三段crack。对于从物理上重新构建一个索引这种情况更可能发生。当列被拆分为多个piece之后三段crack用的就比较少了。

Cracking查询计划

cracker.select操作

MonetDB中的操作会把结果具化。select简单的工作原理：拿到存有指定属性的列，扫描，创建一个新列，新列只包含满足查找谓词的值。
在这里，select也会负责cracking，工作如下：

• 在cracker索引中决定哪(几)个cracker column的pieces要物理重组
• 对cracker column物理重组
• 更新cracker index
• 返回cracker column的一个切片作为结果(0 cost)
  用cracker.select执行上述操作。看起来在select中增加了额外开销，事实并非如此。主要是要分析的元组范围缩小了，再加上物理重组，导致操作速度比MonetDB原来的select(需要扫描列中所有的元组)更快。刚开始cracker.select慢一些，随着查询cracker.select要快得多了。

cracker.rel_select

Ra1 := crackers.select(Ra, 5, 10);
Rb1 := crackers.select(Rb, 9, 20);
Ra2 := algebra.OIDintersect(Ra1, Rb1);
Rc1 := algebra.fetch(Rc, Ra2);

对于OIDintersect代价很大。在原来的查询中，因为不同属性(列)元组对应的属性所在的位置也是一样的，这样的话Ra1和Rb1的oid也是对应的；但是crack不同，在Ra和Rb已经重新打乱了物理位置，这样再进行相交是乱序的，代价很大。因此它需要一个基于哈希的实现(便于内部的随机访问)。在比例因子为0.1时的TPC-H查询6的测试显示OIDintersect成本高出七倍。

代数操作和SQL编译器——cracker-aware查询计划。一个新的cracking操作rel_select，目标是方式OIDintersect。用rel_select取代了原来的select和OIDintersect，同时执行这两个操作。把中间列c1和基列c2作为参数，由于Cracking，c1已经不按OID排了，作为一个没有crack的基列，c2有一个稠密的升序的OID序列。因此在c1上迭代时，rel_select利用对c2的快速位置查找到匹配的元组(c1.oid=c2.oid)，然后检查c2.attr的选择谓词。计划转化器能够简单的解决通过优化器产生下面的查询计划：

Ra1 := crackers.select(Ra, 5, 10);
Rb1 := crackers.rel_select(Rb, 9, 20, Ra1);
Rc1 := algebra.fetch(Rc, Rb1);

上面说的是基列c2是没有crack的原始列，但是代码里又用的是Ra1，但Ra1明显不是没有crack的样子啊，否则原来的OIDintersect就能用了
这个方法显著提升了SQL查询的性能。

实验

select测试

测试三种select，简单的——用MonetDB默认的select操作；排序的——首先基于现存元组的值对列物理重排，之后对于后面的查询用二分查找；crack的——每次查询后物理重排(部分)列。列有10⁷个元组，每个查询v₁<A<v₂中的v₁和v₂是随机选取的。

图2a显示了简单开始最快因为不需要初始化；排序最慢，因为它需要时间排序；对于crack只有第一次比简单慢，后面的查询都会从前面查询构建的cracker列受益。
crack的代价取决于物理重组的pieces的大小，这也是为什么随着越来越多的查询crack变得便宜的原因。图2a中crack的增长速度可以看出来。图2b显示了查询越多，碰的元组越来越少。
crack与排序进行比较的一个关键点就是确定盈亏的平衡点。因为排序是在一开始耗费代价进行了排序，后面是一劳永逸的二分查找。但是crack事实上是把排序的代价分到各个查询中了，前面多一些，后面少一些。在图2a中直到10⁵条查询二者才相等。图2c也证明了这一点。算法复杂度上，第一个crack的复杂度是O(N)，而排序是O(NlogN)。

cracker索引总是要更新，一些部分物理重组。截断策略很有效——当后面的select成本低于某个阈值的时候就停止更新cracker index。

图3显示了选择度对与crack的影响。选择度小的时候，cracker列会创建一个小的piece作为结果，留下大段的供未来的查询的分析，所以未来的查询可能要做大段的物理重组；但选择度高的时候，cracker列能更快的，更均匀的对pieces进行分区。

完全查询评估

上图展示了select count(*) from where R.a>v₁ and R.a<v₂ 的结果
查询是随机的，选择度也是随机的。当选择度很高的时候MySQL的B树性能也很好，但是为了保持这样的性能，传统的系统需要预先了解和稳定的查询工作负载。
图4b显示了crack显著提高了MonetDB的性能。

研究领域

这里分析了crack给数据库系统架构各个角落出现漏洞的后果。在代数core和在计划生成的实现上

cracked查询计划的优化

crackers.rel_select涉及不同的关系只有一个列被重组，需要选择crack哪个属性，会显著影响性能。如A1和A2两个属性间选择，可能A1上crack过了，A2没有crack过，可能crackA1更好；可能在A2上的选择度更高(更大的中间结果会导致额外的代价)。

还有很多参数要考虑，如存储空间限制。这种情况下，尽量减少crack的属性，这样就不用复制列了。

注意，cracker index和cracker column是可以丢弃的信息，可以随时删除，不会产生任何开销或持久性问题。这就意味着一种潜在的自组织策略是可能存在的，如所有cracker列不得超过给定的最大存储大小S。然后可crack列取决于查询负载。S可以变化，适应查询负载和资源限制。

免费的统计(Histogram)

前面只在select中用了crack，下面看crack如何用在其他操作。

cracker索引包含给定属性的确定值范围的信息。不仅能在select中用。如cracker索引可以作为直方图加速查询。用cracker索引可以知道一个给定范围有多少元组在里面
(cracker索引维护pieces的信息，数量，左右区间)

传统的直方图是分开维护的，额外的存储和操作成本。并不总是与数据库当前状态保持最新。传统的直方图也是一个自组织数据结构。

连接

对于cracked的属性都有一个cracker列，cracker列不同pieces之间是有序的。因此可以在cracker列上设置一个类似排序合并的算法。不用排序或建立哈希表，可以直接进行连接。

更多Cracking操作

cracking操作的核心原理是对数据物理重组，是操作的结果元组聚集在一起。挑战在于能不能用在select之外的更多操作符的设计与实现，如连接和聚合。
一个重要挑战是高效地支持多个cracking操作符在一个查询计划的同一个属性上。如在同一个查询中对同一个属性应用cracher.select和cracker.join操作。

并发

crack意味着物理重组，会产生并发问题。如一个查询用cracker列向其查询计划中的下一个运算符提供数据时，另一个查询在同一个属性上开始cracking select。

第一个问题简单解决方案是在操作符级别限制访问，查询q1不允许物理重组cracker column c在c被查询q2的操作符读的时候。这种情况下，q1可能等q2释放或者回到原来的列上进行非crack select操作。

更新

表在查询前没有实例化。对于原始列维持这插入的顺序，更新就是append。但是cracker列如何更新呢。
MonetDB用delta table延迟更新，用delta table来挂起插入、删除和更新。事务提交的时候修改会被写入到原始列。
而crack的做法是把修改单独用一个表，直到表的大小超过阈值。cracker优化器把挂起的更新表合并到查询计划中，补偿过期的原始列和cracker索引。
在只插入的情况下，所有元组都可以简单的加到cracker列的末尾，并忘记cracker索引。用接下来的查询重建cracker索引就行了，因为它是部分有序的，所以重建很快。

内存不足

列不能放到内存里怎么crack？实验证明，与排序或扫描相比，crack是更轻量级的操作。

一个选择是把列逻辑上提前划分成几部分。

何时crack

每来一个查询进行一次crack——但是在crack大的查询序列的时候，可能有不crack更好的情况。随着pieces的增加，管理和维护cracker index就更贵了。
为了进一步优化数据访问，有很多优化方法：如cracker列的pieces最小的大小有临界值，如一个磁盘页或cache line来缓存敏感；查询时，不单对cracker列中的片段进行分区，也可以合并，减少cracker索引维护和访问成本。

先验crack

crack后第二个查询就显示出响应时间的改善。系统空闲时可以运行假查询以便将来的查询受益

分布的cracking

Cracking是一种基于查询负载自然的把数据分到受关注的pieces的方法。在分布式或并行环境中可以通过把数据库的片段分不到多个节点来Cracking。
(分布式)