func checkEquivExpr(a, b parser.Expr, qvals qvalMap) error {
	// The expressions above only use the values 1 and 2. Verify that the
	// simplified expressions evaluate to the same value as the original
	// expression for interesting values.
	zero := parser.DInt(0)
	for _, v := range []parser.Datum{zero, zero + 1, zero + 2, zero + 3, parser.DNull} {
		for _, q := range qvals {
			q.datum = v
		}
		da, err := a.Eval(parser.EvalContext{})
		if err != nil {
			return fmt.Errorf("%s: %v", a, err)
		}
		db, err := b.Eval(parser.EvalContext{})
		if err != nil {
			return fmt.Errorf("%s: %v", b, err)
		}
		// This is tricky: we don't require the expressions to produce identical
		// results, but to either both return true or both return not true (either
		// false or NULL).
		if (da == parser.DBool(true)) != (db == parser.DBool(true)) {
			return fmt.Errorf("%s: %s: expected %s, but found %s", a, v, da, db)
		}
	}
	return nil
}

func (v *extractAggregatesVisitor) Visit(expr parser.Expr, pre bool) (parser.Visitor, parser.Expr) {
	if !pre || v.err != nil {
		return nil, expr
	}

	// This expression is in the GROUP BY - switch to the copy that will accept
	// qvalues for this and any subtrees.
	if _, ok := v.groupStrs[expr.String()]; ok && v.groupedCopy != nil {
		v = v.groupedCopy
	}

	switch t := expr.(type) {
	case *parser.FuncExpr:
		if len(t.Name.Indirect) > 0 {
			break
		}
		if impl, ok := aggregates[strings.ToLower(string(t.Name.Base))]; ok {
			if len(t.Exprs) != 1 {
				// Type checking has already run on these expressions thus
				// if an aggregate function of the wrong arity gets here,
				// something has gone really wrong.
				panic(fmt.Sprintf("%s has %d arguments (expected 1)", t.Name.Base, len(t.Exprs)))
			}

			f := &aggregateFunc{
				expr:    t,
				arg:     t.Exprs[0],
				create:  impl,
				group:   v.n,
				buckets: make(map[string]aggregateImpl),
			}
			if t.Type == parser.Distinct {
				f.seen = make(map[string]struct{})
			}
			v.n.funcs = append(v.n.funcs, f)
			return nil, f
		}
	case *qvalue:
		if v.groupedCopy != nil {
			v.err = fmt.Errorf("column \"%s\" must appear in the GROUP BY clause or be used in an aggregate function",
				t.colRef.get().Name)
			return v, expr
		}
		f := &aggregateFunc{
			expr:    t,
			arg:     t,
			create:  newIdentAggregate,
			group:   v.n,
			buckets: make(map[string]aggregateImpl),
		}
		v.n.funcs = append(v.n.funcs, f)
		return nil, f
	}
	return v, expr
}

func (s *selectNode) addRender(target parser.SelectExpr) *roachpb.Error {
	// outputName will be empty if the target is not aliased.
	outputName := string(target.As)

	if isStar, cols, exprs, err := checkRenderStar(target, &s.table, s.qvals); err != nil {
		s.pErr = roachpb.NewError(err)
		return s.pErr
	} else if isStar {
		s.columns = append(s.columns, cols...)
		s.render = append(s.render, exprs...)
		return nil
	}

	// When generating an output column name it should exactly match the original
	// expression, so determine the output column name before we perform any
	// manipulations to the expression.
	outputName = getRenderColName(target)

	// Resolve qualified names. This has the side-effect of normalizing any
	// qualified name found.
	var resolved parser.Expr
	var err error
	if resolved, err = s.resolveQNames(target.Expr); err != nil {
		s.pErr = roachpb.NewError(err)
		return s.pErr
	}
	if resolved, s.pErr = s.planner.expandSubqueries(resolved, 1); s.pErr != nil {
		return s.pErr
	}
	var typ parser.Datum
	typ, err = resolved.TypeCheck(s.planner.evalCtx.Args)
	s.pErr = roachpb.NewError(err)
	if s.pErr != nil {
		return s.pErr
	}
	var normalized parser.Expr
	normalized, err = s.planner.parser.NormalizeExpr(s.planner.evalCtx, resolved)
	s.pErr = roachpb.NewError(err)
	if s.pErr != nil {
		return s.pErr
	}
	s.render = append(s.render, normalized)

	if target.As == "" {
		switch t := target.Expr.(type) {
		case *parser.QualifiedName:
			// If the expression is a qualified name, use the column name, not the
			// full qualification as the column name to return.
			outputName = t.Column()
		}
	}
	s.columns = append(s.columns, ResultColumn{Name: outputName, Typ: typ})
	return nil
}

func sameTypeExprs(left, right parser.Expr) (bool, error) {
	dummyLeft, err := left.TypeCheck(nil)
	if err != nil || dummyLeft == parser.DNull {
		return false, err
	}
	dummyRight, err := right.TypeCheck(nil)
	if err != nil || dummyRight == parser.DNull {
		return false, err
	}
	return !dummyLeft.TypeEqual(dummyRight), nil
}

// runFilter runs a filter expression and returs whether the filter passes.
func runFilter(filter parser.Expr, evalCtx parser.EvalContext) (bool, error) {
	if filter == nil {
		return true, nil
	}

	d, err := filter.Eval(evalCtx)
	if err != nil {
		return false, err
	}

	return d != parser.DNull && bool(d.(parser.DBool)), nil
}

func (v *checkAggregateVisitor) Visit(expr parser.Expr, pre bool) (parser.Visitor, parser.Expr) {
	if !pre || v.aggrErr != nil {
		return nil, expr
	}

	switch t := expr.(type) {
	case *parser.FuncExpr:
		if _, ok := aggregates[strings.ToLower(string(t.Name.Base))]; ok {
			return nil, expr
		}
	case *qvalue:
		if _, ok := v.groupStrs[t.String()]; ok {
			return nil, expr
		}
		v.aggrErr = fmt.Errorf("column \"%s\" must appear in the GROUP BY clause or be used in an aggregate function", t.col.Name)
		return v, expr
	}

	if _, ok := v.groupStrs[expr.String()]; ok {
		return nil, expr
	}
	return v, expr
}

func (n *scanNode) addRender(target parser.SelectExpr) *roachpb.Error {
	// When generating an output column name it should exactly match the original
	// expression, so determine the output column name before we perform any
	// manipulations to the expression (such as star expansion).
	var outputName string
	if target.As != "" {
		outputName = string(target.As)
	} else {
		outputName = target.Expr.String()
	}

	// If a QualifiedName has a StarIndirection suffix we need to match the
	// prefix of the qualified name to one of the tables in the query and
	// then expand the "*" into a list of columns.
	if qname, ok := target.Expr.(*parser.QualifiedName); ok {
		if n.pErr = roachpb.NewError(qname.NormalizeColumnName()); n.pErr != nil {
			return n.pErr
		}
		if qname.IsStar() {
			if n.desc == nil {
				return roachpb.NewUErrorf("\"%s\" with no tables specified is not valid", qname)
			}
			if target.As != "" {
				return roachpb.NewUErrorf("\"%s\" cannot be aliased", qname)
			}
			tableName := qname.Table()
			if tableName != "" && !equalName(n.desc.Alias, tableName) {
				return roachpb.NewUErrorf("table \"%s\" not found", tableName)
			}

			if n.isSecondaryIndex {
				for _, id := range n.index.ColumnIDs {
					var col *ColumnDescriptor
					if col, n.pErr = n.desc.FindColumnByID(id); n.pErr != nil {
						return n.pErr
					}
					qval := n.getQVal(*col)
					n.columns = append(n.columns, resultColumn{name: col.Name, typ: qval.datum})
					n.render = append(n.render, qval)
				}
			} else {
				for _, col := range n.desc.VisibleColumns() {
					qval := n.getQVal(col)
					n.columns = append(n.columns, resultColumn{name: col.Name, typ: qval.datum})
					n.render = append(n.render, qval)
				}
			}
			return nil
		}
	}

	// Resolve qualified names. This has the side-effect of normalizing any
	// qualified name found.
	var resolved parser.Expr
	if resolved, n.pErr = n.resolveQNames(target.Expr); n.pErr != nil {
		return n.pErr
	}
	if resolved, n.pErr = n.planner.expandSubqueries(resolved, 1); n.pErr != nil {
		return n.pErr
	}
	var typ parser.Datum
	var err error
	typ, err = resolved.TypeCheck(n.planner.evalCtx.Args)
	n.pErr = roachpb.NewError(err)
	if n.pErr != nil {
		return n.pErr
	}
	var normalized parser.Expr
	normalized, err = n.planner.parser.NormalizeExpr(n.planner.evalCtx, resolved)
	n.pErr = roachpb.NewError(err)
	if n.pErr != nil {
		return n.pErr
	}
	n.render = append(n.render, normalized)

	if target.As == "" {
		switch t := target.Expr.(type) {
		case *parser.QualifiedName:
			// If the expression is a qualified name, use the column name, not the
			// full qualification as the column name to return.
			outputName = t.Column()
		}
	}
	n.columns = append(n.columns, resultColumn{name: outputName, typ: typ})
	return nil
}

// splitBoolExpr splits a boolean expression E into two boolean expressions RES and REM such that:
//
//  - RES only has variables known to the conversion function (it is "restricted" to a particular
//    set of variables)
//
//  - If weaker is true, for any setting of variables x:
//       E(x) = (RES(x) AND REM(x))
//    This implies RES(x) <= E(x), i.e. RES is "weaker"
//
//  - If weaker is false:
//       E(x) = (RES(x) OR REM(x))
//    This implies RES(x) => E(x), i.e. RES is "stronger"
//
// Note: the original expression is modified in-place and should not be used again.
func splitBoolExpr(expr parser.Expr, conv varConvertFunc, weaker bool) (restricted, remainder parser.Expr) {
	// If the expression only contains "restricted" vars, the split is trivial.
	if exprCheckVars(expr, conv) {
		// An "empty" filter is always true in the weaker (normal) case (where the filter is
		// equivalent to RES AND REM) and always false in the stronger (inverted) case (where the
		// filter is equivalent to RES OR REM).
		return exprConvertVars(expr, conv), parser.DBool(weaker)
	}

	switch t := expr.(type) {
	case *parser.AndExpr:
		if weaker {
			// In the weaker (normal) case, we have
			//   E = (leftRes AND leftRem) AND (rightRes AND rightRem)
			// We can just rearrange:
			//   E = (leftRes AND rightRes) AND (leftRem AND rightRem)
			leftRes, leftRem := splitBoolExpr(t.Left, conv, weaker)
			rightRes, rightRem := splitBoolExpr(t.Right, conv, weaker)
			return makeAnd(leftRes, rightRes), makeAnd(leftRem, rightRem)
		}

		// In the stronger (inverted) case, we have
		//   E = (leftRes OR leftRem) AND (rightRes OR rightRem)
		// We can't do more than:
		//   E = (leftRes AND rightRes) OR E
		exprCopy := expr.DeepCopy()
		leftRes, _ := splitBoolExpr(t.Left, conv, weaker)
		rightRes, _ := splitBoolExpr(t.Right, conv, weaker)
		return makeAnd(leftRes, rightRes), exprCopy

	case *parser.OrExpr:
		if !weaker {
			// In the stronger (inverted) case, we have
			//   E = (leftRes OR leftRem) OR (rightRes AND rightRem)
			// We can just rearrange:
			//   E = (leftRes OR rightRes) OR (leftRem AND rightRem)
			leftRes, leftRem := splitBoolExpr(t.Left, conv, weaker)
			rightRes, rightRem := splitBoolExpr(t.Right, conv, weaker)
			return makeOr(leftRes, rightRes), makeOr(leftRem, rightRem)
		}

		// In the weaker (normal) case, we have
		//   E = (leftRes AND leftRem) OR (rightRes AND rightRem)
		// We can't do more than:
		//   E = (leftRes OR rightRes) OR E
		exprCopy := expr.DeepCopy()
		leftRes, _ := splitBoolExpr(t.Left, conv, weaker)
		rightRes, _ := splitBoolExpr(t.Right, conv, weaker)
		return makeOr(leftRes, rightRes), exprCopy

	case *parser.ParenExpr:
		return splitBoolExpr(t.Expr, conv, weaker)

	case *parser.NotExpr:
		exprRes, exprRem := splitBoolExpr(t.Expr, conv, !weaker)
		return makeNot(exprRes), makeNot(exprRem)

	default:
		// We can't split off anything (we already handled the case when expr contains only
		// restricted vars above).
		// For why we return DBool(weaker), see the comment above on "empty" filters.
		return parser.DBool(weaker), expr
	}
}