Repository: vitessio/vitess
Pull request #9443 (2021-12-26 20:24:05)

Automatically minimize failing queries
## Description

Adds test minimizer functionality. This is a technique borrowed from Haskells QuickCheck - for a given failing query, we want to simplify the query to the bare essentials that still produce the same error. 
The idea is to use this infrastructure either in conjunction with fuzzing, or when a bug is reported, we can use this infrastructure to minimize the query that fails.

This PR adds a test method that can be used when planner bugs are reported: `TestSimplifyBuggyQuery`
It also hooks up the evalengine fuzzer to the minimizer, so if the fuzzer finds problems, we should get a simpler expression to work on.


Patch:
diff --git a/go/vt/sqlparser/rewriter_api.go b/go/vt/sqlparser/rewriter_api.go
index a1de8a8d53..7398b4739e 100644
--- a/go/vt/sqlparser/rewriter_api.go
+++ b/go/vt/sqlparser/rewriter_api.go
@@ -90,6 +90,15 @@ func (c *Cursor) Replace(newNode SQLNode) {
 	c.node = newNode
 }
 
+// ReplacerF returns a replace func that will work even when the cursor has moved to a different node.
+func (c *Cursor) ReplacerF() func(newNode SQLNode) {
+	replacer := c.replacer
+	parent := c.parent
+	return func(newNode SQLNode) {
+		replacer(newNode, parent)
+	}
+}
+
 // ReplaceAndRevisit replaces the current node in the parent field with this new object.
 // When used, this will abort the visitation of the current node - no post or children visited,
 // and the new node visited.
diff --git a/go/vt/vtgate/planbuilder/abstract/join.go b/go/vt/vtgate/planbuilder/abstract/join.go
index c8a802a7be..2946d1c9de 100644
--- a/go/vt/vtgate/planbuilder/abstract/join.go
+++ b/go/vt/vtgate/planbuilder/abstract/join.go
@@ -45,8 +45,8 @@ func (j *Join) PushPredicate(expr sqlparser.Expr, semTable *semantics.SemTable)
 		// we are looking for predicates like `tbl.col = <>` or `<> = tbl.col`,
 		// where tbl is on the rhs of the left outer join
 		if cmp, isCmp := expr.(*sqlparser.ComparisonExpr); isCmp && cmp.Operator != sqlparser.NullSafeEqualOp &&
-			sqlparser.IsColName(cmp.Left) && semTable.RecursiveDeps(cmp.Left).IsSolvedBy(j.RHS.TableID()) ||
-			sqlparser.IsColName(cmp.Right) && semTable.RecursiveDeps(cmp.Right).IsSolvedBy(j.RHS.TableID()) {
+			(sqlparser.IsColName(cmp.Left) && semTable.RecursiveDeps(cmp.Left).IsSolvedBy(j.RHS.TableID()) ||
+				sqlparser.IsColName(cmp.Right) && semTable.RecursiveDeps(cmp.Right).IsSolvedBy(j.RHS.TableID())) {
 			// When the predicate we are pushing is using information from an outer table, we can
 			// check whether the predicate is "null-intolerant" or not. Null-intolerant in this context means that
 			// the predicate will not return true if the table columns are null.
diff --git a/go/vt/vtgate/simplifier/expression_simplifier.go b/go/vt/vtgate/simplifier/expression_simplifier.go
new file mode 100644
index 0000000000..f132a66b06
--- /dev/null
+++ b/go/vt/vtgate/simplifier/expression_simplifier.go
@@ -0,0 +1,209 @@
+/*
+Copyright 2021 The Vitess Authors.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+*/
+
+package simplifier
+
+import (
+	"fmt"
+	"strconv"
+
+	"vitess.io/vitess/go/vt/log"
+	"vitess.io/vitess/go/vt/sqlparser"
+)
+
+// CheckF is used to see if the given expression exhibits the sought after issue
+type CheckF = func(sqlparser.Expr) bool
+
+func SimplifyExpr(in sqlparser.Expr, test CheckF) (smallestKnown sqlparser.Expr) {
+	var maxDepth, level int
+	resetTo := func(e sqlparser.Expr) {
+		smallestKnown = e
+		maxDepth = depth(e)
+		level = 0
+	}
+	resetTo(in)
+	for level <= maxDepth {
+		current := sqlparser.CloneExpr(smallestKnown)
+		nodes, replaceF := getNodesAtLevel(current, level)
+		replace := func(e sqlparser.Expr, idx int) {
+			// if we are at the first level, we are replacing the root,
+			// not rewriting something deep in the tree
+			if level == 0 {
+				current = e
+			} else {
+				// replace `node` in current with the simplified expression
+				replaceF[idx](e)
+			}
+		}
+		simplified := false
+		for idx, node := range nodes {
+			// simplify each element and create a new expression with the node replaced by the simplification
+			// this means that we not only need the node, but also a way to replace the node
+			s := &shrinker{orig: node}
+			expr := s.Next()
+			for expr != nil {
+				replace(expr, idx)
+
+				valid := test(current)
+				log.Errorf("test: %t - %s", valid, sqlparser.String(current))
+				if valid {
+					simplified = true
+					break // we will still continue trying to simplify other expressions at this level
+				} else {
+					// undo the change
+					replace(node, idx)
+				}
+				expr = s.Next()
+			}
+		}
+		if simplified {
+			resetTo(current)
+		} else {
+			level++
+		}
+	}
+	return smallestKnown
+}
+
+func getNodesAtLevel(e sqlparser.Expr, level int) (result []sqlparser.Expr, replaceF []func(node sqlparser.SQLNode)) {
+	lvl := 0
+	pre := func(cursor *sqlparser.Cursor) bool {
+
+		if expr, isExpr := cursor.Node().(sqlparser.Expr); level == lvl && isExpr {
+			result = append(result, expr)
+			replaceF = append(replaceF, cursor.ReplacerF())
+		}
+		lvl++
+		return true
+	}
+	post := func(cursor *sqlparser.Cursor) bool {
+		lvl--
+		return true
+	}
+	sqlparser.Rewrite(e, pre, post)
+	return
+}
+
+func depth(e sqlparser.Expr) (depth int) {
+	lvl := 0
+	pre := func(cursor *sqlparser.Cursor) bool {
+		lvl++
+		if lvl > depth {
+			depth = lvl
+		}
+		return true
+	}
+	post := func(cursor *sqlparser.Cursor) bool {
+		lvl--
+		return true
+	}
+	sqlparser.Rewrite(e, pre, post)
+	return
+}
+
+type shrinker struct {
+	orig  sqlparser.Expr
+	queue []sqlparser.Expr
+}
+
+func (s *shrinker) Next() sqlparser.Expr {
+	// first we check if there is already something in the queue.
+	// note that we are doing a nil check and not a length check here.
+	// once something has been added to the queue, we are no longer
+	// going to add expressions to the queue
+	if s.queue != nil {
+		if len(s.queue) == 0 {
+			return nil
+		}
+		nxt := s.queue[0]
+		s.queue = s.queue[1:]
+		return nxt
+	}
+
+	// we have yet to fill the queue. let's try that next
+	added := s.fillQueue()
+	if added {
+		return s.Next()
+	}
+	return nil
+}
+
+func (s *shrinker) fillQueue() bool {
+	switch e := s.orig.(type) {
+	case *sqlparser.ComparisonExpr:
+		s.queue = append(s.queue, e.Left, e.Right)
+	case *sqlparser.BinaryExpr:
+		s.queue = append(s.queue, e.Left, e.Right)
+	case *sqlparser.Literal:
+		switch e.Type {
+		case sqlparser.StrVal:
+			half := len(e.Val) / 2
+			if half >= 1 {
+				s.queue = append(s.queue, &sqlparser.Literal{Type: sqlparser.StrVal, Val: e.Val[:half]})
+				s.queue = append(s.queue, &sqlparser.Literal{Type: sqlparser.StrVal, Val: e.Val[half:]})
+			} else {
+				return false
+			}
+		case sqlparser.IntVal:
+			num, err := strconv.ParseInt(e.Val, 0, 64)
+			if err != nil {
+				panic(err)
+			}
+			if num == 0 {
+				// can't simplify this more
+				return false
+			}
+
+			// we'll simplify by halving the current value and decreasing it by one
+			half := num / 2
+			oneLess := num - 1
+			if num < 0 {
+				oneLess = num + 1
+			}
+
+			s.queue = append(s.queue, sqlparser.NewIntLiteral(fmt.Sprintf("%d", half)))
+			if oneLess != half {
+				s.queue = append(s.queue, sqlparser.NewIntLiteral(fmt.Sprintf("%d", oneLess)))
+			}
+		default:
+			panic(fmt.Sprintf("unhandled literal type %v", e.Type))
+		}
+	case sqlparser.ValTuple:
+		// first we'll try the individual elements first
+		for _, v := range e {
+			s.queue = append(s.queue, v)
+		}
+		// then we'll try to use the slice but lacking elements
+		for i := range e {
+			s.queue = append(s.queue, append(e[:i], e[i+1:]...))
+		}
+	case *sqlparser.FuncExpr:
+		for _, ae := range e.Exprs {
+			expr, ok := ae.(*sqlparser.AliasedExpr)
+			if !ok {
+				continue
+			}
+			s.queue = append(s.queue, expr.Expr)
+		}
+		if s.queue == nil {
+			return false
+		}
+	case *sqlparser.ColName:
+		// we can try to replace the column with a literal value
+		s.queue = []sqlparser.Expr{sqlparser.NewIntLiteral("0")}
+	}
+	return false
+}
diff --git a/go/vt/vtgate/simplifier/simplifier.go b/go/vt/vtgate/simplifier/simplifier.go
new file mode 100644
index 0000000000..33d465d6b0
--- /dev/null
+++ b/go/vt/vtgate/simplifier/simplifier.go
@@ -0,0 +1,478 @@
+/*
+Copyright 2021 The Vitess Authors.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+*/
+
+package simplifier
+
+import (
+	"sync"
+
+	"vitess.io/vitess/go/sync2"
+	"vitess.io/vitess/go/vt/log"
+	"vitess.io/vitess/go/vt/sqlparser"
+	"vitess.io/vitess/go/vt/vtgate/semantics"
+)
+
+// SimplifyStatement simplifies the AST of a query. It basically iteratevely prunes leaves of the AST, as long as the pruning
+// continues to return true from the `test` function.
+func SimplifyStatement(
+	in sqlparser.SelectStatement,
+	currentDB string,
+	si semantics.SchemaInformation,
+	testF func(sqlparser.SelectStatement) bool,
+) sqlparser.SelectStatement {
+	var semTable *semantics.SemTable
+	var err error
+	{
+		// Since our semantic analysis changes the AST, we clone it first, so we have a pristine AST to play with
+		clone := sqlparser.CloneSelectStatement(in)
+		semTable, err = semantics.Analyze(clone, currentDB, si)
+		if err != nil {
+			return nil
+		}
+	}
+
+	test := func(s sqlparser.SelectStatement) bool {
+		// Since our semantic analysis changes the AST, we clone it first, so we have a pristine AST to play with
+		return testF(sqlparser.CloneSelectStatement(s))
+	}
+
+	// we start by removing one table at a time, and see if we still have an interesting plan
+	for idx := range semTable.Tables {
+		clone := sqlparser.CloneSelectStatement(in)
+		if err != nil {
+			panic(err) // this should never happen
+		}
+		searchedTS := semantics.SingleTableSet(idx)
+		simplified := removeTable(clone, searchedTS, semTable)
+		if simplified && test(clone) {
+			name, _ := semTable.Tables[idx].Name()
+			log.Errorf("removed table %s", name)
+			return SimplifyStatement(clone, currentDB, si, test)
+		}
+	}
+
+	// now let's try to simplify * expressions
+	if simplifyStarExpr(in, test) {
+		return SimplifyStatement(in, currentDB, si, test)
+	}
+
+	// if we get here, we couldn't find a simpler query by just removing one table,
+	// we try to remove select expressions next
+	ch := make(chan expressionCursor)
+	findExpressions(in, ch)
+	for cursor := range ch {
+		// first - let's try to remove the expression
+		if cursor.remove() {
+			if test(in) {
+				log.Errorf("removed expression: %s", sqlparser.String(cursor.expr))
+				cursor.abort()
+				return SimplifyStatement(in, currentDB, si, test)
+			}
+			cursor.restore()
+		}
+
+		// ok, we seem to need this expression. let's see if we can find a simpler version
+		s := &shrinker{orig: cursor.expr}
+		newExpr := s.Next()
+		for newExpr != nil {
+			cursor.replace(newExpr)
+			if test(in) {
+				log.Errorf("simplified expression: %s -> %s", sqlparser.String(cursor.expr), sqlparser.String(newExpr))
+				cursor.abort()
+				return SimplifyStatement(in, currentDB, si, test)
+			}
+			newExpr = s.Next()
+		}
+		// if we get here, we failed to simplify this expression,
+		// so we put back in the original expression
+		cursor.restore()
+		cursor.wg.Done()
+	}
+
+	return in
+}
+
+func simplifyStarExpr(in sqlparser.SelectStatement, test func(sqlparser.SelectStatement) bool) bool {
+	simplified := false
+	sqlparser.Rewrite(in, func(cursor *sqlparser.Cursor) bool {
+		se, ok := cursor.Node().(*sqlparser.StarExpr)
+		if !ok {
+			return true
+		}
+		cursor.Replace(&sqlparser.AliasedExpr{
+			Expr: sqlparser.NewIntLiteral("0"),
+		})
+		if test(in) {
+			log.Errorf("replaced star with literal")
+			simplified = true
+			return false
+		}
+		cursor.Replace(se)
+
+		return true
+	}, nil)
+	return simplified
+}
+
+// removeTable removes the table with the given index from the select statement, which includes the FROM clause
+// but also all expressions and predicates that depend on the table
+func removeTable(clone sqlparser.SelectStatement, searchedTS semantics.TableSet, inner *semantics.SemTable) bool {
+	simplified := false
+	shouldKeepExpr := func(expr sqlparser.Expr) bool {
+		return !inner.RecursiveDeps(expr).IsOverlapping(searchedTS) || sqlparser.ContainsAggregation(expr)
+	}
+	sqlparser.Rewrite(clone, func(cursor *sqlparser.Cursor) bool {
+		switch node := cursor.Node().(type) {
+		case *sqlparser.JoinTableExpr:
+			lft, ok := node.LeftExpr.(*sqlparser.AliasedTableExpr)
+			if ok {
+				ts := inner.TableSetFor(lft)
+				if ts == searchedTS {
+					cursor.Replace(node.RightExpr)
+					simplified = true
+				}
+			}
+			rgt, ok := node.RightExpr.(*sqlparser.AliasedTableExpr)
+			if ok {
+				ts := inner.TableSetFor(rgt)
+				if ts == searchedTS {
+					cursor.Replace(node.LeftExpr)
+					simplified = true
+				}
+			}
+		case *sqlparser.Select:
+			if len(node.From) == 1 {
+				return true
+			}
+			for i, tbl := range node.From {
+				lft, ok := tbl.(*sqlparser.AliasedTableExpr)
+				if ok {
+					ts := inner.TableSetFor(lft)
+					if ts == searchedTS {
+						node.From = append(node.From[:i], node.From[i+1:]...)
+						simplified = true
+						return true
+					}
+				}
+			}
+		case *sqlparser.Where:
+			exprs := sqlparser.SplitAndExpression(nil, node.Expr)
+			var newPredicate sqlparser.Expr
+			for _, expr := range exprs {
+				if !inner.RecursiveDeps(expr).IsOverlapping(searchedTS) {
+					newPredicate = sqlparser.AndExpressions(newPredicate, expr)
+				}
+			}
+			node.Expr = newPredicate
+		case sqlparser.SelectExprs:
+			_, isSel := cursor.Parent().(*sqlparser.Select)
+			if !isSel {
+				return true
+			}
+
+			var newExprs sqlparser.SelectExprs
+			for _, ae := range node {
+				expr, ok := ae.(*sqlparser.AliasedExpr)
+				if !ok {
+					newExprs = append(newExprs, ae)
+					continue
+				}
+				if shouldKeepExpr(expr.Expr) {
+					newExprs = append(newExprs, ae)
+				}
+			}
+			cursor.Replace(newExprs)
+		case sqlparser.GroupBy:
+			var newExprs sqlparser.GroupBy
+			for _, expr := range node {
+				if shouldKeepExpr(expr) {
+					newExprs = append(newExprs, expr)
+				}
+			}
+			cursor.Replace(newExprs)
+		case sqlparser.OrderBy:
+			var newExprs sqlparser.OrderBy
+			for _, expr := range node {
+				if shouldKeepExpr(expr.Expr) {
+					newExprs = append(newExprs, expr)
+				}
+			}
+
+			cursor.Replace(newExprs)
+		}
+		return true
+	}, nil)
+	return simplified
+}
+
+type expressionCursor struct {
+	expr        sqlparser.Expr
+	replace     func(replaceWith sqlparser.Expr)
+	remove      func() bool
+	restore     func()
+	wg          *sync.WaitGroup
+	abortMarker *sync2.AtomicBool
+}
+
+func (i expressionCursor) abort() {
+	i.abortMarker.Set(true)
+}
+
+func newCursorItem(
+	ch chan<- expressionCursor,
+	expr sqlparser.Expr,
+	abort *sync2.AtomicBool,
+	replace func(replaceWith sqlparser.Expr),
+	remove func() bool,
+	restore func(),
+) {
+	wg := &sync.WaitGroup{}
+	wg.Add(1)
+	ch <- expressionCursor{
+		expr:        expr,
+		replace:     replace,
+		remove:      remove,
+		restore:     restore,
+		wg:          wg,
+		abortMarker: abort,
+	}
+	wg.Wait()
+}
+
+func findExpressions(clone sqlparser.SelectStatement, ch chan<- expressionCursor) {
+	abort := &sync2.AtomicBool{}
+	go func() {
+		sqlparser.Rewrite(clone, func(cursor *sqlparser.Cursor) bool {
+			switch node := cursor.Node().(type) {
+			case sqlparser.SelectExprs:
+				_, isSel := cursor.Parent().(*sqlparser.Select)
+				if !isSel {
+					return true
+				}
+				for idx := 0; idx < len(node); idx++ {
+					ae := node[idx]
+					expr, ok := ae.(*sqlparser.AliasedExpr)
+					if !ok {
+						continue
+					}
+					removed := false
+					original := sqlparser.CloneExpr(expr.Expr)
+					newCursorItem(
+						ch, expr.Expr, abort,
+						/*replace*/ func(replaceWith sqlparser.Expr) {
+							if removed {
+								panic("cant replace after remove without restore")
+							}
+							expr.Expr = replaceWith
+						},
+						/*remove*/ func() bool {
+							if removed {
+								panic("can't remove twice, silly")
+							}
+							if len(node) == 1 {
+								// can't remove the last expressions - we'd end up with an empty SELECT clause
+								return false
+							}
+							withoutElement := append(node[:idx], node[idx+1:]...)
+							cursor.Replace(withoutElement)
+							node = withoutElement
+							removed = true
+							return true
+						},
+						/*restore*/ func() {
+							if removed {
+								front := make(sqlparser.SelectExprs, idx)
+								copy(front, node[:idx])
+								back := make(sqlparser.SelectExprs, len(node)-idx)
+								copy(back, node[idx:])
+								frontWithRestoredExpr := append(front, ae)
+								node = append(frontWithRestoredExpr, back...)
+								cursor.Replace(node)
+								removed = false
+								return
+							}
+							expr.Expr = original
+						},
+					)
+					if abort.Get() {
+						close(ch)
+						return false
+					}
+				}
+			case *sqlparser.Where:
+				exprs := sqlparser.SplitAndExpression(nil, node.Expr)
+				set := func(input []sqlparser.Expr) {
+					node.Expr = sqlparser.AndExpressions(input...)
+					exprs = input
+				}
+				if !visitExpressions(exprs, set, ch, abort) {
+					return false
+				}
+			case *sqlparser.JoinTableExpr:
+
+			case *sqlparser.JoinCondition:
+				join, ok := cursor.Parent().(*sqlparser.JoinTableExpr)
+				if !ok {
+					return true
+				}
+				if join.Join != sqlparser.NormalJoinType || node.Using != nil {
+					return false
+				}
+				exprs := sqlparser.SplitAndExpression(nil, node.On)
+				set := func(input []sqlparser.Expr) {
+					node.On = sqlparser.AndExpressions(input...)
+					exprs = input
+				}
+				if !visitExpressions(exprs, set, ch, abort) {
+					return false
+				}
+			case sqlparser.GroupBy:
+				set := func(input []sqlparser.Expr) {
+					node = input
+					cursor.Replace(node)
+				}
+				if !visitExpressions(node, set, ch, abort) {
+					return false
+				}
+			case sqlparser.OrderBy:
+				for idx := 0; idx < len(node); idx++ {
+					order := node[idx]
+					removed := false
+					original := sqlparser.CloneExpr(order.Expr)
+					newCursorItem(
+						ch, order.Expr, abort,
+						/*replace*/ func(replaceWith sqlparser.Expr) {
+							if removed {
+								panic("cant replace after remove without restore")
+							}
+							order.Expr = replaceWith
+						},
+						/*remove*/ func() bool {
+							if removed {
+								panic("can't remove twice, silly")
+							}
+							withoutElement := append(node[:idx], node[idx+1:]...)
+							cursor.Replace(withoutElement)
+							node = withoutElement
+							removed = true
+							return true
+						},
+						/*restore*/ func() {
+							if removed {
+								front := make(sqlparser.OrderBy, idx)
+								copy(front, node[:idx])
+								back := make(sqlparser.OrderBy, len(node)-idx)
+								copy(back, node[idx:])
+								frontWithRestoredExpr := append(front, order)
+								node = append(frontWithRestoredExpr, back...)
+								cursor.Replace(node)
+								removed = false
+								return
+							}
+							order.Expr = original
+						},
+					)
+					if abort.Get() {
+						close(ch)
+						return false
+					}
+				}
+			case *sqlparser.Limit:
+				if node.Offset != nil {
+					original := node.Offset
+					newCursorItem(ch, node.Offset, abort,
+						/*replace*/ func(replaceWith sqlparser.Expr) {
+							node.Offset = replaceWith
+						},
+						/*remove*/ func() bool {
+							node.Offset = nil
+							return true
+						},
+						/*restore*/ func() {
+							node.Offset = original
+						})
+				}
+				if node.Rowcount != nil {
+					original := node.Rowcount
+					newCursorItem(ch, node.Rowcount, abort,
+						/*replace*/ func(replaceWith sqlparser.Expr) {
+							node.Rowcount = replaceWith
+						},
+						/*remove*/ func() bool {
+							// removing Rowcount is an invalid op
+							return false
+						},
+						/*restore*/ func() {
+							node.Rowcount = original
+						})
+				}
+
+			}
+			return true
+		}, nil)
+		close(ch)
+	}()
+}
+
+// visitExpressions allows the cursor to visit all expressions in a slice,
+// and can replace or remove items and restore the slice.
+func visitExpressions(
+	exprs []sqlparser.Expr,
+	set func(input []sqlparser.Expr),
+	ch chan<- expressionCursor,
+	abort *sync2.AtomicBool,
+) bool {
+	for idx := 0; idx < len(exprs); idx++ {
+		expr := exprs[idx]
+		removed := false
+		newCursorItem(ch, expr, abort,
+			func(replaceWith sqlparser.Expr) {
+				if removed {
+					panic("cant replace after remove without restore")
+				}
+				exprs[idx] = replaceWith
+				set(exprs)
+			},
+			/*remove*/ func() bool {
+				if removed {
+					panic("can't remove twice, silly")
+				}
+				exprs = append(exprs[:idx], exprs[idx+1:]...)
+				set(exprs)
+				removed = true
+				return true
+			},
+			/*restore*/ func() {
+				if removed {
+					front := make([]sqlparser.Expr, idx)
+					copy(front, exprs[:idx])
+					back := make([]sqlparser.Expr, len(exprs)-idx)
+					copy(back, exprs[idx:])
+					frontWithRestoredExpr := append(front, expr)
+					exprs = append(frontWithRestoredExpr, back...)
+					set(exprs)
+					removed = false
+					return
+				}
+				exprs[idx] = expr
+				set(exprs)
+			})
+		if abort.Get() {
+			return false
+		}
+	}
+	return true
+}


Test patch:
diff --git a/go/vt/vtgate/evalengine/integration/fuzz_test.go b/go/vt/vtgate/evalengine/integration/fuzz_test.go
index 8f23ba5dbb..63fe211737 100644
--- a/go/vt/vtgate/evalengine/integration/fuzz_test.go
+++ b/go/vt/vtgate/evalengine/integration/fuzz_test.go
@@ -27,7 +27,12 @@ import (
 	"testing"
 	"time"
 
+	"vitess.io/vitess/go/vt/vtgate/simplifier"
+
+	"github.com/stretchr/testify/require"
+
 	"vitess.io/vitess/go/mysql/collations"
+	"vitess.io/vitess/go/vt/log"
 	"vitess.io/vitess/go/vt/sqlparser"
 	"vitess.io/vitess/go/vt/vtgate/evalengine"
 )
@@ -173,6 +178,9 @@ func safeEvaluate(query string) (evalengine.EvalResult, bool, error) {
 	return eval, evaluated, err
 }
 
+const syntaxErr = `You have an error in your SQL syntax; (errno 1064) (sqlstate 42000) during query: SQL`
+const localSyntaxErr = `You have an error in your SQL syntax;`
+
 func TestGenerateFuzzCases(t *testing.T) {
 	if *fuzzMaxFailures <= 0 {
 		t.Skipf("skipping fuzz test generation")
@@ -201,55 +209,72 @@ func TestGenerateFuzzCases(t *testing.T) {
 	var conn = mysqlconn(t)
 	defer conn.Close()
 
-nextCase:
-	for len(golden) < *fuzzMaxFailures {
-		query := "SELECT " + gen.expr()
+	bothReturnSameResult := func(expr sqlparser.Expr) comparisonResult {
+		query := "SELECT " + sqlparser.String(expr)
 
 		eval, evaluated, localErr := safeEvaluate(query)
 		remote, remoteErr := conn.ExecuteFetch(query, 1, false)
 
-		if localErr != nil {
-			if remoteErr == nil {
-				t.Errorf("local query %q failed: %v (eval=%v); mysql response: %s", query, localErr, evaluated, remote.Rows[0][0].String())
-				goto failed
-			}
-			if !errorsMatch(remoteErr, localErr) {
-				t.Errorf("mismatch in errors for %q: local=%q (eval=%v), remote=%q", query, localErr.Error(), evaluated, remoteErr.Error())
-				goto failed
-			}
-			continue
+		if localErr != nil && strings.Contains(localErr.Error(), "syntax error at position") {
+			localErr = fmt.Errorf(localSyntaxErr)
 		}
 
-		if remoteErr != nil {
-			for _, ke := range knownErrors {
-				if ke.MatchString(remoteErr.Error()) {
-					continue nextCase
-				}
-			}
-			t.Errorf("remote query %q failed: %v, local=%s", query, remoteErr.Error(), eval.Value().String())
-			goto failed
+		if remoteErr != nil && strings.Contains(remoteErr.Error(), "You have an error in your SQL syntax") {
+			remoteErr = fmt.Errorf(syntaxErr)
 		}
 
-		if eval.Value().String() != remote.Rows[0][0].String() {
-			t.Errorf("mismatch for query %q: local=%v, remote=%v", query, eval.Value().String(), remote.Rows[0][0].String())
-			goto failed
+		res := comparisonResult{
+			localErr:  localErr,
+			remoteErr: remoteErr,
+			evaluated: evaluated,
 		}
 
-		// OK -- all match
-		continue
+		if evaluated {
+			res.localVal = eval.Value().String()
+		}
 
-	failed:
-		if remoteErr != nil {
-			golden = append(golden, evaltest{
-				Query: query,
-				Error: remoteErr.Error(),
-			})
-		} else {
-			golden = append(golden, evaltest{
-				Query: query,
-				Value: remote.Rows[0][0].String(),
-			})
+		if remoteErr == nil {
+			res.remoteVal = remote.Rows[0][0].String()
 		}
+
+		return res
+	}
+
+	for len(golden) < *fuzzMaxFailures {
+		query := "SELECT " + gen.expr()
+		stmt, err := sqlparser.Parse(query)
+		require.NoError(t, err)
+		t.Run(query, func(t *testing.T) {
+			astExpr := stmt.(*sqlparser.Select).SelectExprs[0].(*sqlparser.AliasedExpr).Expr
+
+			resultCmp := bothReturnSameResult(astExpr)
+			diff := resultCmp.diff()
+			if diff == "" {
+				return
+			}
+
+			log.Infof("found inconsistency - will try to simplify: %s", query)
+
+			astExpr = simplifier.SimplifyExpr(astExpr, func(expr sqlparser.Expr) bool {
+				return bothReturnSameResult(expr).diff() == diff
+			})
+
+			query = "SELECT " + sqlparser.String(astExpr)
+
+			log.Infof("simplified to: %s", query)
+			t.Errorf("%s", diff)
+			if resultCmp.remoteErr != nil {
+				golden = append(golden, evaltest{
+					Query: query,
+					Error: resultCmp.remoteErr.Error(),
+				})
+			} else {
+				golden = append(golden, evaltest{
+					Query: query,
+					Value: resultCmp.remoteVal,
+				})
+			}
+		})
 	}
 
 	out, err := os.Create(fmt.Sprintf("testdata/mysql_golden_%d.json", time.Now().Unix()))
@@ -262,3 +287,36 @@ nextCase:
 	enc.SetIndent("", "    ")
 	enc.Encode(golden)
 }
+
+type comparisonResult struct {
+	localErr, remoteErr error
+	localVal, remoteVal string
+	evaluated           bool
+}
+
+func (cr comparisonResult) diff() string {
+	if cr.localErr != nil {
+		if cr.remoteErr == nil {
+			return fmt.Sprintf("%v (eval=%v); mysql response: %s", cr.localErr, cr.evaluated, cr.remoteVal)
+		}
+		if !errorsMatch(cr.remoteErr, cr.localErr) {
+			return fmt.Sprintf("mismatch in errors: eval=%s; mysql response: %s", cr.localErr.Error(), cr.remoteErr.Error())
+		}
+		return ""
+	}
+
+	if cr.remoteErr != nil {
+		for _, ke := range knownErrors {
+			if ke.MatchString(cr.remoteErr.Error()) {
+				return ""
+			}
+		}
+		return fmt.Sprintf("%v (eval=%v); mysql failed with: %s", cr.localVal, cr.evaluated, cr.remoteErr.Error())
+	}
+
+	if cr.localVal != cr.remoteVal {
+		return fmt.Sprintf("different results:%s (eval=%v); mysql response: %s", cr.localVal, cr.evaluated, cr.remoteVal)
+	}
+
+	return ""
+}
diff --git a/go/vt/vtgate/planbuilder/simplifier_test.go b/go/vt/vtgate/planbuilder/simplifier_test.go
new file mode 100644
index 0000000000..1fdda8df57
--- /dev/null
+++ b/go/vt/vtgate/planbuilder/simplifier_test.go
@@ -0,0 +1,123 @@
+/*
+Copyright 2021 The Vitess Authors.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+*/
+
+package planbuilder
+
+import (
+	"fmt"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+
+	"vitess.io/vitess/go/vt/vtgate/simplifier"
+
+	"vitess.io/vitess/go/vt/log"
+	"vitess.io/vitess/go/vt/vterrors"
+
+	"github.com/stretchr/testify/require"
+
+	"vitess.io/vitess/go/vt/sqlparser"
+)
+
+// TestSimplifyBuggyQuery should be used to whenever we get a planner bug reported
+// It will try to minimize the query to make it easier to understand and work with the bug.
+func TestSimplifyBuggyQuery(t *testing.T) {
+	query := "select user.id, user.name, count(*), unsharded.name from user join unsharded where unsharded.id = 42"
+	vschema := &vschemaWrapper{
+		v:       loadSchema(t, "schema_test.json", true),
+		version: Gen4,
+	}
+	stmt, reserved, err := sqlparser.Parse2(query)
+	require.NoError(t, err)
+	rewritten, _ := sqlparser.RewriteAST(stmt, vschema.currentDb(), sqlparser.SQLSelectLimitUnset)
+	vschema.currentDb()
+
+	reservedVars := sqlparser.NewReservedVars("vtg", reserved)
+	ast := rewritten.AST
+	_, err = BuildFromStmt(query, ast, reservedVars, vschema, rewritten.BindVarNeeds, true, true)
+	require.Error(t, err)
+
+	simplified := simplifier.SimplifyStatement(
+		ast.(sqlparser.SelectStatement),
+		vschema.currentDb(),
+		vschema,
+		keepSameError(query, reservedVars, vschema, rewritten.BindVarNeeds, err),
+	)
+
+	fmt.Println(sqlparser.String(simplified))
+}
+
+func TestUnsupportedFile(t *testing.T) {
+	t.Skip("run manually to see if any queries can be simplified")
+	vschema := &vschemaWrapper{
+		v:       loadSchema(t, "schema_test.json", true),
+		version: Gen4,
+	}
+	fmt.Println(vschema)
+	for tcase := range iterateExecFile("unsupported_cases.txt") {
+		t.Run(fmt.Sprintf("%d:%s", tcase.lineno, tcase.input), func(t *testing.T) {
+			log.Errorf("%s:%d - %s", tcase.file, tcase.lineno, tcase.input)
+			stmt, reserved, err := sqlparser.Parse2(tcase.input)
+			require.NoError(t, err)
+			_, ok := stmt.(sqlparser.SelectStatement)
+			if !ok {
+				t.Skip()
+				return
+			}
+			rewritten, err := sqlparser.RewriteAST(stmt, vschema.currentDb(), sqlparser.SQLSelectLimitUnset)
+			if err != nil {
+				t.Skip()
+			}
+			vschema.currentDb()
+
+			reservedVars := sqlparser.NewReservedVars("vtg", reserved)
+			ast := rewritten.AST
+			origQuery := sqlparser.String(ast)
+			_, err = BuildFromStmt(origQuery, ast, reservedVars, vschema, rewritten.BindVarNeeds, true, true)
+
+			stmt, _, _ = sqlparser.Parse2(tcase.input)
+			simplified := simplifier.SimplifyStatement(
+				stmt.(sqlparser.SelectStatement),
+				vschema.currentDb(),
+				vschema,
+				keepSameError(tcase.input, reservedVars, vschema, rewritten.BindVarNeeds, err),
+			)
+
+			if simplified == nil {
+				t.Skip()
+			}
+
+			simpleQuery := sqlparser.String(simplified)
+			fmt.Println(simpleQuery)
+
+			assert.Equal(t, origQuery, simpleQuery)
+		})
+	}
+}
+
+func keepSameError(query string, reservedVars *sqlparser.ReservedVars, vschema *vschemaWrapper, needs *sqlparser.BindVarNeeds, expected error) func(statement sqlparser.SelectStatement) bool {
+	return func(statement sqlparser.SelectStatement) bool {
+		_, myErr := BuildFromStmt(query, statement, reservedVars, vschema, needs, true, true)
+		if myErr == nil {
+			return false
+		}
+		state := vterrors.ErrState(expected)
+		if state == vterrors.Undefined {
+			return expected.Error() == myErr.Error()
+		}
+		return vterrors.ErrState(myErr) == state
+	}
+}
diff --git a/go/vt/vtgate/planbuilder/testdata/filter_cases.txt b/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
index d6fb3d6692..b755cccd15 100644
--- a/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
@@ -3270,6 +3270,11 @@ Gen4 plan same as above
   }
 }
 
+# this query lead to a nil pointer error
+"select user.id from user left join user_extra on user.col = user_extra.col where foo(user_extra.foobar)"
+"unsupported: cross-shard left join and where clause"
+Gen4 plan same as above
+
 #subquery on other table
 "select distinct user.id, user.col from user where user.col in (select id from music where col2 = 'a')"
 {
diff --git a/go/vt/vtgate/planbuilder/testdata/unsupported_cases.txt b/go/vt/vtgate/planbuilder/testdata/unsupported_cases.txt
index 685e32b747..cc89053893 100644
--- a/go/vt/vtgate/planbuilder/testdata/unsupported_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/unsupported_cases.txt
@@ -59,7 +59,7 @@ Gen4 plan same as above
 Gen4 plan same as above
 
 # left join with expressions
-"select user.id, user_extra.col+1 from user left join user_extra on user.col = user_extra.col"
+"select user_extra.col+1 from user left join user_extra on user.col = user_extra.col"
 "unsupported: cross-shard left join and column expressions"
 Gen4 plan same as above
 
diff --git a/go/vt/vtgate/simplifier/simplifier_test.go b/go/vt/vtgate/simplifier/simplifier_test.go
new file mode 100644
index 0000000000..a3b0286ad1
--- /dev/null
+++ b/go/vt/vtgate/simplifier/simplifier_test.go
@@ -0,0 +1,148 @@
+/*
+Copyright 2021 The Vitess Authors.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+*/
+
+package simplifier
+
+import (
+	"fmt"
+	"testing"
+
+	"vitess.io/vitess/go/vt/log"
+	"vitess.io/vitess/go/vt/vtgate/evalengine"
+
+	"github.com/stretchr/testify/require"
+
+	"vitess.io/vitess/go/vt/sqlparser"
+)
+
+func TestFindAllExpressions(t *testing.T) {
+	query := `
+select 
+	user.selectExpr1, 
+	unsharded.selectExpr2,
+	count(*) as leCount
+from 
+	user join 
+	unsharded on 
+		user.joinCond = unsharded.joinCond 
+where
+	unsharded.wherePred = 42 and
+	wherePred = 'foo' and 
+	user.id = unsharded.id
+group by 
+	user.groupByExpr1 + unsharded.groupByExpr2
+order by 
+	user.orderByExpr1 desc, 
+	unsharded.orderByExpr2 asc
+limit 123 offset 456
+`
+	ast, err := sqlparser.Parse(query)
+	require.NoError(t, err)
+	ch := make(chan expressionCursor)
+	findExpressions(ast.(sqlparser.SelectStatement), ch)
+	for cursor := range ch {
+		exploreExpression(cursor, ast)
+	}
+}
+
+func exploreExpression(cursor expressionCursor, ast sqlparser.Statement) {
+	defer cursor.wg.Done()
+	fmt.Printf(">> found expression: %s\n", sqlparser.String(cursor.expr))
+	cursor.replace(sqlparser.NewIntLiteral("1"))
+	fmt.Printf("remove: %s\n", sqlparser.String(ast))
+	cursor.restore()
+	fmt.Printf("restore: %s\n", sqlparser.String(ast))
+	cursor.remove()
+	fmt.Printf("replace it with literal: %s\n", sqlparser.String(ast))
+	cursor.restore()
+	fmt.Printf("restore: %s\n", sqlparser.String(ast))
+}
+
+func TestAbortExpressionCursor(t *testing.T) {
+	query := "select user.id, count(*), unsharded.name from user join unsharded on 13 = 14 where unsharded.id = 42 and name = 'foo' and user.id = unsharded.id"
+	ast, err := sqlparser.Parse(query)
+	require.NoError(t, err)
+	ch := make(chan expressionCursor)
+	findExpressions(ast.(sqlparser.SelectStatement), ch)
+	for cursor := range ch {
+		fmt.Println(sqlparser.String(cursor.expr))
+		cursor.replace(sqlparser.NewIntLiteral("1"))
+		fmt.Println(sqlparser.String(ast))
+		cursor.replace(cursor.expr)
+		if _, ok := cursor.expr.(*sqlparser.FuncExpr); ok {
+			cursor.abort()
+			break
+		}
+		cursor.wg.Done()
+	}
+}
+
+func TestSimplifyEvalEngineExpr(t *testing.T) {
+	// ast struct for L0         +
+	// L1                +            +
+	// L2             +     +      +     +
+	// L3            1 2   3 4    5 6   7 8
+
+	// L3
+	i1, i2, i3, i4, i5, i6, i7, i8 :=
+		sqlparser.NewIntLiteral("1"),
+		sqlparser.NewIntLiteral("2"),
+		sqlparser.NewIntLiteral("3"),
+		sqlparser.NewIntLiteral("4"),
+		sqlparser.NewIntLiteral("5"),
+		sqlparser.NewIntLiteral("6"),
+		sqlparser.NewIntLiteral("7"),
+		sqlparser.NewIntLiteral("8")
+	// L2
+	p21, p22, p23, p24 :=
+		plus(i1, i2),
+		plus(i3, i4),
+		plus(i5, i6),
+		plus(i7, i8)
+
+	// L1
+	p11, p12 :=
+		plus(p21, p22),
+		plus(p23, p24)
+
+	// L0
+	p0 := plus(p11, p12)
+
+	expr := SimplifyExpr(p0, func(expr sqlparser.Expr) bool {
+		local, err := evalengine.ConvertEx(expr, nil, true)
+		if err != nil {
+			return false
+		}
+		res, err := (*evalengine.ExpressionEnv)(nil).Evaluate(local)
+		if err != nil {
+			return false
+		}
+		toInt64, err := res.Value().ToInt64()
+		if err != nil {
+			return false
+		}
+		return toInt64 >= 8
+	})
+	log.Infof("simplest expr to evaluate to >= 8: [%s], started from: [%s]", sqlparser.String(expr), sqlparser.String(p0))
+}
+
+func plus(a, b sqlparser.Expr) sqlparser.Expr {
+	return &sqlparser.BinaryExpr{
+		Operator: sqlparser.PlusOp,
+		Left:     a,
+		Right:    b,
+	}
+}