// Optimize applies generic optimizations for the tree.
// If quad store is specified it will also resolve Lookups and apply any specific optimizations.
// Should not be used with Simplify - it will fold query to a compact form again.
326705
func Optimize(s Shape, qs graph.QuadStore) (Shape, bool) {
	if s == nil {
		return nil, false
	}
	qs = graph.Unwrap(qs)
	var opt bool
	if qs != nil {
		// resolve all lookups earlier
		s, opt = s.Optimize(resolveValues{qs: qs})
	}
	if s == nil {
		return Null{}, true
	}
	// generic optimizations
	var opt1 bool
	s, opt1 = s.Optimize(nil)
	if s == nil {
		return Null{}, true
	}
	opt = opt || opt1
	// apply quadstore-specific optimizations
	if so, ok := qs.(Optimizer); ok && s != nil {
		var opt2 bool
		s, opt2 = s.Optimize(so)
		opt = opt || opt2
	}
	if s == nil {
		return Null{}, true
	}
	return s, opt
}
104672
func (r *grammarOptimizer) optimize(expr0 Expression) Visitor {
	switch expr := expr0.(type) {
	case *ActionExpr:
		expr.Expr = r.optimizeRule(expr.Expr)
	case *AndExpr:
		expr.Expr = r.optimizeRule(expr.Expr)
	case *ChoiceExpr:
		expr.Alternatives = r.optimizeRules(expr.Alternatives)

		// Optimize choice nested in choice
		for i := 0; i < len(expr.Alternatives); i++ {
			if choice, ok := expr.Alternatives[i].(*ChoiceExpr); ok {
				r.optimized = true
				if i+1 < len(expr.Alternatives) {
					expr.Alternatives = append(expr.Alternatives[:i], append(choice.Alternatives, expr.Alternatives[i+1:]...)...)
				} else {
					expr.Alternatives = append(expr.Alternatives[:i], choice.Alternatives...)
				}
			}

			// Combine sequence of single char LitMatcher to CharClassMatcher
			if i > 0 {
				l0, lok0 := expr.Alternatives[i-1].(*LitMatcher)
				l1, lok1 := expr.Alternatives[i].(*LitMatcher)
				c0, cok0 := expr.Alternatives[i-1].(*CharClassMatcher)
				c1, cok1 := expr.Alternatives[i].(*CharClassMatcher)

				combined := false

				switch {
				// Combine two LitMatcher to CharClassMatcher
				// "a" / "b" => [ab]
				case lok0 && lok1 && len([]rune(l0.Val)) == 1 && len([]rune(l1.Val)) == 1 && l0.IgnoreCase == l1.IgnoreCase:
					combined = true
					cm := CharClassMatcher{
						Chars:      append([]rune(l0.Val), []rune(l1.Val)...),
						IgnoreCase: l0.IgnoreCase,
						posValue:   l0.posValue,
					}
					expr.Alternatives[i-1] = &cm

				// Combine LitMatcher with CharClassMatcher
				// "a" / [bc] => [abc]
				case lok0 && cok1 && len([]rune(l0.Val)) == 1 && l0.IgnoreCase == c1.IgnoreCase && !c1.Inverted:
					combined = true
					c1.Chars = append(c1.Chars, []rune(l0.Val)...)
					expr.Alternatives[i-1] = c1

				// Combine CharClassMatcher with LitMatcher
				// [ab] / "c" => [abc]
				case cok0 && lok1 && len([]rune(l1.Val)) == 1 && c0.IgnoreCase == l1.IgnoreCase && !c0.Inverted:
					combined = true
					c0.Chars = append(c0.Chars, []rune(l1.Val)...)

				// Combine CharClassMatcher with CharClassMatcher
				// [ab] / [cd] => [abcd]
				case cok0 && cok1 && c0.IgnoreCase == c1.IgnoreCase && c0.Inverted == c1.Inverted:
					combined = true
					c0.Chars = append(c0.Chars, c1.Chars...)
					c0.Ranges = append(c0.Ranges, c1.Ranges...)
					c0.UnicodeClasses = append(c0.UnicodeClasses, c1.UnicodeClasses...)
				}

				// If one of the optimizations was applied, remove the second element from Alternatives
				if combined {
					r.optimized = true
					if i+1 < len(expr.Alternatives) {
						expr.Alternatives = append(expr.Alternatives[:i], expr.Alternatives[i+1:]...)
					} else {
						expr.Alternatives = expr.Alternatives[:i]
					}
				}
			}
		}

	case *Grammar:
		// Reset optimized at the start of each Walk.
		r.optimized = false
		for i := 0; i < len(expr.Rules); i++ {
			rule := expr.Rules[i]
			// Remove Rule, if it is no longer used by any other Rule and it is not the first Rule.
			_, used := r.ruleUsedByRules[rule.Name.Val]
			_, protected := r.protectedRules[rule.Name.Val]
			if !used && !protected {
				expr.Rules = append(expr.Rules[:i], expr.Rules[i+1:]...)
				r.optimized = true
				continue
			}
		}
	case *LabeledExpr:
		expr.Expr = r.optimizeRule(expr.Expr)
	case *NotExpr:
		expr.Expr = r.optimizeRule(expr.Expr)
	case *OneOrMoreExpr:
		expr.Expr = r.optimizeRule(expr.Expr)
	case *Rule:
		r.rule = expr.Name.Val
	case *SeqExpr:
		expr.Exprs = r.optimizeRules(expr.Exprs)

		for i := 0; i < len(expr.Exprs); i++ {
			// Optimize nested sequences
			if seq, ok := expr.Exprs[i].(*SeqExpr); ok {
				r.optimized = true
				if i+1 < len(expr.Exprs) {
					expr.Exprs = append(expr.Exprs[:i], append(seq.Exprs, expr.Exprs[i+1:]...)...)
				} else {
					expr.Exprs = append(expr.Exprs[:i], seq.Exprs...)
				}
			}

			// Combine sequence of LitMatcher
			if i > 0 {
				l0, ok0 := expr.Exprs[i-1].(*LitMatcher)
				l1, ok1 := expr.Exprs[i].(*LitMatcher)
				if ok0 && ok1 && l0.IgnoreCase == l1.IgnoreCase {
					r.optimized = true
					l0.Val += l1.Val
					expr.Exprs[i-1] = l0
					if i+1 < len(expr.Exprs) {
						expr.Exprs = append(expr.Exprs[:i], expr.Exprs[i+1:]...)
					} else {
						expr.Exprs = expr.Exprs[:i]
					}
				}
			}
		}

	case *ZeroOrMoreExpr:
		expr.Expr = r.optimizeRule(expr.Expr)
	case *ZeroOrOneExpr:
		expr.Expr = r.optimizeRule(expr.Expr)
	}
	return r
}
401049
func (ix *Reindexer) Query(q Query) *Reindexer {
	ix.query = q
	return ix
}
302689
func (s *joinReOrderSolver) optimizeRecursive(ctx sessionctx.Context, p LogicalPlan) (LogicalPlan, error) {
	var err error
	curJoinGroup, eqEdges, otherConds := extractJoinGroup(p)
	if len(curJoinGroup) > 1 {
		for i := range curJoinGroup {
			curJoinGroup[i], err = s.optimizeRecursive(ctx, curJoinGroup[i])
			if err != nil {
				return nil, err
			}
		}
		baseGroupSolver := &baseSingleGroupJoinOrderSolver{
			ctx:        ctx,
			otherConds: otherConds,
		}
		if len(curJoinGroup) > ctx.GetSessionVars().TiDBOptJoinReorderThreshold {
			groupSolver := &joinReorderGreedySolver{
				baseSingleGroupJoinOrderSolver: baseGroupSolver,
				eqEdges:                        eqEdges,
			}
			p, err = groupSolver.solve(curJoinGroup)
		} else {
			dpSolver := &joinReorderDPSolver{
				baseSingleGroupJoinOrderSolver: baseGroupSolver,
			}
			dpSolver.newJoin = dpSolver.newJoinWithEdges
			p, err = dpSolver.solve(curJoinGroup, expression.ScalarFuncs2Exprs(eqEdges))
		}
		if err != nil {
			return nil, err
		}
		return p, nil
	}
	newChildren := make([]LogicalPlan, 0, len(p.Children()))
	for _, child := range p.Children() {
		newChild, err := s.optimizeRecursive(ctx, child)
		if err != nil {
			return nil, err
		}
		newChildren = append(newChildren, newChild)
	}
	p.SetChildren(newChildren...)
	return p, nil
}
1209041
func (t *Tree) Build(
	ctx context.Context, sm *SortedMap, txi TxInfo) (err error) {
	t.Lock()
	defer t.Unlock()

	var prevRoot, nextRoot Hash
	if prevRoot, err = t.eng.LookupRoot(ctx); err != nil {
		return err
	}
	if nextRoot, err = t.hashTreeRecursive(ctx,
		Level(0), sm, prevRoot); err != nil {
		return err
	}
	if err = t.eng.CommitRoot(ctx, prevRoot, nextRoot, txi); err != nil {
		return err
	}

	return err
}
982963
func (ub UpdateBuilder) buildTree() (exprNode, error) {
	if ub.operationList == nil {
		return exprNode{}, newUnsetParameterError("buildTree", "UpdateBuilder")
	}
	ret := exprNode{
		children: []exprNode{},
	}

	modes := modeList{}

	for mode := range ub.operationList {
		modes = append(modes, mode)
	}

	sort.Sort(modes)

	for _, key := range modes {
		ret.fmtExpr += string(key) + " $c\n"

		childNode, err := buildChildNodes(ub.operationList[key])
		if err != nil {
			return exprNode{}, err
		}

		ret.children = append(ret.children, childNode)
	}

	return ret, nil
}
678506
func (pe *projectionEliminater) optimize(lp LogicalPlan) (LogicalPlan, error) {
	root := pe.eliminate(lp, make(map[string]*expression.Column), false)
	return root, nil
}
297665
func (c bySortConfig) Less(i, j int) bool {
	ri, rj, cfg := c.rows[i], c.rows[j], c.cfg
	return rowLess(ri, rj, cfg)
}
460942
func (m *OWLQNMinimizer) updateGrad(x *core.Vector, grad *core.Vector) {
	if m.l1reg == 0 {
		return
	}
	for key, val := range grad.Data {
		xval := x.GetValue(key)
		if xval < 0 {
			grad.SetValue(key, val-m.l1reg)
		} else if xval > 0 {
			grad.SetValue(key, val+m.l1reg)
		} else {
			if val < -m.l1reg {
				grad.SetValue(key, val+m.l1reg)
			} else if val > m.l1reg {
				grad.SetValue(key, val-m.l1reg)
			}
		}
	}
	return
}
1130981
func (results *results) search(result *nmVertex) int {
	return sort.Search(len(results.vertices), func(i int) bool {
		return !results.vertices[i].less(results.config, result)
	})
}
848489
func (tr *RTree) Complexity() float64 {
	var nodeCount int
	var itemCount int
	tr.Traverse(func(_, _ []float64, level int, _ interface{}) bool {
		if level == 0 {
			itemCount++
		} else {
			nodeCount++
		}
		return true
	})
	return float64(tr.maxEntries*nodeCount) / float64(itemCount)
}
989823
func (d *SequenceDiffer) computeOptimal(ai, bi int, m blockMode) int32 {
	// base case: no more lines to align
	if ai > len(d.a)-1 || bi > len(d.b)-1 {
		return 0
	}

	// return memoized result
	if d.solution[ai][bi] != Unknown {
		return d.ab[ai][bi]
	}
	// initialize score to infinity
	d.ab[ai][bi] = -math.MaxInt32

	// case: skip a, addition in b (deletion in a)
	if ai < len(d.a) {
		s := d.computeOptimal(ai+1, bi, modeDeleteA)
		s += d.weights.Deletion
		if m != modeDeleteA {
			s += d.weights.NewMode
		}
		if s >= d.ab[ai][bi] {
			d.ab[ai][bi] = s
			d.solution[ai][bi] = LineFromA
		}
	}

	// case: skip b, addition in a (deletion in b)
	if bi < len(d.b) {
		s := d.computeOptimal(ai, bi+1, modeDeleteB)
		s += d.weights.Deletion
		if m != modeDeleteB {
			s += d.weights.NewMode
		}
		if s >= d.ab[ai][bi] {
			d.ab[ai][bi] = s
			d.solution[ai][bi] = LineFromB
		}
	}

	// align lines
	if ai < len(d.a) && bi < len(d.b) {
		var n blockMode
		var s int32
		if d.isLineEqual(d.a[ai], d.b[bi]) {
			n = modeMatch
			s = d.weights.Match
		} else {
			n = modeMismatch
			s = d.weights.Mismatch
		}
		s += d.computeOptimal(ai+1, bi+1, n)
		if m != n {
			s += d.weights.NewMode
		}
		if s >= d.ab[ai][bi] {
			d.ab[ai][bi] = s
			// todo: consolidate with n
			if n == modeMatch {
				d.solution[ai][bi] = LineFromBoth
			} else {
				d.solution[ai][bi] = LineFromBothEdit
			}
		}
	}

	return d.ab[ai][bi]
}
293160
func Pair(g1 *G1, g2 *G2) *GT {
	return &GT{optimalAte(g2.p, g1.p, new(bnPool))}
}
710983
func (s *decorrelateSolver) optimize(p LogicalPlan) (LogicalPlan, error) {
	if apply, ok := p.(*LogicalApply); ok {
		outerPlan := apply.children[0]
		innerPlan := apply.children[1]
		apply.corCols = extractCorColumnsBySchema(apply.children[1], apply.children[0].Schema())
		if len(apply.corCols) == 0 {
			// If the inner plan is non-correlated, the apply will be simplified to join.
			join := &apply.LogicalJoin
			join.self = join
			p = join
		} else if sel, ok := innerPlan.(*LogicalSelection); ok {
			// If the inner plan is a selection, we add this condition to join predicates.
			// Notice that no matter what kind of join is, it's always right.
			newConds := make([]expression.Expression, 0, len(sel.Conditions))
			for _, cond := range sel.Conditions {
				newConds = append(newConds, cond.Decorrelate(outerPlan.Schema()))
			}
			apply.attachOnConds(newConds)
			innerPlan = sel.children[0]
			apply.SetChildren(outerPlan, innerPlan)
			return s.optimize(p)
		} else if m, ok := innerPlan.(*LogicalMaxOneRow); ok {
			if m.children[0].MaxOneRow() {
				innerPlan = m.children[0]
				apply.SetChildren(outerPlan, innerPlan)
				return s.optimize(p)
			}
		} else if proj, ok := innerPlan.(*LogicalProjection); ok {
			for i, expr := range proj.Exprs {
				proj.Exprs[i] = expr.Decorrelate(outerPlan.Schema())
			}
			apply.columnSubstitute(proj.Schema(), proj.Exprs)
			innerPlan = proj.children[0]
			apply.SetChildren(outerPlan, innerPlan)
			if apply.JoinType != SemiJoin && apply.JoinType != LeftOuterSemiJoin && apply.JoinType != AntiSemiJoin && apply.JoinType != AntiLeftOuterSemiJoin {
				proj.SetSchema(apply.Schema())
				proj.Exprs = append(expression.Column2Exprs(outerPlan.Schema().Clone().Columns), proj.Exprs...)
				apply.SetSchema(expression.MergeSchema(outerPlan.Schema(), innerPlan.Schema()))
				np, err := s.optimize(p)
				if err != nil {
					return nil, err
				}
				proj.SetChildren(np)
				return proj, nil
			}
			return s.optimize(p)
		} else if agg, ok := innerPlan.(*LogicalAggregation); ok {
			if apply.canPullUpAgg() && agg.canPullUp() {
				innerPlan = agg.children[0]
				apply.JoinType = LeftOuterJoin
				apply.SetChildren(outerPlan, innerPlan)
				agg.SetSchema(apply.Schema())
				agg.GroupByItems = expression.Column2Exprs(outerPlan.Schema().Keys[0])
				newAggFuncs := make([]*aggregation.AggFuncDesc, 0, apply.Schema().Len())

				outerColsInSchema := make([]*expression.Column, 0, outerPlan.Schema().Len())
				for i, col := range outerPlan.Schema().Columns {
					first := aggregation.NewAggFuncDesc(agg.ctx, ast.AggFuncFirstRow, []expression.Expression{col}, false)
					newAggFuncs = append(newAggFuncs, first)

					outerCol, _ := outerPlan.Schema().Columns[i].Clone().(*expression.Column)
					outerCol.RetType = first.RetTp
					outerColsInSchema = append(outerColsInSchema, outerCol)
				}
				newAggFuncs = append(newAggFuncs, agg.AggFuncs...)
				agg.AggFuncs = newAggFuncs
				apply.SetSchema(expression.MergeSchema(expression.NewSchema(outerColsInSchema...), innerPlan.Schema()))
				np, err := s.optimize(p)
				if err != nil {
					return nil, err
				}
				agg.SetChildren(np)
				// TODO: Add a Projection if any argument of aggregate funcs or group by items are scalar functions.
				// agg.buildProjectionIfNecessary()
				agg.collectGroupByColumns()
				return agg, nil
			}
			// We can pull up the equal conditions below the aggregation as the join key of the apply, if only
			// the equal conditions contain the correlated column of this apply.
			if sel, ok := agg.children[0].(*LogicalSelection); ok && apply.JoinType == LeftOuterJoin {
				var (
					eqCondWithCorCol []*expression.ScalarFunction
					remainedExpr     []expression.Expression
				)
				// Extract the equal condition.
				for _, cond := range sel.Conditions {
					if expr := apply.deCorColFromEqExpr(cond); expr != nil {
						eqCondWithCorCol = append(eqCondWithCorCol, expr.(*expression.ScalarFunction))
					} else {
						remainedExpr = append(remainedExpr, cond)
					}
				}
				if len(eqCondWithCorCol) > 0 {
					originalExpr := sel.Conditions
					sel.Conditions = remainedExpr
					apply.corCols = extractCorColumnsBySchema(apply.children[1], apply.children[0].Schema())
					// There's no other correlated column.
					if len(apply.corCols) == 0 {
						join := &apply.LogicalJoin
						join.EqualConditions = append(join.EqualConditions, eqCondWithCorCol...)
						for _, eqCond := range eqCondWithCorCol {
							clonedCol := eqCond.GetArgs()[1]
							// If the join key is not in the aggregation's schema, add first row function.
							if agg.schema.ColumnIndex(eqCond.GetArgs()[1].(*expression.Column)) == -1 {
								newFunc := aggregation.NewAggFuncDesc(apply.ctx, ast.AggFuncFirstRow, []expression.Expression{clonedCol}, false)
								agg.AggFuncs = append(agg.AggFuncs, newFunc)
								agg.schema.Append(clonedCol.(*expression.Column))
								agg.schema.Columns[agg.schema.Len()-1].RetType = newFunc.RetTp
							}
							// If group by cols don't contain the join key, add it into this.
							if agg.getGbyColIndex(eqCond.GetArgs()[1].(*expression.Column)) == -1 {
								agg.GroupByItems = append(agg.GroupByItems, clonedCol)
							}
						}
						agg.collectGroupByColumns()
						// The selection may be useless, check and remove it.
						if len(sel.Conditions) == 0 {
							agg.SetChildren(sel.children[0])
						}
						defaultValueMap := s.aggDefaultValueMap(agg)
						// We should use it directly, rather than building a projection.
						if len(defaultValueMap) > 0 {
							proj := LogicalProjection{}.Init(agg.ctx)
							proj.SetSchema(apply.schema)
							proj.Exprs = expression.Column2Exprs(apply.schema.Columns)
							for i, val := range defaultValueMap {
								pos := proj.schema.ColumnIndex(agg.schema.Columns[i])
								ifNullFunc := expression.NewFunctionInternal(agg.ctx, ast.Ifnull, types.NewFieldType(mysql.TypeLonglong), agg.schema.Columns[i], val)
								proj.Exprs[pos] = ifNullFunc
							}
							proj.SetChildren(apply)
							p = proj
						}
						return s.optimize(p)
					}
					sel.Conditions = originalExpr
					apply.corCols = extractCorColumnsBySchema(apply.children[1], apply.children[0].Schema())
				}
			}
		}
	}
	newChildren := make([]LogicalPlan, 0, len(p.Children()))
	for _, child := range p.Children() {
		np, err := s.optimize(child)
		if err != nil {
			return nil, err
		}
		newChildren = append(newChildren, np)
	}
	p.SetChildren(newChildren...)
	return p, nil
}
258257
func (i *BTreeIndex) Initialize(less LessFunction, keys <-chan string) {
	i.Lock()
	defer i.Unlock()
	i.LessFunction = less
	i.BTree = rebuild(less, keys)
}
860126
func (s *IndexSnapshotTermFieldReader) optimizeConjunction(
	octx index.OptimizableContext) (index.OptimizableContext, error) {
	if octx == nil {
		octx = &OptimizeTFRConjunction{snapshot: s.snapshot}
	}

	o, ok := octx.(*OptimizeTFRConjunction)
	if !ok {
		return octx, nil
	}

	if o.snapshot != s.snapshot {
		return nil, fmt.Errorf("tried to optimize conjunction across different snapshots")
	}

	o.tfrs = append(o.tfrs, s)

	return o, nil
}
667544
func (pq *txPriorityQueue) Less(i, j int) bool {
	return pq.lessFunc(pq, i, j)
}