Re: Relational Algorithms

Hi Martin,

> Database algorithms are not my area at all but I need to get
>some idea of the time complexity of the algorithms used to manipulate
>relational database tables. For example, when performing a JOIN, is a
>cartesian product actually taken first and then the 'live' rows selected or
>is(are) there algorithms for this task with a better performance?
>

In the Ingres database (and I suppose derivatives such as Sybase/Microsoft SQL Server) query execution is performed in various stages, or facilities.

One of the early stages is the OPF, or optimizer facility.

It is the function of the OPF to create an execution plan that Ingres 'thinks' will be the most optimal.

The execution plan is actually a tree. All possible trees (depending on settings) are generated prior to selecting the most optimal (usually related to disk accesses, although CPU cycles are taken into consideration).

The reason these Query Execution Plans (QEPs) are so important, is that it usually matters in which order tables are joined together, especially with regard to the table structure, available indexes, number of rows per page, etc, etc, etc....

The primary things Ingres uses in QEP Analysis/Execution is Projection-Restriction, Joins (Full/Partial Sort Merges, Key Joins, Cartesian Product joins, Tuple Joins [direct lookups], etc), and Sorting.

This should be documented in any large scale database server (It certainly is in the Ingres DBA guide - try
http://www.cai.com/products/ingres/documentation_set.htm).

Andrew Wilson
BlueOffice Solutions ApS
Denmark Received on Wed May 03 2000 - 00:00:00 CEST