Optimizing join index based join processing: a graph partitioning approach

Sivakumar Ravada, Shashi Shekhar, Chang tien Lu, Sanjay Chawla

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


The cost of join computation, which uses a join-index in a sequential system with limited buffer space, depends primarily on the page access sequence used to fetch the pages of the base relations. In this paper, we introduce a graph-partitioning model that will minimize the length of the page access sequence thus minimizes the redundant I/O, given a fixed buffer. Experiments with Sequoia 2000 data sets show that, the graph-partitioning method outperforms the existing methods based on sorting and online clustering, particularly for a small number of buffers and high join selectivity.

Original languageEnglish (US)
Pages (from-to)302-308
Number of pages7
JournalProceedings of the IEEE Symposium on Reliable Distributed Systems
StatePublished - Dec 1 1998


Dive into the research topics of 'Optimizing join index based join processing: a graph partitioning approach'. Together they form a unique fingerprint.

Cite this