In Chapter 6 we discussed the use of joins as part of the theory of relational database design. Joins, however, can also have a major impact on query performance. The extent of the impact depends on your DBMS and how it implements a join.

From a relational algebra point of view, a join can be implemented using two other operations: product and restrict. As you will see, this sequence of operations requires the manipulation of a great deal of data and, if used by a DBMS, can result in very slow query performance.

The restrict operation retrieves rows from a table by matching each row against logical criteria (a predicate). Those rows that meet the criteria are placed in the result table, and those that do not meet the criteria are omitted. Restrict, which was originally called select, cannot choose columns; you get every column in the table.

The product operation (the mathematical Cartesian product) makes every possible pairing of rows from two source tables. In Figure 7-1, for example, the product of the customer and order tables that you saw in Chapter 6 produces a result table with 48 rows (6 customers times the 8 orders). The customer number column appears twice because it is part of both source tables.

In some rows, the customer number is the same. These are the rows that should be included in a join. We can therefore apply a restrict predicate to the product table to end up with the same table provided by the join you saw in Chapter 6. The predicate's logical condition can be written:

The rows that are chosen by this predicate appear in boldface in Figure 7-2; those eliminated by the predicate are in regular type. Notice that the boldface rows are exactly the same as those in the result table of the join from Chapter 6.

Because of the processing overhead created when performing joins in this way, some database designers make a conscious decision to leave tables unnormalized. For example, if Antique Opticals always accessed the line items at the same time it accessed order information, then a designer might choose to combine the order item and order data into one table, knowing full well that the unnormalized relation exhibits anomalies. The benefit is that the retrieval of order information will be faster than if it were split into two tables.

Should you leave unnormalized relations in your database to achieve better retrieval performance? In this author's opinion, there is rarely any need to do so. First, not all DBMSs implement a join in this way. Before you decide not to normalize tables, investigate how your DBMS performs a join. In addition, there are ways to prepare SQL queries (in particular, using uncorrelated subqueries) that can produce the same result as a join but without actually performing the join. That being the case, it does not seem worth the problems that unnormalized relations present to leave them in the database. Careful writing of retrieval queries can provide performance that is nearly as good as that of retrieval from unnormalized relations.

Indexing is a way of providing a fast access path to the values of a column or a concatenation of columns. New rows are typically added to the bottom of a table, resulting in a relatively random order of the values in any given column. Without some way of ordering the data, the only way the DBMS can search a column is by sequentially scanning each row from top to bottom. The larger a table becomes, the slower a sequential search will be.

The alternative to indexing for ordering the rows in a table is sorting. A sort physically alters the position of rows in a table, placing the rows in order starting with the first row in the table. Most SQL implementations do sort the virtual tables that are created as the result of queries when directed to do so by the SQL query. However, SQL provides no way to sort base tables, and there is good reason for this. Regardless of the sorting method used, as a table grows large (hundreds of thousands to millions of rows), sorting takes a very long time.

Keeping a table in sorted order also means that on average half of the rows in the table will need to be moved to make room for a new row. In addition, searching a sorted base table takes longer than searching an index, primarily because the index search requires less disk access. The overhead in maintaining indexes is far less than that required to sort base tables whenever a specific data order is needed.

The conceptual operation of an index is diagrammed in Figure 7-3. (The different weights of the lines have no significance other than to make it easier for you to follow the crossed lines.) This illustration shows Antique Opticals’ item relation and an index that provides fast access to rows in the table based on the item's title. The index itself contains an ordered list of keys (the titles) along with the locations of the associated rows in the item table. The rows in the item table are in relatively random order. However, because the index is in alphabetical order by title, it can be searched quickly to locate a specific title. Then the DBMS can use the information in the index to go directly to the correct row or rows in the item table, thus avoiding a slow sequential search of the base table's rows.

Once you have created an index, the DBMS's query optimizer will use the index whenever it determines that using the index will speed up data retrieval. You never need to access the index again yourself unless you want to delete it.

When you create a primary key for a table, the DBMS automatically creates an index for that table, using the primary key column or columns in the primary key as the index key. The first step in inserting a new row into a table is therefore verification that the index key (the primary key of the table) is unique in the index. In fact, uniqueness is enforced by requiring the index entries to be unique, rather than by actually searching the base table. This is much faster than attempting to verify uniqueness directly on the base table because the ordered index can be searched much more rapidly than the unordered base table.

The slowest part of a DBMS's actions is retrieving data from or writing data to a disk. If you can cut down on the number of times the DBMS must read from or write to a disk, you can speed up overall database performance. The trick to doing this is understanding that a database must retrieve an entire disk page of data at one time.

The size of a page varies from one computing platform to another; it can be anywhere from 512 bytes to 4 K, with 1 K being typical on a PC. Data always travel to and from disk in page-sized units. Therefore, if you store data that are often accessed together on the same disk page (or pages that are physically close together), you can speed up data access. This process is known as clustering and is available with many large DBMSs (for example, Oracle).

In practice, a cluster is designed to keep together rows related by matching primary and foreign keys. To define the cluster, you specify a column or columns on which the DBMS should form the cluster and the tables that should be included. Then, all of the rows that share the same value of the column or columns on which the cluster is based are stored as physically close together as possible. As a result, the rows in a table may be scattered across several disk pages, but matching primary and foreign keys are usually on the same disk page.

Clustering can significantly speed up join performance. However, just as with indexes, there are some trade-offs to consider when contemplating creating clusters:

Partitioning is the opposite of clustering. It involves the splitting of large tables into smaller ones so that the DBMS does not need to retrieve as much data at any one time. Consider, for example, what happens to Antique Opticals’ order and order items tables over time. Assuming that the business is reasonably successful, those tables (especially order items) will become very large. Retrieval of data from those tables will therefore begin to slow down. It would speed up retrieval of open orders if filled orders and their items could be separated from open orders and their items.

There are two ways to partition a table: horizontally and vertically. Horizontal partitioning involves splitting the rows of a table between two or more tables with identical structures. Vertical partitioning involves dividing the columns of a table and placing them in two or more tables linked by the original table's primary key. As you might expect, there are advantages and disadvantages to both.