OceanBase1.0排序優化演算法介紹

02-09

概述

本篇文章主要講述一下分散式資料庫中的排序優化演算法，之所以叫做優化演算法，是因為每種排序演算法分別是針對不同的排序場景量身定製的，較基礎的全排序有更好的性能。

sort的使用場景除業務本身顯示指定order by之外，它還用於group by、distinct、join、union等運算元的輔助實現，比如使用merge group by來實現groupby的時候需要下層額外分配一個sort，這部分是優化器生成邏輯執行計劃時添加的，實現時與顯式的sort無異。

sort在資料庫中作為一個運算元來實現，是一個需要物化的運算元，物化的概念在這裡是指需要將下層運算元傳遞上來的數據緩存下來，而不是像一些其它運算元拿到一行數據處理完就可以流水線一般一直向上傳遞，而它需要拿到所有的下層傳遞上來的數據才能進行本身的排序處理，排好之後才可以再向上層運算元吐數據。如此，對於排序的性能影響較大的主要有兩個方面，一個是排序本身，一個是深拷貝的過程。

針對這樣的性能問題，考慮不同的業務場景，幾種優化演算法應運而生。本文主要介紹以下兩種排序演算法：

topn-sort
分散式的多路歸併排序

（配圖為堆排，摘自網路）

topn-sort

介紹

一條sql秒懂topn-sort的應用場景：

select * from t1 order by c1 limit 10;

topn的問題通常是指從大數據量中獲得前n個滿足要求的數據，可以是近似的也可以是精確的，近似的演算法OceanBase也是有的，在OceanBase裡面叫做topk。這裡主要講精確的前n個，用於order by + limit 的場景，這是比較常用的，用戶往往會關注最xx的事情，比如你想知道偷你能量最多是哪幾個人。

實現

topn由n大小的堆實現，下層運算元吐出來的數據未達到n行數據時，直接放入heap_array中，這裡會做深拷貝，直到拿到了n行數據後，創建n大小的堆，小頂還是大頂根據排序要求來定。之後再拿到數據就會去更新這個堆，根據與堆頂數據的一次比較決定是直接丟掉還是放入堆中，直到更新完所有的數據。

以取前n大的數據為例：

性能提升與不足

從演算法時間複雜度來看，全排序為NlogN, topn為N1logn, N1最壞等於N。
topn不需要壓縮存，基礎全排序使用了壓縮存儲。數據均勻的情況下，topn只需要部分深拷貝。
topn現在未實現外排，後面會支持。根據實測，考慮時間和內存，在使用方面對n做了一定的限制，在小於某個比例和數值的時候才會使用。

分散式的多路歸併排序merge-sort

介紹

多路歸併排序也被應用於基礎排序的外排中，對於數據量比較大內存中放不下的情況，會分成多份放在文件中，向上返回數據時按照多份數據源進行歸併。這裡的應用場景為分區表的排序，需要每個分區按照鍵值是有序的，每一個數據源對應一個分區的數據返回。

select * from t1 order by c1;

比如這樣的一條簡單的sql, t1是分區表，沒有merge-sort的情況，需要把每個分區的數據拉上來，做一次全排序。使用merge-sort，如果c1本來就是主鍵或者存儲層走的索引，每個分區原本就是有序的，那麼只需要在上層做一次歸併排序即可，如果分區無序，可以把order by c1下壓到每一個分區去做排序，最後再做一次歸併排序，兩種情況都會比全排序的性能好。

實現

從中間結果管理器中拉取每一個分區的數據序列化好放在rowstore(可以壓縮存儲row的一個結構)中，對於每一個分區的數據可以看作一個數據源，每個數據源取一行組成一個k大小的堆，由上層運算元驅動，迭代返回堆頂的數據，每返回一行數據，要從對應的數據源中補回一行，重新調整堆。

性能提升

需要全排序的情況，分區有序，演算法複雜度由NLOGN降到NLOGK, K指分區表的數量；分區無序，由NLOGN到KLOGN/K+NLOGK。上層有limit n時，只需要迭代n次就可以。
所有的數據都會在rowstore中存儲，所以處理過程中不需要深拷貝，與全排序相比，少了N行深拷貝的時間。
沒有merge-sort時，做order by的下壓是沒有意義的，實現merge-sort之後，可以將order by以及limit+order by下壓到每個分區去做，某些場景大大減少了數據的拉取和處理。

sql使用展示

topn-sort

OceanBase (root@oceanbase)> create table t1 (a int, b int, primary key(a));Query OK, 0 rows affected (0.05 sec)OceanBase (root@oceanbase)> explain select * from t1 order by b limit 10;| =====================================|ID|OPERATOR |NAME|EST. ROWS|COST|-------------------------------------|0 |LIMIT | |10 |1695||1 | TOP-N SORT | |1000 |1685||2 | TABLE SCAN|t1 |1000 |1180|=====================================Outputs & filters:------------------------------------- 0 - output([t1.a], [t1.b]), filter(nil), limit(10), offset(nil) 1 - output([t1.a], [t1.b]), filter(nil), sort_keys([t1.b, ASC]), topn(10) 2 - output([t1.a], [t1.b]), filter(nil), access([t1.a], [t1.b]), partitions(p0)

merge-sort

OceanBase (root@oceanbase)> CREATE TABLE t (c1 INT NOT NULL AUTO_INCREMENT, PRIMARY KEY(c1, c2), -> c2 INT) PARTITION BY HASH(c2) PARTITIONS 4;Query OK, 0 rows affected (0.08 sec)OceanBase (root@oceanbase)> select * from t order by c1;+------+----+| c1 | c2 |+------+----+| -128 | 40 || -127 | 30 || 1 | 10 || 2 | 20 |+------+----+4 rows in set (0.01 sec)OceanBase (root@oceanbase)> explain select * from t order by c1;| ================================================|ID|OPERATOR |NAME|EST. ROWS|COST|------------------------------------------------|0 |EXCHANGE IN MERGE DISTR| |4000 |2880||1 | EXCHANGE OUT DISTR | |4000 |1180||2 | TABLE SCAN |t |4000 |1180|================================================Outputs & filters:------------------------------------- 0 - output([t.c1], [t.c2]), filter(nil), sort_keys([t.c1, ASC]) 1 - output([t.c2], [t.c1]), filter(nil), hash(nil) 2 - output([t.c2], [t.c1]), filter(nil), access([t.c2], [t.c1]), partitions(p[0-3])

總結

優化無止境，性能對資料庫來講至關重要，不放過每一個可以優化的性能點，精益求精，這也是OceanBase逐步邁入一個成熟資料庫的必經之路。路漫漫其修遠兮，吾將上下而求索～

（作者OBer)