Re: Help: SQL query optimizer

In <anique.732967452@sun-4> anique@sun-4.cs.uct.ac.za (Anique Van der Vlugt) writes: >I am presently involved in a project for a SQL query optimizer for INFORMIX. >Has anyone done any research in this field or knows of anyone who does? I >am also interested in any articles related to the field of query optimization. >If you can help me in any way please email me. >Thanks for your attention >Anique >---------------------------------------------------------------------------- >Anique van der Vlugt >University of Cape Town >Cape Town >South Africa >email address: anique@cs.uct.ac.za >---------------------------------------------------------------------------- From: Spring 1987 TechNotes Query Optimization ================== This article is applicable to the following products: - INFORMIX-4GL Version 1.00 and later - INFORMIX-SQL Version 2.00 and later - INFORMIX-ESQL/C Version 2.00 and later - INFORMIX-ESQL/COBOL Version 2.00 and later As you use your SQL-based Informix Software product, you can be relatively unconcerned with the mechanics of query pro- cessing. Not only is SQL a results-oriented language, but your product includes an optimizer to ensure that your queries are processed efficiently. Even so, you can influence performance in a number of ways, which Tech Notes will explore in a series of articles on query optimization. This article, the first in that series, appropriately begins by examining the underlying logic of the optimizer. It concludes by explaining how, based on that logic, you can index queries to improve performance. How RDSQL Constructs a Query Plan The REDSQL optimizer (a part of sqlexec or sqlturbo) selects a processing strategy for each RDSQL statement. This strategy, or query plan, determines the order in which RDSQL searches tables (the table-selection order) and which indexes are needed to process the query. The optimizer establishes an efficient table-selection order by applying a set of criteria to the table involved in the query. These table-selection criteria are derived from general principles of query optimization; for example, an indexed search retrieves an arbitrary value faster than a non-indexed (row-by-row) search, and processing speed increases when the number of rows the query processor must examine for the query decreases. If one criterion cannot order the tables, the optimizer applies another, and so on, through the last criterion. If this criterion cannot order the tables, the selection order becomes the order of tables in the FROM clause. (See the section "Establishing the Table-Selection Order" later in this article for details.) Note: The terms filter and join are integral to a discussion of query optimization. They are defined in the following paragraphs if you are not familiar with them. A filter is a condition expressed in a WHERE clause that removes undesired rows from a single table. Example: The following SELECT statement applies two filters ("> 100.00" and "< 400.00") to the same column (the filter column): SELECT FROM stock WHERE (unit_price > 100.00 AND unit_price < 400.00) Each filter defines a subset of all the rows in the unit_price column, thereby reducing the number of rows RDSQL must examine to process the query. A join temporarily links two or more tables so that they can be queries as a single table. You can join tables when they contain columns that store comparable data, such as the customer_num columns in the customer and orders tables of the stores database. Example: A join normally creates a relationship of equality between columns in two or more tables, as in the following WHERE clause: SELECT order_num, lname, fname FROM customer, orders WHERE customer.customer_num = orders.customer_num Although less common, joins can specify nonequal relationships as well. You can, in fact, use any relational operator in place of the equal sign that logically makes sense for your query. Establishing the Table-Selection Order The optimizer applies the following criteria to establish the table-selection order. The first criterion is applied to the FROM clause; subsequent criteria are applied tot he entire WHERE clause. Criterion 1: Outer Joins The optimizer gives priority to the domin ant table in an outer join, or selects this table to be processedd first, without applying subsequent criteria. By processing the domin ant table first, RDSQL can preserve all of its rows. When a query outer-joins the result of a nested outer join to a third table, the optimizer gives priority to the outermost domin ant toable, followed by the innermost dominant table. ("Outermost" and "innermost" refer to the level of nesting in the FROM list.) Examples: SELECT ... FROM x, OUTER y WHERE x.a = y.a table order is x then y SELECT ... FROM x, OUTER (z, OUTER y) WHERE x.a = z.a AND z.b = y.b table order is x then z then y In the preceding example, x is the outermost table, and z is domin ant over y. Example: SELECT ... FROM x, y, OUTER z WHERE x.a = y.a AND y.b = z.b table order is x then y then z or y then x then z In the preceding example, the optimizer gives both table y and x priority over z, the subservient table. Since x and y are at the same level in the FROM list, the optimizer must apply additional criteria to order the tables. With similar exception, the first criterion is normally sufficient to order the tables involved in an outer join. The term join, as used in the remainder of this article, therefore refers to a simple join rather than to an outer join. Criterion 2: Join Columns When joining tables, it is most efficient to use indexes. (If there are no indexes to use, the optimizer creates a temporary index as discussed later in this section.) Thus the optimizer uses indexes, as well as other criteria, to order the query joins. Having determined an efficient order for RDSQL to perform the joins, the optimizer applies the same or similar criteria to order the tables. - If only one of the columns involved in a join is indexed, the optimizer gives priority to the table with the non-indexed join column. This allows RDSQL to use the indexed column to perform the join. Example: (assumes x.a is indexed, but y.a is not) SELECT ...