When index retrieval is restricted to a range or singleton, an index scan is not done in its entirety because key portions before and after the range are skipped. Likewise, in some production databases, gaps between multiple ranges are skipped. However, ranges on the second attribute of a composite key are considered unproductive for key skip because they do not constitute a key range. This is not so. Restriction age=40 for index [sex,age] can be viewed as ORed singletons "female"/spl par/40 OR "male"/spl par/40 and gaps around them can be skipped using a fraction of I/Os needed for a full index scan. In this paper, a novel method of skipping gaps at index scan is introduced which, during index scan, detects practically all gaps for arbitrary Boolean restrictions and skips them. The efficiency of this technology is illustrated using a prototype implementation.

Order-preserving compression can improve sorting and searching performance, and hence the performance of database systems. We describe a new parsing (tokenization) technique that can be applied to variable-length "keys", producing substantial compression. It can both compress and decompress data, permitting variable lengths for dictionary entries and compressed forms. The key notion is to partition the space of strings into ranges, encoding the common prefix of each range. We illustrate our method with padding character compression for multi-field keys, demonstrating the dramatic gains possible. A specific version of the method has been implemented in Digital's Rdb relational database system to enable effective multi-field compression.

Addresses the key theoretical and practical issues of dynamic query optimization and reviews the underlying reasoning that cements the basic concepts of dynamic query optimization. The optimization mechanics are described, in concert with explanations of why and how certain arrangements contribute to a given optimization goal. Compared to traditional approaches, dynamic query optimization offers a much more realistic view of cost distribution modeling. It is a competition-based architecture that is capable of resolving the major limitations of static optimization, viz. the problems of data skew, cost function instability, and host-variable sensitivity.>