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.