View Javadoc

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