Distance-based logical exploration in a relational database query optimizer

A method for generating an execution plan for a query in a relational database system, comprising:

• generating one or more initial logical representations of the query, each initial logical representation including a plurality of operators;
• performing a bounded exploration process comprising:
• (a) adding the operators of the one or more initial logical representations to a data structure;
• (b) identifying zero or more patterns of operators within the data structure that are eligible for the application of a transformation rule, a pattern of operators being eligible for the application of a transformation rule if (i) the pattern of operators matches a pattern associated with the transformation rule and (ii) a search distance associated with one or more of the operators in the pattern of operators is less than a maximum allowable search distance;
• (c) applying a transformation rule to each eligible pattern of operators identified in step (b) to generate a logically-equivalent pattern of operators within the data structure, thereby generating one or more additional logical representations of the query within the data structure;
• (d) assigning a search distance to each operator within each logically-equivalent pattern of operators generated during step (c), the assigned search distance being a function of a search distance of one or more operators within the eligible pattern of operators to which the logically-equivalent pattern of operators corresponds;
• and
• (e) repeatedly performing steps (b), (c) and (d) until no further patterns of operators that are eligible for the application of a transformation rule can be identified within the data structure;
• obtaining one or more physical implementation alternatives for each of the logical representations of the query included in the data structure;
• and
• selecting one of the physical implementation alternatives as the execution plan.

A system, comprising:

• one or more processors;
• and
• a storage medium that stores computer program logic that is executable by the one or more processors, the computer program logic comprising:
• first computer program logic that is programmed to cause the one or more processors to generate one or more initial logical representations of a query;
• second computer program logic that is programmed to cause the one or more processors to perform an exploration process around each of the one or more initial logical representations of the query, the performing of the exploration process around a particular initial logical representation of the query comprising applying transformation rules to generate one or more additional logical representations of the query that are logically equivalent to the particular initial logical representation of the query and that are within a maximum allowable transformation distance of the particular initial logical representation of the query;
• third computer program logic that is programmed to cause the one or more processors to generate one or more execution plans for each initial logical representation of the query and each additional logical representation of the query;
• and
• fourth computer program logic that is programmed to cause the one or more processors to select an execution plan from among the generated execution plans.