DefaultOptimizer


1   /*
2    *   Copyright 2004 The Apache Software Foundation
3    *
4    *   Licensed under the Apache License, Version 2.0 (the "License");
5    *   you may not use this file except in compliance with the License.
6    *   You may obtain a copy of the License at
7    *
8    *       http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *   Unless required by applicable law or agreed to in writing, software
11   *   distributed under the License is distributed on an "AS IS" BASIS,
12   *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *   See the License for the specific language governing permissions and
14   *   limitations under the License.
15   *
16   */
17  package org.apache.ldap.server.db;
18  
19  
20  import org.apache.ldap.common.filter.*;
21  
22  import javax.naming.NamingException  ;
23  import javax.naming.directory.SearchControls  ;
24  import java.math.BigInteger  ;
25  import java.util.ArrayList  ;
26  
27  
28  /**
29   * Optimizer that annotates the filter using scan counts.
30   * 
31   * @author <a HREF="mailto:dev@directory.apache.org">Apache Directory Project</a>
32   * @version $Rev: 169198 $
33   */
34  public class DefaultOptimizer implements Optimizer
35  {
36      /** the maximum size for a count Integer.MAX_VALUE as a BigInteger */
37      private static final BigInteger   MAX = BigInteger.valueOf( Integer.MAX_VALUE );
38      /** the database this optimizer operates on */
39      private Database db;
40      
41      
42      /**
43       * Creates an optimizer on a database.
44       *
45       * @param db the database this optimizer works for.
46       */
47      public DefaultOptimizer( Database db )
48      {
49          this.db = db;
50      }
51      
52  
53      /**
54       * Annotates the expression tree to determine optimal evaluation order based
55       * on the scan count for indices that exist for each expression node.  If an
56       * index on the attribute does not exist an IndexNotFoundException will be
57       * thrown.
58       *
59       * @see Optimizer#annotate(ExprNode)
60       */
61      public void annotate( ExprNode node ) throws NamingException  
62      {
63          // Start off with the worst case unless scan count says otherwise.
64          BigInteger   count = MAX;
65  
66          /* --------------------------------------------------------------------
67           *                 H A N D L E   L E A F   N O D E S          
68           * --------------------------------------------------------------------
69           * 
70           * Each leaf node is based on an attribute and it represents a condition
71           * that needs to be statisfied.  We ask the index (if one exists) for 
72           * the attribute to give us a scan count of all the candidates that 
73           * would satisfy the attribute assertion represented by the leaf node.
74           * 
75           * This is conducted differently based on the type of the leaf node.
76           * Comments on each node type explain how each scan count is arrived at.
77           */
78           
79          if ( node instanceof ScopeNode )
80          {
81              count = getScopeScan( ( ScopeNode ) node );
82          }
83          else if ( node instanceof AssertionNode )
84          {
85              /* 
86               * Leave it up to the assertion node to determine just how much it
87               * will cost us.  Anyway it defaults to a maximum scan count if a
88               * scan count is not specified by the implementation.
89               */
90          }
91          else if ( node.isLeaf() ) 
92          {
93              LeafNode leaf = ( LeafNode ) node;
94              
95              switch ( leaf.getAssertionType() ) 
96              {
97              case( LeafNode.APPROXIMATE ):
98                  /** Feature not implemented so we just use equality matching */
99                  count = getEqualityScan( ( SimpleNode ) leaf );
100                 break;
101             case( LeafNode.EQUALITY ):
102                 count = getEqualityScan( ( SimpleNode ) leaf );
103                 break;
104             case( LeafNode.EXTENSIBLE ):
105                 /** Cannot really say so we presume the total index count */
106                 count = getFullScan( leaf );
107                 break;
108             case( LeafNode.GREATEREQ ):
109                 count = getGreaterLessScan( ( SimpleNode ) leaf, true );
110                 break;
111             case( LeafNode.LESSEQ ):
112                 count = getGreaterLessScan( ( SimpleNode ) leaf, false );
113                 break;
114             case( LeafNode.PRESENCE ):
115                 count = getPresenceScan( ( PresenceNode ) leaf );
116                 break;
117             case( LeafNode.SUBSTRING ):
118                 /** Cannot really say so we presume the total index count */
119                 count = getFullScan( leaf );
120                 break;
121             default:
122                 throw new IllegalArgumentException  ( "Unrecognized leaf node" );
123             }
124         } 
125         // --------------------------------------------------------------------
126         //                 H A N D L E   B R A N C H   N O D E S       
127         // --------------------------------------------------------------------
128         else 
129         {
130             BranchNode bnode = ( BranchNode ) node;
131 
132             switch( bnode.getOperator() )
133             {
134             case( BranchNode.AND ):
135                 count = getConjunctionScan( bnode );
136                 break;
137             case( BranchNode.NOT ):
138                 count = getNegationScan( bnode );
139                 break;
140             case( BranchNode.OR ):
141                 count = getDisjunctionScan( bnode );
142                 break;
143             default:
144                 throw new IllegalArgumentException  (
145                     "Unrecognized branch node type" );
146             }
147         }
148 
149         // Protect against overflow when counting.
150         if ( count.compareTo( BigInteger.ZERO ) < 0 ) 
151         {
152             count = MAX;
153         }
154 
155         node.set( "count", count );
156     }
157 
158 
159     /**
160      * ANDs or Conjunctions take the count of the smallest child as their count.
161      * This is the best that a conjunction can do and should be used rather than
162      * the worst case. Notice that we annotate the child node with a recursive 
163      * call before accessing its count parameter making the chain recursion 
164      * depth first.
165      *
166      * @param node a AND (Conjunction) BranchNode
167      * @return the calculated scan count
168      * @throws NamingException if there is an error
169      */
170     private BigInteger   getConjunctionScan( BranchNode node ) throws NamingException  
171     {
172         BigInteger   count = BigInteger.valueOf( Integer.MAX_VALUE );  
173         ArrayList   children = node.getChildren(); 
174         
175         for ( int ii = 0; ii < children.size(); ii++ ) 
176         {
177             ExprNode child = ( ExprNode ) children.get( ii );
178             annotate( child );
179             count = ( ( BigInteger   ) child.get( "count" ) ).min( count );
180         }
181 
182         return count;    
183     }
184     
185 
186     /**
187      * Negation counts are estimated in one of two ways depending on its 
188      * composition.  If the sole child of the negation is a leaf and an index
189      * exists for the attribute of the leaf then the count on the index is taken
190      * as the scan count.  If the child is a branch node then the count of the
191      * negation node is set to the total count of entries in the master table.
192      * This last resort tactic is used to get a rough estimate because it would 
193      * cost too much to get an exact estimate on the count of a negation on a
194      * branch node.
195      *
196      * @param node the negation node
197      * @return the scan count
198      * @throws NamingException if there is an error
199      */
200     private BigInteger   getNegationScan( BranchNode node ) throws NamingException  
201     {
202         ExprNode onlyChild = ( ExprNode ) node.getChildren().get( 0 );
203         
204         annotate( onlyChild );
205 
206         if ( onlyChild.isLeaf() 
207             && ! ( onlyChild instanceof ScopeNode )
208             && ! ( onlyChild instanceof AssertionNode )  
209             && ! ( onlyChild instanceof PresenceNode ) )
210         {
211             LeafNode leaf = ( LeafNode ) onlyChild;
212             Index idx = db.getUserIndex( leaf.getAttribute() );
213             return BigInteger.valueOf( idx.count() );
214         } 
215 
216         return BigInteger.valueOf( db.count() );
217     }
218     
219 
220     /**
221      * Disjunctions (OR) are the union of candidates across all subexpressions 
222      * so we add all the counts of the child nodes. Notice that we annotate the 
223      * child node with a recursive call.
224      *
225      * @param node the OR branch node
226      * @return the scan count on the OR node
227      * @throws NamingException if there is an error
228      */
229     private BigInteger   getDisjunctionScan( BranchNode node ) throws NamingException  
230     {
231         ArrayList   children = node.getChildren();
232         BigInteger   total = BigInteger.ZERO;
233         
234         for ( int ii = 0; ii < children.size(); ii++ ) 
235         {
236             ExprNode child = ( ExprNode ) children.get( ii );
237             annotate( child );
238             total = total.add( ( BigInteger   ) child.get( "count" ) );
239         }
240 
241         return total;    
242     }
243     
244 
245     /**
246      * Gets the worst case scan count for all entries that satisfy the equality
247      * assertion in the SimpleNode argument.  
248      *
249      * @param node the node to get a scan count for 
250      * @return the worst case
251      * @throws NamingException if there is an error accessing an index
252      */
253     private BigInteger   getEqualityScan( SimpleNode node )
254         throws NamingException  
255     {
256         if ( db.hasUserIndexOn( node.getAttribute() ) )
257         {
258             Index idx = db.getUserIndex( node.getAttribute() );
259             return BigInteger.valueOf( idx.count( node.getValue() ) );
260         }
261 
262         // count for non-indexed attribute is unknown so we presume da worst
263         return MAX;
264     }
265 
266 
267     /**
268      * Gets a scan count of the nodes that satisfy the greater or less than test
269      * specified by the node.
270      *
271      * @param node the greater or less than node to get a count for 
272      * @param isGreaterThan if true test is for >=, otherwise <=
273      * @return the scan count of all nodes satisfying the AVA
274      * @throws NamingException if there is an error accessing an index
275      */
276     private BigInteger   getGreaterLessScan( SimpleNode node, 
277         boolean isGreaterThan ) throws NamingException  
278     {
279         if ( db.hasUserIndexOn( node.getAttribute() ) )
280         {
281             Index idx = db.getUserIndex( node.getAttribute() );
282             int count = idx.count( node.getValue(), isGreaterThan );
283             return BigInteger.valueOf( count );
284         }
285 
286         // count for non-indexed attribute is unknown so we presume da worst
287         return MAX;
288     }
289 
290 
291     /**
292      * Gets the total number of entries within the database index if one is 
293      * available otherwise the count of all the entries within the database is
294      * returned.
295      *
296      * @param node the leaf node to get a full scan count for 
297      * @return the worst case full scan count
298      * @throws NamingException if there is an error access database indices
299      */
300     private BigInteger   getFullScan( LeafNode node )
301         throws NamingException  
302     {
303         if ( db.hasUserIndexOn( node.getAttribute() ) )
304         {
305             Index idx = db.getUserIndex( node.getAttribute() );
306             int count = idx.count();
307             return BigInteger.valueOf( count );
308         }
309         
310         return MAX;
311     }
312 
313 
314     /**
315      * Gets the number of entries that would be returned by a presence node
316      * assertion.  Leverages the existance system index for scan counts.
317      *
318      * @param node the presence node
319      * @return the number of entries matched for the presence of an attribute
320      * @throws NamingException if errors result
321      */
322     private BigInteger   getPresenceScan( PresenceNode node ) throws NamingException  
323     {
324         if ( db.hasUserIndexOn( node.getAttribute() ) )
325         {
326             Index idx = db.getExistanceIndex();
327             int count = idx.count( node.getAttribute() );
328             return BigInteger.valueOf( count );
329         }
330         
331         return MAX;
332     }
333 
334 
335     /**
336      * Gets the scan count for the scope node attached to this filter.
337      *
338      * @param node the ScopeNode
339      * @return the scan count for scope
340      * @throws NamingException if any errors result
341      */
342     private BigInteger   getScopeScan( ScopeNode node ) throws NamingException  
343     {
344         switch ( node.getScope() )
345         {
346             case ( SearchControls.OBJECT_SCOPE ):
347                 return BigInteger.ONE;
348             case ( SearchControls.ONELEVEL_SCOPE ):
349                 BigInteger   id = db.getEntryId( node.getBaseDn() );
350                 return BigInteger.valueOf( db.getChildCount( id ) );
351             case ( SearchControls.SUBTREE_SCOPE ):
352                 return BigInteger.valueOf( db.count() );
353             default:
354                 throw new IllegalArgumentException  ( "Unrecognized search scope "
355                     + "value for filter scope node" );
356         }
357     }
358 }
359
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags