摘要
索引提供了一個非歧視性的導航來定位關注的元組。維護的代價是在數(shù)據(jù)庫更新的時候產生的。本文提出了一種補充方法，用連續(xù)的物理重組把索引維護作為查詢處理的一部分，也就是cracking數(shù)據(jù)庫成可管理的pieces。動機是按照用戶要求的方式自動組織數(shù)據(jù)。
介紹
一種全新的數(shù)據(jù)庫結構，Database cracking，基于這樣的假設：索引維護是查詢處理的副產品，而不是更新的副產品。每個查詢不僅是對特定結果集的請求，也是crack the physical database store into smaller pieces的建議。每個piece用查詢來描述，這些pieces組成一個cracker索引，用來加速未來的搜索。cracking索引取代原先的非歧視索引(B+樹，哈希表之類的)。只有過去感興趣的部分才能夠快速的定位。剩下的在查詢感興趣之前保持非索引狀態(tài)。
用cracking，數(shù)據(jù)的物理存儲方式根據(jù)查詢workload自組織。即便是很大的數(shù)據(jù)集上，只有有興趣的元組會被碰到，在查詢性能上有巨大提升。如果焦點轉移到數(shù)據(jù)的不同部分，Cracking索引會自動調整到該位置。因此將數(shù)據(jù)庫拆分為多個部分，可以使特定的查詢針對的數(shù)據(jù)集不相交。這對高速分布式和多核查詢很有意義。
Cracking
MonetDB是一個列存儲數(shù)據(jù)庫
下面看如何對一個面向列的數(shù)據(jù)庫進行Cracking，具體如下：
- 第一次對屬性A進行范圍查詢的時候，Cracker數(shù)據(jù)庫會對列A進行復制。副本叫作ACRK。
- 基于在屬性A上的查詢持續(xù)地對ACRK進行物理重組。
基于在屬性A上的查詢q的Cracking就是說把A中滿足查詢q的值存在連續(xù)的空間中這樣一種方式對ACRK進行重組。
在副本上進行Crack能保證原始列的完整，從而允許通過插入順序快速重建records.
在原始的面向列的存儲中，不同的屬性是不同的列，但是屬于同一個元組的不同屬性在各自的列中是同一個位置(得到一個列中的位置之后，不用在查找其他列的屬性)。但是在Crack列中，元組的原始位置(插入序列，也是id)因為物理重組被破壞。因此用crack列進行進行快速的查找，用原始列進行高效地投影，基于元組id進行位置的查找。
隨著查詢，crack列被分成越來越多的pieces。因此，需要一種方式能快速本地化cracker列中關注的部分。為此，為每一個cracker列c引入了一個cracker索引，維護在c中值是如何分布的。這里的cracker索引用的平衡二叉樹。樹的每個節(jié)點存一個值v，也就是存一個位置p(referring to the cracker column)所有比p小的都在左邊，所有比p大的都在右邊。
這個信息能夠顯著加速后續(xù)的查詢，即對于請求和索引已知值完全匹配的范圍查詢，只用在索引上的搜索的代價。
如圖1，所示，對于列A，查詢Q1會創(chuàng)建一個ACRK，根據(jù)Q1的查詢謂詞把原先的數(shù)據(jù)分成了三段(,10] (10,14) [14, )。然后Q2對Q1之后的ACRK繼續(xù)進行切片。
Cracking究竟在做什么？現(xiàn)在看起來就像是根據(jù)查詢一步步對數(shù)據(jù)進行了排序，就像是快速排序，這有什么用呢？但幾乎所有索引都是有序的或者節(jié)點間有序啊
幾個問題：
比起排序如何，為什么不預先排序
每次物理重組(或部分物理重組)代價多大
Cracking之后如何適應現(xiàn)代DBMS的查詢計劃
Cracking一個面向行的數(shù)據(jù)庫：面向行的數(shù)據(jù)庫需要為Cracked的屬性創(chuàng)建一個cracker列?？梢允且粋€二元關系存的是reference-value對(r, v)，v是值，r指向v所在的record的地址。
Cracking VS. 排序 VS. 索引
一個主要問題是cracking與排序和索引怎么比。在這一節(jié)，把cracking作為特定環(huán)境中的一個替換策略，無法通過排序或者索引進行有效處理的時候。
cracking會在cracker列中的pieces之間保持順序。piece p中的每個值都比pi(在p前面)中的值大。而對比排序，它就是事先進行了排序，然后進行二分查找。
假設實現(xiàn)知道要查哪(幾)個屬性，因此應該確定元組的物理順序；再假設查詢之前有足夠的時間和資源倆創(chuàng)建物理順序，并且沒有更新，或者在任何更新或者查詢前的時間差足夠維持這個物理順序(或者維護提供順序的索引，如B樹索引)，如果這些假設都滿足，排序當然很好。
當然上面的假設不能都滿足，所以crack可以用在下面的環(huán)境中：
- 不知道要用哪部分數(shù)據(jù)，什么屬性，什么范圍
- 在更新后沒有足夠的時間進行物理重組或者維護物理順序
另外，crack允許每個屬性維護獨立的物理順序。與排序相比，crack是一種輕量級的操作，crack不需要事先了解就可以進行快速的數(shù)據(jù)訪問。
同樣的論點也適用于索引，或任何試圖通過巧妙的將關注的數(shù)據(jù)聚集起來。對于索引，workload的知識是必須的來區(qū)分關注的數(shù)據(jù)(首先得知道在哪個屬性上查詢才能在這個屬性上建立索引吧)。另外，需要提前的時間和資源來準備數(shù)據(jù)(創(chuàng)建索引)。
Cracking 算法
物理重組或crack是對整個列或在列的一個切片上進行的操作。
兩個算法
這個是用med把一個片段分成兩半，和快速查找的合并是一樣的。從左邊找一個大于med的，從右邊找一個小于med的，兩者交換。
算法2是把(low, high)之間的數(shù)據(jù)連續(xù)存儲。
兩個算法都是碰盡可能少的數(shù)據(jù)。核心思想是用兩個或三個指針讀對列進行遍歷，辨別兩個元組交換的情況。Cracking算法是緩存敏感的，總是盡可能用最近讀過的元組。
兩段crack比三段crack更常用。只有當select請求范圍內所有元組都在cracker列的同一個piece的時候采用三段crack。對于從物理上重新構建一個索引這種情況更可能發(fā)生。當列被拆分為多個piece之后三段crack用的就比較少了。
Cracking查詢計劃
cracker.select操作
MonetDB中的操作會把結果具化。select簡單的工作原理：拿到存有指定屬性的列，掃描，創(chuàng)建一個新列，新列只包含滿足查找謂詞的值。
在這里，select也會負責cracking，工作如下：
- 在cracker索引中決定哪(幾)個cracker column的pieces要物理重組
- 對cracker column物理重組
- 更新cracker index
- 返回cracker column的一個切片作為結果(0 cost)
用cracker.select執(zhí)行上述操作?？雌饋碓趕elect中增加了額外開銷，事實并非如此。主要是要分析的元組范圍縮小了，再加上物理重組，導致操作速度比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已經重新打亂了物理位置，這樣再進行相交是亂序的，代價很大。因此它需要一個基于哈希的實現(xiàn)(便于內部的隨機訪問)。在比例因子為0.1時的TPC-H查詢6的測試顯示OIDintersect成本高出七倍。
代數(shù)操作和SQL編譯器——cracker-aware查詢計劃。一個新的cracking操作rel_select，目標是方式OIDintersect。用rel_select取代了原來的select和OIDintersect，同時執(zhí)行這兩個操作。把中間列c1和基列c2作為參數(shù)，由于Cracking，c1已經不按OID排了，作為一個沒有crack的基列，c2有一個稠密的升序的OID序列。因此在c1上迭代時，rel_select利用對c2的快速位置查找到匹配的元組(c1.oid=c2.oid)，然后檢查c2.attr的選擇謂詞。計劃轉化器能夠簡單的解決通過優(yōu)化器產生下面的查詢計劃：
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操作；排序的——首先基于現(xiàn)存元組的值對列物理重排，之后對于后面的查詢用二分查找；crack的——每次查詢后物理重排(部分)列。列有107個元組，每個查詢v1<A<v2中的v1和v2是隨機選取的。
圖2a顯示了簡單開始最快因為不需要初始化；排序最慢，因為它需要時間排序；對于crack只有第一次比簡單慢，后面的查詢都會從前面查詢構建的cracker列受益。
crack的代價取決于物理重組的pieces的大小，這也是為什么隨著越來越多的查詢crack變得便宜的原因。圖2a中crack的增長速度可以看出來。圖2b顯示了查詢越多，碰的元組越來越少。
crack與排序進行比較的一個關鍵點就是確定盈虧的平衡點。因為排序是在一開始耗費代價進行了排序，后面是一勞永逸的二分查找。但是crack事實上是把排序的代價分到各個查詢中了，前面多一些，后面少一些。在圖2a中直到105條查詢二者才相等。圖2c也證明了這一點。算法復雜度上，第一個crack的復雜度是O(N)，而排序是O(NlogN)。
cracker索引總是要更新，一些部分物理重組。截斷策略很有效——當后面的select成本低于某個閾值的時候就停止更新cracker index。
圖3顯示了選擇度對與crack的影響。選擇度小的時候，cracker列會創(chuàng)建一個小的piece作為結果，留下大段的供未來的查詢的分析，所以未來的查詢可能要做大段的物理重組；但選擇度高的時候，cracker列能更快的，更均勻的對pieces進行分區(qū)。
完全查詢評估
上圖展示了select count(*) from where R.a>v1 and R.a<v2 的結果
查詢是隨機的，選擇度也是隨機的。當選擇度很高的時候MySQL的B樹性能也很好，但是為了保持這樣的性能，傳統(tǒng)的系統(tǒng)需要預先了解和穩(wěn)定的查詢工作負載。
圖4b顯示了crack顯著提高了MonetDB的性能。
研究領域
這里分析了crack給數(shù)據(jù)庫系統(tǒng)架構各個角落出現(xiàn)漏洞的后果。在代數(shù)core和在計劃生成的實現(xiàn)上
cracked查詢計劃的優(yōu)化
crackers.rel_select涉及不同的關系只有一個列被重組，需要選擇crack哪個屬性，會顯著影響性能。如A1和A2兩個屬性間選擇，可能A1上crack過了，A2沒有crack過，可能crackA1更好；可能在A2上的選擇度更高(更大的中間結果會導致額外的代價)。
還有很多參數(shù)要考慮，如存儲空間限制。這種情況下，盡量減少crack的屬性，這樣就不用復制列了。
注意，cracker index和cracker column是可以丟棄的信息，可以隨時刪除，不會產生任何開銷或持久性問題。這就意味著一種潛在的自組織策略是可能存在的，如所有cracker列不得超過給定的最大存儲大小S。然后可crack列取決于查詢負載。S可以變化，適應查詢負載和資源限制。
免費的統(tǒng)計(Histogram)
前面只在select中用了crack，下面看crack如何用在其他操作。
cracker索引包含給定屬性的確定值范圍的信息。不僅能在select中用。如cracker索引可以作為直方圖加速查詢。用cracker索引可以知道一個給定范圍有多少元組在里面
(cracker索引維護pieces的信息，數(shù)量，左右區(qū)間)
傳統(tǒng)的直方圖是分開維護的，額外的存儲和操作成本。并不總是與數(shù)據(jù)庫當前狀態(tài)保持最新。傳統(tǒng)的直方圖也是一個自組織數(shù)據(jù)結構。
連接
對于cracked的屬性都有一個cracker列，cracker列不同pieces之間是有序的。因此可以在cracker列上設置一個類似排序合并的算法。不用排序或建立哈希表，可以直接進行連接。
更多Cracking操作
cracking操作的核心原理是對數(shù)據(jù)物理重組，是操作的結果元組聚集在一起。挑戰(zhàn)在于能不能用在select之外的更多操作符的設計與實現(xiàn)，如連接和聚合。
一個重要挑戰(zhàn)是高效地支持多個cracking操作符在一個查詢計劃的同一個屬性上。如在同一個查詢中對同一個屬性應用cracher.select和cracker.join操作。
并發(fā)
crack意味著物理重組，會產生并發(fā)問題。如一個查詢用cracker列向其查詢計劃中的下一個運算符提供數(shù)據(jù)時，另一個查詢在同一個屬性上開始cracking select。
第一個問題簡單解決方案是在操作符級別限制訪問，查詢q1不允許物理重組cracker column c在c被查詢q2的操作符讀的時候。這種情況下，q1可能等q2釋放或者回到原來的列上進行非crack select操作。
更新
表在查詢前沒有實例化。對于原始列維持這插入的順序，更新就是append。但是cracker列如何更新呢。
MonetDB用delta table延遲更新，用delta table來掛起插入、刪除和更新。事務提交的時候修改會被寫入到原始列。
而crack的做法是把修改單獨用一個表，直到表的大小超過閾值。cracker優(yōu)化器把掛起的更新表合并到查詢計劃中，補償過期的原始列和cracker索引。
在只插入的情況下，所有元組都可以簡單的加到cracker列的末尾，并忘記cracker索引。用接下來的查詢重建cracker索引就行了，因為它是部分有序的，所以重建很快。
內存不足
列不能放到內存里怎么crack？實驗證明，與排序或掃描相比，crack是更輕量級的操作。
一個選擇是把列邏輯上提前劃分成幾部分。
何時crack
每來一個查詢進行一次crack——但是在crack大的查詢序列的時候，可能有不crack更好的情況。隨著pieces的增加，管理和維護cracker index就更貴了。
為了進一步優(yōu)化數(shù)據(jù)訪問，有很多優(yōu)化方法：如cracker列的pieces最小的大小有臨界值，如一個磁盤頁或cache line來緩存敏感；查詢時，不單對cracker列中的片段進行分區(qū)，也可以合并，減少cracker索引維護和訪問成本。
先驗crack
crack后第二個查詢就顯示出響應時間的改善。系統(tǒng)空閑時可以運行假查詢以便將來的查詢受益
分布的cracking
Cracking是一種基于查詢負載自然的把數(shù)據(jù)分到受關注的pieces的方法。在分布式或并行環(huán)境中可以通過把數(shù)據(jù)庫的片段分不到多個節(jié)點來Cracking。
(分布式)
