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:
Key takeaways
Retrieving data in a computer database is normally considered to have technical character.
More specifically, cost-based query optimisation that searches for low-cost query execution plans using a cost estimate for computer resources involves further technical considerations.
The invention
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. [0001]). 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. [0004]). 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. [0005]). 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. [0009]). 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. [0010]).
Fig. 2 of EP 1 193 618 A2
-
Claim 1 (auxiliary request IV)
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.
More information
You can read the whole decision here: T 1965/11 (Cost-based materialised view selection/MICROSOFT TECHNOLOGY LICENSING) of 24.3.2017.