論文の概要: Graphical Join: A New Physical Join Algorithm for RDBMSs

• arxiv url: http://arxiv.org/abs/2206.10435v1
• Date: Tue, 21 Jun 2022 14:29:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-22 22:11:09.308884
• Title: Graphical Join: A New Physical Join Algorithm for RDBMSs
• Title（参考訳）: Graphical Join: RDBMSのための新しい物理結合アルゴリズム
• Authors: Ali Mohammadi Shanghooshabad and Peter Triantafillou
• Abstract要約: GJのような結合アルゴリズムは、時間と空間において大きなパフォーマンス上の利点をもたらすことができることを示す。 インメモリ結合計算の結果、MonetDBやUmbraよりも64X、388X、6倍パフォーマンスが向上した。
• 参考スコア（独自算出の注目度）: 9.797488793708624
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Join operations (especially n-way, many-to-many joins) are known to be time- and resource-consuming. At large scales, with respect to table and join-result sizes, current state of the art approaches (including both binary-join plans which use Nested-loop/Hash/Sort-merge Join algorithms or, alternatively, worst-case optimal join algorithms (WOJAs)), may even fail to produce any answer given reasonable resource and time constraints. In this work, we introduce a new approach for n-way equi-join processing, the Graphical Join (GJ). The key idea is two-fold: First, to map the physical join computation problem to PGMs and introduce tweaked inference algorithms which can compute a Run-Length Encoding (RLE) based join-result summary, entailing all statistics necessary to materialize the join result. Second, and most importantly, to show that a join algorithm, like GJ, which produces the above join-result summary and then desummarizes it, can introduce large performance benefits in time and space. Comprehensive experimentation is undertaken with join queries from the JOB, TPCDS, and lastFM datasets, comparing GJ against PostgresQL and MonetDB and a state of the art WOJA implemented within the Umbra system. The results for in-memory join computation show performance improvements up to 64X, 388X, and 6X faster than PostgreSQL, MonetDB and Umbra, respectively. For on-disk join computation, GJ is faster than PostgreSQL, MonetDB and Umbra by up to 820X, 717X and 165X, respectively. Furthermore, GJ space needs are up to 21,488X, 38,333X, and 78,750X smaller than PostgresQL, MonetDB, and Umbra, respectively.
• Abstract（参考訳）: 結合操作(特にn-way, many-to-many joins)は時間とリソース消費であることが知られている。 大規模では、テーブルサイズとジョインサイズに関して、現在の最先端技術(Nested-loop/Hash/Sort-merge Joinアルゴリズムを使ったバイナリジョイン計画と、最悪ケースの最適ジョインアルゴリズム(WOJA)の両方を含む)は、適切なリソースと時間制約を与えられた答えを生成できない。 本稿では, n-way equi-join処理のための新しい手法であるgraphical join (gj)を提案する。 まず、物理結合計算問題をPGMにマッピングし、Run-Length Encoding (RLE)ベースの結合-resultサマリを計算できる微調整推論アルゴリズムを導入する。 第2に,上述のジョイン/リサート要約を生成してデサム化するGJのような結合アルゴリズムが,時間と空間において大きなパフォーマンス上のメリットをもたらすことを示す。 JOB、TPCDS、最後のFMデータセットからの結合クエリを用いて総合的な実験が行われ、PostgresQLとMonetDBに対するGJと、Umbraシステムで実装されたアートWOJAの状態を比較している。 インメモリ結合計算の結果、PostgreSQL、MonetDB、Umbraよりも64X、388X、6倍パフォーマンスが向上した。 ディスク上の結合計算では、GJはPostgreSQL、MonetDB、Umbraよりも最大820X、717X、165X高速である。 さらに、GJスペースの必要性は、PostgresQL、MonetDB、Umbraよりも最大21,488X、38,333X、78,750X小さい。

関連論文リスト

• FastGAS: Fast Graph-based Annotation Selection for In-Context Learning [53.17606395275021]
  インコンテキスト学習(ICL)は、大規模言語モデル(LLM)に対して、一連のトレーニングインスタンスをプロンプトとして使用することにより、新しいタスクに対処する権限を与える。 既存の手法では、アノテーションのラベルなし例のサブセットを選択する方法が提案されている。 本稿では,高品質なインスタンスを効率的に識別するグラフベースの選択手法であるFastGASを提案する。
  論文  参考訳（メタデータ） (2024-06-06T04:05:54Z)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  本稿では,大規模言語モデルの制約を克服する新しいトレーニングフリースキームである階層型cOntext MERging(HOMER)を提案する。 HomeRは、長いインプットを管理可能なチャンクに分割する、分別/対数アルゴリズムを使用する。 トークン削減技術がマージ毎に先行し、メモリ使用効率が保証される。
  論文  参考訳（メタデータ） (2024-04-16T06:34:08Z)
• JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning [58.71541261221863]
  結合順序選択(JOS)は、クエリの実行コストを最小化するために結合操作を順序付けする問題である。 木質強化学習(RL)のためのクエリ最適化環境JoinGymを提案する。 JoinGymは内部で、事前計算されたデータセットから中間結果の濃度を調べることで、クエリプランのコストをシミュレートする。
  論文  参考訳（メタデータ） (2023-07-21T17:00:06Z)
• DeepJoin: Joinable Table Discovery with Pre-trained Language Models [10.639106014582756]
  既存のアプローチは、統一されたビューを作成するためのテーブルを組み合わせる最も一般的な方法である、等結合をターゲットにしている。 Deepjoinは、正確で効率的な結合可能なテーブルディスカバリのためのディープラーニングモデルである。 Deepjoinは、専門家のラベルで評価した場合、セマンティック結合の正確なソリューションよりもはるかに正確です。
  論文  参考訳（メタデータ） (2022-12-15T02:40:57Z)
• FactorJoin: A New Cardinality Estimation Framework for Join Queries [35.22928513918166]
  カーディナリティ推定は、クエリ最適化における最も根本的で難しい問題の1つである。 結合クエリを推定する新しいフレームワークであるFacterJoinを提案する。 評価において、FacterJoinは従来の最先端の学習手法よりも効果的に推定できる。
  論文  参考訳（メタデータ） (2022-12-11T15:51:39Z)
• Integrating connection search in graph queries [6.948362325254044]
  SPARQLやCypherといったグラフクエリ言語に接続ツリーパターン(CTP)を統合する方法を示す。 非常に大きな探索空間に対処するため,我々は効率的な刈り込み手法を提案し,我々のアルゴリズムMOLESPがプルーニングでも完備しているケースの集合を正式に確立する。
  論文  参考訳（メタデータ） (2022-08-09T14:27:57Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)
• Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
  Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。 代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。 データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
  論文  参考訳（メタデータ） (2021-12-06T20:34:55Z)
• Exploiting Database Management Systems and Treewidth for Counting [22.315022989618594]
  正規カウント問題は#SATであり、ブール公式の割り当てを数えるように求めている。 最近の研究によると、#SATのベンチマークインスタンスは、適度に小さなツリー幅を持つことが多い。 本稿では,最先端データベース管理システムに基づく質問数解決のための一般的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-01-13T12:45:22Z)

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

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