使用 Horoscope 測試 TiDB 優(yōu)化器

千鋒Python學堂 2020-08-24

展開全文

優(yōu)化器在數(shù)據(jù)庫中一直位于至關重要的位置，性能調優(yōu)也常常需要圍繞優(yōu)化器來進行。作為數(shù)據(jù)庫廠商，我們希望在各類復雜的業(yè)務場景中，TiDB 都能夠給出比較理想的執(zhí)行計劃，因此在優(yōu)化器和執(zhí)行器上做了非常多的工作和努力，但是選錯執(zhí)行計劃或者索引的情況仍然是日常中最為常見的一個問題。

優(yōu)化器有關的問題可以簡單歸結為兩種：

統(tǒng)計信息準確的情況下給出了錯誤的執(zhí)行計劃。
另一類則是在統(tǒng)計信息過期的情況下給錯了執(zhí)行計劃。

選錯索引是其中比較常見的一種情況，用戶希望添加索引來加速查詢速度，某些情況下，優(yōu)化器可能會走到全表掃的物理執(zhí)行計劃或者選錯索引使得實際執(zhí)行效果退化成全表掃的情況。

針對上述情況，我們需要從更微觀的層面來度量優(yōu)化器的執(zhí)行計劃和索引選擇的性能，評估在優(yōu)化器上做的改進工作能否切實起到期望的效果。

為什么我們要開發(fā) Horoscope?

為了測量優(yōu)化器和執(zhí)行器，從去年開始我們構建了daily benchmark 平臺 perf.pingcap.com，覆蓋常見的幾種復雜查詢的測試場景，包含 TPC-H、TPC-DS、Star Schema Benchmark 等，跟蹤每天開發(fā)分支上這些查詢的執(zhí)行速度情況。

使用 Horoscope 測試 TiDB 優(yōu)化器

通過 daily benchmark，我們觀測和定位到了若干次性能提升以及性能回退的情況。有些提升或者回退是優(yōu)化器組件上的優(yōu)化導致的，有些則是 TiDB 其他組件，或者存儲層引發(fā)的。

雖然 daily benchmark 能夠觀測到性能改進或者回退，但是對于以下幾個問題它卻束手無策：

當前選擇的執(zhí)行計劃是否最優(yōu)？選擇率估計是否準確？
是否選擇到了正確的索引？
現(xiàn)有的啟發(fā)算法能否應對統(tǒng)計信息一定程度的過期？

因此，我們需要另外一種更系統(tǒng)的測試工具，用于優(yōu)化器的測量。

Horoscope 是如何做的?

要測量優(yōu)化器，我們需要：

定義優(yōu)化器的性能指標
遍歷執(zhí)行計劃空間
數(shù)據(jù)集以及查詢生成

定義優(yōu)化器的性能指標

這里我們參考“OptMark: A Toolkit for Benchmarking Query Optimizers”給出的方法來度量優(yōu)化器有效性。簡單地講某個查詢的有效性指標，是指在可遍歷的執(zhí)行計劃空間中，優(yōu)化器選出的默認執(zhí)行計劃的執(zhí)行時間比其他的執(zhí)行計劃的執(zhí)行時間更快的比例。

例如 100% 可以解釋為默認執(zhí)行計劃的執(zhí)行時間比其他執(zhí)行計劃的執(zhí)行時間都更快，50% 解釋為有一半的執(zhí)行計劃要比默認執(zhí)行計劃更快。

遍歷執(zhí)行計劃空間

由于需要一種方式能夠讓 TiDB 按照我們所指定的物理執(zhí)行計劃來實際執(zhí)行查詢，為此我們在 TiDB 中添加了 nth_plan(n) 這個 SQL hint。

當查詢語句提交到 TiDB 后，TiDB 會為搜索空間中的每個執(zhí)行計劃綁定一個固定的序號，通過這個序號我們就能指定優(yōu)化器去選擇哪一個執(zhí)行計劃。

nth_plan 的序號從 1 開始遞增，當其超出優(yōu)化器對該條查詢的搜索空間時，查詢返回會產(chǎn)生一個 warning 來提示當前已經(jīng)完成了搜索空間上的遍歷。

TiDB(root@127.0.0.1:test) > explain select /*+ nth_plan(1) */ * from t where a = 1 and b > 0 and b < 10;
+-------------------------+----------+-----------+---------------+----------------------------------------------------+
| id                      | estRows  | task      | access object | operator info                                      |
+-------------------------+----------+-----------+---------------+----------------------------------------------------+
| TableReader_7           | 0.25     | root      |               | data:Selection_6                                   |
| └─Selection_6           | 0.25     | cop[tikv] |               | eq(hehe.t.a, 1), gt(hehe.t.b, 0), lt(hehe.t.b, 10) |
|   └─TableFullScan_5     | 10000.00 | cop[tikv] | table:t       | keep order:false, stats:pseudo                     |
+-------------------------+----------+-----------+---------------+----------------------------------------------------+
3 rows in set (0.00 sec)

TiDB(root@127.0.0.1:test) > explain select /*+ nth_plan(2) */ * from t where a = 1 and b > 0 and b < 10;
+-------------------------------+---------+-----------+-------------------------+---------------------------------------------+
| id                            | estRows | task      | access object           | operator info                               |
+-------------------------------+---------+-----------+-------------------------+---------------------------------------------+
| IndexLookUp_11                | 0.25    | root      |                         |                                             |
| ├─IndexRangeScan_8(Build)     | 10.00   | cop[tikv] | table:t, index:idx_a(a) | range:[1,1], keep order:false, stats:pseudo |
| └─Selection_10(Probe)         | 0.25    | cop[tikv] |                         | gt(hehe.t.b, 0), lt(hehe.t.b, 10)           |
|   └─TableRowIDScan_9          | 10.00   | cop[tikv] | table:t                 | keep order:false, stats:pseudo              |
+-------------------------------+---------+-----------+-------------------------+---------------------------------------------+
4 rows in set (0.00 sec)

數(shù)據(jù)集以及查詢生成

互聯(lián)網(wǎng)上有很多開放的數(shù)據(jù)集，也有一些 benchmark 提供了 dbgen 工具用來隨機構造數(shù)據(jù)集，我們比較傾向于選擇真實數(shù)據(jù)集，因此我們選擇了 IMDB 數(shù)據(jù)集來進行測試。

有了數(shù)據(jù)集，我們需要在其上構造一些查詢。為了測試索引選擇問題，參考 Manuel Rigger 的 “Testing Database Engines via Pivoted Query Synthesis” 論文中的思路，Horoscope 會在某些表中隨機選擇一行數(shù)據(jù)作為 pivot row 去構建查詢，使得查詢返回的結果會包含這些選擇的行。通過這種方式，我們能保證生成的查詢是更具意義。

例如針對索引選擇問題，查詢構造的流程如下所示，通過在有索引覆蓋的列上構造條件來測試是否選對了索引。

使用 Horoscope 測試 TiDB 優(yōu)化器

例如會生成如下的查詢：

使用 Horoscope 測試 TiDB 優(yōu)化器

開始測量

我們預先導入了一份 IMDB 數(shù)據(jù)集到 imdb 數(shù)據(jù)庫中，可以通過如下命令使用 Join Order Benchmark 的查詢度量有效性指標。

$ git clone https://github.com/chaos-mesh/horoscope.git 
$ cd horoscope && make 
$ ./bin/horo --round 4 -d root:@tcp(localhost:4000)/imdb?charset=utf8 bench -p -w benchmark/job

經(jīng)過漫長的等待，在測量結束時 Horoscope 會出入一份測試報告：

使用 Horoscope 測試 TiDB 優(yōu)化器

ID 列標識查詢的名稱，#PLAN SPACE 是這條查詢當前 TiDB 的搜索空間，DEFAULT EXECUTION TIME 記錄了默認執(zhí)行計劃的執(zhí)行時間（通過中值以及上下界偏差比例給出），BEST PLAN EXECUTION TIME 給出最優(yōu)的執(zhí)行計劃的執(zhí)行時間，EFFECTIVENESS 算出該條查詢優(yōu)化器的有效性，BETTER OPTIMAL PLANS 給出更優(yōu)的執(zhí)行計劃的 ID 以及對應執(zhí)行時間和默認執(zhí)行計劃執(zhí)行時間的占比。

我們使用 Horoscope 測量了不同數(shù)量級的 TPC-H，并且 IMDB 數(shù)據(jù)集上針對索引選擇生成了一些查詢來測試。我們也在 Github 上創(chuàng)建了一個項目來跟蹤這些問題的進展：https://github.com/orgs/pingcap/projects/29

相比于 TPC-H，Horoscope 在 IMDB 的數(shù)據(jù)集和查詢上發(fā)現(xiàn)了更多更優(yōu)的執(zhí)行計劃，但因為 IMDB 數(shù)據(jù)是靜態(tài)的，當想驗證統(tǒng)計信息過期場景下優(yōu)化器的情況時比較困難。

為此 Horoscope 提供了將數(shù)據(jù)按照某個字段進行切分然后導出的功能，通過分批次插入數(shù)據(jù)，提供了數(shù)據(jù)更新情況下的優(yōu)化器測試場景。

數(shù)據(jù)切片和按切片更新數(shù)據(jù)

真實數(shù)據(jù)集上的數(shù)據(jù)分布往往具備傾斜的特征，而這種傾斜的性質對于優(yōu)化器也更有挑戰(zhàn)。

以 IMDB 為例，數(shù)據(jù)在 title.produciton_year 上發(fā)生了傾斜，越靠后的年份，所關聯(lián)的數(shù)據(jù)行數(shù)越多。我們通過對數(shù)據(jù)集在 title.prodution_year 上將數(shù)據(jù)集切分成一塊塊不均等的切片，再進行分批導入，可以模擬數(shù)據(jù)修改所引發(fā)的統(tǒng)計信息過期對于優(yōu)化器的影響。

切分的過程如下：

將各個表之間的關系通過主外鍵進行關聯(lián)，構造出一張無向圖；
選擇某個表上的字段，查詢出其上不同的值；
以這個字段的值作為線索，構造查詢語句，在無向圖上串聯(lián)不同表上能關聯(lián)到的數(shù)據(jù)，導出到切片文件中；
標記串聯(lián)過的數(shù)據(jù)，后續(xù)切片忽略已標記過的數(shù)據(jù)。

在 IMDB 上，我們選擇 title.produciton_year 進行數(shù)據(jù)切分，切分后每個切片文件的大小如下圖所示。

使用 Horoscope 測試 TiDB 優(yōu)化器

約有一半的數(shù)據(jù)集中在最后 20 份切片中，越往后導入數(shù)據(jù)的修改行增速越快，統(tǒng)計信息的過期速度也愈快。

我們設計了 2 個對照試驗，實驗開始之前預先導入切片 0 到切片 124 的數(shù)據(jù)，并從切片 125 開始，每導入一個切片，測量一輪各查詢的有效性指標。

在第一組試驗中我們關閉了 auto analyze 和 feedback，第二組關閉了 auto analyze 但會打開 feedback。然后讓 Horoscope 隨機生成一批簡單查詢，在得到數(shù)據(jù)后我們分別繪制了有效性指標的比例曲線以及散點圖。

使用 Horoscope 測試 TiDB 優(yōu)化器

曲線上的點表示有效性指標大于橫坐標數(shù)值的查詢的比例。從數(shù)據(jù)上看，當打開 feedback 時，有 50.77% 查詢的有效性指標超過了 80%，即對于一半以上的查詢優(yōu)化器選擇到了較優(yōu)的執(zhí)行計劃。而當關閉 feedback 時，這個比例只有 38.70%。這和我們通常所認為的 feedback 能夠一定程度抵抗統(tǒng)計信息過期相符。

另外從散點圖上看會發(fā)現(xiàn)打開 feedback 也有可能會讓優(yōu)化器選擇到更差的執(zhí)行計劃。例如下面的這條 SQL，feedback 機制反而使優(yōu)化器選擇到了更差的執(zhí)行計劃，這些可以作為 bad case 來具體分析。

SELECT *
FROM title
WHERE (title.id IS NOT NULL
       AND title.title!="(#1.69)"
       AND title.imdb_index IS NULL
       AND title.kind_id<8
       AND title.production_year!=1974
       AND title.imdb_id IS NULL
       AND title.phonetic_code IS NULL
       AND title.episode_of_id>184590
       AND title.season_nr IS NULL
       AND title.episode_nr IS NULL
       AND title.series_years IS NULL
       AND title.md5sum<="7cf95ddbd379fdb3e530e0721ff61494")
LIMIT 100

使用 Horoscope 測試 TiDB 優(yōu)化器

后記

Horoscope 還可以做更多的事情，例如當版本升級時，可以用 Horoscope 來測試執(zhí)行計劃會不會變化，如果變化了，是否發(fā)生了回退。

用戶線上的數(shù)據(jù)通常十分敏感，我們內部積累了比較多的有統(tǒng)計信息和 schema 但無實際數(shù)據(jù)的用例集，通過 Horoscope 我們現(xiàn)在希望能夠將這些用例集利用起來，擴充優(yōu)化器測試用例，來幫助優(yōu)化器的開發(fā)者們決策一些優(yōu)化策略是否要合并到下一版本中。

此外，Horoscope 也提供了一種測試優(yōu)化器正確性的途徑。我們正在計劃讓 Horoscope 生成更復雜的查詢，通過比對每個物理執(zhí)行計劃的結果來驗證優(yōu)化器實現(xiàn)的正確性。

優(yōu)化器的工作是個長期且難度非常大的事情，優(yōu)化器的測試也是如此，如果您有更多更好的關于優(yōu)化器或者其他組件的優(yōu)化以及測試的方法或者思路，歡迎在 TiDB 社區(qū)中和我們進行交流。