Concurrency Control for Adaptive Indexing
自适应索引的指标在于可能暗藏或最小化索引创立的代价。它的一个副作用就是在查问过程中，从自读变成了更新事务——可能引起锁的争用。
本文钻研的是自适应索引只读查问的并发管制。
自适应索引是查的越多越优化，先前的查问以Database cracking的形式进入了查问中。代价就是读查问变成了写查问，查问在执行扫描或者索引查找的时候会调用操作来递增地优化数据库的物理构造。

自适应索引在查问中的并发管制须要协调索引的更新优化比更新传统的索引简略(然而传统索引在查找时并不需要更新)。图1展现了自适应索引和传统索引的比照。只读查问引起的更新只影响索引的构造不影响索引的内容，因而用latch而不是lock。并且这种查问带来的更新是可选的，能够跳过的——这就放宽了比传统索引更新的限度。
另外随着查问，索引的优化，锁的粒度会越来越小。
三点奉献：

自适应索引在并发查问中也维持着自适应的属性(体现在锁的粒度)
自适应索引随着查问的减少，并发执行时的抵触会自适应的缩小
自适应索引能够摸索并发查问的调度来减少并行性

前期工作

database cracking 略
Adaptive Merging：database cracking相似于疾速排序，而Adaptive merging相似于归并排序。它会当时分成等大的局部，在各个区内先排序，而后产生后果到一个final partition，查问最初的后果都会进到final partition中，final partition就是优化好的局部。final partition是每次都要拜访的，要么后果在外面，要么后果须要移入外面。图3
Database Cracking的初始化代价很小，然而收敛慢(须要较屡次查问来造成full index)；adaptive merging初始化代价较大，然而收敛较快。如何了解
Hybrid Adaptive Indexing:联合以上两个办法的长处，又防止了两个的毛病，可能疾速收敛，又不必初始分区的齐全排序。如图4
办法

图5是索引的状态，1是不存在索引，2是索引在目录中但还没有创立结束，3是传统索引的操作(在未实现的局部索引上，实际上就是数据的插入)，4是自适应索引的优化操作，5是齐全建设好的索引
自适应索引优化也就是状态4——所有的entries都有，但不在本人的地位上。

两个根本因素加重自适应索引的并发管制的开销（也就是尽管是逻辑上是只读的查问，但事实上会批改索引数据结构）：

只读查问批改的是索引的数据结构而不是索引的内容(latch 和 lock)。用户数据和零碎状态的隔离，零碎事务和用户事务的隔离。当用户事务回滚时，曾经实现的优化是不须要回滚的。
索引构造的自适应性也要适应以后的工作负载，其锁的粒度也会随着调整。越优化，锁的粒度越小。缩小latch争用的可能性。

3.1Locks vs. Latches 略
3.2档次锁和增量锁
档次锁——缩小锁的数量
增量锁——动静扭转锁的粒度
Crack创立的分区有利于增量锁
3.2 并发管制
并发管制的解决有以下集中办法：

Latching：疾速重组期间要持有latch。须要先取得page latch再去获取page或者key value上的lock
冲突检测：因为自适应索引是可选的，有抵触能够放弃优化
提前终止：索引优化能够随时进行
MVCC

B树上的自适应索引
这是用adaptive merging自适应的建设一个残缺的B树的办法，partitioned B-tree。
面向列的自适应索引
面向列的存储与拜访：同一个表中所有元素都是对其的，表中第i个元组的各个元素都在其各自列的第i个地位。面向列的自适应索引利用了列的两个个性：1.定长浓密数据很好优化 2. 对于在多个列查问的状况，每个列的查问只占整个查问的一部分，这就意味着它实现后就能够开释latch了，而不必整个工夫都持有latch。
并发管制

Column latches：思考在一个列上的单个select，select开始执行，（首先latch全局数据结构什么意思看这个列的cracker index有没有创立，如果没有初始化一个原始的cracker index列）latch这个AVL(AVL是database cracking默认的索引)和cracker array。一旦取得latch，开释全局数据结构的latch，而后select和对cracker array的优化开始在下面进行排他拜访。select(蕴含cracker index优化和AVL更新)实现后，索引的latch开释。
(全是排它锁)

读写Latch：同一个列，一个查问一个聚合，重组可能会使聚合呈现谬误。然而多个聚合操作又能够在同一个列并行执行。每个select操作都须要写latch，聚合(和其余不产生cracking的操作)须要读latch。

Pieces-wise Latches：事实上cracking只产生在蕴含这个范畴查问[a,b]边界a和b的两个piece上，也就是这用给这两个pieces和AVL上Latch就好(图9)。
图8两头，首先初始化，Q1给全副加写锁，在70Cracking成两个pieces，而后之后的就能够依照两个边界并行执行了。
Pieces-wise Latch的优化：边界[a,b]在不同pieces时，能够并行执行，一个抵触另一个能够执行。查问Q1会对期待的查问产生影响。如图10，Q1是100，执行后原先的piece被分成了两个，对于Q2和Q3来说其对应的pieces都扭转了(但能够并行执行了)。对于每个查问都是通过AVL树来取得其所在piece的。
另一个优化是能够通过调度来减少并行性，如Q1-Q5别离是期待在piece[0,100]上的查问，并且key别离是20,30,40,50,60，如果依照这个程序来执行的话，只能串行执行，但如果执行Q3-40那么剩下的就能够并行执行了。
继续缩小抵触：越查问越优化 ——》piece越小 ——》优化的老本越低——》一个查问持有的Latch工夫越短——》并发度越高

试验剖析
根本性能

对于扫描，齐全无奈利用之前查问的常识；对于排序，如果一个查问是离群值what？或者工作负载只有几个查问，不能摊派掉后期投入的巨额老本。
并发管制
在齐全索引中 不须要思考并发问题，而在自适应索引中，因为把只读转化为了写，因而为了性能必须要管制并发管制的老本。

单个客户端作为根本(串行执行)，看多个客户端与其的比照状况。图12显示并发管制老本很小。

将来的工作
并发管制的算法
被动算法：一旦索引达到当前工作负载的最佳状态，查问将进行进行优化操作和随着随同的并发问题。——发生冲突机会缩小，代价是流动步骤中产生潜在的高老本。
懈怠算法：如一次只有一个查问对给定的数据局部产生副作用，缩小争用以实现更高的并发——升高优化速度。
动静算法：以后自适应索引优化操作都是独立的对一个查问做出反馈，为一个查问决定如何为以后的工作负载进行优化。因而下一步思考如何应用一组查问来领导索引优化。如在给定一个piece期待的多个查问可能有更高的策略来进行优化。