Sunday, 10 May 2009

Oracle Single Table Hash Clusters are Faster.

This post is about Single Table Hash Clusters.

It is also about The Fastest way to get to 1 single Record of data.
I will try to prove that with a demo.

This post (a bit of a rant, as usual) is prompted by several things:
Prompted by Richard Foote (Recommended reading), who justly argues that Every Block Get counts and who is on a mission to Educate us on the correct use of Indexes.
Prompted by a few reactions to my Endinburgh Presentation about (cost based-) optimized access to data. It all starts with good access-paths to your data.
Prompted by a client with 24 CPUs in a database-server, trying to squeeze the last milliseconds out of 25 million (business-)transactions per hour. (how many app-servers, JVMs and CPU's does it take to process 25 Million items per hour....?? - I don't want to divulge, but the numbers on the "estate" are multiples of 24...).
Prompted by a good lunch-discussion with same client on IOTs and other nerdy but sometimes crucial optimizations (more material for posts and demos, thx J)

In this particular case, the client had a requirement to (repeatedly??) check existence and/or content of a record based on PK-access. This particular data was relatively static (lookup-type data) and apparently only modified overnight.

There is also the need to check on certain values for de-duplication, and that is a different and more challenging matter. Such de-dup-data is modified (inserted) constantly, and needs to be purged based on time, hence "needs" another index. I might eleborate on that some other time.

For the moment, I will also deliberately discard the possibilities of using SQL-resultset-caching by Oracle, or the option of Hash-map tables or other (indexed-)arrays cached by some Java component, or Oracle Coherence. All of those I consider usable, but much more complex and intrusive then a Simple, well-designed database-solution.
I am a data-beast after all.

Why (not) clusters...

Single Table Hash Clusters can fetch a row with a Single Block Get. That beats any other method of access.

Of course, those who have read and understood the manuals, metalink, and various books on the subject already know all of this, and dont need to waste their time on here. But I see surprisingly few implementations of Clusters and IOTs ...

Normally, I shy away from using clusters because you need to know up front:
1) How many records go into your tables (parents and children for multi-table clusters), and
2) How big those records will be and
3) For Hash-clusters, Critical access is on the clusterkey.
Those three conditions are rarely met, and even more difficult to enforce over the lifetime of a system. But sometimes you get lucky.
And if any of the Oracle Cluster-constructions is useful, my vote goes to Single Table Hash Clusters. Simple, Elegant and ... Fast!

If you already know your theory about Single-Table-Hash-clusters, you dont need to read on. You know we will end up showing 1 single consistent get...

The DIY Demo

The rest of the post will allow you yourself to demonstrate on your database how Fast Single Table Hash Clusters can be.

Copy this into your SQL*Plus:

SQL> @

Press enter a few times, and you can re-read the output in your own spool file...

The script creates 3 tables; a heaptable, an IOT and a Single-Table-Hash-Clustered one. All tables are filled with the same 64K records. The Key is deliberately chosen to be a Varchar2 with funny distribution to resemble client case. And as it uses the Julian date 'JSP' format to generate spelled-out-numbers, your results may vary depending on your NLS settings. Any quirks or issues: send me a comment or a postcard.

If anyone spots flaws in the demo: let us know in a comment or an email. My knowledge is only skindeep and errors are easily made. Nor am I as skilled in education as Jonathan Lewis or Tom Kyte. My original demo was only whipped up to show to an Architect. Getting stuff out ready for the dba-community-at-large is more work then I anticipated, and my knowlege on the subject of Clusters is not as deep as I wished.

And if my demo-script fails you, check out the only other mention of STHC-with-demo that I recall seeing, by Joze Senegacnik here.

The demo uses on only 64k records as that was an amount I could test and re-test on my laptop in reasonable timeframes (10 seconds, I'm an impatient person). But it will work on Any size table, as long as the same conditions are met: knowing your data (numbers and size of records), and accessing on (PK-)equal condtion. Single Table Hash Clusters scale nicely.

The demo script can be found Here: demo_sthc.sql. It can be run with no modification in just about any schema able to create tables, indexes and clusters (of course, I always log on as system, but I have tested on, and

The Single table Has cluster is created like this:

create cluster clu
( key varchar2(78 byte)
single table
hashkeys 1000;

( key VARCHAR2(78 BYTE),
num_key NUMBER,
date_modified DATE,
padding VARCHAR2(300 BYTE),
constraint clut_pk primary key ( key)
CLUSTER clu ( key );

Note that the 1000 hashkeys I use is based on the fact that I cold fit approx 64 records in my 8K blocks, your results will vary if you use different blocksize or different size records. All those nitty-gritty details are part of why this is a rather nerdy and underused concept. Material for a follow-up here...

When the table is filled, I then fire some selects with a Key=value condition at the tables, and I use Autotrace to examine the 2nd execute of each query, like this:

select * from heap
where key = 'FIVE HUNDRED'
set autotrace on
set autotrace off

So, How Fast is this thing ... ?

(Did you run the demo in your own database yet... ?)

For a Single Table Hash Cluster, the result is 1 (one) Consistent get.

The result for a conventional heap table is 4 consistent gets. For an IOT it is 3 consistent gets (same index, but no table-access). And these numbers risk to increase by 1 if the blevel of the indexes goes from 2 to 3.

That may not seem like a big improvement, but it happens to be 3 or 4 times less Logical IO then the alternatives. And if executed at 25-million/hr, that is still a significant saving in LIO.

Of course, there is more to it. Such as the additional CPU-usage, chooseing the hash-key and guesstimating the size-value. And how does it perform when your data-volume unexpectedly explodes and it all goes horribly wrong....
I might re-run the demo a bit and experiment. I see a follow-up coming on the next long train journey.


Martin said...

That's a very nice example. I'm looking forward to your next long train journey and thus a follow up Piet.

Some thoughts.
Block size of a database does not really change.
Structure of key application tables where you invariably go in on the same ID do not change often (and, if you want to add more information you can create an auxillary table with a 1:1 mapping and used the same hash). So you can predict the size of the rows and so how many per block.
So where you want absolute performance for those lookups, this is a neat feature.

I can think of two areas off the top of my head where getting the access down to one consistent get would potentially work wonders:
1) Reference values. All those lookups where code 1-15 translates to order status. You go and create a nice normalised table keyed by the code and holding the abbreviation, name, start and end date and join to it over and over again.
2) Instrumentation tables. Where you check to see if there is a row in the "audit my actions" table every time a module is fired. Invariably there is not.

I've seen both types of short, quick, sql statements being fired hundreds of thousands of times a day, all taking 2-5 consistent gets.

In both cases, you can afford to vastly over estimate the number of blocks per cluster key and cluster by the ID.

All those lookups will speed up by probably a factor of 2 or 3.

It could be an almost free system-wide performance boost.

PdV said...

I'm on it Martin (not on the train, but on the topic). I'll get some more experiments out, if only to confirm what the manual already tells us in those very brief paragraphs on STHClusters.

But yeah, an STHC could be a "simple" boost to performance in some cases.

But for a lot of the status-code-lookup cases, so would my old hobby of IOTs. IOTs can be single-segment items, and they dont require size/volume-estimates... Whereas a STHC would still require a unique PK-index for good measure. And for emergencies, in case the hash-lookup cannot be used it will also revert to PK-unique or range-scans. I've had a few mixed-results on OR-clauses and in-list-lookups with STCHs. More later.

Question to you:
How would you see an auxiliary 1:1 table when more information is neeeded? Two same-key tables covered by a view would seem too complex to me.

My next idea was to see how an STHC behaves when data-volume increases (nr of records, the un-predictable growth of data...).

Then there is the inflation of (varchar-)column-sizes or the addition of columns. Those would invalidate the size-estimate. But in the case of static lookup-data, you would probably be allowed to re-define the cluster with new parameters.

Lots of stuff to ponder, and the limitation shows...

sap migration said...

This is really a nice example. I will try some more experiments on this Single Table hash clusters as I have not read about it earlier. Also I find it a very interesting topic to study and to know about how to improve the performance.

Anonymous said...

Thanks for the discussion. I NEARLY used STHC once in my career. It was for a lookup for telephone numbers which were on a "Do not call this number for direct marketing purposes" list. We received new UK phone numbers from various sources and needed to check if the newly seen numbers were on this list. Looking at your criteria:

1) How many records go into your tables (we knew how many telephone numbers were on the list - about 9 million and growing - and we could predict growth and a maximum - all the UK mobiles or landlines)
2) How big those records will be (they always had the same format. They were numbers but stored as character with spaces stripped out to preserve any leading zeros)
3) For Hash-clusters, Critical access is on the clusterkey (Only one column in the table - the phone number in the standard format, and one access method - a function saying: Is this phone number in the list, Yes or No?.

Standard index - 3 gets (no table access needed).
IOT - also 3 gets. No gain except not having to store the table segment.
STHC - 1 get.

It looked perfect but the thing that killed it was (at the time) a limit on the number of values per block in the cluster (128 I think). It meant that the table size exploded as a STHC, and it would be worse with a bigger block size (we used 16K). I couldn't get approval for the extra storage requirements (10 million row cluster was > 1GB). Sounds a trivial size now but it was a trade off at the time. It's another dimension to the cost/benefit.
Tony Killen.