Imported Upstream version 2.6.11upstream/2.6.11

1 files changed, 513 insertions, 0 deletions

diff --git a/src/mongo/db/query/plan_cache.cpp b/src/mongo/db/query/plan_cache.cpp
new file mode 100644
index 00000000000..3c7144b0b14
--- /dev/null
+++ b/src/mongo/db/query/plan_cache.cpp
@@ -0,0 +1,513 @@
+/**
+ *    Copyright (C) 2013 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#include "mongo/db/query/plan_cache.h"
+
+#include <algorithm>
+#include <math.h>
+#include <memory>
+#include "boost/thread/locks.hpp"
+#include "mongo/base/owned_pointer_vector.h"
+#include "mongo/client/dbclientinterface.h"   // For QueryOption_foobar
+#include "mongo/db/query/plan_ranker.h"
+#include "mongo/db/query/query_solution.h"
+#include "mongo/db/query/qlog.h"
+#include "mongo/db/query/query_knobs.h"
+#include "mongo/util/mongoutils/str.h"
+
+namespace mongo {
+
+    //
+    // Cache-related functions for CanonicalQuery
+    //
+
+    bool PlanCache::shouldCacheQuery(const CanonicalQuery& query) {
+        const LiteParsedQuery& lpq = query.getParsed();
+        const MatchExpression* expr = query.root();
+
+        // Collection scan
+        // No sort order requested
+        if (lpq.getSort().isEmpty() &&
+            expr->matchType() == MatchExpression::AND && expr->numChildren() == 0) {
+            return false;
+        }
+
+        // Hint provided
+        if (!lpq.getHint().isEmpty()) {
+            return false;
+        }
+
+        // Min provided
+        // Min queries are a special case of hinted queries.
+        if (!lpq.getMin().isEmpty()) {
+            return false;
+        }
+
+        // Max provided
+        // Similar to min, max queries are a special case of hinted queries.
+        if (!lpq.getMax().isEmpty()) {
+            return false;
+        }
+
+        // Explain queries are not-cacheable. This is primarily because of
+        // the need to generate current and accurate information in allPlans.
+        // If the explain report is generated by the cached plan runner using
+        // stale information from the cache for the losing plans, allPlans would
+        // simply be wrong.
+        if (lpq.isExplain()) {
+            return false;
+        }
+
+        // Tailable cursors won't get cached, just turn into collscans.
+        if (query.getParsed().hasOption(QueryOption_CursorTailable)) {
+            return false;
+        }
+
+        // Snapshot is really a hint.
+        if (query.getParsed().isSnapshot()) {
+            return false;
+        }
+
+        return true;
+    }
+
+    //
+    // CachedSolution
+    //
+
+    CachedSolution::CachedSolution(const PlanCacheKey& key, const PlanCacheEntry& entry)
+        : plannerData(entry.plannerData.size()),
+          backupSoln(entry.backupSoln),
+          key(key),
+          query(entry.query.getOwned()),
+          sort(entry.sort.getOwned()),
+          projection(entry.projection.getOwned()) {
+        // CachedSolution should not having any references into
+        // cache entry. All relevant data should be cloned/copied.
+        for (size_t i = 0; i < entry.plannerData.size(); ++i) {
+            verify(entry.plannerData[i]);
+            plannerData[i] = entry.plannerData[i]->clone();
+        }
+    }
+
+    CachedSolution::~CachedSolution() {
+        for (std::vector<SolutionCacheData*>::const_iterator i = plannerData.begin();
+             i != plannerData.end(); ++i) {
+            SolutionCacheData* scd = *i;
+            delete scd;
+        }
+    }
+
+    //
+    // PlanCacheEntry
+    //
+
+    PlanCacheEntry::PlanCacheEntry(const std::vector<QuerySolution*>& solutions,
+                                   PlanRankingDecision* why)
+        : plannerData(solutions.size()),
+          decision(why) {
+        invariant(why);
+
+        // The caller of this constructor is responsible for ensuring
+        // that the QuerySolution 's' has valid cacheData. If there's no
+        // data to cache you shouldn't be trying to construct a PlanCacheEntry.
+
+        // Copy the solution's cache data into the plan cache entry.
+        for (size_t i = 0; i < solutions.size(); ++i) {
+            invariant(solutions[i]->cacheData.get());
+            plannerData[i] = solutions[i]->cacheData->clone();
+        }
+    }
+
+    PlanCacheEntry::~PlanCacheEntry() {
+        for (size_t i = 0; i < feedback.size(); ++i) {
+            delete feedback[i];
+        }
+        for (size_t i = 0; i < plannerData.size(); ++i) {
+            delete plannerData[i];
+        }
+    }
+
+    PlanCacheEntry* PlanCacheEntry::clone() const {
+        OwnedPointerVector<QuerySolution> solutions;
+        for (size_t i = 0; i < plannerData.size(); ++i) {
+            QuerySolution* qs = new QuerySolution();
+            qs->cacheData.reset(plannerData[i]->clone());
+            solutions.mutableVector().push_back(qs);
+        }
+        PlanCacheEntry* entry = new PlanCacheEntry(solutions.vector(), decision->clone());
+
+        entry->backupSoln = backupSoln;
+
+        // Copy query shape.
+        entry->query = query.getOwned();
+        entry->sort = sort.getOwned();
+        entry->projection = projection.getOwned();
+
+        // Copy performance stats.
+        for (size_t i = 0; i < feedback.size(); ++i) {
+            PlanCacheEntryFeedback* fb = new PlanCacheEntryFeedback();
+            fb->stats.reset(feedback[i]->stats->clone());
+            fb->score = feedback[i]->score;
+            entry->feedback.push_back(fb);
+        }
+        entry->averageScore = averageScore;
+        entry->stddevScore = stddevScore;
+        return entry;
+    }
+
+    string PlanCacheEntry::toString() const {
+        mongoutils::str::stream ss;
+        ss << "(query: " << query.toString()
+           << ";sort: " << sort.toString()
+           << ";projection: " << projection.toString()
+           << ";solutions: " << plannerData.size()
+           << ")";
+        return ss;
+    }
+
+    string CachedSolution::toString() const {
+        mongoutils::str::stream ss;
+        ss << "key: " << key << '\n';
+        return ss;
+    }
+
+
+    // static
+    const double PlanCacheEntry::kMinDeviation = 0.0001;
+
+    //
+    // PlanCacheIndexTree
+    //
+
+    void PlanCacheIndexTree::setIndexEntry(const IndexEntry& ie) {
+        entry.reset(new IndexEntry(ie));
+    }
+
+    PlanCacheIndexTree* PlanCacheIndexTree::clone() const {
+        PlanCacheIndexTree* root = new PlanCacheIndexTree();
+        if (NULL != entry.get()) {
+            root->index_pos = index_pos;
+            root->setIndexEntry(*entry.get());
+        }
+
+        for (vector<PlanCacheIndexTree*>::const_iterator it = children.begin();
+                it != children.end(); ++it) {
+            PlanCacheIndexTree* clonedChild = (*it)->clone();
+            root->children.push_back(clonedChild);
+        }
+        return root;
+    }
+
+    std::string PlanCacheIndexTree::toString(int indents) const {
+        mongoutils::str::stream ss;
+        if (!children.empty()) {
+            ss << string(3 * indents, '-') << "Node\n";
+            int newIndent = indents + 1;
+            for (vector<PlanCacheIndexTree*>::const_iterator it = children.begin();
+                    it != children.end(); ++it) {
+                ss << (*it)->toString(newIndent);
+            }
+            return ss;
+        }
+        else {
+            ss << string(3 * indents, '-') << "Leaf ";
+            if (NULL != entry.get()) {
+                ss << entry->keyPattern.toString() << ", pos: " << index_pos;
+            }
+            ss << '\n';
+        }
+        return ss;
+    }
+
+    //
+    // SolutionCacheData
+    //
+
+    SolutionCacheData* SolutionCacheData::clone() const {
+        SolutionCacheData* other = new SolutionCacheData();
+        if (NULL != this->tree.get()) {
+            // 'tree' could be NULL if the cached solution
+            // is a collection scan.
+            other->tree.reset(this->tree->clone());
+        }
+        other->solnType = this->solnType;
+        other->wholeIXSolnDir = this->wholeIXSolnDir;
+        other->indexFilterApplied = this->indexFilterApplied;
+        return other;
+    }
+
+    std::string SolutionCacheData::toString() const {
+        mongoutils::str::stream ss;
+        switch (this->solnType) {
+        case WHOLE_IXSCAN_SOLN:
+            verify(this->tree.get());
+            ss << "(whole index scan solution: "
+               << "dir=" << this->wholeIXSolnDir << "; "
+               << "tree=" << this->tree->toString()
+               << ")";
+            break;
+        case COLLSCAN_SOLN:
+            ss << "(collection scan)";
+            break;
+        case USE_INDEX_TAGS_SOLN:
+            verify(this->tree.get());
+            ss << "(index-tagged expression tree: "
+               << "tree=" << this->tree->toString()
+               << ")";
+        }
+        return ss;
+    }
+
+    //
+    // PlanCache
+    //
+
+    PlanCache::PlanCache() : _cache(internalQueryCacheSize) { }
+
+    PlanCache::PlanCache(const std::string& ns) : _cache(internalQueryCacheSize), _ns(ns) { }
+
+    PlanCache::~PlanCache() { }
+
+    Status PlanCache::add(const CanonicalQuery& query,
+                          const std::vector<QuerySolution*>& solns,
+                          PlanRankingDecision* why) {
+        invariant(why);
+
+        if (solns.empty()) {
+            return Status(ErrorCodes::BadValue, "no solutions provided");
+        }
+
+        if (why->stats.size() != solns.size()) {
+            return Status(ErrorCodes::BadValue,
+                          "number of stats in decision must match solutions");
+        }
+
+        if (why->scores.size() != solns.size()) {
+            return Status(ErrorCodes::BadValue,
+                          "number of scores in decision must match solutions");
+        }
+
+        if (why->candidateOrder.size() != solns.size()) {
+            return Status(ErrorCodes::BadValue,
+                          "candidate ordering entries in decision must match solutions");
+        }
+
+        PlanCacheEntry* entry = new PlanCacheEntry(solns, why);
+        const LiteParsedQuery& pq = query.getParsed();
+        entry->query = pq.getFilter().getOwned();
+        entry->sort = pq.getSort().getOwned();
+        entry->projection = pq.getProj().getOwned();
+
+        // If the winning solution uses a blocking stage, then try and
+        // find a fallback solution that has no blocking stage.
+        if (solns[0]->hasBlockingStage) {
+            for (size_t i = 1; i < solns.size(); ++i) {
+                if (!solns[i]->hasBlockingStage) {
+                    entry->backupSoln.reset(i);
+                    break;
+                }
+            }
+        }
+
+        boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
+        std::auto_ptr<PlanCacheEntry> evictedEntry = _cache.add(query.getPlanCacheKey(), entry);
+
+        if (NULL != evictedEntry.get()) {
+            LOG(1) << _ns << ": plan cache maximum size exceeded - "
+                   << "removed least recently used entry "
+                   << evictedEntry->toString();
+        }
+
+        return Status::OK();
+    }
+
+    Status PlanCache::get(const CanonicalQuery& query, CachedSolution** crOut) const {
+        const PlanCacheKey& key = query.getPlanCacheKey();
+        verify(crOut);
+
+        boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
+        PlanCacheEntry* entry;
+        Status cacheStatus = _cache.get(key, &entry);
+        if (!cacheStatus.isOK()) {
+            return cacheStatus;
+        }
+        invariant(entry);
+
+        *crOut = new CachedSolution(key, *entry);
+
+        return Status::OK();
+    }
+
+    // TODO: Figure out what the right policy is here for determining if the cached solution is bad.
+    // This is a solution but may not be the right one, if there even is a right one...
+    static bool hasCachedPlanPerformanceDegraded(PlanCacheEntry* entry,
+                                                 PlanCacheEntryFeedback* latestFeedback) {
+
+        if (!entry->averageScore) {
+            // We haven't computed baseline performance stats for this cached plan yet.
+            // Let's do that now.
+
+            // Compute mean score.
+            double sum = 0;
+            for (size_t i = 0; i < entry->feedback.size(); ++i) {
+                sum += entry->feedback[i]->score;
+            }
+            double mean = sum / entry->feedback.size();
+
+            // Compute std deviation of scores.
+            double sum_of_squares = 0;
+            for (size_t i = 0; i < entry->feedback.size(); ++i) {
+                double iscore = entry->feedback[i]->score;
+                sum_of_squares += (iscore - mean) * (iscore - mean);
+            }
+            double stddev = sqrt(sum_of_squares / (entry->feedback.size() - 1));
+
+            entry->averageScore.reset(mean);
+            entry->stddevScore.reset(stddev);
+        }
+
+        // If the latest use of this plan cache entry is too far from the expected
+        // performance, then we should uncache the entry. Only uncache if the deviation
+        // also exceeds a minimum value.
+        double deviation = *entry->averageScore - latestFeedback->score;
+
+        if (deviation < PlanCacheEntry::kMinDeviation) {
+            // The plan performed better then the average or is only worse by
+            // epsilon. Keep the cache entry, regardless of the std dev.
+            return false;
+        }
+
+        if (deviation > (internalQueryCacheStdDeviations * (*entry->stddevScore))) {
+            // This run of the plan was much worse than average.
+            // Kick it out of the plan cache.
+            return true;
+        }
+
+        // If we're here, the performance deviated from the average, but
+        // not by enough to warrant uncaching.
+
+        return false;
+    }
+
+    Status PlanCache::feedback(const CanonicalQuery& cq, PlanCacheEntryFeedback* feedback) {
+        if (NULL == feedback) {
+            return Status(ErrorCodes::BadValue, "feedback is NULL");
+        }
+        std::auto_ptr<PlanCacheEntryFeedback> autoFeedback(feedback);
+        const PlanCacheKey& ck = cq.getPlanCacheKey();
+
+        boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
+        PlanCacheEntry* entry;
+        Status cacheStatus = _cache.get(ck, &entry);
+        if (!cacheStatus.isOK()) {
+            return cacheStatus;
+        }
+        invariant(entry);
+
+        if (entry->feedback.size() >= size_t(internalQueryCacheFeedbacksStored)) {
+            // If we have enough feedback, then use it to determine whether
+            // we should get rid of the cached solution.
+            if (hasCachedPlanPerformanceDegraded(entry, autoFeedback.get())) {
+                LOG(1) << _ns << ": removing plan cache entry " << entry->toString()
+                       << " - detected degradation in performance of cached solution.";
+                _cache.remove(ck);
+            }
+        }
+        else {
+            // We don't have enough feedback yet---just store it and move on.
+            entry->feedback.push_back(autoFeedback.release());
+        }
+
+        return Status::OK();
+    }
+
+    Status PlanCache::remove(const CanonicalQuery& canonicalQuery) {
+        boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
+        return _cache.remove(canonicalQuery.getPlanCacheKey());
+    }
+
+    void PlanCache::clear() {
+        boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
+        _cache.clear();
+        _writeOperations.store(0);
+    }
+
+    Status PlanCache::getEntry(const CanonicalQuery& query, PlanCacheEntry** entryOut) const {
+        const PlanCacheKey& key = query.getPlanCacheKey();
+        verify(entryOut);
+
+        boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
+        PlanCacheEntry* entry;
+        Status cacheStatus = _cache.get(key, &entry);
+        if (!cacheStatus.isOK()) {
+            return cacheStatus;
+        }
+        invariant(entry);
+
+        *entryOut = entry->clone();
+
+        return Status::OK();
+    }
+
+    std::vector<PlanCacheEntry*> PlanCache::getAllEntries() const {
+        boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
+        std::vector<PlanCacheEntry*> entries;
+        typedef std::list< std::pair<PlanCacheKey, PlanCacheEntry*> >::const_iterator ConstIterator;
+        for (ConstIterator i = _cache.begin(); i != _cache.end(); i++) {
+            PlanCacheEntry* entry = i->second;
+            entries.push_back(entry->clone());
+        }
+
+        return entries;
+    }
+
+    bool PlanCache::contains(const CanonicalQuery& cq) const {
+        boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
+        return _cache.hasKey(cq.getPlanCacheKey());
+    }
+
+    size_t PlanCache::size() const {
+        boost::lock_guard<boost::mutex> cacheLock(_cacheMutex);
+        return _cache.size();
+    }
+
+    void PlanCache::notifyOfWriteOp() {
+        // It's fine to clear the cache multiple times if multiple threads
+        // increment the counter to kPlanCacheMaxWriteOperations or greater.
+        if (_writeOperations.addAndFetch(1) < internalQueryCacheWriteOpsBetweenFlush) {
+            return;
+        }
+
+        LOG(1) << _ns << ": clearing collection plan cache - "
+               << internalQueryCacheWriteOpsBetweenFlush
+               << " write operations detected since last refresh.";
+        clear();
+    }
+
+}  // namespace mongo