Mailing-List: contact dev-help@directory.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Apache Directory Developers List" <dev@directory.apache.org>
Received-SPF: pass (asf.osuosl.org: domain of aok123@bellsouth.net designates
 205.152.59.71 as permitted sender)
Message-ID: <45050F79.2000804@bellsouth.net>
Date: Mon, 11 Sep 2006 03:25:45 -0400
From: Alex Karasulu <aok123@bellsouth.net>
User-Agent: Thunderbird 1.5.0.5 (X11/20060728)
MIME-Version: 1.0
To: Apache Directory Developers List <dev@directory.apache.org>
Subject: Re: [ApacheDS] [Performance] Using indices to boost search
 performance
References: <44F91F1C.5090801@bellsouth.net>
In-Reply-To: <44F91F1C.5090801@bellsouth.net>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

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