Patent ID: 6516310
Filing Date: 2003-02-04
Classification: G06F,Y10S

Abstract:
In a relational database system, a method for determining an optimal join order for use in an access plan employed for executing a database query, the method comprising:receiving a query specifying at least one join condition between two or more database tables; establishing an initial join order, based on each table's size and join predicates between the tables, said initial join order specifying a particular sequence for accessing said tables, said sequence indicating a first join position specifying an outer table and one or more subsequent join positions specifying one or more successive inner tables; determining a strategy cost for satisfying the query using a query access plan that employs said initial join order; starting from the innermost positions of the join order and proceeding to be outermost position of the join order, evaluating other candidate join orders by swapping ordering of tables at a given position with those at subsequent positions and thereafter determining the cost strategy for that join order; and if a given candidate join order under consideration has a prefix ordering of outermost tables that has a cost strategy that is worse than that already obtained, then eliminating from consideration any candidate join orders having that prefix ordering of outermost tables; and selecting the candidate join order having the most favorable strategy cost.