|
|
|
     |
                                     |
Return to Optimization
Support for exploratory interaction with databases in applications such as data mining requires that the first few results of an operation be available as quickly as possible. We study the algorithmic side of what can and what cannot be achieved for processing join operations. We develop strategies that modify the strict two-phase processing of the sort-merge paradigm, intermingling join steps with selected merge phases of the sort. We propose an algorithm that produces early join results for a broad class of join problems, including many not addressed well by hash-based algorithms. Our algorithm has no significant increase in the number of I/O operations needed to complete the join compared to standard sort-merge algorithms.
@inproceedings {DBLP:conf/pods/DittrichSTW03, author = {Jens-Peter Dittrich and Bernhard Seeger and David Scot Taylor and Peter Widmayer}, booktitle = {PODS}, title = {On producing join results early.}, pages = {134-142}, year = {2003}, url = {db/conf/pods/pods2003.html#DittrichSTW03}, ee = {http://doi.acm.org/10.1145/773153.773167}, crossref = {conf/pods/2003}, bibsource = {DBLP, http://dblp.uni-trier.de} }  ©2004 Association for Computing Machinery |
