並列データベースシステムにおける多重結合演算処理の最適化とその評価

• Item type: SIG Technical Reports(1)
• 公開日: 1995-08-23
• タイトル: 並列データベースシステムにおける多重結合演算処理の最適化とその評価
• タイトル / 言語: en
• タイトル: Optimization of Multi - Way Join in Parallel Database Systems and its Performance Evaluation
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学生産技術研究所
• 著者所属: 東京大学生産技術研究所
• 著者所属: 東京大学生産技術研究所
• 著者所属(英): en
• 著者所属(英): Institute of Industrial Science, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Institute of Industrial Science, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Institute of Industrial Science, University of Tokyo
• 著者名: 中野, 美由紀; 新谷, 隆彦; 喜連川, 優
• 著者名(英): Miyuki, Nakano; Takahiko, Shintani; Masaru, Kitsuregawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本報告では，非共有型並列計算機における多重結合演算処理の最適化方式として，ネットワークコスト，メモリなどのシステム資源の利用効率を考慮した方式を提案する．本方式では，ネットワークを最大限に有効利用するような部分木を生成し，生成された部分木を組み合わせることで最終スケジューリング木を得る．非共有型並列計算機における多重結合演算処理のコスト式を導入し、部分木の生成するための条件について詳細に述べる．さらに，従来の最適化方式であるleft?deep木，right?deep木，segmented right?deep木との性能比較を行ない，われわれの提案する最適化方式が最適な木を生成する率が高いのみならず，検索空間も従来のフルサーチ方式と比較して十分に実用に適するだけ小さいことを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we consider parallel multi-way join processing in a shared-nothing environment and propose a new multi-join scheduling algorithm which optimizes a query tree taking into account a finite bandwidth network. Our algorithm first generates sub-tree seeds which fully consumes the network bandwidth in pipeline processing. Then, these sub-tree seeds are combined to produce an optimal query tree. The restriction conditions for generating a sub-tree seed which balances I/O accesses and network transfers and which uses less memory are described in detail. The proposed algorithm for generating the multi-way join plan is evaluated in comparison with former work by using the introduced cost formula. From the evaluation results, not only is the quality of the proposed method better than previously presented algorithms such as left-deep, right-deep and segmented right-deep trees, but the quality of our algorithm does not deteriorate comparatively.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 情報処理学会研究報告計算機アーキテクチャ（ARC）; 巻 1995, 号 80(1995-ARC-113), p. 145-152, 発行日 1995-08-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会