Detecting and Exploiting Near-Sortedness for Efficient Relational Query Evaluation

Many relational operations are best performed when the relations are stored sorted over the relevant attributes (e.g. the common attributes in a natural join operation). However, generally relations are not stored sorted because it is expensive to maintain them this way (and impossible whenever there is more than one relevant sort key). Still, many times relations turn out to be nearly-sorted, where most tuples are close to their place in the order. This state can result from "Leftover sortedness", where originally sorted relations were updated, or were combined into interim results when evaluating a complex query.

Provided by: Association for Computing Machinery Topic: Data Management Date Added: Mar 2011 Format: PDF

Find By Topic