System and methodology for join enumeration in a memory-constrained environment

• US 20020116357A1
• Filed: 12/06/2000
• Published: 08/22/2002
• Est. Priority Date: 12/07/1999
• Status: Active Grant

• Current Assignee: iAnywhere Solutions Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Paulley, Glenn Norman
• Granted Patent: US 6,516,310 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A small-footprint relational database system providing a deterministic join enumeration methodology for left-deep processing trees is described. By providing a deterministic branch-and-bound join enumeration method for left-deep processing trees, the invention is able to efficiently optimize complex queries with high join degree by employing a novel approach to cost-based pruning of the search space. For each subquery, plan generation involves the following four distinct steps. First, the system adjusts predicate selectivities to account for disjuncts, Between predicates, and user estimates of selectivities. Next, the system constructs a join graph for the query that models inner and outer equijoin predicates, sargable single-variable predicates on single quantifiers, and Cartesian products. The system then enumerates join strategies and prune the search space using a branch-and-bound heuristic. Finally, the system recalls the cheapest strategy and constructs the detailed access plan for that strategy. Empirical performance results on several production queries show that this approach requires significantly less memory than other deterministic join enumeration approaches, which have been described in the literature.

Claims

1. 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.