US 7,480,649 B2Granted

Method for efficient evaluation of index screening predicates

AssigneeInternational Business Machines Corporation

InventorsYou-Chin Fuh, Ping Wang, Li Xia, Binghua Zhen

Life of this patent

Estimating the term…

Abstract

Techniques are provided for processing a query using an index. It is determined whether a number of consecutive keys that evaluate to a false-positive when applying a screening predicate in the query exceeds a false-positive predefined value. One or more keys in the index are skipped in response to determining that the number of consecutive keys exceeds the false-positive predefined value.

Claims8

Dependent claims

A method for processing a query using an index, comprising:

determining that index matching predicate filtering is not good and that index screening predicate filtering is good for the query, wherein the filtering uses statistics to provide an estimate of results that may be obtained by applying a predicate relative to an original number of keys against which the predicate is applied;
determining that an index full key cardinality divided by an index matching column cardinality is greater than a ratio predefined value, wherein the index full key cardinality is a number of distinct key values for index columns, and wherein the matching column cardinality is a number of distinct key values for a column associated with the matching predicate;
and
setting a skipping mode indicator to indicate that skipping is enabled;
determining whether a number of consecutive keys that evaluate to a false-positive when applying a screening predicate in the query exceeds a false-positive predefined value, wherein, for a key in a range defined by a matching predicate, the number of consecutive keys that evaluate to a false-positive is incremented when the key does not match the screening predicate, wherein the matching predicate has a constraint on a leading index column, and wherein the screening predicate filters the keys in the range defined by the matching predicate;
starting skipping of one or more keys in the index based on a skip interval in response to determining that the number of consecutive keys exceeds the false-positive predefined value, wherein the skipping allows a number of keys qualified by the matching predicate in the query to be skipped without being fetched and evaluated for the screening predicate;
and
in response to determining that evaluation of a key right after the skipping based on the skip interval reveals that the skip interval is too big,
backing up to a key from which the skipping was performed;
adjusting the skip interval;
incrementing a number of skipping failures by one;
determining whether a number of skipping failures is greater than a skipping failures predefined threshold;
in response to determining that the number of skipping failures is greater than a skipping failures predefined threshold,
stopping the skipping;
and
in response to determining that the number of consecutive keys exceeds the false-positive predefined value, restarting the skipping of the one or more keys;
and
in response to determining that the number of skipping failures is not greater than a skipping failures predefined threshold, skipping one or more keys in the index based on the adjusted skip interval.

15 more elements

Dependencies are inferred from the claim text.

patentgrep

Loading patent…

Abstract

A method for processing a query using an index, comprising:

determining that index matching predicate filtering is not good and that index screening predicate filtering is good for the query, wherein the filtering uses statistics to provide an estimate of results that may be obtained by applying a predicate relative to an original number of keys against which the predicate is applied;
determining that an index full key cardinality divided by an index matching column cardinality is greater than a ratio predefined value, wherein the index full key cardinality is a number of distinct key values for index columns, and wherein the matching column cardinality is a number of distinct key values for a column associated with the matching predicate;
and
setting a skipping mode indicator to indicate that skipping is enabled;
determining whether a number of consecutive keys that evaluate to a false-positive when applying a screening predicate in the query exceeds a false-positive predefined value, wherein, for a key in a range defined by a matching predicate, the number of consecutive keys that evaluate to a false-positive is incremented when the key does not match the screening predicate, wherein the matching predicate has a constraint on a leading index column, and wherein the screening predicate filters the keys in the range defined by the matching predicate;
starting skipping of one or more keys in the index based on a skip interval in response to determining that the number of consecutive keys exceeds the false-positive predefined value, wherein the skipping allows a number of keys qualified by the matching predicate in the query to be skipped without being fetched and evaluated for the screening predicate;
and
in response to determining that evaluation of a key right after the skipping based on the skip interval reveals that the skip interval is too big,
backing up to a key from which the skipping was performed;
adjusting the skip interval;
incrementing a number of skipping failures by one;
determining whether a number of skipping failures is greater than a skipping failures predefined threshold;
in response to determining that the number of skipping failures is greater than a skipping failures predefined threshold,
stopping the skipping;
and
in response to determining that the number of consecutive keys exceeds the false-positive predefined value, restarting the skipping of the one or more keys;
and
in response to determining that the number of skipping failures is not greater than a skipping failures predefined threshold, skipping one or more keys in the index based on the adjusted skip interval.

15 more elements