directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From conflue...@apache.org
Subject [CONF] Apache Directory Server v1.5 > Structure and Organization
Date Mon, 26 Mar 2012 14:40:00 GMT
<html>
<head>
    <base href="https://cwiki.apache.org/confluence">
            <link rel="stylesheet" href="/confluence/s/2042/9/1/_/styles/combined.css?spaceKey=DIRxSRVx11&amp;forWysiwyg=true"
type="text/css">
    </head>
<body style="background: white;" bgcolor="white" class="email-body">
<div id="pageContent">
<div id="notificationFormat">
<div class="wiki-content">
<div class="email">
    <h2><a href="https://cwiki.apache.org/confluence/display/DIRxSRVx11/Structure+and+Organization">Structure
and Organization</a></h2>
    <h4>Page <b>edited</b> by             <a href="https://cwiki.apache.org/confluence/display/~elecharny">Emmanuel
L├ęcharny</a>
    </h4>
        <br/>
                         <h4>Changes (9)</h4>
                                 
    
<div id="page-diffs">
                    <table class="diff" cellpadding="0" cellspacing="0">
    
            <tr><td class="diff-snipped" >...<br></td></tr>
            <tr><td class="diff-unchanged" >[!http://cwiki.apache.org/confluence/download/attachments/80384/example_tree.png!|http://cwiki.apache.org/confluence/download/attachments/80384/example_ldif.png]
<br> <br></td></tr>
            <tr><td class="diff-deleted-lines" style="color:#999;background-color:#fdd;text-decoration:line-through;">!example_updn_index.png!
<br></td></tr>
            <tr><td class="diff-added-lines" style="background-color: #dfd;">!ParentIdAndRdn.png|border=1!
<br></td></tr>
            <tr><td class="diff-unchanged" > <br></td></tr>
            <tr><td class="diff-deleted-lines" style="color:#999;background-color:#fdd;text-decoration:line-through;">!example_ndn_index.png!
<br> <br></td></tr>
            <tr><td class="diff-unchanged" >!example_ex_one_sub_index.png!  <br>
<br></td></tr>
            <tr><td class="diff-snipped" >...<br></td></tr>
            <tr><td class="diff-unchanged" >System indices are required indices.
 Table based partitions need these indices to properly manage entries in the LDAP namespace,
and the entry hierarchy.  These indices are the minimum indices required to properly conduct
search operations on the part of the directory information base stored in the partition. 
Just for easy referral we show the example tree here again for index content examples. <br>
<br></td></tr>
            <tr><td class="diff-deleted-lines" style="color:#999;background-color:#fdd;text-decoration:line-through;">h2.
RDN (rdn) Index <br></td></tr>
            <tr><td class="diff-added-lines" style="background-color: #dfd;">h2.
ParentIdAndRdn (called Rdn) Index <br></td></tr>
            <tr><td class="diff-unchanged" > <br>This index associates the
RDN of each entry with it&#39;s entry ID in the aster table. It also stores the hierarchical
structure of the whole DIT. In order to do that, we keep a track to the parent&#39;s ID
in the key. <br></td></tr>
            <tr><td class="diff-snipped" >...<br></td></tr>
            <tr><td class="diff-unchanged" >The key is then a composition of the
entry&#39;s RDN and its parent&#39;s ID. <br> <br></td></tr>
            <tr><td class="diff-deleted-lines" style="color:#999;background-color:#fdd;text-decoration:line-through;">We
have a specific case : a context entry (which has a naming context in the rootDSE) is using
the full DN and 0 as the parent ID. <br></td></tr>
            <tr><td class="diff-added-lines" style="background-color: #dfd;">We
have a specific case : a context entry (which has a naming context in the rootDSE) is using
the full DN and a special marker as the parent ID (note that as we don&#39;t know the
type of the ID, we will have a specific value depending on the iD type : 0 if the ID is a
long, a special UUID if the ID is an UUID, etc) <br></td></tr>
            <tr><td class="diff-unchanged" > <br></td></tr>
            <tr><td class="diff-added-lines" style="background-color: #dfd;">We
don&#39;t necessarily store only a RDN in this data structure : when we are dealing with
a naming context, which may have a DN with more than one RDN, we treat this DN as if it was
a unique RDN. <br> <br></td></tr>
            <tr><td class="diff-unchanged" >For instance, if &#39;dc=example,
dc=org&#39; is a naming context, then its key will be &lt;&#39;dc=example, dc=org&#39;,
0&gt;. <br> <br></td></tr>
            <tr><td class="diff-snipped" >...<br></td></tr>
            <tr><td class="diff-unchanged" >{warning} <br> <br></td></tr>
            <tr><td class="diff-added-lines" style="background-color: #dfd;">h3.
OneLevel/SubLevel index removal <br> <br>We have created those two indexes back
in a time we were using UpDN and NormDn table, indead of RDN table. Now that we are using
the RDN index, we don&#39;t need those two index. <br> <br>Let&#39;s see
with an exemple how we can get rid of those two indexes. <br> <br>h4. OneLevel
index removal <br></td></tr>
            <tr><td class="diff-unchanged" >h2. Existence/Presence Index <br>
<br></td></tr>
            <tr><td class="diff-snipped" >...<br></td></tr>
    
            </table>
    </div>                            <h4>Full Content</h4>
                    <div class="notificationGreySide">
        <h1><a name="StructureandOrganization-Introduction"></a>Introduction</h1>

<p>We already covered some of the basic structural aspects in a 2 column Table based
partition design in the other sections. It should be clear how indices store Long pointers
into the MasterTable to access entries with specific attribute values.  Indices prevent the
need for full MasterTable scans which would entail a massive volume of expensive lookup, deserialization,
normalization and comparison operations.</p>

<p>This document will cover higher level details such as the default system indices
used for common operations and how these indices along with optional user indices work together
to efficiently search Table based partitions using LDAP filters. Namespace and hierarchy maintenance
aspects are also covered.</p>

<h1><a name="StructureandOrganization-SystemIndices"></a>System Indices</h1>

<table class="sectionMacro" border="0" cellpadding="5" cellspacing="0" width="100%"><tbody><tr>
<td class="confluenceTd" valign="top">
<p><a href="http://cwiki.apache.org/confluence/download/attachments/80384/example_ldif.png"
class="external-link" rel="nofollow"><span class="image-wrap" style=""><img src="http://cwiki.apache.org/confluence/download/attachments/80384/example_tree.png"
style="border: 0px solid black" /></span></a></p>

<p><span class="image-wrap" style=""><img src="/confluence/download/attachments/80473/ParentIdAndRdn.png?version=1&amp;modificationDate=1332772777309"
style="border: 1px solid black" /></span></p>

<p><span class="image-wrap" style=""><img src="/confluence/download/attachments/80473/example_ex_one_sub_index.png?version=1&amp;modificationDate=1206146567000"
style="border: 0px solid black" /></span> </p>

<p>Legend of Object Identifiers</p>

<div class='table-wrap'>
<table class='confluenceTable'><tbody>
<tr>
<th class='confluenceTh'>OID</th>
<th class='confluenceTh'>Aliases</th>
</tr>
<tr>
<td class='confluenceTd'>2.5.4.3</td>
<td class='confluenceTd'>cn,commonName</td>
</tr>
<tr>
<td class='confluenceTd'>2.5.4.11</td>
<td class='confluenceTd'>ou,organizationalUnitName</td>
</tr>
</tbody></table>
</div>
</td>
<td class="confluenceTd" valign="top">
<p>System indices are required indices.  Table based partitions need these indices to
properly manage entries in the LDAP namespace, and the entry hierarchy.  These indices are
the minimum indices required to properly conduct search operations on the part of the directory
information base stored in the partition.  Just for easy referral we show the example tree
here again for index content examples.</p>

<h2><a name="StructureandOrganization-ParentIdAndRdn%28calledRdn%29Index"></a>ParentIdAndRdn
(called Rdn) Index</h2>

<p>This index associates the RDN of each entry with it's entry ID in the aster table.
It also stores the hierarchical structure of the whole DIT. In order to do that, we keep a
track to the parent's ID in the key.</p>

<p>The key is then a composition of the entry's RDN and its parent's ID.</p>

<p>We have a specific case : a context entry (which has a naming context in the rootDSE)
is using the full DN and a special marker as the parent ID (note that as we don't know the
type of the ID, we will have a specific value depending on the iD type : 0 if the ID is a
long, a special UUID if the ID is an UUID, etc)</p>

<p>We don't necessarily store only a RDN in this data structure : when we are dealing
with a naming context, which may have a DN with more than one RDN, we treat this DN as if
it was a unique RDN.</p>

<p>For instance, if 'dc=example, dc=org' is a naming context, then its key will be &lt;'dc=example,
dc=org', 0&gt;.</p>

<h2><a name="StructureandOrganization-OneLevel%28onelevel%29Index"></a>One
Level (onelevel) Index</h2>

<p>The one level index maps parent entry identifiers from the master to the identifiers
of their children. This index is used to facilitate various name space operations like renaming,
and moving branches which impacts children.  It is also used by the search engine to conduct
one level search requests.</p>


<h2><a name="StructureandOrganization-SubLevel%28sublevel%29Index"></a>Sub
Level (sublevel) Index</h2>

<p>This index maps ancestor entry identifiers from the master to the identifiers of
all their descendants including immediate children.  It does not map the descendants of the
context entry (at the root) of the partition.  This is just unnecessary since all other entries
in the partition satisfy this condition.  If this is something we desire to enumerate we can
get a reverse Cursor on the ndn index and advance past the first entry, to start enumerating
all the descendant identifiers of the context entry.  Note that this index contains the &lt;id,id&gt;
tuple in order to include the added entry itself to the SUBTREE scope search.</p>

<p>This index plays a critical role in subtree search.  It allows the search optimizer
to detect a count and annotate the modified search filter for subtree scope nodes.  It also
allows a Cursor to enumerate the set of descendants associated with an entry.  Without this
index, the search engine must resort to expensive DN based operations for subtree scope constraint
checking.  </p>

<div class='panelMacro'><table class='tipMacro'><colgroup><col width='24'><col></colgroup><tr><td
valign='top'><img src="/confluence/images/icons/emoticons/check.gif" width="16" height="16"
align="absmiddle" alt="" border="0"></td><td><b>Other Untapped Advantages</b><br
/>Besides helping with search, the forward LUT of the sublevel index can be used to turn
recursive methods for rename and move operations into iterative operations.</td></tr></table></div>

<p>Note that the reverse LUT of this index maps entries to all their ancestors minus
the context entry. This can be used to quickly walk the lineage of an entry in the tree. 
This may be useful for certain operations.  </p>
</td></tr></tbody></table>
<div class='panelMacro'><table class='warningMacro'><colgroup><col width='24'><col></colgroup><tr><td
valign='top'><img src="/confluence/images/icons/emoticons/forbidden.gif" width="16"
height="16" align="absmiddle" alt="" border="0"></td><td>Digram needs to be
updated to reflect the changes done in StoreUtils.java</td></tr></table></div>

<h3><a name="StructureandOrganization-OneLevel%2FSubLevelindexremoval"></a>OneLevel/SubLevel
index removal</h3>

<p>We have created those two indexes back in a time we were using UpDN and NormDn table,
indead of RDN table. Now that we are using the RDN index, we don't need those two index.</p>

<p>Let's see with an exemple how we can get rid of those two indexes.</p>

<h4><a name="StructureandOrganization-OneLevelindexremoval"></a>OneLevel
index removal</h4>
<h2><a name="StructureandOrganization-Existence%2FPresenceIndex"></a>Existence/Presence
Index</h2>

<p>The existence index maps the OID of only indexed attributeTypes, to the identifiers
in the master for entries containing one or more values for the attribute.  All attributeTypes
are not tracked.  When an index is created on ou it will contain IndexEntry objects for 'ou'
in this existence index.  Note the OID for attributeTypes is the normalized form for attribute
type identifiers.</p>

<div class='panelMacro'><table class='tipMacro'><colgroup><col width='24'><col></colgroup><tr><td
valign='top'><img src="/confluence/images/icons/emoticons/check.gif" width="16" height="16"
align="absmiddle" alt="" border="0"></td><td>Remember for our example DIT's
partition we indexed objectClass, ou, and cn.</td></tr></table></div>

<p>The existence index is used to conduct searches using the existence operator =&#42;.
For example a search with the following filter, <b>(cn=&#42;)</b>, returns
entries 5, 6, and 7.  The search engine acquires a Cursor and positions it just before the
key '2.5.4.11' which is the unambiguous representation of 'cn' or 'commonName'.  It then walks
(advances one step at a time) the IndexEntry objects for this key, and stops the walk as soon
as this key's values are exhausted.  At each advance, the entry identifier is used to lookup
the entry in the master table and return it.</p>

<p>Notice the existence index does not add the OID for the objectClass attribute.  This
is specifically avoided since all entries contain the objectClass attribute.  There is no
reason for this index to bloat by including it. </p>

<div class='panelMacro'><table class='warningMacro'><colgroup><col width='24'><col></colgroup><tr><td
valign='top'><img src="/confluence/images/icons/emoticons/forbidden.gif" width="16"
height="16" align="absmiddle" alt="" border="0"></td><td>I <b>'think'</b>
the objectClass attribute is not considered for existence indices however this may not be
the case.  We need to determine this and make sure we do <b>NOT</b> add objectClass
IndexEntrys to the existence index.</td></tr></table></div>

<h2><a name="StructureandOrganization-AliasIndices"></a>Alias Indices</h2>

<div class="error"><span class="error">Unknown macro: {warn}</span> 
<p>Those index might be removed.</p></div>

<h3><a name="StructureandOrganization-AliasSchemaElements"></a>Alias Schema
Elements</h3>

<table class="sectionMacro" border="0" cellpadding="5" cellspacing="0" width="100%"><tbody><tr>
<td class="confluenceTd" valign="top">
<p><span class="image-wrap" style=""><img src="/confluence/download/attachments/80473/alias_schema.png?version=1&amp;modificationDate=1206160171000"
style="border: 0px solid black" /></span></p></td>
<td class="confluenceTd" valign="top">
<p>Aliases are entries of the alias objectClass which reference other entries in the
DIT. Aliases are not allowed to have subordinate (child) entries.  To the left you'll see
the schema ER diagram for the alias objectClass and it's mandatory aliasedObjectName attributeType.</p></td></tr></tbody></table>

<h3><a name="StructureandOrganization-AliasImpactonSearch"></a>Alias Impact
on Search</h3>

<p>Alias entries cause cycles in a DIT partition which would otherwise be a perfect
tree with the context entry at the root. LDAP search operations are conducted using one of
four alias dereferencing modes:</p>

<ol>
	<li>ignore aliases while searching, returning alias entries as part of the results</li>
	<li>dereference aliases while trying to find the search base</li>
	<li>dereference aliases only while searching (search propagates and continues at the
entry referenced)</li>
	<li>dereference aliases while trying to find the search base, and while searching</li>
</ol>


<p>Aliases complicate the mechanics of conducting search operations.  Searches, without
alias dereferencing enabled, contain a clear candidate range for which filter evaluation is
applied.  Without dereferencing the candidate range is based on the search scope parameter
and the search base.  Alias dereferencing expands the candidate range into areas of the DIT
that would not have been normally eligible for filter evaluation.  Candidate determination
with dereferencing must factor in the presence of aliases.   </p>

<p>Three specialized system indices are used to manage the 3 modes above which allow
for some kind of alias dereferencing.  These system indices are called the alias, oneAlias,
and subAlias indices.  We describe what each index contains and how it is used in the subsections
below.  </p>

<table class="sectionMacro" border="0" cellpadding="5" cellspacing="0" width="100%"><tbody><tr>
<td class="confluenceTd" valign="top">

<h3><a name="StructureandOrganization-ExampleDITReloaded%28withAliases%29"></a>Example
DIT Reloaded (with Aliases)</h3>

<p>But first we should add some alias entries to our example DIT to show what the composition
of these alias indices would be.  On the right is our example DIT with some new alias entries
in red.  Two new alias entries have been added:</p>

<div class='table-wrap'>
<table class='confluenceTable'><tbody>
<tr>
<th class='confluenceTh'>Id</th>
<th class='confluenceTh'>Alias DN</th>
<th class='confluenceTh'>Ref. Id</th>
<th class='confluenceTh'>Referenced Entry DN</th>
</tr>
<tr>
<td class='confluenceTd'>8</td>
<td class='confluenceTd'>6</td>
<td class='confluenceTd'>commonName=Jim Bean,ou=Board of Directors,o=Good Times Co.</td>
<td class='confluenceTd'>cn=JIM     BEAN,ou=Sales,o=Good Times Co.</td>
</tr>
<tr>
<td class='confluenceTd'>9</td>
<td class='confluenceTd'>5</td>
<td class='confluenceTd'>2.5.4.3=Johnny Walker,ou=Engineering,o=Good Times Co.</td>
<td class='confluenceTd'>cn=JOhnny WAlkeR,ou=Sales,o=Good Times Co.</td>
</tr>
</tbody></table>
</div>



<p>Follow the link on the image to the right or click <b><a href="http://cwiki.apache.org/confluence/download/attachments/80473/example_alias_ldifs.png"
class="external-link" rel="nofollow">here</a></b> to view the LDIF for these
two newly added alias entries.  These LDIF entries have the extensibleObject objectClass set
for a value of their objectClass attribute.  This marker is a cue to allow these entries to
contain values for any defined attribute in the server's schema.  It's what allows us to use
a commonName attribute for the relative distinguished names of these entries.  Also we mix
things up here to make a point regarding attribute name variance: the attribute identifier
for commonName can be 'cn', 'commonName', or even the OID for this attributeType which is
2.5.4.3. </p></td>
<td class="confluenceTd" valign="top">
<p><a href="http://cwiki.apache.org/confluence/download/attachments/80473/example_alias_ldifs.png"
class="external-link" rel="nofollow"><span class="image-wrap" style=""><img src="/confluence/download/attachments/80473/example_tree_with_aliases.png?version=1&amp;modificationDate=1206154482000"
style="border: 0px solid black" /></span></a></p></td></tr></tbody></table>

<div class='panelMacro'><table class='warningMacro'><colgroup><col width='24'><col></colgroup><tr><td
valign='top'><img src="/confluence/images/icons/emoticons/forbidden.gif" width="16"
height="16" align="absmiddle" alt="" border="0"></td><td>Digram needs to be
updated to reflect the changes done in StoreUtils.java</td></tr></table></div>

<h3><a name="StructureandOrganization-AliasIndex%28alias%29"></a>Alias Index
(alias)</h3>

<table class="sectionMacro" border="0" cellpadding="5" cellspacing="0" width="100%"><tbody><tr>
<td class="confluenceTd" valign="top">
<p>The '<b>alias</b>' index is just like a user index on the aliasedObjectName
attribute.  The normalized distinguished name of the aliased object (the value of aliasedObjectName
attribute) is stored in Tuple keys of the forward LUT.  The Long identifier of the alias entry
is stored in the Tuple value.  The alias index is not essential, however it does improve the
performance of some operations as an optimization.  </p>

<p>To the right, you'll see the composition of the forward LUT for this index.  It's
straight forward: value of aliasedObjectName normalized maps to the id of the alias entry
containing this value.</p></td>
<td class="confluenceTd" valign="top">
<p><span class="image-wrap" style=""><img src="/confluence/download/attachments/80473/example_alias_index.png?version=4&amp;modificationDate=1206204288000"
style="border: 0px solid black" /></span></p></td></tr></tbody></table>

<h3><a name="StructureandOrganization-OneLevelAliasIndex%28oneAlias%29"></a>One
Level Alias Index (oneAlias)</h3>

<table class="sectionMacro" border="0" cellpadding="5" cellspacing="0" width="100%"><tbody><tr>
<td class="confluenceTd" valign="top">
<p>The one level alias index assists in candidacy determination when one level search
is enabled with dereferencing while searching.  This index contains Long identifiers for both
the key and value fields of it's Tuples.  For the forward LUT, the Tuple keys represent non-leaf
entries with alias child entries <b>NOT</b> pointing to their siblings.  Child
alias entry identifiers are stored in the value of the corresponding Tuple.  Child aliases
pointing to entries that are siblings do not alter the candidate range.  Only those child
aliases that point to non-sibling entries expand the candidate range by bringing the referred
to entries into scope.  </p>

<p>To the right, you'll see the composition of the forward LUT for this index.  The
first Tuple maps id 3 to id 8.  This is because the alias entry 8, expands the scope of one
level search when conducted with search base set to entry 3.  Entry 8 brings it's referenced
entry, entry with id 6, into the scope of the search.  Notice the alias entry, the entry with
id 8, does not point to a sibling so it is included.  The same reasoning holds for the second
Tuple in this index's forward LUT.</p></td>
<td class="confluenceTd" valign="top">
<p><span class="image-wrap" style=""><img src="/confluence/download/attachments/80473/example_onealias_index.png?version=5&amp;modificationDate=1206204083000"
style="border: 0px solid black" /></span></p></td></tr></tbody></table>

<div class='panelMacro'><table class='warningMacro'><colgroup><col width='24'><col></colgroup><tr><td
valign='top'><img src="/confluence/images/icons/emoticons/forbidden.gif" width="16"
height="16" align="absmiddle" alt="" border="0"></td><td>Digram needs to be
updated with the correct key-value ids</td></tr></table></div>

<h3><a name="StructureandOrganization-SubLevelAliasIndex%28subAlias%29"></a>Sub
Level Alias Index (subAlias)</h3>

<table class="sectionMacro" border="0" cellpadding="5" cellspacing="0" width="100%"><tbody><tr>
<td class="confluenceTd" valign="top">
<p>The subtree level alias index assists in candidacy determination when subtree level
search is enabled with dereferencing while searching.  This index also contains Long identifiers
for both the key and value fields of it's Tuples.  For the forward LUT, the Tuple keys represent
non-leaf entries with alias descendants referencing entries that are <b>NOT</b>
descendants of the key.  Descendant alias entry identifiers are stored in the value of the
corresponding Tuple.  Descendant aliases pointing to entries that are descendants of the key
do not alter the candidate range.  Only those descendant aliases that point to non-descendant
entries expand the candidate range by bringing the subtree of nodes rooted at the referred
to entries into scope.  Another way to think about this index is that it tracks all the ancestors
of alias entries.</p>

<p>To the right, you'll see the composition of the forward LUT for this index.  The
first Tuple maps id 3 to id 8.  This is because the alias entry 8, expands the scope of subtree
level search when conducted with search base set to entry 3.  Entry 8 brings it's referenced
entry, entry with id 6, into the scope of the search.  Notice the alias entry, the entry with
id 8, does not point to a descendant of the search base, entry with id 3, so it is included.
 The same reasoning holds for the second Tuple in this index's forward LUT.</p>

<p>Notice though we do not have Tuples for (1, 8) and (1,9).  Although alias entries
8 and 9 are descendants of entry 1, they do not expand the search scope with subtree search
operations using entry 1 as the base.  All these aliases and the entries they point to were
reachable as candidates before creating alias entries 8 and 9.  Only alias entries pointing
out of the subtree of the base tow entries that are not search base descendants are tracked
by this index.</p>
</td>
<td class="confluenceTd" valign="top">
<p><span class="image-wrap" style=""><img src="/confluence/download/attachments/80473/example_subalias_index.png?version=5&amp;modificationDate=1206204202000"
style="border: 0px solid black" /></span></p></td></tr></tbody></table>

<div class='panelMacro'><table class='warningMacro'><colgroup><col width='24'><col></colgroup><tr><td
valign='top'><img src="/confluence/images/icons/emoticons/forbidden.gif" width="16"
height="16" align="absmiddle" alt="" border="0"></td><td>Digram needs to be
updated with the correct key-value ids</td></tr></table></div>

<h3><a name="StructureandOrganization-HandlingDereferencingwithObjectLevelScope"></a>Handling
Dereferencing with Object Level Scope</h3>

<p>Object level search requests are trivially handled. Only two of the dereferencing
modes matter to us in this case.</p>

<div class='table-wrap'>
<table class='confluenceTable'><tbody>
<tr>
<th class='confluenceTh'>Mode</th>
<th class='confluenceTh'>Considered</th>
<th class='confluenceTh'>Reason</th>
</tr>
<tr>
<td class='confluenceTd'> neverDerefAliases</td>
<td class='confluenceTd'>no</td>
<td class='confluenceTd'>this is a normal search and dereferencing does not matter</td>
</tr>
<tr>
<td class='confluenceTd'> derefFindingBase</td>
<td class='confluenceTd'>yes</td>
<td class='confluenceTd'>if the base is an alias we must dereference it before filter
evaluation</td>
</tr>
<tr>
<td class='confluenceTd'> derefSearching</td>
<td class='confluenceTd'>no</td>
<td class='confluenceTd'>with object level search we're not searching</td>
</tr>
<tr>
<td class='confluenceTd'> derefAlways</td>
<td class='confluenceTd'>yes</td>
<td class='confluenceTd'>same as derefFindingBase</td>
</tr>
</tbody></table>
</div>


<p>So if alias dereferencing is in effect always or when finding the base a check must
be performed to see if the search base entry is an alias.  If it is an alias, the referenced
entry is resolved, and the search base is set to the referenced entry.  In this simple case
with object level scope, alias dereferencing does not expand the single candidate.  Instead
alias dereferencing switches the base to the referenced entry.</p>

<h3><a name="StructureandOrganization-HandlingDereferencingwithOneLevelScope"></a>Handling
Dereferencing with One Level Scope</h3>

<p>One level search requests apply the same technique of switching the base when base
dereferencing is enabled.  Actually all search scopes switch the search base when base dereferencing
is enabled, and the original search base is in fact an alias.  </p>

<p>The search engine uses this index to find aliases which expand the range of candidates
to entries outside the scope.  After the base entry is resolved, the search engine, uses the
identifier of the base to lookup all alias children.  The referred to entries are then included
in search filter evaluation and returned if accepted by the filter.  This way the candidate
range expands to include referenced entries in the aliasedObjectName attribute.</p>

<div class='panelMacro'><table class='warningMacro'><colgroup><col width='24'><col></colgroup><tr><td
valign='top'><img src="/confluence/images/icons/emoticons/forbidden.gif" width="16"
height="16" align="absmiddle" alt="" border="0"></td><td>When alias dereferencing
while searching is enabled, ScopeNodes, in the filter AST, should not be used as candidate
enumerators.  In fact the search engine's optimizer should annotate the scope node with a
maximum count value when dereferencing while searching is enabled.  I do not know if this
is the case today.</td></tr></table></div>  

<p>For our example, let's do a search where the search base is entry with id 4.  The
scope is one level and derefSearching is enabled.  The search engine positions a Cursor over
the children of entry 4 using the onelevel hierarchy index.  It joins the results of this
Cursor with the results from another Cursor on the oneAlias index over forward LUT key 4.
 This includes entries 6, 7 and 9 as candidates.  Entry 9 however is filtered out of the result
set when derefSearching is enabled.  It is not returned since it is an alias.  </p>

<h3><a name="StructureandOrganization-HandlingDereferencingwithSubtreeLevelScope"></a>Handling
Dereferencing with Subtree Level Scope</h3>

<p>Dereferencing while searching with subtree scope is rather painful.  After dereferencing
the base, if needed and derefFindingBase is enabled, the search engine looks up all alias
descendants in the subAlias index.  Alias descendants are then collected, and put into a special
ScopeAssertion which uses this list and search scope parameters to determine if an entry is
an eligible candidate for filter evaluation.</p>

<p>The semantics of search with derefSearching enabled presumes search propagation into
dereferenced subtrees.  This means a propagated search may encounter new alias entries which
it must dereference as well.  </p>

<p>You'll see in more advanced sections of this guide that assertion and candidate enumerating
Cursors are used by the search engine. One assertion is the scope assertion.  For search without
alias dereferencing while searching, this scope assertion just makes sure the candidate entries
are in scope by checking if they are subordinate to (with on level search) or descendants
of the search base (with subtree level search).  </p>

<p>When derefSearching is enabled, the search engine modifies how this scope assertion
determines if a candidate is within scope.  The algorithm is simple and it uses the subAlias
index with subtree scope search:</p>

<ol>
	<li>Use the provided search base parameter to find all alias entries that are descendants
of the base and point to entries outside the scope to entries that are not descendants of
the search base. To do so we get a Cursor on the forward LUT of the subAlias index over Tuples
with the key of the search base.</li>
	<li>For each value of the Tuples returned, repeat the process recursively by presuming
the alias entry is now the search base.  Stop recursing when no scope expanding alias descendants
are found.  Do this while collecting the complete set of aliases found.</li>
	<li>Use the set of aliases and the search base in the scope assertion: the assertion
returns true if any candidate entry is a descendant of any of these aliases or the search
base.  Otherwise it returns false.</li>
</ol>


<p>By modifying the behavior of the scope assertion to factor in scope expanding aliases
in the scope constraint check we effectively appear to propagate search through aliases.</p>

<div class='panelMacro'><table class='tipMacro'><colgroup><col width='24'><col></colgroup><tr><td
valign='top'><img src="/confluence/images/icons/emoticons/check.gif" width="16" height="16"
align="absmiddle" alt="" border="0"></td><td><b>Optimizations</b><br
/>Sometimes aliases will be return in this set of aliases to consider in scope assertions,
which are descendants of other aliases already in this set.  With subtree searching the search
will automatically hit these descendant aliases so there's no need to have them in the set.
 Hence we can prune this set, or perform checks before insertion to prevent including redundant
aliases in this set.</td></tr></table></div> 

<p>We will cover more of this while looking closer at the search engine in different
sections of this documentation.</p>

<h3><a name="StructureandOrganization-AliasLimitations"></a>Alias Limitations</h3>

<p>ApacheDS places some limitations on Aliases.  The limitations below are imposed either
for the sake of simplicity in conducting search or due to structural limitations. </p>

<ol>
	<li>Alias chaining where one alias refers to another alias is not allowed.</li>
	<li>Aliases can only reference entries within the same Partition.  This limitation
is not by choice and due to the inability to share access to indices across partitions which
may change in the future.</li>
</ol>


<h2><a name="StructureandOrganization-objectClassIndex"></a>objectClass
Index</h2>

<p>For the time being, the objectClass index is considered a system index. This is purposefully
done since objectClass values are critical for server operation and used heavily.  Without
setting this index performance would be terrible.</p>


<h1><a name="StructureandOrganization-UserIndices"></a>User Indices</h1>

<p>The partition can be asked to maintain an index on any attribute defined in the servers
schema.  These indices contain Tuples in their forward LUT, mapping a value of the attribute,
to the id of the entry with that attribute value.  This way after consulting the index, entries
with specific values for this attribute can be quickly looked up by identifier in the master
table.</p>


<h2><a name="StructureandOrganization-OtherUsefulIndices"></a>Other Useful
Indices</h2>

<p>The function of several optional ApacheDS features may be greatly enhanced by the
presence of indices on certain attributes.  One example is the revision attribute which has
not yet been defined, but it will.  This attribute will be used by the change log facility
to track the last altering revision on an entry.  When this system and it's related snapshoting
capabilities are enabled, having an index on this attribute will be very valuable.  </p>

<p>Other similar examples exist.  You'll find for different usecases, and for different
kinds of canned search distributes, indices on some attributes will greatly improve search
performance.  More about this is covered on the search engine section of this guide.   </p>








    </div>
        <div id="commentsSection" class="wiki-content pageSection">
        <div style="float: right;">
            <a href="https://cwiki.apache.org/confluence/users/viewnotifications.action"
class="grey">Change Notification Preferences</a>
        </div>
        <a href="https://cwiki.apache.org/confluence/display/DIRxSRVx11/Structure+and+Organization">View
Online</a>
        |
        <a href="https://cwiki.apache.org/confluence/pages/diffpagesbyversion.action?pageId=80473&revisedVersion=54&originalVersion=53">View
Changes</a>
            </div>
</div>
</div>
</div>
</div>
</body>
</html>

Mime
View raw message