Sort Merge Join Costing

For a Sort-Merge Join, each data set (Outer and Inner) is read separately and sorted by the joining columns. The resultant sorted data sets are then joined together. The cost formula for this is:

• [Outer Access Cost] + [Sorting Outer Cost] + [Inner Access Cost] + [Inner Sort Cost]

We know how to calculate the two data Access Costs from earlier posts for different tables and the indexes available on them. How does the Optimizer cost the two Sorts?

The two key points are - how big is the data set to be sorted, and how much memory is available for use as a sort area?

If both of the data sets fit into the available memory, then they can be sorted directly into memory as they are read from their sources (previous steps in the execution plan). This avoids additional disk I/O and only has a CPU cost for the Sorts. The Optimizer calculates an approximate cost for this CPU component according to its own internal formula. Although this CPU cost is included by the Optimizer in its costs, for our purposes we can ignore it. This is because it is generally so small compared to the I/O costs involved in getting the data from disk in the first place, that it is negligible and has no impact on the final choice of which execution plan to use.

If you are using Oracle 10g and its new initialization parameters, with "workarea_size_policy" set to auto, then the amount of memory used by Optimizer as the query sort area will be a percentage of the memory specified for "pga_aggregate_target". (If these are not set correctly, then it will use the value of the older "sort_area_size parameter" - but this is now deprecated and should not be used.)

The percentage it will use is not documented anywhere, but there are several references to 5% on the web. However, in the testing that I did I saw nearer 20% being used. This could be due to the fact that nothing else was happening on this system, so all of the PGA memory was free and available. Or that I had a relatively small PGA aggregate target of 32 MB, and there is a minimum allocation size from within the PGA memory area.

Either way, if you are trying to estimate the cost yourself, it is probably best to use 5% of the PGA memory as your value.

To calculate the size of the data being sorted you need to know the following:

• The columns being retrieved from each table. Oracle only processes those data columns it needs, and not the whole data row. The columns used will include those needed for the query output itself, plus those needed for filter conditions and joins to other data sets.

• The size of each of these columns, added together for each data set to give a data total.

• An additional 6 bytes per data row, as a unique identifier for it, internal to the processing by the Optimizer. This is present in all data sets, regardless of the join method.

• An additional 12 bytes per data row for sort processing, on 32 bit systems. This would be doubled to 24 bytes on 64 bit systems, as they are memory address pointers. [Jonathan Lewis, Cost Based Oracle Fundamentals].

• The number of rows or cardinality of each data set.

Adding together the row element sizes and multiplying by the cardinality of the data set, gives the total space needed for each data set. If either of these exceeds the available memory, then the Optimizer assumes that the Sort will be done in chunks, or sets, each written out to disk, and then each sorted sub-set merged together into the final sorted result set.

During this Merge phase, Oracle needs to read in blocks of sorted data from all of the sorted sets into memory at the same time, in order to properly merge them together. For efficiency Oracle uses multi-block reads on the sorted sets, because they are already sorted sequentially on disk and are being used in that order. Multi-block reads reduces the total number of read disk I/Os needed to read in all the sorted sets. Thus the number of sorted sub-sets that can be merged simultaneously is limited by the memory available, as mentioned earlier, and the size of the multi-block reads. The Optimizer terms this the "Sort width" in some of its trace output, but it means the number of sort sets that can be merged together at once.

If there is enough memory after the Sort phase to Merge all of the sorted sets together at once, then they are indeed merged this way, and this is termed a "single pass merge" - one processing of the sorted sets to merge them.

If there is not enough memory to Merge all sorted sets at once, then Oracle will merge as many as it can, and produce a single, larger sorted set of data rows from these. It will then repeat this merging across the next group of sorted sets, and so on to iterate over all of the sets from the initial sort. This will result in a smaller number of larger sorted sets, which hopefully can now be merged together. If not, the merging of sets is repeated until the number of sets is reduced to that which can be merged together. This is termed a "multi-pass merge".

Assuming that the data to be sorted is larger than the memory available, then the cost of the initial sort phase into sorted sets is the cost of writing out the data blocks using single block writes, plus the CPU cost to do the sort. Again, as before, the CPU cost is trivial compared to the disk I/O cost, but both are calculated by the Optimizer. The cost of the Merge phase is again the cost to read in the data from disk, plus the CPU cost of the merge.

When reading the data back in to merge, it seems that Oracle wants to use multi-block reads as described, but may not be able to achieve that for all the blocks for some reason or another. The Optimizer seems to base its calculations on achieving multi-block reads for two thirds of the sorted blocks, but not for the other third i.e. single block I/O used for this.

Sort-Merge Example

The calculations here produce results that agree with the costs given in a 10053 event trace file. In fact, it was a number of such trace files for different data sets that was used to derive the formula presented.

The Outer data set has 7 bytes of data, plus the 6 overhead is 13 bytes of data per row, with cardinality of 500,000 rows. The cost to produce this has been calculated by the Optimizer as being 245.84.

The Inner data set has 3 bytes of data, plus 6 overhead gives 9 bytes of data per row, with cardinality of 100,000 rows. The Optimizer has calculated the cost to produce this as 270.83.

Adding on the 12 bytes per row used by the sort operation, gives 25 bytes per Outer data row and 21 bytes per Inner data row. The Outer data volume is therefore 500,000 * 25 = 12,500,00 bytes = 11.92 MB (dividing by 1024 twice). The maximum memory available for the sort is 6.4 MB in this case, so the data will be sorted to disk and then merged back together. The sorts can be done using 2 sort sets, so only a single pass merge is required.

It seems that when the Outer data set is sorted in multiple sets, so is the Inner data set too, even though it could fit in memory in this case.

To calculate the I/Os involved, we must calculate the number of blocks required to store each of these data sets of 25 and 21 bytes per data row each. With an 8 KB block size, the calculations of the number of blocks are:

• Outer Rows per block = floor (8192 / 25) = 327
• Outer blocks = ceiling (500,000 / 327) = 1530
• Inner Rows per block = floor (8192 / 21) = 390
• Inner blocks = ceiling (100,000 / 390) = 257

To each of these another block is added, presumably some kind of master control block, giving 1531 and 258 blocks per data set.

The sort phase cost is that of writing out the blocks using single block I/O i.e. 1531 and 258. The merge phase cost is two thirds multi-block I/O and one third single block I/O. Remember that multi-block I/O is adjusted by Oracle by the ratio of single block read to multi-block read and the value used for Multi-Block Read Count (MBRC, typically being the db_file_multiblock_read_count initialization parameter), as seen previously in the formula for a Full Table Scan. Using typical values of these of 8 for MBRC and 12 for SREADTIM and 26 for MREADTIM, gives an adjusted MBRC value of 3.69.

However, Oracle does not use the value of "db_file_multiblock_read_count" for sorts, and instead uses an undocumented parameter of "_smm_auto_min_io_size", which defaults to 56 KB. This is 7 blocks in size in this case.

• 1530 / 3 = 510
• 510 * 2 = 1020 (multi-block I/O)
• Multi-Block Cost is (1020 * 26) / (7 * 12) = 26520 / 84 = 315.714 i.e. 316 I/O cost units

The Merge phase cost is the sum of both types of I/O - 510 + 316 = 826. The Sort phase cost is 1020. And the total Sort/Merge I/O cost is 1530 + 826 = 2356.

Likewise for the Inner data set the Sort phase cost is 258. The Merge cost is derived from:

• 258 / 3 = 86
• 86 * 2 = 172
• Multi-Block Cost is (172 * 26) / (7 * 12) = 4472 / 84 = 53.23 i.e. 54 I/O cost units
• Total Merge cost is 86 + 54 = 140.
• Total Sort / Merge cost is 258 + 140 = 398.

These results agree very closely with those reported in the 10053 event trace file for this query. This reports the Merge cost separately as "IO Cost / pass", and the "Total IO sort cost" which is actually for the complete Sort / Merge. The Sort cost itself must be deduced by subtracting these two values from each other.

For the Outer data set the 10053 trace file reported 2349 as the total Sort/Merge cost, and 400 for the Inner data set. These differences can be explained as follows:

The Optimizer used a calculated cardinality of 497,392.56 for the Outer data set, instead of 500,000. This resulted in a lower sort block count of 1523 instead of 1530.

After dividing the block count by three into thirds, it seems to add on two more blocks, presumably to account for an uneven division. Thus 1523 / 3 gives 508 blocks rounded up, but the Optimizer uses 510. Likewise instead of 86 for the third of 258, it uses 88.

This gives the modified results of:

• Outer Merge I/O Cost = 510 + 316 = 826
• Outer Sort / Merge I/O Cost = 1523 + 826 = 2349 - as reported in the 10053 file
• Inner Merge I/O Cost = 88 + 55 = 143 - 142 is reported in the 10053 file
• Inner Sort / Merge I/O Cost = 258 + 143 = 401 - 400 is reported in the 10053 file

Using the values reported in the 10053 file, the total cost for the Sort Merge Join is:

• [Outer Access Cost] + [Sorting Outer Cost] + [Inner Access Cost] + [Inner Sort Cost]
• 245.84 + 2349 + 270.83 + 400 = 3265.67

The reported value in the 10053 trace file is 3331.02, of which 3254.00 is the total I/O cost. The missing 65.35 (3331.02 - 3265.67) is presumably the CPU cost of the two sorts and their merges and the production of the Outer and Inner data sets. As predicted this is much lower than the I/O cost of the sorts and merges.

The heuristic presented of the Merge reading two thirds of the sorted blocks using multi-block reads, and single blocks reads for the remaining third, was arrived at by varying the values of different inputs that the Optimizer would use, and observing the impact on the costs reported. Whenever the value of _smm_auto_min_io_size was adjusted there was a corresponding change in the reported value of the Merge cost (IO Cost / pass). From this the splitting into thirds was deduced, and also that the Sort cost was simply the number of blocks to be sorted due to using single block I/O. Once hypothesized, all subsequent tests agreed with this formula, and none disagreed. Increasing the number of rows to be sorted, or the width of the rows, or the PGA Aggregate Target did change the number of sort sets produced, but the formula presented here still held and the Sort and Merge I/O costs reported agreed with those calculated.

Nested Loop Join Costing

As described previously, the optimizer has 3 main join methods available when joining 2 data sets together:

• Nested Loop Join
• Sort Merge Join
• Hash Join

Each method has a different associated formula for its cost of execution. Here I will look at the Nested Loop Join, which is the most straightforward in some respects. Some of this information, such as the costing formula, are given in the Oracle Performance Tuning Guide Manual, in the chapter on the Query Optimizer.

A Nested Loop Join reads data from one data set - the Outer data set - and for each data row retrieves corresponding rows from the other data set - the Inner data set. Clearly the Inner data set is accessed separately for each data row in the Outer data set. And the number of rows in a data set is termed its Cardinality. Hence the cost formula for a Nested Loop Join is as follows, where "Outer" and "Inner" refer to their respective data sets, and square brackets used to enclose each individual element:

• [Cost of Outer Access] + ([Cardinality of Outer] * [Cost of Inner Access])

The Outer and Inner costs will have been determined earlier by the Optimizer, either as a single table access cost or as the cost of a previous join between data sets. Thus these component costs do not have to be recalculated by the Optimizer.

Example

Consider the following query using a table with 100,000 rows in it over 1252 * 8 KB blocks:

select it1.i1
from insert_test_1 it1, insert_test_1 it2
where it1.i1 = it2.i4
and it1.i3 = 99

I am using the same table twice in the query, with an alias for each occurrence of it.

There are indexes on each column i.e. on i1, i2 (not used here), i3 and i4. The i1 index is unique, but the others are not.

Remember that the Optimizer starts with the data set with the lowest cardinality (smallest number of data rows). In this case this is "it1", because the "i3" column has 100 rows for each possible value. This gives a cardinality of 100 for "it1" as the Outer data set. The lowest cost access to this is using the index on this, which has a cost of 102 (costed using index range scan described in an earlier post).

To join to "it2" in this case, the index on "i4" can be used. In this case no other data columns are needed from the "it2" table, and thus the cost is really that of reading the index leaf block with that particular value. For this index all entries for one value fit within one leaf block (leaf blocks per key value is 1), so the access cost is just 1 to read that particular leaf block.

The Nested Loop Cost is therefore:-

• 102 + (100 * 1) = 102 + 100 = 202

This was verified by examining a 10053 event trace file when this SQL was executed. The costs reported differ only after the decimal point, due to a combination of rounding of values within Oracle and additional minor costs such as CPU cost (in 10g).

The 10053 trace file also showed that the Optimizer also costed other variations of the Nested Loop Join. This agrees with the statement that the Optimizer costs all possible access and join plans to determine the cheapest one.

Also considered are a full table scan of it2, at a cost of 243.1. The Nested Loop cost of this should be:

• 102.1 + (100.2 * 243.1) = 102.1 + 24358.2 = 244460.3

The 10053 trace file actually reported a cost of 24580.26 total. Again this would be different due to rounding of results and additional CPU costs. Nevertheless, it is very close to our calculated value for the I/O cost only.

Optimizer Costing of Joins

Previously I have described how the Oracle Cost Based Optimizer costs all possible execution plans for a SQL statement to arrive at the one with the lowest cost (cheapest), and how it costs access to single tables using access methods of Full Table Scan and Index Range Scans. There are a few other potential access methods to a single table, but these are the primary ones that occur most if not all of the time. I will now describe how the Optimizer goes about costing joins between tables.

Although we often say that a query involves processing data from tables, it is important to realise that internally the query processes a series of data sets. Logically each step in the execution plan produces a result set of data rows, that is in turn consumed by its parent step within the execution plan. So although we might talk about joining "tables" together, the Optimizer is actually always joining "data sets" together. Some of these data sets do come from tables, while others may come from other steps within a more complex execution plan e.g. from a join of other data sets.

The Optimizer normally only joins two data sets together at a time. There are some exceptions, such as using Bit Map Indexes on Star schemas in Data Warehouses. But for most transaction processing systems, the joins will be between two data sets at a time. Joining more than two tables together simply involves the Optimizer first joining two of the tables together to produce a resultant data set, and then joining this to the third table, and so on to join together all the tables in the query.

First, how does the Optimizer determine the lowest cost join execution plan? In simple terms it costs each and every possible join method between the pair of data sets being joined, and chooses the cheapest one from these. That is: it considers different join methods for joining Data Set 1 to Data Set 2, and also considers the join the other way around - Data Set 2 to Data Set 1.

When there are more than two tables to join together, the Optimizer simply iterates over all the possible join combinations between them and the different join methods for each. It picks one data set as the first one, another as the second, costs the joins between them to get a cheapest, then costs the joins of this to the third data set. Then the next iteration does the first data set to the third, and in turn to the second. Then it repeats for all the other combinations - second to first to third, second to third to first, and so on. Thus all possible join paths between the data sets are costed, and the cheapest one chosen.

Second, what join methods are available? There are 3 main join methods:

• Nested Loop Join
• Sort Merge Join
• Hash Join

Each method has a different associated formula for its cost of execution. Generally this is the cost of accessing each data set, already calculated previously by the Optimizer, and the cost of the join itself.

Note that when I say "cost of accessing each data set" for a join between two data sets, the actual access method can be different for each join method, and so have a different cost. It is not required that all three join methods use the same access method to get to the data sets they need to join. The Optimizer will cost the join methods with the appropriate data access and choose the cheapest one.

Thus for 2 tables and 3 join methods the Optimizer must cost 6 separate possible join combinations. For 3 tables this produces 6 different join combinations between them, each costed for the 3 join methods, for a total of 18 different possible join costs. For 4 tables it becomes 72 different joins to cost, and so on.

Fully costing each join combination properly would be very time consuming, so the Optimizer has a number of improvements to reduce this. For the first join combination it starts with the data set with the lowest cardinality - smallest estimated number of rows in it. In turn it joins this to the data set with the next lowest cardinality, and so on. This is because this is likely to produce a relatively low cost plan due to it processing less data rows initially. This is not guaranteed to be the lowest cost, but will generally be relatively low. This first join combination is then remembered as the currently lowest join cost.

When costing subsequent join combinations, if the partial cost so far of a join plan is greater than the currently lowest join cost, then it is abandoned (pruned). This makes sense, because costs can only increase for an execution plan as other costs are accumulated within it. Furthermore, sometimes the cost for just accessing the first data set may be greater than the current lowest join cost, and such a join can be pruned without any further consideration or costing of different join methods. Remember that single table access paths are costed first by the Optimizer for each table referenced in the query. So it already knows what these costs are, with no further calculations required.

Thus the Optimizer is able to cost each join combination and each join method between the data sets, to arrive at the cheapest join cost. The internal optimizations attempt to minimise the total effort involved in costing each of these, by picking a relatively low cost join combination as the first one to be costed, and by immediately pruning out any alternative join plan as soon as its partial cost exceeds the current lowest cost join.

Optimizer Costing of Index Scans

Previously I gave a brief overview of the fact that the optimizer costs each potential execution plan for a SQL query and then chooses the one with the lowest cost, and described how it costs a Full Table Scan. Now I will carry on and look at the cost calculations for using an Index to access data in a table. Again, most of this is based on the information in A Look Under The Hood Of CBO: The 10053 Event by Wolfgang Breitling, and various tests I have done to confirm the details of this. Now we will look at the calculation of costs for table access using an Index.

Note that I am concentrating here on the I/O cost as that is the largest component of the cost of an execution plan. However, there is also a CPU cost, which is not shown here. Typically this is far less than the I/O cost, and is so in the cases discussed so far. It is possible for some execution plans that the CPU cost is significant, and this will increase the total cost of such an execution plan.

Just as Oracle can scan all blocks in a table, so it can scan all leaf blocks in an index. This scan can be performed in two different ways potentially - as a scan using single block reads, or a scan using multi-block reads as for a table scan. The former is termed an Index Full Scan, while the latter is termed an Index Fast Full Scan. The cost calculations of each are based on the number of Leaf Blocks in that particular index.

For a Full Scan the cost formula seems to be:

• #Levels + #Leaf Blocks

For a Fast Full Scan the cost formula uses MBRC as for a Full Table Scan:

• #Levels + (#Leaf Blocks * MREADTIM / (MBRC * SREADTIM))

Testing with different queries and different indexes shows this to be the case.

Note that I have seen Oracle report both access methods as an "INDEX FAST FULL SCAN" operation in an EXPLAIN PLAN (DBMS_STATS.DISPLAY_CURSOR). I wonder whether this is a bug within the labelling of operations within the Plan Table used?

Normally however indexes are used to implement a predicate condition, and restrict the number of rows being returned. To do this the index is traversed from the root block down through the levels of the index to the leaf blocks that contain the matching values. Not all leaf blocks will be visited - only those containing a matching entry for the predicate condition. The Oracle Optimizer terms this restriction on the number of matching entries the Filter Factor. It is the proportion of rows in the whole table that will match the predicate condition i.e. a value always less than 1. Thus the cost of using only the index itself is:

• #Levels + (#Leaf Blocks * Filter Factor)

In many situations some data needed for the query is not present in the index, and so the data row needs to be read from the table itself. Thus the cost increases by the cost of reading these data rows, which is essentially the number of rows matching the predicate condition:

• #Rows * Filter Factor

There are however several refinements which need to be made to these formulae to be reflect how the Optimizer actually costs the access paths.

First, it is possible that matching data rows are stored in the same data block. In such cases the data block is only read once, even though multiple data rows are used from it. Such clustering of similar values will reduce the number of data blocks that need to be read i.e. the read of one data block from disk can satisfy multiple entries from the same leaf block. Oracle calculates this clustering as a statistic for each index, and uses this to report the number of data blocks that would need to be read – the Clustering Factor. This is visible in the CLUSTERING_FACTOR column in the USER_INDEXES and USER_IND_STATISTICS data dictionary views.

For many indexes it will be the case that the Clustering Factor is the same value as the number of Rows in the table – no co-location of data values for that particular column. But for some indexes, the Clustering Factor will be much lower, such as an index on the date the data was loaded, or an incrementing sequential account number. The Clustering Factor Statistic factors in the benefits of the reduced disk I/O from this co-location of Index and Data entries, to better estimate the real disk I/O that would actually take place.

The final full index cost formula is thus:

• #Levels + (#Leaf Blocks * Filter Factor) + (Clustering Factor * Filter Factor)

Second the Filter Factor is calculated in different ways for different types of predicate conditions within a query. For now I will restrict myself to equality conditions (=), as they are the most common. Please read Wolfgang's Under The Hood paper for information on the Filter Factor for other conditions.

For a column with no Histograms (this is important), the Filter Factor for an equality condition will be the density of data values within that column - a measure of the proportion of data rows that have the same value for that column. This is true whether the condition uses a literal value or a bind variable. In turn the density value is simply the inverse of the number of distinct values in that column i.e. 1 / NDV. This count is available in the DISTINCT_KEYS column of USER_IND_STATISTICS and USER_INDEXES.

The Filter Factor can also be used to calculate the number of matching rows produced by the predicate condition i.e. the Cardinality of the result set. This is used by the Optimizer when multiple conditions are combined, either on the same table or joined tables.

Filter Factors on multiple conditions in a query are combined together according to the standard rules for probabilities:

• c1 AND c2 ==> FF1 * FF2
• c1 OR c2 ==> FF1 + FF2 – (FF1 * FF2) i.e. exclude duplicate matches

If the column has a Histogram on it, the Density value will be calculated from the Density values of each bucket within the Histogram that fall within the query range. This might be close to 1 / NDV for the whole table, or it might be different. That is one way in which Histograms can have such a big impact on query execution plans.

Examples

Using the index cost formula of:

• #Levels + (#Leaf Blocks * Filter Factor) + (Clustering Factor * Filter Factor)

For a query with a condition on column C3, which has an index on it with a Density of 0.001002, 250 Leaf Blocks, 1 Level and 100,000 rows and the same value for Clustering Factor the cost should be:

• 1 + 250 * 0.001002 + 100000 * 0.001002 = 1 + 0.2505 + 100.2 = 101.4505

The reported I/O cost by Oracle was 102, which agrees very closely with our calculated value. The difference is probably due to rounding errors. The expected cardinality is 100,000 * 0.001002 = 100.2.

Oracle Optimizer Plan Costing - Full Table Scans

Hopefully this is the start of a series on how the Oracle Cost Based Optimizer determines the cost of a particular execution plan for a SQL statement. Knowing how it arrives at the cost of each possible access path to a data set, we can better understand why a particular access path was chosen, and why an alternative access path had a higher cost. This information was kick started by A Look Under The Hood Of CBO: The 10053 Event by Wolfgang Breitling, and also information in Troubleshooting Oracle Performance by Christian Antognini, and refined by various tests I did.The Under the Hood paper is very good, and has a good description of how the Optimizer goes about costing different access paths to data sets. Unfortunately it seems to be based on Oracle 9i, and things have changed slightly in Oracle 10g. The principles are the same, but the trace information output by the optimizer has changed slightly.

For this post I will focus on how the optimizer works generally, and specifically how a Full Table Scan is costed. These will not be full, exhaustive explanations of the inner workings of the Oracle Cost Based Optimiser, but short and to the point descriptions of the key costings.

Plan Costing

The Optimizer itself costs all execution plans in terms of the number of disk I/Os involved, because these are generally the largest component of the execution plan cost. Other costs such as CPU costs are also included in the total plan cost, after being converted to an I/O count via a conversion value. When the lowest cost plan has been produced, this can be easily converted to an elapsed time value by simply multiplying the cost by an average I/O time value.

When producing an execution plan for a SQL query (queries are the most common and also the most complicated things that the Optimizer has to deal with), the Optimizer simply tries to produce all possible execution plans and cost each of them. From these it chooses the plan with the lowest cost. Clearly this could be quite an exhaustive way of doing things. So what the Optimizer actually does is to fully cost one execution plan, and then only partially cost the subsequent execution plans.

Each subsequent plan is costed as each step of the plan is determined by the Optimizer. If the partial cost of such a plan so far is greater than the current best plan, then it is abandoned. This early pruning avoids the optimizer wasting too much time on plans that are too costly. Likewise if a new plan is produced with a total cost less than the current best plan, then the new plan becomes the current best plan.

After considering all possible execution plans the optimizer will have the lowest cost execution plan for the SQL query.

The execution plans themselves are formed in an iterative fashion. First, for each table referenced in the SQL query the optimizer costs each potential access path to the data in that table. Indexes are considered if they can be used directly to implement a predicate - a filter condition within the SQL query restricting the rows returned. Then the optimizer considers each possible join combination between the tables in the SQL query, using each possible join method - Nested Loop, Sort Merge or Hash Join. These joins use some of the costs for accessing each of the tables determined eariler, combined according to how that join method works. Thus each possible join path (A to B to C, A to C to B, B to A to C, etc.) is costed in turn using each of the 3 possible join methods, to arrive at the lowest cost execution plan for the SQL query.

Full Table Scan

This is one access method to data in a table that is always available to the optimizer. Logically the cost is the number of disk I/Os required to read every data block in the table. The number of data blocks in a table is obtained from the BLOCKS column in USER_TABLES. It is as accurate as the last time you gathered statistics on that table. Oracle 10g has an automatic job that runs every night by default to update the statistics on tables that have changed significantly, to minimise the drift between actual table sizes and the statistics stored about them in the database.

An enhancement Oracle has is the ability to issue multi-block reads that read more than one block from disk in a single read request. This reduces the total number of disk I/Os needed. Thus the number of disk I/Os needed is reduced by the multi-block read count (MBRC), according to the formula:

• Blocks / MBRC

The Optimizer wants all costs to be in units of equal disk I/Os i.e. in units of single block reads. However, the time for a multi-block read is likely to be different – generally slightly longer given that more data is transferred. To convert a multi-block read cost into units of a single block read, the multi-block read cost is divided by the time for a multi-block read and multiplied by the time for a single block read. This adjustment means that the “cost” is now in units of cost of single block reads, as used by other access paths such as indexes.

Therefore the cost of a Full Table Scan is actually:

• (Blocks * MREADTIM) / (MBRC * SREADTIM)

MREADTIM and SREADTIM, as well as MBRC, are part of a set of statistics Oracle has about the relative performance of the computer system it is running on. These are termed the System Statistics, and are visible in sys.aux_stats$ or via the dbms_stats.get_system_stats procedure. Out of the box following installation, Oracle only has a minimal set of default values for some of these statistics - IOSEEKTIM, IOTFRSPEED and CPUSPEEDNW. All the other system statistics have no value. They can be set in a number of ways - the intended way being to get Oracle to measure these values from the system itself while it is executing some representative workload (these are termed Workload Statistics) - but they can be set manually if desired, or left unset.

Oracle uses those System Statistics that it has values for. For those with no value Oracle uses various substitution formulae to calculate values to use instead.

If there is a value for MBRC in the System Statistics then the Optimizer uses that value. Otherwise, it uses the value of the db_file_multiblock_read_count (DBFMBRC) initialization parameter.

If MREADTIM and SREADTIM do not have any values in the System Statistics, then the following substitutions are made:

• SREADTIM = IOSEEKTIM + (DB_BLOCK_SIZE / IOTFRSPEED)
• MREADTIM = IOSEEKTIM + (MBRC * DB_BLOCK_SIZE / IOTFRSPEED)

This is probably the general case on most systems - no Workload System Statistics are present (MBRC, SREADTIM, MREADTIM and others) - and only default values for IOSEEKTIM (10 milliseconds) and IOTFRSPEED (4 KB / millisecond). For an 8 KB block size and DBFMBRC of 8 this gives values for SREADTIM of 12 ms and for MREADTIM of 26 ms, and the ratio of MREADTIM to SREADTIM of 2.167.

A simple test shows this to be the case - a SELECT on a table with no indexes. The table I used had 1252 blocks of 8 KB each, and DBFMBRC was set to 8. No System Statistics had been collected, so only the defaults exist for IOSEEKTIM and IOTFRSPEED. Using the substituted formulae for MREADTIM and SREADTIM the calculated cost should be:

• (1252 * 26) / (8 * 12) = 32552 / 96 = 339.08

The reported cost by Oracle was 341, which is very close. The difference is due to various factors, such as rounding within the calculation, the optimizer probably costing an extra read for the table header (+1), and the optimizer adding in a CPU cost for processing the data.

Using these formulae and the values of the System Statistics, we can calculate for ourselves the expected cost of a Full Table Scan of any table.

System Activity Data - What is the System up to?

I'm always amazed at how many people do not know about the SAR utility on UNIX and Linux systems. It is a great little utility for collecting a lot of data about what is going on on a system. No, it is not the best possible tool for all such information, but it comes as standard on most UNIX systems and will give you most of what you want for very little effort on your part.

The problem we often deal with is that when running an application and taking application level measurements we are not sure what is happening lower down on the system, under the covers as it were. When the application performance is slow it would be nice to know if the computer system itself was very heavily loaded too, or whether the cause of the slowness lies somewhere else. Such relatively simple data about activity and resource usage on the system can help us establish what class of problem we have - a saturated resource in the system itself, or a badly behaving application.

To know what the computer system is up to we need to know about all of the resources in it - CPU, Memory, and Disks. And we need several different measurements on each resource - number of requests, elapsed times, and queue lengths. We also need an accurate timestamp with each of these measurements, to know when it occurred, and the period of time it covered.

All of this can be relatively easily achieved with SAR - the System Activity Reporter. It will collect and record a wide range of measurements on system resources, and the time when they occurred.

Behind the scenes SAR uses SADC - the System Activity Data Collector. And in fact it is SADC we are more concerned with than SAR. SAR simply extracts and formats the data you want from an SADC data set. We can run SADC to collect all the data it can about the system, at the frequency we want it collected (measurement period) and for the duration we want (how long until). SADC has a very simple set of options to it:

• /usr/lib/sa/sadc t n file

where

• t is the time duration between measurements i.e. the frequency
• n is the number of measurements to make in total
• file is the name of a file to write these measurements to

To not have SADC tie up a terminal window, it is often run in the background with the '&' specifier at the end of the command line - control then returns to the terminal window. This can also be used in command files and scripts.

The file produced by SACD contains binary data, not text data, and needs SAR to read it and format it as readable text.

• sar [-data_option] -f file

If no data option is specified it defaults to CPU (-u). The common data options are:

• -u CPU
• -d Disk I/O
• -r Physical Memory
• -p Virtual Memory Paging

Remember that the SADC file contains all the data collected, so you can analyse any sub-set of this data any time you want to, at any later point in time. That is the benefit of collecting all of the possible measurements together at the same time and then saving them to a file.

You can obviously use SADC to collect data whenever you have performance problems. But it is far better to run SADC all the time, so that you already have the data to analyse after someone reports a problem. One way to do this is to put an entry into a "crontab" file for use by the "cron" utility, which runs jobs at regular intervals. Putting an entry similar to the following into "crontab" for the system administrator for midnight would run SADC for 24 hours collecting measurements every minute. If this is too frequent just modify the time and number values by the same ratio, so that the two multiplied together give 86400 seconds (24 hours).

• /usr/lib/sa/sadc 60 1440 /usr/adm/sa/`uname -n`_`date +%y%m%d`.sad &

This will create a file named after the system and the current date in a central directory. Make sure there is enough space in that location, or change it to somewhere else. You will need to do housekeeping once in a while to purge and delete old data sets. This could also be done via another "cron" to delete files older than one or two months.

I have found SADC and SAR invaluable in a number of circumstances where I have been able to show that it was the underlying hardware that had performance issues, and not the application itself. And I have used it in the opposite manner too, to show that a poorly performing application was not suffering from running out of system resources or their slow performance. On most UNIX systems the impact of running SADC is minimal, as the UNIX kernel is already collecting all of these measurements anyway. The overhead is simply of SADC reading them from memory and writing them to disk at the frequency requested. And generally this is a very low and negligible overhead, compared to that of the application software itself.

Java Data Types and Oracle (2)

As I said before, when using a Java application against an Oracle database, the java.util.Date data type gets mapped to a java.sql.Timestamp within the layers above JDBC (this application uses an abstraction layer on top of JDBC), and in turn this comes through to Oracle as being of type TIMESTAMP when used against a bind variable in a SQL statement. When used within a WHERE clause, rather than truncate the TIMESTAMP to a DATE by losing the fractions of a second part, Oracle does the opposite and converts each DATE value read from the database to a TIMESTAMP value by adding on a zero sub-second part. The result of this is that any index on such a DATE column is not used by the optimizer in the execution plan for the query, because of the data type conversion.

Oracle themselves acknowledge that this is an issue in their JDBC FAQ and state that in the Oracle 11g JDBC drivers the mapping has reverted back to java.sql.Timestamp and Oracle's DATE being equivalent rather than different. In the meantime, those of us in the real world have to deal with real applications using the Oracle 10g drivers which map java.sql.Timestamp to Oracle's TIMESTAMP data type instead.

As I described before, we came up with a short term fix of creating a different index on the table being queried, with the DATE column as the last column in the index. This did have a major performance benefit (15 hours of the last run down to 2.5 hours with the new index), but was still not the optimal solution. Oracle was still doing an INDEX SKIP SCAN rather than an INDEX UNIQUE SCAN, and so was reading many more index entries than it needed to i.e. more Buffer Gets than it needed to.

I put together a Java program using JDBC to test the effects of using different Java data types (Classes really) and different JDBC settings. The simplest fix is to use the "V8Compatible" property as mentioned in the Oracle FAQ linked to earlier. You create the Property, set the "V8Compatible" value to "true" and then make your normal JDBC connection to Oracle (I've removed all error handling code in the following):

// Create and set V8Compatible property
Properties oraProperties = new Properties () ; // NEW
oraProperties.setProperty("oracle.jdbc.V8Compatible", "true") ; // NEW

// Standard JDBC connection code
OracleDataSource ods = new OracleDataSource();
ods.setURL(connect_string);
ods.setUser(username);
ods.setPassword(password);
// Set properties of the connection
ods.setConnectionProperties (connectionProperties) ; // NEW

Connection dbcon = ods.getConnection () ;

With no other changes than the 3 NEW lines indicated, the application's java.util.Date value now came through as an Oracle DATE after going through the intermediate mapping layers, and the original index was now correctly used in a UNIQUE SCAN.

This is clearly the easiest and most direct solution, and does what we want - all Java Date / Time values now come through mapped as Oracle DATE values, rather than TIMESTAMP values. Although the "V8Compatible" property is deprecated in Oracle 11g, this will have no effect as the behaviour of the Oracle 11g JDBC drivers has changed to what we want, and it can ignore the unneeded property setting.

The other possible solution, which is being investigated by those who know more about the Java abstraction layer API being used by the application than I do, is to get this abstraction layer to wrap all java.util.Date objects within oracle.sql.DATE objects. Thus the JDBC connection is only ever given oracle.sql.DATE values, which are direct equivalents of DATE values in the database. So again, any index would be used directly, and no data type conversions would take place within the Oracle database server.

However, the details of this look like they would still involve mapping a java.util.Date object to a java.sql.Timestamp first in the abstraction layer, and then wrapping this within an oracle.sql.DATE object. This is because oracle.sql.DATE has a constructor that takes a java.sql.Timestamp argument, allowing easy conversion. But it does not have a constructor that takes a java.util.Date argument, or any superclass of it. java.sql.Timestamp is a subclass of java.util.Date.

So for now we have one guaranteed long term fix with the "V8Compatible" property, and another possible fix by changing the mapping within the abstraction layer. So now it is up to the people that own the Java application code to deliver their preferred change, and then we can remove the extra index that we created as a short term fix.