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 期待的多个查问可能有更高的策略来进行优化。