Query optimizer for CPU utilization and code refactoring

Methods, systems, apparatuses, and computer program products are provided for increasing an efficiency of queries in program code. A plurality of queries is detected in program code. A laziness is extended by which the queries are evaluated in the program code. The queries are decomposed into a plurality of query components. A ruleset that includes a plurality of rules is applied to the query components to generate a functionally equivalent query set to the plurality of queries that evaluates more efficiently relative to the plurality of queries.

BACKGROUND

Various types of software development applications exist that software developers may use to develop software. An integrated development environment (IDE) is a type of software development application that contains several development tools in one package. An IDE may include tools such as a source code editor (“code editor”), a build automation tool, and a debugger. Examples of IDEs include Eclipse™ developed by Eclipse Foundation of Ottawa, Canada, ActiveState Komodo™ developed by ActiveState of Vancouver, Canada, IntelliJ IDEA developed by JetBrains of the Czech Republic, Oracle JDeveloper™ developed by Oracle Corporation of Redwood City, Calif., NetBeans developed by Oracle Corporation, Codenvy™ developed by Codenvy of San Francisco, Calif., Xcode® developed by Apple Corporation of Cupertino, Calif., and Microsoft® Visual Studio®, developed by Microsoft Corporation of Redmond, Wash.

Many modern programming languages natively support queries for data. For example, the Microsoft .NET Framework, developed by Microsoft Corporation, supports queries in the form of LINQ (Language Integrated Query), while Java®, developed by Oracle Corporation or Redwood City, Calif., supports queries in the form of Streams. Native support of queries in a programming language enables developers to concentrate on the logic part of their program code, because the integrated query functionality takes care of the actual implementation of the queries for them. This can allow a developer to speed up their coding.

However, not knowing or having a poor understanding of the consequences of inefficient queries can lead to inefficient program code being developed. Furthermore, due to today's best practices for developing software, developers tend to split larger methods/procedures into smaller methods/procedures in their code for greater readability, which can also lead to inefficiencies in queries in program code.

SUMMARY

Methods, systems, apparatuses, and computer program products are provided for increasing an efficiency of queries in program code. A plurality of queries is detected in program code, such as when the program code is entered in a code editor or during compile time. A laziness is extended by which the queries are evaluated in the program code. Furthermore, a ruleset that includes a plurality of rules is applied to the detected queries to generate a functionally equivalent query set that evaluates more efficiently relative to the detected queries.

The rules included in the ruleset can be generated in any manner, including being generated manually by a user or automatically-generated by an algorithm, such as machine learning, big data analysis of code examples, etc. A set of such rules can significantly improve most common errors that occur in developers daily work.

Either a single functionally equivalent query set may be generated and input into the program code in place of one or more of the existing queries, or multiple candidate functionally equivalent query sets can be generated, from which one query set is selected to be input into the program code. A user may select the candidate functionally equivalent query set to be input into the program code, or the candidate functionally equivalent query set may be selected automatically. The selection of the candidate functionally equivalent query set may be influenced by whether the selection is made during development (e.g., during code entry or at compilation time), or is made during runtime. During runtime, a candidate functionally equivalent query set may be selected from the multiple candidates for input into the program code based (at least in part) on runtime factors (e.g., execution conditions such as network availability, processing power available, etc.).

DETAILED DESCRIPTION

The present specification and accompanying drawings disclose one or more embodiments that incorporate the features of the present invention. The scope of the present invention is not limited to the disclosed embodiments. The disclosed embodiments merely exemplify the present invention, and modified versions of the disclosed embodiments are also encompassed by the present invention. Embodiments of the present invention are defined by the claims appended hereto.

II. Example Embodiments for Optimizing Queries in Program Code

Many modern programming languages natively support queries. For example, the Microsoft .NET Framework, developed by Microsoft Corporation, supports queries in the form of LINQ (Language Integrated Query), while Java®, developed by Oracle Corporation or Redwood City, Calif., supports queries in the form of Streams. Native support of queries in a programming language enables developers to concentrate on the logic part of their program code by taking care of the actual implementation of the queries for them. This can allow a developer to speed up their coding. However, not knowing or having a poor understanding of the consequences of inefficient queries can lead to poorly functioning program code being developed. For example, such program code may include queries that retrieve data that ends up being unused, that retrieves redundant quantities of data, and/or that retrieves data more often or earlier than necessary. Queries can be written in many different ways that yield the same logical results, but have very different impact on performance.

Furthermore, due to today's best practices for developing software, developers tend to split larger methods/procedures into smaller methods/procedures in their code for greater readability. Currently available code optimizers can have difficulty in optimizing code that has been developed this way.

According to embodiments, program code is automatically analyzed for queries that are inefficiently implemented, and the queries are replaced with a set of more efficient but logically equivalent queries. Such embodiments may be implemented to take affect during compilation time (e.g., for CPU optimization) and/or to be implemented as refactoring suggestions in IDE tools and/or IDE add-ins. For example, in an embodiment, a code editor is configured to determine a more efficient query set and to suggest the more efficient query set to a developer to be implemented in the developer's code. Embodiments enable readable code to be developed by developers, then transform the code into more efficient code automatically.

In an embodiment, a query optimizer may be configured to: (a) identify queries (e.g., LINQ, Streams, etc.) in program code, (b) inspect the queries' results to determine their usage/context, (c) decompose the queries into atomic units, (d), aggregate (a), (b), and (c) to determine where query optimizations can be implemented. For example, pattern matching may be performed against a set of rules, which can be either explicitly defined rules and/or automatically-generated rules. For example, rules can be automatically-generated by an algorithm, such as machine learning, big data analysis of code examples, etc. A set of such rules can significantly improve most common errors that occur in developers daily work.

Accordingly, embodiments provide one or more of: (1) a tool and process that analyze and recommend code changes that improve query performance, (2) a tool and process that automatically change queries into equivalent more optimized queries, (3) a pre-processing code analyzing tool and process for compilers for automatic performance improvements for queries, (4) an automatic tool and process that analyze and recommend code refactoring regarding queries for databases (like “entity framework” in .NET and equivalents in other languages), and a code optimization tool and process that implement machine learning, which samples equivalent queries during run time and automatically chooses and replaces the best query for the scenario.

As used herein, a query is a query (or request) for data, and may also be referred to as a data query. A query may be provided to any source of data, including a database, an application, an API (application programming interface), etc. A query to a database may be referred to as a “database query.”

Embodiments may be implemented in various ways. For instance,FIG. 1shows a block diagram of a computing device102that contains a query optimizer104configured to improve an efficiency of query execution in program code, according to an example embodiment. As shown inFIG. 1, query optimizer104receives program code106entered by a developer (a person who writes/inputs/modifies program code). Program code106includes a plurality of queries110. Queries110includes multiple queries, which may include one or more separate query operators and/or one or more query expressions (strings/series of query operators). Query optimizer104is configured to analyze and generate a replacement set of queries for queries110, thereby outputting refactored program code108that includes replacement queries112. Refactored program code108is program code that is logically equivalent (performs the same function(s)) as original program code106, but is rewritten with replacement queries112. Replacement queries112are configured to perform more efficiently than original queries110, such as by avoiding retrieving data not used by the program code, avoiding making redundant data retrieval requests, avoiding performing redundant operations, and/or retrieving data less frequently and/or later (increasing laziness).

Query optimizer104may be implemented independently or included in any system or tool that may be used by a developer to input or process program code, such as a code editor, a code compiler, a code debugger, etc. For instance,FIG. 2shows a block diagram of computing device102including a development application200that includes query optimizer104, according to an example embodiment. Development application200is an example of an integrated development environment (IDE). As shown inFIG. 2, computing device102including development application200, storage210, and a communication interface208. Storage210stores program code106and108and ruleset216. Development application200includes a source code editor202, a compiler204, and a debugger tool206. Source code editor202includes a user interface212. As indicated by dotted arrows, query optimizer104may be implemented in or called by any one or more of source code editor202, complier204, and/or debugger tool206. Note that development application200is shown for illustrative purposes, and as an example embodiment, and not all features of development application200need to be present in all embodiments. Furthermore, additional features not shown inFIG. 2may be present in some embodiments. The features of development application200shown inFIG. 2are described as follows.

As shown inFIG. 2, development application200may be implemented in one or more computing devices102. For instance, source code editor202, compiler204, and debugger tool206may be included in a same computing device, or one or more of source code editor202, compiler204, and debugger tool206may be implemented in one or more computing devices separate from those of others of source code editor202, compiler204, and debugger tool206.

Computing device102may be one or more of any type of stationary or mobile computing device(s), including a mobile computer or mobile computing device (e.g., a Microsoft® Surface® device, a personal digital assistant (PDA), a laptop computer, a notebook computer, a tablet computer such as an Apple iPad™, a netbook, etc.), a mobile phone, a wearable computing device, or other type of mobile device, or a stationary computing device such as a desktop computer or PC (personal computer).

Code editor202may be any proprietary or conventional code editor configured for editing of program code mentioned elsewhere herein or otherwise known (e.g., a code editor of Eclipse™, ActiveState Komodo™, IntelliJ IDEA, Oracle JDeveloper™ NetBeans, Codenvy™, Xcode®, Microsoft® Visual Studio®, etc.).

A developer may interact with source code editor202to enter and modify program code when generating source code for an application. For instance, the developer may interact with a user interface212of source code editor202to add, modify, or delete program code text such as by typing, by voice input, by selecting suggested code blocks, etc. Accordingly, user interface212may include one or more text entry boxes/windows (e.g., code editor window604ofFIG. 6), voice/speech recognition, one or more graphical user interface elements (e.g., buttons, check boxes, radio buttons, pull down menus, etc.), and/or other user interface elements that a developer may interact with. When complete, or at other intervals, the user may be enabled to save the program code by interacting with a “save” button or other user interface element.

For instance, as shown inFIG. 2, a developer may interact with user interface212of source code editor202to generate program code106. Program code106is source code, which is a collection of computer instructions (possibly with comments) written using a human-readable computer programming language. Examples of suitable human-readable computer programming languages include C#, C++, Java, etc. Program code106may be received in one or more files or other form. For instance, program code106may be received as one or more “.c” files (when the C programming language is used), as one or more “.cpp” files (when the C++ programming language is used), etc. When query optimizer104is used by source code editor202to refactor program code106, refactored program code108may be generated and saved by source code editor202. In embodiments, source code editor202may apply rules of ruleset216to query components (also referred to as “query operators”) of program code106to create a more efficient set of queries in refactored program code108.

As shown inFIG. 2, program code106and/or108may be stored in storage210. Storage210may include one or more of any type of physical storage hardware/circuitry to store data, including a magnetic disc (e.g., in a hard disk drive), an optical disc (e.g., in an optical disk drive), a magnetic tape (e.g., in a tape drive), a memory device such as a RAM device, a ROM device, etc., and/or any other suitable type of physical storage hardware/circuitry.

Compiler204may be invoked in any manner, such as by a command line, a graphical user interface, etc. A “-full” switch, or other switch, may be used when compiler204is invoked to perform a full compile. Compiler204is configured to receive and compile program code106(or program code108) to generate machine code222. In particular, compiler204is configured to transform program code106and/or108into machine code222in the form of another computer language, typically having a binary form, referred to as machine code or object code. In some cases, compiler204may include multiple stages, and may first convert program code106into an intermediate form (e.g., an intermediate language), which is subsequently converted into machine code222.

Compiler204may be configured to perform one or more types of optimizations on program code106and/or108when generating machine code222. An optimized build results in machine code that is semantically equivalent to machine code generated without optimizations, but is configured in a way that fewer resources are used during execution of the optimized machine code (e.g., less memory, fewer procedure calls, etc.). Examples of optimizations that may be performed include loop optimizations, data-flow optimizations, SSA-based optimizations, code-generator optimizations, functional language optimizations, interprocedural optimizations, and/or further types of optimizations that would be known to persons skilled in the relevant art(s). Many specific types of optimizations exist. For example, “inlining” may be performed, where a callee function called by a caller function is copied into the body of the caller function. In another example of a specific optimization, “common subexpression elimination” may be performed, where a single instance of code is used for a quantity that is computed multiple times in source code. When query optimizer104is used by compiler204to refactor program code106, refactored program code108may be generated and used to generate machine code222by compiler204.

Machine code222may be included in a file (e.g., an object or “.obj” file), or may be created/stored in another form, to form an executable program or application. Machine code222may optionally be stored in storage210.

When program code106and/or108is compiled by compiler204for the debug stage of development, debugger tool206may receive machine code222. Debugger tool206is configured to run a debugger (or “debug”, “debugging”) session on the application represented by machine code222. In a debugger session, a developer may be enabled to step through the execution of code of machine code222, while viewing the values of variables, arrays, attributes, and/or outputs (e.g., contents of registers, a GUI, etc.) generated by the execution of machine code222, including having access to the effects of any debug code/statements entered into program code106and/or108(and passed to machine code222by compiler204for purposes of debug). In this manner, a developer may be able to test or troubleshoot (“debug”) program code106and/or108, making edits to program code106and/or108using source code editor202based on the results of the debugger session. The modified version of program code106and/or108may be compiled by compiler204and received by debugger tool206for further debugging. During debug, debugger tool206may suggest and/or rewrite queries in program code106to generate program code108. Debugger tool206may include one or more processors (e.g., a central processing unit (CPU)), physical and/or virtual, that execute(s) machine code222.

When debugging by debugger tool206is complete, and program code106and/or108is in its final version, compiler204may compile program code106and/or108to generate machine code222for the release stage of development. The release version of machine code222may be released to be used by users.

Communication interface208is configured to transmit program code106and/or108to remote entities, to receive rules for improving program code in accordance with embodiments, and/or to communicate other data according to any suitable communication protocol, proprietary or conventional. Further examples of communication interfaces and communication protocols are described in the next section.

Query optimizer104may be configured in various ways to perform its functions. For instance,FIG. 3shows a flowchart300providing a process for improving an efficiency of query execution in program code, according to an example embodiment. Query optimizer104may operate according to flowchart300in an embodiment. Flowchart300is described as follows with reference toFIG. 1andFIG. 4.FIG. 4shows a block diagram of query optimizer104, according to an example embodiment. As shown inFIG. 4, query optimizer104includes a query detector402, a laziness extender404, and an equivalent query set generator406, which are described as follows with reference to flowchart300.

Flowchart300begins with step302. In step302, a plurality of queries is detected in program code. As shown inFIG. 1, query optimizer104receives program code106, which includes queries110. Query detector402ofFIG. 4is configured to parse through program code106to detect queries. Query detector402may detect queries in any manner, such as by comparing code terms in program code106to a predetermined list of known query operators/components, etc. For instance, when searching for LINQ queries, query detector402may parse through program code106for known LINQ operators such as Select, Where, Sum, Min, Max, Average, Aggregate, Join, GroupJoin, OrderBy, GroupBy, Union, Contains, Count, ToList, ToDictionary, etc. Each found query operator (e.g., found by text matching) is indicated by query detector402as a query for program code106.

In one illustrative example, query detector402may parse the following program code for queries:

public void Main( )var 1stOfPrimes = ReturnListOfPrimes(1000);var 1stOrdered = 1stOfPrimes.OrderBy(x => x).ToList( );var 1stOrderedDesc = 1stOrdered.OrderByDescending(x => x).ToList( );Console.WriteLine(“Biggest prime in range is: {0}”,1stOrderedDesc.First( ));
In this example, query detector402may detect the LINQ queries of Orderby(x=>x) and ToList( ) in the third line of code, and the LINQ queries of OrderByDescending(x=>x) and ToList( ) in the fourth line of code.

Note that step302(and the rest of flowchart300) may be implemented by query optimizer104in any suitable code development tool or application. For example,FIG. 5shows a flowchart500providing a process for generating and presenting a suggested replacement query set in a code editor, according to an example embodiment. In an embodiment, flowchart300ofFIG. 3may implement flowchart500ofFIG. 5. For instance, step302of flowchart300may implement step502of flowchart500, and step504may be an additional step to flowchart300. Flowchart500is described as follows.

In step502, the queries are detected in the program code in a code editor. In an embodiment, query detector402may be configured to detect queries in program code106in a code editor, such as code editor202(FIG. 2), where a developer enters and edits program code. Query detector402may perform a query term search in program code106as the developer enters code, whenever the developer saves the code, in response to request by the developer (e.g., by clicking on a “query detect” button), on a periodic basis, and/or at any other desired time or basis.

For instance,FIG. 6shows a block diagram of computing device102including a code editor window604displaying program code106, according to an example embodiment. Display602may be any suitable type of display device or screen, including an LCD (liquid crystal display), a CRT (cathode ray tube) display, an LED (light emitting diode) display, a plasma display, etc. Code editor window604is a window (framed or frameless) displayed by code editor202in display602as a graphical user interface (GUI) for interaction with program code106displayed in code editor window604. Code lines606,608, and610are each one or more lines of code of any suitable programming language, as would be known to persons skilled in the relevant art(s). In an embodiment, query detector402parses program code106, including code lines606,608, and610, for queries according to step502.

In step504, an option is presented for the code editor to automatically refactor the program code to replace the plurality of queries with the functionally equivalent query set. In an embodiment, after query optimizer104detects queries and determines more efficient queries to replace the detected queries in program code106(as further described elsewhere herein), code editor202may present an option for the developer to accept or reject the determined more efficient queries. For instance, as shown inFIG. 6, a suggested replacement query set612may be displayed in code editor window604for acceptance or rejection by the developer. Suggested replacement query set612is a suggested set of queries determined by query optimizer104to be more efficient than the set of queries detected in program code106. If the developer accepts suggested replacement query set612(e.g., by clicking on a button), code editor202may replace the detected set of queries with suggested replacement query set612in program code106to generate and display refactored program code108in code editor window604. If the developer rejects suggested replacement query set612, no change is made to program code106, and the suggestion is no longer displayed. Note that in another embodiment, suggested replacement query set612may be automatically implemented in program code106(without requesting developer acceptance).

In another embodiment, as described above, query detector402may be configured to detect queries in program code106during compilation. For instance,FIG. 7shows a flowchart700providing a process for generating and implementing replacement query set at compile time, according to an example embodiment. In an embodiment, flowchart300ofFIG. 3may implement flowchart700ofFIG. 7. For instance, step302of flowchart300may implement step702of flowchart700, and step704may be an additional step to flowchart300. Flowchart700is described as follows.

In step702, the queries are detected in the program code during compilation. In an embodiment, query detector402may be configured to detect queries in program code106(e.g., by text matching, etc.) in a compiler, such as compiler204(FIG. 2), when program code106is compiled.

In step704, compiled code is generated in the compiler based on a version of the program code where the plurality of queries is replaced with the functionally equivalent query set. In an embodiment, as described in further detail below, query optimizer104is configured to generate a more efficient replacement query set for the queries detected in program code106by query detector402, to replace the detected queries with the replacement query set in a copy of program code106to generate refactored program code108, and to generate a compiled version of program code106by compiling refactored program code108. In this manner, compiled machine code is generated that includes the more efficiently operating query set without changing program code106, such that the developer does not see changed queries when subsequently editing program code106in code editor202. In another embodiment, however, the replacement query set may be automatically implemented in program code106at compile time (without requesting developer acceptance).

Referring back to flowchart300ofFIG. 3, in step304, laziness is extended by which the queries are evaluated in the program code. In an embodiment, laziness extender404is configured to analyze the queries detected in program code106by query detector402, and to extend a laziness of the evaluation of the queries (when the program code is executed). “Lazy evaluation” refers to an evaluation technique that delays the evaluation of an expression until its value is needed. Laziness extender404is configured to receive a query and postpone execution of as much of its operators as late as possible. Accordingly, laziness extender404analyzes program code106to determine queries that can have their evaluation delayed, and determines an equivalent one or more query statements that perform the queries in a delayed fashion.

For example,FIG. 8shows a flowchart800providing a process for extending the laziness of query execution in program code, according to an example embodiment. In an embodiment, laziness extender404operates according to flowchart800. Flowchart800is described as follows with respect toFIG. 9.FIG. 9shows a block diagram of laziness extender404, according to an example embodiment. As shown inFIG. 9, laziness extender404includes an extendable query detector902and a query expression assembler904.

Flowchart800begins with step802. In step802, one or more of the queries that are evaluation-extendable are detected. In an embodiment, extendable query detector902of laziness extender404analyzes program code106to determine queries that can have their evaluation delayed because their output values are not needed at their present location in program code106, but instead are used later. In such an embodiment, extendable query detector902is configured, for a particular query, to parse past the query in program code106to find a location (e.g., an expression, a code line, etc.) at or closer to where the value of the query is needed, such as where the value is directly output to a user or where an expression uses the value to generate an output to the user.

In an embodiment, extendable query detector902begins by building a data structure such as an Operation Tree for each query of detected queries906, which includes the queries detected by query detector402in the program code as well as non-query program code operations. Extendable query detector902lists multiple related queries together under the same Operation Tree. Such an Operation Tree may be represented as a graph, where each node represents a matching query operator of the query that does not fetch actual data from the data source (e.g., performs an operation on data), and each leaf of the Operation Tree represents a query operator of the query that fetches actual data from the data source. Extendable query detector902builds the Operation Tree by following each variable/query operator/method/code statement in the program code and recursively adding the data to the Operation Tree. Accordingly, extendable query detector902receives queries and transforms them to the relevant tree.

For instance, in one example, extendable query detector902may analyze the following program code to determine one or more LINQ queries that can have their evaluation delayed:

This example program code includes the detected LINQ queries of OrderBy, ToList, and First. Extendable query detector902designates the following Operation Tree:

where 1stOfPrimes is the highest level element of the Operation Tree, and First is the lowest level element of the Operation Tree. In this example, extendable query detector902indicates OrderBy and ToList as extendable (delayed execution) because the value of 1stOrdered is not immediately needed (is an input to the subsequent code line), but First is a leaf, and thus is not indicated as extendable.

In another example, extendable query detector902may analyze the following program code to determine one or more LINQ queries that can have their evaluation delayed:

This example program code includes the detected LINQ queries of OrderBy, ToList, OrderByDescending, ToList, First, and First. Extendable query detector902designates an Operation Tree having the following first and second branches:

In this Operation Tree, a common 1stOfPrimes element is the highest level element, and the OrderBy and OrderByDescending nodes branch from a common ReturnListOfPrimes node linked to the 1stOfPrimes element. In this example, extendable query detector902indicates OrderBy and ToList in the first branch and OrderByDescending and ToList in the second branch as extendable (delayed execution) because the values of 1stOrdered and LastOrdered are not immediately needed (are inputs to subsequent code line), but the First in the first branch and the First in the second branch are both leafs, and thus are not indicated as extendable.

In still another example, extendable query detector902may analyze the following example program code to determine one or more LINQ queries that can have their evaluation delayed. This example program code is designed to find the last prime number in the range of 2 to 1000:

public Dictionary<int, double. ReturnDictionaryOfPower(List<int>1stOfInts, int pow){return 1stOfInts.ToDictionary(x => x, x => Math.Pow(x, pow));}public void MainMethod( ){var 1stOfPrimes = ReturnListOfPrimes(1000);var power = ReturnDictionaryOfPower(lstOfPrimes, 2);var lastItem = power.Last( );Console.WriteLine(“Last prime: {0}, {1}”, lastItem,Key,lastItem.Value);}
In this example, the third method (“MainMethod”) references two earlier methods (“ReturnListOfPrimes” and “ReturnDictionaryOfPower”). The first method includes query components of Range, Where, and ToList. The second method includes the ToDictionary query component. The third method includes the Last query component. Query detector402detects these queries in the three methods (step302ofFIG. 3). As shown inFIG. 9, extendable query detector902receives detected queries906, which includes the queries detected by query detector402in the program code. In an embodiment, extendable query detector902analyzes detected queries906and program code106(e.g., by generating an Operation Tree, not shown here for purposes of brevity) to determine whether the detected queries can be lazily evaluated in program code106.

In particular, the third method includes four code lines. When the third method is executed, the first line accesses the first method for a first value, the second line accesses the second method for a second value (based on the first value), the third line performs a query (Last) related to the second value to generate a third value, and the fourth line generates an output based on the third value. Accordingly, extendable query detector902determines that the first and second lines generate values that are not immediately needed (e.g., not output to the user or to the database), but instead are used as inputs to subsequent code lines, and thus the evaluation of the queries in the first and second lines can be delayed. As shown inFIG. 9, extendable query detector902outputs extendable queries908, which indicates the queries determined by extendable query detector902as being extendable.

Referring back to flowchart800inFIG. 8, in step804, a single query expression is formed that includes the one or more evaluation-extendable queries. In an embodiment, query expression assembler904receives extendable queries908, and generates a single query expression that includes the queries determined to be evaluation-extendable (in step802). As shown inFIG. 9, query expression assembler904generates modified queries910, which includes the single query expression that combines evaluation-extendable queries determined by extendable query detector902for program code. Note that for particular program code, query expression assembler904may generate one or more of such query expressions that combine evaluation-extendable queries. Techniques performed by query expression assembler904to combine separate queries into a single query expression will be known to persons skilled in the relevant art(s), and will depend on the particular query language. In one example, a variable in an expression may be replaced with an expression used elsewhere to determine the variable.

For instance, with respect to the above example program code, query expression assembler904may generate the following single query expression for the “var lastItem” expression, which includes the LINQ queries of the first and second methods and the first three lines of the third method:

Note that in an embodiment, query expression assembler904may operate by receiving the Operation Tree generated by extendable query detector902for a query, and in the Operation Tree data structure, indicate/mark query operators that explicitly cause query execution to be “disabled” if not a leaf. In other words, query expression assembler904may mark the Operation Tree in such a manner that query execution happens only on leafs, thereby extending the laziness of the query to a latest point in time.

Referring back to flowchart300inFIG. 3, in step306, a ruleset that includes a plurality of rules is applied to the query components to generate a functionally equivalent query set to the plurality of queries that evaluates more efficiently relative to the plurality of queries. In an embodiment, equivalent query set generator406(FIG. 4) is configured to analyze the detected queries (queries110ofFIG. 1) and generate an alternative query set (replacement queries112ofFIG. 1) that is functionally equivalent to the detected queries, yet executes more efficiently than the original configuration of the detected queries. For instance, equivalent query set generator406may generate replacement queries112to avoid retrieving data that is not used by the program code, to avoid making redundant retrievals of data, to avoid performing operations on data that have no effect on output, etc. To enact these efficiencies, equivalent query set generator406may remove query components, add query components, and/or modify query components.

Equivalent query set generator406may perform its functions in various ways. For instance,FIG. 10shows a flowchart1000providing a process for applying a ruleset to determine a replacement query set for program code, according to an example embodiment. Equivalent query set generator406may operate according to flowchart1000in an embodiment. Flowchart1000is described as follows with respect toFIG. 11.FIG. 11shows a block diagram of equivalent query set generator406, according to an example embodiment. As shown inFIG. 11, equivalent query set generator406includes a context determiner1104and a rule selector1106, and is communicatively coupled with storage210containing ruleset216.

Flowchart1000begins with step1002. In step1002, a common logical context between multiple query components is determined. As shown inFIG. 11, context determiner1104receives modified queries910, which are the queries detected by query detector402and rewritten for lazier evaluation by laziness extender404. Context determiner1104analyzes modified queries910for a common logical context. For example, context determiner1104may decompose modified queries910, which may be a single query expression, into a set of query components, and compares the query components to each other. When similar or related types of query components are detected (e.g., OrderBy and OrderByDescending, etc.), a common logical context between the query components is established. As shown inFIG. 11, context determiner1104outputs contextually associated queries1114, which includes groups of query components of modified queries910that are contextually associated.

In step1004, a rule of the ruleset corresponding to the common logical context is applied to the multiple query components. As shown inFIG. 11, rule selector1106receives contextually associated queries1114. Rule selector1106analyzes contextually associated queries1114for applicability of rules of ruleset216, such as a first rule1108, a second rule1110, etc. Each rule of ruleset216is configured to be applied to query components of a corresponding common context, and to rewrite the query components for greater efficiency, such as by adding, modifying, and/or deleting query components of the contextually associated queries. Any number and variety of rules may be included in ruleset216. Seven examples of rules that may be included in ruleset216are described as follows for purposes of illustration. Each rule is described below with an exemplary rule name, an abstract, and a description of the function/mechanics of the rule:

Abstract: Used to eliminate unnecessary OrderBy operations.

Rule Mechanics: The OrderBy Minimizer steps through a list of OrderBy operators found in the program code, and finds any of the OrderBy operators whose result is not used in the program code (where “used” means the ordering performed by the OrderBy operator is not relied upon—is not output or required by a subsequent expression or method). For such a found OrderBy operator, the OrderBy Minimizer deletes the OrderBy operator as redundant from the program code, and rewrites any other lines of the program code affected by deletion of the code line statement (e.g., replacing variable names, etc.)

Abstract: Used in the case of a complicated query that performs the following “ToCurrent” type of operators multiple times in succession—“ToList”, ‘ToDictionary’, etc. Each of these ToCurrent operators are costly, and in a sequence of them, they are redundant except for the last operator in the sequence.

Rule Mechanics: The following pattern is detected—two or more of such operators in an aggregated set of query components (e.g., the single query expression containing multiple query components that was generated in step804of flowchart800). All of the ToCurrent type operators are discarded from the aggregated set of query components except for the one (without changing the logic).

Abstract: Used when a large quantity of data requested by a query operator is not ultimately used, and thus the data retrieval can safely by reduced or not performed at all.

Rule Mechanics: The following pattern is detected—a query operator retrieves data, the retrieved data is sorted, and just the first or last element of the sorted data is used. Replace this query by a query which just performs the minimum value element or maximum value element retrieval, respectively, from the data

Abstract: Used when a large quantity of data requested by a query operator is not ultimately used, and thus the data retrieval can safely by reduced or not performed at all.

Rule Mechanics: The following pattern is detected—a query operator retrieves data, and just the first or last element of the data is used. Replace this query by a query which just retrieves any random data element from the data.

Abstract: Used when a single very large data entity is retrieved but just a portion of the data is ultimately used.

Rule Mechanics: The following pattern is detected—data is requested that has the potential of being a large dataset (e.g., XML data, JSON data, a whole file, etc.), while just a subset of the retrieved data is to be used. Replace this query by a query which just retrieves the subset of data.

Examples of the applicability of the “DataRetrival Minimizer—Type 3” rule include:

(1) Requesting retrieval of a file, but ultimately only using the metadata of the file to determine how large the file is (rather than using the contents of the file). This rule can be used to avoid using a query operator to retrieve the entire file, but instead use a query operator to retrieve the file metadata (which may be several factors smaller in size than the entire file).

(2) Requesting a single database line or entity, and ultimately only using a single column of that line/entity. The entire DB line/entity might be very large. This rule can be used to replace the query operator with another query operator that retrieves only the desired column.

Abstract: Used when a query is utilizing a single value, and therefore there is no need to build the entire data structure in memory.

Rule Mechanics: The following pattern is detected—only a single value is used after a “ToCurrent” type operator. Switch the first with the later.

Abstract: Used in cases where just the last item is needed, and therefore enumerating from start to end is inefficient. By enumerating in reverse order we increase performance.

Rule Mechanics: The following pattern is detected—only the last value is used after a “ToCurrent” type operator. Replace the enumeration with its “reverse” matching operator and/or reverse the enumeration range values, and replace the operator “Last” with the operator “First”.

As a further illustration, example rules are applied against the single query expression generated above, which is repeated below for ease of description:

As described above, lazy evaluation was extended (step304of flowchart300; laziness extender404) to generate this functionally-equivalent aggregated set of query components. Furthermore, the efficiency of this single query expression may be further improved by applying rules of ruleset216(step306of flowchart300; equivalent query set generator406).

For instance, the ToCurrent Collection Minimizer rule (rule (B) above) may applied. In such case, context determiner1104detects the ToList and ToDictionary operators in the above query statement, which establish a common logical context. Rule selector1106applies the ToCurrent collection minimizer rule, which is associated with this common logical context in ruleset216. The ToCurrent collection minimizer rule removes all ToCurrent operators from the query statement except for the last one, to generate the following more efficient, but functionally-equivalent query expression:

Furthermore, the Enumeration Iteration Minimizer rule (rule (F) above) may be used that repositions a Last( )/First( ) operator to be located before a ToCurrent statement (in this case ToDictionary). In this manner, the query statement iterates until the first item is found, and therefore all the data structure is not filled. Instead, the ToDictionary operator will operate on a single entity. Accordingly, context determiner1104determines the ToDictionary operator followed by a Last operator in the above query statement to establish a common logical context. Rule selector1106applies the Enumerable iteration rule, which is associated with this common logical context. The Enumerable iteration rule repositions the Last operator before the ToDictionary operator, to generate the following more efficient, but functionally-equivalent query expression:

Still further, the Reversing Enumeration When Using Last( ) Operator (rule (G) above) may be used that reverses an order of search for a last item. This is because it is much more efficient to go in reverse order when looking for the last item. Thus, this rule enumerates numbers in reverse order and take the first element rather than the last. Accordingly, context determiner1104determines the Last operator preceding the ToDictionary operator in the above query statement to establish a common logical context. Rule selector1106applies the Optimizing the Enumerable rule, which is associated with this common logical context. The Optimizing the Enumerable rule replaces the Last operator with a First operator, to generate the following more efficient, but functionally-equivalent query expression:

This final query iterates over the integers starting from 1100 downwards, finding the first prime therein, and performing this much more efficiently (e.g., using less memory to store data, and better using the CPU) than the original, three-method version shown further above.

Note that in an embodiment, equivalent query set generator406may sequentially apply rules of ruleset216until no more rules can be applied to determine a single functionally equivalent query set. In another embodiment, multiple different sets of functionally equivalent query sets may be determined by equivalent query set generator406, with each determined set being applicable to replace the detected queries in program code106. In such an embodiment, rule selector1106may enable the developer to manually select one of the functionally equivalent query sets to apply to program code106to generate refactored program code108. Alternatively, rule selector1106may make the selection automatically.

For instance,FIG. 12shows a flowchart1200providing a process for generating and selecting between a plurality of candidate functionally equivalent query sets, according to an example embodiment. In an embodiment, rule selector1106may perform flowchart1200. Flowchart1200is described as follows.

In step1202, the application of a plurality of combinations of rules of the ruleset to the query components is evaluated to generate a plurality of candidate functionally equivalent query sets. In an embodiment, rule selector1106may apply different combinations and/or orders of rules to program code to generate different functionally equivalent query sets. For example, a particular program code may include OrderBy, GroupBy, and ThenBy query components in a query expression. Rule selector1106may apply a first rule to the query expression that replaces the OrderBy and GroupBy with a first query operator to generate a first functionally equivalent query set, and then may alternatively then apply a second rule to the query expression that replaces the GroupBy and ThenBy with a second query operator to generate a second functionally equivalent query sets. In this manner, two functionally equivalent query sets are generated for a same query expression, which may each have their own efficiency characteristics. Any number of functionally equivalent query sets may be generated for a same query expression, depending on the particular query operators in the query expression, and the rules available in ruleset216.

In step1204, a candidate functionally equivalent query set of the plurality of candidate functionally equivalent query sets having a greatest efficiency gain is selected to be the generated functionally equivalent query set. In the above example, rule selector1106may enable the developer to select which of the first and second functionally equivalent query sets to refactor into the program code, or may automatically select which of the first and second query components to refactor into the program code. For example, rule selector1106may select the one of the available functionally equivalent query sets having a greatest efficiency. This greatest efficiency may be determined in various ways.

For instance, each rule in ruleset216may have a corresponding efficiency value (e.g., a number from 0-1) that indicates a relative efficiency for the rule. Rule selector1106may combine the efficiency values for each of the rules used for a particular functionally equivalent query set to determine an overall efficiency value of that functionally equivalent query set, and then may compare the overall efficiency values for all functionally equivalent query sets to determine which has the greatest efficiency. In other embodiments, rule selector1106may determine a greatest efficiency in other ways.

Note that in an embodiment, flowchart1200may be performed at compile time or at runtime. For instance, at runtime, an executable version of program code106or refactored program code108(e.g., machine code222) may be executed by an execution engine (e.g., in an operating system, etc.). According to a runtime embodiment, the best candidate functionally equivalent query set may be determined in a manner that takes into account the actual system health state. This is because the efficiency gain provided by one or more of the candidate functionally equivalent query sets may be at least partially dependent on execution conditions at runtime. For instance, at runtime, the executable version of program code may execute, and when a particular query is to be executed, a call may be made by the program code to rule selector1106(which may be implemented by the execution engine, for instance), to select which candidate functionally equivalent query set to implement based runtime conditions (e.g., network conditions, available processing bandwidth, available processing power, etc.).

For example, in normal runtime conditions (e.g., full network availability, etc.), candidate functionally equivalent query set A may be more efficient than functionally equivalent query set B. However, during a particular runtime, something undesired may interfere with the performance of the query components of functionally equivalent query set A, such as a slow Internet connection, etc. Accordingly, in such a runtime condition (e.g., poor network response), functionally equivalent query set B may enable more efficiency, and thus may be selected by rule selector1106to be executed during that particular runtime (rather than query set A). Accordingly, in embodiments, rule selector1106may be configured to enable selection of a candidate functionally equivalent query set at runtime.

It is noted the rules may be added to ruleset216in any manner, including manually or automatically. For example, a developer may add a rule to ruleset216based on the experience of the developer, including a desire to fix a particular efficiency problem with queries that developer as seen or been made aware of. In another embodiment, an automatic mechanism may generate new rules, including an automatic mechanism that incorporates machine learning. Machine learning may be used to sample equivalent queries during runtime for relative efficiency, and based thereon, automatically select the most efficient query for that scenario. For each query optimization provided by a rule, query optimizer104may maintain a detailed analysis of the impact made by the query optimization.

III. Example Mobile and Stationary Device Embodiments

For instance, in an embodiment, one or more, in any combination, of query optimizer104, compiler204, development application200, source code editor202, compiler204, debugger tool206, query detector402, laziness extender404, equivalent query set generator406, extendable query detector902, query expression assembler904, content determiner1104, rule selector1106, flowchart300, flowchart500, flowchart700, flowchart800, flowchart1000, and/or flowchart1200may be implemented together in a SoC. The SoC may include an integrated circuit chip that includes one or more of a processor (e.g., a central processing unit (CPU), microcontroller, microprocessor, digital signal processor (DSP), etc.), memory, one or more communication interfaces, and/or further circuits, and may optionally execute received program code and/or include embedded firmware to perform functions.

FIG. 13depicts an exemplary implementation of a computing device1300in which embodiments may be implemented. For example, computing device102and/or client computing device104may be implemented in one or more computing devices similar to computing device1300in stationary or mobile computer embodiments, including one or more features of computing device1300and/or alternative features. The description of computing device1300provided herein is provided for purposes of illustration, and is not intended to be limiting. Embodiments may be implemented in further types of computer systems, as would be known to persons skilled in the relevant art(s).

As shown inFIG. 13, computing device1300includes one or more processors, referred to as processor circuit1302, a system memory1304, and a bus1306that couples various system components including system memory1304to processor circuit1302. Processor circuit1302is an electrical and/or optical circuit implemented in one or more physical hardware electrical circuit device elements and/or integrated circuit devices (semiconductor material chips or dies) as a central processing unit (CPU), a microcontroller, a microprocessor, and/or other physical hardware processor circuit. Processor circuit1302may execute program code stored in a computer readable medium, such as program code of operating system1330, application programs1332, other programs1334, etc. Bus1306represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. System memory1304includes read only memory (ROM)1308and random access memory (RAM)1310. A basic input/output system1312(BIOS) is stored in ROM1308.

Computing device1300also has one or more of the following drives: a hard disk drive1314for reading from and writing to a hard disk, a magnetic disk drive1316for reading from or writing to a removable magnetic disk1318, and an optical disk drive1320for reading from or writing to a removable optical disk1322such as a CD ROM, DVD ROM, or other optical media. Hard disk drive1314, magnetic disk drive1316, and optical disk drive1320are connected to bus1306by a hard disk drive interface1324, a magnetic disk drive interface1326, and an optical drive interface1328, respectively. The drives and their associated computer-readable media provide nonvolatile storage of computer-readable instructions, data structures, program modules and other data for the computer. Although a hard disk, a removable magnetic disk and a removable optical disk are described, other types of hardware-based computer-readable storage media can be used to store data, such as flash memory cards, digital video disks, RAMs, ROMs, and other hardware storage media.

A number of program modules may be stored on the hard disk, magnetic disk, optical disk, ROM, or RAM. These programs include operating system1330, one or more application programs1332, other programs1334, and program data1336. Application programs1332or other programs1334may include, for example, computer program logic (e.g., computer program code or instructions) for implementing query optimizer104, compiler204, development application200, source code editor202, compiler204, debugger tool206, query detector402, laziness extender404, equivalent query set generator406, extendable query detector902, query expression assembler904, content determiner1104, rule selector1106, flowchart300, flowchart500, flowchart700, flowchart800, flowchart1000, and/or flowchart1200(including any suitable step of flowcharts300,500,700,800,1000,1200), and/or further embodiments described herein.

A user may enter commands and information into the computing device1300through input devices such as keyboard1338and pointing device1340. Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, a touch screen and/or touch pad, a voice recognition system to receive voice input, a gesture recognition system to receive gesture input, or the like. These and other input devices are often connected to processor circuit1302through a serial port interface1342that is coupled to bus1306, but may be connected by other interfaces, such as a parallel port, game port, or a universal serial bus (USB).

A display screen1344is also connected to bus1306via an interface, such as a video adapter1346. Display screen1344may be external to, or incorporated in computing device1300. Display screen1344may display information, as well as being a user interface for receiving user commands and/or other information (e.g., by touch, finger gestures, virtual keyboard, etc.). In addition to display screen1344, computing device1300may include other peripheral output devices (not shown) such as speakers and printers.

Computing device1300is connected to a network1348(e.g., the Internet) through an adaptor or network interface1350, a modem1352, or other means for establishing communications over the network. Modem1352, which may be internal or external, may be connected to bus1306via serial port interface1342, as shown inFIG. 13, or may be connected to bus1306using another interface type, including a parallel interface.

As noted above, computer programs and modules (including application programs1332and other programs1334) may be stored on the hard disk, magnetic disk, optical disk, ROM, RAM, or other hardware storage medium. Such computer programs may also be received via network interface1350, serial port interface1342, or any other interface type. Such computer programs, when executed or loaded by an application, enable computing device1300to implement features of embodiments discussed herein. Accordingly, such computer programs represent controllers of the computing device1300.

In an embodiment, a method comprises: detecting a plurality of queries in program code; extending laziness by which the queries are evaluated in the program code; and applying a ruleset that includes a plurality of rules to the detected queries to generate a functionally equivalent query set that evaluates more efficiently relative to the detected queries.

In an embodiment, the detecting comprises: detecting the queries in the program code in a code editor; and the method further comprising: presenting an option for the code editor to automatically refactor the program code to replace the plurality of queries with the functionally equivalent query set.

In an embodiment, the detecting comprises: detecting the queries in the program code during compilation; and the method further comprising: generating compiled code in the compiler based on a version of the program code where the plurality of queries is replaced with the functionally equivalent query set.

In an embodiment, the extending laziness by which the queries are evaluated in the program code comprises: detecting one or more of the queries that are evaluation-extendable; and forming a single query expression that includes the one or more evaluation-extendable queries.

In an embodiment, the applying a ruleset comprises: determining a common logical context between multiple query components; and applying a rule of the ruleset corresponding to the common logical context to the multiple query components.

In an embodiment, the generated functionally equivalent query set evaluates more efficiently relative to the plurality of queries by at least one of generating query results consuming less memory space than query results of the plurality of queries, taking less time to execute than the plurality of queries, consuming less network bandwidth than the plurality of queries, or, consuming less processing power than the plurality of queries.

In an embodiment, the applying a ruleset comprises: evaluating the application of a plurality of combinations of rules of the ruleset to the query components to generate a plurality of candidate functionally equivalent query sets; and selecting a candidate functionally equivalent query set of the plurality of candidate functionally equivalent query sets having a greatest efficiency gain to be the generated functionally equivalent query set.

In an embodiment, the applying a ruleset comprises: evaluating during runtime the application of a plurality of combinations of rules of the ruleset to the query components to generate a plurality of candidate functionally equivalent query sets; and selecting during runtime a candidate functionally equivalent query set of the plurality of candidate functionally equivalent query sets having a greatest efficiency gain to be the generated functionally equivalent query set.

In an embodiment, the efficiency gain provided by one or more of the candidate functionally equivalent query sets is at least partially dependent on execution conditions at runtime.

In an embodiment, the method further comprises: using machine learning to generate at least one rule to add to the ruleset.

In another embodiment, a computing device comprises: at least one processor circuit; and at least one memory that stores program code configured to be executed by the at least one processor circuit, the program code configured to perform operations comprising: detecting a plurality of queries in program code; extending laziness by which the queries are evaluated in the program code; and applying a ruleset that includes a plurality of rules to the detected queries to generate a functionally equivalent query set that evaluates more efficiently relative to the detected queries.

In an embodiment, the detecting comprises: detecting the queries in the program code in a code editor; and the method further comprising: presenting an option for the code editor to automatically refactor the program code to replace the plurality of queries with the functionally equivalent query set.

In an embodiment, the detecting comprises: detecting the queries in the program code during compilation; and the method further comprising: generating compiled code in the compiler based on a version of the program code where the plurality of queries is replaced with the functionally equivalent query set.

In an embodiment, the extending laziness by which the queries are evaluated in the program code comprises: detecting one or more of the queries that are evaluation-extendable; and forming a single query expression that includes the one or more evaluation-extendable queries.

In an embodiment, the applying a ruleset comprises: determining a common logical context between multiple query components; and applying a rule of the ruleset corresponding to the common logical context to the multiple query components.

In an embodiment, the applying a ruleset comprises: evaluating the application of a plurality of combinations of rules of the ruleset to the query components to generate a plurality of candidate functionally equivalent query sets; and selecting a candidate functionally equivalent query set of the plurality of candidate functionally equivalent query sets having a greatest efficiency gain to be the generated functionally equivalent query set.

In an embodiment, the applying a ruleset comprises: evaluating during runtime the application of a plurality of combinations of rules of the ruleset to the query components to generate a plurality of candidate functionally equivalent query sets; and selecting during runtime a candidate functionally equivalent query set of the plurality of candidate functionally equivalent query sets having a greatest efficiency gain to be the generated functionally equivalent query set.

In an embodiment, the efficiency gain provided by one or more of the candidate functionally equivalent query sets is at least partially dependent on execution conditions at runtime.

In an embodiment, the operations further comprise: using machine learning to generate at least one rule to add to the ruleset.

In another embodiment, a computing device comprises: at least one processor circuit; and at least one memory that stores program code configured to be executed by the at least one processor circuit, the program code comprising: a query detector configured to detect a plurality of queries in program code; a laziness extender configured to extend laziness by which the queries are evaluated in the program code; and an equivalent query set generator configured to apply a ruleset that includes a plurality of rules to the detected queries to generate a functionally equivalent query set that evaluates more efficiently relative to the detected queries.