Optimizing join index based join processing: a graph partitioning approach

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

Optimizing join index based join processing: a graph partitioning approach

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

^*Corresponding author for this work

University of Minnesota Twin Cities

Research output: Contribution to journal › Conference article › peer-review

4 Citations (Scopus)

Abstract

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 language	English
Pages (from-to)	302-308
Number of pages	7
Journal	Proceedings of the IEEE Symposium on Reliable Distributed Systems
Publication status	Published - 1998
Externally published	Yes
Event	Proceedings of the 1998 IEEE 17th Symposium on Reliable Distributed Systems, SRDS - West Lafayette, IN, USA Duration: 20 Oct 1998 → 23 Oct 1998

Cite this

@article{3910fae012b544eca64f858f6cf29fa6,

title = "Optimizing join index based join processing: a graph partitioning approach",

abstract = "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.",

author = "Sivakumar Ravada and Shashi Shekhar and Lu, \{Chang tien\} and Sanjay Chawla",

year = "1998",

language = "English",

pages = "302--308",

journal = "Proceedings of the IEEE Symposium on Reliable Distributed Systems",

issn = "1060-9857",

publisher = "IEEE Computer Society",

note = "Proceedings of the 1998 IEEE 17th Symposium on Reliable Distributed Systems, SRDS ; Conference date: 20-10-1998 Through 23-10-1998",

}

TY - JOUR

T1 - Optimizing join index based join processing

T2 - Proceedings of the 1998 IEEE 17th Symposium on Reliable Distributed Systems, SRDS

AU - Ravada, Sivakumar

AU - Shekhar, Shashi

AU - Lu, Chang tien

AU - Chawla, Sanjay

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0032313819

M3 - Conference article

AN - SCOPUS:0032313819

SN - 1060-9857

SP - 302

EP - 308

JO - Proceedings of the IEEE Symposium on Reliable Distributed Systems

JF - Proceedings of the IEEE Symposium on Reliable Distributed Systems

Y2 - 20 October 1998 through 23 October 1998

ER -

Optimizing join index based join processing: a graph partitioning approach

Abstract

Other files and links

Fingerprint

Cite this