equality index in OpenDS
By sin on May 21, 2009
An equality index is used when the search filter uses an equality match. For example, to search an existing entry cn=user,dc=example,dc=com if I use a filter "cn=user", an equality index will be used behind-the-scene. Let us see how an equality index works from its creation to the search. Assuming the first entry for this back-end is "dc=example,dc=com", the corresponding EntryID will be 1. If we create our entry next to this base dn, our entry with a dn: cn=user,dc=example,dc=com will have an EntryID as 2.
While creating our entry server will create an equality index key-value pair for all the attributes which have an equality index configured. Since attribute "cn" has it by default, the server will find its default equality matching rule and normalize the value "user" using that rule. This normalized value is converted into bytes and is available as a key. As rightly guessed, the value is the entryID which we just saw above i.e. 2. EntryID is generated prior to inserting anything into the database.
When you search for this entry using "cn=user" filter, it figures out an equality index needs to be used and searches the equality index database for a key with value "user". Once it retrieves any EntryID from the database, the actual entry is grabbed from id2entry database.
What if we add another entry which has a cn with a value = "user"? Will it overwrite our key in the equality index? No.. it doesn't. I was incorrect while saying that the value in the key-value pair is just an EntryID; it is actually a list of EntryIDs. If there are multiple EntryIDs corresponding to a key, all of them are concatenated. To find the number of EntryIDs, you can divide the length of concatenated byte array with 8. See an example:
I have following 3 entries in my userRoot backend:
Get the list of all the databases in this backend
sin > bin/dbtest list-database-containers -n userRoot
Database Name Database Type JE Database Name Entry Count
Base DN: dc=example,dc=com
dn2id DN2ID dc_example_dc_com_dn2id 3
id2entry ID2Entry dc_example_dc_com_id2entry 3
referral DN2URI dc_example_dc_com_referral 0
id2children Index dc_example_dc_com_id2children 1
id2subtree Index dc_example_dc_com_id2subtree 1
state State dc_example_dc_com_state 20
aci.presence Index dc_example_dc_com_aci.presence 0
cn.equality Index dc_example_dc_com_cn.equality 2
Dump the content of the equality index database
sin > bin/dbtest dump-database-container -n userRoot -b "dc=example,dc=com" -d cn.equality
Indexed Value (3 bytes): abc
Entry ID List (8 bytes): 2
Indexed Value (4 bytes): user
Entry ID List (8 bytes): 3
Using dbdump utility to see non-opends representation of index database contents
sin > export CLASSPATH=/Users/sin/opends/b2.0/opends/build/package/OpenDS-2.0.0/lib/OpenDS.jar:/Users/sin/opends/b2.0/opends/build/package/OpenDS-2.0.0/lib/je.jar:$CLASSPATH
sin > java com.sleepycat.je.util.DbDump -h db/userRoot/ -p -s dc_example_dc_com_cn.equality
You can see the byte values of entryID against each of the keys.