導(dǎo)讀

本文基于ByteBrain團隊實際生產(chǎn)場景，提出一項新的研究問題，即如何在無數(shù)據(jù)訪問條件下，從不完美的查詢工作負載中學習一個具備泛化能力與魯棒性的基數(shù)估計模型；同時提出創(chuàng)新技術(shù)方案 GRASP （Generalizable and Robust, data-AgnoStic cardinality Prediction） ，借助組合式設(shè)計（Compositional Design）解決這一頗具挑戰(zhàn)性的問題。論文目前已經(jīng)被VLDB25接收。

論文標題：Data-Agnostic Cardinality Learning from Imperfect Workloads

論文作者：Peizhi Wu, Rong Kang, Tieying Zhang*, Jianjun Chen, Ryan Marcus, Zachary G. Ives，其中，第一作者Peizhi Wu為賓夕法尼亞大學在讀博士，其論文工作是在 ByteBrain 團隊實習期間完成的。通訊作者Tieying Zhang為ByteBrain團隊負責人

論文地址：https://arxiv.org/abs/2506.16007

項目地址：https://github.com/shoupzwu/GRASP

背景

在數(shù)據(jù)庫管理和數(shù)據(jù)庫系統(tǒng)領(lǐng)域，基數(shù)估計（Cardinality Estimation, 也就是預(yù)測查詢的返回行數(shù)）是個重要的研究課題。因為準確的基數(shù)估計是關(guān)系型數(shù)據(jù)庫查詢優(yōu)化的必要條件，也是索引推薦的關(guān)鍵因素。隨著大數(shù)據(jù)技術(shù)發(fā)展，處理海量數(shù)據(jù)時，快速又準確的基數(shù)估計方法非常重要。

在現(xiàn)有的基數(shù)估計研究里，已經(jīng)提出并廣泛應(yīng)用了多種技術(shù)。這些技術(shù)主要有：

1. 基于數(shù)據(jù)驅(qū)動的方法：這類方法要對數(shù)據(jù)庫的所有數(shù)據(jù)進行掃描，通過構(gòu)建不同的數(shù)據(jù)模型（像直方圖、sketches）來對查詢做基數(shù)估計。
2. 基于查詢工作負載 (Query Workload) 驅(qū)動的方法：這類算法要利用歷史查詢工作負載（就是歷史執(zhí)行過的查詢和對應(yīng)的真實基數(shù)）來構(gòu)建機器學習模型，從而對未來的查詢進行基數(shù)估計。

現(xiàn)有的基于數(shù)據(jù)驅(qū)動的方法需要直接訪問數(shù)據(jù)庫實例的數(shù)據(jù)。但在實際生產(chǎn)環(huán)境中，常常由于數(shù)據(jù)隱私、組織權(quán)限隔離或法規(guī)限制，無法直接訪問底層數(shù)據(jù)。這使得傳統(tǒng)依賴數(shù)據(jù)統(tǒng)計（如直方圖、樣本）的估計方法難以適用。另一方面，基于查詢工作負載的方法能避免用戶數(shù)據(jù)隱私問題，但現(xiàn)有的技術(shù)方案都要求有完美的工作負載。完美的工作負載指的是歷史查詢工作負載里包含所有可能的連接模版，而且分布均勻。但在實際查詢工作負載中，連接模版往往不完整，分布也不均衡，并且查詢謂詞的分布可能會隨時間變化。

目標

本文目標是在無數(shù)據(jù)訪問的約束下，從從實際工作負載上構(gòu)建準確的基數(shù)估計模型。

同時，從實際工作負載上構(gòu)建基數(shù)估計模型往往具有三大挑戰(zhàn)：

1. Join 模板不完備（僅覆蓋部分表連接形式）；
2. Join 模板嚴重不平衡（某些模板出現(xiàn)頻率極低）；
3. 謂詞值分布隨時間發(fā)生漂移。

因此，我們定義了一個新問題：在無數(shù)據(jù)訪問約束下，如何從不完美的查詢工作 負載 中學習一個具有 泛化能力 和 魯棒性 的基數(shù)估計模型。

訓練數(shù)據(jù)

構(gòu)建階段以以下輸入為基礎(chǔ)：

• 數(shù)據(jù)庫模式（Schema）；
• 歷史工作負載，即歷史查詢及其真實基數(shù)標簽；
• 各基表的行數(shù)（表級基數(shù)信息，非敏感）。

組合式設(shè)計

如圖二所示，不同于現(xiàn)有方法對每個join模板訓練一個 獨立 的模型或者用一個模型處理所有的join模版，本發(fā)明提出了利用join的結(jié)構(gòu)關(guān)系來訓練不同但是相互關(guān)聯(lián)的模型。該設(shè)計顯著增強了模型對未見 join 模板（Unseen Join Templates）的 泛化能力 ，大大提升了實用性和擴展性。此外，由于各join模板復(fù)用相同的 基礎(chǔ)模型 ， GRASP 天然支持從高頻 join 模板中獲得泛化能力，并遷移至低頻模板，解決 訓練樣本 不均問題。

具體地，在此階段，本發(fā)明通過深度神經(jīng)網(wǎng)絡(luò)為每個單表（base table）訓練兩類關(guān)鍵基礎(chǔ)模塊：

• 表級基數(shù)預(yù)測模型（CardEst） ：用于估計每個子查詢（如 select + predicate）的表級基數(shù)。
• Learned Count Sketch 模型（LCS） ：用于建模各表 join key 分布的低維分布向量。

對于任意輸入查詢，其中包括多表聯(lián)合查詢 (join query)：

1. 按聯(lián)合查詢所對應(yīng)的join 模板解析其組成表 (base tables)。
   例如：聯(lián)合查詢“SELECT * FROM A, B WHERE A.key = B.key AND A.a > 5 AND B.b < 10”包含兩個組成表，即表A和表B。
2. 將聯(lián)合查詢拆分成各個組成表上的子查詢 (subquery)，例如上述聯(lián)合查詢可被拆分成兩個分表在表A和表B上的子查詢:
   a. SELECT * FROM A WHERE A.a > 5;
   b. SELECT * FROM B WHERE B.b > 10;
3. 調(diào)用對應(yīng)的 CardEst 模型預(yù)測每個子表的基數(shù)。
     CardEst 模型輸入是一個在單一關(guān)系表上 (base table) 的包含多維謂詞的查詢，輸出是基數(shù) (cardinality)，也即這張表上的滿足給定謂詞的數(shù)據(jù)行數(shù)。
4. 調(diào)用組成表對應(yīng)的 LCS 模型生成子查詢中連接鍵（join key）分布對應(yīng)的低維計數(shù)草圖（count sketch），后文將會介紹 LCS 模型的模型架構(gòu)。
5. 利用不同子表的低維計數(shù)草圖（Count Sketch）向量內(nèi)積（dot product）結(jié)果，并結(jié)合每個子表上CardEst模型的預(yù)測結(jié)果，對最終連接查詢的基數(shù)進行估計。具體示例可參考圖一。
   

圖一： GRASP估計聯(lián)合查詢基數(shù)的例子

圖二：GRASP的組合式設(shè)計 vs 現(xiàn)有工作

訓練目標為最小化基數(shù)估計誤差（如對數(shù)平方誤差 SLE）。所有模塊均為可微結(jié)構(gòu)，支持端到端優(yōu)化。

ArCDF: Autoregressive CDF Modeling

圖三:  ArCDF模型利用deep autoregressive model來自回歸地預(yù)測段單調(diào)樣條 (monotonic rational-quadratic splines)的參數(shù)

對于針對數(shù)值型屬性的范圍查詢（范圍謂詞），GRASP的CardEst板塊采用了創(chuàng)新的ArCDF（如圖三所示）來預(yù)測基數(shù)。ArCDF首先將范圍查詢轉(zhuǎn)換為其上界和下界的線性組合，然后運用ArCDF模型來預(yù)測所有上下界的累積分布函數(shù)（CDF）。具體而言，將謂詞轉(zhuǎn)換為上界和下界，輸入ArCDF，獲取所有上界和下界的CDF估計值，通過作差得到基數(shù)：card = rows * [CDF(up) - CDF(down)]。這保證了預(yù)測基數(shù)的單調(diào)性和非負性，即使在謂詞值分布變化（如滑動窗口、區(qū)間變更）時，仍能保持魯棒的估計性能。

ArCDF沿用了本專利之外的前人工作NeuroCDF [1]，但進行了關(guān)鍵改進，引入了自回歸建模，模型結(jié)構(gòu)如圖三。其輸入是對應(yīng)單表上每個屬性的值，ArCDF利用深度自回歸模型來對所有屬性的CDF的聯(lián)合分布進行建模，其計算公式如下圖所示：

并且ArCDF在每個屬性上使用 monotonic rational-quadratic splines 函數(shù)來建模CDF，以確保CDF在每個維度上具有局部單調(diào)遞增的特性，降低負基數(shù)估計出現(xiàn)的可能性。

[1]. Peizhi Wu, Haoshu Xu, Ryan Marcus, Zachary G. Ives. A Practical Theory of Generalization in Selectivity Learning. VLDB 2025.

Learned Count Sketch模型

圖四：Learned Count Sketch (LCS) 模型架構(gòu)

因此，連接的關(guān)聯(lián)性（join correlations, 通常通過其組成表上子查詢的連接鍵分布進行向量內(nèi)積運算獲得）可通過低維計數(shù)草圖進行向量內(nèi)積（dot product）近似計算。

傳統(tǒng)方法需要在數(shù)據(jù)預(yù)處理階段通過掃描全量表數(shù)據(jù)生成靜態(tài)計數(shù)草圖，而本文提出了查詢驅(qū)動的 LCS 模型（模型結(jié)構(gòu)如圖四所示） ，利用神經(jīng)網(wǎng)絡(luò)直接依據(jù)輸入查詢動態(tài)預(yù)測查詢結(jié)果中連接鍵分布對應(yīng)的計數(shù)草圖向量。 如果其包含多個連接鍵，LCS模型則對每個連接鍵輸出其對應(yīng)的低維計數(shù)草圖（count sketch）。通過神經(jīng)網(wǎng)絡(luò)直接根據(jù)查詢結(jié)構(gòu)動態(tài)生成 count sketch 向量，支持端到端訓練并與 CardEst 協(xié)同優(yōu)化。

實驗與結(jié)果

1.顯著提升基數(shù)估計準確度（更準的預(yù)測結(jié)果）

通過組合式的建模設(shè)計與更強的模型表達能力（包括表級估計模塊和基于學習的 Count Sketch 模塊），GRASP能對從未見過的 join 模板、長尾查詢結(jié)構(gòu)以及謂詞值偏移情況做出更準確的估計。預(yù)測準確度實驗結(jié)果如下圖所示，在不訪問底層數(shù)據(jù)的前提下，GRASP在多個實際和標準基準上（如CEB-IMDb、DSB等）實現(xiàn)了與傳統(tǒng)基于數(shù)據(jù)統(tǒng)計方法相當甚至更優(yōu)的預(yù)測準確度，尤其在查詢模板覆蓋率低至10%的情況下依然保持穩(wěn)定性能。

2.有效提升查詢優(yōu)化質(zhì)量（更優(yōu)的執(zhí)行計劃）

由于查詢優(yōu)化器高度依賴基數(shù)估計值來選擇執(zhí)行計劃，準確的基數(shù)預(yù)測直接影響最終查詢性能。GRASP提供更魯棒的基數(shù)估計后，能有效避免常見的執(zhí)行計劃錯誤（如錯誤的連接順序、索引誤選等），從而提升整個查詢執(zhí)行效率。如下圖所示，在實驗中，GRASP在無數(shù)據(jù)訪問條件下，仍能在多個 benchmark 上顯著減少查詢延遲，體現(xiàn)出實際系統(tǒng)部署中的優(yōu)化能力和商業(yè)價值。

ByteBrain團隊介紹

ByteBrain是字節(jié)跳動 AI for Infra / AI for System服務(wù)平臺，旨在利用 AI技術(shù)（機器學習、大模型、運籌優(yōu)化等），對基礎(chǔ)架構(gòu)和系統(tǒng)的全生命周期進行自動優(yōu)化。優(yōu)化對象包括：數(shù)據(jù)庫、存儲、大數(shù)據(jù)系統(tǒng)、虛機、容器、網(wǎng)絡(luò)、運維和穩(wěn)定性等。ByteBrain 的主要方向為AIOPS、AI4DB、運籌優(yōu)化、LLM4Infra，功能模塊包括容量規(guī)劃、資源調(diào)度、系統(tǒng)調(diào)參、異常檢測、根因分析、慢SQL優(yōu)化、Text2SQL、LLM-AGENT 等。ByteBrain團隊正在招聘相關(guān)方向的研究員和實習生，聯(lián)系方式：tieying.zhang@bytedance.com