org.apache.directory.server.xdbm.search.impl

Class DefaultOptimizer<E>

java.lang.Object

org.apache.directory.server.xdbm.search.impl.DefaultOptimizer<E>

All Implemented Interfaces:

Optimizer

public class DefaultOptimizer<E>
extends java.lang.Object
implements Optimizer

Optimizer that annotates the filter using scan counts.

Field Summary

Fields

Modifier and Type	Field and Description
(package private) static java.lang.String	CANDIDATES_ANNOTATION_KEY
private java.lang.String	contextEntryId
private Store	db the database this optimizer operates on

Constructor Summary

Constructors

Constructor and Description
DefaultOptimizer(Store db) Creates an optimizer on a database.

Method Summary

Modifier and Type	Method and Description
java.lang.Long	annotate(org.apache.directory.api.ldap.model.filter.ExprNode node) Annotates the expression tree to determine optimal evaluation order based on the scan count for indices that exist for each expression node.
private long	getConjunctionScan(org.apache.directory.api.ldap.model.filter.BranchNode node) ANDs or Conjunctions take the count of the smallest child as their count.
private java.lang.String	getContextEntryId()
private long	getDisjunctionScan(org.apache.directory.api.ldap.model.filter.BranchNode node) Disjunctions (OR) are the union of candidates across all subexpressions so we add all the counts of the child nodes.
private <V> long	getEqualityScan(org.apache.directory.api.ldap.model.filter.SimpleNode<V> node) Gets the worst case scan count for all entries that satisfy the equality assertion in the SimpleNode argument.
private long	getFullScan(org.apache.directory.api.ldap.model.filter.LeafNode node) Gets the total number of entries within the database index if one is available otherwise the count of all the entries within the database is returned.
private <V> long	getGreaterLessScan(org.apache.directory.api.ldap.model.filter.SimpleNode<V> node, boolean isGreaterThan) Gets a scan count of the nodes that satisfy the greater or less than test specified by the node.
private long	getPresenceScan(org.apache.directory.api.ldap.model.filter.PresenceNode node) Gets the number of entries that would be returned by a presence node assertion.
private long	getScopeScan(org.apache.directory.api.ldap.model.filter.ScopeNode node) Gets the scan count for the scope node attached to this filter.
private long	getSubstringScan(org.apache.directory.api.ldap.model.filter.SubstringNode node) Get a scan count based on a Substring node : we will count the entries that are greater than ABC where the filter is (attr=ABC*).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

CANDIDATES_ANNOTATION_KEY

static final java.lang.String CANDIDATES_ANNOTATION_KEY

See Also:

Constant Field Values

db

private final Store db

the database this optimizer operates on

contextEntryId

private java.lang.String contextEntryId

Constructor Detail

DefaultOptimizer

public DefaultOptimizer(Store db)
                 throws java.lang.Exception

Creates an optimizer on a database.

Parameters:

db - the database this optimizer works for.

Throws:

java.lang.Exception

Method Detail

getContextEntryId

private java.lang.String getContextEntryId()
                                    throws java.lang.Exception

Throws:

java.lang.Exception

annotate

public java.lang.Long annotate(org.apache.directory.api.ldap.model.filter.ExprNode node)
                        throws java.lang.Exception

Annotates the expression tree to determine optimal evaluation order based on the scan count for indices that exist for each expression node. If an index on the attribute does not exist an IndexNotFoundException will be thrown.

Specified by:

annotate in interface Optimizer

Parameters:

node - the root of the expression node tree

Throws:

java.lang.Exception - if there are failures while optimizing

See Also:

Optimizer.annotate(ExprNode)

getConjunctionScan

private long getConjunctionScan(org.apache.directory.api.ldap.model.filter.BranchNode node)
                         throws java.lang.Exception

ANDs or Conjunctions take the count of the smallest child as their count. This is the best that a conjunction can do and should be used rather than the worst case. Notice that we annotate the child node with a recursive call before accessing its count parameter making the chain recursion depth first.

Parameters:

node - a AND (Conjunction) BranchNode

Returns:

the calculated scan count

Throws:

java.lang.Exception - if there is an error

getDisjunctionScan

private long getDisjunctionScan(org.apache.directory.api.ldap.model.filter.BranchNode node)
                         throws java.lang.Exception

Disjunctions (OR) are the union of candidates across all subexpressions so we add all the counts of the child nodes. Notice that we annotate the child node with a recursive call.

Parameters:

node - the OR branch node

Returns:

the scan count on the OR node

Throws:

java.lang.Exception - if there is an error

getEqualityScan

private <V> long getEqualityScan(org.apache.directory.api.ldap.model.filter.SimpleNode<V> node)
                          throws java.lang.Exception

Gets the worst case scan count for all entries that satisfy the equality assertion in the SimpleNode argument.

Parameters:

node - the node to get a scan count for

Returns:

the worst case

Throws:

java.lang.Exception - if there is an error accessing an index

getGreaterLessScan

private <V> long getGreaterLessScan(org.apache.directory.api.ldap.model.filter.SimpleNode<V> node,
                                    boolean isGreaterThan)
                             throws java.lang.Exception

Gets a scan count of the nodes that satisfy the greater or less than test specified by the node.

Parameters:

node - the greater or less than node to get a count for

isGreaterThan - if true test is for >=, otherwise <=

Returns:

the scan count of all nodes satisfying the Ava

Throws:

java.lang.Exception - if there is an error accessing an index

getSubstringScan

private long getSubstringScan(org.apache.directory.api.ldap.model.filter.SubstringNode node)
                       throws java.lang.Exception

Get a scan count based on a Substring node : we will count the entries that are greater than ABC where the filter is (attr=ABC*). Any other filter won't be evaluated (for instance, a filter like (attr=*ABC) will resolve to a full scan atm - we could have created a reverted index for such a case -, and filters like (attr=*ABC*) also esolve to a full scan).

Parameters:

node - The substring node

Returns:

The number of candidates

Throws:

java.lang.Exception - If there is an error accessing an index

getFullScan

private long getFullScan(org.apache.directory.api.ldap.model.filter.LeafNode node)
                  throws java.lang.Exception

Gets the total number of entries within the database index if one is available otherwise the count of all the entries within the database is returned.

Parameters:

node - the leaf node to get a full scan count for

Returns:

the worst case full scan count

Throws:

java.lang.Exception - if there is an error access database indices

getPresenceScan

private long getPresenceScan(org.apache.directory.api.ldap.model.filter.PresenceNode node)
                      throws java.lang.Exception

Gets the number of entries that would be returned by a presence node assertion. Leverages the presence system index for scan counts.

Parameters:

node - the presence node

Returns:

the number of entries matched for the presence of an attribute

Throws:

java.lang.Exception - if errors result

getScopeScan

private long getScopeScan(org.apache.directory.api.ldap.model.filter.ScopeNode node)
                   throws java.lang.Exception

Gets the scan count for the scope node attached to this filter.

Parameters:

node - the ScopeNode

Returns:

the scan count for scope

Throws:

java.lang.Exception - if any errors result