Database guru Craig Mullins explains the basics of access paths and join methods, and then shows you how tools such as Explain to monitor and tune your SQL performance.

Craig Mullins, Director of Technology Planning , BMC Software

Craig S. Mullins is a Director of Technology Planning for BMC Software, located in Houston, Texas. Craig has extensive experience in the field of database management having worked as an application developer, a DBA, and an instructor with multiple database management systems including DB2, Oracle, and SQL Server. Previously, Craig worked as a Research Director with the Gartner Group covering the field of database administration. Craig is the author of DB2 Developer's Guide, the industry-leading book on DB2 for OS/390, and a new book titled Database Administration: Practices and Procedures, which was published by Addison-Wesley in June 2002. Additionally, he is a contributing editor and regular columnist at www.dbazine.com, he writes the monthly DBA Corner column for Database Trends & Application magazine, and he writes the quarterly Database Report column for The Data Administration Newsletter portal. You can contact Craig via his Web site at http://www.craigsmullins.com.



23 January 2003

Also available in Japanese

© 2003 International Business Machines Corporation. All rights reserved.

Introduction

IBM DB2 e-kit for Database Professionals

Learn how easy it is to get trained and certified for DB2 for Linux, UNIX, and Windows with the IBM DB2 e-kit for Database Professionals. Register now, and expand your skills portfolio, or extend your DBMS vendor support to include DB2.

Visual Explain is a phenomenal tool in IBM® DB2® Universal DatabaseTM that can be used by programmers and DBAs to detail the access paths chosen by the DB2 optimizer for SQL statements. Indeed, Explain should be a key component of your performance monitoring strategy. The information provided by Explain is invaluable for resolving many types of performance issues because it provides details such as:

  • The work DB2 does "behind the scenes" to satisfy the data requirements of SQL requests
  • Whether or not DB2 uses available indexes and, if indexes are used, how DB2 uses them
  • The order in which DB2 tables are accessed to satisfy join criteria
  • Locking requirements to satisfy a SQL statement
  • The performance of an SQL statement based on the access paths chosen

For Borland® DelphiTM 7 programmers, Visual Explain can be a fantastic resource for discovering just how DB2 will execute your SQL requests. Delphi uses the CLI native interface to interact with DB2. As such, Delphi uses dynamic SQL. DB2 formulates the access paths for dynamic SQL statements "on the fly" - as the SQL statement is submitted to DB2 for execution. There is no way for an analyst to review the access paths chosen by DB2 for each SQL statement prior to execution. Therefore, it makes sense to periodically examine the access paths that will be chosen by DB2 for all Delphi SQL statement using Visual Explain. Doing so will provide insight into which statements consume the most resources. It can also provide guidance on how to tune your SQL to deliver better performance.

But before I delve into the usage of explain, I first need to examine what exactly is being explained. The short answer is DB2 access paths are being explained. An access path is an algorithm used by DB2 to satisfy the requirements of SQL statements. But there are many different types of access paths that need to be understood.


Types and Components of DB2 Access Paths

The DB2 optimizer can choose from a variety of different techniques as it creates optimal access paths for each SQL statement. These techniques range from a simple series of sequential reads to much more complicated strategies such as using multiple indexes to access data. Let's learn about some of the most popular techniques used by the optimizer to formulate DB2 access paths.

Of the many decisions that must be made by the optimizer, perhaps the most important decision is whether an index will be used to satisfy the query. Before it can determine this, the optimizer must first determine whether an index exists. Remember, you can query any column of any table and an index is not required to do so. So, the optimizer must be able to access non-indexed data; it does this using a scan.

The preference of the DB2 optimizer, in most cases, is to use an index. This is true because an index greatly optimizes data retrieval. However, an index cannot be used if one does not exist. And certain types of SQL statements simply are best satisfied with a complete scan of the data. For example, consider this SQL statement:

SELECT * FROM EMP;

Why should DB2 attempt to use an index on this statement? There is no WHERE clause, so a complete scan is best. Even when a WHERE clause is specified the optimizer may determine that a sequential scan of pages will outperform indexed retrieval - and therefore an index may not be chosen.

Why would non-indexed access outperform indexed access when the primary reason indexes exist in the first place is to improve performance? Well, it's possible that indexed access can be slower than a simple scan. For example, a very small table may have only a few pages. Reading all of the pages may be faster than first reading the index page(s) and then reading the data page(s). Even for larger tables, the organization of the index could require additional I/O to satisfy the query in some cases. When an index is not used to satisfy a query, the resulting access path uses a table scan (or table space scan).

A table scan generally reads every page of the table. In certain circumstances, though, DB2 can be smart enough to limit the pages that are scanned. Additionally, DB2 can invoke sequential prefetch to read pages before they have been requested. Sequential prefetch is particularly useful when a SQL request needs to access rows sequentially, in the order in which they are stored on disk. The optimizer can signal that sequential prefetch should be used when it determines that the query will sequentially read data pages. Table scans frequently benefit from the read ahead processing of sequential prefetch because the data already will be in memory when it is requested by the query.


Fast indexed access

In general, the fastest way to access DB2 data is to use an index. Indexes are structured in such a way as to increase the efficiency of finding a particular piece of data. Figure 1 shows the structure of a b-tree index. You can see that by simply traversing the index from the root to the leaf page you can quickly find the appropriate data page where your requested data exists. But, the manner in which DB2 uses an index varies from statement to statement. DB2 uses many different internal algorithms to traverse an index structure (see Figure 1).

Figure 1. The structure of a b-tree index.
The Structure of a b-tree Index.

Before DB2 will use an index to satisfy a data access request, the following criteria must be met:

  • At least one of the SQL predicates must be indexable. Certain predicates are not indexable by their very nature and therefore the optimizer will never be able to use an index to satisfy them.
  • One of the columns (in any indexable predicate) must exist as a column in an available index.

So, you see, the requirements for DB2 to consider using an index are quite simple. But there is much more learn about indexed access in DB2. There are actually different types of indexed access.

The first, and most simple, type of indexed access is the direct index lookup. For a direct index lookup, DB2 will start at the top using the root page of the index and follow down through the intermediate leaf pages until it reaches the appropriate leaf page. There, it will read the pointer to the actual data page. Based on the index entries, DB2 will read the correct data pages to return the desired result. In order for DB2 to perform a direct index lookup, values must be provided for each column in the index. For example, consider an EMPLOYEE table with an index on the DEPTNO, TYPE, and EMPCODE columns. Now consider this query:

SELECT   FIRSTNAME, LASTNAME 
FROM     EMPLOYEE 
WHERE    DEPTNO = 5 
AND      TYPE = 'X' 
AND      EMPCODE = 10;

If only one or two of these columns were specified, a direct index lookup could not occur because DB2 would not have a value for each column and could not match the full index key. Instead, an index scan could be chosen. There are two types of index scans: matching index scans and non-matching index scans. A matching index scan is sometimes called absolute positioning; a non-matching index scan is sometimes called relative positioning. Recall our earlier examination of table scans? Index scans are similar. In an index scan the leaf pages of the index are read sequentially.

A matching index scan begins at the root page of an index and works down to a leaf page in much the same manner as a direct index lookup does. However, because the complete key of the index is unavailable, DB2 must scan the leaf pages using the values that it does have, until all matching values have been retrieved. Consider a re-write of the previous query, this time without the EMPCODE predicate:

SELECT   FIRSTNAME, LASTNAME 
FROM     EMPLOYEE 
WHERE    DEPTNO = 5 
AND      TYPE = 'X';

A matching index scan can locate the first leaf page with the appropriate value for DEPTNO and TYPE by traversing the index starting at the root. But there can be multiple index entries with this combination of values and different EMPCODE values. Therefore, leaf pages to the right are sequentially scanned until no more valid DEPTNO, TYPE, and varying EMPCODE combinations are encountered.

For a matching index scan to be requested, you must specify the high order column in the index key, which is DEPTNO in the preceding example. This provides a starting point for DB2 to traverse the index structure from the root page to the appropriate leaf page. But what would happen if you did not specify this high order column? Suppose that you alter the sample query such that a predicate for DEPTNO is not specified:

SELECT   FIRSTNAME, LASTNAME 
FROM     EMPLOYEE 
WHERE    TYPE = 'X' 
AND      EMPCODE = 10;

In this instance, a non-matching index scan can be used. In this case DB2 cannot use the index tree structure because the first column in the key is unavailable. A non-matching index scan begins with the first leaf page in the index and sequentially scans subsequent leaf pages, applying the available predicates. The root page and any intermediate leaf pages are not used.

A special type of index scan is known as index only access. DB2 can avoid reading data pages completely if all the required data exists in the index. For example:

SELECT   DEPTNO, TYPE 
FROM     EMPLOYEE 
WHERE    EMPCODE = 10;

Remember, the database contains an index on the DEPTNO, TYPE, and EMPCODE columns. In the previous query these are the only columns requested. Therefore, DB2 need never access the table because all of the data exists in the index.

Another type of indexed access that can be used by DB2 is multiple index access. Multiple index access will use more than one index for a single access path. For example, consider a query against the employee table where I only have two indexes: IX1 on the EMPNO column and another, IX2, on the DEPTNO column. This query is then requested to show which employees work in a certain department:

SELECT   LASTNAME, FIRSTNME, MIDINIT 
FROM     EMPLOYEE 
WHERE    EMPNO IN ('000100', '000110', '000120') 
AND      DEPTNO = 5;

Should DB2 use IX1 for the EMPNO predicate or IX2 for the DEPTNO predicate? Why not use both of them? This is the essence of multiple index access. There are two types of multi-index access, depending on whether the predicates are tied together using AND or OR.


Understanding join methods

So far I have looked at simple access paths when a single table is involved. But what about joins and more complicated SQL statements? The DB2 optimizer has at its disposal a series of techniques that can be used to join table data. When more than one DB2 table is referenced in the FROM clause (or a JOIN clause is specified), the SQL is requesting DB2 to perform a join. Based on the join criteria, a series of instructions must be carried out to combine the data from the tables.

How does DB2 do this? Each multi-table query is broken down into separate access paths. The DB2 optimizer selects two of the tables and creates an optimized access path for accomplishing that join. It does not do this randomly, but chooses based on what it deems will be the most optimal manner for joining. The optimizer will then continue joining to the other tables until the entire query has been optimized.

When joining tables, the optimizer will have to determine the best join algorithm to use. The join algorithm, or join method, defines the basic procedure for combining the tables. There are three types of joins that DB2 can deploy: nested loop, merge scan, and hash joins. Each join method operates differently from the others but achieves the same results. However, the choice of join method has an important effect on the performance of the join. Each join method used by DB2 is engineered such that, given a set of statistics, optimum performance can be achieved. Therefore, you should understand the different join methods and the factors that cause them to be chosen.

Certain basic steps are common to each join method. In general, the first decision to be made is which table should be processed first. This table is referred to as the outer table. After this decision is made, a series of operations are performed on the outer table to prepare it for joining. Rows from that table are then combined to the second table, called the inner table. A series of operations are also performed on the inner table either before the join occurs, as the join occurs, or both. Although all joins are composed of similar steps, each of the three join methods is quite different when you get beyond the generalities. The optimizer understands the advantages and disadvantages of each method and how the use of that method can affect performance. Based on the current statistics in the system catalog, the optimizer understands also which tables are best for the inner table and the outer table. Here is a high-level summary of some of the considerations used by the optimizer:

  • The smaller the table is the more likely it will be chosen as the outer table. This helps to reduce the number of times the inner table must be re-accessed.
  • A table is more likely to be chosen as the outer table if selective predicates can be applied to it because the inner table is only accessed for rows satisfying the predicates applied to the outer table.
  • If it is possible to do an index lookup on one of the tables, then that table is a good candidate to use as the inner table. If a table does not have an index, it would not be a good candidate for the inner table because the entire inner table would have to be scanned for every row of the outer table.
  • The table with fewest duplicates may have a propensity to be chosen as the outer table in a join.

Of course, none of these are hard and fast rules. In the end, the optimizer will choose the outer and inner tables based on detailed cost estimates. Now I'll examine the types of joins available to DB2 and how they differ from one another.

Probably the most common type of join method is the nested loop join (NLJ). To perform a NLJ, a qualifying row is identified in the outer table, and then the inner table is scanned searching for a match. A qualifying row is one in which the predicates for columns in the table match. When the inner table scan is complete, another qualifying row in the outer table is identified. The inner table is scanned for a match again, and so on. The repeated scanning of the inner table is usually accomplished with an index to minimize I/O cost.

The second type of join method used by DB2 is the merge join (MJ). With the MJ, the tables to be joined need to be ordered by the join predicates. That means that each table must be accessed in order by the columns that specify the join criteria. This ordering can be the result of either a sort or indexed access. After ensuring that both the outer and inner tables are properly sequenced, each table is read sequentially, and the join columns are matched up. Neither table is read more than once during a merge scan join.

The third type of join depends on the platform on which you are running DB2. For DB2 for OS/390 and z/OS there is the hybrid join. The hybrid join combines data and pointers to access and combine the rows from the tables being joined. A complete discussion of this join type is beyond the scope of this article.

For DB2 for Linux, UNIX, and Windows, the third type of join is the hash join. Hash join requires one or more predicates of the form table1.ColX = table2.ColY, and for which the column types are the same. The inner table is scanned and the rows copied into memory buffers drawn from the sort heap allocation. The memory buffers are divided into partitions based on a "hash code" computed from the column(s) of the join predicate(s). If the size of the first table exceeds the available sort heap space, buffers from selected partitions are written to temporary tables. After processing the inner table, the outer table is scanned and its rows are matched to the inner table rows by comparing the "hash code." Hash joins can require a significant amount of memory. So, for the hash join to produce realistic performance benefits, you may need to change the value of the sortheap database configuration parameter, and the sheapthres database manager configuration parameter.

Now then, when do you know which of these join methods should be used? In general, the nested loop join is preferred in terms of execution cost when a small number of rows qualify for the join. As the number of qualifying rows increases, the merge join becomes a better choice. Finally, in the case of a hash join, the inner table is kept in memory buffers. If there are too few memory buffers, then the hash join is obliged to spill. The optimizer attempts to avoid this and so will pick the smaller of the two tables as the inner table, and the larger one as the outer table.

Results for performance generalizations will depend on the exact number of qualifying rows as well as other factors such as your database design, database organization, accuracy of statistics, type of hardware, and the setup of your DB2 environment.


Specify search strategies with optimization classes

The choice of join method also will depend on the optimization class being used. Optimization classes specify the different search strategies that should be used by the optimizer when compiling and optimizing SQL statements. So, not every access path technique described above is always available to the optimizer. Instead, based on the optimization class, different techniques will be made available to the optimizer.

The purpose of the optimization class is to guide DB2 as to how thorough it should be when considering search strategies and optimization techniques to use. In general, the more search strategies considered by the optimizer the better the access plan will be for the query. However, when the optimizer is guided to consider more search strategies it will take longer to compile the SQL into an executable access path. Fortunately, you can set the optimization class to limit the number of techniques applied when optimizing your query. This can be quite useful for simpler queries, resource-constrained systems, and dynamic SQL. The optimization classes are outlined in Table 1.

Table 1. DB2 optimization classes

ClassDescription
0Directs the optimizer to use a minimal amount of optimization to generate an access plan. Only nested loop join and index scan access methods are available. Limited use of statistics (e.g. does not consider non-uniform distribution statistics).
1Similar to class 0, but adds merge joins, table scans, and very basic query rewrite (plus a few additional features).
2Significantly improves on class 1 but with significantly lower compilation cost than class 3. This class makes use of all available statistics, most query rewrite rules, list prefetch, and summary table routing. Similar to class 5 except that it uses greedy join enumeration rather than dynamic programming.
3This class is the closest to the query optimization used by DB2 for OS/390. It provides a moderate amount of optimization and requires moderate amount of resources to compile.
5Provides a significant amount of optimization and requires more resources to compile than class 3. The optimizer intelligently determines when additional resources are not warranted for dynamic SQL. Class 5 is a good choice for a mixed environment of complex and simpler queries.
7This class is similar to class 5 but adds some optimization techniques not available to class 5. This class will not determine when additional resources are not warranted for dynamic SQL.
9Uses all available optimization techniques.

Although you may select any query optimization class as described in the table, classes 0 and 9 should be used only on rare occasions. Classes 0, 1, and 2 use the Greedy join enumeration algorithm; for complex queries this algorithm considers far fewer alternative plans, and incurs significantly less compilation time, than classes 3 and above. Classes 3 and above use the Dynamic Programming join enumeration algorithm; this algorithm considers far more alternative plans, and can incur significantly more compilation time, than classes 0, 1, and 2 as the number of tables increases.

The way you set a specific query optimization class depends on whether you are using static or dynamic SQL. For static SQL statements the optimization class is specified on the PREP and BIND commands. The QUERYOPT column in the SYSCAT.PACKAGES catalog table records the optimization class that was used to bind the package. Dynamic SQL statements use the optimization class specified by the CURRENT QUERY OPTIMIZATION special register that is set using the SQL SET statement.

Finally, let me quickly define the two types of search strategies and their characteristics. The first type, used by classes 0,1, and 2, is greedy join enumeration. With greedy join enumeration, once a join method is selected for two tables, it will not be changed during further optimization. Therefore, it may not choose the absolute best access plan when joining many tables. Queries joining only a few tables will likely have the same access plan chosen by greedy join enumeration as by the other search strategy, dynamic programming join enumeration. Dynamic programming join enumeration will require more time and resources as the number of tables being joined increases. It is more likely choose the best access plan possible than greedy join enumeration.


Using Visual Explain

Now that we have a basic understanding of the access paths that DB2 can choose to satisfy SQL requests, let's examine how we can uncover which access paths DB2 uses for our queries. This is done using explain. A single SQL statement, or a series of SQL statements in a package, can be the subject of an explain. Of course, when a package is explained, only the static SQL will be explained. For Delphi, this is not helpful because, as previously mentioned, all SQL is dynamic, not static.

When an explain is requested, the SQL statements are passed through the DB2 optimizer, and the access paths that DB2 chooses are externalized, in coded format, into a set of DB2 explain tables. The explain tables are nothing more than standard DB2 tables that must be defined with predetermined columns, data types, and lengths. Keep in mind, though, that the explain tables are not created automatically. In order to use explain, you (or your DBA) must first create these explain tables. A DB2 CLP script named explain.ddl can be found in the misc subdirectory of the sqllib directory where DB2 was installed. Executing this script will cause the explain tables to be created. Once the explain tables have been successfully created, there are several options you can use to explain DB2 access paths.

Visual Explain is the easiest method because it is accessed using a GUI with simple point-and-click commands and pull-down menus (see Figure 2). Visual Explain can be accessed as a standalone tool or from the DB2 Control Center. The primary benefit of Visual Explain is that it provides a graphical depiction of your access paths therefore you do not need to understand the coded information in the explain tables. Each access path operation is placed into a color-coded node in a tree structure. Simply mousing over that node and clicking allows you to display the arguments, statistics, and cost estimate for that portion of the access path. Visual Explain can also be run from the command line as db2vexp.exe.

Figure 2. Visual Explain GUI
Visual Explain GUI

This example in Figure 2 shows that DB2 used an index scan of an index named PK_15 to SELECT data from the ATTRIBUTE_REGION table. By clicking on the nodes you can get additional details about the components of each part of the access path. As we examined in the previous section on access paths, there will be nodes to identify scans, indexed access, and sorts. Figure 3 shows the results of clicking on the IXSCAN node. We can see that the index scan will be done on the REGION_TYPE_ID column. By reviewing the output of the explain you can readily determine the access paths that DB2 will use to satisfy each SQL query (see Figure 3).

Figure 3. Visual Explain details
Visual Explain Details

A manual process is required without a tool such as Visual Explain to provide easy-to-read access path information. Furthermore, you have to be able to interpret the coded information in the explain tables to understand the output of a manual explain. With Visual Explain, you need not concern yourself with the actual format or contents of the explain tables - the tool does it all for you.

There are other EXPLAIN tools provided with DB2. These include db2expln which is a "bare bones" tool that provides a textual description of the access paths for static packages only. This tool is not useful for Delphi; instead you might choose to use dynexpln, which offers text analysis of dynamic SQL queries. The dynexpln tool will package the dynamic query and then call db2expln to do the work. In general, though, stick to Visual Explain because it is easier to use and provides the basic information that you will need to tune your SQL.

A good rule of thumb for Delphi users is to use Visual Explain to show the access paths for SQL SELECT statements in your Delphi programs. Try to get indexed access for most of your SELECT statements. To do this you can either create additional indexes (in a production environment do so only under the guidance of your DBA) or modify your SQL statements to include indexable predicates. Analyze the join methods being used and understand the implications. For example, will a merge scan join require sorting? Is that acceptable or will performance suffer?

Keep in mind that the results of explain are only as good as the statistics in the DB2 system catalog. Ensure that the DB2 system catalog statistics are up-to-date before using explain. Accurate statistical information for DB2 tables, indexes, and columns in the system catalog is instrumental for the optimizer to choose an efficient access plan. If the statistics were not collected recently, verify that they are still appropriate before running explain.

Finally, be aware of the missing pieces that you will need to do a good job of SQL tuning. To analyze SQL performance properly, you will require more than just the explain results. Proper performance analysis requires:

  • The actual SQL statement
  • A listing of the DDL (or system catalog information) for the objects being accessed and/or modified
  • The Delphi code in which the SQL statement is embedded
  • The actual system catalog statistics that were in place at the time the explain was performed
  • Knowledge of the DB2 environment in which the SQL statement will be executed (including settings for buffers, locking parameters, and so on)
  • Knowledge of the environment where the SQL is being run (including operating system, number and type of processors, amount of memory, and so on)
  • Knowledge of concurrent activity in the system when the SQL statement was (or will be) executed

This additional information can be used, along with the explain output, to estimate the performance of any given SQL statement. The Delphi code is important to help you regulate application performance because explain cannot provide information about the high-level language in which the SQL is embedded. The explain output may show an efficient access path for the SQL statement but then if it is embedded in a loop that runs thousands of times performance will likely suffer.

Use explain to help ensure that indexes are being applied properly for join predicates, local predicates, and GROUP BY and ORDER BY clauses to avoid sorting. Furthermore, use your knowledge of the data in the tables to determine if the proper type of join is being deployed and if the correct tables are being used for the inner and outer tables of the join. Attention to these types of details can be the difference between an optimized application and a slow performer.


Conclusion

Effective use of the Visual Explain facility can help Delphi programmers understand the access paths being used to satisfy their DB2 SQL requests. There are many different techniques that DB2 can choose to satisfy a request for data - and some are much more efficient than others. An informed Delphi programmer can use explain to optimize his code thereby efficiently accessing DB2 data.

Resources

Comments

developerWorks: Sign in

Required fields are indicated with an asterisk (*).


Need an IBM ID?
Forgot your IBM ID?


Forgot your password?
Change your password

By clicking Submit, you agree to the developerWorks terms of use.

 


The first time you sign into developerWorks, a profile is created for you. Information in your profile (your name, country/region, and company name) is displayed to the public and will accompany any content you post, unless you opt to hide your company name. You may update your IBM account at any time.

All information submitted is secure.

Choose your display name



The first time you sign in to developerWorks, a profile is created for you, so you need to choose a display name. Your display name accompanies the content you post on developerWorks.

Please choose a display name between 3-31 characters. Your display name must be unique in the developerWorks community and should not be your email address for privacy reasons.

Required fields are indicated with an asterisk (*).

(Must be between 3 – 31 characters.)

By clicking Submit, you agree to the developerWorks terms of use.

 


All information submitted is secure.

Dig deeper into Information management on developerWorks


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=1
Zone=Information Management
ArticleID=13318
ArticleTitle=Tuning DB2 SQL Access Paths
publish-date=01232003