Title:	EQUI JOIN QUERY ACCELERATION USING ALGEBRAIC SIGNATURES
Author(s):	Riad Mokadem , Abdelkader Hameurlain , Franck Morvan
ISBN:	978-972-8924-56-0
Editors:	Nuno Guimarães and Pedro Isaías
Year:	2008
Edition:	Single
Keywords:	Hash Join Algorithms, Algebraic Signatures, String Matching, Performance Evaluation
Type:	Full Paper
First Page:	78
Last Page:	85
Language:	English
Cover:
Full Contents:	click to dowload
Paper Abstract:	Evaluation of join queries is very challenging since they have to deal with an increasing data size. We study the relational join query processing realized by hash tables and we focus on the case of equi join queries. We propose to use a new form of signatures, the algebraic signatures, for fast comparison between values of two attributes in relations participating in an equi join operations. Our technique is efficient especially when the attribute join is a long string. In this paper, we investigate this issue and prove that algebraic signatures combined to known hash join technique constitute an efficient method to accelerate equi join operations. Algebraic signatures allow fast string search. They are descending from the Karp-Rabin signatures. String matching using our algebraic calculus is then several times faster comparing to the fastest known methods, e.g. Boyer Moore. We justify our approach and present an experimental evaluation. We also present a cost analysis for an equi join operation using algebraic signatures. The performance evaluation of our technique shows the improvement of query processing times. We also discuss the reductions of required memory sizes and the disk I/O. The main contribution of this paper is the using of algebraic signatures to accelerate equi join operations especially when the attribute join is a long string and to avoid multiples I/O disk by reduce memory requirement.
	Go Back