Optimizing the cost of relational queries using partial-relation schemes (Q1108822)

We propose a new access path to a relation, called a partial-relation scheme, in order to speed up the relational join operations. We present two join algorithms which preprocess the partial relations first and then join the selected tuples of the relations. We have considered join-only queries and queries involving restrictions, projections and joins. The performance of these algorithms is compared with sort-merge and hash- based join algorithms. The analysis is based on the cost of accesses to the secondary storage and the CPU usage. It has been shown that for wide range of selectivity factors and/or join factors the proposed algorithms perform better than the sort-merge and hash-based join algorithms.