Execution of negated conditions using a bitmap

Patent metadata

Field	Value
Publication number	US-9471634-B2
Application number	US-201414206531-A
Country	US
Kind code	B2
Filing date	Mar 12, 2014
Priority date	Mar 12, 2014
Publication date	Oct 18, 2016
Grant date	Oct 18, 2016

Abstract

Disclosed herein are system, method, and computer program product embodiments for accelerating database queries containing bitmap-based conditions. An embodiment operates by determining a bitmap, where the bitmap represents a set of rows that have satisfied a conjunct that precedes a negated condition in a query expression and restricting the evaluation of the negated condition to the set of rows represented by the bitmap.

First claim

What is claimed is:

1. A computer implemented method comprising:
rewriting, by a processor, a condition as a negated condition based on a determination that a collective cost of the rewriting and a negation operation is less than a cost of executing the condition;
determining, by the processor, a bitmap, wherein the bitmap represents a set of rows that have satisfied a conjunct that precedes the negated condition in a query expression, wherein the conjunct is a condition within a conjunction; and
restricting, by the processor, evaluation of the negated condition to the set of rows represented by the bitmap.

2. The method of claim 1 , further comprising:
determining a cost saving based on the restricting; and
comparing, before performing the restricting, the cost saving against a cost of an additional bitmap operation.

3. The method of claim 1 , wherein the negated condition is a negation of a second condition, the restricting further comprising:
restricting evaluation of the second condition to the set of rows represented by the bitmap before evaluating the negated condition.

4. The method of claim 1 , wherein the determining the bitmap comprises:
dividing a total set of rows, on which the bitmap is determined, into a plurality of work-units; and
determining a respective bitmap on each one of the plurality of work-units.

5. The method of claim 4 , wherein the restricting evaluation of the negated condition further comprises restricting evaluation of the negated condition to a set of rows represented by the respective bitmap on each one of the plurality of work-units.

6. The method of claim 5 , further comprising:
producing a respective final bitmap result on each one of the plurality of work-units by intersecting the respective bitmap of the conjunct and the negated condition on each one of the plurality of work-units; and
combining the respective final bitmap results to produce a final bitmap result.

7. A system, comprising:
a memory; and
at least one processor coupled to the memory and configured to:
rewrite a condition as a negated condition based on a determination that a collective cost of the rewriting and a negation operation is less than a cost of executing the condition;
determine, a bitmap, wherein the bitmap represents a set of rows that have satisfied a conjunct that precedes the negated condition in a query expression, wherein the conjunct is a condition within a conjunction; and
restrict evaluation of the negated condition to the set of rows represented by the bitmap.

8. The system of claim 7 , the at least one processor further configured to:
determine a cost saving based on the restricting; and
compare, before performing the restricting, the cost saving against a cost of an additional bitmap operation.

9. The system of claim 7 , wherein the negated condition is a negation of a second condition, and wherein to restrict evaluation the at least one processor is configured to:
restrict evaluation of the second condition to the set of rows represented by the bitmap before evaluating the negated condition.

10. A non-transitory tangible computer-readable device having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:
rewriting a condition as a negated condition based on a determination that a collective cost of the rewriting and a negation operation is less than a cost of executing the condition;
determining a bitmap, wherein the bitmap represents a set of rows that have satisfied a conjunct that precedes the negated condition in a query expression, wherein the conjunct is a condition within a conjunction; and
restricting evaluation of the negated condition to the set of rows represented by the bitmap.

11. The non-transitory computer-readable device of claim 10 , the operations further comprising:
determining a cost saving based on the restricting;
comparing, before performing the restricting, the cost saving against a cost of an additional bitmap operation; and
producing a final bitmap result by intersecting the bitmap of the conjunct and the negated condition after performing the restricting.

12. A computer implemented method comprising:
rewriting, by a processor, a condition as a negated condition based on a determination that a collective cost of the rewriting and a negation operation is less than a cost of executing the condition;
determining, by the processor, a satisfaction bitmap, wherein the satisfaction bitmap represents result of a disjunct that precedes the negated condition in a query expression, wherein the disjunct is a condition within a disjunction; and
restricting, by the processor, evaluation of the negated condition to a set of rows that are not within the determined satisfaction bitmap.

13. The method of claim 12 , further comprising:
determining a cost saving based on the restricting; and
comparing, before performing the restricting, the cost saving against a cost of an additional bitmap operation.

14. The method of claim 12 , wherein the negated condition is a negation of a second condition, the restricting further comprising:
restricting evaluation of the second condition to the set of rows that are not within the determined satisfaction bitmap before evaluating the negated condition.

15. The method of claim 12 , wherein the determining the satisfaction bitmap comprises:
dividing a total set of rows, on which the satisfaction bitmap is determined, into a plurality of work-units; and
determining a respective satisfaction bitmap on each one of the plurality of work-units.

16. The method of claim 15 , wherein the restricting evaluation of the negated condition further comprises restricting evaluation of the negated condition to a set of rows that are not within respective satisfaction bitmap on each one of the plurality of work-units.

17. The method of claim 16 , further comprising:
producing a respective final bitmap result on each one of the plurality of work-units by performing disjunction between the respective bitmap of the disjunct and the negated condition on each one of the plurality of work-units; and
combining the respective final bitmap results to produce a final bitmap result.

18. A system, comprising:
a memory; and
at least one processor coupled to the memory and configured to:
rewrite a condition as a negated condition based on a determination that a collective cost of the rewriting and a negation operation is less than a cost of executing the condition;
determine a satisfaction bitmap, wherein the satisfaction bitmap represents result of a disjunct that precedes the negated condition in a query expression, wherein the disjunct is a condition within a disjunction; and
restrict evaluation of the negated condition to a set of rows that are not within the determined satisfaction bitmap.

19. The system of claim 18 , the at least one processor further configured to:
determine a cost saving based on the restricting;
compare, before performing the restricting, the cost saving against a cost of an additional bitmap operation; and
produce a final bitmap result by performing disjunction between the bitmap of the disjunct and the negated condition after performing the restricting.

20. A non-transitory computer-readable device having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:
rewriting a condition as

Assignees

• Mittal Kaushal
• Chavan Mahendra
• Sybase Inc

Inventors

• Mittal Kaushal
• Chavan Mahendra

Classifications

• G06F17/30463

  Physics · mapped topic

• G06F17/30324

  Physics · mapped topic

• G06F17/30483

  Physics · mapped topic

• G06F17/30469 Primary

  Physics · mapped topic

• G06F16/24545 Primary

  Selectivity estimation or determination · CPC title