虛擬索引技術（virtual index，也稱為 hypothetical index）在數據庫系統的查詢優化、索引推薦等場景中扮演著關鍵角色。簡單來說，虛擬索引可以理解為數據庫的'沙盤推演'系統——無需真實構建索引，僅基于統計信息即可精準模擬不同索引方案對查詢計劃的優化效果。由于虛擬索引的創建/刪除代價極低，使用者可以大量創建和刪除索引、反復推演，確定最有效的索引方案。在AI時代，基于機器學習模型的NDV、Cardinality估計算法層出不窮，但是在MySQL落地往往遇到很大挑戰：無法注入機器學習模型的預測值，便無法得到MySQL索引推薦結果。

業界許多數據庫已經以官方或第三方的方式提供了虛擬索引功能，例如 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 ）。大量數據庫領域的研究都圍繞虛擬索引技術展開。遺憾的是，MySQL 長期缺乏這一能力，導致其在復雜場景下的優化效果始終受限。

經過長期的生產驗證，字節跳動正式開源了 MySQL 虛擬索引項目  VIDEX（Virtual Index ），讓 MySQL 也有了自己的虛擬索引機制 ??

VIDEX 開源地址：https://github.com/bytedance/videx

VIDEX 已經部署在了字節跳動大規模生產系統中，每天為數千用戶、數十萬慢 SQL 提供優化服務。VIDEX 的實用價值、工業級部署設計等特點，引來 Daniel Black（MariaDB Foundation 首席創新官）和Federico Razzoli (Founder of Vettabase) 等業界知名專家的點贊與認可。

VIDEX 提供開箱即用的虛擬索引能力，可無縫集成至現有 MySQL 生態；對于數據庫研究者，VIDEX 模塊化設計允許新算法（如 NDV 估計、Cardinality估計等等）在 MySQL 上快速驗證，推動前沿技術落地。

具體來說，VIDEX 的貢獻如下：

彌補 MySQL 虛擬索引空白：盡管業界已經有多種數據庫支持了虛擬索引功能（ Postgres、Oracle、 IBM DB2），也有一些論文和博客提到了 MySQL 的虛擬索引技術 [1,2]，但據我們所知，VIDEX 是首個開源的、可拓展、支持多形態部署的 MySQL 虛擬索引解決方案。

高精度地擬合 MySQL：我們已經在 TPC-H、TPC-H-Skew 和 JOB 等復雜分析基準測試上對 VIDEX 進行了測試。給定準確的獨立值估計（ndv） 和基數估計（Cardinality） 信息，VIDEX 可以 100% 模擬 MySQL InnoDB 的查詢計劃。

基于分離架構的多形態部署：VIDEX 實現了數據庫實例-VIDEX優化器插件-VIDEX算法服務的模塊分離。既支持作為插件無縫集成到現有MySQL實例，也可作為獨立服務構建虛擬庫環境，實現生產環境零干擾的索引驗證；額外地，將 VIDEX優化器插件和VIDEX算法服務也做了分離，便于 AI 算法服務的集成和熱更新。

可拓展的實驗平臺：準確地模擬MySQL查詢代價依賴于對獨立值（ndv）和基數（Cardinality）的準確估計——這正是AI+數據庫研究中最火熱的方向之一 [3]。VIDEX 給出了標準化、清晰易懂的接口設計，屏蔽了復雜的系統細節。研究者可以自由地用各種語言來重寫 VIDEX 的算法模型，甚至只需要改動一個 JSON 文件，就能將自己的新算法應用于 MySQL查詢優化器！

多形態部署：從實驗平臺到生產環境

由于 VIDEX 將真實數據庫實例、虛擬數據庫實例、算法服務器三個部分解耦了，因此可以靈活應用于各種適用場景，從個人研究到生產環境部署：

VIDEX-Optimizer 的兩種形態

作為插件安裝到真實數據庫：將 VIDEX 作為插件安裝到真實數據庫實例，這樣只需要一臺 MySQL實例，即可體驗基于虛擬索引的各種 what-if 分析。適合于個人實驗和分析。

以獨立實例啟動：獨立啟動 VIDEX 示例，同步統計信息，然后開始分析。此模式可以完全避免影響在線運行實例的穩定性，在工業環境中很實用。

VIDEX 算法服務器的兩種形態

與 VIDEX-Optimizer 配套啟動：最經典的方式，無須額外設置，VIDEX-Optimizer 會自動尋找本地啟動的VIDEX算法服務器。

獨立啟動算法服務器：只要設置一下 SQL 環境變量（SET @VIDEX_STATISTIC_SERVER='ip:port'），VIDEX-Optimizer 會將算法請求轉發到指定的算法服務器上。對于研究者來說，可以自由實現算法、啟動自定義的算法服務；對于云原生場景，可以將大量 MySQL 實例的算法請求發往中心式的算法服務，便于運維和快速更新。

VIDEX 任務的兩種形態

非任務模式：默認情況下，用戶不需要關注 “task_id” —— 只需要指定目標庫、指定虛擬庫，同步數據即可；

任務模式：在大規模分析任務中（例如大規模索引推薦任務），各種用戶往往會對同一個生產庫的不同表、或不同實例的同名表發起多次分析。這種情況下，用戶可以指定任務 id（SET @VIDEX_OPTIONS={'task_id': 'abc'}），讓多個任務彼此互不影響。

算法試驗場：把算法模型接入 MySQL 優化器

MySQL 采用了分離式的架構，上層的查詢優化器會向下層存儲引擎請求各種信息，包括元數據信息（table_rows、data_length 等等）、獨立值（ndv）、基數（cardinality）、索引內存加載率等等。其中基數估計和獨立值估計是 AI for DB 研究領域的熱點方向。現已有大量 data-driven 或者 query-driven 的算法被提出，但這些算法往往只能以 PostgreSQL 作為試驗場。

VIDEX 讓用戶不必與 MySQL 查詢優化器做交互、也屏蔽了 MySQL 對庫表元數據信息（table_rows、deta_length）的請求。由此，用戶可以專注于一些重點的算法問題，例如 NDV 估計和 Cardinality 估計。

方法 1：在 VIDEX-Statistic-Server 中添加一種新方法

考慮到許多研究者習慣于用 Python 研究各種 AI 與 DB 結合的算法，因此，我們用Python 實現了 VIDEX-Statistic。

用戶可以繼承并修改 VidexModelInnoDB。VidexModelInnoDB 為用戶屏蔽了系統變量、索引元數據格式等復雜細節，并提供了一個基于獨立、均勻分布假設的 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()

假設用戶用 VidexModelExample 重載了 VidexModelInnoDB ，可以指定模然后啟動 VIDEX-Statistic-Server（詳見代碼啟動腳本）。

startup_videx_server(VidexModelClass=VidexModelExample)
startup_videx_server(VidexModelClass=VidexModelExample)

方法 2: 全新實現 VIDEX-Statistic-Server

用戶可以用任何編程語言實現 HTTP 響應、并在任意位置啟動 VIDEX-Statistic。

使用時，只需要指定環境變量（SET @VIDEX_STATISTIC_SERVER='ip:port'），VIDEX-Optimizer 就會將所有請求轉發到指定服務上。

兩步玩轉 VIDEX，在 TPC-H 上看看效果

步驟 1: Docker 啟動 VIDEX

最簡單的情況下，用戶可以用 Docker 啟動一個安裝好 VIDEX-Optimizer 和 VIDEX-Statistic 的容器。用戶也可以參考文檔說明，嘗試其他啟動方式。

為簡化部署，我們提供了預編譯的 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 算法服務

如果您尚未安裝 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 數據準備

VIDEX 需要 Python 3.9 環境，執行元數據采集等任務。我們推薦使用 Anaconda/Miniconda 創建獨立的 Python 環境來安裝，詳見 README 文檔的 Quick Start 章節（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 庫地址，用腳本一鍵式同步數據（以 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 數據集演示 VIDEX 的完整使用流程。

假設用戶已經準備好了 TPCH 數據。篇幅限制，我們將更詳細的步驟說明放到了 README 文檔的 Example 章節（https://github.com/bytedance/videx?tab=readme-ov-file#3-examples）。

為了展示 VIDEX 的有效性，我們對比了 TPC-H Q21 的 EXPLAIN 細節，這是一個包含四表連接的復雜查詢，涉及 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，這是一種更加嚴格的格式。

我們不僅比較表連接順序和索引選擇，還包括查詢計劃的每一個細節（例如每一步的行數和代價）。

如下圖所示，VIDEX（左圖）能生成一個與 InnoDB（右圖）幾乎 100% 相同的查詢計劃。

VIDEX 的一個重要作用是模擬索引代價。我們額外新增一個索引。VIDEX 增加索引的代價是 O(1) ，因為他并不需要在真實數據上創建索引：

-- 為 innodb 庫創建索引ALTER TABLE tpch_tiny.orders ADD INDEX idx_o_orderstatus (o_orderstatus);-- 為 videx 創建索引ALTER TABLE videx_tpch_tiny.orders ADD INDEX idx_o_orderstatus (o_orderstatus);
-- 為 innodb 庫創建索引
ALTER TABLE tpch_tiny.orders ADD INDEX idx_o_orderstatus (o_orderstatus);
-- 為 videx 創建索引
ALTER TABLE videx_tpch_tiny.orders ADD INDEX idx_o_orderstatus (o_orderstatus);

再次執行 EXPLAIN，我們看到 MySQL-InnoDB 和 VIDEX 的查詢計劃發產生了相同的變化，兩個查詢計劃均采納了新索引，并且查詢計劃的細節也非常接近。

VIDEX 的行數估計 (7404) 與 MySQL-InnoDB (7362) 相差約為 0.56%，這個誤差來自于基數估計算法的誤差。

深入解析 VIDEX 架構

如圖展現了 VIDEX 的架構。總體來說，VIDEX 包含兩個模塊：

• VIDEX-Optimizer-Plugin（簡稱 VIDEX-Optimizer）：VIDEX 的“前端”。可以作為插件安裝到現有數據庫，或者以一個獨立的新實例啟動。這一部分實現了 MySQL 查詢優化器接口，并將其中一部分復雜的請求轉發到 VIDEX-Statistic-Server。我們全面梳理了 MySQL handler 的超過90個接口函數，并實現與索引（Index）相關的接口。
• VIDEX-Statistic-Server（簡稱 VIDEX-Statistic）：VIDEX 的“后端”。基于收集到的統計信息（表行數、表大小、直方圖等等）和集成的算法或模型，計算獨立值（NDV） 和基數（Cardinality），并將結果返回給 VIDEX-Optimizer。

當用戶指定了要分析（what-if analysis）的真實數據庫之后，VIDEX 會在 VIDEX-Optimizer 上創建一個虛擬數據庫。虛擬數據庫與真實數據庫的關系表結構完全一致，只是將 Engine 從 InnoDB 更換為 VIDEX。為了準確模擬目標數據庫的查詢代價，VIDEX 會調用腳本，從真實數據庫采集必要的統計信息。上述過程都可以用我們提供好的腳本一鍵式完成。

用戶也可以自定義地提供一份元數據文件、讓腳本直接導入。元數據文件是 json 格式，包含了庫表結構信息、統計信息（table_rows、單列 ndv等等）、直方圖信息，非常容易理解。

VIDEX-Statistic-Server 是 VIDEX 的算法服務器。我們已經提供了基于獨立均勻假設的 ndv 和 cardinality 算法。研究者可以自由地使用 Python、或者其他語言來實現算法，我們已經封裝好了清晰明了的接口。

上述環節完成后，你就可以在虛擬數據庫上自由的創建和刪除索引，然后使用 EXPLAIN 來獲取“貼近真實”的查詢計劃了 ??

作者團隊

我們來自字節跳動的 ByteBrain 團隊，我們致力于用 AI 技術，為各種基礎架構與系統（數據庫、云原生、大數據）優化降本、提質增效。

如果您有任何疑問，請隨時通過電子郵件聯系我們:

• 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.

相關鏈接

項目地址：

  https://github.com/bytedance/videx