# Welcome to the DoltSQL shell.
# Statements must be terminated with ';'.
# "exit" or "quit" (or Ctrl-D) to exit.
join_planning> create table states (name varchar(100) primary key not null, population int unsigned);
join_planning> create table cities (name varchar(100) primary key not null, state varchar(100) not null, population int unsigned);
join_planning> create table people (name varchar(100) primary key not null, city varchar(100) not null);Copy

select * from people p
    join cities c on p.city = c.name
    join states s on s.name = c.state
    where p.name = "John Smith";Copy

join_planning> explain select * from people p
    join cities c on p.city = c.name
    join states s on s.name = c.state
    where p.name = "John Smith";
+-------------------------------------------------------------+
| plan                                                        |
+-------------------------------------------------------------+
| IndexedJoin(p.city = c.name)                                |
|  ├─ Filter(p.name = "John Smith")                           |
|  │   └─ Projected table access on [name city]               |
|  │       └─ TableAlias(p)                                   |
|  │           └─ Indexed table access on index [people.name] |
|  │               └─ Exchange(parallelism=16)                |
|  │                   └─ Table(people)                       |
|  └─ IndexedJoin(s.name = c.state)                           |
|      ├─ TableAlias(c)                                       |
|      │   └─ IndexedTableAccess(cities on [cities.name])     |
|      └─ TableAlias(s)                                       |
|          └─ IndexedTableAccess(states on [states.name])     |
+-------------------------------------------------------------+Copy

select * from A join B on a = b;Copy

select * from A join B on a = b join C on b = c;Copy

select * from A join B on a = b join C on b = c join D on c = d;Copy

// joinSearchNode 是一种简化类型，代表一个连接树节点，它既可以是一个内部节点（连接），也可以是一个
// 叶节点（表）。连接树的顶层节点总是内部节点。每个内部节点都有一个
// 左子节点和右子节点。
type joinSearchNode struct {
    table string // 如果是内部节点则为空
    joinCond *joinCond // 如果是叶节点，则为 nil
    parent *joinSearchNode // 如果是根节点则为 nil
    left *joinSearchNode // 如果是叶节点，则为 nil
    right *joinSearchNode // 如果是叶节点，则为 nil
    params *joinSearchParams // 组装此节点的搜索参数
}Copy

func searchJoins(parent *joinSearchNode, params *joinSearchParams) []*joinSearchNode {
    // 我们的目标是为给定的父节点构建所有可能的子节点。
    //合法子树的每一种排列都应进入这个列表。
    children := make([]*joinSearchNode, 0)

    // <snipped code appending tables to the list of children>

    for i, cond := range params.joinConds {
        if params.joinCondIndexUsed(i) {
            continue
        }

        paramsCopy := params.copy()
        paramsCopy.usedJoinCondsIndexes = append(paramsCopy.usedJoinCondsIndexes, i)

        candidate := &joinSearchNode{
            joinCond: cond,
            parent:   parent,
            params:   paramsCopy,
        }

        // 为每个左分支和右分支找到所有可能的子树，并将所有有效子树添加到列表中
        candidate = candidate.targetLeft()
        leftChildren := searchJoins(candidate, paramsCopy)

        // 注意此区块中的变量阴影
        for _, left := range leftChildren {
            if !isValidJoinSubTree(left) {
                continue
            }
            candidate := candidate.withChild(left).targetRight()
            candidate.params = candidate.accumulateAllUsed()
            rightChildren := searchJoins(candidate, paramsCopy)
            for _, right := range rightChildren {
                if !isValidJoinSubTree(right) {
                    continue
                }
                candidate := candidate.withChild(right)
                if isValidJoinSubTree(candidate) {
                    children = append(children, candidate)
                }
            }
        }
    }

    return children
}Copy

func replaceTableAccessWithIndexedAccess(
    node sql.Node,
    schema sql.Schema,
    scope *Scope,
    joinIndexes joinIndexesByTable,
    exprAliases ExprAliases,
    tableAliases TableAliases,
) sql.Node {

    switch node := node.(type) {
    case *plan.TableAlias, *plan.ResolvedTable:
        // 如果可用模式可以在该表上建立索引，则使用该索引，用索引访问替换该表
        indexes := joinIndexes[node.(sql.Nameable).Name()]
        indexToApply := indexes.getUsableIndex(schema)
        if indexToApply == nil {
            return node
        }

        node, err := plan.TransformUp(node, func(node sql.Node) (sql.Node, error) {
            switch node := node.(type) {
            case *plan.ResolvedTable:
                if _, ok := node.Table.(sql.IndexAddressableTable); !ok {
                    return node
                }

                keyExprs := createIndexLookupKeyExpression(indexToApply, exprAliases, tableAliases)
                keyExprs, err := FixFieldIndexesOnExpressions(scope, schema, keyExprs...)

                return plan.NewIndexedTableAccess(node, indexToApply.index, keyExprs)
            default:
                return node
            }
        })

        return node
    case *plan.IndexedJoin:
        // 使用输入模式从左侧向下递归
        left, replacedLeft, err := replaceTableAccessWithIndexedAccess(node.Left(), schema, scope, joinIndexes, exprAliases, tableAliases)

       // 然后在右侧添加左侧的模式
       right, replacedRight, err := replaceTableAccessWithIndexedAccess(node.Right(), append(schema, left.Schema()...), scope, joinIndexes, exprAliases, tableAliases)

       // 如果表格顺序发生变化，可能需要调整条件的字段索引
       cond, err := FixFieldIndexes(scope, append(schema, append(left.Schema(), right.Schema()...)...), node.Cond)
       return plan.NewIndexedJoin(left, right, node.JoinType(), cond)
   default:
       // 其他节点类型
       newChild, replaced, err := replaceTableAccessWithIndexedAccess(node.Child, schema, scope, joinIndexes, exprAliases, tableAliases)
       return node.WithChildren(newChild)
   }
}Copy

// orderTables 返回所提供表格的访问顺序，试图将总查询成本降至最低
func orderTables(tables []NameableNode, tablesByName map[string]NameableNode, joinIndexes joinIndexesByTable) []string {
    tableNames := make([]string, len(tablesByName))
    indexes := make([]int, len(tablesByName))
    for i, table := range tables {
        tableNames[i] = strings.ToLower(table.Name())
        indexes[i] = i
    }

    // 生成表顺序的所有排列
    accessOrders := permutations(indexes)
    lowestCost := int64(math.MaxInt64)
    lowestCostIdx := 0
    for i, accessOrder := range accessOrders {
        cost := estimateTableOrderCost(tableNames, tablesByName, accessOrder, joinIndexes, lowestCost)
        if cost < lowestCost {
            lowestCost = cost
            lowestCostIdx = i
        }
    }

    cheapestOrder := make([]string, len(tableNames))
    for i, j := range accessOrders[lowestCostIdx] {
        cheapestOrder[i] = tableNames[j]
    }

    return cheapestOrder
}Copy

// 估计所给表格排序的成本。数字越小越好。如果成本超过目前发现的最低值就返还
// 如果我们有表格和键的统计信息，我们可以做得更好。
func estimateTableOrderCost(
    tables []string,
    tableNodes map[string]NameableNode,
    accessOrder []int,
    joinIndexes joinIndexesByTable,
    lowestCost int64,
) int64 {
    cost := int64(1)
    var availableSchemaForKeys sql.Schema
    for i, idx := range accessOrder {
        if cost >= lowestCost {
            return cost
        }

        table := tables[idx]
        availableSchemaForKeys = append(availableSchemaForKeys, tableNodes[table].Schema()...)
        indexes := joinIndexes[table]

        // 如果该表是左连接或右连接的一部分，请确保表的顺序正确。在这种情况下，连接条件中引用的
        // 在这种情况下，连接条件中引用的任何表都不能在此表之前。
        for _, idx := range indexes {
            if (idx.joinType == plan.JoinTypeLeft && idx.joinPosition == plan.JoinTypeLeft) ||
                (idx.joinType == plan.JoinTypeRight && idx.joinPosition == plan.JoinTypeRight) {
                for j := 0; j < i; j++ {
                    otherTable := tables[accessOrder[j]]
                    if colsIncludeTable(idx.comparandCols, otherTable) {
                        return math.MaxInt64
                    }
                }
            }
        }

        if i == 0 || indexes.getUsableIndex(availableSchemaForKeys) == nil {
            // TODO：估算表格中的行数
            cost *= 1000
        } else {
            // TODO: 根据索引查找结果估算行数。
            cardinality
            cost += 1
        }
    }

    return cost
}Copy