STATIC QUERY OPTIMIZATION FOR LINQ

• US 20090144229A1
• Filed: 11/30/2007
• Published: 06/04/2009
• Est. Priority Date: 11/30/2007
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Vick, Paul A., Meijer, Henricus Johannes Maria, Silver, Amanda K., Tsingauz, Aleksey V.
• Application Number:
  US11/948,078
• Publication Number:
  US 20090144229A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

Systems and methods that optimize query translations at compile time in LINQ languages. An optimization component optimizes algebraic trees and rewrites an expression composed from sequence operators into a more efficient expression(s). A compiler associated with the optimization component can receive syntax (e.g., query comprehensions, query expressions) to turn into standard sequence operators that can operate on arbitrary collections. The compiler can then perform transformations on the algebraic trees, such as push filter conditions upwards or downwards and/or to combine filter conditions.

Claims

1. A computer implemented system comprising:

a plurality of expression trees that represent syntax associated with a Language-Integrated Query (LINQ); and

an optimization component that optimizes query translations based on the expression trees during compile time.

2. The computer implemented system of claim 1 further comprising a compiler that receives the expression trees.

3. The computer implemented system of claim 2, the compiler with filter conditions to mitigate projections and perform nesting operations.

4. The computer implemented system of claim 3, an operation of the compiler further customizable based on defined collections for data.

5. The computer implemented system of claim 4 further comprising generic compilation or optimization rules that are valid for all sequence operators.

6. The computer implemented system of claim 4 further comprising specific optimization rules that are valid based on domains.

7. The computer implemented system of claim 4 further comprising a feedback from instrumented runs of a program based on the LINQ.

8. The computer implemented system of claim 4 further comprising run time optimization passes performable on the query translation.

9. The computer implemented system of claim 4 further comprising an artificial intelligence or machine learning component that facilitates the optimizations.

10. A computer implemented method comprising:

receiving an algebraic tree or syntax associated with a LINQ via a compiler; and

optimizing the algebraic tree or syntax during compile time.

11. The computer implemented method of claim 10 further comprising performing a semantic analysis and transformations on the algebraic tree.

12. The computer implemented method of claim 11 further comprising changing iterations over collections or pushing filter operations upfront, or combination thereof.

13. The computer implemented method of claim 10 further comprising performing a run-time optimization of in memory queries.

14. The computer implemented method of claim 10 further comprising transforming syntax into sequence operators.

15. The computer implemented method of claim 10 further comprising supplying feedback from instrumented runs of the program.

16. The computer implemented method of claim 10 further comprising customizing rules based on domains.

17. The computer implemented method of claim 16 further comprising parameterizing algebraic rules based on external rules or hints.

18. The computer implemented method of claim 16 further comprising pushing filter operations upfront.

19. The computer implemented method of claim 16 further comprising inferring optimizations based on general rules or customized rules.

20. A computer implemented system comprising:

means for representing syntax as an expression tree associated with a Language-Integrated Query (LINQ); and

means for optimizing query translations based on means for representing syntax.