View Javadoc

1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  You may obtain a copy of the License at
9    *  
10   *    http://www.apache.org/licenses/LICENSE-2.0
11   *  
12   *  Unless required by applicable law or agreed to in writing,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License. 
18   *  
19   */
20  package org.apache.directory.server.xdbm.search.impl;
21  
22  
23  import java.util.List;
24  
25  import org.apache.directory.shared.ldap.filter.AndNode;
26  import org.apache.directory.shared.ldap.filter.ApproximateNode;
27  import org.apache.directory.shared.ldap.filter.AssertionNode;
28  import org.apache.directory.shared.ldap.filter.BranchNode;
29  import org.apache.directory.shared.ldap.filter.EqualityNode;
30  import org.apache.directory.shared.ldap.filter.ExprNode;
31  import org.apache.directory.shared.ldap.filter.ExtensibleNode;
32  import org.apache.directory.shared.ldap.filter.GreaterEqNode;
33  import org.apache.directory.shared.ldap.filter.LeafNode;
34  import org.apache.directory.shared.ldap.filter.LessEqNode;
35  import org.apache.directory.shared.ldap.filter.NotNode;
36  import org.apache.directory.shared.ldap.filter.OrNode;
37  import org.apache.directory.shared.ldap.filter.PresenceNode;
38  import org.apache.directory.shared.ldap.filter.ScopeNode;
39  import org.apache.directory.shared.ldap.filter.SimpleNode;
40  import org.apache.directory.shared.ldap.filter.SubstringNode;
41  import org.apache.directory.server.xdbm.Index;
42  import org.apache.directory.server.xdbm.search.Optimizer;
43  import org.apache.directory.server.xdbm.Store;
44  
45  
46  /**
47   * Optimizer that annotates the filter using scan counts.
48   * 
49   * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
50   * @version $Rev: 689396 $
51   */
52  public class DefaultOptimizer<E> implements Optimizer
53  {
54      /** the database this optimizer operates on */
55      private final Store<E> db;
56      private Long contextEntryId;
57      
58  
59      /**
60       * Creates an optimizer on a database.
61       *
62       * @param db the database this optimizer works for.
63       */
64      public DefaultOptimizer( Store<E> db ) throws Exception
65      {
66          this.db = db;
67      }
68  
69      
70      private Long getContextEntryId()
71      {
72          if ( contextEntryId == null )
73          {
74              try
75              {
76                  this.contextEntryId = db.getEntryId( db.getSuffix().getNormName() );
77              }
78              catch ( Exception e )
79              {
80                  // might not have been created
81              }
82          }
83          
84          if ( contextEntryId == null )
85          {
86              return 1L;
87          }
88          
89          return contextEntryId;
90      }
91      
92  
93      /**
94       * Annotates the expression tree to determine optimal evaluation order based
95       * on the scan count for indices that exist for each expression node.  If an
96       * index on the attribute does not exist an IndexNotFoundException will be
97       * thrown.
98       *
99       * @see org.apache.directory.server.xdbm.search.Optimizer#annotate(ExprNode)
100      */
101     @SuppressWarnings("unchecked")
102     public Long annotate( ExprNode node ) throws Exception
103     {
104         // Start off with the worst case unless scan count says otherwise.
105         Long count = Long.MAX_VALUE;
106 
107         /* --------------------------------------------------------------------
108          *                 H A N D L E   L E A F   N O D E S          
109          * --------------------------------------------------------------------
110          * 
111          * Each leaf node is based on an attribute and it represents a condition
112          * that needs to be statisfied.  We ask the index (if one exists) for 
113          * the attribute to give us a scan count of all the candidates that 
114          * would satisfy the attribute assertion represented by the leaf node.
115          * 
116          * This is conducted differently based on the type of the leaf node.
117          * Comments on each node type explain how each scan count is arrived at.
118          */
119 
120         if ( node instanceof ScopeNode )
121         {
122             count = getScopeScan( ( ScopeNode ) node );
123         }
124         else if ( node instanceof AssertionNode )
125         {
126             /* 
127              * Leave it up to the assertion node to determine just how much it
128              * will cost us.  Anyway it defaults to a maximum scan count if a
129              * scan count is not specified by the implementation.
130              */
131         }
132         else if ( node.isLeaf() )
133         {
134             LeafNode leaf = ( LeafNode ) node;
135 
136             if ( node instanceof PresenceNode )
137             {
138                 count = getPresenceScan( ( PresenceNode ) leaf );
139             }
140             else if ( node instanceof EqualityNode )
141             {
142                 count = getEqualityScan( ( EqualityNode ) leaf );
143             }
144             else if ( node instanceof GreaterEqNode )
145             {
146                 count = getGreaterLessScan( ( GreaterEqNode ) leaf, SimpleNode.EVAL_GREATER );
147             }
148             else if ( node instanceof LessEqNode )
149             {
150                 count = getGreaterLessScan( ( SimpleNode ) leaf, SimpleNode.EVAL_LESSER );
151             }
152             else if ( node instanceof SubstringNode )
153             {
154                 /** Cannot really say so we presume the total index count */
155                 count = getFullScan( leaf );
156             }
157             else if ( node instanceof ExtensibleNode )
158             {
159                 /** Cannot really say so we presume the total index count */
160                 count = getFullScan( leaf );
161             }
162             else if ( node instanceof ApproximateNode )
163             {
164                 /** Feature not implemented so we just use equality matching */
165                 count = getEqualityScan( ( ApproximateNode ) leaf );
166             }
167             else
168             {
169                 throw new IllegalArgumentException( "Unrecognized leaf node" );
170             }
171         }
172         // --------------------------------------------------------------------
173         //                 H A N D L E   B R A N C H   N O D E S       
174         // --------------------------------------------------------------------
175         else
176         {
177             if ( node instanceof AndNode )
178             {
179             	count = getConjunctionScan( (AndNode)node );
180             }
181             else if ( node instanceof OrNode )
182             {
183             	count = getDisjunctionScan( (OrNode)node );
184             }
185             else if ( node instanceof NotNode )
186             {
187                 annotate( ( ( NotNode ) node ).getFirstChild() );
188 
189                 /*
190                  * A negation filter is always worst case since we will have
191                  * to retrieve all entries from the master table then test
192                  * each one against the negated child filter.  There is no way
193                  * to use the indices.
194                  */
195                 count = Long.MAX_VALUE;
196             }
197             else
198             {
199             	throw new IllegalArgumentException( "Unrecognized branch node type" );
200             }
201         }
202 
203         // Protect against overflow when counting.
204         if ( count < 0L )
205         {
206             count = Long.MAX_VALUE;
207         }
208 
209         node.set( "count", count );
210         return count;
211     }
212 
213 
214     /**
215      * ANDs or Conjunctions take the count of the smallest child as their count.
216      * This is the best that a conjunction can do and should be used rather than
217      * the worst case. Notice that we annotate the child node with a recursive 
218      * call before accessing its count parameter making the chain recursion 
219      * depth first.
220      *
221      * @param node a AND (Conjunction) BranchNode
222      * @return the calculated scan count
223      * @throws Exception if there is an error
224      */
225     private long getConjunctionScan( BranchNode node ) throws Exception
226     {
227         long count = Long.MAX_VALUE;
228         List<ExprNode> children = node.getChildren();
229 
230         for ( ExprNode child : children )
231         {
232             annotate( child );
233             count = Math.min( ( ( Long ) child.get( "count" ) ), count );
234         }
235 
236         return count;
237     }
238 
239 
240     /**
241      * Disjunctions (OR) are the union of candidates across all subexpressions 
242      * so we add all the counts of the child nodes. Notice that we annotate the 
243      * child node with a recursive call.
244      *
245      * @param node the OR branch node
246      * @return the scan count on the OR node
247      * @throws Exception if there is an error
248      */
249     private long getDisjunctionScan( BranchNode node ) throws Exception
250     {
251         List<ExprNode> children = node.getChildren();
252         long total = 0L;
253 
254         for ( ExprNode child : children )
255         {
256             annotate( child );
257             total += ( Long ) child.get( "count" );
258         }
259         
260         return total;
261     }
262 
263 
264     /**
265      * Gets the worst case scan count for all entries that satisfy the equality
266      * assertion in the SimpleNode argument.  
267      *
268      * @param node the node to get a scan count for 
269      * @return the worst case
270      * @throws Exception if there is an error accessing an index
271      */
272     @SuppressWarnings("unchecked")
273     private<V> long getEqualityScan( SimpleNode<V> node ) throws Exception
274     {
275         if ( db.hasUserIndexOn( node.getAttribute() ) )
276         {
277             Index<V,E> idx = ( Index<V, E> ) db.getUserIndex( node.getAttribute() );
278             return idx.count( node.getValue().get() );
279         }
280 
281         // count for non-indexed attribute is unknown so we presume da worst
282         return Long.MAX_VALUE;
283     }
284 
285 
286     /**
287      * Gets a scan count of the nodes that satisfy the greater or less than test
288      * specified by the node.
289      *
290      * @param node the greater or less than node to get a count for 
291      * @param isGreaterThan if true test is for >=, otherwise <=
292      * @return the scan count of all nodes satisfying the AVA
293      * @throws Exception if there is an error accessing an index
294      */
295     @SuppressWarnings("unchecked")
296     private<V> long getGreaterLessScan( SimpleNode<V> node, boolean isGreaterThan ) throws Exception
297     {
298         if ( db.hasUserIndexOn( node.getAttribute() ) )
299         {
300             Index<V, E> idx = ( Index<V, E> ) db.getUserIndex( node.getAttribute() );
301             if ( isGreaterThan )
302             {
303                 return idx.greaterThanCount( node.getValue().get() );
304             }
305             else
306             {
307                 return idx.lessThanCount( node.getValue().get() );
308             }
309         }
310 
311         // count for non-indexed attribute is unknown so we presume da worst
312         return Long.MAX_VALUE;
313     }
314 
315 
316     /**
317      * Gets the total number of entries within the database index if one is 
318      * available otherwise the count of all the entries within the database is
319      * returned.
320      *
321      * @param node the leaf node to get a full scan count for 
322      * @return the worst case full scan count
323      * @throws Exception if there is an error access database indices
324      */
325     @SuppressWarnings("unchecked")
326     private long getFullScan( LeafNode node ) throws Exception
327     {
328         if ( db.hasUserIndexOn( node.getAttribute() ) )
329         {
330             Index idx = db.getUserIndex( node.getAttribute() );
331             return idx.count();
332         }
333 
334         return Long.MAX_VALUE;
335     }
336 
337 
338     /**
339      * Gets the number of entries that would be returned by a presence node
340      * assertion.  Leverages the existance system index for scan counts.
341      *
342      * @param node the presence node
343      * @return the number of entries matched for the presence of an attribute
344      * @throws Exception if errors result
345      */
346     private long getPresenceScan( PresenceNode node ) throws Exception
347     {
348         if ( db.hasUserIndexOn( node.getAttribute() ) )
349         {
350             Index<String,E> idx = db.getPresenceIndex();
351             return idx.count( node.getAttribute() );
352         }
353 
354         return Long.MAX_VALUE;
355     }
356 
357 
358     /**
359      * Gets the scan count for the scope node attached to this filter.
360      *
361      * @param node the ScopeNode
362      * @return the scan count for scope
363      * @throws Exception if any errors result
364      */
365     private long getScopeScan( ScopeNode node ) throws Exception
366     {
367         Long id = db.getEntryId( node.getBaseDn() );
368         switch ( node.getScope() )
369         {
370             case OBJECT:
371                 return 1L;
372             
373             case ONELEVEL:
374                 return db.getChildCount( id );
375                 
376             case SUBTREE:
377                 if ( id == getContextEntryId() )
378                 {
379                     return db.count();
380                 }
381                 else
382                 {
383                     return db.getSubLevelIndex().count( id );
384                 }
385             
386             default:
387                 throw new IllegalArgumentException( "Unrecognized search scope " + "value for filter scope node" );
388         }
389     }
390 }