func makeIsNotNull(left parser.TypedExpr) parser.TypedExpr {
	return parser.NewTypedComparisonExpr(
		parser.IsNot,
		left,
		parser.DNull,
	)
}

func makePrefixRange(prefix parser.DString, datum parser.TypedExpr, complete bool) parser.TypedExpr {
	if complete {
		return parser.NewTypedComparisonExpr(
			parser.EQ,
			datum,
			&prefix,
		)
	}
	if len(prefix) == 0 {
		return parser.MakeDBool(true)
	}
	return parser.NewTypedAndExpr(
		parser.NewTypedComparisonExpr(
			parser.GE,
			datum,
			&prefix,
		),
		parser.NewTypedComparisonExpr(
			parser.LT,
			datum,
			parser.NewDString(string(roachpb.Key(prefix).PrefixEnd())),
		),
	)
}

func simplifyOneOrExpr(left, right parser.TypedExpr) (parser.TypedExpr, parser.TypedExpr, bool) {
	lcmp, ok := left.(*parser.ComparisonExpr)
	if !ok {
		return left, right, true
	}
	rcmp, ok := right.(*parser.ComparisonExpr)
	if !ok {
		return left, right, true
	}
	lcmpLeft, lcmpRight := lcmp.TypedLeft(), lcmp.TypedRight()
	rcmpLeft, rcmpRight := rcmp.TypedLeft(), rcmp.TypedRight()
	if !isDatum(lcmpRight) || !isDatum(rcmpRight) {
		return parser.MakeDBool(true), nil, false
	}
	if !varEqual(lcmpLeft, rcmpLeft) {
		return left, right, true
	}

	if lcmp.Operator == parser.IsNot || rcmp.Operator == parser.IsNot {
		switch lcmp.Operator {
		case parser.Is:
			if lcmpRight == parser.DNull && rcmpRight == parser.DNull {
				// a IS NULL OR a IS NOT NULL
				return parser.MakeDBool(true), nil, true
			}
		case parser.IsNot:
			if lcmpRight == parser.DNull {
				switch rcmp.Operator {
				case parser.Is:
					if rcmpRight == parser.DNull {
						// a IS NOT NULL OR a IS NULL
						return parser.MakeDBool(true), nil, true
					}
				case parser.IsNot:
					if rcmpRight == parser.DNull {
						// a IS NOT NULL OR a IS NOT NULL
						return left, nil, true
					}
				}
			}
		}
		return left, right, true
	}

	if lcmp.Operator == parser.In || rcmp.Operator == parser.In {
		left, right = simplifyOneOrInExpr(lcmp, rcmp)
		return left, right, true
	}

	if reflect.TypeOf(lcmpRight) != reflect.TypeOf(rcmpRight) {
		allowCmp := false
		switch lcmp.Operator {
		case parser.EQ, parser.NE, parser.GT, parser.GE, parser.LT, parser.LE:
			switch rcmp.Operator {
			case parser.EQ, parser.NE, parser.GT, parser.GE, parser.LT, parser.LE:
				// Break, permitting heterogeneous comparison.
				allowCmp = true
			}
		}
		if !allowCmp {
			// If the types of the left and right datums are different, no
			// simplification is possible.
			return left, right, true
		}
	}

	ldatum := lcmpRight.(parser.Datum)
	rdatum := rcmpRight.(parser.Datum)
	cmp := ldatum.Compare(rdatum)

	// Determine which expression to use when either expression (left or right)
	// is valid as a return value but their types are different. The reason
	// to prefer a comparison between a column value and a datum of the same
	// type is that it makes index constraint construction easier.
	either := lcmp
	if !ldatum.ResolvedType().Equal(rdatum.ResolvedType()) {
		switch ta := lcmpLeft.(type) {
		case *parser.IndexedVar:
			if ta.ResolvedType().Equal(rdatum.ResolvedType()) {
				either = rcmp
			}
		}
	}

	// TODO(pmattis): Figure out how to generate this logic.
	switch lcmp.Operator {
	case parser.EQ:
		switch rcmp.Operator {
		case parser.EQ:
			// a = x OR a = y
			if cmp == 0 {
				// x = y
				return either, nil, true
			} else if cmp == 1 {
				// x > y
				ldatum, rdatum = rdatum, ldatum
			}
			return parser.NewTypedComparisonExpr(
				parser.In,
				lcmpLeft,
//.........这里部分代码省略.........

func simplifyOneAndInExpr(left, right *parser.ComparisonExpr) (parser.TypedExpr, parser.TypedExpr) {
	if left.Operator != parser.In && right.Operator != parser.In {
		panic(fmt.Sprintf("IN expression required: %s vs %s", left, right))
	}

	origLeft, origRight := left, right

	switch left.Operator {
	case parser.EQ, parser.NE, parser.GT, parser.GE, parser.LT, parser.LE, parser.Is:
		switch right.Operator {
		case parser.In:
			left, right = right, left
		}
		fallthrough

	case parser.In:
		ltuple := *left.Right.(*parser.DTuple)
		switch right.Operator {
		case parser.Is:
			if right.Right == parser.DNull {
				return parser.MakeDBool(false), nil
			}

		case parser.EQ, parser.NE, parser.GT, parser.GE, parser.LT, parser.LE:
			// Our tuple will be sorted (see simplifyComparisonExpr). Binary search
			// for the right datum.
			datum := right.Right.(parser.Datum)
			i := sort.Search(len(ltuple), func(i int) bool {
				return ltuple[i].(parser.Datum).Compare(datum) >= 0
			})

			switch right.Operator {
			case parser.EQ:
				if i < len(ltuple) && ltuple[i].Compare(datum) == 0 {
					return right, nil
				}
				return parser.MakeDBool(false), nil

			case parser.NE:
				if i < len(ltuple) && ltuple[i].Compare(datum) == 0 {
					if len(ltuple) < 2 {
						return parser.MakeDBool(false), nil
					}
					ltuple = remove(ltuple, i)
				}
				return parser.NewTypedComparisonExpr(
					parser.In,
					left.TypedLeft(),
					&ltuple,
				), nil

			case parser.GT:
				if i < len(ltuple) {
					if ltuple[i].Compare(datum) == 0 {
						ltuple = ltuple[i+1:]
					} else {
						ltuple = ltuple[i:]
					}
					if len(ltuple) > 0 {
						return parser.NewTypedComparisonExpr(
							parser.In,
							left.TypedLeft(),
							&ltuple,
						), nil
					}
				}
				return parser.MakeDBool(false), nil

			case parser.GE:
				if i < len(ltuple) {
					ltuple = ltuple[i:]
					if len(ltuple) > 0 {
						return parser.NewTypedComparisonExpr(
							parser.In,
							left.TypedLeft(),
							&ltuple,
						), nil
					}
				}
				return parser.MakeDBool(false), nil

			case parser.LT:
				if i < len(ltuple) {
					if i == 0 {
						return parser.MakeDBool(false), nil
					}
					ltuple = ltuple[:i]
					return parser.NewTypedComparisonExpr(
						parser.In,
						left.TypedLeft(),
						&ltuple,
					), nil
				}
				return left, nil

			case parser.LE:
				if i < len(ltuple) {
					if ltuple[i].Compare(datum) == 0 {
						i++
					}
//.........这里部分代码省略.........

//.........这里部分代码省略.........
			if cmp == 1 || (cmp == 0 && rcmp.Operator == parser.LT) {
				// x > y OR x = y
				return parser.MakeDBool(false), nil, true
			}
			return left, nil, true
		}

	case parser.NE:
		switch rcmp.Operator {
		case parser.EQ:
			// a != x AND a = y
			if cmp == 0 {
				// x = y
				return parser.MakeDBool(false), nil, true
			}
			return right, nil, true
		case parser.NE:
			// a != x AND a != y
			if cmp == 0 {
				// x = y
				return either, nil, true
			}
			return left, right, true
		case parser.GT:
			// a != x AND a > y
			return right, nil, cmp <= 0
		case parser.LT:
			// a != x AND a < y
			return right, nil, cmp >= 0
		case parser.GE:
			// a != x AND a >= y
			if cmp == 0 {
				// x = y
				return parser.NewTypedComparisonExpr(
					parser.GT,
					rcmpLeft,
					either.TypedRight(),
				), nil, true
			}
			// x != y
			return right, nil, cmp == -1
		case parser.LE:
			// a != x AND a <= y
			if cmp == 0 {
				// x = y
				return parser.NewTypedComparisonExpr(
					parser.LT,
					rcmpLeft,
					either.TypedRight(),
				), nil, true
			}
			// x != y
			return right, nil, cmp == +1
		}

	case parser.GT:
		switch rcmp.Operator {
		case parser.EQ:
			// a > x AND a = y
			if cmp != -1 {
				// x >= y
				return parser.MakeDBool(false), nil, true
			}
			// x < y
			return right, nil, true
		case parser.NE:

func simplifyNotExpr(n *parser.NotExpr) (parser.TypedExpr, bool) {
	if n.Expr == parser.DNull {
		return parser.DNull, true
	}
	switch t := n.Expr.(type) {
	case *parser.ComparisonExpr:
		op := t.Operator
		switch op {
		case parser.EQ:
			op = parser.NE
		case parser.NE:
			op = parser.EQ
		case parser.GT:
			op = parser.LE
		case parser.GE:
			op = parser.LT
		case parser.LT:
			op = parser.GE
		case parser.LE:
			op = parser.GT
		case parser.In:
			op = parser.NotIn
		case parser.NotIn:
			op = parser.In
		case parser.Like:
			op = parser.NotLike
		case parser.NotLike:
			op = parser.Like
		case parser.ILike:
			op = parser.NotILike
		case parser.NotILike:
			op = parser.ILike
		case parser.SimilarTo:
			op = parser.NotSimilarTo
		case parser.NotSimilarTo:
			op = parser.SimilarTo
		case parser.RegMatch:
			op = parser.NotRegMatch
		case parser.RegIMatch:
			op = parser.NotRegIMatch
		default:
			return parser.MakeDBool(true), false
		}
		return simplifyExpr(parser.NewTypedComparisonExpr(
			op,
			t.TypedLeft(),
			t.TypedRight(),
		))

	case *parser.AndExpr:
		// De Morgan's Law: NOT (a AND b) -> (NOT a) OR (NOT b)
		return simplifyExpr(parser.NewTypedOrExpr(
			parser.NewTypedNotExpr(t.TypedLeft()),
			parser.NewTypedNotExpr(t.TypedRight()),
		))

	case *parser.OrExpr:
		// De Morgan's Law: NOT (a OR b) -> (NOT a) AND (NOT b)
		return simplifyExpr(parser.NewTypedAndExpr(
			parser.NewTypedNotExpr(t.TypedLeft()),
			parser.NewTypedNotExpr(t.TypedRight()),
		))
	}
	return parser.MakeDBool(true), false
}

func simplifyComparisonExpr(n *parser.ComparisonExpr) (parser.TypedExpr, bool) {
	// NormalizeExpr will have left comparisons in the form "<var> <op>
	// <datum>" unless they could not be simplified further in which case
	// simplifyExpr cannot handle them. For example, "lower(a) = 'foo'"
	left, right := n.TypedLeft(), n.TypedRight()
	if isVar(left) && isDatum(right) {
		if right == parser.DNull {
			switch n.Operator {
			case parser.IsNotDistinctFrom:
				switch left.(type) {
				case *parser.IndexedVar:
					// Transform "a IS NOT DISTINCT FROM NULL" into "a IS NULL".
					return parser.NewTypedComparisonExpr(
						parser.Is,
						left,
						right,
					), true
				}
			case parser.IsDistinctFrom:
				switch left.(type) {
				case *parser.IndexedVar:
					// Transform "a IS DISTINCT FROM NULL" into "a IS NOT NULL".
					return parser.NewTypedComparisonExpr(
						parser.IsNot,
						left,
						right,
					), true
				}
			case parser.Is, parser.IsNot:
				switch left.(type) {
				case *parser.IndexedVar:
					// "a IS {,NOT} NULL" can be used during index selection to restrict
					// the range of scanned keys.
					return n, true
				}
			default:
				// All of the remaining comparison operators have the property that when
				// comparing to NULL they evaluate to NULL (see evalComparisonOp). NULL is
				// not the same as false, but in the context of a WHERE clause, NULL is
				// considered not-true which is the same as false.
				return parser.MakeDBool(false), true
			}
		}

		switch n.Operator {
		case parser.EQ:
			// Translate "(a, b) = (1, 2)" to "(a, b) IN ((1, 2))".
			switch left.(type) {
			case *parser.Tuple:
				return parser.NewTypedComparisonExpr(
					parser.In,
					left,
					&parser.DTuple{right.(parser.Datum)},
				), true
			}
			return n, true
		case parser.NE, parser.GE, parser.LE:
			return n, true
		case parser.GT:
			// This simplification is necessary so that subsequent transformation of
			// > constraint to >= can use Datum.Next without concern about whether a
			// next value exists. Note that if the variable (n.Left) is NULL, this
			// comparison would evaluate to NULL which is equivalent to false for a
			// boolean expression.
			if right.(parser.Datum).IsMax() {
				return parser.MakeDBool(false), true
			}
			return n, true
		case parser.LT:
			// Note that if the variable is NULL, this would evaluate to NULL which
			// would equivalent to false for a boolean expression.
			if right.(parser.Datum).IsMin() {
				return parser.MakeDBool(false), true
			}
			return n, true
		case parser.In, parser.NotIn:
			tuple := *right.(*parser.DTuple)
			if len(tuple) == 0 {
				return parser.MakeDBool(false), true
			}
			return n, true
		case parser.Like:
			// a LIKE 'foo%' -> a >= "foo" AND a < "fop"
			if d, ok := right.(*parser.DString); ok {
				if i := strings.IndexAny(string(*d), "_%"); i >= 0 {
					return makePrefixRange((*d)[:i], left, false), false
				}
				return makePrefixRange(*d, left, true), false
			}
			// TODO(pmattis): Support parser.DBytes?
		case parser.SimilarTo:
			// a SIMILAR TO "foo.*" -> a >= "foo" AND a < "fop"
			if d, ok := right.(*parser.DString); ok {
				pattern := parser.SimilarEscape(string(*d))
				if re, err := regexp.Compile(pattern); err == nil {
					prefix, complete := re.LiteralPrefix()
					return makePrefixRange(parser.DString(prefix), left, complete), false
				}
			}
			// TODO(pmattis): Support parser.DBytes?
//.........这里部分代码省略.........

func simplifyOneOrInExpr(left, right *parser.ComparisonExpr) (parser.TypedExpr, parser.TypedExpr) {
	if left.Operator != parser.In && right.Operator != parser.In {
		panic(fmt.Sprintf("IN expression required: %s vs %s", left, right))
	}

	origLeft, origRight := left, right

	switch left.Operator {
	case parser.EQ, parser.NE, parser.GT, parser.GE, parser.LT, parser.LE:
		switch right.Operator {
		case parser.In:
			left, right = right, left
		}
		fallthrough

	case parser.In:
		tuple := *left.Right.(*parser.DTuple)
		switch right.Operator {
		case parser.EQ:
			datum := right.Right.(parser.Datum)
			// We keep the tuples for an IN expression in sorted order. So now we just
			// merge the two sorted lists.
			return parser.NewTypedComparisonExpr(
				parser.In,
				left.TypedLeft(),
				mergeSorted(tuple, parser.DTuple{datum}),
			), nil

		case parser.NE, parser.GT, parser.GE, parser.LT, parser.LE:
			datum := right.Right.(parser.Datum)
			i := sort.Search(len(tuple), func(i int) bool {
				return tuple[i].(parser.Datum).Compare(datum) >= 0
			})

			switch right.Operator {
			case parser.NE:
				if i < len(tuple) && tuple[i].Compare(datum) == 0 {
					return makeIsNotNull(right.TypedLeft()), nil
				}
				return right, nil

			case parser.GT:
				if i == 0 {
					// datum >= tuple[0]
					if tuple[i].Compare(datum) == 0 {
						// datum = tuple[0]
						return parser.NewTypedComparisonExpr(
							parser.GE,
							left.TypedLeft(),
							datum,
						), nil
					}
					return right, nil
				}
			case parser.GE:
				if i == 0 {
					// datum >= tuple[0]
					return right, nil
				}
			case parser.LT:
				if i == len(tuple) {
					// datum > tuple[len(tuple)-1]
					return right, nil
				} else if i == len(tuple)-1 {
					// datum >= tuple[len(tuple)-1]
					if tuple[i].Compare(datum) == 0 {
						// datum == tuple[len(tuple)-1]
						return parser.NewTypedComparisonExpr(
							parser.LE,
							left.TypedLeft(),
							datum,
						), nil
					}
				}
			case parser.LE:
				if i == len(tuple) ||
					(i == len(tuple)-1 && tuple[i].Compare(datum) == 0) {
					// datum >= tuple[len(tuple)-1]
					return right, nil
				}
			}

		case parser.In:
			// We keep the tuples for an IN expression in sorted order. So now we
			// just merge the two sorted lists.
			return parser.NewTypedComparisonExpr(
				parser.In,
				left.TypedLeft(),
				mergeSorted(tuple, *right.Right.(*parser.DTuple)),
			), nil
		}
	}

	return origLeft, origRight
}

// makeIndexConstraints generates constraints for a set of conjunctions (AND
// expressions). These expressions can be the entire filter, or they can be one
// of multiple top-level disjunctions (ORs).
//
// The constraints consist of start and end expressions for a prefix of the
// columns that make up the index. For example, consider the expression
// "a >= 1 AND b >= 2":
//
//   {a: {start: >= 1}, b: {start: >= 2}}
//
// This method generates one indexConstraint for a prefix of the columns in
// the index (except for tuple constraints which can account for more than
// one column). A prefix of the generated constraints has a .start, and
// similarly a prefix of the constraints has a .end (in other words,
// once a constraint doesn't have a .start, no further constraints will
// have one). This is because they wouldn't be useful when generating spans.
//
// makeIndexConstraints takes into account the direction of the columns in the
// index.  For ascending cols, start constraints look for comparison expressions
// with the operators >, >=, = or IN and end constraints look for comparison
// expressions with the operators <, <=, = or IN. Vice versa for descending
// cols.
//
// Whenever possible, < and > are converted to <= and >=, respectively.
// This is because we can use inclusive constraints better than exclusive ones;
// with inclusive constraints we can continue to accumulate constraints for
// next columns. Not so with exclusive ones: Consider "a < 1 AND b < 2".
// "a < 1" will be encoded as an exclusive span end; if we were to append
// anything about "b" to it, that would be incorrect.
// Note that it's not always possible to transform ">" to ">=", because some
// types do not support the Next() operation. Similarly, it is not always possible
// to transform "<" to "<=", because some types do not support the Prev() operation.
// So, the resulting constraints might contain ">" or "<" (depending on encoding
// direction), in which case that will be the last constraint with `.end` filled.
//
// TODO(pmattis): It would be more obvious to perform this transform in
// simplifyComparisonExpr, but doing so there eliminates some of the other
// simplifications. For example, "a < 1 OR a > 1" currently simplifies to "a !=
// 1", but if we performed this transform in simpilfyComparisonExpr it would
// simplify to "a < 1 OR a >= 2" which is also the same as "a != 1", but not so
// obvious based on comparisons of the constants.
func (v *indexInfo) makeIndexConstraints(andExprs parser.TypedExprs) (indexConstraints, error) {
	var constraints indexConstraints

	trueStartDone := false
	trueEndDone := false

	for i := 0; i < len(v.index.ColumnIDs); i++ {
		colID := v.index.ColumnIDs[i]
		var colDir encoding.Direction
		var err error
		if colDir, err = v.index.ColumnDirections[i].ToEncodingDirection(); err != nil {
			return nil, err
		}

		var constraint indexConstraint
		// We're going to fill in that start and end of the constraint
		// by indirection, which keeps in mind the direction of the
		// column's encoding in the index.
		// This allows us to produce direction-aware constraints, but
		// still have the code below be intuitive (e.g. treat ">" always as
		// a start constraint).
		startExpr := &constraint.start
		endExpr := &constraint.end
		startDone := &trueStartDone
		endDone := &trueEndDone
		if colDir == encoding.Descending {
			// For descending index cols, c.start is an end constraint
			// and c.end is a start constraint.
			startExpr = &constraint.end
			endExpr = &constraint.start
			startDone = &trueEndDone
			endDone = &trueStartDone
		}

	exprLoop:
		for _, e := range andExprs {
			if c, ok := e.(*parser.ComparisonExpr); ok {
				var tupleMap []int

				if ok, colIdx := getColVarIdx(c.Left); ok && v.desc.Columns[colIdx].ID != colID {
					// This expression refers to a column other than the one we're
					// looking for.
					continue
				}

				if _, ok := c.Right.(parser.Datum); !ok {
					continue
				}

				if t, ok := c.Left.(*parser.Tuple); ok {
					// If we have a tuple comparison we need to rearrange the comparison
					// so that the order of the columns in the tuple matches the order in
					// the index. For example, for an index on (a, b), the tuple
					// comparison "(b, a) = (1, 2)" would be rewritten as "(a, b) = (2,
					// 1)". Note that we don't actually need to rewrite the comparison,
					// but simply provide a mapping from the order in the tuple to the
					// order in the index.
					for _, colID := range v.index.ColumnIDs[i:] {
						idx := -1
//.........这里部分代码省略.........