path: root/db/queryutil.h

// queryutil.h

/*    Copyright 2009 10gen Inc.
 *
 *    Licensed under the Apache License, Version 2.0 (the "License");
 *    you may not use this file except in compliance with the License.
 *    You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 *    Unless required by applicable law or agreed to in writing, software
 *    distributed under the License is distributed on an "AS IS" BASIS,
 *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *    See the License for the specific language governing permissions and
 *    limitations under the License.
 */

#pragma once

#include "jsobj.h"

namespace mongo {

    struct FieldBound {
        BSONElement _bound;
        bool _inclusive;
        bool operator==( const FieldBound &other ) const {
            return _bound.woCompare( other._bound ) == 0 &&
                   _inclusive == other._inclusive;
        }
        void flipInclusive() { _inclusive = !_inclusive; }
    };

    struct FieldInterval {
        FieldInterval() : _cachedEquality( -1 ) {}
        FieldInterval( const BSONElement& e ) : _cachedEquality( -1 ) {
            _lower._bound = _upper._bound = e;
            _lower._inclusive = _upper._inclusive = true;
        }
        FieldBound _lower;
        FieldBound _upper;
        bool strictValid() const {
            int cmp = _lower._bound.woCompare( _upper._bound, false );
            return ( cmp < 0 || ( cmp == 0 && _lower._inclusive && _upper._inclusive ) );
        }
        bool equality() const {
            if ( _cachedEquality == -1 ) {
                _cachedEquality = ( _lower._inclusive && _upper._inclusive && _lower._bound.woCompare( _upper._bound, false ) == 0 );
            }
            return _cachedEquality;
        }
        mutable int _cachedEquality;
    };

    // range of a field's value that may be determined from query -- used to
    // determine index limits
    class FieldRange {
    public:
        FieldRange( const BSONElement &e = BSONObj().firstElement() , bool isNot=false , bool optimize=true );
        const FieldRange &operator&=( const FieldRange &other );
        const FieldRange &operator|=( const FieldRange &other );
        const FieldRange &operator-=( const FieldRange &other );
        // true iff other includes this
        bool operator<=( const FieldRange &other );
        BSONElement min() const { assert( !empty() ); return _intervals[ 0 ]._lower._bound; }
        BSONElement max() const { assert( !empty() ); return _intervals[ _intervals.size() - 1 ]._upper._bound; }
        bool minInclusive() const { assert( !empty() ); return _intervals[ 0 ]._lower._inclusive; }
        bool maxInclusive() const { assert( !empty() ); return _intervals[ _intervals.size() - 1 ]._upper._inclusive; }
        bool equality() const {
            return
                !empty() &&
                min().woCompare( max(), false ) == 0 &&
                maxInclusive() &&
                minInclusive();
        }
        bool inQuery() const {
            if ( equality() ) {
                return true;
            }
            for( vector< FieldInterval >::const_iterator i = _intervals.begin(); i != _intervals.end(); ++i ) {
                if ( !i->equality() ) {
                    return false;
                }
            }
            return true;
        }
        bool nontrivial() const {
            return
                ! empty() &&
                ( _intervals.size() != 1 ||
                  minKey.firstElement().woCompare( min(), false ) != 0 ||
                  maxKey.firstElement().woCompare( max(), false ) != 0 );
        }
        bool empty() const { return _intervals.empty(); }
        void makeEmpty() { _intervals.clear(); }
        const vector< FieldInterval > &intervals() const { return _intervals; }
        string getSpecial() const { return _special; }
        void setExclusiveBounds() {
            for( vector< FieldInterval >::iterator i = _intervals.begin(); i != _intervals.end(); ++i ) {
                i->_lower._inclusive = false;
                i->_upper._inclusive = false;
            }
        }
        // constructs a range which is the reverse of the current one
        // note - the resulting intervals may not be strictValid()
        void reverse( FieldRange &ret ) const {
            assert( _special.empty() );
            ret._intervals.clear();
            ret._objData = _objData;
            for( vector< FieldInterval >::const_reverse_iterator i = _intervals.rbegin(); i != _intervals.rend(); ++i ) {
                FieldInterval fi;
                fi._lower = i->_upper;
                fi._upper = i->_lower;
                ret._intervals.push_back( fi );
            }
        }
    private:
        BSONObj addObj( const BSONObj &o );
        void finishOperation( const vector< FieldInterval > &newIntervals, const FieldRange &other );
        vector< FieldInterval > _intervals;
        vector< BSONObj > _objData;
        string _special;
    };

    // implements query pattern matching, used to determine if a query is
    // similar to an earlier query and should use the same plan
    class QueryPattern {
    public:
        friend class FieldRangeSet;
        enum Type {
            Equality,
            LowerBound,
            UpperBound,
            UpperAndLowerBound
        };
        // for testing only, speed unimportant
        bool operator==( const QueryPattern &other ) const {
            bool less = operator<( other );
            bool more = other.operator<( *this );
            assert( !( less && more ) );
            return !( less || more );
        }
        bool operator!=( const QueryPattern &other ) const {
            return !operator==( other );
        }
        bool operator<( const QueryPattern &other ) const {
            map< string, Type >::const_iterator i = _fieldTypes.begin();
            map< string, Type >::const_iterator j = other._fieldTypes.begin();
            while( i != _fieldTypes.end() ) {
                if ( j == other._fieldTypes.end() )
                    return false;
                if ( i->first < j->first )
                    return true;
                else if ( i->first > j->first )
                    return false;
                if ( i->second < j->second )
                    return true;
                else if ( i->second > j->second )
                    return false;
                ++i;
                ++j;
            }
            if ( j != other._fieldTypes.end() )
                return true;
            return _sort.woCompare( other._sort ) < 0;
        }
    private:
        QueryPattern() {}
        void setSort( const BSONObj sort ) {
            _sort = normalizeSort( sort );
        }
        BSONObj static normalizeSort( const BSONObj &spec ) {
            if ( spec.isEmpty() )
                return spec;
            int direction = ( spec.firstElement().number() >= 0 ) ? 1 : -1;
            BSONObjIterator i( spec );
            BSONObjBuilder b;
            while( i.moreWithEOO() ) {
                BSONElement e = i.next();
                if ( e.eoo() )
                    break;
                b.append( e.fieldName(), direction * ( ( e.number() >= 0 ) ? -1 : 1 ) );
            }
            return b.obj();
        }
        map< string, Type > _fieldTypes;
        BSONObj _sort;
    };

    // a BoundList contains intervals specified by inclusive start
    // and end bounds.  The intervals should be nonoverlapping and occur in
    // the specified direction of traversal.  For example, given a simple index {i:1}
    // and direction +1, one valid BoundList is: (1, 2); (4, 6).  The same BoundList
    // would be valid for index {i:-1} with direction -1.
    typedef vector< pair< BSONObj, BSONObj > > BoundList;

    // ranges of fields' value that may be determined from query -- used to
    // determine index limits
    class FieldRangeSet {
    public:
        friend class FieldRangeOrSet;
        friend class FieldRangeVector;
        FieldRangeSet( const char *ns, const BSONObj &query , bool optimize=true );
        bool hasRange( const char *fieldName ) const {
            map< string, FieldRange >::const_iterator f = _ranges.find( fieldName );
            return f != _ranges.end();
        }
        const FieldRange &range( const char *fieldName ) const {
            map< string, FieldRange >::const_iterator f = _ranges.find( fieldName );
            if ( f == _ranges.end() )
                return trivialRange();
            return f->second;
        }
        FieldRange &range( const char *fieldName ) {
            map< string, FieldRange >::iterator f = _ranges.find( fieldName );
            if ( f == _ranges.end() )
                return trivialRange();
            return f->second;
        }
        int nNontrivialRanges() const {
            int count = 0;
            for( map< string, FieldRange >::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
                if ( i->second.nontrivial() )
                    ++count;
            }
            return count;
        }
        const char *ns() const { return _ns; }
        // if fields is specified, order fields of returned object to match those of 'fields'
        BSONObj simplifiedQuery( const BSONObj &fields = BSONObj() ) const;
        bool matchPossible() const {
            for( map< string, FieldRange >::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i )
                if ( i->second.empty() )
                    return false;
            return true;
        }
        QueryPattern pattern( const BSONObj &sort = BSONObj() ) const;
        string getSpecial() const;
        // Btree scanning for a multidimentional key range will yield a
        // multidimensional box.  The idea here is that if an 'other'
        // multidimensional box contains the current box we don't have to scan
        // the current box.  If the 'other' box contains the current box in
        // all dimensions but one, we can safely subtract the values of 'other'
        // along that one dimension from the values for the current box on the
        // same dimension.  In other situations, subtracting the 'other'
        // box from the current box yields a result that is not a box (but
        // rather can be expressed as a union of boxes).  We don't support
        // such splitting currently in calculating index ranges.  Note that
        // where I have said 'box' above, I actually mean sets of boxes because
        // a field range can consist of multiple intervals.
        const FieldRangeSet &operator-=( const FieldRangeSet &other ) {
            int nUnincluded = 0;
            string unincludedKey;
            map< string, FieldRange >::iterator i = _ranges.begin();
            map< string, FieldRange >::const_iterator j = other._ranges.begin();
            while( nUnincluded < 2 && i != _ranges.end() && j != other._ranges.end() ) {
                int cmp = i->first.compare( j->first );
                if ( cmp == 0 ) {
                    if ( i->second <= j->second ) {
                        // nothing
                    }
                    else {
                        ++nUnincluded;
                        unincludedKey = i->first;
                    }
                    ++i;
                    ++j;
                }
                else if ( cmp < 0 ) {
                    ++i;
                }
                else {
                    // other has a bound we don't, nothing can be done
                    return *this;
                }
            }
            if ( j != other._ranges.end() ) {
                // other has a bound we don't, nothing can be done
                return *this;
            }
            if ( nUnincluded > 1 ) {
                return *this;
            }
            if ( nUnincluded == 0 ) {
                makeEmpty();
                return *this;
            }
            // nUnincluded == 1
            _ranges[ unincludedKey ] -= other._ranges[ unincludedKey ];
            appendQueries( other );
            return *this;
        }
        const FieldRangeSet &operator&=( const FieldRangeSet &other ) {
            map< string, FieldRange >::iterator i = _ranges.begin();
            map< string, FieldRange >::const_iterator j = other._ranges.begin();
            while( i != _ranges.end() && j != other._ranges.end() ) {
                int cmp = i->first.compare( j->first );
                if ( cmp == 0 ) {
                    i->second &= j->second;
                    ++i;
                    ++j;
                }
                else if ( cmp < 0 ) {
                    ++i;
                }
                else {
                    _ranges[ j->first ] = j->second;
                    ++j;
                }
            }
            while( j != other._ranges.end() ) {
                _ranges[ j->first ] = j->second;
                ++j;
            }
            appendQueries( other );
            return *this;
        }
        // TODO get rid of this
        BoundList indexBounds( const BSONObj &keyPattern, int direction ) const;

        /**
         * @param return - A new FieldRangeSet based on this FieldRangeSet, but with only
         * a subset of the fields.
         * @param fields - Only fields which are represented as field names in this object
         * will be included in the returned FieldRangeSet.
         */
        FieldRangeSet *subset( const BSONObj &fields ) const;
    private:
        void appendQueries( const FieldRangeSet &other ) {
            for( vector< BSONObj >::const_iterator i = other._queries.begin(); i != other._queries.end(); ++i ) {
                _queries.push_back( *i );
            }
        }
        void makeEmpty() {
            for( map< string, FieldRange >::iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
                i->second.makeEmpty();
            }
        }
        void processQueryField( const BSONElement &e, bool optimize );
        void processOpElement( const char *fieldName, const BSONElement &f, bool isNot, bool optimize );
        static FieldRange *trivialRange_;
        static FieldRange &trivialRange();
        mutable map< string, FieldRange > _ranges;
        const char *_ns;
        // make sure memory for FieldRange BSONElements is owned
        vector< BSONObj > _queries;
    };

    class IndexSpec;

    /**
     * This class manages the ranges of valid element values for each field in
     * an ordered list of signed fields corresponding to an index specification.
     */
    class FieldRangeVector {
    public:
        /**
         * @param frs The valid ranges for all fields, as defined by the query spec
         * @prarm keyPattern The index key pattern
         * @param direction The direction of index traversal
         */
        FieldRangeVector( const FieldRangeSet &frs, const BSONObj &keyPattern, int direction )
            :_keyPattern( keyPattern ), _direction( direction >= 0 ? 1 : -1 ) {
            _queries = frs._queries;
            BSONObjIterator i( _keyPattern );
            while( i.more() ) {
                BSONElement e = i.next();
                int number = (int) e.number(); // returns 0.0 if not numeric
                bool forward = ( ( number >= 0 ? 1 : -1 ) * ( direction >= 0 ? 1 : -1 ) > 0 );
                if ( forward ) {
                    _ranges.push_back( frs.range( e.fieldName() ) );
                }
                else {
                    _ranges.push_back( FieldRange() );
                    frs.range( e.fieldName() ).reverse( _ranges.back() );
                }
                assert( !_ranges.back().empty() );
            }
            uassert( 13385, "combinatorial limit of $in partitioning of result set exceeded", size() < 1000000 );
        }
        long long size() {
            long long ret = 1;
            for( vector< FieldRange >::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
                ret *= i->intervals().size();
            }
            return ret;
        }
        BSONObj startKey() const {
            BSONObjBuilder b;
            for( vector< FieldRange >::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
                const FieldInterval &fi = i->intervals().front();
                b.appendAs( fi._lower._bound, "" );
            }
            return b.obj();
        }
        BSONObj endKey() const {
            BSONObjBuilder b;
            for( vector< FieldRange >::const_iterator i = _ranges.begin(); i != _ranges.end(); ++i ) {
                const FieldInterval &fi = i->intervals().back();
                b.appendAs( fi._upper._bound, "" );
            }
            return b.obj();
        }
        BSONObj obj() const {
            BSONObjBuilder b;
            BSONObjIterator k( _keyPattern );
            for( int i = 0; i < (int)_ranges.size(); ++i ) {
                BSONArrayBuilder a( b.subarrayStart( k.next().fieldName() ) );
                for( vector< FieldInterval >::const_iterator j = _ranges[ i ].intervals().begin();
                        j != _ranges[ i ].intervals().end(); ++j ) {
                    a << BSONArray( BSON_ARRAY( j->_lower._bound << j->_upper._bound ).clientReadable() );
                }
                a.done();
            }
            return b.obj();
        }
        /**
         * @return true iff the provided document matches valid ranges on all
         * of this FieldRangeVector's fields, which is the case iff this document
         * would be returned while scanning the index corresponding to this
         * FieldRangeVector.  This function is used for $or clause deduping.
         */
        bool matches( const BSONObj &obj ) const;
        class Iterator {
        public:
            Iterator( const FieldRangeVector &v ) : _v( v ), _i( _v._ranges.size(), -1 ), _cmp( _v._ranges.size(), 0 ), _inc( _v._ranges.size(), false ), _after() {
            }
            static BSONObj minObject() {
                BSONObjBuilder b;
                b.appendMinKey( "" );
                return b.obj();
            }
            static BSONObj maxObject() {
                BSONObjBuilder b;
                b.appendMaxKey( "" );
                return b.obj();
            }
            bool advance() {
                int i = _i.size() - 1;
                while( i >= 0 && _i[ i ] >= ( (int)_v._ranges[ i ].intervals().size() - 1 ) ) {
                    --i;
                }
                if( i >= 0 ) {
                    _i[ i ]++;
                    for( unsigned j = i + 1; j < _i.size(); ++j ) {
                        _i[ j ] = 0;
                    }
                }
                else {
                    _i[ 0 ] = _v._ranges[ 0 ].intervals().size();
                }
                return ok();
            }
            // return value
            // -2 end of iteration
            // -1 no skipping
            // >= 0 skip parameter
            int advance( const BSONObj &curr );
            const vector< const BSONElement * > &cmp() const { return _cmp; }
            const vector< bool > &inc() const { return _inc; }
            bool after() const { return _after; }
            void prepDive();
            void setZero( int i ) {
                for( int j = i; j < (int)_i.size(); ++j ) {
                    _i[ j ] = 0;
                }
            }
            void setMinus( int i ) {
                for( int j = i; j < (int)_i.size(); ++j ) {
                    _i[ j ] = -1;
                }
            }
            bool ok() {
                return _i[ 0 ] < (int)_v._ranges[ 0 ].intervals().size();
            }
            BSONObj startKey() {
                BSONObjBuilder b;
                for( int unsigned i = 0; i < _i.size(); ++i ) {
                    const FieldInterval &fi = _v._ranges[ i ].intervals()[ _i[ i ] ];
                    b.appendAs( fi._lower._bound, "" );
                }
                return b.obj();
            }
            // temp
            BSONObj endKey() {
                BSONObjBuilder b;
                for( int unsigned i = 0; i < _i.size(); ++i ) {
                    const FieldInterval &fi = _v._ranges[ i ].intervals()[ _i[ i ] ];
                    b.appendAs( fi._upper._bound, "" );
                }
                return b.obj();
            }
            // check
        private:
            const FieldRangeVector &_v;
            vector< int > _i;
            vector< const BSONElement* > _cmp;
            vector< bool > _inc;
            bool _after;
        };
    private:
        int matchingLowElement( const BSONElement &e, int i, bool direction, bool &lowEquality ) const;
        bool matchesElement( const BSONElement &e, int i, bool direction ) const;
        vector< FieldRange > _ranges;
        BSONObj _keyPattern;
        int _direction;
        vector< BSONObj > _queries; // make sure mem owned
        // This IndexSpec is lazily constructed directly from _keyPattern if needed.
        mutable shared_ptr< IndexSpec > _indexSpec;
    };

    // generages FieldRangeSet objects, accounting for or clauses
    class FieldRangeOrSet {
    public:
        FieldRangeOrSet( const char *ns, const BSONObj &query , bool optimize=true );
        // if there's a useless or clause, we won't use or ranges to help with scanning
        bool orFinished() const { return _orFound && _orSets.empty(); }
        /**
         * Removes the top or clause, which would have been recently scanned, and
         * removes the field ranges it covers from all subsequent or clauses.  As a
         * side effect, this function may invalidate the return values of topFrs()
         * calls made before this function was called.
         * @param indexSpec - Keys of the index that was used to satisfy the last or
         * clause.  Used to determine the range of keys that were scanned.  If
         * empty we do not constrain the previous clause's ranges using index keys,
         * which may reduce opportunities for range elimination.
         */
        void popOrClause( const BSONObj &indexSpec = BSONObj() );
        FieldRangeSet *topFrs() const {
            FieldRangeSet *ret = new FieldRangeSet( _baseSet );
            if (_orSets.size()) {
                *ret &= _orSets.front();
            }
            return ret;
        }
        // while the original bounds are looser, they are composed of fewer
        // ranges and it is faster to do operations with them; when they can be
        // used instead of more precise bounds, they should
        FieldRangeSet *topFrsOriginal() const {
            FieldRangeSet *ret = new FieldRangeSet( _baseSet );
            if (_originalOrSets.size()) {
                *ret &= _originalOrSets.front();
            }
            return ret;
        }
        void allClausesSimplified( vector< BSONObj > &ret ) const {
            for( list< FieldRangeSet >::const_iterator i = _orSets.begin(); i != _orSets.end(); ++i ) {
                if ( i->matchPossible() ) {
                    ret.push_back( i->simplifiedQuery() );
                }
            }
        }
        string getSpecial() const { return _baseSet.getSpecial(); }

        bool moreOrClauses() const { return !_orSets.empty(); }
    private:
        FieldRangeSet _baseSet;
        list< FieldRangeSet > _orSets;
        list< FieldRangeSet > _originalOrSets;
        list< FieldRangeSet > _oldOrSets; // make sure memory is owned
        bool _orFound;
    };

    /** returns a string that when used as a matcher, would match a super set of regex()
        returns "" for complex regular expressions
        used to optimize queries in some simple regex cases that start with '^'

        if purePrefix != NULL, sets it to whether the regex can be converted to a range query
    */
    string simpleRegex(const char* regex, const char* flags, bool* purePrefix=NULL);

    /** returns the upper bound of a query that matches prefix */
    string simpleRegexEnd( string prefix );

    long long applySkipLimit( long long num , const BSONObj& cmd );

} // namespace mongo