MySQL遇到AI：字節(jié)跳動開源 MySQL 虛擬索引 VIDEX
虛擬索引技術(shù)（virtual index，也稱為 hypothetical index）在數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化、索引推薦等場景中扮演著關(guān)鍵角色。簡單來說，虛擬索引可以理解為數(shù)據(jù)庫的'沙盤推演'系統(tǒng)——無需真實構(gòu)建索引，僅基于統(tǒng)計信息即可精準模擬不同索引方案對查詢計劃的優(yōu)化效果。由于虛擬索引的創(chuàng)建/刪除代價極低，使用者可以大量創(chuàng)建和刪除索引、反復(fù)推演，確定最有效的索引方案。在AI時代，基于機器學(xué)習(xí)模型的NDV、Cardinality估計算法層出不窮，但是在MySQL落地往往遇到很大挑戰(zhàn)：無法注入機器學(xué)習(xí)模型的預(yù)測值，便無法得到MySQL索引推薦結(jié)果。
業(yè)界許多數(shù)據(jù)庫已經(jīng)以官方或第三方的方式提供了虛擬索引功能，例如 Postgres（https://github.com/HypoPG/hypopg ）、Oracle（https://oracle-base.com/articles/misc/virtual-indexes ）和 IBM DB2（https://www.ibm.com/docs/en/db2-for-zos/12?topic=tables-dsn-virtual-indexes ）。大量數(shù)據(jù)庫領(lǐng)域的研究都圍繞虛擬索引技術(shù)展開。遺憾的是，MySQL 長期缺乏這一能力，導(dǎo)致其在復(fù)雜場景下的優(yōu)化效果始終受限。
經(jīng)過長期的生產(chǎn)驗證，字節(jié)跳動正式開源了 MySQL 虛擬索引項目 VIDEX（Virtual Index ），讓 MySQL 也有了自己的虛擬索引機制 ??
VIDEX 開源地址：https://github.com/bytedance/videx
VIDEX 已經(jīng)部署在了字節(jié)跳動大規(guī)模生產(chǎn)系統(tǒng)中，每天為數(shù)千用戶、數(shù)十萬慢 SQL 提供優(yōu)化服務(wù)。VIDEX 的實用價值、工業(yè)級部署設(shè)計等特點，引來 Daniel Black（MariaDB Foundation 首席創(chuàng)新官）和Federico Razzoli (Founder of Vettabase) 等業(yè)界知名專家的點贊與認可。
VIDEX 提供開箱即用的虛擬索引能力，可無縫集成至現(xiàn)有 MySQL 生態(tài)；對于數(shù)據(jù)庫研究者，VIDEX 模塊化設(shè)計允許新算法（如 NDV 估計、Cardinality估計等等）在 MySQL 上快速驗證，推動前沿技術(shù)落地。
具體來說，VIDEX 的貢獻如下：
彌補 MySQL 虛擬索引空白：盡管業(yè)界已經(jīng)有多種數(shù)據(jù)庫支持了虛擬索引功能（ Postgres、Oracle、 IBM DB2），也有一些論文和博客提到了 MySQL 的虛擬索引技術(shù) [1,2]，但據(jù)我們所知，VIDEX 是首個開源的、可拓展、支持多形態(tài)部署的 MySQL 虛擬索引解決方案。
高精度地擬合 MySQL：我們已經(jīng)在 TPC-H、TPC-H-Skew 和 JOB 等復(fù)雜分析基準測試上對 VIDEX 進行了測試。給定準確的獨立值估計（ndv） 和基數(shù)估計（Cardinality） 信息，VIDEX 可以 100% 模擬 MySQL InnoDB 的查詢計劃。
基于分離架構(gòu)的多形態(tài)部署：VIDEX 實現(xiàn)了數(shù)據(jù)庫實例-VIDEX優(yōu)化器插件-VIDEX算法服務(wù)的模塊分離。既支持作為插件無縫集成到現(xiàn)有MySQL實例，也可作為獨立服務(wù)構(gòu)建虛擬庫環(huán)境，實現(xiàn)生產(chǎn)環(huán)境零干擾的索引驗證；額外地，將 VIDEX優(yōu)化器插件和VIDEX算法服務(wù)也做了分離，便于 AI 算法服務(wù)的集成和熱更新。
可拓展的實驗平臺：準確地模擬MySQL查詢代價依賴于對獨立值（ndv）和基數(shù)（Cardinality）的準確估計——這正是AI+數(shù)據(jù)庫研究中最火熱的方向之一 [3]。VIDEX 給出了標準化、清晰易懂的接口設(shè)計，屏蔽了復(fù)雜的系統(tǒng)細節(jié)。研究者可以自由地用各種語言來重寫 VIDEX 的算法模型，甚至只需要改動一個 JSON 文件，就能將自己的新算法應(yīng)用于 MySQL查詢優(yōu)化器！
多形態(tài)部署：從實驗平臺到生產(chǎn)環(huán)境
由于 VIDEX 將真實數(shù)據(jù)庫實例、虛擬數(shù)據(jù)庫實例、算法服務(wù)器三個部分解耦了，因此可以靈活應(yīng)用于各種適用場景，從個人研究到生產(chǎn)環(huán)境部署：
VIDEX-Optimizer 的兩種形態(tài)
作為插件安裝到真實數(shù)據(jù)庫：將 VIDEX 作為插件安裝到真實數(shù)據(jù)庫實例，這樣只需要一臺 MySQL實例，即可體驗基于虛擬索引的各種 what-if 分析。適合于個人實驗和分析。
以獨立實例啟動：獨立啟動 VIDEX 示例，同步統(tǒng)計信息，然后開始分析。此模式可以完全避免影響在線運行實例的穩(wěn)定性，在工業(yè)環(huán)境中很實用。
VIDEX 算法服務(wù)器的兩種形態(tài)
與 VIDEX-Optimizer 配套啟動：最經(jīng)典的方式，無須額外設(shè)置，VIDEX-Optimizer 會自動尋找本地啟動的VIDEX算法服務(wù)器。
獨立啟動算法服務(wù)器：只要設(shè)置一下 SQL 環(huán)境變量（SET @VIDEX_STATISTIC_SERVER='ip:port'），VIDEX-Optimizer 會將算法請求轉(zhuǎn)發(fā)到指定的算法服務(wù)器上。對于研究者來說，可以自由實現(xiàn)算法、啟動自定義的算法服務(wù)；對于云原生場景，可以將大量 MySQL 實例的算法請求發(fā)往中心式的算法服務(wù)，便于運維和快速更新。
VIDEX 任務(wù)的兩種形態(tài)
非任務(wù)模式：默認情況下，用戶不需要關(guān)注 “task_id” —— 只需要指定目標庫、指定虛擬庫，同步數(shù)據(jù)即可；
任務(wù)模式：在大規(guī)模分析任務(wù)中（例如大規(guī)模索引推薦任務(wù)），各種用戶往往會對同一個生產(chǎn)庫的不同表、或不同實例的同名表發(fā)起多次分析。這種情況下，用戶可以指定任務(wù) id（SET @VIDEX_OPTIONS={'task_id': 'abc'}），讓多個任務(wù)彼此互不影響。
算法試驗場：把算法模型接入 MySQL 優(yōu)化器
MySQL 采用了分離式的架構(gòu)，上層的查詢優(yōu)化器會向下層存儲引擎請求各種信息，包括元數(shù)據(jù)信息（table_rows、data_length 等等）、獨立值（ndv）、基數(shù)（cardinality）、索引內(nèi)存加載率等等。其中基數(shù)估計和獨立值估計是 AI for DB 研究領(lǐng)域的熱點方向。現(xiàn)已有大量 data-driven 或者 query-driven 的算法被提出，但這些算法往往只能以 PostgreSQL 作為試驗場。
VIDEX 讓用戶不必與 MySQL 查詢優(yōu)化器做交互、也屏蔽了 MySQL 對庫表元數(shù)據(jù)信息（table_rows、deta_length）的請求。由此，用戶可以專注于一些重點的算法問題，例如 NDV 估計和 Cardinality 估計。
方法 1：在 VIDEX-Statistic-Server 中添加一種新方法
考慮到許多研究者習(xí)慣于用 Python 研究各種 AI 與 DB 結(jié)合的算法，因此，我們用Python 實現(xiàn)了 VIDEX-Statistic。
用戶可以繼承并修改 VidexModelInnoDB。VidexModelInnoDB 為用戶屏蔽了系統(tǒng)變量、索引元數(shù)據(jù)格式等復(fù)雜細節(jié)，并提供了一個基于獨立、均勻分布假設(shè)的 ndv 和 cardinality 算法。這樣用戶可以聚焦于 cardinality 和 ndv 這兩個研究熱點：
class VidexModelBase(ABC): """ Abstract cost model class. VIDEX-Statistic-Server receives requests from VIDEX-Optimizer for Cardinality and NDV estimates, parses them into structured data for ease use of developers. Implement these methods to inject Cardinality and NDV algorithms into MySQL. """ @abstractmethod def cardinality(self, idx_range_cond: IndexRangeCond) -> int: """ Estimates the cardinality (number of rows matching a criteria) for a given index range condition. Parameters: idx_range_cond (IndexRangeCond): Condition object representing the index range. Returns: int: Estimated number of rows that match the condition. Example: where c1 = 3 and c2 < 3 and c2 > 1, ranges = [RangeCond(c1 = 3), RangeCond(c2 < 3 and c2 > 1)] """ pass @abstractmethod def ndv(self, index_name: str, table_name: str, column_list: List[str]) -> int: """ Estimates the number of distinct values (NDV) for specified fields within an index. Parameters: index_name (str): Name of the index. table_name (str): Table Name column_list (List[str]): List of columns(aka. fields) for which NDV is to be estimated. Returns: int: Estimated number of distinct values. Example: index_name = 'idx_videx_c1c2', table_name= 't1', field_list = ['c1', 'c2'] """ raise NotImplementedError()
class VidexModelBase(ABC):
"""
Abstract cost model class. VIDEX-Statistic-Server receives requests from VIDEX-Optimizer for Cardinality
and NDV estimates, parses them into structured data for ease use of developers.
Implement these methods to inject Cardinality and NDV algorithms into MySQL.
"""
@abstractmethod
def cardinality(self, idx_range_cond: IndexRangeCond) -> int:
"""
Estimates the cardinality (number of rows matching a criteria) for a given index range condition.
Parameters:
idx_range_cond (IndexRangeCond): Condition object representing the index range.
Returns:
int: Estimated number of rows that match the condition.
Example:
where c1 = 3 and c2 < 3 and c2 > 1, ranges = [RangeCond(c1 = 3), RangeCond(c2 < 3 and c2 > 1)]
"""
pass
@abstractmethod
def ndv(self, index_name: str, table_name: str, column_list: List[str]) -> int:
"""
Estimates the number of distinct values (NDV) for specified fields within an index.
Parameters:
index_name (str): Name of the index.
table_name (str): Table Name
column_list (List[str]): List of columns(aka. fields) for which NDV is to be estimated.
Returns:
int: Estimated number of distinct values.
Example:
index_name = 'idx_videx_c1c2', table_name= 't1', field_list = ['c1', 'c2']
"""
raise NotImplementedError()假設(shè)用戶用 VidexModelExample 重載了 VidexModelInnoDB ，可以指定模然后啟動 VIDEX-Statistic-Server（詳見代碼啟動腳本）。
startup_videx_server(VidexModelClass=VidexModelExample)
startup_videx_server(VidexModelClass=VidexModelExample)方法 2: 全新實現(xiàn) VIDEX-Statistic-Server
用戶可以用任何編程語言實現(xiàn) HTTP 響應(yīng)、并在任意位置啟動 VIDEX-Statistic。
使用時，只需要指定環(huán)境變量（SET @VIDEX_STATISTIC_SERVER='ip:port'），VIDEX-Optimizer 就會將所有請求轉(zhuǎn)發(fā)到指定服務(wù)上。
兩步玩轉(zhuǎn) VIDEX，在 TPC-H 上看看效果
步驟 1: Docker 啟動 VIDEX
最簡單的情況下，用戶可以用 Docker 啟動一個安裝好 VIDEX-Optimizer 和 VIDEX-Statistic 的容器。用戶也可以參考文檔說明，嘗試其他啟動方式。
為簡化部署，我們提供了預(yù)編譯的 Docker 鏡像，包含:
- VIDEX-Optimizer: 基于 Percona-MySQL 8.0.34-26
（https://github.com/percona/percona-server/tree/release-8.0.34-26），并集成了 VIDEX 插件 - VIDEX-Statistic: ndv 和 cardinality 算法服務(wù)
如果您尚未安裝 Docker:
- Docker Desktop for Windows/Mac（https://www.docker.com/products/docker-desktop/）
- Linux: 參考官方安裝指南（https://docs.docker.com/engine/install/）
docker run -d -p 13308:13308 -p 5001:5001 --name videx kangrongme/videx:0.0.2步驟 2: VIDEX 數(shù)據(jù)準備
VIDEX 需要 Python 3.9 環(huán)境，執(zhí)行元數(shù)據(jù)采集等任務(wù)。我們推薦使用 Anaconda/Miniconda 創(chuàng)建獨立的 Python 環(huán)境來安裝，詳見 README 文檔的 Quick Start 章節(jié)（https://github.com/bytedance/videx?tab=readme-ov-file#2-quick-start）：
git clone git@github.com:bytedance/videx.git videx_statistic
git clone git@github.com:bytedance/videx.git videx_statistic
cd videx_statistic
python3.9 -m pip install -e . --use-pep517指定原庫和 VIDEX 庫地址，用腳本一鍵式同步數(shù)據(jù)（以 tpch 為例）：
python src/sub_platforms/sql_opt/videx/scripts/videx_build_env.py \
python src/sub_platforms/sql_opt/videx/scripts/videx_build_env.py \
--target 127.0.0.1:13308:tpch_tiny:videx:password \
--videx 127.0.0.1:13308:videx_tpch_tiny:videx:password效果展示：以 TPC-H 為例
本示例使用 TPC-H 數(shù)據(jù)集演示 VIDEX 的完整使用流程。
假設(shè)用戶已經(jīng)準備好了 TPCH 數(shù)據(jù)。篇幅限制，我們將更詳細的步驟說明放到了 README 文檔的 Example 章節(jié)（https://github.com/bytedance/videx?tab=readme-ov-file#3-examples）。
為了展示 VIDEX 的有效性，我們對比了 TPC-H Q21 的 EXPLAIN 細節(jié)，這是一個包含四表連接的復(fù)雜查詢，涉及 WHERE、聚合、ORDER BY、GROUP BY、EXISTS 和 SELF-JOIN 等多種部分。初始情況下，MySQL 可以選擇的索引有 11 個，分布在 4 個表上。
EXPLAIN FORMAT = JSON
SELECT s_name, count(*) AS numwait
FROM supplier,
lineitem l1,
orders,
nation
WHERE s_suppkey = l1.l_suppkey
AND o_orderkey = l1.l_orderkey
AND o_orderstatus = 'F'
AND l1.l_receiptdate > l1.l_commitdate
AND EXISTS (SELECT *
FROM lineitem l2
WHERE l2.l_orderkey = l1.l_orderkey
AND l2.l_suppkey <> l1.l_suppkey)
AND NOT EXISTS (SELECT *
FROM lineitem l3
WHERE l3.l_orderkey = l1.l_orderkey
AND l3.l_suppkey <> l1.l_suppkey
AND l3.l_receiptdate > l3.l_commitdate)
AND s_nationkey = n_nationkey
AND n_name = 'IRAQ'
GROUP BY s_name
ORDER BY numwait DESC, s_name;讓我們來對比 VIDEX 和 InnoDB 的估計效果。我們使用 EXPLAIN FORMAT=JSON，這是一種更加嚴格的格式。
我們不僅比較表連接順序和索引選擇，還包括查詢計劃的每一個細節(jié)（例如每一步的行數(shù)和代價）。
如下圖所示，VIDEX（左圖）能生成一個與 InnoDB（右圖）幾乎 100% 相同的查詢計劃。
VIDEX 的一個重要作用是模擬索引代價。我們額外新增一個索引。VIDEX 增加索引的代價是 O(1) ，因為他并不需要在真實數(shù)據(jù)上創(chuàng)建索引：
-- 為 innodb 庫創(chuàng)建索引ALTER TABLE tpch_tiny.orders ADD INDEX idx_o_orderstatus (o_orderstatus);-- 為 videx 創(chuàng)建索引ALTER TABLE videx_tpch_tiny.orders ADD INDEX idx_o_orderstatus (o_orderstatus);
-- 為 innodb 庫創(chuàng)建索引
ALTER TABLE tpch_tiny.orders ADD INDEX idx_o_orderstatus (o_orderstatus);
-- 為 videx 創(chuàng)建索引
ALTER TABLE videx_tpch_tiny.orders ADD INDEX idx_o_orderstatus (o_orderstatus);再次執(zhí)行 EXPLAIN，我們看到 MySQL-InnoDB 和 VIDEX 的查詢計劃發(fā)產(chǎn)生了相同的變化，兩個查詢計劃均采納了新索引，并且查詢計劃的細節(jié)也非常接近。
VIDEX 的行數(shù)估計 (7404) 與 MySQL-InnoDB (7362) 相差約為
0.56%，這個誤差來自于基數(shù)估計算法的誤差。
深入解析 VIDEX 架構(gòu)
如圖展現(xiàn)了 VIDEX 的架構(gòu)。總體來說，VIDEX 包含兩個模塊：
- VIDEX-Optimizer-Plugin（簡稱 VIDEX-Optimizer）：VIDEX 的“前端”。可以作為插件安裝到現(xiàn)有數(shù)據(jù)庫，或者以一個獨立的新實例啟動。這一部分實現(xiàn)了 MySQL 查詢優(yōu)化器接口，并將其中一部分復(fù)雜的請求轉(zhuǎn)發(fā)到 VIDEX-Statistic-Server。我們?nèi)媸崂砹?MySQL handler 的超過90個接口函數(shù)，并實現(xiàn)與索引（Index）相關(guān)的接口。
- VIDEX-Statistic-Server（簡稱 VIDEX-Statistic）：VIDEX 的“后端”。基于收集到的統(tǒng)計信息（表行數(shù)、表大小、直方圖等等）和集成的算法或模型，計算獨立值（NDV） 和基數(shù)（Cardinality），并將結(jié)果返回給 VIDEX-Optimizer。
當用戶指定了要分析（what-if analysis）的真實數(shù)據(jù)庫之后，VIDEX 會在 VIDEX-Optimizer 上創(chuàng)建一個虛擬數(shù)據(jù)庫。虛擬數(shù)據(jù)庫與真實數(shù)據(jù)庫的關(guān)系表結(jié)構(gòu)完全一致，只是將 Engine 從 InnoDB 更換為 VIDEX。為了準確模擬目標數(shù)據(jù)庫的查詢代價，VIDEX 會調(diào)用腳本，從真實數(shù)據(jù)庫采集必要的統(tǒng)計信息。上述過程都可以用我們提供好的腳本一鍵式完成。
用戶也可以自定義地提供一份元數(shù)據(jù)文件、讓腳本直接導(dǎo)入。元數(shù)據(jù)文件是 json 格式，包含了庫表結(jié)構(gòu)信息、統(tǒng)計信息（table_rows、單列 ndv等等）、直方圖信息，非常容易理解。
VIDEX-Statistic-Server 是 VIDEX 的算法服務(wù)器。我們已經(jīng)提供了基于獨立均勻假設(shè)的 ndv 和 cardinality 算法。研究者可以自由地使用 Python、或者其他語言來實現(xiàn)算法，我們已經(jīng)封裝好了清晰明了的接口。
上述環(huán)節(jié)完成后，你就可以在虛擬數(shù)據(jù)庫上自由的創(chuàng)建和刪除索引，然后使用 EXPLAIN 來獲取“貼近真實”的查詢計劃了 ??
作者團隊
我們來自字節(jié)跳動的 ByteBrain 團隊，我們致力于用 AI 技術(shù)，為各種基礎(chǔ)架構(gòu)與系統(tǒng)（數(shù)據(jù)庫、云原生、大數(shù)據(jù)）優(yōu)化降本、提質(zhì)增效。
如果您有任何疑問，請隨時通過電子郵件聯(lián)系我們:
- Rong Kang: kangrong.cn@bytedance.com, kr11thss@gmail.com
- Tieying Zhang: tieying.zhang@bytedance.com
參考資料
1. Meta: Yadav, Ritwik, Satyanarayana R. Valluri, and Mohamed Za?t. "AIM: A practical approach to automated index management for SQL databases." 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 2023.
2. Meituan: Slow Query Optimized Ddvice Driven by Cost Model：https://tech.meituan.com/2022/04/21/slow-query-optimized-advice-driven-by-cost-model.html
3. Kossmann, J., Halfpap, S., Jankrift, M., & Schlosser, R. (2020). Magic mirror in my hand, which is the best in the land? an experimental evaluation of index selection algorithms. Proceedings of the VLDB Endowment, 13(12), 2382-2395.
相關(guān)鏈接
項目地址：
