The European Patent Office considered cost-based optimisation of a query in a relational database system technical. Here are the practical takeaways from the decision T 1965/11 (Cost-based materialised view selection/MICROSOFT TECHNOLOGY LICENSING) of 24.3.2017 of Technical Board of Appeal 3.5.07:
The application underlying the present decision relates to a database query optimizer that selects materialized views on a cost basis (cf. EP 1 193 618 A2, para. ). A known concept regarding databases is to materialize (store) the result of queries and then use the computed result when similar queries are submitted to the database (cf. EP 1 193 618 A2, para. ). For maximum flexibility, applications should not need to be aware that certain views exist, or are materialized. A query processor should identify matches between user queries and existing pre-computed results, and use such results when applicable (cf. EP 1 193 618 A2, para. ). However, on some complex queries, view utilization will be possible only in sub-expressions of the complete query. These sub-queries may appear only after some reordering has taken place, which is a time-consuming task (cf. EP 1 193 618 A2, para. ). Hence, the present application aims at providing a cost based query optimizer that determines the applicability of materialized views to a query. View utilization alternatives are generated in the exploration stage of optimization, so that interaction with other transformations in complex queries is taken into account. A final decision on whether to use a materialized view is based on estimated costs (cf. EP 1 193 618 A2, para. ).
Fig. 2 of EP 1 193 618 A2
Claim 1 (auxiliary request IV)
1. A method for a computer-implemented query optimizer for selecting an execution plan for use in execution of a relational database query, the method comprising:
generating, by a cost-based query optimizer, a table (300) of alternatives, the table (300) of alternatives comprising several groups, one group having a root entry representing the database query and additional entries representing alternative possibilities for executing the database query and the other groups having root entries representing sub-expressions of the database query and additional entries representing alternative possibilities for executing the respective sub-expression of the database query;
selecting candidate views for the query from a number of materialized views by using information about what database tables are referenced in the query and whether or not the query contains aggregations;
for each root entry,
extracting an operator tree for the root entry,
collapsing binary joins contained in the operator tree to obtain a query graph for the root entry, the query graph listing all underlying tables along with predicates that are applied on them,
matching the query graph for the root entry and the candidate views, and
if a match is found, extending the table (300) of alternatives with the corresponding candidate view by extending the group of the root entry with the corresponding candidate view; and
using the cost based query optimizer to select an execution plan based on the extended table (300) of alternatives.
Is it patentable?
The examining division rejected the present application at the end of the examining phase due to added subject-matter. This decision was appealed. In the statement of grounds of appeal, the appellant requested that the decision be set aside and also asked the Board to decide that the claims of at least the fourth auxiliary requests were allowable.
A plurality of prior art documents were discussed during the oral hearing. When it came to the assessment of inventive step, the Board in charge argued as follows:
5.1 According to decision T 1569/05 of 26 June 2008, reasons 3.6, retrieving data in a computer database is normally considered to have technical character. While the method of claim 1 does not include the actual data retrieval, the Board considers that the cost-based optimisation of a query in a relational database system has normally technical character (see T 1003/09 of 29 April 2015, reasons 13.3 and 13.5). Such cost-based query optimisation searches for low-cost query execution plans using a cost estimate for the computer resources (such as CPU, main memory or hard disk) needed to execute a query plan (see D8, section 2, for technical background). Hence, this cost-based approach involves further technical considerations (see opinion G 3/08, “Programs for computers”, OJ EPO 2011, 10, reasons 13.5) relating to the internal functioning of the computer system.
Furthermore, the Board was of the opinion that none of the cited prior art documents could render-obvious the subject-matter as defined by claim 1 of auxiliary request IV:
5.3 None of these prior-art documents addresses the problem of extending a table of alternatives generated by the query optimiser by adding further alternatives using materialised views. The invention makes it possible to find low-cost query execution plans that make use of the available materialised views in order to improve query performance (see page 2, third paragraph). Moreover, in order to explore the search space for such low-cost query execution plans, it proposes integrating the materialised views into the table of alternatives during the plan exploration stage. For this integration, it is necessary to match query plans with materialised views in order to identify useful plan alternatives for such views. The invention teaches using query graphs for the matching in order to substantially reduce the complexity of extracting operator trees which encode a specific join order. In the technical context of query optimisation in relational database systems, this teaching is based on further technical considerations and solves the problem of providing a technically feasible implementation, in particular one that achieves an acceptable time complexity for query optimisation in relational database systems.
As a result, the Board remitted the application back to the examining division with the order to grant a patent based on auxiliary request IV.
You can read the whole decision here: T 1965/11 (Cost-based materialised view selection/MICROSOFT TECHNOLOGY LICENSING) of 24.3.2017.