Return-Path: X-Original-To: apmail-directory-dev-archive@www.apache.org Delivered-To: apmail-directory-dev-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 6AF0079F3 for ; Sat, 8 Oct 2011 10:22:53 +0000 (UTC) Received: (qmail 9342 invoked by uid 500); 8 Oct 2011 10:22:53 -0000 Delivered-To: apmail-directory-dev-archive@directory.apache.org Received: (qmail 9295 invoked by uid 500); 8 Oct 2011 10:22:53 -0000 Mailing-List: contact dev-help@directory.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: "Apache Directory Developers List" Delivered-To: mailing list dev@directory.apache.org Received: (qmail 9287 invoked by uid 99); 8 Oct 2011 10:22:53 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 08 Oct 2011 10:22:53 +0000 X-ASF-Spam-Status: No, hits=-0.0 required=5.0 tests=SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (nike.apache.org: domain of hyc@symas.com designates 64.71.152.235 as permitted sender) Received: from [64.71.152.235] (HELO lirone.symas.net) (64.71.152.235) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 08 Oct 2011 10:22:46 +0000 Received: from oag3.wlan.daa.dublin.eircom.net ([83.71.193.228] helo=[172.26.43.32]) by lirone.symas.net with esmtpsa (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.72) (envelope-from ) id 1RCU2z-0004Sg-Gh; Sat, 08 Oct 2011 03:22:25 -0700 Message-ID: <4E902461.3060605@symas.com> Date: Sat, 08 Oct 2011 03:22:25 -0700 From: Howard Chu User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0a1) Gecko/20111001 Firefox/10.0a1 SeaMonkey/2.7a1 MIME-Version: 1.0 To: Apache Directory Developers List CC: Emmanuel Lecharny Subject: Re: RDN index, oneLevel and sublevel index merge References: <4E8FED61.5020203@gmail.com> <4E902243.9060406@symas.com> In-Reply-To: <4E902243.9060406@symas.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Checked: Checked by ClamAV on apache.org Howard Chu wrote: > Emmanuel Lecharny wrote: >> Hi guys, >> >> Stefan started to modify the code to get rid of the oneLevel and >> subLevel index, which are more or less useless as we already have the >> hierarchy stored into the rdn index. >> >> However, this rdn index is not good enough as is to be use as a >> replacement for the two other indexes. Its structure forbid us to easily >> retrieve the children from a known entry. >> >> The current RDN index structure is : >> -> Entry ID >> >> The key is a tuple containing the parent ID to be able to rebuild the DN. >> >> The reverse index is : >> Entry ID -> >> >> We don't have duplicated values. >> >> Now, when we have an entry ID, there is no simple way to get the list of >> all the children for this entry. >> >> We will have to add a third index to deal with such searches : >> ParentId -> >> >> which will list all the children of a specific entry. >> >> I'm going to investigate around this idea i the next few days. >> >> Thoughts ? > > Currently in OpenLDAP back-hdb and back-mdb, the DN index contains > > Entry ID -> [, ...] > > So each entry's RDN is stored twice, once under its own entryID, and once > under its parent's entryID. This allows top-down DN to ID lookups and > bottom-up ID to DN lookups from a single index. > > (This is a bit different from the original layout described in 2003 > http://www.openldap.org/conf/odd-sfo-2003/proceedings.html ) > I forgot to mention... Onelevel lookups are obviously trivial with this scheme. back-hdb and back-mdb differ in how they perform subordinate lookups. back-hdb recursively builds a list of subordinate members (and caches this list for future queries). back-hdb is ridiculously slow for subordinate lookups that haven't been cached yet. back-mdb is a bit more straightforward; given a list of candidate entry IDs, it simply walks up from the entryID until it hits the base of the desired subtree (meaning candidate is present in the result set) or until it hits the root of the tree (candidate is not present). As a further refinement (not yet implemented) if a search yields an all-entries candidate list (unindexed search), it can just recursively descend from the base of the desired subtree and ignore the candidate list. It turns out that building the cached IDLs in back-hdb is much slower than just reading the index in back-mdb. (Not to mention being a memory pig.) -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/