論文の概要: FactorJoin: A New Cardinality Estimation Framework for Join Queries

• arxiv url: http://arxiv.org/abs/2212.05526v1
• Date: Sun, 11 Dec 2022 15:51:39 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-13 18:17:28.455988
• Title: FactorJoin: A New Cardinality Estimation Framework for Join Queries
• Title（参考訳）: FactorJoin: ジョインクエリのための新しいカーディナリティ推定フレームワーク
• Authors: Ziniu Wu, Parimarjan Negi, Mohammad Alizadeh, Tim Kraska, Samuel Madden
• Abstract要約: カーディナリティ推定は、クエリ最適化における最も根本的で難しい問題の1つである。 結合クエリを推定する新しいフレームワークであるFacterJoinを提案する。 評価において、FacterJoinは従来の最先端の学習手法よりも効果的に推定できる。
• 参考スコア（独自算出の注目度）: 35.22928513918166
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Cardinality estimation is one of the most fundamental and challenging problems in query optimization. Neither classical nor learning-based methods yield satisfactory performance when estimating the cardinality of the join queries. They either rely on simplified assumptions leading to ineffective cardinality estimates or build large models to understand the data distributions, leading to long planning times and a lack of generalizability across queries. In this paper, we propose a new framework FactorJoin for estimating join queries. FactorJoin combines the idea behind the classical join-histogram method to efficiently handle joins with the learning-based methods to accurately capture attribute correlation. Specifically, FactorJoin scans every table in a DB and builds single-table conditional distributions during an offline preparation phase. When a join query comes, FactorJoin translates it into a factor graph model over the learned distributions to effectively and efficiently estimate its cardinality. Unlike existing learning-based methods, FactorJoin does not need to de-normalize joins upfront or require executed query workloads to train the model. Since it only relies on single-table statistics, FactorJoin has small space overhead and is extremely easy to train and maintain. In our evaluation, FactorJoin can produce more effective estimates than the previous state-of-the-art learning-based methods, with 40x less estimation latency, 100x smaller model size, and 100x faster training speed at comparable or better accuracy. In addition, FactorJoin can estimate 10,000 sub-plan queries within one second to optimize the query plan, which is very close to the traditional cardinality estimators in commercial DBMS.
• Abstract（参考訳）: 基数推定はクエリ最適化における最も基本的かつ困難な問題の1つである。 古典的手法も学習的手法も、結合クエリの濃度を推定する際に満足な性能は得られない。 それらは単純化された仮定に頼るか、データ分布を理解するために大規模なモデルを構築し、長い計画時間とクエリ間の一般化性の欠如をもたらす。 本稿では,結合クエリを推定するための新しいフレームワークであるfactorjoinを提案する。 FactorJoinは、古典的な結合ヒストグラム法の背後にあるアイデアを組み合わせて、結合を学習に基づく手法で効率的に処理し、属性相関を正確に捉える。 具体的には、FactJoinはDBのすべてのテーブルをスキャンし、オフライン準備フェーズ中に単一テーブルの条件分布を構築する。 結合クエリが現れると、factorjoinはそれを学習した分布よりも係数グラフモデルに変換し、効果的かつ効率的に濃度を推定する。 既存の学習ベースの方法とは異なり、factorjoinは結合を事前に非正規化したり、モデルをトレーニングするために実行されたクエリワークロードを必要とする必要はない。 シングルテーブルの統計にのみ依存するため、FactJoinは空間オーバーヘッドが小さく、トレーニングとメンテナンスが極めて容易である。 評価では、FactJoinは、従来の最先端の学習ベース手法よりも、40倍のレイテンシ、100倍のモデルサイズ、100倍の高速なトレーニング速度で、より効果的な評価を行うことができる。 さらに、FactJoinは1秒以内に10,000のサブプランクエリを推定してクエリ計画を最適化することができる。

関連論文リスト

• GenJoin: Conditional Generative Plan-to-Plan Query Optimizer that Learns from Subplan Hints [1.3108652488669732]
  我々は,クエリ最適化問題を共生生成タスクとして考える,新しい学習クエリであるGenJoinを提案する。 GenJoinは、よく知られた2つの実世界のベンチマークの最先端メソッドと同様に、大きく、一貫してパフォーマンスを向上する最初の学習クエリである。
  論文  参考訳（メタデータ） (2024-11-07T08:31:01Z)
• CardBench: A Benchmark for Learned Cardinality Estimation in Relational Databases [17.46316633654637]
  データベースにおける高いクエリパフォーマンスを実現するには、心臓病推定が不可欠である。 研究者が新しい学習アプローチによる進捗を評価することができるような、体系的なベンチマークやデータセットは存在しない。 我々は,20の異なる実世界のデータベースに数千のクエリを格納したベンチマークを,学習された濃度推定のためにリリースした。
  論文  参考訳（メタデータ） (2024-08-28T23:25:25Z)
• JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning [58.71541261221863]
  結合順序選択(JOS)は、クエリの実行コストを最小化するために結合操作を順序付けする問題である。 木質強化学習(RL)のためのクエリ最適化環境JoinGymを提案する。 JoinGymは内部で、事前計算されたデータセットから中間結果の濃度を調べることで、クエリプランのコストをシミュレートする。
  論文  参考訳（メタデータ） (2023-07-21T17:00:06Z)
• Scardina: Scalable Join Cardinality Estimation by Multiple Density Estimators [8.641606056228675]
  機械学習に基づく濃度推定手法が従来の手法に取って代わっている。 スキーマ構造に基づく分割モデルを用いた新しい結合濃度推定法であるScardinaを提案する。
  論文  参考訳（メタデータ） (2023-03-31T13:22:28Z)
• Lero: A Learning-to-Rank Query Optimizer [49.841082217997354]
  これは、ネイティブクエリの上に構築され、クエリ最適化を改善するために継続的に学習される。 Leroはスクラッチから学習を構築するのではなく、数十年にわたるデータベースの知恵を活用し、ネイティブ性を改善するように設計されている。 Leroはいくつかのベンチマークでほぼ最適なパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2023-02-14T07:31:11Z)
• DORE: Document Ordered Relation Extraction based on Generative Framework [56.537386636819626]
  本稿では,既存のDocREモデルの根本原因について検討する。 本稿では,モデルが学習しやすく,決定論的な関係行列から記号列と順序列を生成することを提案する。 4つのデータセットに対する実験結果から,提案手法は生成型DocREモデルの性能を向上させることができることが示された。
  論文  参考訳（メタデータ） (2022-10-28T11:18:10Z)
• Glue: Adaptively Merging Single Table Cardinality to Estimate Join Query Size [35.1093718746362]
  カーディナリティ推定(CardEst)は、高品質なクエリプランを生成する上で重要な役割を果たす。 CardEstの最も難しい問題、すなわち、複数のテーブル上でジョインクエリサイズを推定する方法は、広く解決されていない。 本稿では,テーブル単位のCardEst結果をサポートするGlueという,非常に一般的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-12-07T02:46:46Z)
• Robust Generalization and Safe Query-Specialization in Counterfactual Learning to Rank [62.28965622396868]
  本稿では,特徴量に基づく対実的学習手法であるgenSPECアルゴリズムについて紹介する。 以上の結果から,GENSPECは十分なクリックデータを持つクエリに対して,ほとんどあるいはノイズのないクエリに対してロバストな振る舞いを持ちながら,最適なパフォーマンスを実現することが示唆された。
  論文  参考訳（メタデータ） (2021-02-11T13:17:26Z)
• FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation [45.98791307420517]
  確率計算の高速化とグラフィカルモデルサイズの軽量化,推定精度の向上を実現したCardEst法であるFLATを提案する。 FLATは、基礎となるFSPNモデル上で、ほぼ線形時間で効率的なオンライン確率計算をサポートする。 単一のテーブルクエリとマルチテーブルジョインクエリの両方の濃度を推定できる。 1〜5桁の精度、1〜3桁の確率速度、1～2桁のストレージコストを実現する。
  論文  参考訳（メタデータ） (2020-11-18T01:14:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。