SQL Performance Tuning: Simple "Searches"

This chapter is from the book

SQL Performance Tuning

Learn More Buy

This chapter is from the book

This chapter is from the book 

SQL Performance Tuning

Learn More Buy

Specific Tuning

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.

AND

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 must—that's just what they do. You can take advantage of this behavior by putting the least likely expression first or—if both expressions are equally likely—putting 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'

to:

 ... WHERE column2 = 'B' AND column1 = 'A'
 GAIN: 6/7 assuming column2 = 'B' is less likely

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.

OR

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
 

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:

• Index lookup: column1=1. Result set = {row 3}

• Index lookup: column2='A'. Result set = {row 1}

• AND to merge the result sets. Result set = {}

• Index lookup: column1=1. Result set = {row 3}

• Index lookup: column2='A'. Result set = {row 1}

• AND to merge the result sets. Result set = {}

• OR to merge the result sets. Result set = {}

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:

• Index lookup: column2='A'. Result set = {row 1}

• Index lookup: column2='B'. Result set = {row 2}

• OR to merge the result sets. Result set = {row 1, 2}

• Index lookup: column1=1. Result set = {row 3}

• AND to merge the result sets. Result set = {}

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

NOT

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)

transforms to:

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

and

 NOT (A OR B) = (NOT A) AND (NOT B)

Thus, for example, this search condition:

 ... WHERE NOT (column1 > 5 OR column2 = 7)

transforms to:

 ... 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 than—so you can transform this type of condition:

 ... WHERE NOT (bloodtype = 'O')

to:

 ... 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 type—so 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.)

IN

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.

LIKE

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 ?

transforms to:

 ... 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 help—for example, you can transform this condition:

 ... WHERE column1 LIKE 'ABC'

into:

 ... 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, but—because functions on columns are bad—LIKE 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

In the near future, some types of LIKE search will become obsolete because full-text indexes will become more common.

SIMILAR

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 OR—the 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:

• % or _ means the same as the wildcards used with LIKE.

• * or + means "the preceding repeats indefinitely"—zero to infinity times in the first case, one to infinity in the second.

• [A-F] means any character between A and F.

• [AEK] means either A or E or K.

• [^AEK] means anything other than A or E or K.

• [:ALPHA:] means anything that is a simple Latin letter. Other options for this enumeration include [:UPPER:] (for uppercase letters only), [:LOWER:] (for lowercase letters only), [:DIGIT:] (for any digit from 0 to 9), and [:ALNUM:] (for any Latin letter or digit).

• | and || mean the logical OR of two expressions, and concatenation, respectively.

Thus, for example, this search condition:

 ... WHERE column1 SIMILAR TO '[A-F][AEK]_'

will be true for both these strings:

 DEN
 FAB

and will be false for these strings:

 GIB
 AKRON

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

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)

UNION

In SQL, a union of two tables is the set of distinct data values that is found in either table—that 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

In our tests, neither column1 nor column2 were indexed. Note that Query #1 is longer, uses a relatively rare SQL construct, and—with some SQL packages, at least—is 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 pass—that 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.

EXCEPT

Any A AND NOT B expression can be transformed with EXCEPT. Here's an example—Query #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

The negative gain shows that doing the transform is a bad idea! Coupled with the fact that support for EXCEPT is rare, our advice is—Use AND NOT; avoid EXCEPT.

INTERSECT

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.

CASE

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

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

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 expressions—unless 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.