虛擬索引技術(shù)（virtual index，也稱為 hypothetical index）在數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化、索引推薦等場(chǎng)景中扮演著關(guān)鍵角色。簡(jiǎn)單來說，虛擬索引可以理解為數(shù)據(jù)庫的'沙盤推演'系統(tǒng)——無需真實(shí)構(gòu)建索引，僅基于統(tǒng)計(jì)信息即可精準(zhǔn)模擬不同索引方案對(duì)查詢計(jì)劃的優(yōu)化效果。由于虛擬索引的創(chuàng)建/刪除代價(jià)極低，使用者可以大量創(chuàng)建和刪除索引、反復(fù)推演，確定最有效的索引方案。在AI時(shí)代，基于機(jī)器學(xué)習(xí)模型的NDV、Cardinality估計(jì)算法層出不窮，但是在MySQL落地往往遇到很大挑戰(zhàn)：無法注入機(jī)器學(xué)習(xí)模型的預(yù)測(cè)值，便無法得到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 長(zhǎng)期缺乏這一能力，導(dǎo)致其在復(fù)雜場(chǎng)景下的優(yōu)化效果始終受限。

經(jīng)過長(zhǎng)期的生產(chǎn)驗(yàn)證，字節(jié)跳動(dòng)正式開源了 MySQL 虛擬索引項(xiàng)目  VIDEX（Virtual Index ），讓 MySQL 也有了自己的虛擬索引機(jī)制 ??

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

VIDEX 已經(jīng)部署在了字節(jié)跳動(dòng)大規(guī)模生產(chǎn)系統(tǒng)中，每天為數(shù)千用戶、數(shù)十萬慢 SQL 提供優(yōu)化服務(wù)。VIDEX 的實(shí)用價(jià)值、工業(yè)級(jí)部署設(shè)計(jì)等特點(diǎn)，引來 Daniel Black（MariaDB Foundation 首席創(chuàng)新官）和Federico Razzoli (Founder of Vettabase) 等業(yè)界知名專家的點(diǎn)贊與認(rèn)可。

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

具體來說，VIDEX 的貢獻(xiàn)如下：

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

高精度地?cái)M合 MySQL：我們已經(jīng)在 TPC-H、TPC-H-Skew 和 JOB 等復(fù)雜分析基準(zhǔn)測(cè)試上對(duì) VIDEX 進(jìn)行了測(cè)試。給定準(zhǔn)確的獨(dú)立值估計(jì)（ndv） 和基數(shù)估計(jì)（Cardinality） 信息，VIDEX 可以 100% 模擬 MySQL InnoDB 的查詢計(jì)劃。

基于分離架構(gòu)的多形態(tài)部署：VIDEX 實(shí)現(xiàn)了數(shù)據(jù)庫實(shí)例-VIDEX優(yōu)化器插件-VIDEX算法服務(wù)的模塊分離。既支持作為插件無縫集成到現(xiàn)有MySQL實(shí)例，也可作為獨(dú)立服務(wù)構(gòu)建虛擬庫環(huán)境，實(shí)現(xiàn)生產(chǎn)環(huán)境零干擾的索引驗(yàn)證；額外地，將 VIDEX優(yōu)化器插件和VIDEX算法服務(wù)也做了分離，便于 AI 算法服務(wù)的集成和熱更新。

可拓展的實(shí)驗(yàn)平臺(tái)：準(zhǔn)確地模擬MySQL查詢代價(jià)依賴于對(duì)獨(dú)立值（ndv）和基數(shù)（Cardinality）的準(zhǔn)確估計(jì)——這正是AI+數(shù)據(jù)庫研究中最火熱的方向之一 [3]。VIDEX 給出了標(biāo)準(zhǔn)化、清晰易懂的接口設(shè)計(jì)，屏蔽了復(fù)雜的系統(tǒng)細(xì)節(jié)。研究者可以自由地用各種語言來重寫 VIDEX 的算法模型，甚至只需要改動(dòng)一個(gè) JSON 文件，就能將自己的新算法應(yīng)用于 MySQL查詢優(yōu)化器！

多形態(tài)部署：從實(shí)驗(yàn)平臺(tái)到生產(chǎn)環(huán)境

由于 VIDEX 將真實(shí)數(shù)據(jù)庫實(shí)例、虛擬數(shù)據(jù)庫實(shí)例、算法服務(wù)器三個(gè)部分解耦了，因此可以靈活應(yīng)用于各種適用場(chǎng)景，從個(gè)人研究到生產(chǎn)環(huán)境部署：

VIDEX-Optimizer 的兩種形態(tài)

作為插件安裝到真實(shí)數(shù)據(jù)庫：將 VIDEX 作為插件安裝到真實(shí)數(shù)據(jù)庫實(shí)例，這樣只需要一臺(tái) MySQL實(shí)例，即可體驗(yàn)基于虛擬索引的各種 what-if 分析。適合于個(gè)人實(shí)驗(yàn)和分析。

以獨(dú)立實(shí)例啟動(dòng)：獨(dú)立啟動(dòng) VIDEX 示例，同步統(tǒng)計(jì)信息，然后開始分析。此模式可以完全避免影響在線運(yùn)行實(shí)例的穩(wěn)定性，在工業(yè)環(huán)境中很實(shí)用。

VIDEX 算法服務(wù)器的兩種形態(tài)

與 VIDEX-Optimizer 配套啟動(dòng)：最經(jīng)典的方式，無須額外設(shè)置，VIDEX-Optimizer 會(huì)自動(dòng)尋找本地啟動(dòng)的VIDEX算法服務(wù)器。

獨(dú)立啟動(dòng)算法服務(wù)器：只要設(shè)置一下 SQL 環(huán)境變量（SET @VIDEX_STATISTIC_SERVER='ip:port'），VIDEX-Optimizer 會(huì)將算法請(qǐng)求轉(zhuǎn)發(fā)到指定的算法服務(wù)器上。對(duì)于研究者來說，可以自由實(shí)現(xiàn)算法、啟動(dòng)自定義的算法服務(wù)；對(duì)于云原生場(chǎng)景，可以將大量 MySQL 實(shí)例的算法請(qǐng)求發(fā)往中心式的算法服務(wù)，便于運(yùn)維和快速更新。

VIDEX 任務(wù)的兩種形態(tài)

非任務(wù)模式：默認(rèn)情況下，用戶不需要關(guān)注 “task_id” —— 只需要指定目標(biāo)庫、指定虛擬庫，同步數(shù)據(jù)即可；

任務(wù)模式：在大規(guī)模分析任務(wù)中（例如大規(guī)模索引推薦任務(wù)），各種用戶往往會(huì)對(duì)同一個(gè)生產(chǎn)庫的不同表、或不同實(shí)例的同名表發(fā)起多次分析。這種情況下，用戶可以指定任務(wù) id（SET @VIDEX_OPTIONS={'task_id': 'abc'}），讓多個(gè)任務(wù)彼此互不影響。

算法試驗(yàn)場(chǎng)：把算法模型接入 MySQL 優(yōu)化器

MySQL 采用了分離式的架構(gòu)，上層的查詢優(yōu)化器會(huì)向下層存儲(chǔ)引擎請(qǐng)求各種信息，包括元數(shù)據(jù)信息（table_rows、data_length 等等）、獨(dú)立值（ndv）、基數(shù)（cardinality）、索引內(nèi)存加載率等等。其中基數(shù)估計(jì)和獨(dú)立值估計(jì)是 AI for DB 研究領(lǐng)域的熱點(diǎn)方向。現(xiàn)已有大量 data-driven 或者 query-driven 的算法被提出，但這些算法往往只能以 PostgreSQL 作為試驗(yàn)場(chǎng)。

VIDEX 讓用戶不必與 MySQL 查詢優(yōu)化器做交互、也屏蔽了 MySQL 對(duì)庫表元數(shù)據(jù)信息（table_rows、deta_length）的請(qǐng)求。由此，用戶可以專注于一些重點(diǎn)的算法問題，例如 NDV 估計(jì)和 Cardinality 估計(jì)。

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

考慮到許多研究者習(xí)慣于用 Python 研究各種 AI 與 DB 結(jié)合的算法，因此，我們用Python 實(shí)現(xiàn)了 VIDEX-Statistic。

用戶可以繼承并修改 VidexModelInnoDB。VidexModelInnoDB 為用戶屏蔽了系統(tǒng)變量、索引元數(shù)據(jù)格式等復(fù)雜細(xì)節(jié)，并提供了一個(gè)基于獨(dú)立、均勻分布假設(shè)的 ndv 和 cardinality 算法。這樣用戶可以聚焦于 cardinality 和 ndv 這兩個(gè)研究熱點(diǎn)：

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 ，可以指定模然后啟動(dòng) VIDEX-Statistic-Server（詳見代碼啟動(dòng)腳本）。

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

方法 2: 全新實(shí)現(xiàn) VIDEX-Statistic-Server

用戶可以用任何編程語言實(shí)現(xiàn) HTTP 響應(yīng)、并在任意位置啟動(dòng) VIDEX-Statistic。

使用時(shí)，只需要指定環(huán)境變量（SET @VIDEX_STATISTIC_SERVER='ip:port'），VIDEX-Optimizer 就會(huì)將所有請(qǐng)求轉(zhuǎn)發(fā)到指定服務(wù)上。

兩步玩轉(zhuǎn) VIDEX，在 TPC-H 上看看效果

步驟 1: Docker 啟動(dòng) VIDEX

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

為簡(jiǎn)化部署，我們提供了預(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ù)準(zhǔn)備

VIDEX 需要 Python 3.9 環(huán)境，執(zhí)行元數(shù)據(jù)采集等任務(wù)。我們推薦使用 Anaconda/Miniconda 創(chuàng)建獨(dú)立的 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)準(zhǔn)備好了 TPCH 數(shù)據(jù)。篇幅限制，我們將更詳細(xì)的步驟說明放到了 README 文檔的 Example 章節(jié)（https://github.com/bytedance/videx?tab=readme-ov-file#3-examples）。

為了展示 VIDEX 的有效性，我們對(duì)比了 TPC-H Q21 的 EXPLAIN 細(xì)節(jié)，這是一個(gè)包含四表連接的復(fù)雜查詢，涉及 WHERE、聚合、ORDER BY、GROUP BY、EXISTS 和 SELF-JOIN 等多種部分。初始情況下，MySQL 可以選擇的索引有 11 個(gè)，分布在 4 個(gè)表上。

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;

讓我們來對(duì)比 VIDEX 和 InnoDB 的估計(jì)效果。我們使用 EXPLAIN FORMAT=JSON，這是一種更加嚴(yán)格的格式。

我們不僅比較表連接順序和索引選擇，還包括查詢計(jì)劃的每一個(gè)細(xì)節(jié)（例如每一步的行數(shù)和代價(jià)）。

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

VIDEX 的一個(gè)重要作用是模擬索引代價(jià)。我們額外新增一個(gè)索引。VIDEX 增加索引的代價(jià)是 O(1) ，因?yàn)樗⒉恍枰谡鎸?shí)數(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 的查詢計(jì)劃發(fā)產(chǎn)生了相同的變化，兩個(gè)查詢計(jì)劃均采納了新索引，并且查詢計(jì)劃的細(xì)節(jié)也非常接近。

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

深入解析 VIDEX 架構(gòu)

如圖展現(xiàn)了 VIDEX 的架構(gòu)。總體來說，VIDEX 包含兩個(gè)模塊：

• VIDEX-Optimizer-Plugin（簡(jiǎn)稱 VIDEX-Optimizer）：VIDEX 的“前端”。可以作為插件安裝到現(xiàn)有數(shù)據(jù)庫，或者以一個(gè)獨(dú)立的新實(shí)例啟動(dòng)。這一部分實(shí)現(xiàn)了 MySQL 查詢優(yōu)化器接口，并將其中一部分復(fù)雜的請(qǐng)求轉(zhuǎn)發(fā)到 VIDEX-Statistic-Server。我們?nèi)媸崂砹?MySQL handler 的超過90個(gè)接口函數(shù)，并實(shí)現(xiàn)與索引（Index）相關(guān)的接口。
• VIDEX-Statistic-Server（簡(jiǎn)稱 VIDEX-Statistic）：VIDEX 的“后端”。基于收集到的統(tǒng)計(jì)信息（表行數(shù)、表大小、直方圖等等）和集成的算法或模型，計(jì)算獨(dú)立值（NDV） 和基數(shù)（Cardinality），并將結(jié)果返回給 VIDEX-Optimizer。

當(dāng)用戶指定了要分析（what-if analysis）的真實(shí)數(shù)據(jù)庫之后，VIDEX 會(huì)在 VIDEX-Optimizer 上創(chuàng)建一個(gè)虛擬數(shù)據(jù)庫。虛擬數(shù)據(jù)庫與真實(shí)數(shù)據(jù)庫的關(guān)系表結(jié)構(gòu)完全一致，只是將 Engine 從 InnoDB 更換為 VIDEX。為了準(zhǔn)確模擬目標(biāo)數(shù)據(jù)庫的查詢代價(jià)，VIDEX 會(huì)調(diào)用腳本，從真實(shí)數(shù)據(jù)庫采集必要的統(tǒng)計(jì)信息。上述過程都可以用我們提供好的腳本一鍵式完成。

用戶也可以自定義地提供一份元數(shù)據(jù)文件、讓腳本直接導(dǎo)入。元數(shù)據(jù)文件是 json 格式，包含了庫表結(jié)構(gòu)信息、統(tǒng)計(jì)信息（table_rows、單列 ndv等等）、直方圖信息，非常容易理解。

VIDEX-Statistic-Server 是 VIDEX 的算法服務(wù)器。我們已經(jīng)提供了基于獨(dú)立均勻假設(shè)的 ndv 和 cardinality 算法。研究者可以自由地使用 Python、或者其他語言來實(shí)現(xiàn)算法，我們已經(jīng)封裝好了清晰明了的接口。

上述環(huán)節(jié)完成后，你就可以在虛擬數(shù)據(jù)庫上自由的創(chuàng)建和刪除索引，然后使用 EXPLAIN 來獲取“貼近真實(shí)”的查詢計(jì)劃了 ??

作者團(tuán)隊(duì)

我們來自字節(jié)跳動(dòng)的 ByteBrain 團(tuán)隊(duì)，我們致力于用 AI 技術(shù)，為各種基礎(chǔ)架構(gòu)與系統(tǒng)（數(shù)據(jù)庫、云原生、大數(shù)據(jù)）優(yōu)化降本、提質(zhì)增效。

如果您有任何疑問，請(qǐng)隨時(shí)通過電子郵件聯(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)鏈接

項(xiàng)目地址：

  https://github.com/bytedance/videx