Two-valued logic primitives for SQL query processing

Patent metadata

Field	Value
Publication number	US-11269874-B2
Application number	US-202016823632-A
Country	US
Kind code	B2
Filing date	Mar 19, 2020
Priority date	Mar 19, 2020
Publication date	Mar 8, 2022
Grant date	Mar 8, 2022

Abstract

The present invention relates to data manipulation language (DML) acceleration. Herein are database techniques to use value range analysis and range-limited execution operators when a value is excluded. In an embodiment, a computer receives a data access request that specifies an expression that includes operator(s), including a particular operator that has argument(s) that has only three possible values. Before detecting the actual value of a particular argument, the computer detects that a particular value of the three possible values is excluded for the particular argument. Responsively, an implementation of the particular operator that never accepts the particular value for the particular argument is selected. Applying the expression to fulfil the data access request entails invoking the selected implementation of the particular operator.

First claim

What is claimed is:

1. A method comprising:
receiving a data access request that specifies an expression that includes one or more operators that include a particular operator that has a plurality of arguments, wherein each argument of the plurality of arguments has only three possible values;
detecting, before detecting actual values of the plurality of arguments, that a particular value of the three possible values is excluded for the plurality of arguments;
selecting, based on said detecting that the particular value is excluded, an implementation of the particular operator that never accepts the particular value for the plurality of arguments;
fulfilling, by a database management system (DBMS), the data access request, including applying the expression and invoking said implementation of the particular operator.

2. The method of claim 1 wherein said detecting that the particular value is excluded comprises at least one selected from the group consisting of:
detecting, before invoking a second operator of the one or more operators, that the second operator will not produce the particular value, and
traversing the one or more operators as a tree that does not contain the particular operator as a leaf.

3. The method of claim 1 wherein:
said detecting that the particular value is excluded comprises traversing the one or more operators as a tree;
said traversing the the one or more operators as the tree comprises at least one selected from the group consisting of: a post order traversal and a depth first traversal.

4. The method of claim 1 wherein said detecting that the particular value is excluded comprises:
associating a respective set of projected fields with each operator of the one or more operators;
detecting that at least one projected field of the set of projected fields of at least one operator of the one or more operators excludes the particular value.

5. The method of claim 1 wherein at least one selected from the group consisting of:
the particular value is null, and
the particular operator produces a Boolean.

6. The method of claim 1 wherein:
each record of a plurality of records has a same field;
said detecting that the particular value is excluded comprises detecting at least one selected from the group consisting of:
said field is a candidate key or a sequence, and
a data schema indicates that said field excludes duplicate values.

7. The method of claim 6 wherein said detecting that the field excludes the particular value comprises:
setting, before said receiving the data access request, a flag to indicate that a particular scan does not find the particular value, wherein said particular scan is one selected from the group consisting of:
a scan of the plurality of records, and
a scan by a single instruction multiple data (SIMD);

detecting that the flag indicates that the particular scan does not find the particular value.

8. The method of claim 7 further comprising toggling said flag that indicates that the particular scan does not find the particular value when one selected from the group consisting of:
said field of a record of the plurality of records is reassigned to the particular value, and
said field of a new record that is added to the plurality of records has the particular value.

9. The method of claim 1 wherein separate network elements or separate computers respectively perform:
in said DBMS, said detecting that the particular value is excluded, and
not in the DBMS, said invoking said implementation of the particular operator.

10. The method of claim 1 wherein said invoking said implementation of the particular operator comprises executing at most one branch instruction of an instruction set architecture (ISA).

11. A method comprising:
receiving a data access request that specifies an expression that includes one or more operators that include a particular operator that has at least one argument that has only three possible values;
detecting, before detecting an actual value of a particular argument of the at least one argument, that a particular value of the three possible values is excluded for the particular argument, wherein said detecting that the particular value is excluded comprises detecting one selected from the group consisting of:
the particular value is not contained in an encoding dictionary or an index,
the particular value is not found by a scan of a plurality of records or by a single instruction multiple data (SIMD), and
no bits of a bit string have a particular bit value

selecting, based on said detecting that the particular value is excluded, an implementation of the particular operator that never accepts the particular value for the particular argument;
applying the expression, including invoking said implementation of the particular operator, to fulfil the data access request.

12. One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:
receiving a data access request that specifies an expression that includes one or more operators that include a particular operator that has a plurality of arguments, wherein each argument of the plurality of arguments has only three possible values;
detecting, before detecting actual values of the plurality of arguments, that a particular value of the three possible values is excluded for the plurality of arguments;
selecting, based on said detecting that the particular value is excluded, an implementation of the particular operator that never accepts the particular value for the plurality of arguments;
applying the expression, including invoking said implementation of the particular operator, to fulfil the data access request.

13. The one or more non-transitory computer-readable media of claim 12 said detecting that the particular value is excluded comprises at least one selected from the group consisting of:
detecting, before invoking a second operator of the one or more operators, that the second operator will not produce the particular value, and

traversing the one or more operators as a tree that does not contain the particular operator as a leaf.

14. The one or more non-transitory computer-readable media of claim 12 wherein said detecting that the particular value is excluded comprises:
associating a respective set of projected fields with each operator of the one or more operators;
detecting that at least one projected field of the set of projected fields of at least one operator of the one or more operators excludes the particular value.

15. The one or more non-transitory computer-readable media of claim 12 wherein at least one selected from the group consisting of:
the particular value is null, and
the particular operator produces a Boolean.

16. The one or more non-transitory computer-readable media of claim 12 wherein:
each record of a plurality of records has a same field;
said detecting that the particular value is excluded comprises detecting at least one selected from the group consisting of:
said field is a candidate key or a sequence, and
a data schema indicates that said field excludes duplicate values.

17. The one or more non-transitory computer-readable media of claim 16 wherein said detecting that the field excludes the particular value comprises:
setting, before said receiving the data access request, a flag to indicate that a particular scan does not find the particular value, wherein said particular scan is one selected from the group consisting of:
a scan of the plurality of records, and
a scan by a sin

Assignees

• Oracle Int Corp

Inventors

• Fender Pit
• Schlegel Benjamin
• Ulrich Alexander

Classifications

• G06F16/24542 Primary

  Plan optimisation · CPC title

• G06F16/245 Primary

  Query processing · CPC title