導讀

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

背景

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

在現有的基數估計研究里，已經提出并廣泛應用了多種技術。這些技術主要有：

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

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

目標

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

同時，從實際工作負載上構建基數估計模型往往具有三大挑戰：

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

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

訓練數據

構建階段以以下輸入為基礎：

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

組合式設計

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

具體地，在此階段，本發明通過深度神經網絡為每個單表（base table）訓練兩類關鍵基礎模塊：

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

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

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

圖一： GRASP估計聯合查詢基數的例子

圖二：GRASP的組合式設計 vs 現有工作

訓練目標為最小化基數估計誤差（如對數平方誤差 SLE）。所有模塊均為可微結構，支持端到端優化。

ArCDF: Autoregressive CDF Modeling

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

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

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

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

[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) 模型架構

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

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

實驗與結果

1.顯著提升基數估計準確度（更準的預測結果）

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

2.有效提升查詢優化質量（更優的執行計劃）

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

ByteBrain團隊介紹

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