1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
48
49
50
51
52 public class DefaultOptimizer<E> implements Optimizer
53 {
54
55 private final Store<E> db;
56 private Long contextEntryId;
57
58
59
60
61
62
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
81 }
82 }
83
84 if ( contextEntryId == null )
85 {
86 return 1L;
87 }
88
89 return contextEntryId;
90 }
91
92
93
94
95
96
97
98
99
100
101 @SuppressWarnings("unchecked")
102 public Long annotate( ExprNode node ) throws Exception
103 {
104
105 Long count = Long.MAX_VALUE;
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120 if ( node instanceof ScopeNode )
121 {
122 count = getScopeScan( ( ScopeNode ) node );
123 }
124 else if ( node instanceof AssertionNode )
125 {
126
127
128
129
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
155 count = getFullScan( leaf );
156 }
157 else if ( node instanceof ExtensibleNode )
158 {
159
160 count = getFullScan( leaf );
161 }
162 else if ( node instanceof ApproximateNode )
163 {
164
165 count = getEqualityScan( ( ApproximateNode ) leaf );
166 }
167 else
168 {
169 throw new IllegalArgumentException( "Unrecognized leaf node" );
170 }
171 }
172
173
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
191
192
193
194
195 count = Long.MAX_VALUE;
196 }
197 else
198 {
199 throw new IllegalArgumentException( "Unrecognized branch node type" );
200 }
201 }
202
203
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
216
217
218
219
220
221
222
223
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
242
243
244
245
246
247
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
266
267
268
269
270
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
282 return Long.MAX_VALUE;
283 }
284
285
286
287
288
289
290
291
292
293
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
312 return Long.MAX_VALUE;
313 }
314
315
316
317
318
319
320
321
322
323
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
340
341
342
343
344
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
360
361
362
363
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 }