[ApacheDS] Indices for parameterized filters

[Alex Karasulu <ak...@apache.org>]

Another idea which came to mind while in the JDBM code was the potential for
creating special kinds of indices.  For example an index could be built on a
parameterized filter like in prepared statements in SQL.  Here's an example
of such a filter:

(& (objectClass=person) (ou=?) (l=?))

Each parameter has an position index. The first parameter is the missing ou
value, and the second parameter is localityName value.   An index built on
this filter would contain tuples where the key would be the concatenation of
the ou and localityName values.  The value of the tuple would contain the
Long identifier of the entry matched by the filter with the substitutions.
So on write operations like add, modify, and delete this index would be
updated.  For example on an entry add a check would be performed to see if
the following filter matches the entry:

(& (objectClass=person) (ou=*) (l=*))

If so then we would permute the combinations of ou and localityName
attribute values to add tuples.  If the entry id is 7 and the entry has ou
values 'engineering' and 'management' with localityName value 'sunnyvale' we
would add these tuples:

(engineeringsunnyvale, 7)
(managementsunnyvale, 7)

Other maintenance operations for modify and delete would be implemented.
Such an index would allow the server to optimize common canned filters.  On
a search request using this filter with different parameterized values for
ou and localityName, the server can easily detect the filter and find this
filter index.  Then a single Cursor could be used on this index to retrieve
the results rapidly.  This optimization would bypass the Cursor creation
phase, and would result in more efficient Cursors that perform less IO and
less calculations on positioning and advances.

Thoughts?

Alex