Accelerating database queries containing bitmap-based conditions

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.

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.

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.

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 a presence of a disjunction expression in a 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, 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 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 bitmap result determined, in part, using the restricted evaluation of the disjunctive condition.

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 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, 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, a restriction bitmap for the 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;
• receiving, in response to the determining, a satisfaction bitmap for each disjunctive condition of the disjunction expression, the satisfaction bitmap representing a set of rows that have satisfied the one or more preceding disjunctive conditions in said disjunction, 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 disjunctive expression using the satisfaction bitmap and the restriction bitmap;
• responsive to determining that the disjunctive condition has a respective cost saving that justifies restricting evaluation, restricting, evaluation of the disjunctive condition to a set of rows that are within the restriction bitmap and not within the satisfaction bitmap;
• and
• providing a bitmap result of evaluating the disjunction expression, the bitmap result determined, in part, using the restricted evaluation of the disjunctive condition.