Repository: vitessio/vitess
Pull request #7274 (2021-01-09 07:09:42)

Gen4 Planner: AxB vs BxA
This PR teaches the Gen4 planner how to re-evaluate routes after a predicate has been pushed during the join tree comparisons.

### Better plans

I'll use an example to show what the planner does:

```sql
SELECT user.col 
FROM user JOIN user_extra ON user.id = user_extra.col
```

There is a primary vindex on `user.id`, but for `user_extra`, there are no applicable vindexes.
This means first of all that we can't merge the two tables into a single route - for certain `user.id` values, the matching `user_extra.col` might well be placed in a different shard.

So, we are forced to do the join on the vtgate - we can't delegate this to mysql. Now the question is: should we first query the `user` table and push down the `user.id` to the `user_extra` route, or the other way around?

Given the available vindexes, we have to evaluate `user_extra` using a scatter query no matter if we have `user.id` available or not. For the `user` table on the other hand, if we have `user_extra.col` available, we could use a `SelectEqualUnique` which is way better than a scatter query.

### Implementation comments

Because the planner now takes the same predicate (`user.id = user_extra.col`) and rewrites it in two different ways depending on which route is on the LHS, I needed to make it possible to clone expressions. I have hand-written the clone method for expressions, but I think it makes sense to use the visitorgen to generate this code, and do it for all AST structs and not just `Expr`.

I also had to move the pushing of predicates to the joinTree phase instead of waiting until we have logical plans. 

### Planner performance

I was afraid that all this new logic that is being done during joinTree selection would lead to much slower planning, but the benchmarks don't look too scary. 😅 

```
BenchmarkPlanner/from_cases.txt-v3-16       	  	    	    1198	    853119 ns/op	  393968 B/op	    7319 allocs/op
BenchmarkPlanner/from_cases.txt-v4-16         	    		    1436	    796068 ns/op	  366321 B/op	    7553 allocs/op
BenchmarkPlanner/from_cases.txt-v4left2right-16         	    1545	    747779 ns/op	  342363 B/op	    6999 allocs/op
BenchmarkPlanner/filter_cases.txt-v3-16                 	    1544	    763470 ns/op	  340849 B/op	    6820 allocs/op
BenchmarkPlanner/filter_cases.txt-v4-16                 	    1749	    656536 ns/op	  291623 B/op	    5779 allocs/op
BenchmarkPlanner/filter_cases.txt-v4left2right-16       	    1764	    658813 ns/op	  288869 B/op	    5705 allocs/op
BenchmarkPlanner/large_cases.txt-v3-16                  	    8616	    126044 ns/op	   54688 B/op	    1189 allocs/op
BenchmarkPlanner/large_cases.txt-v4-16                  	    6630	    163335 ns/op	   72650 B/op	    1564 allocs/op
BenchmarkPlanner/large_cases.txt-v4left2right-16        	   13299	     88614 ns/op	   41088 B/op	    1003 allocs/op
BenchmarkPlanner/aggr_cases.txt-v3-16                   	    2864	    433544 ns/op	  148570 B/op	    4068 allocs/op
BenchmarkPlanner/aggr_cases.txt-v4-16                   	    3622	    337122 ns/op	  110093 B/op	    3157 allocs/op
BenchmarkPlanner/aggr_cases.txt-v4left2right-16         	    3675	    336505 ns/op	  110174 B/op	    3157 allocs/op
BenchmarkPlanner/select_cases.txt-v3-16                 	    1092	    967935 ns/op	  328761 B/op	    8525 allocs/op
BenchmarkPlanner/select_cases.txt-v4-16                 	    1335	    911256 ns/op	  285991 B/op	    7859 allocs/op
BenchmarkPlanner/select_cases.txt-v4left2right-16       	    1269	    900011 ns/op	  279665 B/op	    7769 allocs/op
BenchmarkPlanner/union_cases.txt-v3-16                  	    1315	    948248 ns/op	  338814 B/op	    9025 allocs/op
BenchmarkPlanner/union_cases.txt-v4-16                  	    1221	    925400 ns/op	  338622 B/op	    9025 allocs/op
BenchmarkPlanner/union_cases.txt-v4left2right-16        	    1280	    899773 ns/op	  338773 B/op	    9025 allocs/op
BenchmarkPlanner/wireup_cases.txt-v3-16                 	   19597	     58601 ns/op	   24786 B/op	     586 allocs/op
BenchmarkPlanner/wireup_cases.txt-v4-16                 	   25574	     45954 ns/op	   18512 B/op	     470 allocs/op
BenchmarkPlanner/wireup_cases.txt-v4left2right-16       	   27835	     42890 ns/op	   15732 B/op	     429 allocs/op
```


Patch:
diff --git a/go/vt/sqlparser/ast.go b/go/vt/sqlparser/ast.go
index 308b7b0751..0b97ad88e6 100644
--- a/go/vt/sqlparser/ast.go
+++ b/go/vt/sqlparser/ast.go
@@ -1474,6 +1474,7 @@ type (
 	Expr interface {
 		iExpr()
 		SQLNode
+		Clone() Expr
 	}
 
 	// AndExpr represents an AND expression.
diff --git a/go/vt/sqlparser/ast_funcs.go b/go/vt/sqlparser/ast_funcs.go
index 40dc63d24b..bdd00bce72 100644
--- a/go/vt/sqlparser/ast_funcs.go
+++ b/go/vt/sqlparser/ast_funcs.go
@@ -1299,3 +1299,315 @@ const (
 	// DoubleAt represnts @@
 	DoubleAt
 )
+
+func nilOrClone(in Expr) Expr {
+	if in == nil {
+		return nil
+	}
+	return in.Clone()
+}
+
+// Clone implements the Expr interface
+func (node *Subquery) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	panic("Subquery cloning not supported")
+}
+
+// Clone implements the Expr interface
+func (node *AndExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &AndExpr{
+		Left:  nilOrClone(node.Left),
+		Right: nilOrClone(node.Right),
+	}
+}
+
+// Clone implements the Expr interface
+func (node *OrExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &OrExpr{
+		Left:  nilOrClone(node.Left),
+		Right: nilOrClone(node.Right),
+	}
+}
+
+// Clone implements the Expr interface
+func (node *XorExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &XorExpr{
+		Left:  nilOrClone(node.Left),
+		Right: nilOrClone(node.Right),
+	}
+}
+
+// Clone implements the Expr interface
+func (node *NotExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &NotExpr{
+		Expr: nilOrClone(node),
+	}
+}
+
+// Clone implements the Expr interface
+func (node *ComparisonExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &ComparisonExpr{
+		Operator: node.Operator,
+		Left:     nilOrClone(node.Left),
+		Right:    nilOrClone(node.Right),
+		Escape:   nilOrClone(node.Escape),
+	}
+}
+
+// Clone implements the Expr interface
+func (node *RangeCond) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &RangeCond{
+		Operator: node.Operator,
+		Left:     nilOrClone(node.Left),
+		From:     nilOrClone(node.From),
+		To:       nilOrClone(node.To),
+	}
+}
+
+// Clone implements the Expr interface
+func (node *IsExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &IsExpr{
+		Operator: node.Operator,
+		Expr:     nilOrClone(node.Expr),
+	}
+}
+
+// Clone implements the Expr interface
+func (node *ExistsExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &ExistsExpr{
+		Subquery: nilOrClone(node.Subquery).(*Subquery),
+	}
+}
+
+// Clone implements the Expr interface
+func (node *Literal) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &Literal{}
+}
+
+// Clone implements the Expr interface
+func (node Argument) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	cpy := make(Argument, len(node))
+	copy(cpy, node)
+	return cpy
+}
+
+// Clone implements the Expr interface
+func (node *NullVal) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &NullVal{}
+}
+
+// Clone implements the Expr interface
+func (node BoolVal) Clone() Expr {
+	return node
+}
+
+// Clone implements the Expr interface
+func (node *ColName) Clone() Expr {
+	return node
+}
+
+// Clone implements the Expr interface
+func (node ValTuple) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	cpy := make(ValTuple, len(node))
+	copy(cpy, node)
+	return cpy
+}
+
+// Clone implements the Expr interface
+func (node ListArg) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	cpy := make(ListArg, len(node))
+	copy(cpy, node)
+	return cpy
+}
+
+// Clone implements the Expr interface
+func (node *BinaryExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &BinaryExpr{
+		Operator: node.Operator,
+		Left:     nilOrClone(node.Left),
+		Right:    nilOrClone(node.Right),
+	}
+}
+
+// Clone implements the Expr interface
+func (node *UnaryExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &UnaryExpr{
+		Operator: node.Operator,
+		Expr:     nilOrClone(node.Expr),
+	}
+}
+
+// Clone implements the Expr interface
+func (node *IntervalExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &IntervalExpr{
+		Expr: nilOrClone(node.Expr),
+		Unit: node.Unit,
+	}
+}
+
+// Clone implements the Expr interface
+func (node *CollateExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &CollateExpr{
+		Expr:    nilOrClone(node.Expr),
+		Charset: node.Charset,
+	}
+}
+
+// Clone implements the Expr interface
+func (node *FuncExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	panic("FuncExpr cloning not supported")
+}
+
+// Clone implements the Expr interface
+func (node *TimestampFuncExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &TimestampFuncExpr{
+		Name:  node.Name,
+		Expr1: nilOrClone(node.Expr1),
+		Expr2: nilOrClone(node.Expr2),
+		Unit:  node.Unit,
+	}
+}
+
+// Clone implements the Expr interface
+func (node *CurTimeFuncExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &CurTimeFuncExpr{
+		Name: node.Name,
+		Fsp:  nilOrClone(node.Fsp),
+	}
+}
+
+// Clone implements the Expr interface
+func (node *CaseExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	panic("CaseExpr cloning not supported")
+}
+
+// Clone implements the Expr interface
+func (node *ValuesFuncExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &ValuesFuncExpr{
+		Name: nilOrClone(node.Name).(*ColName),
+	}
+}
+
+// Clone implements the Expr interface
+func (node *ConvertExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	panic("ConvertExpr cloning not supported")
+}
+
+// Clone implements the Expr interface
+func (node *SubstrExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &SubstrExpr{
+		Name:   node.Name,
+		StrVal: nilOrClone(node.StrVal).(*Literal),
+		From:   nilOrClone(node.From),
+		To:     nilOrClone(node.To),
+	}
+}
+
+// Clone implements the Expr interface
+func (node *ConvertUsingExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &ConvertUsingExpr{
+		Expr: nilOrClone(node.Expr),
+		Type: node.Type,
+	}
+}
+
+// Clone implements the Expr interface
+func (node *MatchExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	panic("MatchExpr cloning not supported")
+}
+
+// Clone implements the Expr interface
+func (node *GroupConcatExpr) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	panic("GroupConcatExpr cloning not supported")
+}
+
+// Clone implements the Expr interface
+func (node *Default) Clone() Expr {
+	if node == nil {
+		return nil
+	}
+	return &Default{ColName: node.ColName}
+}
diff --git a/go/vt/vtgate/planbuilder/jointree_transformers.go b/go/vt/vtgate/planbuilder/jointree_transformers.go
new file mode 100644
index 0000000000..9235eafef2
--- /dev/null
+++ b/go/vt/vtgate/planbuilder/jointree_transformers.go
@@ -0,0 +1,116 @@
+/*
+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 (
+	"sort"
+	"strings"
+
+	vtrpcpb "vitess.io/vitess/go/vt/proto/vtrpc"
+	"vitess.io/vitess/go/vt/sqlparser"
+	"vitess.io/vitess/go/vt/vtgate/engine"
+	"vitess.io/vitess/go/vt/vtgate/semantics"
+	"vitess.io/vitess/go/vt/vtgate/vindexes"
+
+	"vitess.io/vitess/go/vt/vterrors"
+)
+
+func transformToLogicalPlan(tree joinTree, semTable *semantics.SemTable) (logicalPlan, error) {
+	switch n := tree.(type) {
+	case *routePlan:
+		return transformRoutePlan(n)
+
+	case *joinPlan:
+		return transformJoinPlan(n, semTable)
+	}
+
+	return nil, vterrors.Errorf(vtrpcpb.Code_INTERNAL, "BUG: unknown type encountered: %T", tree)
+}
+
+func transformJoinPlan(n *joinPlan, semTable *semantics.SemTable) (logicalPlan, error) {
+	lhs, err := transformToLogicalPlan(n.lhs, semTable)
+	if err != nil {
+		return nil, err
+	}
+	rhs, err := transformToLogicalPlan(n.rhs, semTable)
+	if err != nil {
+		return nil, err
+	}
+	return &joinV4{
+		Left:  lhs,
+		Right: rhs,
+		Cols:  n.columns,
+		Vars:  n.vars,
+	}, nil
+}
+
+func transformRoutePlan(n *routePlan) (*route, error) {
+	var tablesForSelect sqlparser.TableExprs
+	tableNameMap := map[string]interface{}{}
+
+	sort.Sort(n._tables)
+	for _, t := range n._tables {
+		alias := sqlparser.AliasedTableExpr{
+			Expr: sqlparser.TableName{
+				Name: t.vtable.Name,
+			},
+			Partitions: nil,
+			As:         t.qtable.alias.As,
+			Hints:      nil,
+		}
+		tablesForSelect = append(tablesForSelect, &alias)
+		tableNameMap[sqlparser.String(t.qtable.table.Name)] = nil
+	}
+
+	predicates := n.Predicates()
+	var where *sqlparser.Where
+	if predicates != nil {
+		where = &sqlparser.Where{Expr: predicates, Type: sqlparser.WhereClause}
+	}
+
+	var singleColumn vindexes.SingleColumn
+	if n.vindex != nil {
+		singleColumn = n.vindex.(vindexes.SingleColumn)
+	}
+
+	var expressions sqlparser.SelectExprs
+	for _, col := range n.columns {
+		expressions = append(expressions, &sqlparser.AliasedExpr{Expr: col})
+	}
+
+	var tableNames []string
+	for name := range tableNameMap {
+		tableNames = append(tableNames, name)
+	}
+	sort.Strings(tableNames)
+
+	return &route{
+		eroute: &engine.Route{
+			Opcode:    n.routeOpCode,
+			TableName: strings.Join(tableNames, ", "),
+			Keyspace:  n.keyspace,
+			Vindex:    singleColumn,
+			Values:    n.vindexValues,
+		},
+		Select: &sqlparser.Select{
+			SelectExprs: expressions,
+			From:        tablesForSelect,
+			Where:       where,
+		},
+		tables: n.solved,
+	}, nil
+}
diff --git a/go/vt/vtgate/planbuilder/route.go b/go/vt/vtgate/planbuilder/route.go
index 2a357845ec..6998a16b31 100644
--- a/go/vt/vtgate/planbuilder/route.go
+++ b/go/vt/vtgate/planbuilder/route.go
@@ -237,6 +237,16 @@ func (rb *route) prepareTheAST() {
 					},
 				}
 			}
+		case *sqlparser.ComparisonExpr:
+			// 42 = colName -> colName = 42
+			b := node.Operator == sqlparser.EqualOp
+			value := sqlparser.IsValue(node.Left)
+			name := sqlparser.IsColName(node.Right)
+			if b &&
+				value &&
+				name {
+				node.Left, node.Right = node.Right, node.Left
+			}
 		}
 		return true, nil
 	}, rb.Select)
diff --git a/go/vt/vtgate/planbuilder/route_planning.go b/go/vt/vtgate/planbuilder/route_planning.go
index e655083d19..7003fe1b85 100644
--- a/go/vt/vtgate/planbuilder/route_planning.go
+++ b/go/vt/vtgate/planbuilder/route_planning.go
@@ -17,6 +17,7 @@ limitations under the License.
 package planbuilder
 
 import (
+	"fmt"
 	"sort"
 	"strings"
 
@@ -133,6 +134,11 @@ type (
 
 		// cost is simply the number of routes in the joinTree
 		cost() int
+
+		// creates a copy of the joinTree that can be updated without changing the original
+		clone() joinTree
+
+		pushOutputColumns([]*sqlparser.ColName, *semantics.SemTable) int
 	}
 	routeTable struct {
 		qtable *queryTable
@@ -147,86 +153,169 @@ type (
 		// the tables also contain any predicates that only depend on that particular table
 		_tables routeTables
 
-		// extraPredicates are the predicates that depend on multiple tables
-		extraPredicates []sqlparser.Expr
+		// predicates are the predicates evaluated by this plan
+		predicates []sqlparser.Expr
+
+		// vindex and vindexValues is set if a vindex will be used for this route.
+		vindex       vindexes.Vindex
+		vindexValues []sqltypes.PlanValue
+
+		// here we store the possible vindexes we can use so that when we add predicates to the plan,
+		// we can quickly check if the new predicates enables any new vindex options
+		vindexPreds []*vindexPlusPredicates
 
-		// vindex and conditions is set if a vindex will be used for this route.
-		vindex     vindexes.Vindex
-		conditions []sqlparser.Expr
+		// columns needed to feed other plans
+		columns []*sqlparser.ColName
 	}
 	joinPlan struct {
-		predicates []sqlparser.Expr
-		lhs, rhs   joinTree
+		// columns needed to feed other plans
+		columns []int
+
+		// arguments that need to be copied from the LHS/RHS
+		vars map[string]int
+
+		lhs, rhs joinTree
 	}
 	routeTables []*routeTable
 )
 
+var _ joinTree = (*routePlan)(nil)
+var _ joinTree = (*joinPlan)(nil)
+
+// clone returns a copy of the struct with copies of slices,
+// so changing the the contents of them will not be reflected in the original
+func (rp *routePlan) clone() joinTree {
+	result := *rp
+	result.vindexPreds = make([]*vindexPlusPredicates, len(rp.vindexPreds))
+	for i, pred := range rp.vindexPreds {
+		// we do this to create a copy of the struct
+		p := *pred
+		result.vindexPreds[i] = &p
+	}
+	return &result
+}
+
 // tables implements the joinTree interface
 func (rp *routePlan) tables() semantics.TableSet {
 	return rp.solved
 }
 
 // cost implements the joinTree interface
-func (*routePlan) cost() int {
+func (rp *routePlan) cost() int {
+	switch rp.routeOpCode {
+	case // these op codes will never be compared with each other - they are assigned by a rule and not a comparison
+		engine.SelectDBA,
+		engine.SelectNext,
+		engine.SelectNone,
+		engine.SelectReference,
+		engine.SelectUnsharded:
+		return 0
+	// TODO revisit these costs when more of the gen4 planner is done
+	case engine.SelectEqualUnique:
+		return 1
+	case engine.SelectEqual:
+		return 5
+	case engine.SelectIN:
+		return 10
+	case engine.SelectMultiEqual:
+		return 10
+	case engine.SelectScatter:
+		return 20
+	}
 	return 1
 }
 
 // vindexPlusPredicates is a struct used to store all the predicates that the vindex can be used to query
 type vindexPlusPredicates struct {
-	vindex     *vindexes.ColumnVindex
-	covered    bool
-	predicates []sqlparser.Expr
+	vindex *vindexes.ColumnVindex
+	values []sqltypes.PlanValue
+	// Vindex is covered if all the columns in the vindex have an associated predicate
+	covered bool
 }
 
+// addPredicate clones this routePlan and returns a new one with these predicates added to it. if the predicates can help,
+// they will improve the routeOpCode
 func (rp *routePlan) addPredicate(predicates ...sqlparser.Expr) error {
-	if len(rp._tables) != 1 {
-		return vterrors.Errorf(vtrpcpb.Code_INTERNAL, "addPredicate should only be called when the route has a single table")
+	newVindexFound, err := rp.searchForNewVindexes(predicates)
+	if err != nil {
+		return err
 	}
 
-	var vindexPreds []*vindexPlusPredicates
-
-	// Add all the column vindexes to the list of vindexPlusPredicates
-	for _, columnVindex := range rp._tables[0].vtable.ColumnVindexes {
-		vindexPreds = append(vindexPreds, &vindexPlusPredicates{vindex: columnVindex})
+	// if we didn't open up any new vindex options, no need to enter here
+	if newVindexFound {
+		rp.pickBestAvailableVindex()
 	}
 
+	// any predicates that cover more than a single table need to be added here
+	rp.predicates = append(rp.predicates, predicates...)
+
+	return nil
+}
+
+func (rp *routePlan) searchForNewVindexes(predicates []sqlparser.Expr) (bool, error) {
+	newVindexFound := false
 	for _, filter := range predicates {
 		switch node := filter.(type) {
 		case *sqlparser.ComparisonExpr:
 			switch node.Operator {
 			case sqlparser.EqualOp:
+				// here we are searching for predicates in the form n.col = XYZ
 				if sqlparser.IsNull(node.Left) || sqlparser.IsNull(node.Right) {
 					// we are looking at ANDed predicates in the WHERE clause.
 					// since we know that nothing returns true when compared to NULL,
 					// so we can safely bail out here
 					rp.routeOpCode = engine.SelectNone
-					return nil
+					return false, nil
 				}
 				// TODO(Manan,Andres): Remove the predicates that are repeated eg. Id=1 AND Id=1
-				for _, v := range vindexPreds {
-					column := node.Left.(*sqlparser.ColName)
-					for _, col := range v.vindex.Columns {
-						// If the column for the predicate matches any column in the vindex add it to the list
-						if column.Name.Equal(col) {
-							v.predicates = append(v.predicates, node)
-							// Vindex is covered if all the columns in the vindex have a associated predicate
-							v.covered = len(v.predicates) == len(v.vindex.Columns)
+				for _, v := range rp.vindexPreds {
+					if v.covered {
+						// already covered by an earlier predicate
+						continue
+					}
+					column, ok := node.Left.(*sqlparser.ColName)
+					other := node.Right
+					if !ok {
+						column, ok = node.Right.(*sqlparser.ColName)
+						other = node.Left
+					}
+					value, err := sqlparser.NewPlanValue(other)
+					if err != nil {
+						// if we are unable to create a PlanValue, we can't use a vindex, but we don't have to fail
+						if strings.Contains(err.Error(), "expression is too complex") {
+							continue
+						}
+						// something else went wrong, return the error
+						return false, err
+					}
+					if ok {
+						for _, col := range v.vindex.Columns {
+							// If the column for the predicate matches any column in the vindex add it to the list
+							if column.Name.Equal(col) {
+								v.values = append(v.values, value)
+								// Vindex is covered if all the columns in the vindex have a associated predicate
+								v.covered = len(v.values) == len(v.vindex.Columns)
+								newVindexFound = newVindexFound || v.covered
+							}
 						}
 					}
 				}
 			}
 		}
 	}
+	return newVindexFound, nil
+}
 
-	//TODO (Manan,Andres): Improve cost metric for vindexes
-	for _, v := range vindexPreds {
+// pickBestAvailableVindex goes over the available vindexes for this route and picks the best one available.
+func (rp *routePlan) pickBestAvailableVindex() {
+	for _, v := range rp.vindexPreds {
 		if !v.covered {
 			continue
 		}
 		// Choose the minimum cost vindex from the ones which are covered
 		if rp.vindex == nil || v.vindex.Vindex.Cost() < rp.vindex.Cost() {
 			rp.vindex = v.vindex.Vindex
-			rp.conditions = v.predicates
+			rp.vindexValues = v.values
 		}
 	}
 
@@ -236,7 +325,6 @@ func (rp *routePlan) addPredicate(predicates ...sqlparser.Expr) error {
 			rp.routeOpCode = engine.SelectEqualUnique
 		}
 	}
-	return nil
 }
 
 // Predicates takes all known predicates for this route and ANDs them together
@@ -252,34 +340,128 @@ func (rp *routePlan) Predicates() sqlparser.Expr {
 			Right: e,
 		}
 	}
-	for _, t := range rp._tables {
-		for _, predicate := range t.qtable.predicates {
-			add(predicate)
-		}
-	}
-	for _, p := range rp.extraPredicates {
+	for _, p := range rp.predicates {
 		add(p)
 	}
 	return result
 }
 
+func (rp *routePlan) pushOutputColumns(col []*sqlparser.ColName, _ *semantics.SemTable) int {
+	newCol := len(rp.columns)
+	rp.columns = append(rp.columns, col...)
+	return newCol
+}
+
 func (jp *joinPlan) tables() semantics.TableSet {
 	return jp.lhs.tables() | jp.rhs.tables()
 }
+
 func (jp *joinPlan) cost() int {
 	return jp.lhs.cost() + jp.rhs.cost()
 }
 
-func createJoin(lhs, rhs joinTree, joinPredicates []sqlparser.Expr, semTable *semantics.SemTable) joinTree {
-	newPlan := tryMerge(lhs, rhs, joinPredicates, semTable)
-	if newPlan == nil {
-		newPlan = &joinPlan{
-			lhs:        lhs,
-			rhs:        rhs,
-			predicates: joinPredicates,
+func (jp *joinPlan) clone() joinTree {
+	result := &joinPlan{
+		lhs: jp.lhs.clone(),
+		rhs: jp.rhs.clone(),
+	}
+	return result
+}
+
+func (jp *joinPlan) pushOutputColumns(columns []*sqlparser.ColName, semTable *semantics.SemTable) int {
+	resultIdx := len(jp.columns)
+	var toTheLeft []bool
+	var lhs, rhs []*sqlparser.ColName
+	for _, col := range columns {
+		if semTable.Dependencies(col).IsSolvedBy(jp.lhs.tables()) {
+			lhs = append(lhs, col)
+			toTheLeft = append(toTheLeft, true)
+		} else {
+			rhs = append(rhs, col)
+			toTheLeft = append(toTheLeft, false)
 		}
 	}
-	return newPlan
+	lhsOffset := jp.lhs.pushOutputColumns(lhs, semTable)
+	rhsOffset := -jp.rhs.pushOutputColumns(rhs, semTable)
+
+	for _, left := range toTheLeft {
+		if left {
+			jp.columns = append(jp.columns, lhsOffset)
+			lhsOffset++
+		} else {
+			jp.columns = append(jp.columns, rhsOffset)
+			rhsOffset--
+		}
+	}
+	return resultIdx
+}
+
+func pushPredicate2(exprs []sqlparser.Expr, tree joinTree, semTable *semantics.SemTable) (joinTree, error) {
+	switch node := tree.(type) {
+	case *routePlan:
+		plan := node.clone().(*routePlan)
+		err := plan.addPredicate(exprs...)
+		if err != nil {
+			return nil, err
+		}
+		return plan, nil
+
+	case *joinPlan:
+		// we break up the predicates so that colnames from the LHS are replaced by arguments
+		var rhsPreds []sqlparser.Expr
+		var lhsColumns []*sqlparser.ColName
+		lhsSolves := node.lhs.tables()
+		for _, expr := range exprs {
+			cols, predicate, err := breakPredicateInLHSandRHS(expr, semTable, lhsSolves)
+			if err != nil {
+				return nil, err
+			}
+			lhsColumns = append(lhsColumns, cols...)
+			rhsPreds = append(rhsPreds, predicate)
+		}
+		node.pushOutputColumns(lhsColumns, semTable)
+		rhsPlan, err := pushPredicate2(rhsPreds, node.rhs, semTable)
+		if err != nil {
+			return nil, err
+		}
+		return &joinPlan{
+			lhs: node.lhs,
+			rhs: rhsPlan,
+		}, nil
+	default:
+		panic(fmt.Sprintf("BUG: unknown type %T", node))
+	}
+}
+
+func breakPredicateInLHSandRHS(expr sqlparser.Expr, semTable *semantics.SemTable, lhs semantics.TableSet) (columns []*sqlparser.ColName, predicate sqlparser.Expr, err error) {
+	predicate = expr.Clone()
+	sqlparser.Rewrite(predicate, nil, func(cursor *sqlparser.Cursor) bool {
+		switch node := cursor.Node().(type) {
+		case *sqlparser.ColName:
+			deps := semTable.Dependencies(node)
+			if deps == 0 {
+				err = vterrors.Errorf(vtrpcpb.Code_INTERNAL, "unknown column. has the AST been copied?")
+				return false
+			}
+			if deps.IsSolvedBy(lhs) {
+				columns = append(columns, node)
+				arg := sqlparser.NewArgument([]byte(":" + node.CompliantName("")))
+				cursor.Replace(arg)
+			}
+		}
+		return true
+	})
+	return
+}
+
+func mergeOrJoin(lhs, rhs joinTree, joinPredicates []sqlparser.Expr, semTable *semantics.SemTable) (joinTree, error) {
+	newPlan := tryMerge(lhs, rhs, joinPredicates, semTable)
+	if newPlan != nil {
+		return newPlan, nil
+	}
+
+	tree := &joinPlan{lhs: lhs.clone(), rhs: rhs.clone()}
+	return pushPredicate2(joinPredicates, tree, semTable)
 }
 
 type (
@@ -304,11 +486,20 @@ func greedySolve(qg *queryGraph, semTable *semantics.SemTable, vschema ContextVS
 
 	crossJoinsOK := false
 	for len(joinTrees) > 1 {
-		bestTree, lIdx, rIdx := findBestJoinTree(qg, semTable, joinTrees, planCache, crossJoinsOK)
+		bestTree, lIdx, rIdx, err := findBestJoinTree(qg, semTable, joinTrees, planCache, crossJoinsOK)
+		if err != nil {
+			return nil, err
+		}
+		// if we found a best plan, we'll replace the two plans that were joined with the join plan created
 		if bestTree != nil {
-			// if we found a best plan, we'll replace the two joinTrees that were joined with the join plan created
-			joinTrees = removeAt(joinTrees, rIdx)
-			joinTrees = removeAt(joinTrees, lIdx)
+			// we need to remove the larger of the two plans first
+			if rIdx > lIdx {
+				joinTrees = removeAt(joinTrees, rIdx)
+				joinTrees = removeAt(joinTrees, lIdx)
+			} else {
+				joinTrees = removeAt(joinTrees, lIdx)
+				joinTrees = removeAt(joinTrees, rIdx)
+			}
 			joinTrees = append(joinTrees, bestTree)
 		} else {
 			// we will only fail to find a join plan when there are only cross joins left
@@ -321,14 +512,19 @@ func greedySolve(qg *queryGraph, semTable *semantics.SemTable, vschema ContextVS
 	return joinTrees[0], nil
 }
 
-func (cm cacheMap) getJoinTreeFor(lhs, rhs joinTree, joinPredicates []sqlparser.Expr, semTable *semantics.SemTable) joinTree {
+func (cm cacheMap) getJoinTreeFor(lhs, rhs joinTree, joinPredicates []sqlparser.Expr, semTable *semantics.SemTable) (joinTree, error) {
 	solves := tableSetPair{left: lhs.tables(), right: rhs.tables()}
-	plan := cm[solves]
-	if plan == nil {
-		plan = createJoin(lhs, rhs, joinPredicates, semTable)
-		cm[solves] = plan
+	cachedPlan := cm[solves]
+	if cachedPlan != nil {
+		return cachedPlan, nil
 	}
-	return plan
+
+	join, err := mergeOrJoin(lhs, rhs, joinPredicates, semTable)
+	if err != nil {
+		return nil, err
+	}
+	cm[solves] = join
+	return join, nil
 }
 
 func findBestJoinTree(
@@ -337,10 +533,7 @@ func findBestJoinTree(
 	plans []joinTree,
 	planCache cacheMap,
 	crossJoinsOK bool,
-) (joinTree, int, int) {
-	var lIdx, rIdx int
-	var bestPlan joinTree
-
+) (bestPlan joinTree, lIdx int, rIdx int, err error) {
 	for i, lhs := range plans {
 		for j, rhs := range plans {
 			if i == j {
@@ -353,8 +546,10 @@ func findBestJoinTree(
 				// cartesian product, which is almost always a bad idea
 				continue
 			}
-			plan := planCache.getJoinTreeFor(lhs, rhs, joinPredicates, semTable)
-
+			plan, err := planCache.getJoinTreeFor(lhs, rhs, joinPredicates, semTable)
+			if err != nil {
+				return nil, 0, 0, err
+			}
 			if bestPlan == nil || plan.cost() < bestPlan.cost() {
 				bestPlan = plan
 				// remember which plans we based on, so we can remove them later
@@ -363,7 +558,7 @@ func findBestJoinTree(
 			}
 		}
 	}
-	return bestPlan, lIdx, rIdx
+	return bestPlan, lIdx, rIdx, nil
 }
 
 func leftToRightSolve(qg *queryGraph, semTable *semantics.SemTable, vschema ContextVSchema) (joinTree, error) {
@@ -379,7 +574,10 @@ func leftToRightSolve(qg *queryGraph, semTable *semantics.SemTable, vschema Cont
 			continue
 		}
 		joinPredicates := qg.getPredicates(acc.tables(), plan.tables())
-		acc = createJoin(acc, plan, joinPredicates, semTable)
+		acc, err = mergeOrJoin(acc, plan, joinPredicates, semTable)
+		if err != nil {
+			return nil, err
+		}
 	}
 
 	return acc, nil
@@ -419,6 +617,10 @@ func createRoutePlan(table *queryTable, solves semantics.TableSet, vschema Conte
 		keyspace: vschemaTable.Keyspace,
 	}
 
+	for _, columnVindex := range vschemaTable.ColumnVindexes {
+		plan.vindexPreds = append(plan.vindexPreds, &vindexPlusPredicates{vindex: columnVindex})
+	}
+
 	switch {
 	case vschemaTable.Type == vindexes.TypeSequence:
 		plan.routeOpCode = engine.SelectNext
@@ -443,133 +645,6 @@ func createRoutePlan(table *queryTable, solves semantics.TableSet, vschema Conte
 	return plan, nil
 }
 
-func transformToLogicalPlan(tree joinTree, semTable *semantics.SemTable) (logicalPlan, error) {
-	switch n := tree.(type) {
-	case *routePlan:
-		return transformRoutePlan(n)
-
-	case *joinPlan:
-		return transformJoinPlan(n, semTable)
-	}
-
-	return nil, vterrors.Errorf(vtrpcpb.Code_INTERNAL, "BUG: unknown type encountered: %T", tree)
-}
-
-func transformJoinPlan(n *joinPlan, semTable *semantics.SemTable) (*joinV4, error) {
-	lhsColList := extractColumnsNeededFromLHS(n, semTable, n.lhs.tables())
-
-	lhs, err := transformToLogicalPlan(n.lhs, semTable)
-	if err != nil {
-		return nil, err
-	}
-
-	vars := map[string]int{}
-	for _, col := range lhsColList {
-		offset, err := pushProjection(&sqlparser.AliasedExpr{Expr: col}, lhs, semTable)
-		if err != nil {
-			return nil, err
-		}
-		vars[col.CompliantName("")] = offset
-	}
-
-	rhs, err := transformToLogicalPlan(n.rhs, semTable)
-	if err != nil {
-		return nil, err
-	}
-
-	err = pushPredicate(n.predicates, rhs, semTable)
-	if err != nil {
-		return nil, err
-	}
-
-	return &joinV4{
-		Left:  lhs,
-		Right: rhs,
-		Vars:  vars,
-	}, nil
-}
-
-func extractColumnsNeededFromLHS(n *joinPlan, semTable *semantics.SemTable, lhsSolves semantics.TableSet) []*sqlparser.ColName {
-	lhsColMap := map[*sqlparser.ColName]sqlparser.Argument{}
-	for _, predicate := range n.predicates {
-		sqlparser.Rewrite(predicate, func(cursor *sqlparser.Cursor) bool {
-			switch node := cursor.Node().(type) {
-			case *sqlparser.ColName:
-				if semTable.Dependencies(node).IsSolvedBy(lhsSolves) {
-					arg := sqlparser.NewArgument([]byte(":" + node.CompliantName("")))
-					lhsColMap[node] = arg
-					cursor.Replace(arg)
-				}
-			}
-			return true
-		}, nil)
-	}
-
-	var lhsColList []*sqlparser.ColName
-	for col := range lhsColMap {
-		lhsColList = append(lhsColList, col)
-	}
-	return lhsColList
-}
-
-func transformRoutePlan(n *routePlan) (*route, error) {
-	var tablesForSelect sqlparser.TableExprs
-	tableNameMap := map[string]interface{}{}
-
-	sort.Sort(n._tables)
-	for _, t := range n._tables {
-		alias := sqlparser.AliasedTableExpr{
-			Expr: sqlparser.TableName{
-				Name: t.vtable.Name,
-			},
-			Partitions: nil,
-			As:         t.qtable.alias.As,
-			Hints:      nil,
-		}
-		tablesForSelect = append(tablesForSelect, &alias)
-		tableNameMap[sqlparser.String(t.qtable.table.Name)] = nil
-	}
-
-	predicates := n.Predicates()
-	var where *sqlparser.Where
-	if predicates != nil {
-		where = &sqlparser.Where{Expr: predicates, Type: sqlparser.WhereClause}
-	}
-	var values []sqltypes.PlanValue
-	if len(n.conditions) == 1 {
-		value, err := sqlparser.NewPlanValue(n.conditions[0].(*sqlparser.ComparisonExpr).Right)
-		if err != nil {
-			return nil, err
-		}
-		values = []sqltypes.PlanValue{value}
-	}
-	var singleColumn vindexes.SingleColumn
-	if n.vindex != nil {
-		singleColumn = n.vindex.(vindexes.SingleColumn)
-	}
-
-	var tableNames []string
-	for name := range tableNameMap {
-		tableNames = append(tableNames, name)
-	}
-	sort.Strings(tableNames)
-
-	return &route{
-		eroute: &engine.Route{
-			Opcode:    n.routeOpCode,
-			TableName: strings.Join(tableNames, ", "),
-			Keyspace:  n.keyspace,
-			Vindex:    singleColumn,
-			Values:    values,
-		},
-		Select: &sqlparser.Select{
-			From:  tablesForSelect,
-			Where: where,
-		},
-		tables: n.solved,
-	}, nil
-}
-
 func findColumnVindex(a *routePlan, exp sqlparser.Expr, sem *semantics.SemTable) vindexes.SingleColumn {
 	left, isCol := exp.(*sqlparser.ColName)
 	if !isCol {
@@ -642,10 +717,11 @@ func tryMerge(a, b joinTree, joinPredicates []sqlparser.Expr, semTable *semantic
 		routeOpCode: aRoute.routeOpCode,
 		solved:      newTabletSet,
 		_tables:     append(aRoute._tables, bRoute._tables...),
-		extraPredicates: append(
-			append(aRoute.extraPredicates, bRoute.extraPredicates...),
+		predicates: append(
+			append(aRoute.predicates, bRoute.predicates...),
 			joinPredicates...),
-		keyspace: aRoute.keyspace,
+		keyspace:    aRoute.keyspace,
+		vindexPreds: append(aRoute.vindexPreds, bRoute.vindexPreds...),
 	}
 
 	switch aRoute.routeOpCode {
@@ -665,14 +741,7 @@ func tryMerge(a, b joinTree, joinPredicates []sqlparser.Expr, semTable *semantic
 		if !canMerge {
 			return nil
 		}
-		if aRoute.routeOpCode == engine.SelectEqualUnique {
-			r.vindex = aRoute.vindex
-			r.conditions = aRoute.conditions
-		} else if bRoute.routeOpCode == engine.SelectEqualUnique {
-			r.routeOpCode = bRoute.routeOpCode
-			r.vindex = bRoute.vindex
-			r.conditions = bRoute.conditions
-		}
+		r.pickBestAvailableVindex()
 	}
 
 	return r
diff --git a/go/vt/vtgate/semantics/semantic_state.go b/go/vt/vtgate/semantics/semantic_state.go
index 6e770a5c18..d6430082ff 100644
--- a/go/vt/vtgate/semantics/semantic_state.go
+++ b/go/vt/vtgate/semantics/semantic_state.go
@@ -42,6 +42,11 @@ type (
 	}
 )
 
+// NewSemTable creates a new empty SemTable
+func NewSemTable() *SemTable {
+	return &SemTable{exprDependencies: map[sqlparser.Expr]TableSet{}}
+}
+
 // TableSetFor returns the bitmask for this particular tableshoe
 func (st *SemTable) TableSetFor(t table) TableSet {
 	for idx, t2 := range st.Tables {
@@ -54,7 +59,10 @@ func (st *SemTable) TableSetFor(t table) TableSet {
 
 // Dependencies return the table dependencies of the expression.
 func (st *SemTable) Dependencies(expr sqlparser.Expr) TableSet {
-	var deps TableSet
+	deps, found := st.exprDependencies[expr]
+	if found {
+		return deps
+	}
 
 	_ = sqlparser.Walk(func(node sqlparser.SQLNode) (kontinue bool, err error) {
 		colName, ok := node.(*sqlparser.ColName)
@@ -65,6 +73,8 @@ func (st *SemTable) Dependencies(expr sqlparser.Expr) TableSet {
 		return true, nil
 	}, expr)
 
+	st.exprDependencies[expr] = deps
+
 	return deps
 }
 
@@ -112,11 +122,13 @@ func (ts TableSet) NumberOfTables() int {
 // Constituents returns an slice with all the
 // individual tables in their own TableSet identifier
 func (ts TableSet) Constituents() (result []TableSet) {
-	for i := 0; i < 64; i++ {
-		i2 := TableSet(1 << i)
-		if ts&i2 == i2 {
-			result = append(result, i2)
-		}
+	mask := ts
+
+	for mask > 0 {
+		maskLeft := mask & (mask - 1)
+		constituent := mask ^ maskLeft
+		mask = maskLeft
+		result = append(result, constituent)
 	}
 	return
 }


Test patch:
diff --git a/go/vt/vtgate/planbuilder/plan_test.go b/go/vt/vtgate/planbuilder/plan_test.go
index b280a215b1..c8194aa8d6 100644
--- a/go/vt/vtgate/planbuilder/plan_test.go
+++ b/go/vt/vtgate/planbuilder/plan_test.go
@@ -400,7 +400,7 @@ func testFile(t *testing.T, filename, tempDir string, vschema *vschemaWrapper, c
 		expected := &strings.Builder{}
 		fail := checkAllTests
 		for tcase := range iterateExecFile(filename) {
-			t.Run(tcase.comments, func(t *testing.T) {
+			t.Run(fmt.Sprintf("%d V3: %s", tcase.lineno, tcase.comments), func(t *testing.T) {
 				vschema.version = V3
 				plan, err := TestBuilder(tcase.input, vschema)
 				out := getPlanOrErrorOutput(err, plan)
@@ -432,7 +432,7 @@ func testFile(t *testing.T, filename, tempDir string, vschema *vschemaWrapper, c
 			//       with this last expectation, it is an error if the V4 planner
 			//       produces the same plan as the V3 planner does
 			if !empty || checkAllTests {
-				t.Run("V4: "+tcase.comments, func(t *testing.T) {
+				t.Run(fmt.Sprintf("%d V4: %s", tcase.lineno, tcase.comments), func(t *testing.T) {
 					if out != tcase.output2ndPlanner {
 						fail = true
 						t.Errorf("V4 - %s:%d\nDiff:\n%s\n[%s] \n[%s]", filename, tcase.lineno, cmp.Diff(tcase.output2ndPlanner, out), tcase.output, out)
diff --git a/go/vt/vtgate/planbuilder/querygraph_test.go b/go/vt/vtgate/planbuilder/querygraph_test.go
index 71c8c06989..43717a4a46 100644
--- a/go/vt/vtgate/planbuilder/querygraph_test.go
+++ b/go/vt/vtgate/planbuilder/querygraph_test.go
@@ -123,7 +123,6 @@ func TestQueryGraph(t *testing.T) {
 			require.NoError(t, err)
 			qgraph, err := createQGFromSelect(tree.(*sqlparser.Select), semTable)
 			require.NoError(t, err)
-			fmt.Println(qgraph.testString())
 			assert.Equal(t, tc.output, qgraph.testString())
 			utils.MustMatch(t, tc.output, qgraph.testString(), "incorrect query graph")
 		})
diff --git a/go/vt/vtgate/planbuilder/route_planning_test.go b/go/vt/vtgate/planbuilder/route_planning_test.go
index f3335d9d1e..4209225bd6 100644
--- a/go/vt/vtgate/planbuilder/route_planning_test.go
+++ b/go/vt/vtgate/planbuilder/route_planning_test.go
@@ -99,8 +99,28 @@ func TestMergeJoins(t *testing.T) {
 	}}
 	for i, tc := range tests {
 		t.Run(fmt.Sprintf("%d", i), func(t *testing.T) {
-			result := tryMerge(tc.l, tc.r, tc.predicates, &semantics.SemTable{})
+			result := tryMerge(tc.l, tc.r, tc.predicates, semantics.NewSemTable())
 			assert.Equal(t, tc.expected, result)
 		})
 	}
 }
+
+func TestClone(t *testing.T) {
+	original := &routePlan{
+		routeOpCode: engine.SelectEqualUnique,
+		vindexPreds: []*vindexPlusPredicates{{
+			covered: false,
+		}},
+	}
+
+	clone := original.clone()
+
+	clonedRP := clone.(*routePlan)
+	clonedRP.routeOpCode = engine.SelectDBA
+	assert.Equal(t, clonedRP.routeOpCode, engine.SelectDBA)
+	assert.Equal(t, original.routeOpCode, engine.SelectEqualUnique)
+
+	clonedRP.vindexPreds[0].covered = true
+	assert.True(t, clonedRP.vindexPreds[0].covered)
+	assert.False(t, original.vindexPreds[0].covered)
+}
diff --git a/go/vt/vtgate/planbuilder/testdata/filter_cases.txt b/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
index d7ebbd53b1..9625327dd4 100644
--- a/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
@@ -34,7 +34,21 @@ Gen4 plan same as above
     "Table": "user"
   }
 }
-Gen4 plan same as above
+{
+  "QueryType": "SELECT",
+  "Original": "select id from user where someColumn = null",
+  "Instructions": {
+    "OperatorType": "Route",
+    "Variant": "SelectNone",
+    "Keyspace": {
+      "Name": "user",
+      "Sharded": true
+    },
+    "FieldQuery": "select id from user where 1 != 1",
+    "Query": "select id from user where someColumn = null",
+    "Table": "user"
+  }
+}
 
 # Single table unique vindex route
 "select id from user where user.id = 5"
@@ -76,6 +90,7 @@ Gen4 plan same as above
     "Table": "user"
   }
 }
+Gen4 plan same as above
 
 # Single table multiple unique vindex match
 "select id from music where id = 5 and user_id = 4"
@@ -981,7 +996,44 @@ Gen4 plan same as above
     ]
   }
 }
-Gen4 plan same as above
+{
+  "QueryType": "SELECT",
+  "Original": "select unsharded.id from user join unsharded where unsharded.id = user.id",
+  "Instructions": {
+    "OperatorType": "Join",
+    "Variant": "Join",
+    "JoinColumnIndexes": "-2",
+    "TableName": "unsharded_user",
+    "Inputs": [
+      {
+        "OperatorType": "Route",
+        "Variant": "SelectUnsharded",
+        "Keyspace": {
+          "Name": "main",
+          "Sharded": false
+        },
+        "FieldQuery": "select unsharded.id, unsharded.id from unsharded where 1 != 1",
+        "Query": "select unsharded.id, unsharded.id from unsharded",
+        "Table": "unsharded"
+      },
+      {
+        "OperatorType": "Route",
+        "Variant": "SelectEqualUnique",
+        "Keyspace": {
+          "Name": "user",
+          "Sharded": true
+        },
+        "FieldQuery": "select 1 from user where 1 != 1",
+        "Query": "select 1 from user where user.id = :unsharded_id",
+        "Table": "user",
+        "Values": [
+          ":unsharded_id"
+        ],
+        "Vindex": "user_index"
+      }
+    ]
+  }
+}
 
 # routing rules: choose the redirected table
 "select col from route1 where id = 1"
@@ -1540,6 +1592,25 @@ Gen4 plan same as above
     "Vindex": "user_index"
   }
 }
+{
+  "QueryType": "SELECT",
+  "Original": "select user_extra.Id from user join user_extra on user.iD = user_extra.User_Id where user.Id = 5",
+  "Instructions": {
+    "OperatorType": "Route",
+    "Variant": "SelectEqualUnique",
+    "Keyspace": {
+      "Name": "user",
+      "Sharded": true
+    },
+    "FieldQuery": "select user_extra.Id from user, user_extra where 1 != 1",
+    "Query": "select user_extra.Id from user, user_extra where user.Id = 5 and user.iD = user_extra.User_Id",
+    "Table": "user, user_extra",
+    "Values": [
+      5
+    ],
+    "Vindex": "user_index"
+  }
+}
 
 # database() call in where clause.
 "select id from user where database()"
@@ -1582,7 +1653,21 @@ Gen4 plan same as above
     "Table": "music"
   }
 }
-Gen4 plan same as above
+{
+  "QueryType": "SELECT",
+  "Original": "select id from music where id = null",
+  "Instructions": {
+    "OperatorType": "Route",
+    "Variant": "SelectNone",
+    "Keyspace": {
+      "Name": "user",
+      "Sharded": true
+    },
+    "FieldQuery": "select id from music where 1 != 1",
+    "Query": "select id from music where id = null",
+    "Table": "music"
+  }
+}
 
 # SELECT with IS NULL
 "select id from music where id is null"
@@ -1642,7 +1727,21 @@ Gen4 plan same as above
     "Table": "music"
   }
 }
-Gen4 plan same as above
+{
+  "QueryType": "SELECT",
+  "Original": "select id from music where user_id = 4 and id = null",
+  "Instructions": {
+    "OperatorType": "Route",
+    "Variant": "SelectNone",
+    "Keyspace": {
+      "Name": "user",
+      "Sharded": true
+    },
+    "FieldQuery": "select id from music where 1 != 1",
+    "Query": "select id from music where user_id = 4 and id = null",
+    "Table": "music"
+  }
+}
 
 # Single table with unique vindex match and IN (null)
 "select id from music where user_id = 4 and id IN (null)"
diff --git a/go/vt/vtgate/planbuilder/testdata/from_cases.txt b/go/vt/vtgate/planbuilder/testdata/from_cases.txt
index b0d3f050b3..7c60194057 100644
--- a/go/vt/vtgate/planbuilder/testdata/from_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/from_cases.txt
@@ -1151,6 +1151,7 @@ Gen4 plan same as above
     ]
   }
 }
+Gen4 plan same as above
 
 # sharded join, non-vindex col
 "select user.col from user join user_extra on user.id = user_extra.col"
@@ -1194,8 +1195,8 @@ Gen4 plan same as above
   "Instructions": {
     "OperatorType": "Join",
     "Variant": "Join",
-    "JoinColumnIndexes": "-2",
-    "TableName": "user_user_extra",
+    "JoinColumnIndexes": "1",
+    "TableName": "user_extra_user",
     "Inputs": [
       {
         "OperatorType": "Route",
@@ -1204,20 +1205,24 @@ Gen4 plan same as above
           "Name": "user",
           "Sharded": true
         },
-        "FieldQuery": "select user.id, user.col from user where 1 != 1",
-        "Query": "select user.id, user.col from user",
-        "Table": "user"
+        "FieldQuery": "select user_extra.col from user_extra where 1 != 1",
+        "Query": "select user_extra.col from user_extra",
+        "Table": "user_extra"
       },
       {
         "OperatorType": "Route",
-        "Variant": "SelectScatter",
+        "Variant": "SelectEqualUnique",
         "Keyspace": {
           "Name": "user",
           "Sharded": true
         },
-        "FieldQuery": "select 1 from user_extra where 1 != 1",
-        "Query": "select 1 from user_extra where user_extra.col = :user_id",
-        "Table": "user_extra"
+        "FieldQuery": "select user.col from user where 1 != 1",
+        "Query": "select user.col from user where user.id = :user_extra_col",
+        "Table": "user",
+        "Values": [
+          ":user_extra_col"
+        ],
+        "Vindex": "user_index"
       }
     ]
   }
@@ -2395,8 +2400,8 @@ Gen4 plan same as above
   "Instructions": {
     "OperatorType": "Join",
     "Variant": "Join",
-    "JoinColumnIndexes": "-2",
-    "TableName": "user_user_extra",
+    "JoinColumnIndexes": "1",
+    "TableName": "user_extra_user",
     "Inputs": [
       {
         "OperatorType": "Route",
@@ -2405,20 +2410,24 @@ Gen4 plan same as above
           "Name": "user",
           "Sharded": true
         },
-        "FieldQuery": "select user.id, user.id from user where 1 != 1",
-        "Query": "select user.id, user.id from user",
-        "Table": "user"
+        "FieldQuery": "select user_extra.id from user_extra where 1 != 1",
+        "Query": "select user_extra.id from user_extra",
+        "Table": "user_extra"
       },
       {
         "OperatorType": "Route",
-        "Variant": "SelectScatter",
+        "Variant": "SelectEqualUnique",
         "Keyspace": {
           "Name": "user",
           "Sharded": true
         },
-        "FieldQuery": "select 1 from user_extra where 1 != 1",
-        "Query": "select 1 from user_extra where user_extra.id = :user_id",
-        "Table": "user_extra"
+        "FieldQuery": "select user.id from user where 1 != 1",
+        "Query": "select user.id from user where user.id = :user_extra_id",
+        "Table": "user",
+        "Values": [
+          ":user_extra_id"
+        ],
+        "Vindex": "user_index"
       }
     ]
   }
diff --git a/go/vt/vtgate/planbuilder/testdata/large_cases.txt b/go/vt/vtgate/planbuilder/testdata/large_cases.txt
index 3ec24ac86c..064a60a479 100644
--- a/go/vt/vtgate/planbuilder/testdata/large_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/large_cases.txt
@@ -178,24 +178,24 @@
     "OperatorType": "Join",
     "Variant": "Join",
     "JoinColumnIndexes": "1",
-    "TableName": "unsharded, unsharded_a, unsharded_auto, unsharded_b_user, user_extra, user_metadata_music, music_extra",
+    "TableName": "music, music_extra_user, user_extra, user_metadata_unsharded, unsharded_a, unsharded_auto, unsharded_b",
     "Inputs": [
       {
         "OperatorType": "Route",
-        "Variant": "SelectUnsharded",
+        "Variant": "SelectScatter",
         "Keyspace": {
-          "Name": "main",
-          "Sharded": false
+          "Name": "user",
+          "Sharded": true
         },
-        "FieldQuery": "select 1 from unsharded, unsharded_a, unsharded_b, unsharded_auto where 1 != 1",
-        "Query": "select 1 from unsharded, unsharded_a, unsharded_b, unsharded_auto where unsharded.x = unsharded_a.y",
-        "Table": "unsharded, unsharded_a, unsharded_auto, unsharded_b"
+        "FieldQuery": "select 1 from music, music_extra where 1 != 1",
+        "Query": "select 1 from music, music_extra where music.id = music_extra.music_id",
+        "Table": "music, music_extra"
       },
       {
         "OperatorType": "Join",
         "Variant": "Join",
         "JoinColumnIndexes": "-1",
-        "TableName": "user, user_extra, user_metadata_music, music_extra",
+        "TableName": "user, user_extra, user_metadata_unsharded, unsharded_a, unsharded_auto, unsharded_b",
         "Inputs": [
           {
             "OperatorType": "Route",
@@ -210,14 +210,14 @@
           },
           {
             "OperatorType": "Route",
-            "Variant": "SelectScatter",
+            "Variant": "SelectUnsharded",
             "Keyspace": {
-              "Name": "user",
-              "Sharded": true
+              "Name": "main",
+              "Sharded": false
             },
-            "FieldQuery": "select 1 from music, music_extra where 1 != 1",
-            "Query": "select 1 from music, music_extra where music.id = music_extra.music_id",
-            "Table": "music, music_extra"
+            "FieldQuery": "select 1 from unsharded, unsharded_a, unsharded_b, unsharded_auto where 1 != 1",
+            "Query": "select 1 from unsharded, unsharded_a, unsharded_b, unsharded_auto where unsharded.x = unsharded_a.y",
+            "Table": "unsharded, unsharded_a, unsharded_auto, unsharded_b"
           }
         ]
       }
diff --git a/go/vt/vtgate/planbuilder/testdata/select_cases.txt b/go/vt/vtgate/planbuilder/testdata/select_cases.txt
index 5d07ee2cc9..42ef6bf233 100644
--- a/go/vt/vtgate/planbuilder/testdata/select_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/select_cases.txt
@@ -838,6 +838,7 @@ Gen4 plan same as above
     "Table": "user"
   }
 }
+Gen4 plan same as above
 
 # sharded limit offset
 "select user_id from music order by user_id limit 10, 20"
diff --git a/go/vt/vtgate/semantics/analyzer_test.go b/go/vt/vtgate/semantics/analyzer_test.go
index cca3eef467..8a30c4dbf8 100644
--- a/go/vt/vtgate/semantics/analyzer_test.go
+++ b/go/vt/vtgate/semantics/analyzer_test.go
@@ -40,7 +40,6 @@ func extract(in *sqlparser.Select, idx int) sqlparser.Expr {
 }
 
 func TestScopeForSubqueries(t *testing.T) {
-	t.Skip("re-enable when gen4 supports subqueries")
 	query := `
 select t.col1, (
 	select t.col2 from z as t) 
diff --git a/go/vt/vtgate/semantics/tabletset_test.go b/go/vt/vtgate/semantics/tabletset_test.go
index c3d1da5b95..8ff41c57ec 100644
--- a/go/vt/vtgate/semantics/tabletset_test.go
+++ b/go/vt/vtgate/semantics/tabletset_test.go
@@ -29,15 +29,25 @@ const (
 	F3
 )
 
-func TestTableSet(t *testing.T) {
+func TestTableSet_IsOverlapping(t *testing.T) {
 	assert.True(t, (F1 | F2).IsOverlapping(F1|F2))
 	assert.True(t, F1.IsOverlapping(F1|F2))
 	assert.True(t, (F1 | F2).IsOverlapping(F1))
 	assert.False(t, F3.IsOverlapping(F1|F2))
 	assert.False(t, (F1 | F2).IsOverlapping(F3))
+}
 
+func TestTableSet_IsSolvedBy(t *testing.T) {
 	assert.True(t, F1.IsSolvedBy(F1|F2))
 	assert.False(t, (F1 | F2).IsSolvedBy(F1))
 	assert.False(t, F3.IsSolvedBy(F1|F2))
 	assert.False(t, (F1 | F2).IsSolvedBy(F3))
 }
+
+func TestTableSet_Constituents(t *testing.T) {
+	assert.Equal(t, []TableSet{F1, F2, F3}, (F1 | F2 | F3).Constituents())
+	assert.Equal(t, []TableSet{F1, F2}, (F1 | F2).Constituents())
+	assert.Equal(t, []TableSet{F1, F3}, (F1 | F3).Constituents())
+	assert.Equal(t, []TableSet{F2, F3}, (F2 | F3).Constituents())
+	assert.Empty(t, TableSet(0).Constituents())
+}