Heuristic Method for Joining Relational Data Base Tables
Original Publication Date: 1988-Feb-01
Included in the Prior Art Database: 2005-Feb-14
This invention relates to a method for joining tables responsive to relational queries. (Image Omitted) The method is of the "greedy heuristic" type. This type combines features of both breadth-first and depth-first search strategies. The method iteratively estimates the cost of all joins it could perform next and picks the cheapest one, without concern for the impact that that choice might have on future joins. For example, the cheapest join of A and B might access table A as the outer table using a DBSPACE scan, leaving the tuples of the result in no particular order; whereas a more expensive index scan of A might have left the tuples of A*B in the order necessary to join A*B with C. Existing breadth-first algorithms would retain the more expensive plan in the hope of reducing the cost of a later join.