# 近似クエリ処理 ## 定義 近似クエリ処理(Approximate Query Processing, AQP)は、推定精度を犠牲にする代わりに、複雑なクエリの**運用コストとレイテンシをさらに下げる**手法群。near real-time な分析を要し、近似だが高精度な結果(例: 95% 以上)を許容できる用途——データセンターのアラート、ネットワーク計測、オートスケール——で有効。主に 2 系統がある: (1) **サンプリングベース**(データサンプルを事前処理してクエリ時に使う。任意クエリに適用できるが quantile・entropy など複雑統計で精度が劣化し不安定)、(2) **スケッチベース**(取り込み時にコンパクトなサマリを作り、可証明な誤差境界つきで統計を推定する。sub-linear 空間だが特定クエリ種に限られがち)。([[@2025__VLDB__Approximation-First Timeseries Monitoring Query At Scale]]) 時系列モニタリングでは、スライディングウィンドウに対する集約(quantile・count・distinct・entropy・L2 norm・TopK)を近似する。固定ウィンドウ用のスライディングウィンドウスケッチ(sliding sum、0-1 counting、heavy hitter、distinct counting、sliding quantile)が個別に存在するが、任意サブウィンドウクエリを支援しないものが多い。Exponential Histogram(EH)や Smooth Histogram(SH)は `o(N)` メモリで直近ウィンドウの推定を与えるウィンドウベースフレームワークで、これにスケッチを部品として載せると任意サブウィンドウ・多様な統計を支援できる。([[@2025__VLDB__Approximation-First Timeseries Monitoring Query At Scale]]) ## 横断的知見 - **単一フィールドスケッチと多フィールド生成モデルの汎用性トレードオフ**: PromSketch([[@2025__VLDB__Approximation-First Timeseries Monitoring Query At Scale]])はスライディングウィンドウ上の分位数・エントロピー・distinct カウント等を可証明誤差境界つきで推定する。特定の統計種に特化し sub-linear メモリで高速クエリを実現する。一方 PrvTel([[@2026__NSDI__PrvTel - Lightweight Models for Private and Accurate Telemetry Data Retention]])は複数フィールドの組み合わせ(クロスフィールドカーディナリティ・頻度分布等)を生成モデルから回答できるが、スケッチが対応可能な事前指定クエリでは精度・速度で劣る場合がある。両手法はカバーする「クエリ空間の幅」と「特定クエリへの精度保証の強さ」のトレードオフで補完的に位置づけられる。(Source: [[@2025__VLDB__Approximation-First Timeseries Monitoring Query At Scale]], [[@2026__NSDI__PrvTel - Lightweight Models for Private and Accurate Telemetry Data Retention]]) - **差分プライバシーを組み込んだ近似クエリ回答の方式が二系統に分岐する**: (a) スケッチへの DP ノイズ注入(Count-Sketch・HyperLogLog の初期化時にガウスノイズを追加)は可証明誤差境界を持ちリアルタイム処理に向くが、クロスフィールドクエリを支援しない。(b) PrvTel の「事前データ摂動→生成モデル学習→合成データからクエリ回答」方式は後処理不変性定理で ε-DP を保証し、広域クエリに答えられるが、個別クエリへの最悪ケース保証はない。長期縦断保持 + 広域クエリには(b)が、リアルタイム + 特定統計には(a)が適する。(Source: [[@2026__NSDI__PrvTel - Lightweight Models for Private and Accurate Telemetry Data Retention]], [[@2025__VLDB__Approximation-First Timeseries Monitoring Query At Scale]]) ## 未解決の問い - AQP の誤差保証は統計量に強く依存する(サンプリングは quantile で弱く、スケッチは種別が限られる)。1 つのフレームワークでどこまで広い統計クラスに**一様な保証**を与えられるか。Universal Sketching の GSum クラス(L0/L1/L2/entropy/TopK)はその一つの答えだが、上限はどこか。([[@2025__VLDB__Approximation-First Timeseries Monitoring Query At Scale]]) - 近似は「ダウンストリームが誤差を許容する」前提に立つ。どの監視・アラート用途が実際に 5% 誤差を許せるか、許せないかを切り分ける基準は何か。誤差予算(error budget)を運用指標として管理できるか。 - 時間次元の集約は AQP で攻められたが、**ラベル次元**の集約(高カーディナリティの label join・group-by)への近似はどう設計するか([[PromSketch]] の将来課題)。 - スケッチを中間キャッシュとして持つと、障害時の再構築・out-of-order データ・重複排除との整合をどう保つか。 ## 関連 - ソース: [[@2025__VLDB__Approximation-First Timeseries Monitoring Query At Scale]] / [[@2026__NSDI__PrvTel - Lightweight Models for Private and Accurate Telemetry Data Retention]] - 概念: [[時系列データベース]] / [[テレメトリ]] / [[異常検知]] / [[差分プライバシー]] - エンティティ: [[PromSketch]] / [[Prometheus]] / [[VictoriaMetrics]] / [[Zaoxing Liu]] - 関連 MOC: [[SRE - MOC]] ## 出典 - [[@2025__VLDB__Approximation-First Timeseries Monitoring Query At Scale]](§2.4 AQP の分類、§4 EH+KLL / EH+Universal Sketching の構成と誤差境界) - [[@2026__NSDI__PrvTel - Lightweight Models for Private and Accurate Telemetry Data Retention]](§2.2 スケッチの限界とクロスフィールドクエリ非対応、§5.2–5.3 単一フィールド・クロスフィールドクエリ精度評価、§5.6 DP 下の精度-プライバシートレードオフ)