Method constructTreeNode

src/planner/join_order/join_tree_constructor.cpp:60–132

}

JoinTreeConstructor::IntermediateResult JoinTreeConstructor::constructTreeNode(
    std::shared_ptr<BoundJoinHintNode> hintNode) {
    // Construct leaf scans.
    if (hintNode->isLeaf()) {
        if (ExpressionUtil::isNodePattern(*hintNode->nodeOrRel)) {
            return constructNodeScan(hintNode->nodeOrRel);
        } else {
            DASSERT(ExpressionUtil::isRelPattern(*hintNode->nodeOrRel) ||
                    ExpressionUtil::isRecursiveRelPattern(*hintNode->nodeOrRel));
            return constructRelScan(hintNode->nodeOrRel);
        }
    }
    // Construct binary join.
    if (hintNode->isBinary()) {
        auto left = constructTreeNode(hintNode->children[0]);
        auto right = constructTreeNode(hintNode->children[1]);
        auto joinNodes = getJoinNodes(left.subqueryGraph, right.subqueryGraph);
        if (joinNodes.empty()) {
            joinNodes = getJoinNodes(right.subqueryGraph, left.subqueryGraph);
        }
        if (joinNodes.empty()) {
            throw BinderException(std::format("Cannot resolve join condition between {} and {}.",
                left.treeNode->toString(), right.treeNode->toString()));
        }
        auto newSubgraph = left.subqueryGraph;
        newSubgraph.addSubqueryGraph(right.subqueryGraph);
        auto predicates = Planner::getNewlyMatchedExprs(left.subqueryGraph, right.subqueryGraph,
            newSubgraph, queryGraphPredicates);
        // First try to construct as index nested loop join.
        auto nestedLoopTreeNode =
            tryConstructNestedLoopJoin(joinNodes, *left.treeNode, *right.treeNode, predicates);
        if (nestedLoopTreeNode != nullptr) {
            return {nestedLoopTreeNode, newSubgraph};
        }
        // Cannot construct index nested loop join. Fall back to hash join.
        auto extraInfo = std::make_unique<ExtraJoinTreeNodeInfo>(joinNodes);
        extraInfo->predicates = predicates;
        auto treeNode =
            std::make_shared<JoinTreeNode>(TreeNodeType::BINARY_JOIN, std::move(extraInfo));
        treeNode->addChild(left.treeNode);
        treeNode->addChild(right.treeNode);
        return {treeNode, newSubgraph};
    }
    // Construct multi-way join
    DASSERT(hintNode->isMultiWay());
    auto probe = constructTreeNode(hintNode->children[0]);
    auto newSubgraph = probe.subqueryGraph;
    std::vector<std::shared_ptr<JoinTreeNode>> childrenNodes;
    childrenNodes.push_back(probe.treeNode);
    std::vector<SubqueryGraph> buildSubgraphs;
    for (auto i = 1u; i < hintNode->children.size(); ++i) {
        auto build = constructTreeNode(hintNode->children[i]);
        if (build.treeNode->type != TreeNodeType::REL_SCAN) {
            throw BinderException(std::format(
                "Cannot construct multi-way join because build side is not a relationship table."));
        }
        newSubgraph.addSubqueryGraph(build.subqueryGraph);
        childrenNodes.push_back(build.treeNode);