《高并發Oracle資料庫系統的架構與設計》一2.2 索引與排序

本節書摘來自華章出版社《高并發oracle資料庫系統的架構與設計》一書中的第2章，第2.2節，作者 侯松，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視

通過2.1節的介紹，我們知道了索引掃描是可以優化排序的，索引掃描輸出的結果是有序排列的（索引快速全掃描除外），為什麼會這樣呢，難道索引輸出的時候自動做了一次排序嗎？其實不是的，應該說索引本身就是一種有序排列的資料結構。索引在建立條目的時候，就已經将其按照索引列的順序進行順序存儲，這和表的存儲結構是不一樣的。

之是以将排序這個話題單拿出來講，主要是為了說明一個排序的道理。很多人可能有意無意地忽略了sql語句中的排序這塊，其實很多時候，避免排序可以大大提升sql語句的性能，這是非常重要的一點。不論作為開發者還是管理者，都需要時刻保持對排序的敏感。很多時候，臨時表空間使用率超限，查詢速度太慢都可能是因為排序太多，pga記憶體排序區裝不下，不得不放到臨時表空間去排序，臨時表空間是磁盤排序，在速度上和記憶體排序是無法比拟的。

本節将圍繞索引這種有序結構與排序優化展開介紹，讓讀者充分了解到索引對優化排序的作用。

我們已經了解到b樹索引是一種典型的樹形結構，其包含的元件主要是：

根節點：隻有一個根節點，是位于樹的最頂端的分支節點；

分支節點：存儲指針指向索引裡其他的分支節點或者葉節點；

葉子節點：存儲索引條目（包括索引條目頭資訊、索引鍵值長度、索引鍵值，以及rowid相關資訊）直接指向表裡的資料行。

下面通過一張示意圖來描述一下這種内部結構，如圖2-7所示，就分支節點塊（包括根節點塊）來說，其所包含的索引條目都是按照順序排列的（預設是asc升序排列，也可以在建立索引時指定為desc降序排列）。每個索引條目均由兩個字段組成，第一個字段表示目前該分支節點塊下所指向的葉節點塊中所包含的開始鍵值（對升序排序的索引來說，就是最小鍵值），第二個字段為指向葉節點塊位址的指針。在一個分支節點塊中所能容納的記錄行數由資料塊大小以及索引鍵值的長度決定。在本例中，對于根節點塊來說，包含三個指針，分别為（1 b1）、（100 b2）、（200 b3），它們指向三個分支節點塊。其中的1、100和200分别表示這三個分支節點塊所指向的開始鍵值，而b1、b2和b3則表示所指向的三個分支節點塊的位址。

對于葉子節點塊來說，其所包含的索引條目與分支節點一樣，都是按照順序排列的。每個索引條目也包含兩個字段。第一個字段表示索引的鍵值，對于單列索引來說是一個值，而對于複合索引來說則是多個值組合在一起的。第二個字段表示該鍵值所對應的資料行的rowid，該rowid是資料行在表裡的實體位址。

當有新的索引鍵值插入的時候，索引會判斷新鍵值的排序位置。如果新鍵值大于目前索引存儲的最大值，則會将新鍵值插入到最右側的葉節點塊（l8）上，如果新鍵值為198，則會将其插入到節點塊l6上。如果對應葉節點塊已滿，則會分裂出新的葉節點塊，分支節點塊滿了，同樣會分裂出新塊。

索引這個特點是不同于表的，dml操作過程中，對索引維護成本是比較大的，是以我們需要定期地去分析索引的結構，保證其高效支援查詢的能力。

在使用索引優化查詢的過程中，一方面是通過索引掃描快速定位傳回行的rowid，另一方面則是利用索引的有序結構避免一些不必要的排序操作。

下面我們将結合2.1節中介紹的五種索引掃描方式來讨論一下使用索引掃描輸出結果集的排序問題吧。

索引唯一掃描：這種掃描方式，輸出的結果集隻有一個記錄行，就不存在排序的問題；

索引範圍掃描：該方式是索引排序最典型的應用，其輸出結果集都是有序的（升序輸出還是降序輸出取決于索引建立時的參數，預設為升序）；

索引全掃描：這個方式可以看做是全範圍的掃描，其效果和索引範圍掃描是一樣的；

索引快速全掃描：從字面上來看，和索引全掃描非常相像，但兩者是完全不同的兩種方式，快速全掃描的輸出結果集是不排序的，如果where子句中要求order by，則需要額外的排序開銷；

索引跳躍掃描：可以視作是分拆成多個邏輯子索引後的index combine掃描，對于邏輯子索引的掃描即為索引範圍掃描或者索引全掃描。

下面我們通過幾個執行個體對比來具體分析一下幾個比較典型的掃描方式的排序情況：索引範圍掃描、索引快速全掃描、索引跳躍掃描。

1.?索引範圍掃描排序

首先，要建立一個測試表，2.1節的alex_t01表都是順序插入的連續性資料，這對于排序的識别有些困難，我們重新建立一個表alex_t02，修改b列和c列的資料為随機數插入。具體步驟和sql語句如下所示：

步驟1　建立表alex_t02，及主鍵索引和普通索引：

步驟2　初始化資料，随機插入10萬行資料：

步驟3　收集表和索引的統計資訊及直方圖資訊：

不進行排序操作，先來對比一下全表掃描和索引掃描的輸出結果。如下例所示，可以看到，索引掃描輸出的結果是有序的（對c列采用預設的升序排列），全表掃描則是無序的（其結果的順序為資料實際入庫的順序）。

如果需要全表掃描的輸出與索引掃描一緻，就需要進行一次額外的排序（order by c）操作。如下所示，在sql語句執行的統計資訊中多了一次記憶體排序操作：

如果我們使用的是索引範圍掃描的話，即使我們添加了order by子句，聲明需要排序操作，但是cbo優化器也會忽略掉這個要求，在執行後的統計資訊中也沒有出現任何排序，如下所示：

在索引掃描取數的時候，對索引列進行order by是沒有必要的（索引快速全掃描除外）。

2.?索引跳躍掃描排序

前面介紹過索引跳躍掃描其實是将複合索引打散成邏輯上的子索引，再進行掃描。基于這個原理，我們可以想象到，子索引和子索引之間的關系是按照複合索引的前導列的順序有序組織的，子索引内部則是按照子索引的鍵值的順序有序組織的。各個子索引對應輸出的子結果集也具有同樣的順序關系。

在下面的例子中，order by子句要求的排序方式為（a，b），這和複合索引的預設順序是一緻的，是以子結果集直接輸出即可，不必額外的排序，最終看到的統計資訊中的排序次數為0。

如果order by子句要求的排序方式和複合索引結構的預設順序不一緻呢？如下例所示，b列的資料是随機生成的，本是無序的。在各個子結果集内部，由于索引有序結構的關系，b列是有序排列的，但在各個子結果集之間比較，b列則是無序的。比如：子結果集（a=0）中可能存在b={1,2,3,4}，子結果集（a=1）中可能存在b={1,3,5,6}，如果按照複合索引的預設順序（order by a, b）輸出則是b={1,2,3,4,1,3,5,6}，如果按照子索引鍵值順序（order by b）輸出，則是b={1,1,2,3,3,4,5,6}，後者的輸出意味着需要一次額外的排序。

3.?索引快速全掃描排序

現在我們知道了對于複合索引來說，order by子句要求排序的列正好在複合索引鍵上是可以避免不必要的排序的，但是這裡也有一個例外，就是索引快速全掃描的情況。前面提到該掃描方式是不支援排序輸出的，如果指明order by的話，會需要額外的排序操作，而且此排序的cost開銷非常大，如下例所示：

細心的讀者可能已經注意到，上例中添加了hint關鍵字強制執行計劃，而且執行計劃中的cost開銷是比較大的，如果去掉hint呢？結果如下：

從執行計劃中可以看到，快速全掃描被全掃描代替了，cost開銷反而降低了。一般情況下，快速全掃描的效率是要比全掃描高的，此時cbo為什麼反而選擇全掃描的方式呢？原因就出在排序上。

對于大結果集的輸出，盡量避免不必要的排序，如果能用索引排序進行優化，也請盡量使用。

看到這裡，有的讀者可能會問到，我們一直都是在說升序的情況，如果要求降序查詢呢，情況是否會不一樣呢？是的，會不一樣。我們接下來将圍繞這個索引降序的話題來說一說。

我們可以從單列索引和複合索引兩個次元來進行闡述。當然，在闡述之前，先介紹一個新的概念，就是“降序索引”。

1.?降序索引

什麼是降序索引呢？其實降序索引也是b樹索引，隻是将通常意義上的b樹索引中的存儲方式從升序變成了降序，如果應用場景中經常會出現降序排序的查詢，建立一個降序b樹索引不失為一個很好的選擇。

預設情況下建立的b樹索引均為升序（asc）索引，語句如下：

如果需要建立降序（desc）索引，隻需要在索引列後注明“desc”關鍵字，語句如下：

2.?單列索引的降序

對于單列索引來說，進行升序查詢的時候，其實就是按照從左到右的順序逐一掃描索引的葉節點塊。這個動作是否可以反過來進行呢，從右到左地去掃描？答案是肯定的，這樣就是降序查詢的優化了，即使我們建索引的時候是按照升序來建的，cbo優化器也可以自動進行降序查詢優化。

下面是一個降序查詢的例子，在升序索引上的掃描，不論是升序查詢，還是降序查詢，都沒有額外的排序操作，而且cbo計算出來的cost開銷也是一緻的。

同理可知，如果我們建立的是降序索引，cbo優化器也會自動對升序查詢進行優化，同樣不會有額外的cost開銷。但是，降序索引上的升序掃描會被識别為降序操作。

是以，對于單列索引來說，沒有必要刻意建立降序索引，預設的升序索引是可以支援降序查詢的，并且自動優化，不會産生額外的cost開銷。

3.?複合索引的降序

如果說升序索引上進行降序查詢可以自動優化，那還需要降序索引幹什麼呢？它的作用主要表現在複合索引的應用上。

我們通過幾個例子來分析一下其應用場景，先清理掉之前的索引，在(b, c)列上建立一個複合索引。sql語句如下所示：

此時，在(b, c)列上進行(b asc, c asc)的排序操作，很顯然是不會有額外排序的，複合索引兩個索引列都是升序組織起來的。示例如下：

将排序條件修改一下，(b desc, c asc)，b列降序，c列升序。先來想象一下，此刻b列需要降序，cbo優化器可以自動優化，讓b列的從大到小地讀，也就是葉節點塊從右往左地掃描，這沒有問題。但不幸的是，c列則需要從左往右地掃描，這就發生沖突了。解決沖突的方式就是額外進行一次排序，示例如下所示：

我們說一切應從适合應用場景出發，如果應用場景中，經常要求(b desc, c asc)的排序方式，那我們就應該建立一個如下的降序索引：

新的索引建立完成，再來執行一下上面的兩個sql語句看看。此時的情況完全反過來了，(b desc, c asc)沒有額外排序，而(b asc, c asc)有了。

此處，我們不妨再引申一下。現在的索引順序是(b desc, c asc)，如果sql語句要求的排序輸出的方式變為(b asc, c desc)呢？如果你能像剛才一樣想象一下，就不難得到答案。此時，b列和c列都是要求從右往左地掃描索引葉節點塊，cbo優化器可以通過index range scan descending的方式優化執行計劃，其過程不會有額外的排序和cost開銷。示例如下所示：

降序索引在日常工作中，尤其是做報表和大資料分析應用的sql語句，應該能發揮比較積極和重要的作用。index range scan descending的掃描優化方式也不能忽略，這種優化方式對于index full scan同樣适用。

降序索引和降序掃描在索引的排序應用中有積極的意義。根據實際應用情況，選擇合适的索引組織形式，往往可以事半功倍的。

前面的章節中，我們提到count()的聚合查詢可以利用索引掃描來規避回表取數的動作，而且索引掃描過程也可以選擇index fast full scan的高效方式。現在，我們再來說說另一種聚合查詢min()與max()。這個和索引有關系嗎，能用到索引進行優化嗎？也許有讀者會說：“是的，但索引列必須要有not null的限制，或者在查詢過程中過濾掉null。”這個回答是值得鼓勵和肯定的。但是，另一個問題出來了，它能用到哪種索引掃描方式呢？像count()一樣，index fast full scan嗎？min()與max()是依賴于順序的，能接受不排序的輸出嗎？

下面的例子告訴我們，在主鍵索引列上的min()與max()，是可以用到索引快速全掃描的，而且cost下降比較明顯，達到了優化的目的。

我們說主鍵索引的鍵值具有唯一性，而且順序排列，這固然能用到index fast full scan，而如果是有重複性的非唯一索引呢？就隻能走index full scan了，甚至可能會因為cost太高，而選擇走全表掃描。

不知道有沒有讀者還沉浸在我們之前的想象中呢？如果有，相信你已經想象到了更好的優化方法。我們都知道索引的樹形結構，各層節點塊都是有序排列的，預設升序的情況下，從左到右即是從小到大，min()就是最左葉節點塊，max()則是最右葉節點塊。想象完成，通過執行個體來驗證一下吧。

從下面的例子可以看到，執行計劃變成了索引全掃描的方式，但是多了(min/max)的字樣。這是cbo優化器對索引全掃描的一個優化，其間蘊藏着一個stopkey的機制，簡單來說，就是掃描到需要的東西就退出，不繼續掃描了。執行計劃中index full scan (min/max)的cost開銷隻有2，較之index fast full scan更優。

細心的讀者應該注意到了，上面的sql語句隻做了min()，并沒有同時取min()與max()，同時取的話，是什麼效果呢？下面的例子告訴我們，仍然會走index fast full scan。原因很簡單，索引掃描隻能是單向的掃描，要麼從左到右，要麼從右到左，現在是需要同時傳回min()和max()，如果stopkey在取到min()退出，就取不到max()，反之亦然。是以，index full scan (min/max)就未被使用。

但事實上，從cost計算來看，即使單獨取一次min()，再單獨取一次max()，開銷之和都較索引快速全掃描要小。我們可以把sql語句改寫如下：

min()與max()通常是最常用的高頻sql寫法之一，特别是在一些計費系統和報表系統的應用中，這樣的寫法比比皆是。希望讀者能充分利用index full scan (min/max)這一蘊藏stopkey機制的特性來提高查詢性能，甚至可以通過改寫sql，将原本用不到該特性的查詢利用上，其間盡量保證該列為not null。

再多說一句關于stopkey特性的應用，在top-n的查詢或者分頁查詢中，它的作用是不容小觑的。示例如下所示：

綜上所述，索引的掃描和快速取數往往是大家建索引的目的，甚至有的時候會被認為是唯一的目的，而忽略掉了索引對排序的意義，是以丢失了原本應該更優的性能。通過本節的介紹，希望能對讀者有所啟示，能夠更全面地了解和思考索引的設計和使用。