DB2 for I: Index internals. Part-3 Encoded Vector Index

Encoded Vector Index or EVI

1. It’s IBM’s version of the Bitmap index.
2. EVI is relatively new compared to Radix Index.
3. Logical files do not support EVI.
4. Use “CREATE ENCODED VECTOR INDEX ….” Statement to create EVI index on the table
5. It’s very efficient for:

• Small set or say defined set of distinct keys like States in the USA.
• Read-only table

A quick look into Bitmap Index

Let say this table represents the keys and corresponding RRNs.

Here is the Bitmap index for these keys(with RRN)

1. Bitmap Index is suitable for small values.
2. As the number of keys increase (new RRNs) number of bits needs to store the index also increased. (Issue 1)
3. The System has to update the complete index every time a new key comes in. (Issue 2)

So, IBM created a modified version called Encoded Vector Index, aka EVI.

EVI: Encoded Vector Index

EVI has two parts

1. Symbol table:

• It contains a distinct list of keys.
• A reference (called code) to an element in the Vector list.
• And it may contain the values for some SQL functions like sum(), count(),avg().

2. Vector list:

• It’s just a list.
• Each position represents the RRN from the base table.
• This position is the only link between the index and the base table.
• The value at a position is the link between the Symbol table and this list.

Let say this is the data in the base table.

The Symbol table might look like this.

Vector List :

So, let say the System needs to find a match for the key-value “TX.”

1. Look into the Symbol table for the code for this key-value TX = 99
2. Now check the vector list for all the values equals 99.
3. RRN 1 and 4 in the base table contains the record for the key “TX.”

If you add a new Key in the symbol table, it will only impact a single entry in the vector list. So unlike the Bitmap Index system don’t need to update the complete index. The System will create a new entry in the vector list.

Memory allocation for the CODE (the reference between the Symbol table and the Vector list)

1. By default, DB2 allocates 1 byte for the code.

• This means a total of 256 distinct keys (28) can be added to the symbol table.
• If the number of distinct keys increased beyond 256

— DB2 will allocate 2 bytes (then 4 bytes .. 8 bytes, and so on) for the code

Get Sumit goyal’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

— And rebuild the index.

• So, every time the size increases, the System has to rebuild the complete index.

2. To limit these rebuilds, you can give some idea of how many distinct keys you expect in this index.

• So, based on this idea, the System will allocate an appropriate number of bytes for the code.

CREATE ENCODED VECTOR INDEX XYZ on ABC(state)

WITH 3650 DISTINCT VALUES

1. From this statement, System gets the idea that there might be 3650 distinct keys in this index.

• So, 1-byte won’t be enough for 3650 values
• But 2 bytes will be enough for now.

2. This is not a hard limit. If the number of distinct keys in the index goes beyond 2 bytes, the System will allocate extra space and rebuild the index.

More references

1. https://www.ibm.com/developerworks/ibmi/library/i-evi-only-access-in-ibm-db2-for-i/index.html
2. https://www.ibm.com/support/knowledgecenter/en/ssw_ibm_i_73/rzajq/howeviworks.htm