Granted Patent B2

US 12,259,878 · App. 17/448,242 · Granted Mar 25, 2025

Inventor: Jason Arnold (Chicago, IL)

G06F16/2425G06F16/2272

Abstract

Claims (66)

1. A method comprising:

determining a query expression indicating a query for execution against a plurality of rows;

generating a superset-guaranteeing expression in conjunctive normal form (CNF) based on the query expression, wherein the superset-guaranteeing expression is not logically equivalent to the query expression;

generating a query operator execution flow for the query by selecting an ordered arrangement of a plurality of operators for execution to include:

a plurality of index-based IO operators operable to implement the superset-guaranteeing expression; and

at least one additional operator serially after the plurality of index-based IO operators in the ordered arrangement of the plurality of operators; and

facilitating execution of the query via execution of the query operator execution flow by:

applying the plurality of index-based IO operators to identify a first subset of rows as a proper subset of the plurality of rows based on index data stored for the plurality of rows, wherein the first subset of rows corresponds to a true resultant of the superset-guaranteeing expression, and wherein the first subset of rows corresponds to a proper superset of a true resultant of the query expression; and

applying the at least one additional operator to the first subset of rows to identify a second subset of rows as a proper subset of the first subset of rows, wherein the second subset of rows corresponds to the true resultant of the query expression.

2. The method of claim 1 , wherein the query operator execution flow is in accordance with a non-normalized form that is neither CNF nor disjunctive normal form (DNF) based on the query expression being in neither CNF nor DNF.

3. The method of claim 1 , wherein generating the superset-guaranteeing expression includes generating a plurality of superset-guaranteeing sub-expressions based on the query expression, wherein each of the plurality of superset-guaranteeing sub-expressions is non-equivalent with all other ones of the plurality of superset-guaranteeing sub-expressions, and wherein each of the plurality of superset-guaranteeing sub-expressions has a corresponding true resultant that is a proper superset of the of the true resultant of the superset-guaranteeing expression.

4. The method of claim 3 , wherein each of the plurality of superset-guaranteeing sub-expressions are generated in CNF, and wherein generating the superset-guaranteeing expression further includes conjunctively combining the plurality of superset-guaranteeing sub-expressions.

5. The method of claim 3 , wherein generating each of the plurality of superset-guaranteeing sub-expressions includes:

identifying a nested AND expression within an operand of an OR expression of the query expression;

selecting one of a plurality of operands of the nested AND expression for inclusion in the each of the plurality of superset-guaranteeing sub-expressions; and

removing all other ones of the plurality of operands of the nested AND expression from the query expression to generate the each of the plurality of superset-guaranteeing sub-expressions.

6. The method of claim 5 , wherein generating a first one of the plurality of superset-guaranteeing sub-expressions includes selecting a first operand of the nested AND expression for inclusion in the first one of the plurality of superset-guaranteeing sub-expressions, and wherein generating a second one of the plurality of superset-guaranteeing sub-expressions includes selecting a second operand of the nested AND expression for inclusion in the second one of the plurality of superset-guaranteeing sub-expressions.

7. The method of claim 3 , wherein generating the plurality of superset-guaranteeing sub-expressions includes performing a recursive function upon an operator tree generated from the query expression.

8. The method of claim 1 , wherein generating the superset-guaranteeing expression in CNF includes removing at least one nested AND expression within at least one operand of at least one OR expression of the query expression from the query expression, wherein the superset-guaranteeing expression includes no nested AND expressions within any operands of any OR expression.

9. The method of claim 1 , further comprising:

storing the plurality of rows, wherein the plurality of rows correspond to relational database rows of a relational database, wherein each of the plurality of rows includes a set of column values for a set of columns of the relational database; and

further storing the index data indexing the plurality of rows based on column values of at least one column of the set of columns, wherein the index data is stored via at least one structure distinct from the plurality of rows;

wherein applying the plurality of index-based IO operators to identify the first subset of rows as the proper subset of the plurality of rows includes accessing the index data stored for the plurality of rows.

10. The method of claim 1 , wherein the at least one additional operator includes:

a plurality of parallel sub-flows of the query operator execution flow; and

at least one serialized set of multiple operators within at least one of the plurality of parallel sub-flows.

11. The method of claim 1 , wherein applying the at least one additional operator to the first subset of rows to identify a second subset of rows as a proper subset of the first subset of rows includes:

assigning each of the first subset of rows an appended identifier by applying an identifier appending operator;

generating a plurality of duplicates of the first subset of rows by applying a tee operator;

processing each of the plurality of duplicates of the first subset of rows applying each of a plurality of parallel sub-flows; and

applying a union distinct operator to remove all remaining duplicated ones the plurality of rows outputted by the plurality of parallel sub-flows based on the appended identifiers.

12. The method of claim 1 , wherein generating the query operator execution flow to include a plurality of index-based IO operators is further based on utilizing a plurality of operands of an AND operator being implemented as a root operator of an operator tree generated for the query expression.

13. A query processing system comprising:

at least one processor; and

memory that stores executable instructions that, when executed by the at least one processor, cause the query processing system to:

determine a query expression indicating a query for execution against a plurality of rows;

generate a superset-guaranteeing expression in a conjunctive normal form (CNF) based on the query expression, wherein the superset-guaranteeing expression is not logically equivalent to the query expression;

generate a query operator execution flow for the query by selecting an ordered arrangement of a plurality of operators for execution to include:

a plurality of index-based IO operators operable to implement the superset-guaranteeing expression; and

at least one additional operator serially after the plurality of index-based IO operators in the ordered arrangement of the plurality of operators; and

facilitate execution of the query via execution of the query operator execution flow by:

applying the plurality of index-based IO operators to identify a first subset of rows as a proper subset of the plurality of rows based on index data stored for the plurality of rows, wherein the first subset of rows corresponds to a true resultant of the superset-guaranteeing expression, and wherein the first subset of rows corresponds to a proper superset of a true resultant of the query expression; and

applying the at least one additional operator to the first subset of rows to identify a second subset of rows as a proper subset of the first subset of rows,

wherein the second subset of rows corresponds to the true resultant of the query expression.

14. The query processing system of claim 13 , wherein the query operator execution flow is in accordance with a non-normalized form that is neither CNF nor disjunctive normal form (DNF) based on the query expression being in neither CNF nor DNF.

15. The query processing system of claim 13 , wherein generating the superset-guaranteeing expression includes generating a plurality of superset-guaranteeing sub-expressions based on the query expression, wherein each of the plurality of superset-guaranteeing sub-expressions is non-equivalent with all other ones of the plurality of superset-guaranteeing sub-expressions, and wherein each of the plurality of superset-guaranteeing sub-expressions has a corresponding true resultant that is a proper superset of the of the true resultant of the superset-guaranteeing expression.

16. The query processing system of claim 13 , wherein generating the superset-guaranteeing expression in CNF includes removing at least one nested AND expression within at least one operand of at least one OR expression of the query expression from the query expression, wherein the superset-guaranteeing expression includes no nested AND expressions within any operands of any OR expression.

17. The query processing system of claim 13 , wherein the superset-guaranteeing expression is not logically equivalent to the query expression, and wherein the second subset of rows is a proper subset of the first subset of rows.

18. The query processing system of claim 13 , wherein the at least one additional operator includes:

a plurality of parallel sub-flows of the query operator execution flow; and

at least one serialized set of multiple operators within at least one of the plurality of parallel sub-flows.

19. The query processing system of claim 13 , wherein applying the at least one additional operator to the first subset of rows to identify a second subset of rows as a proper subset of the first subset of rows includes:

assigning each of the first subset of rows an appended identifier by applying an identifier appending operator;

generating a plurality of duplicates of the first subset of rows by applying a tee operator;

processing each of the plurality of duplicates of the first subset of rows applying each of a plurality of parallel sub-flows; and

applying a union distinct operator to remove all remaining duplicated ones the plurality of rows outputted by the plurality of parallel sub-flows based on the appended identifiers.

20. A non-transitory computer readable storage medium comprises:

at least one memory section that stores operational instructions that, when executed by a processing module that includes a processor and a memory, causes the processing module to:

determine a query expression indicating a query for execution against a plurality of rows;

generate a superset-guaranteeing expression in a conjunctive normal form (CNF) based on the query expression, wherein the superset-guaranteeing expression is not logically equivalent to the query expression;

generate a query operator execution flow for the query by selecting an ordered arrangement of a plurality of operators for execution to include:

a plurality of index-based IO operators operable to implement the superset-guaranteeing expression; and

at least one additional operator serially after the plurality of index-based IO operators in the ordered arrangement of the plurality of operators; and

facilitate execution of the query via execution of the query operator execution flow by:

applying the plurality of index-based IO operators to identify a first subset of rows as a proper subset of the plurality of rows based on index data stored for the plurality of rows, wherein the first subset of rows corresponds to a true resultant of the superset-guaranteeing expression, and wherein the first subset of rows corresponds to a proper superset of a true resultant of the query expression; and

applying the at least one additional operator to the first subset of rows to identify a second subset of rows as a proper subset of the first subset of rows, wherein the second subset of rows corresponds to the true resultant of the query expression.

Assignments (1)

Continuity (1)

References Cited (54)