Index Compression Part IV (Packt Like Sardines In a Crushd Tin Box) February 29, 2008
Posted by Richard Foote in Index Compression, Index Internals, Oracle Cost Based Optimizer, Oracle General, Oracle Indexes, Performance Tuning.17 comments
A great question by Brian Tkatch has convinced me there needs to be at least a Part IV in this particular mini-series. The basic question is what size does the column need to be for it to be effectively compressed ?
If a column is only just the one byte, then it can’t really be compressed as the prefix related overheads would likely make the exercise pointless, right ?
Well not quite …
True a larger column that is heavily repeated will yield a better return from compression than a smaller column, but even a single byte column could be effectively compressed, IF there are sufficient repeated values per index leaf block.
Previously, I illustrated a logical representation of how Oracle compresses a block. The following is more of a physical representation of a compressed block:
Prefix 0: David Bowie
0:0
: ROWID
1: 0
: ROWID
2: 0
: ROWID
3: 0
: ROWID
4: 0
: ROWID
Prefix 1: David Jones
5: 1
: ROWID
6: 1
: ROWID
7: 1
: ROWID
…
Remember, only the leading columns in an index can be compressed and index row entries must be sorted by these leading columns. Therefore each prefix entry is referenced by one or more logically consecutive index row entries and each index row entry can only have the one index prefix. The corresponding prefix for a specific index row entry is therefore simply the prefix entry that precedes it within the leaf block.
If we look at sample prefix entries:
prefix row#0[8030] flag: -P—-, lock: 0, len=6
col 0; len 3; (3): c2 08 43
prc 1
prefix row#1[8015] flag: -P—-, lock: 0, len=6
col 0; len 3; (3): c2 08 44
prc 1
Note that the prefix row#0 starts at address 8030 while the next prefix entry row#1 starts at address 8015. That’s a total of 15 byes and yet the length of the prefix entry is just 6. Where’s the other 9 bytes ?
Well note the prc value for prefix row#0 is 1 meaning this prefix entry is only referenced by the one index row, as is the next prefix entry as well. The leading column in this particular example is actually unique meaning each and every prefix entry only has one corresponding index row.
If we look at the corresponding row entry, guess what it’s length will be …
row#0[8021] flag: ——, lock: 0, len=9
col 0; len 6; (6): 04 81 aa 8b 00 69
psno 0
row#1[8006] flag: ——, lock: 0, len=9
col 0; len 6; (6): 04 81 aa 8b 00 6a
psno 1
If you guessed 9, well done. Note that it’s starting address is 8021, which is the starting address of the previous entry 3015 + 6 bytes for the prefix entry which equals 8021 (as Oracle actually fills index blocks from the “bottom up”). Note that index entry row#0 has a psno of 0 meaning it’s corresponding prefix entry references prefix row#0.
Note that the index row length of 9 is made up of 2 byes for locks and flags info, 6 byes for the rowid and 1 byte for the rowid length (as this index is a non-unique index, albeit with unique index values).
Therefore the psno value actually uses 0 bytes as its value can be purely derived from it’s position within the leaf block in relation to its parent prefix value.
Let’s now look at an index row entry with a leading column that is heavily repeated but only one byte in size.
row#0[8025] flag: ——, lock: 0, len=11
col 0; len 1; (1): 41
col 1; len 6; (6): 04 81 12 8a 02 67
row#1[8014] flag: ——, lock: 0, len=11
col 0; len 1; (1): 41
col 1; len 6; (6): 04 81 12 8a 02 68
row#2[8003] flag: ——, lock: 0, len=11
col 0; len 1; (1): 41
col 1; len 6; (6): 04 81 12 8a 02 69
Note the same leading column (hex 41) is repeated again and again within the leaf block and uses a total of 2 bytes of storage, 1 byte for the value and 1 byte for the column length. That means for each and every index row entry, this column uses 2 bytes. Note the length of the index row entries is currently 11 bytes.
Let’s look at the same index compressed.
prefix row#0[8032] flag: -P—-, lock: 0, len=4
col 0; len 1; (1): 41
prc 726
row#0[8023] flag: ——, lock: 0, len=9
col 0; len 6; (6): 04 81 12 8b 00 42
psno 0
row#1[8014] flag: ——, lock: 0, len=9
col 0; len 6; (6): 04 81 12 8b 00 43
psno 0
row#2[8005] flag: ——, lock: 0, len=9
col 0; len 6; (6): 04 81 12 8b 00 44
psno 0
First thing to note is that there is only the one prefix row entry for this particular leaf block and that all 727 index row entries all share the same prefix row entry.
The length of the prefix entry is 4, 2 bytes for these flags and locking info, 1 byte for the prefix column value and 1 bye for the prefix column length. That’s just 4, tiny little byes.
Note that each index row entry is now only 9 bytes reduced from 11 as we no longer need to store the 2 bytes for the repeated column entry. That means for a total overhead of 4 byes, we are able to save 2 bytes in each and every index row entry.
Not bad at all and as such represents a useful saving. In this particular example, the index reduced from 163 leaf blocks down to 138 leaf blocks, just by compressing a single byte column as the column has very low cardinality.
Note however if this leading column were unique for every row, we would increase the storage of this column from 2 bytes for every index row entry up to 4 bytes for every index row entry as every index entry would have it’s own associated prefix entry. That’s why compression can potentially increase the size of an index if the compressed column(s) has too high a cardinality due to the additional 2 byte overhead required to store all prefix row entries.
The following Index Compression Part IV demo shows all this in a little more detail.
There’s more to index (and indeed table) compression than simply compressing an index (or table) for the sake of it …
BTW, the spelling mistakes in the post title are fully intentional 😉
Oracle Diagnostic Tools – Some Random Thoughts (Hammer To Fall) February 26, 2008
Posted by Richard Foote in Oracle Cost Based Optimizer, Oracle General, Performance Tuning, Richard's Musings.37 comments
There’s been a bit of discussion lately and some interesting opinions aired, such as those by Daniel Fink , Doug Burns, and Alex Gorgachev regarding the whole issue of the usefulness or otherwise of various Oracle diagnostic tools (such as Statspack, AWR, ADDM, Extended Tracing, etc).
Are they really useful in diagnosing problems or do they simply provide a whole bunch of numbers that most folk can’t readily decipher ?
Boy, I could go on and on with this one …
IMHO, there’s no doubt that many (most even ?) people use many of these “diagnostic tools” incorrectly and use their view and perception of the data as some kind of justification for what really amounts to nothing more than a guess when attempting to determine the root cause and solution of a performance issue.
Look at all that time spent performing sequential reads, boy you need faster disks. Buffer Busy Waits are in your top 5 wait events, obviously need to add more freelists somewhere. Your session’s running slow eh, well statspack is showing enqueue waits times are really high, it’s probably that. If not, it might have something to do with those log file sync times (whatever they are).
I have no doubt about Mogens Norgaard’s assertion (as referred to by Daniel Fink) that if you take 2 people of the same skill in separate rooms and arm them with the same Statspack report, they would both come up with different suggestions on what needs to be done. I’ve lost count of the number of threads in forums that start with someone complaining about “performance”, posting a statspack report and ending up with 10 different people making 10 different suggestions.
I’ll digress somewhat, but this is a story I use to try and explain to my kids what it is I actually do.
Mum says she’s heading off to the local shops to get some milk for our breakfast cereal. The shops are close, a few minutes drive away and I expect she’ll be back in 10 minutes or so. 2 hours later, she finally gets home, drops off the milk and leaves again in a huff before we can ask what happened. Kids, my job is to find out what took her so long.
It’s at this point the kids say that we don’t normally have cereal, but toast anyways and if I’m angry at mum for taking so long I should have gone and got the milk myself, but I try to get the discussion back on track …
I know there was plenty of fuel in the car, the weather was fine and clear and that the traffic generally wasn’t too busy at the time. There’s also usually plenty of milk at the shop. Now I’ve been listening to the radio and have a pretty good idea of the overall traffic and weather conditions. There was a truck that overturned nearby, resulting in some pretty major traffic delays, causing lots of folk to run late.
So I “guess” it must have been the truck that likely caused the delay, right ?
The kids suggest it was probably someone she met and she just got caught up having a long chat. Then again, maybe the car broke down or maybe she didn’t have enough money and had to go to town to get to the bank or maybe …
The point of course is that we simply don’t know. Any diagnosis based on the data at hand would be nothing but a guess. Yes there maybe some historical additional reference we could use (like she sometimes gets caught up with someone for a chat) but it would still be a guess to assume it was the issue this time.
There maybe some “global” events taking place that could be a factor (such as the overturned truck, or really bad weather) but again, there’s nothing to directly suggest it’s the actual issue.
Yet how often do people when trying to determine the cause of specific performance issues turn to global, generalised, averaged to death statistics, charts and reports to diagnose the problem ? How often do people “hope” that because the weather looks bad, that it’s a likely cause of the problem. Or because the amount of traffic is more than a certain threshold or slower than a certain ratio that maybe that’s the cause of the issue.
How often do people make these (sometimes educated) guesses, get it wrong, apply a solution that makes no difference, take another stab, wrong again, yet another guess and yet another guess until eventually either they hit the right diagnosis and solution or the problem goes away (only to come back at some other point in time) …
A key issue is that many of these fancy diagnosis tools, reports and lists of statistics are used inappropriately. It’s a potential diagnostic tool but often the wrong tool for the problem at hand. A really really sharp and shiny and fancy looking saw when the problem is a “protruding nail” that needs to be hit with a hammer.
Another problem is that there’s generally no process or methodology associated with looking at these reports and charts and database wide statistics. As such they’re open to interpretation and differing views. Most databases can be improved somehow in all sorts of different ways but what is the precise reason for a specific (or general) database performance issue. Everyone is slightly sick or imperfect in some way or another (with the possible exception of David Bowie), but what exactly is it that’s killing us …
However the key problem is that often, very often, most of these diagnostic tools, reports and flashing screens don’t actually provide the necessary information to make an educated diagnosis. The answer to the problem is simply not to be found in statspack, or in the v$ views or on the radio or in the weather report. 10 people can look at a statspack report and 10 different solutions can improve the database in 10 different ways but none of them may necessarily solve the specific database performance issue that’s causing stress to the business.
The actual issue is buried and hidden and drowned out in a sea of numbers, averages, statistics and people who are all predominately able to get their milk in a timely manner.
Not that a “saw” is a totally useless tool. Jonathan Lewis recently referenced a rather nice article by Connie Green on how a saw can be used effectively for slicing through some issues. The traffic report can be a useful source of information.
However, the Oracle marketing machine has certainly been promoting many of these “shiny saws” to the point where many see them as being the tools of choice, no matter the performance issue at hand. Oracle says they provide great, “useful” information so they must be really really useful in solving my performance issues. The answer to my problems has got to be in here somewhere right, if I just know where to look ?
The problem is not necessarily with the diagnostic tools themselves but in the manner in which they’re often used and attempted to be applied to specific issues. A saw is not particularly useful at driving in a nail. You need a hammer for that …
Back to my little story.
Kids, imagine if we had a camera on mum and saw exactly what she was doing for the entire time she was away getting the milk. We could actually see where all the time was spent, see exactly what happened in the 2 hours she was away. We can account for every moment and see exactly what happened during the 1 hour and 50 minutes of “lost” time.
Then we could see that in fact, the car worked fine, she took another route to the local shops bypassing the truck, got the milk at the counter straightaway. However, when she got back to the car she had a problem unlocking the car door as the key was quite bent and got to the point where she just couldn’t open the door.
In fact, out of the 2 hours, 1 hour and 50 minutes was spent frustratingly trying to open the car door.
So it was a “locking” problem all along 😉
No guesses. No assumptions. No ifs and maybes. We know exactly the root cause of the problem.
Therefore no wasted effort and time filling the car up with petrol, no need to drive the longer way around to miss that interchange, no need to demand she stop chatting at the shops (thank goodness), none of which if applied would have actually resolved the issue, none of which would have prevented the same problem from reoccurring again next time …
And that of course is the information Extended Tracing can provide. IMHO, if only this hammer were used more often, if this tool was considered more often to knock in that “protruding nail”, if people posted an extended trace file more frequently, then it would be a big step in the right general direction in correctly diagnosing problems.
Is a 10046 event, DBMS_SUPPORT, DBMS_MONITOR, etc. perfect ? No, of course not. Although there are constant improvements with most releases, it can be difficult to setup in some environments and configurations, it can be difficult to interpret and piece together, it can tell you what the issue might be without telling why, it may only tell you that the problem isn’t Oracle related (although that in itself can be useful), it requires the issue to generally be repeatable, it has overheads, etc. etc.
However, in most scenarios, when applied appropriately, it can provide the necessary information to diagnose the exact cause of performance issues. In most scenarios, it can take the guess work out of the equation and save time by driving one directly to the correct diagnosis, first time.
I’ll add this point in as well. Most people working on other software solutions trying to resolve performance issues, would faint with disbelief at the level of instrumentation available in Oracle. No it’s not perfect, but boy, things could be a lot lot worse.
My general recommendation is this. When you want to determine and diagnose the cause of specific or general database performance issues, consider extended tracing as the first tool within the toolkit. You want to know why the milk took so long, ensure you have a camera available and record what happens.
If you want to be on the lookout for low hanging fruit, if you want to have a global view of the general road conditions, of the weather, of the fuel left in the tank, and proactively see what areas in a database may benefit from some attention, then look at using “saws” such as Statspack, ADDM, etc.
IMHO, if the Oracle diagnostic tools were used more appropriately, if more people read Connie Green’s article, if more people investigated and applied the use of extended tracing, then I’m sure the perception of their usefulness would increase as well.
Meanwhile, I’m going to use a hammer to see if I can get this damn key straightened out …
BTW, the kids think I’m some kind of private investigator who follows and monitors people all day long so I guess I need to try again in explaining what it is I actually do …
Index Compression Part III (2+2=5) February 22, 2008
Posted by Richard Foote in Index Compression, Index Internals, Oracle General, Oracle Indexes, Performance Tuning.1 comment so far
As previously discussed, compression is only beneficial when the compressed columns have repeated values within an index leaf block. If a compressed column has repeated values, Oracle will basically store the one copy of the compressed column (or columns) as a prefix entry within a leaf block and each index row entry will then be associated with its corresponding prefix entry.
That being the case, it makes no sense in compressing a single column Unique index. Each index entry must be unique, there can’t be any repeatable, duplicate column values. Therefore compression will be not only totally ineffective, but would actually result in an index structure that increases rather than decreases in size due to the extra overheads associated with having a prefix index entry for each and every index row entry.
It also makes no sense in compressing every column in a concatenated, multi-column Unique index. For exactly the same reasons. Each compressed index column combination must be unique and would result in a prefix entry for each and every index row entry. Compression would be worse than useless and result in an increased index structure.
However, Oracle does its best to protect ourselves from ourselves.
For a start, it does not allow one to create a compressed index on a single column Unique index. Attempt to do so and Oracle generates an “ORA-25193: cannot use COMPRESS option for a single column key”. Hey, even the error message is nice and meaningful.
If the Unique index has multiple columns, the default prefix length value (number of compressed columns) is the number of indexed columns minus one, not all columns as it is for a Non-Unique index. See, Oracle is doing its best here to prevent a useless attempt at index compression.
If you specify a prefix length value equal or greater than the number of columns in a Unique index, Oracle generates an “ORA-25194: invalid COMPRESS prefix length value”. These are not restrictions but designed to stop the creation of inefficient compressed indexes.
Note however that Non-Unique indexes can be used to police primary Key (PK) and Unique Key (UK) constraints. I’ve discussed all this previously. The constraints might be Unique, the data might be unique but the index is Non-Unique and so these “protections” fly out the window. There is nothing stopping one creating a single column compressed Non-Unique index to police a PK or UK constraint. There’s nothing preventing you from creating a concatenated, Non-Unique index with all columns compressed, from policing a PK or UK constraint. In fact, you can even create a fully compressed Non-Unique index at the same time as the PK or UK constraint with Oracle’s extended constraint and index creation syntax.
Nothing stopping you, except perhaps the realisation that it would be a very bad and futile thing to implement as the resultant index will be guaranteed to be less efficient than an equivalent nocompress index.
Yes, it might make sense to compress just the leading columns of a Unique index or a Non-Unique index that’s policing a PK or UK constraint, if such leading columns have sufficient repeating values to make compression effective. But it would simply not make sense to compress all columns from such indexes.
See this demo Index Compression Part III on how compression works and doesn’t work for Unique Indexes.
In Part IV, we’ll look at the issue of what specific columns might benefit from compression and look a little closer at how storage is actually saved.
Whoever said there can’t possibly be enough things to discuss on a Blog that focuses mainly on Oracle indexes 😉
Index Compression Part II (Down Is The New Up) February 20, 2008
Posted by Richard Foote in Index Compression, Oracle Cost Based Optimizer, Oracle General, Oracle Indexes, Performance Tuning.12 comments
Compression can be very beneficial when the compressed columns of an index have many repeated values within a leaf block as these repeated values are only stored once and subsequently referred to within the index row entries themselves.
However, when the leading column is very selective or the compressed columns are very selective and have very few or possibly no repeating values in an index, then we have a problem.
In these scenarios, Oracle will create a massive prefix table, housing most if not all the individual column values anyways, as the prefix table stores all unique combinations of compressed column values within a leaf block.
The index row entries will point or refer to a prefix entry which is hardly shared (if at all) by other index row entries.
Compression in these cases is not only pointless but potentially worse than pointless as we now not only have to store a similar amount of index column data anyways, but additional compression related overheads such as those associated with the prefix table entries.
Net result can be no effective compression or indeed leaf blocks that can no longer store as many index values due to these associated compression overheads, resulting in indexes increasing rather than decreasing in size as a consequence.
For concatenated, multi-column indexes, the order of the indexed columns can make a huge difference to the compression of an index. If the leading column or columns (depending on how many columns are compressed) have many repeated column value combinations, not a problem as compression will be effective.
However if the leading column is very selective, then compression by definition will be ineffective, as there must be many distinct column values in the prefix table as a result which are less likely to shared by the index row entries.
For compression to be effective, the prefix table should have considerably fewer entries than index row entries in most leaf blocks. If there are approximately (say) 200 index entries per no-compressed leaf block, you want the number of distinct column combinations within the leaf block to be substantially less than 200.
For index compression to be feasible, ensure low cardinality columns are the leading columns in a concatenated index, else compression may be futile or worse.
See this demo on Index Compression Part II to see how compressing an index can be either effective or plain terrible and how the order of columns in a concatenated index can make all the difference to the effectiveness of index compression.
Next I’ll cover index compression with Unique Indexes …
Index Compression Part I (Low) February 17, 2008
Posted by Richard Foote in Index Compression, Oracle Cost Based Optimizer, Oracle General, Oracle Indexes, Performance Tuning.26 comments
Index compression is perhaps one of the most under used and neglected index options available. It has the potential to substantially reduce the overall size of Non-Unique indexes and multi-column Unique indexes, in some scenarios dramatically so. A smaller index, especially if it stays permanently smaller without any subsequent expensive maintenance operations, it always a nice thing. Not only will it potentially save storage, but if the resultant index contains fewer leaf blocks, that’s potentially fewer LIOs and from the Cost Based Optimizer’s point of view, potentially a cheaper execution plan option.
All possible without a single index rebuild in sight …
However like most things Oracle, index compression also has the potential to be misused and to cause rather than solve problems. So it really helps to understand how index compression works and how it’s actually implemented before we rush into anything.
The first point to understand is that index compression is implemented at the index block level. Basically, Oracle stores each distinct combination of compressed column values found within a specific index leaf block in a “Prefix” table within the leaf block and assigns each combination a unique prefix number.
The more numbers of distinct compressed column values, the more entries in the prefix table and the larger the prefixed related data. The fewer numbers of distinct compressed column values, the fewer entries in the prefix table and the smaller the prefix related data. Generally, the fewer entries in the prefix table, the better the compression.
Oracle now no longer stores these compressed columns within the actual index row entries. These compressed columns are substituted and referenced with the details stored in the prefix table entry, which are shared by all index row entries with the same corresponding prefix value.
Only leading columns (which in a Non-Unique Index can potentially be all the columns in an index, in a Unique Index can potentially be all but the last column in the index) can be compressed. Therefore, the prefix table is in the same logical order as they would appear in the index row entries. The values of the prefix values always appear within the index row entries in a sequential manner, noting that (hopefully) several row entries share the same prefix number.
Let’s say we currently have a nocompress Non-Unique index on a NAME column with the following entries:
0: David Bowie
: ROWID
1: David Bowie
: ROWID
2: David Bowie
: ROWID
3: David Bowie
: ROWID
4: David Bowie
: ROWID
5: David Jones
: ROWID
6: David Jones
: ROWID
7: David Jones
: ROWID
After the index is compressed, the leaf block entries would look logically something like this:
Prefix
0: David Bowie
1: David Jones
—
0:0
: ROWID
1: 0
: ROWID
2: 0
: ROWID
3: 0
: ROWID
4: 0
: ROWID
5: 1
: ROWID
6: 1
: ROWID
7: 1
: ROWID
…
Importantly, each distinct combination of compressed column values is now stored just the once within an individual index leaf block. In the example above, we previously stored “David Bowie” 5 times. In the compressed index leaf block, we now only store “David Bowie” once, with the prefix value now being referenced by each index entry instead.
The net result being we can now (hopefully) store many more index entries per leaf block meaning we don’t need as many leaf blocks in our index.
To compress an index, simply specify the COMPRESS option:
CREATE INDEX bowie_table_i ON bowie_table(col1, col2) COMPRESS 2;
The number after the COMPRESS keyword denotes how many columns to compress. The default is all columns in a Non-Unique index and all columns except the last column in a Unique index.
This demo, Index Compression Part I shows how an appropriately compressed index can substantially reduce the overall size of an index. It also shows a couple of index leaf block dumps to highlight how index compression is implemented.
In Part II, I’ll show you how you can really stuff things up by implementing index compression totally inappropriately …
Clustering Factor: A Consideration in Concatenated Index Leading Column Decision (Sweet Thing) February 15, 2008
Posted by Richard Foote in Clustering Factor, Concatenated Indexes, Oracle Cost Based Optimizer, Oracle General, Oracle Indexes, Performance Tuning.14 comments
Short but sweet today.
I last discussed how high cardinality columns shouldn’t necessarily be in the leading column of a concatenated index as they don’t provide the performance benefit as sometimes claimed.
If all things are equal and the columns in the concatenated index are all likely to be referenced, a simple consideration that is often forgotten when deciding which column to have as the leading index column is the Clustering Factor of the corresponding columns.
As previously discussed, the Clustering Factor determines how well aligned or ordered the index entries are in relation to the rows in the parent table. So if the rows are ordered within the table on a particular column or columns (such as a sequential ID column, a monotonically increasing date or time-stamp, etc), then an index on these columns is likely to have a very good Clustering Factor. Consequently less IOs will be required to retrieve all the required rows via the index as all the required rows will be housed in relatively few, well clustered data blocks.
It therefore makes sense to at least consider the Clustering Factor of the various columns in a concatenated index. Why ? Because if the leading column has a very good Clustering Factor, the concatenated index by definition must also have a very good Clustering Factor as all indexes are primarily ordered based on the leading indexed column. A concatenated index with a good Clustering Factor is going to be more efficient in retrieving rows from the table and more importantly, will be considered more desirably by the CBO when costing access path options.
Of course, the opposite is also true. By having a leading column with a poor Clustering Factor will mean the concatenated index will have a poor Clustering Factor, making it less efficient and less likely to be considered by the CBO.
As such, the Clustering Factor of each corresponding column in a concatenated index is at least worthy of some consideration when making the decision on how best to order the indexed columns.
This demo on Index Column Order and Clustering Factor shows how the order of columns in a concatenated index has a big impact on the Clustering Factor of the resultant index.
UPDATE: However as Tom Kyte has stated in the comments, in virtually all cases, the Clustering Factor is not really a factor (yes, pun fully intended) as subsequently columns are generally going to impact the CF anyways or the selectivity of the index is such that the improved CF is not relevant anyways.
More relevant considerations regarding the ordering of columns in an index coming I promise 🙂
It’s Less Efficient To Have Low Cardinality Leading Columns In An Index (Right) ? February 13, 2008
Posted by Richard Foote in Concatenated Indexes, Index Internals, Oracle General, Oracle Indexes, Oracle Myths, Performance Tuning.26 comments
A common myth or mis-perception is that when deciding how to order the columns in a concatenated, multi-column index, one should avoid placing low cardinality columns in front.
For example, if you want to create an index on two columns, column ID which has many many distinct values and column CODE which has very few distinct values, create the index as (ID, CODE) as it’ll be far more efficient than a corresponding index on (CODE, ID).
The reasoning goes that by creating the (CODE, ID) index, one decreases the performance and efficiency of using the index as Oracle will have to scan through multiple index leaf blocks containing the low cardinality column, until it eventually finds the specific index entries of interest.
Or so the theory goes …
In actual fact, there’s no real difference in navigating to the specific leaf block of interest for an index on (ID, CODE) compared to an index based on (CODE, ID), providing both indexed columns are known.
The important fact that’s missed is that the branch index entries contain column entries based on all indexed columns, or at least on as much as is necessary to uniquely identify the required navigational path. Therefore, Oracle can directly navigate to the leaf block of interest, no matter the index order, providing all index column values are know.
The only slight overhead that an index based on (CODE,ID) will have is that these branch index entries are going to be somewhat larger as it will likely require both columns for the branch index entries but likely only the one column the other way around. However, branch blocks usually take up a small percentage of the overall index structure and this (usually) minor overhead is very unlikely to make a difference to the index height.
This demo on Index Column Cardinality Order shows how Oracle navigates to a specific leaf block of interest in the same manner and with the same costs, regardless of the ordering of low and high cardinality columns in the index. It also shows and describes a couple of index branch block dumps to highlight how Oracle uses the column values to define the necessary navigational path.
So the high cardinality column shouldn’t necessarily be the column given leading column status.
In actual fact there are a number of good reasons why the low cardinality column could be considered as the better option as the leading column. For a start, the index can be compressed much more efficiently if the leading column has lower cardinality. Also, an Index Skip Scan can at least be considered if the leading column has lower cardinality.
Of course, the ordering of columns in an index can be very significant and can make a huge difference to the possible efficiency of an index for other key reasons as well. Whether the leading column is always going to be a known value is an important consideration, as is the clustering factor of the leading column.
All good discussions for another day 🙂
Index Create and Rebuild Locking Improvements in 11g (Ch Ch Ch Changes) February 11, 2008
Posted by Richard Foote in 11g, Index Rebuild, Locking Issues, Oracle General, Oracle Indexes.20 comments
Although the CREATE INDEX … ONLINE and ALTER INDEX … REBUILD ONLINE options have been available for a long while, they can still introduce locking issues in highly active databases.
Oracle requires a table lock on the index base table at the start of the CREATE or REBUILD process (to guarantee DD information) and a lock at the end of the process (to merge index changes made during the rebuild into the final index structure).
These locks have two implications. Firstly, if there’s an active transaction on the base table of the index being created or rebuilt at the time one of these locks is required, the indexing process will hang. This will of course impact the time it takes to complete the indexing process. However the second far more serious issue is that any other active transactions on the base table starting after the indexing process hangs will likewise be locked and be prevented from continuing, until the indexing process obtains and releases its locks. In highly concurrent environments with many transactions, this can cause serious disruptions to the response times of these impacted transactions. Of course, depending on the time the initial locking transactions take to commit or rollback, this backlog of locked transactions can be quite significant.
Oracle11g has made some improvements in the locking implications regarding creating or rebuilding indexes online.
During the creation or rebuilding of an index online, Oracle still requires two associated table locks on the base table at the start and end of indexing process. If there’s an active transaction on the base table at the time one of these locks is required, the indexing process will still hang as its done previously until all these prior active transactions have completed. No change so far.
However, if the indexing process has been locked out and subsequent transactions relating to the base table start afterwards, these transactions will no longer in turn be locked out by the indexing table locks and are able to complete successfully. The indexing process no longer impacts other concurrent transactions on the base table, it will be the only process potentially left hanging while waiting to acquire its associated lock resource.
This means it may not be quite so “risky” to urgently introduce that new index or rebuild that troublesome index during core business hours due to the reduced locking implications introduced in 11g.
See this demo for Index Rebuild Locking Issues in 10g and the 11g Improvements.
Does this means we can now simply rebuild all our indexes, whenever ? Ummmm, no 😉
Index Rebuild vs. Coalesce vs. Shrink Space (Pigs – 3 Different Ones) February 8, 2008
Posted by Richard Foote in Index Coalesce, Index Rebuild, Index Shrink, Oracle General, Oracle Indexes, Performance Tuning.33 comments
Previously, I discussed how an ALTER INDEX … COALESCE is going to be less expensive in terms of using resources than an equivalent ALTER INDEX … SHRINK SPACE COMPACT (or ALTER INDEX … SHRINK SPACE) as the Coalesce doesn’t have to concern itself with ensuring all leaf blocks at the physical end of the index segment have all been moved to allow for the storage to be de-allocated from the index segment. If you just want to de-fragment an index and not necessarily reduce the overall space allocated to the segment, use Coalesce rather than the Shrink options as it’s cheaper.
But what about an ALTER INDEX … REBUILD, when, if ever, should it be used ?
Well the answer is as with most things Oracle, it depends.
Scenario One.
We have a table and the application deletes historical data but in a manner in which leaf blocks are not being entirely emptied. Basically, older stuff is removed, but it’s only removed in a random manner, from approximately the “earlier” 10% of the table. The index is sequenced which means only those leaf blocks in the “left-most” 10% of the index structure are impacted but all this deleted space is “deadwood” as new index entries are only being inserted into the “right-most” part of the index.
Note that basically 90% of the index is fine and very well utilised, it’s only 10% of the index that’s problematic. Of the problem 10% of leaf blocks, there’s plenty of free or deleted space, with many leaf blocks almost but not quite empty.
Coalesce (and indeed Shrink) will basically run through these 10% of fragmented leaf blocks and will merge the index row entries into as few leaf blocks as possible. With the 90% of blocks that are fine, Coalesce will basically read and then ignore them from any processing as there’s nothing that can be done for them.
Rebuild on the other hand will take an entirely different approach. It will (generally) read the entire existing index structure and will build a brand new, bright and shining index segment. As part of this process, it will rebuild the entire index, it has no choice (assuming the index isn’t partitioned, but that’s another story) and will rebuild the 90% of the index that was actually perfect to begin with. Rebuilding 90% of something that doesn’t need rebuilding doesn’t sound particularly efficient and indeed it isn’t. As a result, the index rebuild will use substantially more resources and generate substantially more redo than an equivalent Coalesce (or Shrink Space).
Scenario Two.
We have an application that deletes data and it deletes data throughout the entire index structure. The deletes are significant with a substantial proportion of the overall rows having been deleted. Additionally, the table is not going to be repopulated with anything like the same volume of data or it won’t be repopulated for a substantial period of time. As such, all this deleted index space is “deadwood” as it’s not going to be used any time soon, if at all.
Now typically in this sort of scenario, it’s of course the table as much as the associated indexes that needs to be rebuilt. That’s a key point. However, maybe Full Table Scans are not an issue for this table so the wasted space in the table is not of urgent concern. Maybe the table in not in an ASSM tablespace or in a database that supports a Table Shrink command and maybe moving the table is not an immediate option due to availability concerns. For whatever reason (or lack of reason), the index needs to be de-fragmented.
Note it’s the entire index that’s problematic here and there could be portions of the index that have very few remaining index entries.
Now poor Coalesce (and indeed Shrink) has a bit of an issue here. They both merge index entries from two blocks into the one block where it can. However, if leaf blocks are really empty, these merged index entries may in turn be merged and moved again with index entries from yet another leaf block. And maybe yet again with another leaf block. And again and again … So a specific index entry may actually be moved into several different leaf blocks during the entire process. Each of these moves requires resources and generates redo and takes time.
Now the rebuild has an entirely different approach. As mentioned, it will basically (generally) read the entire exisiting index structure and will build a brand new one, but importantly as it does so will only have to locate a specific index entry once and once only. Also, as it’s the entire index structure that’s problematic, there’s no issue with fixing the entire index, as it’s all “broken”.
As a result of only having to deal with an existing index entry the once vs. the Coalesce which may relocate a specific index entry many times, the index rebuild is going to be substantially more efficient and potentially use significantly less resources and generate less redo.
This demo of the Differences between a Coalesce, Shrink Space and Rebuild shows when one out performs the other.
Basically, Coalesce is particularly efficient and uses less resources when the percentage of the overall index structure that’s problematic and fragmented is relatively small (less than approximately 20-25% of leaf blocks). Rebuild is particularly efficient when the percentage of the overall index structure that’s problematic and fragmented is relatively large and the average degree of fragmentation within an index leaf block is relatively high. Note Pre 10g, an index needed to have at least 50% free space less pctfree in neighbouring leaf blocks for a Coalesce to be effective.
Now Rebuild (and Rebuild Online) potentially have locking implications that need to be considered although as we’ll see later, 11g has addressed some of these issues …
Differences and Similarities Between Index Coalesce and Shrink Space February 6, 2008
Posted by Richard Foote in Index Coalesce, Index Shrink, Oracle General, Oracle Indexes, Performance Tuning.8 comments
As already discussed, ALTER INDEX COALESCE in 10g onwards works in a very similar manner to ALTER INDEX SHRINK SPACE.
However, there are a number of key differences.
The first thing to point out is that each command has a slightly different purpose.
Coalesce is designed specifically to reduce fragmentation within an index but not to deallocate any freed up blocks which are placed on the freelist and recycled by subsequent block splits.
Shrink is designed specifically to reduce the overall size of an index segment, resetting the High Water Mark (HWM) and releasing any excess storage as necessary.
The key difference being that Shrink must reorganise the index leaf blocks in such a way that all the freed up, now empty blocks are all grouped together at “one end” of the index segment. All these blocks can then be deallocated and removed from the index segment. This means that specific leaf block entries must be removed from these specific blocks, in order to free up the leaf blocks in this manner.
Although Coalesce in 10g performs the operation in a similar manner to that of the Shrink Space, it can be more “lazy” in how it deals with the subsequent empty blocks and places then on the segment freelist as necessary.
COALESCE and SHRINK SPACE COMPACT are logically equivalent commands. Both options will “defragment” an index by “merging” index entries where possible thus reducing the number of blocks within the logical index structure. Both will result in the same number of leaf blocks within the index and both will result in the index height not being changed.
However, there are two key differences.
1) The SHRINK SPACE COMPACT option has the disadvantage of being more expensive to process as it has to concern itself with ensuring all necessary blocks can be emptied from the physical “end” of the index segment to be subsequently deallocated. This will result in more undo and redo being generated during the defragmentation of the index than would have been generated by the same corresponding COALESCE command.
2) The SHRINK SPACE COMPACT option has the advantage of being able to immediately deallocate the empty blocks, thereby reducing the actual size of the index segment by issuing a subsequent SHRINK SPACE option (although of course this can be performed in the one step by issuing SHRINK SPACE in the first place). However, the COALESCE option will not be able to just deallocate the free space. A subsequent Index SHRINK SPACE command on a previously coalesced index will require additional undo and redo than that of a previously “Shrunk” index as the necessary empty blocks are removed from the freelist and redistributed to allow for the de-allocation of blocks and the resetting of the High Water Mark of the index segment.
Note also that the Shrink option can only be used in Automatic Segment Space Management (ASSM) tablespaces.
Use Coalesce when the intent is to just defragment an index, knowing that the freed leaf blocks will be recycled by subsequent block splits, as it uses less resources than an equivalent Index Shrink Space.
Use Shrink Space when the intent is to reduce the actual storage allocated to an index, for example in the scenario where a table has permanently reduced its size and the index is unlikely to reuse the freed storage.
This demo highlights the Differences (and similarities) between an Index Coalesce and an Index Shrink Space.
Note however, that an index REBUILD might actually use substantially less resources than either a Coalesce or a Shrink Space and might reduce the height of an index as well.
But that’s a discussion for another day …
ALTER INDEX COALESCE: 10g Improvements (Jump They Say) February 5, 2008
Posted by Richard Foote in Index Coalesce, Oracle General, Oracle Indexes, Performance Tuning.2 comments
I thought it might be worth mentioning some interesting changes in the manner in which the ALTER INDEX … COALESCE command works since Oracle 10g.
Basically the purpose of the COALESCE option is to reduce free space within the Leaf Blocks of an index. This is achieved by effectively performing a Full Index Scan of the leaf blocks, comparing the free space available in neighbouring blocks. In 9i, the basic method was to logically start with the left most leaf block and see if it could be coalesced or merged with the 2nd left most block. This required the sum of used space within these 2 blocks to be less than 100% of a block less the PCTFREE value. If so, the contents were merged with the contents of one block placed in the other and with the now empty leaf block removed from the index structure and placed on the index freelist.
It then looked at the 2nd leaf block (which might now be the first block if previously coalesced) and 3rd leaf blocks to see if these could be coalesced. If so they were merged and the empty block placed on the freelist.
And so on and so on until all leaf blocks had been traversed and all possible leaf blocks coalesced.
Note branch blocks are not directly merged during this process, except to be updated with modified pointer information if a leaf block coalesce had taken place. However, if enough leaf blocks are removed such that the branch block contains no more pointers to leaf blocks (or other intermediate branch blocks), it’s also removed from the index structure. However, there must always be at least one branch block from each level remaining hence the height of an index always remains the same during a coalesce operation.
Note if no leaf block had 50% or more free space, nothing would be coalesced as no two consecutive leaf blocks would have sufficient free space in which to be coalesced.
In 10g, the Coalesce operation has been modified somewhat.
An index no longer requires the sum of used space plus PCTFREE in adjacent blocks to be less than 100% of a block be effectively coalesced. For example, the free space in a block can be 25% in one leaf block and just 25% in the adjacent block (hence the combined used space alone being 150% of a block) and 10g can effectively coalesce these leaf blocks together.
This demo show how Coalesce differs between a 9i (9.2.0.7) and a 10g (10.2.0.3) database.
10g introduced the concept of being able to SHRINK an index and the Coalesce option can be viewed as now being very similar to an index Shrink command. Similar but not quite the same.
I’ll cover the similarities and differences between a Coalesce and a Shrink in the next day or two …
Bitmap Indexes With Many Distinct Column Values (Wots…uh the deal) February 1, 2008
Posted by Richard Foote in Bitmap Indexes, Oracle General, Oracle Indexes, Oracle Myths.29 comments
In the seemingly never ending list of 8 things one may not have known about indexes, Number 3 stated:
“Bitmap Indexes can be extremely useful and beneficial even if the column contains thousands of distinct values”.
On the surface, this may seem like a somewhat strange thing to suggest to many folk. It seems to be stated in numerous places that Bitmap indexes are only really beneficial with columns that have low numbers of distinct values. For example, a column called GENDER (I was going to use another word but I have to deal with enough spam messages as it is 🙂 ) has only a few distinct values, so it would be perfect for a Bitmap Index.
Columns that have say 5 or 10 or maybe 20 distinct values should all be OK. But what if a column has 100 distinct values, that might just be pushing it. A column with 1000 distinct values would obviously be totally inappropriate. I would have to be some kind of deranged fool for even contemplating and suggesting a column with 10,000 distinct values, right !!
A Bitmap Index is actually a B-Tree index in it’s basic structure and shape. It has index branch blocks that point to index leaf blocks that have all the necessary index information stored in an ordered and sorted manner. However, in the leaf blocks, a conventional B-Tree index basically stores the indexed column values followed by its corresponding rowid. A bitmap index differs considerably and basically stores in the leaf blocks for each distinct column, the column value followed by a starting and ending rowid that specifies a range of possible rowids within the table followed by a series of bits that denotes for each possible rowid within the range whether the row contains the column value (1) or not (0). If the index entry is larger than roughly half the index block size, another bitmap “piece” is created for the index entry, specifying a different range of rowids with corresponding bitmaps.
The “biggest” component of the index entry is thus this series of bits. But most of the values will be zeros (as a specific row can only have at most the one value of the column) and all these zeros can be compressed quite efficiently by Oracle within the index entry.
So having lots of distinct column values means having lots of index entries with lots of rowid ranges with lots of bitmaps. So a column with anything approaching 10,000 values would be totally inappropriate, right ?
Well take a look at this demo comparing a B-Tree Index vs. a Bitmap Index for a column that has 10,000 distinct values and you might just be surprised.
The table contains 1 Million rows and one of the columns is a NUMBER field that has 10,000 distinct values (hence a Density value of 1%).
The B-Tree Index required 2,090 leaf blocks to store the index and an equality query returning the expected 100 rows requires 19 consistent reads. Not too bad.
However, the equivalent Bitmap Index required just 56 leaf blocks and an equality query returning the same 100 rows does so with just 11 consistent reads.
Ummm, perhaps bitmaps indexes don’t require such low numbers of distinct column values to be useful after all …
A few points to ponder on from this specific example.
The B-Tree index had to store 1,000,000 index values, once for each and every not null row in the parent table. The Bitmap Index only had to store the index values 10,000 times, once for each unique occurrence of the column value (although there may be times when this ratio may be higher)
The B-Tree index had to stored 1,000,000 rowids, once for each and every index row entry. The Bitmap Index only had to store a pair of rowid values for each unique occurrence of the column value (although there may be times when Bitmap Indexes need to store more than one pair of rowids per index value).
If the rows in the table are clustered together based on the index column value, it means the zeros in the bitmap index can be nice and continuous within the bitmap string and so will compress nicely. Therefore, the manner in which the rows are ordered in the table will have a direct impact in how efficient the Bitmap Index can be compressed.
There’s lots and lots of interesting things to discuss about Bitmap Indexes. For now, just note the next time you read Bitmap Indexes should only be used for columns with few distinct values, you may want to get some clarification on what is meant exactly by “few” …
Richard Foote's Oracle Blog 