To this point, we've talked about general tuning of search conditions. Now we'll look at how you can improve your code using specific SQL operators.
When everything else is equal, DBMSs will evaluate a series of ANDed expressions from left to right (except Oracle, which evaluates from right to left when the cost-based optimizer is operating). No rule says they mustthat's just what they do. You can take advantage of this behavior by putting the least likely expression first orif both expressions are equally likelyputting the least complex expression first. Then, if the first expression is false , the DBMS won't bother to evaluate the second expression. So, for example (unless you're using Oracle), you should transform:
... WHERE column1 = 'A' AND column2 = 'B'
... WHERE column2 = 'B' AND column1 = 'A' GAIN: 6/7 assuming column2 = 'B' is less likely
Oracle with the rule-based optimizer shows a gain, but don't do this for Oracle running the cost-based optimizer. The gain shown is for only seven DBMSs.
The gain shown represents an extreme case with this example. In our sample database column2 = 'B' is always false , column1 = 'A' is always true , and there are no indexes. With other scenarios the gain is less and can be 0/8. It's never less than zero though, so reordering ANDed expressions is a highly recommended optimization. Rule-based optimizers will transpose two expressions if they have different point counts.
When you're writing expressions with OR, put the most likely expression at the left. That's the exact reverse of the advice for AND, because an OR causes further tests if the first expression is false , while AND causes further tests if the first expression is true . So, do transform Expression #1 to Expression #2:
Expression #1: ... WHERE column2 = 'B' OR column1 = 'A' Expression #2: ... WHERE column1 = 'A' OR column2 = 'B' GAIN: 4/7 assuming column1 = 'A' is most likely
Oracle with the rule-based optimizer shows no change, but don't do this for Oracle running the cost-based optimizer. The gain shown is for only seven DBMSs.
Microsoft specifically recommends this transform. Once again, Oracle users should ignore this advice because Oracle evaluates from right to left when the cost-based optimizer is operating.
ORs are also faster if all columns are the same, because that reduces the number of columns and indexes that the DBMS has to read. Therefore, in a long series of ORs, expressions for the same column should be together. For example, you should transform Expression #1 to Expression #2:
Expression #1: ... WHERE column1 = 1 OR column2 = 3 OR column1 = 2 Expression #2: ... WHERE column1 = 1 OR column1 = 2 OR column2 = 3 GAIN: 1/8
AND Plus OR
The Distributive Law states that:
A AND (B OR C) is the same thing as (A AND B) OR (A AND C)
Suppose you have the table shown in Table 2-3, on which you must execute a query where the ANDs come first:
SELECT * FROM Table1 WHERE (column1 = 1 AND column2 = 'A') OR (column1 = 1 AND column2 = 'B')
Table 2-3. Table for an AND Plus OR Query
When the DBMS does index lookups in the order of the query, it might follow these steps:
Now let's transpose the query using the Distributive Law, in reverse:
SELECT * FROM Table1 WHERE column1 = 1 AND (column2 = 'A' OR column2 = 'B') GAIN: 2/8
Doing lookups in the new order, the DBMS might follow these steps:
This test gave us a gain for only two of the Big Eight. The other DBMSs tend to apply the Distributive Law themselves , so that they will always be working with the same, canonical query. Nevertheless, the evidence shows that, for simple search conditions, you're better off with this construct:
A AND (B OR C)
than with this one:
(A AND B) OR (A AND C)
When you're joining, however, it's a different matter; see Chapter 5, "Joins."
Transform a NOT expression to something more readable. A simple condition can be transformed by reversing the comparison operator, for example:
... WHERE NOT (column1 > 5)
... WHERE column1 <= 5
A more complex condition requires more caution, but you can apply DeMorgan's Theorem, which states:
NOT (A AND B) = (NOT A) OR (NOT B)
NOT (A OR B) = (NOT A) AND (NOT B)
Thus, for example, this search condition:
... WHERE NOT (column1 > 5 OR column2 = 7)
... WHERE column1 <= 5 AND column2 <> 7
If, after transforming, you end up with a not equals operator, expect slowness. After all, in any evenly distributed set of values, when there are more than two rows, the unequal values always outnumber the equal values. Because of this, some DBMSs won't use an index for not equals comparisons. But they will use an index for greater than and for less thanso you can transform this type of condition:
... WHERE NOT (bloodtype = 'O')
... WHERE bloodtype < 'O' OR bloodtype > 'O' GAIN: 3/8
The gain for this example is 3/8 if almost everyone has blood type O, as in the original North American population. But it's the other way around if most people have a different blood typeso do this transform only if you know how values are distributed and if a change to the distribution is unlikely . (If the DBMS keeps statistics, it knows this and will override you.)
Many people think that there is no difference between these two conditions because they both return the same result set:
Condition #1: ... WHERE column1 = 5 OR column1 = 6 Condition #2: ... WHERE column1 IN (5, 6) GAIN: 2/8
Those people are 0.01% wrong. With two of the Big Eight, IN is faster than OR. So transform OR to IN when you can. All the other DBMSs will just translate IN back to OR, so you won't lose anything.
When an IN operator has a dense series of integers, it's better to ask "what is out" rather than "what is in." Thus, this condition:
... WHERE column1 IN (1, 3, 4, 5)
should be transformed to:
... WHERE column1 BETWEEN 1 AND 5 AND column1 <> 2 GAIN: 7/8
Similar gains can happen when a series can be represented by an arithmetic expression.
Most DBMSs will use an index for a LIKE pattern if it starts with a real character but will avoid an index for a LIKE pattern that starts with a wildcard (either % or _ ). The only DBMSs that never use indexes for LIKE are Pick and mSQL (on TEXT fields). For example, if the search condition is:
... WHERE column1 LIKE 'C_F%'
DBMSs will resolve it by finding all index keys that start with C and then filtering those that contain F in the third position. In other words, you don't need to transform this search condition:
... WHERE column1 LIKE 'C_F%'
to this one:
... WHERE column1 >= 'C' AND column1 < 'D' AND column1 LIKE 'C_F%' GAIN: -5/8
(In fact, with IBM, Informix, Microsoft, Oracle, and Sybase, the transformed expression is actually slower!)
If you want to speed up LIKE with a parameter ( LIKE ?) and you know the pattern starts with a character, do the transform yourself. Here's how:
... WHERE column1 LIKE ?
... WHERE column1 > SUBSTRING(? FROM 1 FOR 1) AND column1 LIKE ? GAIN: 4/8
Another tempting transform of LIKE with a parameter is to use the equals operator instead of LIKE if the parameter does not contain a wildcard. Surprisingly, this can actually helpfor example, you can transform this condition:
... WHERE column1 LIKE 'ABC'
... WHERE column1 = 'ABC' GAIN: 5/8
The trap here is that LIKE 'A' and = 'A' are not precisely the same conditions. In standard SQL, a LIKE comparison takes trailing spaces into account, while an equals comparison ignores trailing spaces. Furthermore, LIKE and equals don't necessarily use the same collations by default. So don't do the transform on VARCHAR columns, and be sure to force the same collation if necessary.
If a column is only two or three characters long, you might be tempted to use SUBSTRING instead of LIKE, butbecause functions on columns are badLIKE will always beat multiple SUBSTRINGs. That is, you should transform Expression #1 to Expression #2:
Expression #1: ... WHERE SUBSTRING(column1 FROM 1 FOR 1) = 'F' OR SUBSTRING(column1 FROM 2 FOR 1) = 'F' OR SUBSTRING(column1 FROM 3 FOR 1) = 'F' Expression #2: ...WHERE column1 LIKE '%F%' GAIN: 5/6
Neither Ingres nor InterBase support SUBSTRING; the gain shown is for only six DBMSs. IBM and Oracle call the SUBSTRING function SUBSTR. Informix puts the substring parameters inside square brackets.
In the near future, some types of LIKE search will become obsolete because full-text indexes will become more common.
If two expressions you're joining with OR are on columns defined as CHAR or VARCHAR, a new SQL:1999 operator might be faster than ORthe SIMILAR operator. If you haven't heard of SIMILAR yet, and you're not familiar with the grep utility in Unix, here's a short summary.
The basic SIMILAR syntax is:
... <string> SIMILAR TO <'pattern'>
For SIMILAR, string is usually either the name of a column or a column expression. You can put these wildcards inside the pattern:
Thus, for example, this search condition:
... WHERE column1 SIMILAR TO '[A-F][AEK]_'
will be true for both these strings:
and will be false for these strings:
Because SIMILAR allows OR logic in the pattern, you sometimes won't need OR. For example, you could transform Expression #1 to Expression #2:
Expression #1: ... WHERE column1 = 'A' OR column1 = 'B' OR column1 = 'K' Expression #2: ... WHERE column1 SIMILAR TO '[ABK]' GAIN: 1/1
Informix uses MATCHES instead of SIMILAR and supports different pattern wildcards for this operator; the gain shown is for only one DBMS.Both Microsoft and Sybase support some of the SIMILAR pattern wild-cards with LIKE, but they often return the wrong result. No other DBMS supports SIMILAR in any fashion.
Only Informix provides support for a SIMILAR-type operator. Until it's commonly supported, add a conditional statement to your code after using SIMILAR, such as:
IF (the DBMS returns a syntax error) THEN (try the old way with OR)
In SQL, a union of two tables is the set of distinct data values that is found in either tablethat is, UNION returns nonduplicate rows from two or more queries. This can be a great way to merge data. But is it the best way? To test this, we ran two different SELECT statements, Query #1 and Query #2:
Query #1 SELECT * FROM Table1 WHERE column1 = 5 UNION SELECT * FROM Table1 WHERE column2 = 5 Query #2 SELECT DISTINCT * FROM Table1 WHERE column1 = 5 OR column2 = 5 GAIN: 7/7
MySQL doesn't support UNION. The gain shown is for only seven DBMSs.
In our tests, neither column1 nor column2 were indexed. Note that Query #1 is longer, uses a relatively rare SQL construct, andwith some SQL packages, at leastis illegal as part of a CREATE VIEW statement. If Query #2 always ran faster, as it does in this example, we could recommend that Query #1 always be transformed to Query #2. However, in one case doing so might actually result in slower execution with some DBMSs. To see why, we need to consider two optimizer flaws.
The first flaw is that many optimizers optimize only within a single WHERE clause in a single SELECT statement. So the two SELECTs in Query #1 are really both performed. First the optimizer finds all the rows where the condition column1 = 5 is true , then it finds all the rows where column2 = 5 in a separate passthat is, it scans the table twice! (A table scan is a search of an entire table, row by row.) Therefore, if column1 is not indexed, Query #1 should take precisely twice as long to perform as Query #2.
If column1 is indexed, the double search still occurs, but an uncommon optimizer flaw, seen in some DBMSs, more than makes up for this. When these optimizers see that a search condition contains OR, they refuse to use indexes at all; so in this instance, and only in this instance, UNION outperforms OR. This is a narrow enough set of circumstances that our advice still is to use OR rather than UNION when the columns in question are not indexed.
Any A AND NOT B expression can be transformed with EXCEPT. Here's an exampleQuery #1 transforms to Query #2:
Query #1: SELECT * FROM Table1 WHERE column1 = 7 AND NOT column2 = 8 Query #2: SELECT * FROM Table1 WHERE column1 = 7 EXCEPT SELECT * FROM Table1 WHERE column2 = 8 GAIN: -2/3
Informix, Ingres, InterBase, Microsoft, and MySQL don't support EXCEPT. The gain shown is for only three DBMSs. Oracle and Sybase call EXCEPT the MINUS operator.
The negative gain shows that doing the transform is a bad idea! Coupled with the fact that support for EXCEPT is rare, our advice isUse AND NOT; avoid EXCEPT.
Although there are many ways to transform ANDed expressions using INTERSECT, we found none that resulted in any gain. Because many DBMSs won't support INTERSECT anyway, we won't provide details.
Informix, Ingres, InterBase, Microsoft, MySQL, and Sybase don't support INTERSECT.
Suppose a search condition has more than one reference to a slow routine:
... WHERE slow_function(column1) = 3 OR slow_function(column1) = 5
To avoid executing slow_function twice, transform the condition with CASE:
... WHERE 1 = CASE slow_function(column1) WHEN 3 THEN 1 WHEN 5 THEN 1 END GAIN: 4/7
InterBase doesn't support CASE. The gain shown is for only seven DBMSs.
It's useful to bury a search condition in a CASE expression if the result is a reduction in the number of references.
CASE expressions are also useful for final filtering in the select list . (The select list is everything between the keyword SELECT and the keyword FROM in a SELECT statement.)
IBM and Informix process the select list at fetch timethat is, at the time you fetch the rows in the result set. The rest of the Big Eight process the select list when you execute the SELECTthat is, at the time the DBMS evaluates the SELECT to determine the rows that belong in the result set.
The Bottom Line: Specific Tuning
When everything else is equal, DBMSs will evaluate a series of ANDed expressions from left to right (except Oracle, which evaluates from right to left). Take advantage of this behavior by putting the least likely expression first. If two expressions are equally likely, put the least complex expression first.
Put the most likely expression first in a series of ORed expressionsunless you're using Oracle.
Put the same columns together in a series of ORed expressions.
Apply the Distributive Law to write simple search conditions with the form A AND (B ORC) rather than (A AND B) OR (A AND C) .
Transform a NOT expression to something more readable. For a simple condition, reverse the comparison operator. For a more complex condition, apply DeMorgan's Theorem.
When you know the distribution of a set of values, you can speed things up by transforming not equals searches to greater than and less than searches.
Transform a series of ORed expressions on the same column to IN.
When IN has a dense series of integers, ask "what is out" rather than "what is in."
Most DBMSs will use an index for a LIKE pattern that starts with a real character but will avoid an index for a pattern that starts with a wildcard. Don't transform LIKE conditions to comparisons with >= , < , and so on unless the LIKE pattern is a parameter, for example, LIKE ? .
Speed up LIKE ? , where the parameter does not contain a wildcard, by substituting the equals operator for LIKE as long as trailing spaces and different collations aren't a factor.
LIKE will always beat multiple SUBSTRINGs, so don't transform.
Transform UNION to OR.
Put a search condition in a CASE expression if the result is a reduction in the number of references.
Use CASE expressions for final filtering in the select list.