Browse Prior Art Database

An Efficient Algorithm for Determining the Optimum Access Path for Complex SQL Queries

IP.com Disclosure Number: IPCOM000021754D
Original Publication Date: 2004-Feb-05
Included in the Prior Art Database: 2004-Feb-05
Document File: 1 page(s) / 27K

Publishing Venue

IBM

Abstract

Algorithms used to determine the optimum join sequence for relational database queries which involve multiple tables can be very expensive in terms of CPU and storage use. One algorithm, known as the dynamic programming algorithm, can increase such usage proportional to 2**N, where N is the number of tables in the query. The dynamic programming algorithm simulates the construction of composite tables. For the first step, one-table composites are simulated, and the cost and best plan to construct each one are determined. At each subsequent step, the construction of all composites with first two tables, then three tables, and so on are simulated, until the final N-table composite is simulated. For every composite simulated, the cost and best plan are determined. As the number of tables increases, the amount of data required can become very large, consuming large amounts of storage. This invention solves this problem by reducing the number of candidate solutions at each step of the dynamic programming algorithm.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 64% of the total text.

Page 1 of 1

An Efficient Algorithm for Determining the Optimum Access Path for Complex SQL Queries

Algorithms used to determine the optimum join sequence for relational database queries which involve multiple tables can be very expensive in terms of CPU and storage use. One algorithm, known as the dynamic programming algorithm, can increase such usage proportional to 2**N, where N is the number of tables in the query.

The dynamic programming algorithm simulates the construction of composite tables. For the first step, one-table composites are simulated, and the cost and best plan to construct each one are determined. At each subsequent step, the construction of all composites with first two tables, then three tables, and so on are simulated, until the final N-table composite is simulated. For every composite simulated, the cost and best plan are determined.

As the number of tables increases, the amount of data required can become very large, consuming large amounts of storage.

This invention solves this problem by reducing the number of candidate solutions at each step of the dynamic programming algorithm.

The reduction process, which will be termed "clipping", selects a subset of the composites at each step. Only the composites in the subset will be used to generate the composites at the next step. This reduces the number of composites simulated, thereby reducing both the CPU and storage required to find the best solution.

The subset is selected by choosing a number of comp...