Counter reduction technique for combined processing of selection and join

摘要

A query processing technique called counter reduction is presented. When a query on two relations contains a join and a selection, an ordinary query optimizer arranges for the selection to be done first, in order to reduce the size of the join operands. The counter reduction technique reduces the size of both the join operands before or during the join processing even if the selection is specified on only one operand. The trick can be used when relations are organized as hash files on the primary key and the selection is processed using indirect indices. In these conditions, counter reduction can be applied to an important class of joins called key joins. A key join is a natural join between the primary key of one operand and a part of the primary key of the other operand. Key joins appear very frequently in queries on databases which map hierarchy or network structures into a relational schema, when it is necessary to recover these semantics from a set of flat relations.The contributions of this paper include the introduction of the counter reduction technique, its extension to multiway key joins, a performance analysis and a comparison with other join algorithms.