Query language distribution heuristics

• US 10,691,681 B2
• Filed: 09/21/2017
• Issued: 06/23/2020
• Est. Priority Date: 09/21/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Sharad, Aditya, Eyers-Taylor, Alexander, Peyton Jones, Michael
• Primary Examiner(s): Morrison, Jay A
• Assistant Examiner(s): Hu, Xiaoqin
• Application Number:
  US15/711,378
• Publication Number:
  US 20190087456A1
• Time in Patent Office: 1,006 Days
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/2433 Query languages
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/2454 Optimisation of common expressions

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for performing local distribution heuristics. One of the methods includes receiving an original expression having a conjunction comprising a context term and a disjunction of a plurality of other terms. The context term and the disjunction are evaluated according to one or more local distribution heuristics to determine that the context term is a candidate for distribution across the disjunction of the plurality of other terms. In response, a transformed expression is generated in which the candidate context term is distributed across the disjunction of the plurality of other terms.

Claims

1. A system comprising:

one or more processors and one or more storage devices storing computer-executable instructions, when executed by the one or more processors, the computer-executable instructions cause the one or more processors to perform operations comprising;

receiving an original expression for a data processing query, the original expression having a conjunction joining a plurality of terms, wherein the plurality of terms comprises a context term as one term and a disjunction of a plurality of other terms as another term;

evaluating the context term and the disjunction according to one or more local distribution heuristics to determine that the context term is a candidate for distribution across the plurality of other terms of the disjunction, the evaluating the context term and the disjunction comprising;

determining whether the context term includes a single free variable, a free variable being a variable that does not relate to other variables in the context term;

in response to a determination that the context term includes a single free variable, determining whether each of the plurality of other terms of the disjunction also includes the single free variable; and

in response to a determination that each of the plurality of other terms of the disjunction also includes the single free variable, determining that the context term is a candidate for distribution across the plurality of other terms of the disjunction;

in response, generating a first transformed expression in which the candidate context term is distributed across the plurality of other terms of the disjunction;

determining, based on one or more deletion heuristics, whether the distributed candidate context term can be safely deleted from context outside of the disjunction of the first transformed expression;

in response to a determination that the distributed candidate context term can be safely deleted from context outside of the disjunction of the first transformed expression, determining that the distributed candidate context term is a deletion candidate;

generating a second transformed expression by deleting the deletion candidate from the context outside of the disjunction of the first transformed expression; and

executing the second transformed expression to generate a data processing query result for the original expression, wherein the second transformed expression reduces repetition of terms that are to be evaluated individually in the original expression.

2. The system of claim 1, wherein:

the original expression comprises a plurality of context terms, each of which being a term in a conjunction along with a disjunction of a plurality of other terms, and

generating the first transformed expression comprises distributing fewer than all of the plurality of context terms in the original expression.

3. The system of claim 1, wherein the conjunction further comprises a second disjunction, and wherein the operations further comprise:

separately evaluating the context term and the second disjunction according to the one or more local distribution heuristics to determine that the context term is not a candidate for distribution across the second disjunction,

wherein generating the first transformed expression comprises generating an expression in which the candidate context term is distributed across the disjunction of the plurality of other terms and is not distributed across the second disjunction.

4. The system of claim 1, wherein evaluating the context term according to one or more local distribution heuristics comprises determining that the context term uses exactly one free variable and determining that the free variable is used by every term of the disjunction.

5. The system of claim 4, wherein determining that the context term uses exactly one free variable comprises determining that a result of the context term is a one-attribute relation.

6. The system of claim 1, wherein evaluating the context term according to one or more local distribution heuristics comprises determining that the context term resolves a Cartesian product in one or more terms of the disjunction.

7. The system of claim 1, wherein evaluating the context term according to one or more local distribution heuristics comprises:

computing a first set of equivalence classes for variables in the disjunction only using one or more relatedness criteria;

computing a second set of equivalence classes for variables in the disjunction after distributing the context term using the one or more relatedness criteria; and

determining that the second set of equivalence classes is smaller than the first set of equivalence classes.

8. The system of claim 7, wherein the one or more relatedness criteria comprise:

determining whether the original expression includes a term that explicitly relates two variables, or

determining whether two variables are related by at least one term in every disjunctive term.

9. The system of claim 8, wherein determining whether the original expression includes a term that explicitly relates two variables comprises ignoring negated terms and calls that do not bind their variables.

10. The system of claim 1, wherein the operations further comprise:

evaluating the context term according to a shared variables deletion heuristic to determine that the context term can be deleted from the context of the first transformed expression; and

in response, deleting the context term from the context of the first transformed expression to generate the second transformed expression.

11. The system of claim 10, wherein the operations further comprise:

determining that a second candidate context term is recursive and that the second candidate context term is not a candidate for deletion from the context; and

in response, undesignating the second candidate context term as a candidate for distribution.

12. The system of claim 10, wherein the operations further comprise:

determining that a second candidate context term is recursive and that the second candidate context term is a candidate for distribution into multiple disjunctions; and

in response, undesignating the second candidate context term as a candidate for distribution.

13. The system of claim 1, wherein the operations further comprise:

until a fixed point is reached in which a first set of pairs of candidate context terms and corresponding disjunctions and a second set of deletion candidates do not change, performing operations comprising;

evaluating one or more candidate context terms according to a shared variables deletion heuristic to designate some of the one or more candidate context terms as deletion candidates, and

undesignating any recursive candidate context terms that are not deletion candidates.

14. The system of claim 13, wherein the operations further comprise undesignating any recursive candidate context terms that are candidate context terms for multiple disjunctions.

15. A computer-implemented method comprising:

receiving an original expression for a data processing query, the original expression having a conjunction joining a plurality of terms, wherein the plurality of terms comprises a context term as one term and a disjunction of a plurality of other terms as another term;

evaluating the context term and the disjunction according to one or more local distribution heuristics to determine that the context term is a candidate for distribution across the plurality of other terms of the disjunction, the evaluating the context term and the disjunction comprising;

determining whether the context term includes a single free variable, a free variable being a variable that does not relate to other variables in the context term;

in response to a determination that the context term includes a single free variable, determining whether each of the plurality of other terms of the disjunction also includes the single free variable; and

in response to a determination that each of the plurality of other terms of the disjunction also includes the single free variable, determining that the context term is a candidate for distribution across the plurality of other terms of the disjunction;

in response, generating a first transformed expression in which the candidate context term is distributed across the plurality of other terms of the disjunction;

determining, based on one or more deletion heuristics, whether the distributed candidate context term can be safely deleted from context outside of the disjunction of the first transformed expression;

in response to a determination that the distributed candidate context term can be safely deleted from context outside of the disjunction of the first transformed expression, determining that the distributed candidate context term is a deletion candidate;

generating a second transformed expression by deleting the deletion candidate from the context outside of the disjunction of the first transformed expression; and

executing the second transformed expression to generate a data processing query result for the original expression, wherein the second transformed expression reduces repetition of terms that are to be evaluated individually in the original expression.

16. The method of claim 15, wherein:

the original expression comprises a plurality of context terms, each of which being a term in a conjunction along with a disjunction of a plurality of other terms, and

generating the first transformed expression comprises distributing fewer than all of the plurality of context terms in the original expression.

17. The method of claim 15, wherein the conjunction further comprises a second disjunction, and further comprising:

separately evaluating the context term and the second disjunction according to the one or more local distribution heuristics to determine that the context term is not a candidate for distribution across the second disjunction,

wherein generating the first transformed expression comprises generating an expression in which the candidate context term is distributed across the disjunction of the plurality of other terms and is not distributed across the second disjunction.

18. A computer program product comprising one or more hardware storage devices having stored thereon computer-executable instructions that are structured such that, when executed by one or more processors of a computing system cause the one or more processors to perform operations comprising:

receiving an original expression for a data processing query, the original expression having a conjunction of a plurality of terms, wherein the plurality of terms comprises a context term as one term and a disjunction of a plurality of other terms as another term;

evaluating the context term and the disjunction according to one or more local distribution heuristics to determine that the context term is a candidate for distribution across the plurality of other terms of the disjunction, the evaluating the context term and the disjunction comprising;

determining whether the context term includes a single free variable, a free variable being a variable that does not relate to other variables in the context term;

in response to a determination that the context term includes a single free variable, determining whether each of the plurality of other terms of the disjunction also includes the single free variable; and

in response to a determination that each of the plurality of other terms of the disjunction also includes the single free variable, determining that the context term is a candidate for distribution across the plurality of other terms of the disjunction;

in response, generating a first transformed expression in which the candidate context term is distributed across the plurality of other terms of the disjunction;

determining, based on one or more deletion heuristics, whether the distributed candidate context term can be safely deleted from context outside of the disjunction of the first transformed expression;

in response to a determination that the distributed candidate context term can be safely deleted from context outside of the disjunction of the first transformed expression, determining that the distributed candidate context term is a deletion candidate;

generating a second transformed expression by deleting the deletion candidate from the context outside of the disjunction of the first transformed expression; and

executing the second transformed expression to generate a data processing query result for the original expression, wherein the second transformed expression reduces repetition of terms that are to be evaluated individually in the original expression.

19. The computer program product of claim 18, wherein:

the original expression comprises a plurality of context terms, each of which being a term in a conjunction along with a disjunction of a plurality of other terms,

generating the first transformed expression comprises distributing fewer than all of the plurality of context terms in the original expression.

20. The computer program product of claim 18, wherein the conjunction further comprises a second disjunction, and wherein the operations further comprise:

separately evaluating the context term and the second disjunction according to the one or more local distribution heuristics to determine that the context term is not a candidate for distribution across the second disjunction,

wherein generating the first transformed expression comprises generating an expression in which the candidate context term is distributed across the disjunction of the plurality of other terms and is not distributed across the second disjunction.