PJoin: MapReduceにおける高速ジョイン処理

• 鬼塚, 真

• 久保, 類

書誌事項

タイトル別名

• PJoin: Efficient Join Algorithm Based on MapReduce

抄録

MapReduceは分散処理フレームワークとして分析応用において広く利用されつつある．OLAPは分析応用の典型例の1つであり，OLAP分析ではスタースキーマによる多テーブルジョインが多く利用される特徴がある．しかし，MapReduceによるジョイン処理では，ジョイン対象となるテーブルをシャッフルにより通信しなければならずコストが大きいという問題があった．本論文では，MapReduceにおける高速ジョイン処理PJoinを提案する．PJoinの特徴は，ディメンジョンテーブルごとにジョイン対象となるテーブルの主キーと外部キーのペアを射影した実体化ビューを構築し，テーブルを主キーで分散配置し実体化ビューを外部キーで分散配置することで，mapタスクにおいてファクトテーブルとディメンションテーブル間の多テーブルのsemi-joinを実行することにある．TPC-Hのベンチマークによって評価した結果，PJoinにより応答性能が平均的に33.9%向上し，シャッフルによる通信量は62.6%削減できたことを確認した．

MapReduce is a distributed computation framework and is getting widely used in data intensive analytic applications. One important type of data analysis is OLAP, in which queries intensively use join operations for multi-dimensional aggregations. However, a typical join algorithm used in MapReduce, reduce-side join, shuffles the records of the join tables by the join key, which greatly increases the network overhead. We propose PJoin, an efficient join algorithm for MapReduce. The features of PJoin are 1) to materialize projection views required for semi-joins, and 2) to pre-partition them and base tables by foreign keys and primary keys, respectively. Thus, semi-joins between two tables that are connected by one-to-many relationships are to be made without shuffle. We use the TPC-H benchmark to verify the efficiency of PJoin and show that it improves the response time by 33.9% over the reduce-side join. Its key advances are a 62.6% reduction in shuffle size.

収録刊行物

• 情報処理学会論文誌データベース（TOD）

  情報処理学会論文誌データベース（TOD） 6 (3), 105-119, 2013-06-28

キーワード

• [研究論文] MapReduce，OLAP分析，最適化

詳細情報

• CRID: 1050282812879929344
• NII論文ID: 110009579669
• NII書誌ID: AA11464847
• ISSN: 18827799
• Web Site: http://id.nii.ac.jp/1001/00092736/
• 本文言語コード: ja
• 資料種別: article
• データソース種別:
  • IRDB
  • CiNii Articles