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    }