Hi again,
I've completed my optimization on indices under high partition
capacities. The results are in line and side by side to the old
results. For those not interested in the exact optimization that took
place skip down to the results.
The problem:
------------
Up to now duplicate keys (keys with many values) were stored using a
TreeSet within the B+Trees of indices. Indices usually map some
attribute value to an ID into the master table for an entry. The ID is
a sequentially unique value assigned to the entry.
So if 100 people have initials AA then there would be 100 values in the
TreeSet for the key 'AA' in the intials index. This would be serialized
and deserialized to and from disk. At these low numbers there's really
very little impact. However certain indices were seriously impacted
like the objectClass index or the hierarchy based system index. Just
imagine having 1 million entries of inetOrgPersons. The objectClass
index would then have 1 million values in the TreeSet for the key
'inetOrgPerson'. This would seriously hurt performance from both a
space and time perspective. It would essentially obfuscate the benefits
of using BTree's in the first place with large numbers of entries.
Solution:
---------
What I did was add a configurable threshold parameter when instead of
using a TreeSet to store duplicates another B+Tree was created and used
within the same index database file. Right now the default value for
this which these tests were conducted with is 1000. So after having
1000 duplicate values the server switches from using in memory TreeSets
to on disk B+Trees for only storing values for that key.
Alex Karasulu wrote:
Hi all,
I've been testing the search performance boost gained from indexing
attributes before starting development on an optimization to improve
index performance and in memory size. I thought I'd share these
dramatic results of my pre-optimization tests with you since they
clearly show the benefits of indices.
Before I do this let me list the characteristics of the hardware used
and my configuration settings:
-------------
Machine Setup
-------------
CPU: Dual Athlon MP 1900
OS: Linux 2.6.15
Mem: 2GB 266Mhz
--------------
ApacheDS Setup
--------------
ApacheDS: Stock RC4 (to be released pre-image) w/ modifications
- Using 1024MB Memory
- Indexed st and initials
----------
Data Setup
----------
Wrote a simple tool to generate random values for descent sized entries.
The data sort of looks like this for a user entry:
dn: uid=user.1,ou=users,dc=example,dc=com
uid: user.1
initials: yq
description: cFocJATNuhlXisDCqGtY
pager: FYyimqyZRW
cn: HSGMzajYKmicUTe
postalcode: WiXXA
st: xy
street: kpCCqmrsCzkpdtHXWMfY
l: KqmAXFYTrI
objectclass: person
objectclass: organizationalPerson
objectclass: inetOrgPerson
sn: nuymgOwpm
homephone: PERamkCtsv
mobile: vkIviOGNTC
telephonenumber: 7248889026
mail: pYvEoOjSnEymcWD
givenname: IVHJZB
postaladdress: crObexKoUTIFdzNHcZMr
employeenumber: 1
userpassword:: cGFzc3dvcmQ=
I started loading a partition up with these entries 100,000 of them at a
time then performing the following searches for all entries with
initials aa:
(1) index on initials but no cached entries
(2) index on initials with cached entries
(3) no index without cached entries
Here are the results at the various capacities:
---------------
100,000 Entries
---------------
[cached] [indexed] [time (seconds)]
(1) no yes 3.30
2.37
(2) yes yes 0.72
0.76
(3) no no 30.63
42.08
search results = 153 entries
146
Notice that if #2 is total time for cached entries we can conclude that
#1 - #2 is a descent measure of pulling from disk. So let's see what
that number looks like:
Old: 2.58
New: 1.61
---------------
200,000 Entries
---------------
[cached] [indexed] [time (seconds)]
(1) no yes 6.04
3.29
(2) yes yes 1.44
1.49
(3) no no 82
83
search results = 302 entries
297
#1 - #2 values:
Old: 4.60
New: 1.80
---------------
300,000 Entries
---------------
[cached] [indexed] [time (seconds)]
(1) no yes 7.54
4.11
(2) yes yes 1.95
2.22
(3) no no 146
128
search results = 451 entries
435
#1 - #2 values:
Old: 5.59
New: 1.89
---------------
400,000 Entries
---------------
[cached] [indexed] [time (seconds)]
(1) no yes 9.24
4.87
(2) yes yes 3.80
2.69
(3) no no 196
168
search results = 586 entries
577
#1 - #2 values:
Old: 5.44
New: 2.18
---------------
500,000 Entries
---------------
[cached] [indexed] [time (seconds)]
(1) no yes 11.96
5.06
(2) yes yes 3.21
3.21
(3) no no 224
209
search results = 748 entries
706
#1 - #2 values:
Old: 8.75
New: 1.85
Besides these numbers I've noticed that adds are now faster and total
garbage collection is lower. These were eyeballed figures. For example
the adds would grow in time up to 28 minutes per 100K entries for those
between 400K-500K. This has dropped down to 18 minutes.
Now it would be interesting to see what happens with these trends once
the intials index converts from a TreeSet to a BTree for the values of
the key 'aa'. So just to see we keep loading up the partition until
there are over 1000 entries with initials 'aa'.
I'll report on this tomorrow as the server loads these entries.
I guess the conclusion here is that the optimization had a significant
effect and is worth the additional complexity it introduced into the
JDBM partition implementation. Here's the access times (#1-#2) as a
function of the number of entries:
Retrieval Times | 100K | 200K | 300K | 400K | 500K
--------------------------------------------------
Before: | 2.58 | 4.60 | 5.59 | 5.44 | 8.75
After: | 1.61 | 1.80 | 1.89 | 2.18 | 1.85
Before the optimization there seems to be a linear growth to access time
whereas after the optimization the growth rate is almost unmeasurable
above the noise.
-Alex
