1
2
3
4
5
6
7
8
9
10
11
12
13
14
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: 159259 $
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
64 BigInteger count = MAX;
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79 if ( node instanceof ScopeNode )
80 {
81 count = getScopeScan( ( ScopeNode ) node );
82 }
83 else if ( node instanceof AssertionNode )
84 {
85
86
87
88
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
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
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
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
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 }