[MongoDB] Optimizer Process

MongoDB Optimizer 프로세스는 타 DBMS의 Optimizer와 다소 상이하고, 관련 포스트가 거의 없어서 프로세스를 파악하기 어렵다.

인터넷에 정리된 문서들과 MongoDB 소스코드를 참고하여 MongoDB의 옵티마이저 프로세스를 이해해보자.

 

Overview

MongoDB Optimizer Process

MongoDB는 RDBMS와 비교했을 때 데이터베이스에 대한 통계정보가 거의 없는 수준이다. 따라서 RDB처럼 통계정보를 이용하여 쿼리 최적화를 수행할 수가 없고, 쿼리 형태와 사용 인덱스만 비교하며 플랜을 생성하는 다소 무식한 방법을 사용한다.

이로 인한 부정확성을 보완하기 위해 MongoDB는 특수한 Evaluating 과정을 수행하여 각 후보 플랜에 점수를 부여한다.

가장 점수가 높은 플랜은 Winning Plan으로 선정되어 Plan Cache에 저장되고, 쿼리에 사용된다.

이후에 동일한 쿼리 형태가 들어오면 Plan Cache에 있는 플랜을 사용하여 쿼리 최적화 시간을 최소화하도록 동작한다.

 

Process

일단 쿼리가 들어오면, MongoDB Optimizer는 Plan Cache에 매칭되는 플랜이 있는지 검색을 수행한다. 들어온 쿼리와 동일한 쿼리 형태에 대한 플랜을 매칭 플랜으로 인식한다.

 

A. Plan Cache에 매칭 플랜이 있는 경우

1. Evaluate Plan Performance : 캐싱된 플랜의 효율성 검증
2. 캐싱 플랜이 효율적인 경우 : 캐싱 플랜으로 현재 쿼리를 수행한다.
3. 캐싱 플랜이 비효율적인 경우 : 캐싱 플랜을 Evict 하고, 아래의 프로세스 B를 

B. Plan Cache에 매칭 플랜이 없는 경우

1. Plan : 요청된 쿼리 형태에 대해 사용할 수 있는 쿼리 플랜 생성 → Candiate Plans
2. Work Candidate Plans : 모든 Candidate Plan에 대해 쿼리 일부 실행
3. Pick Best Plan : 각 Candidate Plan의 점수를 책정한 후 가장 높은 점수의 플랜을 Winning Plan으로 선정
4. Plan Cache에 선정된 플랜 저장
5. 선정된 플랜으로 쿼리 수행

Plan

타 DBMS와 달리, MongoDB는 쿼리 플랜을 생성할 때 데이터베이스의 통계 정보를 전혀 사용하지 않는다. 오직 요청된 쿼리의 형태와 인덱스 목록만 보고 플랜을 생성한다.

MongoDB는 컬렉션의 인덱스 목록 중, 요청된 쿼리와 '연관된' 인덱스를 추출하여 Indexed Plan을 생성한다. 쿼리와 인덱스의 '연관성'을 판단하는 기준은 아래와 같다.

 

• 쿼리와 인덱스에 일치하는 필드가 있는가?
• 인덱스 프리픽스가 쿼리 필드에 포함되는가?
• hint가 사용되었는가?
• GEO_NEAR, TEXT 인덱스인가?
• min( ), max( )가 사용되었는가?

적절한 Indexed Plan이 없는 경우에는 COLLSCAN Plan을 생성하게 된다. 다시 말해서, Indexed Plan이 하나라도 있는 경우에는 COLLSCAN이 더 효율적인 경우에도 COLLSCAN Plan은 생성되지 않는다는 의미이다.

 

StatusWith<std::vector<std::unique_ptr<QuerySolution>>> QueryPlanner::plan(
    const CanonicalQuery& query, const QueryPlannerParams& params) {
    //중략
    }
 
    const bool canTableScan = !(params.options & QueryPlannerParams::NO_TABLE_SCAN);
     
    //중략   
 
    std::vector<IndexEntry> fullIndexList;
 
    // Figure out what fields we care about.
    stdx::unordered_set<string> fields;
    QueryPlannerIXSelect::getFields(query.root(), &fields);
    for (auto&& field : fields) {
        LOG(5) << "Predicate over field '" << field << "'";
    }
 
    fullIndexList = QueryPlannerIXSelect::expandIndexes(fields, std::move(fullIndexList));
    std::vector<IndexEntry> relevantIndices;
 
    //중략
 
    // Figure out how useful each index is to each predicate.
    QueryPlannerIXSelect::rateIndices(query.root(), "", relevantIndices, query.getCollator());
    QueryPlannerIXSelect::stripInvalidAssignments(query.root(), relevantIndices);
 
    //중략
 
    // If we have any relevant indices, we try to create indexed plans.
    if (0 < relevantIndices.size()) {
            //중략
            std::unique_ptr<QuerySolutionNode> solnRoot(QueryPlannerAccess::buildIndexedDataAccess(
                query, std::move(nextTaggedTree), relevantIndices, params));
 
            if (!solnRoot) {
                continue;
            }
 
            auto soln = QueryPlannerAnalysis::analyzeDataAccess(query, params, std::move(solnRoot));
            //중략
    }
 
    // Don't leave tags on query tree.
    query.root()->resetTag();
 
    LOG(5) << "Planner: outputted " << out.size() << " indexed solutions.";
 
    //중략
 
    // If a sort order is requested, there may be an index that provides it, even if that
    // index is not over any predicates in the query.
    //
    if (!query.getQueryRequest().getSort().isEmpty() &&
        //중략
    }
 
    // If a projection exists, there may be an index that allows for a covered plan, even if none
    // were considered earlier.
    const auto projection = query.getProj();
    if (params.options & QueryPlannerParams::GENERATE_COVERED_IXSCANS && out.size() == 0 &&
        query.getQueryObj().isEmpty() && projection && !projection->requiresDocument()) {
        //중략
        }
    }
 
    //중략
 
    // No indexed plans?  We must provide a collscan if possible or else we can't run the query.
    bool collscanNeeded = (0 == out.size() && canTableScan);
 
    if (possibleToCollscan && (collscanRequested || collscanNeeded)) {
        auto collscan = buildCollscanSoln(query, isTailable, params);
        if (collscan) {
            LOG(5) << "Planner: outputting a collscan:" << endl << redact(collscan->toString());
            SolutionCacheData* scd = new SolutionCacheData();
            scd->solnType = SolutionCacheData::COLLSCAN_SOLN;
            collscan->cacheData.reset(scd);
            out.push_back(std::move(collscan));
        }
    }
 
    return {std::move(out)};
}

 

Work Candidate Plans

MongoDB는 옵티마이징에 다양한 데이터베이스 정보를 이용하지 못한다는 약점을 보완하기 위해, 모든 후보 플랜(Candidate Plan)을 동시에 조금씩 수행해보는 과정을 거친다. 반복문을 사용해 모든 후보 플랜에 Work를 1회씩 호출하는데, 이 과정을 Working이라고 지칭하자.

Working 아래 조건 중 하나를 만족할 때까지 반복적으로 수행된다.

 

• 후보 플랜 중 하나라도 먼저 numResults* 만큼의 도큐먼트 반환
• 후보 플랜 중 하나라도 먼저 쿼리 수행 완료
• numWorks*회 만큼 Working 수행
• Working 중 에러가 발생한 경우'

* numWorks : (컬렉션의 데이터 개수 * 0.29) 와 10,000 중 큰 값
* numResults : limit() 파라미터와 101 중 작은 값

Status MultiPlanStage::pickBestPlan(PlanYieldPolicy* yieldPolicy) {
    ScopedTimer timer(getClock(), &_commonStats.executionTimeMillis);
 
    size_t numWorks = getTrialPeriodWorks(getOpCtx(), collection());
    size_t numResults = getTrialPeriodNumToReturn(*_query);
 
    for (size_t ix = 0; ix < numWorks; ++ix) {
        bool moreToDo = workAllPlans(numResults, yieldPolicy);
        if (!moreToDo) {
            break;
        }
    }
 
    //후략
 
    }

bool MultiPlanStage::workAllPlans(size_t numResults, PlanYieldPolicy* yieldPolicy) {
    bool doneWorking = false;
 
    for (size_t ix = 0; ix < _candidates.size(); ++ix) {
        CandidatePlan& candidate = _candidates[ix];
        if (candidate.failed) {
            continue;
        }
 
        if (!(tryYield(yieldPolicy)).isOK()) {
            return false;
        }
 
        WorkingSetID id = WorkingSet::INVALID_ID;
        PlanStage::StageState state = candidate.root->work(&id);
 
        if (PlanStage::ADVANCED == state) {
            WorkingSetMember* member = candidate.ws->get(id);
            member->makeObjOwnedIfNeeded();
            candidate.results.push(id);
 
            if (candidate.results.size() >= numResults) {
                doneWorking = true;
            }
        } else if (PlanStage::IS_EOF == state) {
            doneWorking = true;
        } else if (PlanStage::NEED_YIELD == state) {
            //중략
        } else if (PlanStage::NEED_TIME != state) {
            //중략
        }
    }
 
    return !doneWorking;
}

 

Pick Best Plan

MongoDB Query Score

Working이 완료된 플랜들은 아래 지표의 합으로 점수가 책정된다.

 

• baseScore = 1
• productivity = advanced / workUnits (실제 반환 도큐먼트 수 / work 횟수)
• tieBreakers : 비효율적인 특정 작업들을 수행하지 않는 플랜에게 부여하는 보너스 점수
• EOF Bonus : Plan Working 중 먼저 쿼리 수행을 완료한 플랜에게 부여하는 보너스 점수 (+1)

tieBreakers는 쿼리 플랜이 다음의 경우를 만족할 경우 각각 epsilon* 만큼 부여하는 보너스 점수를 의미한다.

 

• Fetch 스테이지가 없을 경우
• Sort 스테이지가 없을 경우
• Index Intersection을 사용하지 않을 경우

* epsilon : ( 1 / ( 10 *workUnits ) ) 와 10-4 중 작은 값

double PlanRanker::scoreTree(const PlanStageStats* stats) {
    double baseScore = 1;
 
    size_t workUnits = stats->common.works;
    invariant(workUnits != 0);
 
    double productivity =
        static_cast<double>(stats->common.advanced) / static_cast<double>(workUnits);
 
    const double epsilon = std::min(1.0 / static_cast<double>(10 * workUnits), 1e-4);
 
    double noFetchBonus = epsilon;
    if (hasStage(STAGE_FETCH, stats)) {
        noFetchBonus = 0;
    }
 
    double noSortBonus = epsilon;
    if (hasStage(STAGE_SORT, stats)) {
        noSortBonus = 0;
    }
 
    double noIxisectBonus = epsilon;
    if (hasStage(STAGE_AND_HASH, stats) || hasStage(STAGE_AND_SORTED, stats)) {
        noIxisectBonus = 0;
    }
 
    double tieBreakers = noFetchBonus + noSortBonus + noIxisectBonus;
    double score = baseScore + productivity + tieBreakers;
     
    //중략
 
    return score;
}

Evict Plan Cache Entry

한번 생성된 쿼리 플랜은 플랜 캐시에 저장되어 있다가, 아래의 경우에 Evict된다.

 

• 인덱스 ReBuild
• 인덱스 추가 및 삭제
• mongod 프로세스 재시작
• 쿼리 플랜이 비효율적이라고 판단될 경우

Optimizer가 쿼리 플랜의 효율성을 검증하는 방법은 아래와 같다.

 

• 캐싱 플랜을 maxWorksBeforeReplan* 회 만큼 working
• Working이 끝나기 전에 아래 조건 중 하나를 만족하면 캐싱 플랜이 evict되지 않고 계속 사용됨
  • 캐싱 플랜이 numResults* 만큼의 도큐먼트 반환
  • 캐싱 플랜이 쿼리 수행 완료
• 그 외의 경우 기존의 캐싱 플랜이 evict되고 Replanning을 수행한다.

* maxWorksBeforeReplan : 10 * _decisionWorks
* numResults : limit() 파라미터와 101 중 작은 값
* decisionWorks : the number of work cycle taken to decide on a winning plan when the plan was first cached

Status CachedPlanStage::pickBestPlan(PlanYieldPolicy* yieldPolicy) {
    size_t numResults = MultiPlanStage::getTrialPeriodNumToReturn(*_canonicalQuery);
 
    for (size_t i = 0; i < maxWorksBeforeReplan; ++i) {
        Status yieldStatus = tryYield(yieldPolicy);
        if (!yieldStatus.isOK()) {
            return yieldStatus;
        }
 
        WorkingSetID id = WorkingSet::INVALID_ID;
        PlanStage::StageState state = child()->work(&id);
 
        if (PlanStage::ADVANCED == state) {
            WorkingSetMember* member = _ws->get(id);
            member->makeObjOwnedIfNeeded();
            _results.push(id);
 
            if (_results.size() >= numResults) {
                updatePlanCache();
                return Status::OK();
            }
        } else if (PlanStage::IS_EOF == state) {
            updatePlanCache();
            return Status::OK();
        } else if (PlanStage::NEED_YIELD == state) {
            //중략
            }
        } else if (PlanStage::FAILURE == state) {
            //중략
        } else {
            invariant(PlanStage::NEED_TIME == state);
        }
    }
 
    //중략
 
    return replan(
        //중략
        );
}

 

참고자료

percona server mongodb 4.2.10-11 Source Code : github.com/percona/percona-server-mongodb/tree/psmdb-4.2.10-11

 

https://www.slideshare.net/MyDBOPS/introduction-to-mongodb-execution-plan-and-optimizer?qid=116fadbd-5fa3-4cc3-9f9a-caa1dec0ebf9&v=&b=&from_search=1

 

https://mongoing.com/archives/5624