Accelerating database queries containing bitmap-based conditions

Patent metadata

Field	Value
Publication number	US-9317556-B2
Application number	US-89231210-A
Country	US
Kind code	B2
Filing date	Sep 28, 2010
Priority date	Sep 28, 2010
Publication date	Apr 19, 2016
Grant date	Apr 19, 2016

Abstract

Systems, methods and articles of manufacture for accelerating database queries containing bitmap-based conditions are described herein. An embodiment includes determining a bitmap, where the bitmap represents a set of rows that have satisfied one or more conjunctive conditions which preceded a conjunct that is a disjunction in a query expression and restricting evaluation of a disjunct within the disjunction to the set of rows represented by the bitmap. Another embodiment includes determining a satisfaction bitmap, where the bitmap represents the result of one or more preceding disjuncts in a disjunction within a query expression and restricting scope of evaluation of a disjunct to a set of rows that are not within the determined satisfaction bitmap. In this way, embodiments of the present invention enable the acceleration of queries containing disjunctions of conditions on a database table, as well as reduce the temporary resources consumed for such queries.

First claim

What is claimed is:

1. A computer implemented method, comprising:
determining, by at least one processor, a presence of a disjunction expression in a complex query expression, the disjunction expression including a disjunctive operator and a plurality of disjunctive conditions, wherein the complex query expression comprises a conjunction expression including a conjunction operator, the disjunction expression, and one or more conjunctive conditions that precede the disjunction expression;
receiving, in response to the determining, by the at least one processor, a restriction bitmap for each disjunction expression in the complex query expression, the restriction bitmap representing a set of rows that have satisfied the one or more preceding conjunctive conditions, wherein a bit from the restriction bitmap represents whether a respective row has satisfied the one or more preceding conjunctive conditions;
determining whether respective cost savings justify restricting evaluation of each disjunctive condition from the plurality of disjunctive conditions using the restriction bitmap;
responsive to determining that a disjunctive condition from the plurality of disjunctive conditions has a respective cost saving that justifies restricting evaluation, restricting, by the at least one processor, evaluation of the disjunctive condition from the plurality of disjunctive conditions to the set of rows represented by the restriction bitmap; and
providing, by the at least one processor, a bitmap result of evaluating the disjunction expression, the bitmap result determined, in part, using the restricted evaluation of the disjunctive condition.

2. The method of claim 1 , further comprising:
comparing said cost savings against a cost of additional bitmap operations before performing said restricting.

3. The method of claim 1 , further comprising:
if not all disjunctive conditions from the plurality of disjunctive conditions used said restricting, producing a final bitmap result for a conjunction of the disjunction expression and the one or more preceding conjunctive conditions by intersecting the bitmap result of the disjunction expression with the restriction bitmap.

4. The method of claim 1 , further comprising
reordering conjunctive conditions in the conjunction expression by placing conjunctive conditions that are disjunctions after conjunctive conditions that are not disjunctions.

5. A computer implemented method, comprising:
determining, by at least one processor, a presence of a disjunction expression in a complex query expression, the disjunction expression including a disjunctive operator, a disjunctive condition, and one or more disjunctive conditions that precede the disjunctive condition in the complex query expression;
receiving, in response to the determining, by the at least one processor, a satisfaction bitmap that represents a set of rows that have satisfied the one or more preceding disjunctive conditions, wherein a bit from the satisfaction bitmap represents whether a respective row has satisfied the one or more preceding disjunctive conditions;
determining whether respective cost savings justify restricting evaluation of each disjunctive condition within the disjunction expression using the satisfaction bitmap;
responsive to determining that the disjunctive condition has a respective cost saving that justifies restricting evaluation, restricting, by the at least one processor, scope of evaluation of the disjunctive condition to a set of rows that are not within the satisfaction bitmap; and
providing, by the at least one processor, a bitmap result of evaluating the disjunction expression, the final result determined, in part, using the restricted evaluation of the disjunctive condition.

6. The method of claim 5 , further comprising:
reordering, based on selectivities of respective disjunction conditions, disjunctive conditions in the disjunction expression from the least selective disjunctive condition to the most selective condition; and
evaluating the reordered disjunctive conditions.

7. A computer-based system, comprising:
a memory configured to store modules comprising:
a first module configured to determine a presence of a disjunction expression in a complex query expression, the disjunction expression including a disjunctive operator and a plurality of disjunctive conditions, wherein the complex query expression comprises a conjunction expression including a conjunction operator, the disjunction expression, and one or more additional conjunctive conditions that precede the disjunction expression;

a second module configured to receive, in response to the determining, a restriction bitmap for each disjunction expression in the complex query expression, the restriction bitmap representing a set of rows that have satisfied the one or more preceding conjunctive conditions, wherein a bit from the restriction bitmap represents whether a respective row has satisfied the one or more preceding conjunctive conditions; and
a third optimization module configured to:
determine whether respective cost savings justify restricting evaluation of each disjunctive condition from the plurality of disjunctive conditions using the restriction bitmap,
responsive to determining that a disjunctive condition from the plurality of disjunctive conditions has a respective cost saving that justifies restricting evaluation, restrict evaluation of the disjunctive condition to said set of rows represented by said restriction bitmap, and
provide a bitmap result of evaluating the disjunction expression, the bitmap result determined, in part, using the restricted evaluation of the disjunctive condition; and

at least one processor configured to process the first, second, and third modules.

8. A non-transitory computer-readable storage device having instructions stored thereon, execution of which by a computing device, cause said computing device to perform operations comprising:
determining, by at least one processor, a presence of a disjunction expression in a complex query expression, the disjunction expression including a disjunctive operator and a plurality of disjunctive conditions, wherein the complex query expression comprises a conjunction expression including a conjunction operator, the disjunction expression, and one or more conjunctive conditions that precede the disjunction expression;
receiving, in response to the determining, by the at least one processor, a restriction bitmap for each disjunction expression in the complex query expression, the restriction bitmap representing a set of rows that have satisfied the one or more preceding conjunctive conditions, wherein a bit from the restriction bitmap represents whether a respective row has satisfied the one or more preceding conjunctive conditions;
determining whether respective cost savings justify restricting evaluation of each disjunctive condition from the plurality of disjunctive conditions using the restriction bitmap;
responsive to determining that a disjunctive condition from the plurality of disjunctive conditions has a respective cost saving that justifies restricting evaluation, restricting, by the at least one processor, evaluation of the disjunctive condition to the set of rows represented by the restriction bitmap; and
providing, by the at least one processor, a bitmap result of evaluating the disjunction expression, the bitmap result determined, in part, using the restricted evaluation of the disjunctive condition.

9. The non-transitory computer-readable storage device of claim 8 , said operations further comprising:
comparing said cost savings against a cost of additional bitmap operations before performing said restricting.

10. The non-t

Assignees

• Kirk Steven A
• Walrath David E
• Sybase Inc

Inventors

• Kirk Steven A
• Walrath David E

Classifications

• G06F16/2456 Primary

  Join operations · CPC title

• G06F16/2237

  Vectors, bitmaps or matrices · CPC title

• G06F17/30324

  Physics · mapped topic

• G06F17/30498 Primary

  Physics · mapped topic