2026-03-15T02:54:49Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00074658 2025-01-21T21:29:15Z 934:1022:6385:6456

BFマージ結合：Bloomフィルタを保持するB+木を用いた低結合選択率に適した結合手法 BF Merge Join: A Merge Join for Low Selectivity Using Extended B+ Trees with Bloom Filters 的野, 晃整 スティーブン, リンデン 谷村, 勇輔 小島, 功 Akiyoshi, Matono Steven, Lynden Yusuke, Tanimura Isao, Kojima 研究論文 本論文では，結合不能タプルを読み飛ばしできるマージ結合アルゴリズム（BFマージ結合）と，それに用いる，各ノードにBloomフィルタを付与するよう拡張したB+木（BB+木）を提案する．BFマージ結合は，2つのBB+木の各ノードにおいて，子孫ノードの読み飛ばしのために，子孫集合が互いに素であるかどうかの判定を行う．この判定は，的野ら（2010）が提案した素集合判定可能なBloomフィルタを用いる．BB+木の機能として，Bloomフィルタを遅延更新可能なレコードの追加と削除に加え，木全体を高速にメンテナンスする操作も提案する．実験を通して，BB+木およびBFマージ結合の性能を評価した結果，BFマージ結合は選択率が低い等結合処理時に非常に効率的であることを確認した． In this paper, we propose a novel merge join algorithm, called BF merge join, that can skip dangling tuples using extended B+ trees, which we call BB+ trees, each node of which has Bloom filters to represent its descendant keys. BF merge join traverses BB+ trees, comparing nodes to check whether the nodes' descendants are disjoint ot not. This disjoint test uses Bloom filters that we have extended to be able to check whether they are disjoint. The proposed BB+ tree supports lazy scalable insertion and deletion. Furthermore, we propose a memtenance operation to updete entire tree. We evaluated the performance of our BB+ tree and BF merge join. The results show that a BF merge join can give performance improvements, especially in the case of low-selectivity equi-join queries. journal article 情報処理学会 2011-07-01 application/pdf 情報処理学会論文誌データベース（TOD） 2 4 114 125 1882-7799 AA11464847 https://ipsj.ixsq.nii.ac.jp/record/74658/files/IPSJ-TOD0402011.pdf jpn