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 }