jump to navigation

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.
trackback

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 ;)

About these ads

Comments»

1. Neil Johnson - February 29, 2008

As all features have cons as well as pros I wondered if there’s room for “Part V (Wolf at the Door)”.

It was hinted at in a comment on a previous post that “compressed indexes will deteriorate the performance if the table is prone for huge concurrent multi row dml statements”. I hasten to add I’m not saying this is true or not – at worst I can only imagine it making an already present problem more pronounced – but it did make me wonder what side effects there may be.

2. Brian Tkatch - February 29, 2008

Ah, so because it is a compressed INDEX, Oracle knows it is a reference to the prefix, and it also knows how long the reference to the prefix is. So, we traded a value which needed a length for a value that does not need a length, and voila. Thus, a byte saved.

I would think an INDEX could skip the length block on a CHAR-based index, but it seems it does not.

3. Robert - March 4, 2008

Really great stuff,Richard! You’re certainly setting great expectations for next blog entries. :-)

PS: now where did I sneak in a title? Hint: it’s an album name. :-)

4. Richard Foote - March 4, 2008

Hi Neil,

I won’t stop until this series becomes a “Rocky Part X”, all about an aging DBA who tried to compress a Bitmap Index one day and couldn’t remember why it didn’t work ;)

Hi Brian, actually we traded in a prefix value that contains exactly the same info as what appears in an index entry plus 2 additional bytes overhead for now not needing anything in the index entry for the compressed column and voila, thus 2 bytes saved for every index entry. If the compressed index column value is repeated twice, we break even, any more and we’re ahead.

Thanks Roberts, let’s hope I meet those great expectations ;)

5. Magesh - May 14, 2008

Great Job on index compression Richard. Is there a script available which can identify if a given column(s) are good for index compression?

6. Richard Foote - May 15, 2008

Hi Magesh

I don’t have one to hand but a script that divided the distinct value column combinations on the compressed columns by the number of leaf blocks and compared this to the average number of index entries per leaf block would give you some indication. Remember, you need a index in which the compressed columns are typically repeated somewhat within an index leaf block.

7. Alberto Dell'Era - February 10, 2009

Excellent post about this topic; the most informative I’ve found around. Thank you!

8. jiri - May 30, 2009

very nice series !!

it would be very interesting to do PART V about compression on partitioned tables (local index, global index, PK, …)

jiri

9. Richard Foote - May 31, 2009

Hi Jiri

The compression story doesn’t change much for partitioned indexes. It’s still performed in very much the manner I describe, the main difference being that for non-partitioned indexes on a partitioned table, Oracle needs to use the 10 byte extended rowid as the restricted rowid doesn’t provide enough information to uniquely identify the location of a row (as the relative file id is not necessarily unique across multiple tablespaces).

I haven’t discussed partitioning much which is a bit of a surprise as I have an entire section on partitioning in my index internals seminar. Will look to write about it “sometime”.

10. A few words on Index Compression « The Dutch Prutser's Blog - April 6, 2010

[...] Hopefully this little post is enough to trigger you to dive into the world of compressed indexes! For a much more thorough discussion on index compression see Richard Foote’s fabulous Oracle blog. ( part 1 , part 2 , part 3 And part 4).-Harald [...]

11. marios - August 19, 2010

Thanks for the wonderful articles about compressing indexes.
I have read your index compression articles, plus your article about index block size myth. And I agree.
Now I have a complicated question for you.
What if we had an index partition with 64k block size (8 times the default 8k size). Then when compressing an index, we would get more values per block since the prefix table would not grow that much. So we would have better compression!
Am I correct? Or am I missing something?

12. Richard Foote - September 9, 2010

Hi Marios

Firstly, can’t get 64K block sizes, 32K is the max on some platforms.

Yes, it’s possible to get slightly better compression with a larger block size because you could get away with less prefix table values.

That said, not sure such savings would balance out the potential disadvanatges.

13. Bhavik Desai - December 8, 2010

Hi Richard,

Indeed valuable information on compression…
I got leaf block dump of one of my 3 col compressed (compression on first 2 col) b-tree non partitioned index which is sized at 289GB. Here are few entries from dump :

Block header dump: 0x6cded763
Object id on Block? Y
seg/obj: 0x31a50 csc: 0×692.2f341beb itc: 148 flg: E typ: 2 – INDEX
brn: 0 bdba: 0x6cdec205 ver: 0×01 opc: 0
inc: 0 exflg: 0
.
.
.
Leaf block dump
===============
header address 47533102400532=0x2b3b29af0414
kdxcolev 0
KDXCOLEV Flags = – - -
kdxcolok 0
kdxcoopc 0xa0: opcode=0: iot flags=-C- is converted=Y
kdxconco 3
kdxcosdc 2
kdxconro 100
kdxcofbo 244=0xf4
kdxcofeo 2498=0x9c2
kdxcoavs 2254
kdxlespl 0
kdxlende 0
kdxlenxt 1826541927=0x6cded167
kdxleprv 1826539105=0x6cdec661
kdxledsz 6
kdxlebksz 4528
kdxlepnro 1
kdxlepnco 2
prefix row#0[4498] flag: -P—-, lock: 0, len=30 :lengh of prefix entry is 30
col 0; len 23; (23):
54 72 61 6e 73 66 65 72 52 65 63 65 69 76 65 41 63 74 69 6f 6e 49 44
col 1; len 3; (3): c2 0f 06
prc 100
row#0[2498] flag: ——, lock: 0, len=20, data:(6): 27 9d 8a f7 00 99
col 0; len 11; (11): 35 33 38 33 39 33 32 30 30 30 37
psno 0
row#1[2518] flag: ——, lock: 0, len=20, data:(6): 27 9d 8a a3 00 1c
col 0; len 11; (11): 35 33 38 33 39 33 32 31 30 30 37
psno 0
row#2[2538] flag: ——, lock: 0, len=20, data:(6): 27 9d 8b 1d 01 11
col 0; len 11; (11): 35 33 38 33 39 33 32 32 30 30 37
psno 0
row#3[2558] flag: ——, lock: 0, len=20, data:(6): 27 9d 8a fc 01 21
col 0; len 11; (11): 35 33 38 33 39 33 32 33 30 30 37
psno 0
row#4[2578] flag: ——, lock: 0, len=20, data:(6): 27 9d 8a 76 00 5c
col 0; len 11; (11): 35 33 38 33 39 33 32 34 30 30 37
psno 0
row#5[2598] flag: ——, lock: 0, len=20, data:(6): 27 9d 8a ec 00 5f
col 0; len 11; (11): 35 33 38 33 39 33 32 35 30 30 37
psno 0
row#6[2618] flag: ——, lock: 0, len=20, data:(6): 27 9d 8b 0a 00 50
col 0; len 11; (11): 35 33 38 33 39 33 32 36 30 30 37
psno 0
row#7[2638] flag: ——, lock: 0, len=20, data:(6): 27 9d 8a fc 01 23
col 0; len 11; (11): 35 33 38 33 39 33 32 37 30 30 37
psno 0

I think, I gained very good compression ratio, as all 100 rowid are sharing same prefix rowid. Notice that i have a scenario of ITL explosion (itc=148). First column has 36 distinct values,second has 124 and the last one is really a unique value (3327M) being populated by an Oracle sequence.
Is there any recommendations to place better re-org method here? My table is INSERT only. (Conventional path insert by 30-50 concurrent sessions all the time by a service).
I have never done any re-org on this index and i am sure, i am going to gain lot of storage gain after re-org. This leaf is not the last leaf block and it is lying somewhere in the middle in B-TREE structure. The last leaf block is having ICT=127.

14. Bhavik Desai - December 8, 2010

forgot the DB version : is 11.1.0.7

15. Richard Foote - December 21, 2010

Hi Bhavik

Yes, an ITC of 148 is exessive and if numbers of that magnitude are common (eg. 127 for the last leaf block) then a rebuild might be benifical if performance is being impacted.

Note Jonathan Lewis recently noted this issue has been identified as a bug now (8767925), is fixed in 12.1 and will likely be back ported on request:

http://jonathanlewis.wordpress.com/2010/12/13/index-itl-fix/

16. Salek Talangi - August 15, 2014

Hi Richard,

for me, the most important sentence is in the linked PDF: “Prefix pointer is positional and so takes no space”.
I always wondered reading the block dumps why they include the “psno 0″ for every index row. Now I realise that this has no length given and therefore is just informational. The prefix for the current row can be computed by the row number and the prc-values in the prefix table.

Best regards,
Salek

Richard Foote - September 3, 2014

Hi Salek

Precisely :)


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,913 other followers

%d bloggers like this: