001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020 package org.apache.directory.server.xdbm.search.impl; 021 022 023 import java.util.List; 024 025 import org.apache.directory.shared.ldap.filter.AndNode; 026 import org.apache.directory.shared.ldap.filter.ApproximateNode; 027 import org.apache.directory.shared.ldap.filter.AssertionNode; 028 import org.apache.directory.shared.ldap.filter.BranchNode; 029 import org.apache.directory.shared.ldap.filter.EqualityNode; 030 import org.apache.directory.shared.ldap.filter.ExprNode; 031 import org.apache.directory.shared.ldap.filter.ExtensibleNode; 032 import org.apache.directory.shared.ldap.filter.GreaterEqNode; 033 import org.apache.directory.shared.ldap.filter.LeafNode; 034 import org.apache.directory.shared.ldap.filter.LessEqNode; 035 import org.apache.directory.shared.ldap.filter.NotNode; 036 import org.apache.directory.shared.ldap.filter.OrNode; 037 import org.apache.directory.shared.ldap.filter.PresenceNode; 038 import org.apache.directory.shared.ldap.filter.ScopeNode; 039 import org.apache.directory.shared.ldap.filter.SimpleNode; 040 import org.apache.directory.shared.ldap.filter.SubstringNode; 041 import org.apache.directory.server.i18n.I18n; 042 import org.apache.directory.server.xdbm.Index; 043 import org.apache.directory.server.xdbm.search.Optimizer; 044 import org.apache.directory.server.xdbm.Store; 045 046 047 /** 048 * Optimizer that annotates the filter using scan counts. 049 * 050 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 051 * @version $Rev: 920097 $ 052 */ 053 public class DefaultOptimizer<E, ID> implements Optimizer 054 { 055 /** the database this optimizer operates on */ 056 private final Store<E, ID> db; 057 private ID contextEntryId; 058 059 060 /** 061 * Creates an optimizer on a database. 062 * 063 * @param db the database this optimizer works for. 064 */ 065 public DefaultOptimizer( Store<E, ID> db ) throws Exception 066 { 067 this.db = db; 068 } 069 070 071 private ID getContextEntryId() throws Exception 072 { 073 if ( contextEntryId == null ) 074 { 075 try 076 { 077 this.contextEntryId = db.getEntryId( db.getSuffix().getNormName() ); 078 } 079 catch ( Exception e ) 080 { 081 // might not have been created 082 } 083 } 084 085 if ( contextEntryId == null ) 086 { 087 return db.getDefaultId(); 088 } 089 090 return contextEntryId; 091 } 092 093 094 /** 095 * Annotates the expression tree to determine optimal evaluation order based 096 * on the scan count for indices that exist for each expression node. If an 097 * index on the attribute does not exist an IndexNotFoundException will be 098 * thrown. 099 * 100 * @see org.apache.directory.server.xdbm.search.Optimizer#annotate(ExprNode) 101 */ 102 @SuppressWarnings("unchecked") 103 public Long annotate( ExprNode node ) throws Exception 104 { 105 // Start off with the worst case unless scan count says otherwise. 106 Long count = Long.MAX_VALUE; 107 108 /* -------------------------------------------------------------------- 109 * H A N D L E L E A F N O D E S 110 * -------------------------------------------------------------------- 111 * 112 * Each leaf node is based on an attribute and it represents a condition 113 * that needs to be statisfied. We ask the index (if one exists) for 114 * the attribute to give us a scan count of all the candidates that 115 * would satisfy the attribute assertion represented by the leaf node. 116 * 117 * This is conducted differently based on the type of the leaf node. 118 * Comments on each node type explain how each scan count is arrived at. 119 */ 120 121 if ( node instanceof ScopeNode ) 122 { 123 count = getScopeScan( ( ScopeNode ) node ); 124 } 125 else if ( node instanceof AssertionNode ) 126 { 127 /* 128 * Leave it up to the assertion node to determine just how much it 129 * will cost us. Anyway it defaults to a maximum scan count if a 130 * scan count is not specified by the implementation. 131 */ 132 } 133 else if ( node.isLeaf() ) 134 { 135 LeafNode leaf = ( LeafNode ) node; 136 137 if ( node instanceof PresenceNode ) 138 { 139 count = getPresenceScan( ( PresenceNode ) leaf ); 140 } 141 else if ( node instanceof EqualityNode ) 142 { 143 count = getEqualityScan( ( EqualityNode ) leaf ); 144 } 145 else if ( node instanceof GreaterEqNode ) 146 { 147 count = getGreaterLessScan( ( GreaterEqNode ) leaf, SimpleNode.EVAL_GREATER ); 148 } 149 else if ( node instanceof LessEqNode ) 150 { 151 count = getGreaterLessScan( ( SimpleNode ) leaf, SimpleNode.EVAL_LESSER ); 152 } 153 else if ( node instanceof SubstringNode ) 154 { 155 /** Cannot really say so we presume the total index count */ 156 count = getFullScan( leaf ); 157 } 158 else if ( node instanceof ExtensibleNode ) 159 { 160 /** Cannot really say so we presume the total index count */ 161 count = getFullScan( leaf ); 162 } 163 else if ( node instanceof ApproximateNode ) 164 { 165 /** Feature not implemented so we just use equality matching */ 166 count = getEqualityScan( ( ApproximateNode ) leaf ); 167 } 168 else 169 { 170 throw new IllegalArgumentException( I18n.err( I18n.ERR_711 ) ); 171 } 172 } 173 // -------------------------------------------------------------------- 174 // H A N D L E B R A N C H N O D E S 175 // -------------------------------------------------------------------- 176 else 177 { 178 if ( node instanceof AndNode ) 179 { 180 count = getConjunctionScan( ( AndNode ) node ); 181 } 182 else if ( node instanceof OrNode ) 183 { 184 count = getDisjunctionScan( ( OrNode ) node ); 185 } 186 else if ( node instanceof NotNode ) 187 { 188 annotate( ( ( NotNode ) node ).getFirstChild() ); 189 190 /* 191 * A negation filter is always worst case since we will have 192 * to retrieve all entries from the master table then test 193 * each one against the negated child filter. There is no way 194 * to use the indices. 195 */ 196 count = Long.MAX_VALUE; 197 } 198 else 199 { 200 throw new IllegalArgumentException( I18n.err( I18n.ERR_712 ) ); 201 } 202 } 203 204 // Protect against overflow when counting. 205 if ( count < 0L ) 206 { 207 count = Long.MAX_VALUE; 208 } 209 210 node.set( "count", count ); 211 return count; 212 } 213 214 215 /** 216 * ANDs or Conjunctions take the count of the smallest child as their count. 217 * This is the best that a conjunction can do and should be used rather than 218 * the worst case. Notice that we annotate the child node with a recursive 219 * call before accessing its count parameter making the chain recursion 220 * depth first. 221 * 222 * @param node a AND (Conjunction) BranchNode 223 * @return the calculated scan count 224 * @throws Exception if there is an error 225 */ 226 private long getConjunctionScan( BranchNode node ) throws Exception 227 { 228 long count = Long.MAX_VALUE; 229 List<ExprNode> children = node.getChildren(); 230 231 for ( ExprNode child : children ) 232 { 233 annotate( child ); 234 count = Math.min( ( ( Long ) child.get( "count" ) ), count ); 235 } 236 237 return count; 238 } 239 240 241 /** 242 * Disjunctions (OR) are the union of candidates across all subexpressions 243 * so we add all the counts of the child nodes. Notice that we annotate the 244 * child node with a recursive call. 245 * 246 * @param node the OR branch node 247 * @return the scan count on the OR node 248 * @throws Exception if there is an error 249 */ 250 private long getDisjunctionScan( BranchNode node ) throws Exception 251 { 252 List<ExprNode> children = node.getChildren(); 253 long total = 0L; 254 255 for ( ExprNode child : children ) 256 { 257 annotate( child ); 258 total += ( Long ) child.get( "count" ); 259 } 260 261 return total; 262 } 263 264 265 /** 266 * Gets the worst case scan count for all entries that satisfy the equality 267 * assertion in the SimpleNode argument. 268 * 269 * @param node the node to get a scan count for 270 * @return the worst case 271 * @throws Exception if there is an error accessing an index 272 */ 273 @SuppressWarnings("unchecked") 274 private <V> long getEqualityScan( SimpleNode<V> node ) throws Exception 275 { 276 if ( db.hasIndexOn( node.getAttribute() ) ) 277 { 278 Index<V, E, ID> idx = ( Index<V, E, ID> ) db.getIndex( node.getAttribute() ); 279 return idx.count( node.getValue().get() ); 280 } 281 282 // count for non-indexed attribute is unknown so we presume da worst 283 return Long.MAX_VALUE; 284 } 285 286 287 /** 288 * Gets a scan count of the nodes that satisfy the greater or less than test 289 * specified by the node. 290 * 291 * @param node the greater or less than node to get a count for 292 * @param isGreaterThan if true test is for >=, otherwise <= 293 * @return the scan count of all nodes satisfying the AVA 294 * @throws Exception if there is an error accessing an index 295 */ 296 @SuppressWarnings("unchecked") 297 private <V> long getGreaterLessScan( SimpleNode<V> node, boolean isGreaterThan ) throws Exception 298 { 299 if ( db.hasIndexOn( node.getAttribute() ) ) 300 { 301 Index<V, E, ID> idx = ( Index<V, E, ID> ) db.getIndex( node.getAttribute() ); 302 if ( isGreaterThan ) 303 { 304 return idx.greaterThanCount( node.getValue().get() ); 305 } 306 else 307 { 308 return idx.lessThanCount( node.getValue().get() ); 309 } 310 } 311 312 // count for non-indexed attribute is unknown so we presume da worst 313 return Long.MAX_VALUE; 314 } 315 316 317 /** 318 * Gets the total number of entries within the database index if one is 319 * available otherwise the count of all the entries within the database is 320 * returned. 321 * 322 * @param node the leaf node to get a full scan count for 323 * @return the worst case full scan count 324 * @throws Exception if there is an error access database indices 325 */ 326 @SuppressWarnings("unchecked") 327 private long getFullScan( LeafNode node ) throws Exception 328 { 329 if ( db.hasIndexOn( node.getAttribute() ) ) 330 { 331 Index idx = db.getIndex( node.getAttribute() ); 332 return idx.count(); 333 } 334 335 return Long.MAX_VALUE; 336 } 337 338 339 /** 340 * Gets the number of entries that would be returned by a presence node 341 * assertion. Leverages the existence system index for scan counts. 342 * 343 * @param node the presence node 344 * @return the number of entries matched for the presence of an attribute 345 * @throws Exception if errors result 346 */ 347 private long getPresenceScan( PresenceNode node ) throws Exception 348 { 349 if ( db.hasUserIndexOn( node.getAttribute() ) ) 350 { 351 Index<String, E, ID> idx = db.getPresenceIndex(); 352 return idx.count( node.getAttribute() ); 353 } 354 else if ( db.hasSystemIndexOn( node.getAttribute() ) ) 355 { 356 // the system indices (objectClass, entryUUID, entryCSN) are maintained for 357 // each entry, so we could just return the index count 358 Index<?, E, ID> idx = db.getSystemIndex( node.getAttribute() ); 359 return idx.count(); 360 } 361 362 return Long.MAX_VALUE; 363 } 364 365 366 /** 367 * Gets the scan count for the scope node attached to this filter. 368 * 369 * @param node the ScopeNode 370 * @return the scan count for scope 371 * @throws Exception if any errors result 372 */ 373 private long getScopeScan( ScopeNode node ) throws Exception 374 { 375 ID id = db.getEntryId( node.getBaseDn() ); 376 switch ( node.getScope() ) 377 { 378 case OBJECT: 379 return 1L; 380 381 case ONELEVEL: 382 return db.getChildCount( id ); 383 384 case SUBTREE: 385 if ( id == getContextEntryId() ) 386 { 387 return db.count(); 388 } 389 else 390 { 391 return db.getSubLevelIndex().count( id ); 392 } 393 394 default: 395 throw new IllegalArgumentException( I18n.err( I18n.ERR_713 ) ); 396 } 397 } 398 }