Database System and Methodology for Generalized Order Optimization

A system for optimizing a query requesting data from a database in an ordered form, the system comprising:

• a module for generating a plurality of partial plans for obtaining data requested by the query;
• a generalized order comprising a data structure for representing a set of simple orders;
• a module for constructing generalized orders representing interesting orders of the query and generalized orders representing order properties of each of said plurality of partial plans;
• a matching module for determining if a partial plan has order properties matching the interesting orders based on comparing a generalized order representing order properties of the partial plan with generalized orders representing interesting orders;
• and
• a module for building a query execution plan for obtaining and ordering the data requested by the query based, at least in part, on selecting partial plans having order properties matching the interesting orders.

In a database system, a method for constructing an optimal query execution plan for executing a query requesting data in an ordered form, the method comprising:

• identifying each query block within said query, each query block comprising an atomic portion of said query;
• creating subplans for each query block for returning data requested by the query;
• constructing a first set of generalized orders representing requirements of the query for ordering of data, each generalized order representing a set of simple orders;
• creating a second set of generalized orders representing order properties of each subplan;
• comparing generalized orders in the second set with generalized orders in the first set to identify subplans having favorable order properties;
• and
• building a query execution plan for returning the data in the ordered form requested by the query based, at least in part, on selecting subplans having favorable order properties.