func colExprsToJoinIndex(table string, idx sql.Index, joinCond joinCond, colExprs joinColExprs) *joinIndex {
	cols := make([]*expression.GetField, len(colExprs))
	cmpCols := make([]*expression.GetField, len(colExprs))
	exprs := make([]sql.Expression, len(colExprs))
	cmpExprs := make([]sql.Expression, len(colExprs))
	joinPosition := plan.JoinTypeLeft
	if strings.ToLower(table) == joinCond.rightHandTable {
		joinPosition = plan.JoinTypeRight
	}
	for i, col := range colExprs {
		cols[i] = col.col
		cmpCols[i] = col.comparandCol
		exprs[i] = col.colExpr
		cmpExprs[i] = col.comparand
	}
	return &joinIndex{
		index:          idx,
		table:          table,
		joinCond:       joinCond.cond,
		joinType:       joinCond.joinType,
		joinPosition:   joinPosition,
		cols:           cols,
		colExprs:       exprs,
		comparandCols:  cmpCols,
		comparandExprs: cmpExprs,
	}
}
colExprsToJoinIndex converts a slice of joinColExpr on a single table to a single *joinIndex
package analyzer
import (
	"fmt"
	"reflect"
	"regexp"
	"strings"
	"github.com/dolthub/go-mysql-server/sql"
	"github.com/dolthub/go-mysql-server/sql/expression"
	"github.com/dolthub/go-mysql-server/sql/plan"
)
func constructJoinPlan(ctx *sql.Context, a *Analyzer, n sql.Node, scope *Scope) (sql.Node, error) {
	span, ctx := ctx.Span("construct_join_plan")
	defer span.Finish()
	if !n.Resolved() {
		return n, nil
	}
	if plan.IsNoRowNode(n) {
		return n, nil
	}
	return replaceJoinPlans(ctx, a, n, scope)
}
func replaceJoinPlans(ctx *sql.Context, a *Analyzer, n sql.Node, scope *Scope) (sql.Node, error) {
	selector := func(c plan.TransformContext) bool {
		switch c.Parent.(type) {
		case *plan.InnerJoin, *plan.LeftJoin, *plan.RightJoin:
			return false
		default:
			return true
		}
	}
	var tableAliases TableAliases
	var joinIndexes joinIndexesByTable
	var oldJoin sql.Node
	newJoin, err := plan.TransformUpCtx(n, selector, func(c plan.TransformContext) (sql.Node, error) {
		switch n := c.Node.(type) {
		case *plan.IndexedJoin:
			return n, nil
		case plan.JoinNode:
			oldJoin = n
			var err error
			tableAliases, err = getTableAliases(n, scope)
			if err != nil {
				return nil, err
			}
			joinIndexes, err = findJoinIndexesByTable(ctx, n, tableAliases, a)
			if err != nil {
				return nil, err
			}
			if len(joinIndexes) != len(getTablesOrSubqueryAliases(n)) {
				return n, nil
			}
			return replanJoin(ctx, n, a, joinIndexes, scope)
		default:
			return n, nil
		}
	})
	if err != nil {
		return nil, err
	}
	withIndexedTableAccess, replacedTableWithIndexedAccess, err := replaceTableAccessWithIndexedAccess(
		ctx, newJoin, a, nil, scope, joinIndexes, tableAliases)
	if err != nil {
		return nil, err
	}
	if !replacedTableWithIndexedAccess {
		return n, nil
	}
	if _, ok := withIndexedTableAccess.(*plan.Update); ok {
		withIndexedTableAccess, err = wrapIndexedJoinForUpdateCases(withIndexedTableAccess, oldJoin)
		if err != nil {
			return nil, err
		}
	}
	return withIndexedTableAccess, nil
}
func wrapIndexedJoinForUpdateCases(node sql.Node, oldJoin sql.Node) (sql.Node, error) {
	topLevelIndexedJoinSelector := func(c plan.TransformContext) bool {
		switch c.Node.(type) {
		case *plan.IndexedJoin:
			_, hasParent := c.Parent.(*plan.IndexedJoin)
			return !hasParent
		default:
			return true
		}
	}
	updated, err := plan.TransformUpCtx(node, topLevelIndexedJoinSelector, func(c plan.TransformContext) (sql.Node, error) {
		switch n := c.Node.(type) {
		case *plan.IndexedJoin:
			return plan.NewProject(expression.SchemaToGetFields(oldJoin.Schema()), n), nil
		default:
			return c.Node, nil
		}
	})
	return updated, err
}
func replaceTableAccessWithIndexedAccess(
	ctx *sql.Context,
	node sql.Node,
	a *Analyzer,
	schema sql.Schema,
	scope *Scope,
	joinIndexes joinIndexesByTable,
	tableAliases TableAliases,
) (sql.Node, bool, error) {
	var toIndexedTableAccess func(node *plan.ResolvedTable, indexToApply *joinIndex) (sql.Node, bool, error)
	toIndexedTableAccess = func(node *plan.ResolvedTable, indexToApply *joinIndex) (sql.Node, bool, error) {
		if _, ok := node.Table.(sql.IndexAddressableTable); !ok {
			return node, false, nil
		}
		if indexToApply.index != nil {
			keyExprs := createIndexLookupKeyExpression(ctx, indexToApply, tableAliases)
			keyExprs, err := FixFieldIndexesOnExpressions(ctx, scope, a, schema, keyExprs...)
			if err != nil {
				return nil, false, err
			}
			return plan.NewIndexedTableAccess(node, indexToApply.index, keyExprs), true, nil
		} else {
			ln, lr, lerr := toIndexedTableAccess(node, indexToApply.disjunction[0])
			if lerr != nil {
				return node, false, lerr
			}
			rn, rr, rerr := toIndexedTableAccess(node, indexToApply.disjunction[1])
			if rerr != nil {
				return node, false, rerr
			}
			if lr && rr {
				return plan.NewTransformedNamedNode(plan.NewConcat(ln, rn), node.Name()), true, nil
			}
			return node, false, nil
		}
	}
	switch node := node.(type) {
	case *plan.TableAlias, *plan.ResolvedTable:
		indexes := joinIndexes[node.(sql.Nameable).Name()]
		_, isSubquery := node.(*plan.SubqueryAlias)
		indexToApply := indexes.getUsableIndex(schema)
		if isSubquery || indexToApply == nil {
			return node, false, nil
		}
		replaced := false
		node, err := plan.TransformUp(node, func(node sql.Node) (sql.Node, error) {
			switch node := node.(type) {
			case *plan.ResolvedTable:
				n, r, err := toIndexedTableAccess(node, indexToApply)
				replaced = r
				return n, err
			default:
				return node, nil
			}
		})
		if err != nil {
			return nil, false, err
		}
		return node, replaced, nil
	case *plan.IndexedJoin:
		left, replacedLeft, err := replaceTableAccessWithIndexedAccess(ctx, node.Left(), a, schema, scope, joinIndexes, tableAliases)
		if err != nil {
			return nil, false, err
		}
		if scope != nil {
			left = plan.NewStripRowNode(left, len(scope.Schema()))
		}
		right, replacedRight, err := replaceTableAccessWithIndexedAccess(ctx, node.Right(), a, append(schema, left.Schema()...), scope, joinIndexes, tableAliases)
		if err != nil {
			return nil, false, err
		}
		if scope != nil {
			right = plan.NewStripRowNode(right, len(scope.Schema()))
		}
		cond, err := FixFieldIndexes(ctx, scope, a, append(schema, append(left.Schema(), right.Schema()...)...), node.Cond)
		if err != nil {
			return nil, false, err
		}
		return plan.NewIndexedJoin(left, right, node.JoinType(), cond, len(scope.Schema())), replacedLeft || replacedRight, nil
	case *plan.Limit:
		return replaceIndexedAccessInUnaryNode(ctx, node.UnaryNode, node, a, schema, scope, joinIndexes, tableAliases)
	case *plan.Sort:
		return replaceIndexedAccessInUnaryNode(ctx, node.UnaryNode, node, a, schema, scope, joinIndexes, tableAliases)
	case *plan.Filter:
		return replaceIndexedAccessInUnaryNode(ctx, node.UnaryNode, node, a, schema, scope, joinIndexes, tableAliases)
	case *plan.Project:
		return replaceIndexedAccessInUnaryNode(ctx, node.UnaryNode, node, a, schema, scope, joinIndexes, tableAliases)
	case *plan.Update:
		return replaceIndexedAccessInUnaryNode(ctx, node.UnaryNode, node, a, schema, scope, joinIndexes, tableAliases)
	case *plan.UpdateSource:
		return replaceIndexedAccessInUnaryNode(ctx, node.UnaryNode, node, a, schema, scope, joinIndexes, tableAliases)
	case *plan.GroupBy:
		return replaceIndexedAccessInUnaryNode(ctx, node.UnaryNode, node, a, schema, scope, joinIndexes, tableAliases)
	case *plan.Window:
		return replaceIndexedAccessInUnaryNode(ctx, node.UnaryNode, node, a, schema, scope, joinIndexes, tableAliases)
	case *plan.Distinct:
		return replaceIndexedAccessInUnaryNode(ctx, node.UnaryNode, node, a, schema, scope, joinIndexes, tableAliases)
	case *plan.CrossJoin:
		newRight, replaced, err := replaceTableAccessWithIndexedAccess(ctx, node.Right(), a, append(schema, node.Left().Schema()...), scope, joinIndexes, tableAliases)
		if err != nil {
			return nil, false, err
		}
		newNode, err := node.WithChildren(node.Left(), newRight)
		return newNode, replaced, err
	default:
		return node, false, nil
	}
}
func replaceIndexedAccessInUnaryNode(
	ctx *sql.Context,
	un plan.UnaryNode,
	node sql.Node,
	a *Analyzer,
	schema sql.Schema,
	scope *Scope,
	joinIndexes joinIndexesByTable,
	tableAliases TableAliases,
) (sql.Node, bool, error) {
	newChild, replaced, err := replaceTableAccessWithIndexedAccess(ctx, un.Child, a, schema, scope, joinIndexes, tableAliases)
	if err != nil {
		return nil, false, err
	}
	newNode, err := node.WithChildren(newChild)
	if err != nil {
		return nil, false, err
	}
	newNode, err = FixFieldIndexesForExpressions(ctx, a, newNode, scope)
	if err != nil {
		return nil, false, err
	}
	return newNode, replaced, nil
}
func replanJoin(ctx *sql.Context, node plan.JoinNode, a *Analyzer, joinIndexes joinIndexesByTable, scope *Scope) (sql.Node, error) {
	eligible := true
	plan.Inspect(node, func(node sql.Node) bool {
		switch node.(type) {
		case plan.JoinNode, *plan.ResolvedTable, *plan.TableAlias, *plan.ValueDerivedTable, nil:
		case *plan.SubqueryAlias:
			return false
		default:
			a.Log("Skipping join replanning because of incompatible node: %T", node)
			eligible = false
		}
		return true
	})
	if !eligible {
		return node, nil
	}
	joinHint := extractJoinHint(node)
	tableJoinOrder := newJoinOrderNode(node)
	ordered := false
	if joinHint != nil {
		var err error
		ordered, err = tableJoinOrder.applyJoinHint(joinHint)
		if err != nil {
			return nil, err
		}
	}
	if !ordered {
		err := tableJoinOrder.estimateCost(ctx, joinIndexes)
		if err != nil {
			return nil, err
		}
	}
	joinTree := buildJoinTree(tableJoinOrder, joinIndexes.flattenJoinConds(tableJoinOrder.tableNames()))
	if joinTree == nil {
		return node, nil
	}
	tablesByName := byLowerCaseName(tableJoinOrder.tables())
	joinNode := joinTreeToNodes(joinTree, tablesByName, scope)
	return joinNode, nil
}
func extractJoinHint(node plan.JoinNode) QueryHint {
	if node.Comment() != "" {
		return parseJoinHint(node.Comment())
	}
	return nil
}
var hintRegex = regexp.MustCompile("(\\s*[a-z_]+\\([^\\(]+\\)\\s*)+")
func parseJoinHint(comment string) QueryHint {
	comment = strings.TrimPrefix(comment, "/*+")
	comment = strings.TrimSuffix(comment, "*/")
	comment = strings.ToLower(strings.TrimSpace(comment))
	hints := hintRegex.FindAll([]byte(comment), -1)
	for _, hint := range hints {
		hintStr := strings.TrimSpace(string(hint))
		if strings.HasPrefix(string(hintStr), "join_order(") {
			var tables []string
			var table strings.Builder
			for _, b := range hintStr[len("join_order("):] {
				switch b {
				case ',', ')':
					tables = append(tables, strings.TrimSpace(table.String()))
					table = strings.Builder{}
				default:
					table.WriteRune(b)
				}
			}
			return JoinOrder{
				tables: tables,
			}
		}
	}
	return nil
}
type QueryHint interface {
	fmt.Stringer
	HintType() string
}
type JoinOrder struct {
	tables []string
}
func (j JoinOrder) String() string {
	return "JOIN_ORDER(" + strings.Join(j.tables, ",") + ")"
}
func (j JoinOrder) HintType() string {
	return "JOIN_ORDER"
}
func joinTreeToNodes(tree *joinSearchNode, tablesByName map[string]NameableNode, scope *Scope) sql.Node {
	if tree.isLeaf() {
		nn, ok := tablesByName[strings.ToLower(tree.table)]
		if !ok {
			panic(fmt.Sprintf("Could not find NameableNode for '%s'", tree.table))
		}
		return nn
	}
	left := joinTreeToNodes(tree.left, tablesByName, scope)
	right := joinTreeToNodes(tree.right, tablesByName, scope)
	return plan.NewIndexedJoin(left, right, tree.joinCond.joinType, tree.joinCond.cond, len(scope.Schema()))
}
func createIndexLookupKeyExpression(ctx *sql.Context, ji *joinIndex, tableAliases TableAliases) []sql.Expression {
	keyExprs := make([]sql.Expression, len(ji.index.Expressions()))
IndexExpressions:
	for i, idxExpr := range ji.index.Expressions() {
		for j, col := range ji.cols {
			if idxExpr == normalizeExpression(ctx, tableAliases, col).String() {
				keyExprs[i] = ji.comparandExprs[j]
				continue IndexExpressions
			}
		}
		return nil
	}
	return keyExprs
}
type joinIndex struct {
	table string
	index sql.Index
	disjunction [2]*joinIndex
	joinCond sql.Expression
	joinType plan.JoinType
	joinPosition plan.JoinType
	cols []*expression.GetField
	colExprs []sql.Expression
	comparandCols []*expression.GetField
	comparandExprs []sql.Expression
}
func (ji *joinIndex) hasIndex() bool {
	if ji.index != nil {
		return true
	}
	if ji.disjunction[0] != nil {
		return ji.disjunction[0].hasIndex() && ji.disjunction[1].hasIndex()
	}
	return false
}
type joinIndexes []*joinIndex
type joinIndexesByTable map[string]joinIndexes
func (j joinIndexes) getUsableIndex(schema sql.Schema) *joinIndex {
	for _, joinIndex := range j {
		if !joinIndex.hasIndex() {
			continue
		}
		allFound := true
		for _, cmpCol := range joinIndex.comparandCols {
			if !schemaContainsField(schema, cmpCol) {
				allFound = false
				break
			}
		}
		if allFound {
			return joinIndex
		}
	}
	return nil
}
func schemaContainsField(schema sql.Schema, field *expression.GetField) bool {
	for _, col := range schema {
		if strings.ToLower(col.Source) == strings.ToLower(field.Table()) &&
			strings.ToLower(col.Name) == strings.ToLower(field.Name()) {
			return true
		}
	}
	return false
}
type joinCond struct {
	cond           sql.Expression
	joinType       plan.JoinType
	rightHandTable string
}
func findJoinIndexesByTable(
	ctx *sql.Context,
	node sql.Node,
	tableAliases TableAliases,
	a *Analyzer,
) (joinIndexesByTable, error) {
	indexSpan, _ := ctx.Span("find_join_indexes")
	defer indexSpan.Finish()
	var err error
	var conds []joinCond
	plan.Inspect(node, func(node sql.Node) bool {
		switch node := node.(type) {
		case plan.JoinNode:
			conds = append(conds, joinCond{
				cond:           node.JoinCond(),
				joinType:       node.JoinType(),
				rightHandTable: strings.ToLower(getTableName(node.Right())),
			})
		}
		return true
	})
	var joinIndexesByTable joinIndexesByTable
	plan.Inspect(node, func(node sql.Node) bool {
		switch node := node.(type) {
		case *plan.InnerJoin, *plan.LeftJoin, *plan.RightJoin:
			var indexAnalyzer *indexAnalyzer
			indexAnalyzer, err = getIndexesForNode(ctx, a, node)
			if err != nil {
				return false
			}
			defer indexAnalyzer.releaseUsedIndexes()
			joinIndexesByTable = getJoinIndexesByTable(ctx, a, indexAnalyzer, conds, tableAliases)
			return false
		}
		return true
	})
	return joinIndexesByTable, err
}
func getJoinIndexesByTable(
	ctx *sql.Context,
	a *Analyzer,
	ia *indexAnalyzer,
	joinConds []joinCond,
	tableAliases TableAliases,
) joinIndexesByTable {
	result := make(joinIndexesByTable)
	for _, cond := range joinConds {
		indexes := getJoinIndexes(ctx, a, ia, cond, tableAliases)
		if len(indexes) == 0 {
			return nil
		}
		result.merge(indexes)
	}
	return result
}
func (ji joinIndexesByTable) merge(other joinIndexesByTable) {
	for table, indices := range other {
		ji[table] = append(ji[table], indices...)
	}
}
func (ji joinIndexesByTable) flattenJoinConds(tableOrder []string) []*joinCond {
	if len(tableOrder) != len(ji) {
		panic(fmt.Sprintf("Inconsistent table order for flattenJoinConds: tableOrder: %v, ji: %v", tableOrder, ji))
	}
	joinConditions := make([]*joinCond, 0)
	for _, table := range tableOrder {
		for _, joinIndex := range ji[table] {
			if joinIndex.joinPosition != plan.JoinTypeRight && !joinCondPresent(joinIndex.joinCond, joinConditions) {
				joinConditions = append(joinConditions, &joinCond{joinIndex.joinCond, joinIndex.joinType, joinIndex.table})
			}
		}
	}
	return joinConditions
}
func joinCondPresent(e sql.Expression, jcs []*joinCond) bool {
	for _, jc := range jcs {
		if reflect.DeepEqual(e, jc.cond) {
			return true
		}
	}
	return false
}
func getJoinIndexes(
	ctx *sql.Context,
	a *Analyzer,
	ia *indexAnalyzer,
	jc joinCond,
	tableAliases TableAliases,
) joinIndexesByTable {
	switch cond := jc.cond.(type) {
	case *expression.Equals, *expression.NullSafeEquals:
		result := make(joinIndexesByTable)
		left, right := getEqualityIndexes(ctx, a, ia, jc, tableAliases)
		if left == nil || right == nil {
			return nil
		}
		result[left.table] = append(result[left.table], left)
		result[right.table] = append(result[right.table], right)
		return result
	case *expression.And:
		exprs := splitConjunction(jc.cond)
		for _, expr := range exprs {
			switch e := expr.(type) {
			case *expression.Equals, *expression.NullSafeEquals, *expression.IsNull:
			case *expression.Not:
				switch e.Child.(type) {
				case *expression.Equals, *expression.NullSafeEquals, *expression.IsNull:
				default:
					return nil
				}
			default:
				return nil
			}
		}
		return getJoinIndex(ctx, jc, exprs, ia, tableAliases)
	case *expression.Or:
		leftCond := joinCond{cond.Left, jc.joinType, jc.rightHandTable}
		rightCond := joinCond{cond.Right, jc.joinType, jc.rightHandTable}
		leftIdxByTbl := getJoinIndexes(ctx, a, ia, leftCond, tableAliases)
		rightIdxByTbl := getJoinIndexes(ctx, a, ia, rightCond, tableAliases)
		result := make(joinIndexesByTable)
		for table, lefts := range leftIdxByTbl {
			if rights, ok := rightIdxByTbl[table]; ok {
				var v joinIndexes
				for _, left := range lefts {
					for _, right := range rights {
						cols := make([]*expression.GetField, 0, len(left.cols)+len(right.cols))
						cols = append(cols, left.cols...)
						cols = append(cols, right.cols...)
						colExprs := make([]sql.Expression, 0, len(left.colExprs)+len(right.colExprs))
						colExprs = append(colExprs, left.colExprs...)
						colExprs = append(colExprs, right.colExprs...)
						comparandCols := make([]*expression.GetField, 0, len(left.comparandCols)+len(right.comparandCols))
						comparandCols = append(comparandCols, left.comparandCols...)
						comparandCols = append(comparandCols, right.comparandCols...)
						comparandExprs := make([]sql.Expression, 0, len(left.comparandExprs)+len(right.comparandExprs))
						comparandExprs = append(comparandExprs, left.comparandExprs...)
						comparandExprs = append(comparandExprs, right.comparandExprs...)
						v = append(v, &joinIndex{
							table:          table,
							index:          nil,
							disjunction:    [2]*joinIndex{left, right},
							joinCond:       jc.cond,
							joinType:       jc.joinType,
							joinPosition:   left.joinPosition,
							cols:           cols,
							colExprs:       colExprs,
							comparandCols:  comparandCols,
							comparandExprs: comparandExprs,
						})
					}
				}
				result[table] = v
			}
		}
		return result
	}
	return nil
}
func getEqualityIndexes(
	ctx *sql.Context,
	a *Analyzer,
	ia *indexAnalyzer,
	joinCond joinCond,
	tableAliases TableAliases,
) (leftJoinIndex *joinIndex, rightJoinIndex *joinIndex) {
	switch joinCond.cond.(type) {
	case *expression.Equals, *expression.NullSafeEquals:
	default:
		return nil, nil
	}
	cond := joinCond.cond.(expression.Comparer)
	if isEvaluable(cond.Left()) || isEvaluable(cond.Right()) {
		return nil, nil
	}
	leftCol, rightCol := extractJoinColumnExpr(cond)
	if leftCol == nil || rightCol == nil {
		return nil, nil
	}
	leftIdx, rightIdx :=
		ia.IndexByExpression(ctx, ctx.GetCurrentDatabase(), leftCol.col.Table(), normalizeExpressions(ctx, tableAliases, cond.Left())...),
		ia.IndexByExpression(ctx, ctx.GetCurrentDatabase(), rightCol.col.Table(), normalizeExpressions(ctx, tableAliases, cond.Right())...)
	leftJoinPosition := plan.JoinTypeLeft
	rightJoinPosition := plan.JoinTypeRight
	if strings.ToLower(rightCol.col.Table()) != joinCond.rightHandTable {
		leftJoinPosition, rightJoinPosition = rightJoinPosition, leftJoinPosition
	}
	leftJoinIndex = &joinIndex{
		table:          leftCol.col.Table(),
		index:          leftIdx,
		joinCond:       joinCond.cond,
		joinType:       joinCond.joinType,
		joinPosition:   leftJoinPosition,
		cols:           []*expression.GetField{leftCol.col},
		colExprs:       []sql.Expression{leftCol.colExpr},
		comparandCols:  []*expression.GetField{leftCol.comparandCol},
		comparandExprs: []sql.Expression{leftCol.comparand},
	}
	rightJoinIndex = &joinIndex{
		table:          rightCol.col.Table(),
		index:          rightIdx,
		joinCond:       joinCond.cond,
		joinType:       joinCond.joinType,
		joinPosition:   rightJoinPosition,
		cols:           []*expression.GetField{rightCol.col},
		colExprs:       []sql.Expression{rightCol.colExpr},
		comparandCols:  []*expression.GetField{rightCol.comparandCol},
		comparandExprs: []sql.Expression{rightCol.comparand},
	}
	return leftJoinIndex, rightJoinIndex
}
func getJoinIndex(
	ctx *sql.Context,
	joinCond joinCond,
	joinCondPredicates []sql.Expression,
	ia *indexAnalyzer,
	tableAliases TableAliases,
) joinIndexesByTable {
	exprsByTable := joinExprsByTable(joinCondPredicates)
	indexesByTable := make(joinIndexesByTable)
	for table, cols := range exprsByTable {
		exprs := extractExpressions(cols)
		idx := ia.IndexByExpression(ctx, ctx.GetCurrentDatabase(), table, normalizeExpressions(ctx, tableAliases, exprs...)...)
		if idx == nil && len(exprs) > 1 {
			for _, e := range exprs {
				idx = ia.IndexByExpression(ctx, ctx.GetCurrentDatabase(), table, normalizeExpressions(ctx, tableAliases, e)...)
				if idx != nil {
					break
				}
			}
		}
		indexesByTable[table] = append(indexesByTable[table], colExprsToJoinIndex(table, idx, joinCond, cols))
	}
	return indexesByTable
}