Figure 7-1 illustrates the first case, in which a single foreign key joins to primary keys in two different master tables.

Figure 7-1. Case 1 for a cyclic query diagram

In this case, you can infer that the SQL itself looks something like this:

SELECT ... 
FROM ...T1, ... T2, ... T3, ... 
WHERE ... T1.FKey1=T2.PKey2 
  AND T1.FKey1=T3.PKey3 
  AND T2.PKey2=T3.PKey3 ...

Here, I have named the single foreign key that points to both tables from T1 FKey1, and I have named the primary keys of T2 and T3 PKey2 and PKey3, respectively. With all three of these joins explicit in the SQL, the cyclic links are obvious, but note that you could have left any one of these links out of the query, and transitivity (if a=b and b=c, then a=c) would imply the missing join condition. If one of these joins were left out, you might diagram the same query in any of the three forms shown in Figure 7-2.

Figure 7-2. The same cyclic query, missing one of the three transitive join conditions

Note that in versions A and B of this query you can infer the missing arrow from the fact that the link between T2 and T3 has an arrowhead on both ends, and an arrow at both ends implies a one-to-one join. Version C, on the other hand, looks exactly like a plain-vanilla join tree, and you would not realize that it had cyclic joins unless you happened to notice that T1 used the same foreign key to join to both T2 and T3.

When you have one-to-one tables, cyclic joins like the one in Figure 7-1 are common. These are not a functional problem, though I will later describe issues to consider whenever you encounter a one-to-one join. Instead of being a problem, you can see such joins as an opportunity. If you have already reached T1, it is useful to have the choice of either T2 or T3 next, since either might have the better filter ratio or provide access to good filters lower down the tree. If you reach either T2 or T3 in the join order before you reach T1, it is also useful to have the option to join one-to-one to the other (from T2 to T3, or from T3 to T2). This enables you to reach any filter the other table might have, without joining to T1 first. Without the horizontal link, you could join from T2 to T3 or vice versa, only through T1, at likely higher cost.

Some optimizers are written cleverly enough to use transitivity to fill in a missing join condition even if it is left out and take advantage of the extra degrees of freedom that are provided in the join order. However, to be safe, it is best to make all three joins explicit if you notice that two joins imply a third by transitivity. At the least, you should make explicit in your SQL statement any join you need for the optimum plan you find.

There exists a special case in which the one-to-one tables shown as T2 and T3 are the same table! In this case, each row from T1 joins to the same row of T2 twice, a clear inefficiency. The obvious cause, having the same table name repeated twice in the FROM clause and aliased to both T2 and T3, is unlikely, precisely because it is too obvious to go unnoticed. However, a join to the same table twice can happen more subtly and be missed in code review. For example, it can happen if a synonym or simple view hides the true identity of the underlying table behind at least one of the aliases in the query. Either way, you are clearly better off eliminating the redundant table reference from the query and shifting all column references and further downward joins to the remaining alias.

Figure 7-3 shows the second major case with cyclic joins. Here, identical foreign keys in T1 and T2 point to the same primary key value in T3.

Figure 7-3. A cyclic join that implies denormalization

This time, the SQL looks like this:

SELECT ... 
FROM ...T1, ... T2, ... T3, ... 
WHERE ... T1.FKey1=T2.PKey2 
  AND T1.FKey2=T3.PKey3 
  AND T2.FKey2=T3.PKey3 ...

In this SQL statement, I name the foreign keys that point from T1 to T2 and T3 FKey1 and FKey2, respectively. By transitivity, the foreign-key column T2.FKey2 has the same value as T1.FKey, since both join to T3.PKey3. I name the primary keys of T2 and T3 PKey2 and PKey3, respectively. The most likely explanation for T1 and T2 joining to the same table, T3, on its full primary key is that T1 and T2 contain redundant foreign keys to that table. In this scenario, the FKey2 column in the detail table T1 has denormalized data from its master table T2. This data always matches the FKey2 value in the matching master row of T2.

Chapter 10 covers the pros and cons of denormalization in cases like this. Briefly, if the denormalization is justifiable, it is possible that the extra link in the query diagram will buy you access to a better execution plan. However, it is more likely that the denormalization is a mistake, with more cost and risk than benefit. Eliminating the denormalization would eliminate the foreign key FKey2 in T1, thus eliminating the link from T1 to T3 and making the query diagram a tree.

Figure 7-4 shows the third major case with cyclic joins. This time, you have normal downward arrows from T1 to T2 and T3, but you also have some third, unusual join condition between T2 and T3 that does not involve the primary key of either table.

Figure 7-4. A cyclic join with a two-node filter

The SQL behind Figure 7-4 looks like this:

SELECT ... 
FROM ...T1, ... T2, ... T3,... 
WHERE ... T1.FKey1=T2.PKey2 
  AND T1.FKey2=T3.PKey3 
  AND T2.Col2<IsSomeHowComparedTo>T3.Col3 ...

For example, if T1 were on the Orders table, having joins to Customers, T2, and Salespersons, T3, a query might request orders in which customers are assigned to different regions than the salesperson responsible for the order:

SELECT ... 
FROM Orders T1, Customers T2, Salespersons T3
WHERE T1.Customer_ID=T2.Customer_ID
  AND T1.Salesperson_ID=T3.Salesperson_ID
  AND T2.Region_ID!=T3.Region_ID

Here, the condition T2.Region_ID!=T3.Region_ID is technically a join, but it is better to view it as a filter condition that happens to require rows from two different tables before it can be applied. If you ignore the unusual, arrow-free link between T2 and T3, you will reach T1 before you can apply the two-node filter on Region_ID. The only allowed join orders, which avoid directly following the unusual join between T2 and T3, are:

Any join order other than these four (such as (T2, T3, T1)) would create a disastrous many-to-many explosion of rows after reaching the second table, almost a Cartesian product of the rows in T2 and T3. All of these join orders reach T1 by the first or second table, before you have both T2 and T3. These join orders therefore follow only the two ordinary many-to-one joins between the detail table T1 and its master tables T2 and T3.

The unusual, two-node filter acts like no filter at all when you reach the first of the two filtered tables, then it acts like an ordinary filter, discarding some fraction of rows, when you reach the second of the two tables. Viewed in this way, handling this case is fairly straightforward: consider the filter to be nonexistent (or at least not directly accessible) until you happen to join to one of the filtered tables as a matter of course. However, as soon as you have joined to either end of the two-node filter, the other node suddenly acquires a better filter ratio and becomes more attractive to join to next.

Figure 7-5 shows a specific example with a two-node filter, in which the fraction of rows from the ordinary joins from T1 to T2 and T3 that meet the additional two-node filter condition is 0.2. In this case, you would initially choose a join order independent of the existence of the two-node filter, following only ordinary join links. However, as soon as you happened to join to either T2 or T3, the other would have its former filter ratio (1.0 for T2 and 0.5 for T3) multiplied by 0.2, becoming much more attractive for future joins.

Figure 7-5. A two-node filter with explicit two-node filter ratio

Follow the normal procedure to tune Figure 7-5, ignoring the two-node filter between T2 and T3 until you reach one of those tables as a matter of course. The driving table is T1, followed by T4, the table with the best ordinary filter downstream of T1. T3 has the next best ordinary filter available, with the filter ratio 0.5, so it follows next in the join order. Now, you have a choice between T2 and T5 next in the join order, but T2 has at last seen the two-node filter activated, since you just reached T3, so it has a more effective filter ratio, at 0.2, than T5 has, and you join to T2 next. The final best join order is (T1, T4, T3, T2, T5).

Finally, Figure 7-6 shows the fourth major case with cyclic joins. Here are two unusual joins to T3, neither using the whole primary key of that table nor the primary keys of the tables on the other ends of these joins. If such cases of failing to join to the whole primary key on at least one end of each join are “wrongs,” then Case 4 is usually a case in which two wrongs make a right!

Figure 7-6. A cyclic join with two unusual joins

In a situation such as that shown in Figure 7-6, the SQL typically looks like this:

SELECT ... 
FROM ...T1, ... T2, ... T3, ... 
WHERE ... T1.FKey1=T2.PKey2 
  AND T1.FKey2=T3.PKeyColumn1 
  AND T2.FKey3=T3.PkeyColumn2 ...

Such SQL typically arises when you have a two-part primary key on T3 and the two-part foreign key is somehow distributed over two tables in a master-detail relationship.

A concrete example will clarify this case. Consider data-dictionary tables called Tables, Indexes, Table_Columns, and Index_Columns. You might choose a two-part primary key for Table_Columns of (Table_ID, Column_Number), where Column_Number designates the place that table column holds in the natural column order of the table—1 for the first column, 2 for the second, and so on. The Indexes table would have a foreign key to Tables on the Table_ID column, and the Index_Columns table would also have a two-part primary key, (Index_ID, Column_Number). The Column_Number value in the Index_Columns has the same meaning as Column_Number in Table_Columns: the place the column holds in the natural order of table columns (not its place in the index order, which is Index_Position). If you knew the name of an index and wished to know the list of column names that make up the index in order of Index_Position, you might query:

SELECT TC.Column_Name 
FROM Indexes Ind, Index_Columns IC, Table_Columns TC
WHERE Ind.Index_Name='EMPLOYEES_X1'
  AND Ind.Index_ID=IC.Index_ID
  AND Ind.Table_ID=TC.Table_ID
  AND IC.Column_Number=TC.Column_Number
ORDER BY IC.Index_Position ASC

If the condition on Index_Name had a filter ratio of 0.0002, the query diagram, leaving off the join ratios, would look like Figure 7-7.

Figure 7-7. A concrete example of the fourth type of cyclic join

Here, two wrongs (i.e., two joins that fail to find a full primary key on either side) combine to make a right when you consider the joins to TC together, because combined they reach the full primary key of that table. You can transform the diagram of this uncommon case generically, as in Figure 7-8.

Figure 7-8. Combining multipart joins from foreign keys distributed across two tables

If you follow the rule of thumb to join either to or from full primary keys, the best join order for Figure 7-7 becomes clear. Drive from the filter on Ind and follow the upward link to IC. Only then, after reaching both parts of the primary key to TC, should you join to TC. This is, in fact, the best execution plan for the example. The rule of thumb in these cases is only to follow these unusual links into a multipart primary key once the database has reached all the upward nodes necessary to use the full primary key.

The following list summarizes the way in which you should treat each of the four cyclic join types just described:

Most often, the appearance of a second root node points to some missing join condition that would convert one of the root nodes to a master node. Figure 7-11 shows this transformation, where the join from Master to Root1 has been converted to a one-to-one join by the addition (or recognition) of some extra condition on Root1 (renamed R1) that ensures that the database will find at most one row in R1 for every row in Master. This is particularly likely when R1 contains time-interval detail data (such as a varying tax rate) that matches a master record (such as taxing entity) and the addition of a date condition (such as requesting the current tax rate) makes the join one-to-one.

Figure 7-11. Repairing a query with multiple root nodes

Often, the condition that makes the join one-to-one is already there, and you find a combination of a many-to-one join and an apparent filter that just cancels the detail join ratio.

Alternatively, the condition that makes the join one-to-one might be missing from the query, especially if development happens in a test system where the one-to-many relationship is hidden.

Whether the condition that makes the join one-to-one was missing or was just not recognized as being connected with the join, you should include the condition and recognize it as part of the join, not as an independent filter condition. Such a missing join condition is particularly likely when you find that the foreign key for one of the root tables pointing downward to a shared master table is also part of the multipart primary key of that root table.

Figure 7-12 shows another solution to the multiroot-query-diagram problem. This solution is akin to running explicitly separate queries in the disconnected query diagram (discussed earlier), breaking up the Cartesian product and replacing it with the two separate sets. In the example, this replaces a query that would return 150 rows per Master row with two queries that, combined, return 35 rows per Master row. Whenever you have one-to-many relationships from a master table to two different detail root tables, you can get precisely the same underlying data, with far fewer rows read and with separate queries, as illustrated. Since the result takes an altered form, you will also need to change the underlying application logic to handle the new form.

Figure 7-12. Resolving the Cartesian product with separate queries

Figure 7-13 shows a case of multiple roots in which performance of the query, unaltered, is not a problem. Since the detail join ratio from Master to Root1 is 0.5, you see no Cartesian explosion of rows when you combine matching Root1 with Root2 records for the average matching Master record. You can treat Root1 as if it were a downward join, even favoring it as if it had a filter ratio enhanced by 0.5 for the filtering join, following the special-case rules in Chapter 6 for detail join ratios less than 1.0.

Figure 7-13. A Cartesian product with a low detail join ratio

Although this query is no problem for tuning, it might still be incorrect. The one-to-zero or one-to-many join from Master to Root1 evidently usually finds either the one-to-zero or the one-to-one case, leading to a well-behaved Cartesian product. However, as long as the join is ever one-to-many, you must consider that the result might return a Cartesian product with repeats for a given row of Root2. Since this case is rare, it is all too likely that the query was actually designed and tested to return results that map one-to-one with rows from Root2, and the application might not even work in the other rare case.

For example, if the application will alter Root2 data after reading it out with this query and attempt to post the alterations back to the database, the application must consider which copy of a repeated Root2 row should get posted back to the database. Should the application warn an end user that it attempted to post inconsistent copies? If the application aggregates Root2 data from the query, does it avoid adding data from repeated Root2 rows?

One solution to the functional problem that Figure 7-13 represents is already shown in Figure 7-12: just break up the query into two queries. Another solution, surprisingly often, is to isolate the branch to Root1 into a subquery, usually with an EXISTS condition. This solution works especially easily if the original query did not select columns from Root1 (or any of the tables joined below it through hidden gray links in Figure 7-13). In this relatively common special case, you are really interested only in whether a matching row in Root1 exists and perhaps matches some filter conditions, not in the contents of that row or the number of matches (beyond the first) that might exist. Later in this chapter, you will see how to diagram and tune queries with subqueries like this.

Figure 7-15 shows a typical one-to-one join embedded in a larger query. While many-to-many joins have detail join ratios on both ends, one-to-one joins have master join ratios on both ends. The master join ratios in the example show that the join between T1 and T2 is really one-to-zero or one-to-one; the one-to-zero case happens for 30% of the rows in T1.

Figure 7-15. A typical one-to-one join

Since this is an inner join, the one-to-zero cases between T1 and T2 make up a hidden join filter, which you should handle as described at the end of Chapter 6. Also note that this might be a case of a hidden cyclic join, as often happens when a master table joins one-to-one with another table. If you have a detail table above T1, as implied by the gray link upward, and if that detail table joins to T1 by the same unique key as used for the join to T2, then you have, by transitivity, an implied join from the detail table to T2. Figure 7-16 shows this implied link in gray. Refer back to cyclic joins earlier in this chapter for how to handle this case.

Figure 7-16. An implied link making a cyclic join

Whether or not you have a cyclic join, though, you might have an opportunity to improve the database design. The case in Figure 7-16 implies a set of entities that map one-to-one with T1 and a subset of those same entities that map one-to-one with T2, with T2 built out of T1’s primary key and columns that apply only to that subset. In this case, there is no compelling need to have two tables at all; just add the extra columns to T1 and leave them null for members of the larger set that do not belong to the subset! Occasionally, there are good reasons why development prefers a two-table design for convenience in a situation like this. However, from the perspective of tuning, combining these two comparably sized tables is almost always helpful, so at least give it some thought if you have any chance to influence the database design.

Figure 7-17 shows an especially compelling case for combining the tables into a single table, when possible. Here, the master join ratios are each exactly 1.0, and the relationship between the tables is exactly one-to-one. Both tables, therefore, map to the same set of entities, and the join is just needless expense compared to using a combined table.

Figure 7-17. A precise one-to-one join

The only reason, from a performance perspective, to separate these tables is if queries almost always need just the data from one or the other and rarely need to do the join. The most common example of this is when one of the tables has rarely needed data, compared to the other. In that case, especially if the rarely needed data takes up a lot of space per row and the tables are large, you might find that the better compactness of the commonly queried table, resulting in a better cache-hit ratio, will (barely) justify the cost of the rarely needed joins. Even from a functional or development perspective, it is likely that the coding costs of adding and deleting rows for both tables at once—and, sometimes, updating both at once—are high. You might prefer to maintain a single, combined table. Usually, when you see an exact one-to-one join, it is a result of some bolted-on new functionality that requires new columns for existing entities, and some imagined or real development constraint prevented altering the original table. When possible, it is best to solve the problem by eliminating that constraint.

At the other end of the spectrum, you have the case shown in Figure 7-18, a one-to-zero or one-to-one join that is almost always one-to-zero. Here, the case for separating the tables is excellent. The tiny subset of entities represented by T2 might have different optimization needs than the superset represented by T1. Probably, T1 is usually queried without the join to T2, and, in these cases, it is useful that it excludes the inapplicable columns in T2 and has only the indexes that make sense for the common entities. Here, the hidden join filter represented by the small master join ratio on the T2 side of the join is excellent. It is so good, in fact, that you might choose to drive from an unfiltered full table scan of T2 and still find the best path to the rest of the data. Such an execution plan would be hard to approximate, without creating otherwise useless indexes, if you combined these tables into a single table.

Figure 7-18. A one-to-zero or one-to-one join between very different-sized tables

Here, the key issue is not to neglect to take into account the hidden join filter from T1 to T2, either driving from the T2 side of the query or reaching it as soon as possible to pick up the hidden filter early.

Figure 7-19 shows a rare case of a [zero or one]-to-[zero or one] join, which filters in both directions. If one-to-one joins are downhill in both directions, then [zero or one]-to-[zero or one] joins are steeply downhill in both directions. However, unless data is corrupt (i.e., one of the tables is missing data), this rare case probably implies that yet a third table exists, or should exist, representing a superset of these two overlapping sets. If you find or create such a table, the same arguments as before apply for combining it with one or both of the subset tables.

Figure 7-19. A [zero or one]-to-[zero or one] join

It helps to have agreed-upon conventions for laying out query diagrams. Such conventions aid tuning intuition by presenting key information uniformly. Single-ended arrows always point down, by convention. Figure 7-20 shows two alternatives that work well for one-to-one joins that lie below the root detail table. The first alternative emphasizes the two-headed arrow, placing neither node above the other. The second alternative emphasizes the usual downward flow of reference links from the root detail table. Either alternative works well, as long as you remember that both directions of a one-to-one join are, in the usual sense, downward.

Figure 7-20. Diagramming one-to-one joins lying under a root detail table

For this case, in which both joined tables are below the root, keep in mind that if the one-to-one tables actually share a common primary key, then the link from above into T1 could probably just as easily be to T2, by transitivity, unless it is to some alternate unique key on T1 not shared by T2. This is the implied cyclic-join case illustrated with form B in Figure 7-2.

Figure 7-21 illustrates alternate diagrams for one-to-one joins of tables that both qualify as root detail tables (i.e., they have no joins from above), where at least one of the directions of the one-to-one join shows a master join ratio less than 1.0. Again, you can emphasize the one-to-one link with a horizontal layout, or you can emphasize which table is larger (and which direction of the join is “more downhill”) by placing the node with the larger master join ratio higher. The node with the larger master join ratio represents a table with more rows in this [zero or one]-to-[zero or one] join.

Figure 7-21. Alternate diagram methods for [zero or one]-to-[zero or one] root detail tables

Figure 7-22 illustrates a case similar to Figure 7-21, but with nodes that are perfectly one-to-one (tables that always join successfully). Again, you can emphasize the equal nature of the join directions by laying the nodes out horizontally. Alternatively, you can just choose a direction that makes a more balanced-looking tree, which fits better on the page, placing the node with deeper branches at the top. The choice in this case matters least, as long as you remember that both join directions are virtually downhill, regardless of how you lay out the diagram.

Figure 7-22. Alternate diagram methods for exact one-to-one root detail tables

Consider Figure 7-23, with an outer join to a table with a filter condition. In the outer case, the case where a T1 row has no matching T2 row, the database assigns null to every T2 column in the result. Therefore, except for T2.SomeColumn IS NULL, almost any filtering condition on T2 would specifically exclude a result row that comes from the outer case of the outer join.

Figure 7-23. Outer join to a filtered node

Even conditions such as T2.Unpaid_Flag != 'Y' or NOT T2.Unpaid_Flag = 'Y', which you might expect to be true for the outer case, are not.

Since most filters on the outer table discard the outer case of an outer join, and since the whole purpose of an outer join is to preserve such cases, you need to give careful attention to any filter on an outer table. One of the following scenarios applies, and you should take the time to determine which:

WHERE ...
  AND O.Order_Type_Code=OTypeTrans.Code(+)
  AND OTypeTrans.Type(+)='ORDER_TYPE'

FROM ... Orders O ...
LEFT OUTER JOIN Code_Translations OTypeTrans
             ON O.Order_Type_Code=OTypeTrans.Code
            AND OTypeTrans.Type='ORDER_TYPE'

WHERE ...
  AND O.Order_Type_Code*=OTypeTrans.Code
  AND OTypeTrans.Type='ORDER_TYPE'

Let’s consider the first scenario in further depth. Consider the query:

SELECT ... 
FROM Employees E 
     LEFT OUTER JOIN Departments D 
                  ON E.Department_ID=D.Department_ID
WHERE D.Dept_Manager_ID IS NULL

What is the query really asking the database in this case? Semantically, this requests two rather distinct rowsets: all employees that have no department at all and all employees that have leaderless departments. It is possible that the application actually calls for just two such distinct rowsets at once, but it is more likely that the developer did not notice that such a simple query had such a complex result, and did not intend to request one of those rowsets.

Consider a slightly different example:

SELECT ... FROM Employees E 
         LEFT OUTER JOIN Departments D 
                      ON E.Department_ID=D.Department_ID
WHERE D.Department_ID IS NULL

On the surface, this might seem to be a bizarre query, because the primary key (Department_ID) of Departments cannot be null. Even if the primary key could be null, such a null key value could never successfully join to another table with a join like this (because the conditional expression NULL = NULL returns the truth value “unknown”). However, since this is an outer join, there is a reasonable interpretation of this query: “Find the employees that fail to have matching departments.” In the outer case of these outer joins, every column of Departments, including even mandatory nonnull columns, is replaced by a null, so the condition D.Department_ID IS NULL is true only in the outer case. There is a much more common and easier-to-read way to express this query:

SELECT ... 
FROM Employees E 
WHERE NOT EXISTS (SELECT * 
                  FROM Departments D 
                  WHERE E.Department_ID=D.Department_ID)

Although the NOT EXISTS form of this sort of query is more natural and easier to read and understand, the other form (preferably commented carefully with explanation) has its place in SQL tuning. The advantage of expressing the NOT EXISTS condition as an outer join followed by PrimaryKey IS NULL is that it allows more precise control of when in the execution plan the join happens and when you pick up the selectivity of that condition. Usually, NOT EXISTS conditions evaluate after all ordinary joins, at least on Oracle. This is the one example in which a filter (that is not part of the outer join) on an outer-joined table is really likely to have been deliberate and correct.

SELECT ... 
FROM Employees E, Departments D 
WHERE E.Department_ID*=D.Department_ID
  AND D.Department_ID IS NULL

Consider Figure 7-24, in which an outer join leads to an inner join.

Figure 7-24. An outer join leading to an inner join

In old-style Oracle SQL, you express such a join as follows:

SELECT ... 
FROM Table1 T1, Table2 T2, Table3 T3
WHERE T1.FKey2=T2.PKey2(+)
  AND T2.FKey3=T3.PKey3

In the outer case for the first join, the database will generate a pseudorow of T2 with all null column values, including the value of T2.FKey3. However, a null foreign key can never successfully join to another table, so that row representing the outer case will be discarded when the database attempts the inner join to T3. Therefore, the result of an outer join leading to an inner join is precisely the same result you would get with both joins being inner joins, but the result is more expensive, since the database discards the rows that fail to join later in the execution plan. This is always a mistake. If the intent is to keep the outer case, then replace the outer join to an inner join with an outer join leading to another outer join. Otherwise, use an inner join leading to an inner join.

Consider Figure 7-25, in which the midlink arrow shows the outer join that points toward the detail table.

Figure 7-25. An outer join toward a detail table

In the new-style ANSI join notation, this might look like this:

SELECT ... 
FROM Departments D 
     LEFT OUTER JOIN Employees E 
                  ON D.Department_ID=E.Department_ID

Or, in older Oracle notation:

SELECT ... 
FROM Departments D, Employees E 
WHERE D.Department_ID=E.Department_ID(+)

Or, in older SQL Server notation:

SELECT ... 
FROM Departments D, Employees E 
WHERE D.Department_ID*=E.Department_ID

In any of these, what does this query semantically ask? It asks something like: “Give me all the employees that have departments (the inner case), together with their department data, and also include data for departments that don’t happen to have employees (the outer case).” In the inner case, the result maps each row to a detail entity (an employee who belongs to a department), while in the outer case, the result maps each row to a master entity (a department that belongs to no employee). It is unlikely that such an incongruous mixture of entities would be useful and needed from a single query, so queries like this, with outer joins to detail tables, are rarely correct. The most common case of this mistake is a join to a detail table that usually offers zero or one detail per master, and that is only rarely many-to-one to the master table. Developers sometimes miss the implications of the rare many-to-one case, and it might not come up in testing.

Figure 7-26 shows an outer join to a detail table that also has a filter condition. Occasionally, two wrongs do make a right. An outer join to a detail table that also has a filter might be doubly broken, suffering from the problems described in the last two subsections. Sometimes, the filter cancels the effect of the problematic outer join, converting it functionally to an inner join. In such cases, you need to avoid removing the filter unless you also make the outer join inner.

Figure 7-26. An outer join to a filtered detail table

The most interesting case Figure 7-26 can illustrate is the case in which the filter makes sense only in the context of the outer join. This is the case in which the filter condition on T1 is true only in the outer case—for example, T1.Fkey_ID IS NULL. (Here, T1.Fkey_ID is the foreign key pointing to T2.PKey_ID in the diagrammed join.) Like the earlier example of a join-key-value IS NULL condition (on the primary key, in the earlier case), this case is equivalent to a NOT EXISTS subquery. As in the earlier example, this unusual alternative expression for the NOT EXISTS condition sometimes offers a useful additional degree of control over when in the execution plan the database performs the join and discards the rows that do not meet the condition. Since all inner-joined rows are discarded by the IS NULL condition, it avoids the usual problem of outer joins to a detail table: the mixing of distinct entities behind rows from the inner and the outer cases of the join. Two wrongs make a right!

Figure 7-27 shows my convention for diagramming a query with an EXISTS-type subquery (which might be expressed by the equivalent IN subquery). The figure is based on the earlier EXISTS subquery:

SELECT ... FROM Departments D
WHERE EXISTS (SELECT NULL 
              FROM Employees E 
              WHERE E.Department_ID=D.Department_ID)

Figure 7-27. A simple query with a subquery

For the correlation join (known as a semi-join when applied to an EXISTS-type subquery) from Departments to Employees, the diagram begins with the same join statistics shown for Figure 5-1.

Like any join, the semi-join that links the inner query to the outer query is a link with an arrowhead on any end of the join that points toward a primary key. Like any join link, it has join ratios on each end, which represent the same statistical properties the same join would have in an ordinary query. I use a midpoint arrow to point from the outer-query correlated node to the subquery correlated node. I place an E beside the midpoint arrow to show that this is a semi-join for an EXISTS or IN subquery.

In this case, as in many cases with subqueries, the subquery part of the diagram is a single node, representing a subquery without joins of its own. Less frequently, also as in this case, the outer query is a single node, representing an outer query with no joins of its own. The syntax is essentially unlimited, with the potential for multiple subqueries linked to the outer query, for subqueries with complex join skeletons of their own, and even for subqueries that point to more deeply nested subqueries of their own.

The semi-join link also requires up to two new numbers to convey properties of the subquery for purposes of choosing the best plan. Figure 7-27 shows both potential extra values that you sometimes need to choose the optimum plan for handling a subquery.

The first value, next to the E (20 in Figure 7-27) is the correlation preference ratio. The correlation preference ratio is the ratio of I/E. E is the estimated or measured runtime of the best plan that drives from the outer query to the subquery (following EXISTS logic). I is the estimated or measured runtime of the best plan that drives from the inner query to the outer query (following IN logic). You can always measure this ratio directly by timing both forms, and doing so is usually not much trouble, unless you have many subqueries combined. Soon I will explain some rules of thumb to estimate I/E more or less accurately, and even a rough estimate is adequate to choose a plan when, as is common, the value is either much less than 1.0 or much greater than 1.0. When the correlation preference ratio is greater than 1.0, choose a correlated subquery with an EXISTS condition and a plan that drives from the outer query to the subquery.

The other new value is the subquery adjusted filter ratio (0.8 in Figure 7-27), next to the detail join ratio. This is an estimated value that helps you choose the best point in the join order to test the subquery condition. This applies only to queries that should begin with the outer query, so exclude it from any semi-join link (with a correlation preference ratio less than 1.0) that you convert to the driving query in the plan.

Before I explain how to calculate the correlation preference ratio and the subquery adjusted filter ratios, let’s consider when you even need them. Figure 7-28 shows a partial query diagram for an EXISTS-type subquery, with the root detail table of the subquery on the primary-key end of the semi-join.

Figure 7-28. A semi-join to a primary key

Here, the semi-join is functionally no different than an ordinary join, because the query will never find more than a single match from table M for any given row from the outer query.

Since the semi-join is functionally no different than an ordinary join, you can actually buy greater degrees of freedom in the execution plan by explicitly eliminating the EXISTS condition and merging the subquery into the outer query. For example, consider this query:

SELECT<Columns from outer query only>
FROM Order_Details OD, Products P, Shipments S, 
     Addresses A, Code_Translations ODT
WHERE OD.Product_ID = P.Product_ID
  AND P.Unit_Cost > 100
  AND OD.Shipment_ID = S.Shipment_ID
  AND S.Address_ID = A.Address_ID(+)
  AND OD.Status_Code = ODT.Code
  AND ODT.Code_Type = 'Order_Detail_Status'
  AND S.Shipment_Date > :now - 1
  AND EXISTS (SELECT null
              FROM Orders O, Customers C, Code_Translations OT, 
                   Customer_Types CT
              WHERE C.Customer_Type_ID = CT.Customer_Type_ID
                AND CT.Text = 'Government'
                AND OD.Order_ID = O.Order_ID
                AND O.Customer_ID = C.Customer_ID
                AND O.Status_Code = OT.Code
                AND O.Completed_Flag = 'N'
                AND OT.Code_Type = 'ORDER_STATUS'
                AND OT.Text != 'Canceled')
ORDER BY <Columns from outer query only>

Using the new semi-join notation, you can diagram this as shown in Figure 7-29.

Figure 7-29. A complex example of a semi-join with a correlation to the primary key of the subquery root detail table

If you simply rewrite this query to move the table joins and conditions in the subquery into the outer query, you have a functionally identical query, since the semi-join is toward the primary key and the subquery is one-to-one with its root detail table:

SELECT<Columns from the original outer query only>
FROM Order_Details OD, Products P, Shipments S, 
     Addresses A, Code_Translations ODT,
     Orders O, Customers C, Code_Translations OT, Customer_Types CT
WHERE OD.Product_Id = P.Product_Id
  AND P.Unit_Cost > 100
  AND OD.Shipment_Id = S.Shipment_Id
  AND S.Address_Id = A.Address_Id(+)
  AND OD.Status_Code = ODT.Code
  AND ODT.Code_Type = 'Order_Detail_Status'
  AND S.Shipment_Date > :now - 1
                AND C.Customer_Type_Id = CT.Customer_Type_Id
                AND CT.Text = 'Government'
                AND OD.Order_Id = O.Order_Id
                AND O.Customer_Id = C.Customer_Id
                AND O.Status_Code = OT.Code
                AND O.Completed_Flag = 'N'
                AND OT.Code_Type = 'ORDER_STATUS'
                AND OT.Text != 'Canceled'
ORDER BY <Columns from the original outer query only>

I have indented this version to make obvious the simple transformation from one to the other in this case. The query diagram is also almost identical, as shown in Figure 7-30.

Figure 7-30. The same query transformed to merge the subquery

This new form has major additional degrees of freedom, allowing, for example, a plan joining to moderately filtered P after joining to highly filtered O but before joining to the almost unfiltered node OT. With the original form, the database would be forced to complete the whole subquery branch before it could consider joins to further nodes of the outer query. Since merging the subquery in cases like this can only help, and since this creates a query diagram you already know how to optimize, I will assume for the rest of this section that you will merge this type of subquery. I will only explain diagramming and optimizing other types.

In theory, you can adapt the same trick for merging EXISTS-type subqueries with the semi-join arrow pointing to the detail end of the join too, but it is harder and less likely to help the query performance. Consider the earlier query against departments with the EXISTS condition on Employees:

SELECT ... 
FROM Departments D
WHERE EXISTS (SELECT NULL 
              FROM Employees E 
              WHERE E.Department_ID=D.Department_ID)

These are the problems with the trick in this direction:

Therefore, you should rarely transform semi-joins to ordinary joins when the semi-join arrow points upward, except when the detail join ratio for the semi-join is near 1.0 or even less than 1.0.

To complete a diagram for an EXISTS-type subquery, you just need rules to estimate the correlation preference ratio and the subquery adjusted filter ratio. Use the following procedure to estimate the correlation preference ratio:

Once you have found the correlation preference ratio, check whether you need the subquery adjusted filter ratio and determine the subquery adjusted filter ratio when you need it:

Try to see if you understand the rules to fill in the correlation preference ratio and the subquery adjusted filter ratio by completing Figure 7-31, which is missing these two numbers.

Figure 7-31. A complex query with missing values for the semi-join

Check your own work against this explanation. Calculate the correlation preference ratio:

To find the subquery adjusted filter ratio, follow these steps:

In the following section on optimizing EXISTS subqueries, I will illustrate optimizing the completed diagram, shown in Figure 7-32.

Subquery conditions that you can express with NOT EXISTS or NOT IN are simpler than EXISTS-type subqueries in one respect: you cannot drive from the subquery outward to the outer query. This eliminates the need for the correlation preference ratio. The E that indicates an EXISTS-type subquery condition is replaced by an N to indicate a NOT EXISTS-type subquery condition, and the correlation join is known as an anti-join rather than a semi-join, since it searches for the case when the join to rows from the subquery finds no match.

It turns out that it is almost always best to express NOT EXISTS-type subquery conditions with NOT EXISTS, rather than with NOT IN. Consider the following template for a NOT IN subquery:

SELECT ... 
FROM ... Outer_Anti_Joined_Table Outer 
WHERE...
  AND Outer.Some_Key NOT IN (SELECT Inner.Some_Key 
                             FROM ... Subquery_Anti_Joined_Table Inner WHERE<Conditions_And_Joins_On_Subquery_Tables_Only>)
...

You can and should rephrase this in the equivalent NOT EXISTS form:

SELECT ... 
FROM ... Outer_Anti_Joined_Table Outer 
WHERE...
  AND Outer.Some_Key IS NOT NULL
  AND NOT EXISTS (SELECT null 
                  FROM ... Subquery_Anti_Joined_Table Inner WHERE<Conditions_And_Joins_On_Subquery_Tables_Only>
                  AND Outer.Some_Key = Inner.Some_Key)

Both EXISTS-type and NOT EXISTS-type subquery conditions stop looking for matches after they find the first match, if one exists. NOT EXISTS subquery conditions are potentially more helpful early in the execution plan, because when they stop early with a found match, they discard the matching row, rather than retain it, making later steps in the plan faster. In contrast, to discard a row with an EXISTS condition, the database must examine every potentially matching row and rule them all out, a more expensive operation when there are many details per master across the semi-join. Remember the following rules, which compare EXISTS and NOT EXISTS conditions that point to detail tables from a master table in the outer query:

Since it is generally both more difficult and less rewarding to convert NOT EXISTS subquery conditions to equivalent simple queries without subqueries, you will often use NOT EXISTS subqueries at either end of the anti-join: the master-table end or the detail-table end. You rarely need to search for alternate ways to express a NOT EXISTS condition.

Since selective NOT EXISTS conditions are inexpensive to check, it turns out to be fairly simple to estimate the subquery adjusted filter ratio:

Returning to the earlier example, consider what it means to have an outer join to the view Shipment_V, which itself is an inner join between tables Shipments and Addresses. Since the database must behave as if there were a real table with precisely the rows the view would find, the join finds the inner case for Shipment_IDs that exist in Shipments and point to shipments that have an Address_ID that successfully joins to Addresses. When the database cannot successfully join to both Shipments and Addresses, the join to the view is entirely an outer join (to both tables), even if the initial join to Shipments could succeed. When searching for a nested-loops plan, the database cannot know whether the outer join finds the inner case until it joins successfully to both tables in the view-defining query.

Unfortunately, this is all too complex for most automated code to handle, so your database might simply give up on a nested-loops plan. Instead, the database code recognizes that no matter how complex the underlying logic might be, it cannot go wrong functionally if, in tricky cases like this, it gets every row from the view-defining query and treats the result like a real table. For the outer join to the view, the database normally performs a sort-merge join or a hash join to that temporarily created table. This is safe enough functionally, but it is usually a disaster for performance, unless the view-defining query is fast as a standalone query.

Similar problems result for all sorts of joins into views that have UNIONs or GROUP BYs in the view-defining queries. However, joining from these views, when they contain the table you would choose as the driving table of the query, usually works fine.

Consider, again, the view-using query from the previous subsection. If you merge the view-defining query for Shipment_V into the view-using query, to resolve the performance problem with the outer join, you might expect this result:

SELECT OV.Customer_Main_Phone, C.Honorific, OV.Customer_First_Name, 
       OV.Customer_Last_Name, C.Suffix, OV.Customer_Address_ID,
       A.Address_ID Shipment_Address_ID, 
       A.Street_Addr_Line1 Shipment_Street_Address_Line1, 
       A.Street_Addr_Line2 Shipment_Street_Address_Line2, 
       A.City_Name Shipment_City_Name, A.State_Abbreviation Shipment_State, 
       A.ZIP_Code Shipment_ZIP, OD.Deferred_Ship_Date, OD.Item_Count, 
       ODT.Text, P.Prod_Description, S.Shipment_Date 
FROM Recent_Order_V OV, Order_Details OD, Products P, Shipments S, 
     Addresses A, Code_Translations ODT, Customers C
WHERE UPPER(OV.Customer_Last_Name) LIKE :last_name||'%'
  AND UPPER(OV.Customer_First_Name) LIKE :first_name||'%'
  AND OD.Order_ID = OV.Order_ID
  AND OV.Customer_ID = C.Customer_ID
  AND OD.Product_ID = P.Product_ID(+)
  AND OD.Shipment_ID = S.Shipment_ID(+)
  AND S.Address_ID = A.Address_ID(+)
  AND OD.Status_Code = ODT.Code
  AND ODT.Code_Type = 'ORDER_DETAIL_STATUS'
ORDER BY OV.Customer_ID, OV.Order_ID Desc, S.Shipment_ID, OD.Order_Detail_ID

Unfortunately, this does not produce quite the same result as the original query, because of the peculiarity of the outer join to the view. Specifically, the original query returns a null Shipment_Date from the view whenever the entire view, including the join to Addresses, fails to join to Order_Details. Therefore, whenever the shipment does not have a valid, nonnull Address_ID, the original query returns null for Shipment_Date, even though the join to Shipments, by itself, is valid.

Almost certainly, this peculiar behavior is not what the developer intended and is not functionally necessary, so the form just shown will likely work fine, even better than the original in this corner case. However, any change in functionality, for a performance fix, is dangerous. Therefore, before making a change such as the one just described that merges the view-defining query into the main SQL statement, make certain the new corner-case behavior is correct and warn developers that the change might cause regression tests to return changed results. In the unlikely event that you really need the original behavior, or if you just want to play safe without investigating whether the original corner-case behavior was correct, you can perfectly emulate the original query functionality with this:

SELECT OV.Customer_Main_Phone, C.Honorific, OV.Customer_First_Name, 
       OV.Customer_Last_Name, C.Suffix, OV.Customer_Address_ID,
       A.Address_ID Shipment_Address_ID, 
       A.Street_Addr_Line1 Shipment_Street_Address_Line1, 
       A.Street_Addr_Line2 Shipment_Street_Address_Line2, 
       A.City_Name Shipment_City_Name, A.State_Abbreviation Shipment_State, 
       A.ZIP_Code Shipment_ZIP, OD.Deferred_Ship_Date, OD.Item_Count, 
       ODT.Text, P.Prod_Description,DECODE(A.Address_ID, NULL, TO_DATE(NULL), 
                                                    S.Shipment_Date) Shipment_Date 
FROM Recent_Order_V OV, Order_Details OD, Products P, Shipments S, 
     Addresses A, Code_Translations ODT, Customers C
WHERE UPPER(OV.Customer_Last_Name) LIKE :last_name||'%'
  AND UPPER(OV.Customer_First_Name) LIKE :first_name||'%'
  AND OD.Order_ID = OV.Order_ID
  AND OV.Customer_ID = C.Customer_ID
  AND OD.Product_ID = P.Product_ID(+)
  AND OD.Shipment_ID = S.Shipment_ID(+)
  AND S.Address_ID = A.Address_ID(+)
  AND OD.Status_Code = ODT.Code
  AND ODT.Code_Type = 'ORDER_DETAIL_STATUS'
ORDER BY OV.Customer_ID, OV.Order_ID Desc, 
     DECODE(A.Address_ID, NULL, TO_NUMBER(NULL), S.Shipment_ID), 
         OD.Order_Detail_ID

This query includes two changes that cause the query to return results as if the join to Shipments produced the outer case whenever the join to Addresses produced the outer case. Without the view, the query will treat the join to Shipments independently from the join to Addresses. However, the DECODE expressions in both the end of the SELECT list and the middle of the ORDER BY list cause the inner case of the first join to emulate the outer case of the join (producing NULL in place of Shipment_Date and Shipment_ID) whenever the join to Addresses finds the outer case.

Occasionally, you will have some functional need to use a view in place of simple tables. The most common reason for this is to work around limitations in autogenerated SQL. Functionally, you might require some bit of complex SQL syntax that the SQL generator cannot handle. The common workaround is to bury that complexity in a view-defining query that you create manually and have the SQL generator simply treat the view as if it were a simple table, hiding the complexity from the SQL-generator code. In these cases, you might not be able to eliminate use of a view, such as I suggest in the earlier solutions. Your alternate approach is to extend use of the view, burying more of the SQL in the view definition. For example, since the previous problem involved an outer join to a view, you could solve the problem by pulling the outer join into the view-defining query. With this solution, you would replace use of Shipment_V with OrderDetail_V, using this view-defining query:

CREATE VIEW Order_Detail_V AS 
SELECT A.Address_ID Shipment_Address_ID, 
       A.Street_Addr_Line1 Shipment_Street_Address_Line1, 
       A.Street_Addr_Line2 Shipment_Street_Address_Line2, 
       A.City_Name Shipment_City_Name, A.State_Abbreviation Shipment_State, 
       A.ZIP_Code Shipment_ZIP,  S.Shipment_Date, S.Shipment_ID, 
       OD.Deferred_Ship_Date, OD.Item_Count, OD.Order_ID, 
       OD.Order_Detail_ID, OD.Product_ID, OD.Status_Code
FROM Shipments S, Addresses A, Order_Details OD
WHERE OD.Shipment_ID = S.Shipment_ID(+)
  AND S.Address_ID = A.Address_ID(+)

The view-using query, using the extended view, then becomes:

SELECT OV.Customer_Main_Phone, C.Honorific, OV.Customer_First_Name, 
       OV.Customer_Last_Name, C.Suffix, OV.Customer_Address_ID, 
       ODV.Shipment_Address_ID, ODV.Shipment_Street_Address_Line1, 
       ODV.Shipment_Street_Address_Line2, ODV.Shipment_City_Name, 
       ODV.Shipment_State, ODV.Shipment_Zip, ODV.Deferred_Ship_Date, 
       ODV.Item_Count, ODT.Text, P.Prod_Description, ODV.Shipment_Date 
FROM Recent_Order_V OV, Order_Detail_V ODV, Products P,
     Code_Translations ODT, Customers C
WHERE UPPER(OV.Customer_Last_Name) LIKE :last_name||'%'
  AND UPPER(OV.Customer_First_Name) LIKE :first_name||'%'
  AND ODV.Order_ID = OV.Order_ID
  AND OV.Customer_ID = C.Customer_ID
  AND ODV.Product_ID = P.Product_ID(+)
  AND ODV.Status_Code = ODT.Code
  AND ODT.Code_Type = 'ORDER_DETAIL_STATUS'
ORDER BY OV.Customer_ID, OV.Order_ID Desc, ODV.Shipment_ID, ODV.Order_Detail_ID

Now, consider the case of the joins in Figure 7-35 to nodes labeled C* and C. These nodes represent the same table, with identical join clauses, so any execution plan that hits both nodes is redundant, reading the same table rows and probably the same index entries twice. The second, redundant read in every case should avoid physical I/O, because the first read, likely less than a millisecond earlier, should place the table or index block safely at the head of the shared cache. If the execution plan is highly filtered before it reaches the second, redundant node, the excess logical I/Os might be negligible, but for large queries or queries that filter most rows only after such redundant reads, the costs of the extra logical I/Os are important.

If the developer wrote the query originally against simple tables, this sort of error would be unlikely; he would have to go out of his way to include the redundant join, and the redundancy would be obvious in code review. With views, however, these errors are easy to make and are well hidden.

How do you fix the redundant join to Customers? You have three options:

Consider the join to node OT in the recent view-using query. The original view-defining query appears to include that join to support queries of the order status, but the view-using query does not even refer to the order status, so you might question whether this node is necessary. If you did not happen to notice the seemingly unused node, you could diagnose the unused node if you noticed a join, in the execution plan, to the primary-key index of this table with no read of the table itself. Such index-only reads of primary-key indexes usually point to unnecessary joins.

Safely eliminating these unnecessary joins is not simple, because they sometimes have functional side effects. Since this is an inner join, it is at least possible that, even with no filter on the node, the join itself eliminates rows the query should not return. This can result either by eliminating rows where Orders.Status_Code IS NULL or where Status_Code points to invalid status codes that fail to find a match in the Code_Translations table. The latter possibility is unlikely or should be eliminated by repairing referential integrity. However, null foreign keys are common, and if the column can be null, you should consider adding an explicit Status_Code IS NOT NULL condition before eliminating the join, to emulate the implicit filtering function of the inner join. More likely, the developer using the view did not even think about the implicit filtering function of the view, and the implicit filter was entirely unintentional and undesirable. Therefore, before emulating the old behavior in a base-table-only query that eliminates the unneeded join, check whether the old behavior was even correct. If your change will subtly change behavior, even for the better, warn testers that regression test results might change for this corner case.