Repository: vitessio/vitess
Pull request #8773 (2021-09-07 07:34:27)

Gen4: improve expand star
## Description

This pull request improves the expand star logic. Star expressions are now supported in the select list.

While improving the expand star logic, @systay and I improved the analyzer. The analyzer is now binding columns to expressions in a better way, mainly a new `dependencies` interface allows us to tell three things: if a column has `certain`, `uncertain` dependencies or none (`nothing`), this gives us more power when trying to detect column ambiguity. Additionally, the derived tables are using a different implementation `TableInfo` which is `derivedTable` instead of `vTableInfo`.

### New supported queries

- select star against a derived table selecting from an unsharded tabled: `select u.* from (select * from unsharded) u`
- select star against a sharded table: `select user.* from user`
- select star inside a derived table against information schema table (non authoritative): `select x.table_name from (select a.* from information_schema.key_column_usage a) x`
- join with a predicate that comes from a derived table that does a select star against an information schema table: `select x.table_name from (select a.* from information_schema.key_column_usage a) x join user on x.id = user.id`


## Related Issue(s)

- #7280 

## Checklist
- [x] Tests were added or are not required
- [x] Documentation was added or is not required



Patch:
diff --git a/go/vt/topo/k8stopo/client/clientset/versioned/clientset.go b/go/vt/topo/k8stopo/client/clientset/versioned/clientset.go
index 40b5548e40..83ad7c4c83 100644
--- a/go/vt/topo/k8stopo/client/clientset/versioned/clientset.go
+++ b/go/vt/topo/k8stopo/client/clientset/versioned/clientset.go
@@ -24,6 +24,7 @@ import (
 	discovery "k8s.io/client-go/discovery"
 	rest "k8s.io/client-go/rest"
 	flowcontrol "k8s.io/client-go/util/flowcontrol"
+
 	topov1beta1 "vitess.io/vitess/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1"
 )
 
diff --git a/go/vt/topo/k8stopo/client/clientset/versioned/fake/clientset_generated.go b/go/vt/topo/k8stopo/client/clientset/versioned/fake/clientset_generated.go
index 71e764f470..532eab2b2a 100644
--- a/go/vt/topo/k8stopo/client/clientset/versioned/fake/clientset_generated.go
+++ b/go/vt/topo/k8stopo/client/clientset/versioned/fake/clientset_generated.go
@@ -24,6 +24,7 @@ import (
 	"k8s.io/client-go/discovery"
 	fakediscovery "k8s.io/client-go/discovery/fake"
 	"k8s.io/client-go/testing"
+
 	clientset "vitess.io/vitess/go/vt/topo/k8stopo/client/clientset/versioned"
 	topov1beta1 "vitess.io/vitess/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1"
 	faketopov1beta1 "vitess.io/vitess/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/fake"
diff --git a/go/vt/topo/k8stopo/client/clientset/versioned/fake/register.go b/go/vt/topo/k8stopo/client/clientset/versioned/fake/register.go
index 55ae45f14c..5b425fd460 100644
--- a/go/vt/topo/k8stopo/client/clientset/versioned/fake/register.go
+++ b/go/vt/topo/k8stopo/client/clientset/versioned/fake/register.go
@@ -24,6 +24,7 @@ import (
 	schema "k8s.io/apimachinery/pkg/runtime/schema"
 	serializer "k8s.io/apimachinery/pkg/runtime/serializer"
 	utilruntime "k8s.io/apimachinery/pkg/util/runtime"
+
 	topov1beta1 "vitess.io/vitess/go/vt/topo/k8stopo/apis/topo/v1beta1"
 )
 
diff --git a/go/vt/topo/k8stopo/client/clientset/versioned/scheme/register.go b/go/vt/topo/k8stopo/client/clientset/versioned/scheme/register.go
index dbfa0f69fa..1d8b48578c 100644
--- a/go/vt/topo/k8stopo/client/clientset/versioned/scheme/register.go
+++ b/go/vt/topo/k8stopo/client/clientset/versioned/scheme/register.go
@@ -24,6 +24,7 @@ import (
 	schema "k8s.io/apimachinery/pkg/runtime/schema"
 	serializer "k8s.io/apimachinery/pkg/runtime/serializer"
 	utilruntime "k8s.io/apimachinery/pkg/util/runtime"
+
 	topov1beta1 "vitess.io/vitess/go/vt/topo/k8stopo/apis/topo/v1beta1"
 )
 
diff --git a/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/fake/fake_topo_client.go b/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/fake/fake_topo_client.go
index a669d391f3..76c43f0d8d 100644
--- a/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/fake/fake_topo_client.go
+++ b/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/fake/fake_topo_client.go
@@ -21,6 +21,7 @@ package fake
 import (
 	rest "k8s.io/client-go/rest"
 	testing "k8s.io/client-go/testing"
+
 	v1beta1 "vitess.io/vitess/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1"
 )
 
diff --git a/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/fake/fake_vitesstoponode.go b/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/fake/fake_vitesstoponode.go
index b3cd86c6d8..45841625eb 100644
--- a/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/fake/fake_vitesstoponode.go
+++ b/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/fake/fake_vitesstoponode.go
@@ -27,6 +27,7 @@ import (
 	types "k8s.io/apimachinery/pkg/types"
 	watch "k8s.io/apimachinery/pkg/watch"
 	testing "k8s.io/client-go/testing"
+
 	v1beta1 "vitess.io/vitess/go/vt/topo/k8stopo/apis/topo/v1beta1"
 )
 
diff --git a/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/topo_client.go b/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/topo_client.go
index 4a94ffe7d6..55b78f6fd1 100644
--- a/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/topo_client.go
+++ b/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/topo_client.go
@@ -20,6 +20,7 @@ package v1beta1
 
 import (
 	rest "k8s.io/client-go/rest"
+
 	v1beta1 "vitess.io/vitess/go/vt/topo/k8stopo/apis/topo/v1beta1"
 	"vitess.io/vitess/go/vt/topo/k8stopo/client/clientset/versioned/scheme"
 )
diff --git a/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/vitesstoponode.go b/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/vitesstoponode.go
index f790824866..7b458f7dfe 100644
--- a/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/vitesstoponode.go
+++ b/go/vt/topo/k8stopo/client/clientset/versioned/typed/topo/v1beta1/vitesstoponode.go
@@ -26,6 +26,7 @@ import (
 	types "k8s.io/apimachinery/pkg/types"
 	watch "k8s.io/apimachinery/pkg/watch"
 	rest "k8s.io/client-go/rest"
+
 	v1beta1 "vitess.io/vitess/go/vt/topo/k8stopo/apis/topo/v1beta1"
 	scheme "vitess.io/vitess/go/vt/topo/k8stopo/client/clientset/versioned/scheme"
 )
diff --git a/go/vt/topo/k8stopo/client/informers/externalversions/factory.go b/go/vt/topo/k8stopo/client/informers/externalversions/factory.go
index b276971816..5c5886daed 100644
--- a/go/vt/topo/k8stopo/client/informers/externalversions/factory.go
+++ b/go/vt/topo/k8stopo/client/informers/externalversions/factory.go
@@ -27,6 +27,7 @@ import (
 	runtime "k8s.io/apimachinery/pkg/runtime"
 	schema "k8s.io/apimachinery/pkg/runtime/schema"
 	cache "k8s.io/client-go/tools/cache"
+
 	versioned "vitess.io/vitess/go/vt/topo/k8stopo/client/clientset/versioned"
 	internalinterfaces "vitess.io/vitess/go/vt/topo/k8stopo/client/informers/externalversions/internalinterfaces"
 	topo "vitess.io/vitess/go/vt/topo/k8stopo/client/informers/externalversions/topo"
diff --git a/go/vt/topo/k8stopo/client/informers/externalversions/generic.go b/go/vt/topo/k8stopo/client/informers/externalversions/generic.go
index 005272fb66..8064882a6b 100644
--- a/go/vt/topo/k8stopo/client/informers/externalversions/generic.go
+++ b/go/vt/topo/k8stopo/client/informers/externalversions/generic.go
@@ -23,6 +23,7 @@ import (
 
 	schema "k8s.io/apimachinery/pkg/runtime/schema"
 	cache "k8s.io/client-go/tools/cache"
+
 	v1beta1 "vitess.io/vitess/go/vt/topo/k8stopo/apis/topo/v1beta1"
 )
 
diff --git a/go/vt/topo/k8stopo/client/informers/externalversions/internalinterfaces/factory_interfaces.go b/go/vt/topo/k8stopo/client/informers/externalversions/internalinterfaces/factory_interfaces.go
index 51a70f9174..ca90aa8983 100644
--- a/go/vt/topo/k8stopo/client/informers/externalversions/internalinterfaces/factory_interfaces.go
+++ b/go/vt/topo/k8stopo/client/informers/externalversions/internalinterfaces/factory_interfaces.go
@@ -24,6 +24,7 @@ import (
 	v1 "k8s.io/apimachinery/pkg/apis/meta/v1"
 	runtime "k8s.io/apimachinery/pkg/runtime"
 	cache "k8s.io/client-go/tools/cache"
+
 	versioned "vitess.io/vitess/go/vt/topo/k8stopo/client/clientset/versioned"
 )
 
diff --git a/go/vt/topo/k8stopo/client/informers/externalversions/topo/v1beta1/vitesstoponode.go b/go/vt/topo/k8stopo/client/informers/externalversions/topo/v1beta1/vitesstoponode.go
index 948024afaf..af6e8b17ac 100644
--- a/go/vt/topo/k8stopo/client/informers/externalversions/topo/v1beta1/vitesstoponode.go
+++ b/go/vt/topo/k8stopo/client/informers/externalversions/topo/v1beta1/vitesstoponode.go
@@ -26,6 +26,7 @@ import (
 	runtime "k8s.io/apimachinery/pkg/runtime"
 	watch "k8s.io/apimachinery/pkg/watch"
 	cache "k8s.io/client-go/tools/cache"
+
 	topov1beta1 "vitess.io/vitess/go/vt/topo/k8stopo/apis/topo/v1beta1"
 	versioned "vitess.io/vitess/go/vt/topo/k8stopo/client/clientset/versioned"
 	internalinterfaces "vitess.io/vitess/go/vt/topo/k8stopo/client/informers/externalversions/internalinterfaces"
diff --git a/go/vt/topo/k8stopo/client/listers/topo/v1beta1/vitesstoponode.go b/go/vt/topo/k8stopo/client/listers/topo/v1beta1/vitesstoponode.go
index 3859fe4b36..edf3033350 100644
--- a/go/vt/topo/k8stopo/client/listers/topo/v1beta1/vitesstoponode.go
+++ b/go/vt/topo/k8stopo/client/listers/topo/v1beta1/vitesstoponode.go
@@ -22,6 +22,7 @@ import (
 	"k8s.io/apimachinery/pkg/api/errors"
 	"k8s.io/apimachinery/pkg/labels"
 	"k8s.io/client-go/tools/cache"
+
 	v1beta1 "vitess.io/vitess/go/vt/topo/k8stopo/apis/topo/v1beta1"
 )
 
diff --git a/go/vt/vtgate/engine/concatenate.go b/go/vt/vtgate/engine/concatenate.go
index 1a1c20b079..1336e43fac 100644
--- a/go/vt/vtgate/engine/concatenate.go
+++ b/go/vt/vtgate/engine/concatenate.go
@@ -63,9 +63,10 @@ func formatTwoOptionsNicely(a, b string) string {
 	return a + "_" + b
 }
 
-var errWrongNumberOfColumnsInSelect = vterrors.NewErrorf(vtrpcpb.Code_FAILED_PRECONDITION, vterrors.WrongNumberOfColumnsInSelect, "The used SELECT statements have a different number of columns")
+// ErrWrongNumberOfColumnsInSelect is an error
+var ErrWrongNumberOfColumnsInSelect = vterrors.NewErrorf(vtrpcpb.Code_FAILED_PRECONDITION, vterrors.WrongNumberOfColumnsInSelect, "The used SELECT statements have a different number of columns")
 
-// Execute performs a non-streaming exec.
+// TryExecute performs a non-streaming exec.
 func (c *Concatenate) TryExecute(vcursor VCursor, bindVars map[string]*querypb.BindVariable, wantfields bool) (*sqltypes.Result, error) {
 	res, err := c.execSources(vcursor, bindVars, wantfields)
 	if err != nil {
@@ -86,7 +87,7 @@ func (c *Concatenate) TryExecute(vcursor VCursor, bindVars map[string]*querypb.B
 		if len(rows) > 0 &&
 			len(r.Rows) > 0 &&
 			len(rows[0]) != len(r.Rows[0]) {
-			return nil, errWrongNumberOfColumnsInSelect
+			return nil, ErrWrongNumberOfColumnsInSelect
 		}
 
 		rows = append(rows, r.Rows...)
@@ -139,7 +140,7 @@ func (c *Concatenate) execSources(vcursor VCursor, bindVars map[string]*querypb.
 	return results, nil
 }
 
-// StreamExecute performs a streaming exec.
+// TryStreamExecute performs a streaming exec.
 func (c *Concatenate) TryStreamExecute(vcursor VCursor, bindVars map[string]*querypb.BindVariable, wantfields bool, callback func(*sqltypes.Result) error) error {
 	var seenFields []*querypb.Field
 	var fieldset sync.WaitGroup
@@ -235,7 +236,7 @@ func (c *Concatenate) description() PrimitiveDescription {
 
 func compareFields(fields1 []*querypb.Field, fields2 []*querypb.Field) error {
 	if len(fields1) != len(fields2) {
-		return errWrongNumberOfColumnsInSelect
+		return ErrWrongNumberOfColumnsInSelect
 	}
 	for i, field2 := range fields2 {
 		field1 := fields1[i]
diff --git a/go/vt/vtgate/planbuilder/abstract/derived.go b/go/vt/vtgate/planbuilder/abstract/derived.go
index 1ee993754a..01c28f9171 100644
--- a/go/vt/vtgate/planbuilder/abstract/derived.go
+++ b/go/vt/vtgate/planbuilder/abstract/derived.go
@@ -17,7 +17,9 @@ limitations under the License.
 package abstract
 
 import (
+	vtrpcpb "vitess.io/vitess/go/vt/proto/vtrpc"
 	"vitess.io/vitess/go/vt/sqlparser"
+	"vitess.io/vitess/go/vt/vterrors"
 	"vitess.io/vitess/go/vt/vtgate/semantics"
 )
 
@@ -39,6 +41,9 @@ func (d *Derived) TableID() semantics.TableSet {
 func (d *Derived) PushPredicate(expr sqlparser.Expr, semTable *semantics.SemTable) error {
 	tableInfo, err := semTable.TableInfoForExpr(expr)
 	if err != nil {
+		if err == semantics.ErrMultipleTables {
+			return semantics.ProjError{Inner: vterrors.Errorf(vtrpcpb.Code_UNIMPLEMENTED, "unsupported: unable to split predicates to derived table: %s", sqlparser.String(expr))}
+		}
 		return err
 	}
 
diff --git a/go/vt/vtgate/planbuilder/abstract/join.go b/go/vt/vtgate/planbuilder/abstract/join.go
index fc842f1065..788b3dc93f 100644
--- a/go/vt/vtgate/planbuilder/abstract/join.go
+++ b/go/vt/vtgate/planbuilder/abstract/join.go
@@ -31,7 +31,7 @@ var _ Operator = (*Join)(nil)
 
 // PushPredicate implements the Operator interface
 func (j *Join) PushPredicate(expr sqlparser.Expr, semTable *semantics.SemTable) error {
-	deps := semTable.BaseTableDependencies(expr)
+	deps := semTable.RecursiveDeps(expr)
 	switch {
 	case deps.IsSolvedBy(j.LHS.TableID()):
 		return j.LHS.PushPredicate(expr, semTable)
@@ -55,13 +55,13 @@ func (j *Join) UnsolvedPredicates(semTable *semantics.SemTable) []sqlparser.Expr
 	ts := j.TableID()
 	var result []sqlparser.Expr
 	for _, expr := range j.LHS.UnsolvedPredicates(semTable) {
-		deps := semTable.Dependencies(expr)
+		deps := semTable.DirectDeps(expr)
 		if !deps.IsSolvedBy(ts) {
 			result = append(result, expr)
 		}
 	}
 	for _, expr := range j.RHS.UnsolvedPredicates(semTable) {
-		deps := semTable.Dependencies(expr)
+		deps := semTable.DirectDeps(expr)
 		if !deps.IsSolvedBy(ts) {
 			result = append(result, expr)
 		}
diff --git a/go/vt/vtgate/planbuilder/abstract/left_join.go b/go/vt/vtgate/planbuilder/abstract/left_join.go
index 73369b2e9e..2b992010af 100644
--- a/go/vt/vtgate/planbuilder/abstract/left_join.go
+++ b/go/vt/vtgate/planbuilder/abstract/left_join.go
@@ -31,7 +31,7 @@ var _ Operator = (*LeftJoin)(nil)
 
 // PushPredicate implements the Operator interface
 func (oj *LeftJoin) PushPredicate(expr sqlparser.Expr, semTable *semantics.SemTable) error {
-	deps := semTable.BaseTableDependencies(expr)
+	deps := semTable.RecursiveDeps(expr)
 	if deps.IsSolvedBy(oj.Left.TableID()) {
 		return oj.Left.PushPredicate(expr, semTable)
 	}
@@ -49,13 +49,13 @@ func (oj *LeftJoin) UnsolvedPredicates(semTable *semantics.SemTable) []sqlparser
 	ts := oj.TableID()
 	var result []sqlparser.Expr
 	for _, expr := range oj.Left.UnsolvedPredicates(semTable) {
-		deps := semTable.Dependencies(expr)
+		deps := semTable.DirectDeps(expr)
 		if !deps.IsSolvedBy(ts) {
 			result = append(result, expr)
 		}
 	}
 	for _, expr := range oj.Right.UnsolvedPredicates(semTable) {
-		deps := semTable.Dependencies(expr)
+		deps := semTable.DirectDeps(expr)
 		if !deps.IsSolvedBy(ts) {
 			result = append(result, expr)
 		}
diff --git a/go/vt/vtgate/planbuilder/abstract/querygraph.go b/go/vt/vtgate/planbuilder/abstract/querygraph.go
index 68e6d1e838..fa0a786cc9 100644
--- a/go/vt/vtgate/planbuilder/abstract/querygraph.go
+++ b/go/vt/vtgate/planbuilder/abstract/querygraph.go
@@ -106,7 +106,7 @@ func (qg *QueryGraph) collectPredicates(sel *sqlparser.Select, semTable *semanti
 }
 
 func (qg *QueryGraph) collectPredicate(predicate sqlparser.Expr, semTable *semantics.SemTable) error {
-	deps := semTable.BaseTableDependencies(predicate)
+	deps := semTable.RecursiveDeps(predicate)
 	switch deps.NumberOfTables() {
 	case 0:
 		qg.addNoDepsPredicate(predicate)
diff --git a/go/vt/vtgate/planbuilder/abstract/queryprojection.go b/go/vt/vtgate/planbuilder/abstract/queryprojection.go
index 7f9e322202..ebd731b71b 100644
--- a/go/vt/vtgate/planbuilder/abstract/queryprojection.go
+++ b/go/vt/vtgate/planbuilder/abstract/queryprojection.go
@@ -28,7 +28,7 @@ import (
 type (
 	// SelectExpr provides whether the columns is aggregation expression or not.
 	SelectExpr struct {
-		Col  *sqlparser.AliasedExpr
+		Col  sqlparser.SelectExpr
 		Aggr bool
 	}
 
@@ -41,6 +41,7 @@ type (
 		GroupByExprs       []GroupBy
 		OrderExprs         []OrderBy
 		CanPushDownSorting bool
+		HasStar            bool
 	}
 
 	// OrderBy contains the expression to used in order by and also if ordering is needed at VTGate level then what the weight_string function expression to be sent down for evaluation.
@@ -60,35 +61,44 @@ type (
 	}
 )
 
+// GetExpr returns the underlying sqlparser.Expr of our SelectExpr
+func (s SelectExpr) GetExpr() (sqlparser.Expr, error) {
+	switch sel := s.Col.(type) {
+	case *sqlparser.StarExpr:
+		return nil, vterrors.New(vtrpcpb.Code_INTERNAL, "starExpr does not have expr")
+	case *sqlparser.AliasedExpr:
+		return sel.Expr, nil
+	case *sqlparser.Nextval:
+		return sel.Expr, nil
+	}
+	return nil, nil
+}
+
+// GetAliasedExpr returns the SelectExpr as a *sqlparser.AliasedExpr if its type allows it,
+// otherwise an error is returned.
+func (s SelectExpr) GetAliasedExpr() (*sqlparser.AliasedExpr, error) {
+	switch expr := s.Col.(type) {
+	case *sqlparser.AliasedExpr:
+		return expr, nil
+	case *sqlparser.StarExpr:
+		return nil, vterrors.Errorf(vtrpcpb.Code_UNIMPLEMENTED, "unsupported: '*' expression in cross-shard query")
+	default:
+		return nil, vterrors.Errorf(vtrpcpb.Code_UNIMPLEMENTED, "not an aliased expression: %T", expr)
+	}
+}
+
 // CreateQPFromSelect creates the QueryProjection for the input *sqlparser.Select
 func CreateQPFromSelect(sel *sqlparser.Select, semTable *semantics.SemTable) (*QueryProjection, error) {
 	qp := &QueryProjection{
 		Distinct: sel.Distinct,
 	}
 
-	for _, selExp := range sel.SelectExprs {
-		exp, ok := selExp.(*sqlparser.AliasedExpr)
-		if !ok {
-			return nil, semantics.Gen4NotSupportedF("%T in select list", selExp)
-		}
-
-		err := checkForInvalidAggregations(exp)
-		if err != nil {
-			return nil, err
-		}
-		col := SelectExpr{
-			Col: exp,
-		}
-		if sqlparser.ContainsAggregation(exp.Expr) {
-			col.Aggr = true
-			qp.HasAggr = true
-		}
-
-		qp.SelectExprs = append(qp.SelectExprs, col)
+	err := qp.addSelectExpressions(sel)
+	if err != nil {
+		return nil, err
 	}
-
 	for _, group := range sel.GroupBy {
-		expr, weightStrExpr, err := qp.getSimplifiedExpr(group)
+		expr, weightStrExpr, err := qp.getSimplifiedExpr(group, semTable)
 		if err != nil {
 			return nil, err
 		}
@@ -98,7 +108,7 @@ func CreateQPFromSelect(sel *sqlparser.Select, semTable *semantics.SemTable) (*Q
 		qp.GroupByExprs = append(qp.GroupByExprs, GroupBy{Inner: expr, WeightStrExpr: weightStrExpr})
 	}
 
-	err := qp.addOrderBy(sel.OrderBy, semTable)
+	err = qp.addOrderBy(sel.OrderBy, semTable)
 	if err != nil {
 		return nil, err
 	}
@@ -122,23 +132,47 @@ func CreateQPFromSelect(sel *sqlparser.Select, semTable *semantics.SemTable) (*Q
 	return qp, nil
 }
 
+func (qp *QueryProjection) addSelectExpressions(sel *sqlparser.Select) error {
+	for _, selExp := range sel.SelectExprs {
+		switch selExp := selExp.(type) {
+		case *sqlparser.AliasedExpr:
+			err := checkForInvalidAggregations(selExp)
+			if err != nil {
+				return err
+			}
+			col := SelectExpr{
+				Col: selExp,
+			}
+			if sqlparser.ContainsAggregation(selExp.Expr) {
+				col.Aggr = true
+				qp.HasAggr = true
+			}
+
+			qp.SelectExprs = append(qp.SelectExprs, col)
+		case *sqlparser.StarExpr:
+			qp.HasStar = true
+			col := SelectExpr{
+				Col: selExp,
+			}
+			qp.SelectExprs = append(qp.SelectExprs, col)
+		default:
+			return semantics.Gen4NotSupportedF("%T in select list", selExp)
+		}
+	}
+	return nil
+}
+
 // CreateQPFromUnion creates the QueryProjection for the input *sqlparser.Union
 func CreateQPFromUnion(union *sqlparser.Union, semTable *semantics.SemTable) (*QueryProjection, error) {
 	qp := &QueryProjection{}
 
 	sel := sqlparser.GetFirstSelect(union)
-	for _, selExp := range sel.SelectExprs {
-		exp, ok := selExp.(*sqlparser.AliasedExpr)
-		if !ok {
-			return nil, semantics.Gen4NotSupportedF("%T in select list", selExp)
-		}
-		col := SelectExpr{
-			Col: exp,
-		}
-		qp.SelectExprs = append(qp.SelectExprs, col)
+	err := qp.addSelectExpressions(sel)
+	if err != nil {
+		return nil, err
 	}
 
-	err := qp.addOrderBy(union.OrderBy, semTable)
+	err = qp.addOrderBy(union.OrderBy, semTable)
 	if err != nil {
 		return nil, err
 	}
@@ -149,7 +183,7 @@ func CreateQPFromUnion(union *sqlparser.Union, semTable *semantics.SemTable) (*Q
 func (qp *QueryProjection) addOrderBy(orderBy sqlparser.OrderBy, semTable *semantics.SemTable) error {
 	canPushDownSorting := true
 	for _, order := range orderBy {
-		expr, weightStrExpr, err := qp.getSimplifiedExpr(order.Expr)
+		expr, weightStrExpr, err := qp.getSimplifiedExpr(order.Expr, semTable)
 		if err != nil {
 			return err
 		}
@@ -178,20 +212,24 @@ func checkForInvalidAggregations(exp *sqlparser.AliasedExpr) error {
 	}, exp.Expr)
 }
 
-func (qp *QueryProjection) getNonAggrExprNotMatchingGroupByExprs() sqlparser.Expr {
+func (qp *QueryProjection) getNonAggrExprNotMatchingGroupByExprs() sqlparser.SelectExpr {
 	for _, expr := range qp.SelectExprs {
 		if expr.Aggr {
 			continue
 		}
 		isGroupByOk := false
 		for _, groupByExpr := range qp.GroupByExprs {
-			if sqlparser.EqualsExpr(groupByExpr.WeightStrExpr, expr.Col.Expr) {
+			exp, err := expr.GetExpr()
+			if err != nil {
+				return expr.Col
+			}
+			if sqlparser.EqualsExpr(groupByExpr.WeightStrExpr, exp) {
 				isGroupByOk = true
 				break
 			}
 		}
 		if !isGroupByOk {
-			return expr.Col.Expr
+			return expr.Col
 		}
 	}
 	for _, order := range qp.OrderExprs {
@@ -207,7 +245,9 @@ func (qp *QueryProjection) getNonAggrExprNotMatchingGroupByExprs() sqlparser.Exp
 			}
 		}
 		if !isGroupByOk {
-			return order.Inner.Expr
+			return &sqlparser.AliasedExpr{
+				Expr: order.Inner.Expr,
+			}
 		}
 	}
 	return nil
@@ -215,16 +255,20 @@ func (qp *QueryProjection) getNonAggrExprNotMatchingGroupByExprs() sqlparser.Exp
 
 // getSimplifiedExpr takes an expression used in ORDER BY or GROUP BY, which can reference both aliased columns and
 // column offsets, and returns an expression that is simpler to evaluate
-func (qp *QueryProjection) getSimplifiedExpr(e sqlparser.Expr) (expr sqlparser.Expr, weightStrExpr sqlparser.Expr, err error) {
+func (qp *QueryProjection) getSimplifiedExpr(e sqlparser.Expr, semTable *semantics.SemTable) (expr sqlparser.Expr, weightStrExpr sqlparser.Expr, err error) {
 	// If the ORDER BY is against a column alias, we need to remember the expression
 	// behind the alias. The weightstring(.) calls needs to be done against that expression and not the alias.
 	// Eg - select music.foo as bar, weightstring(music.foo) from music order by bar
 	colExpr, isColName := e.(*sqlparser.ColName)
 	if isColName && colExpr.Qualifier.IsEmpty() {
 		for _, selectExpr := range qp.SelectExprs {
-			isAliasExpr := !selectExpr.Col.As.IsEmpty()
-			if isAliasExpr && colExpr.Name.Equal(selectExpr.Col.As) {
-				return e, selectExpr.Col.Expr, nil
+			aliasedExpr, isAliasedExpr := selectExpr.Col.(*sqlparser.AliasedExpr)
+			if !isAliasedExpr {
+				continue
+			}
+			isAliasExpr := !aliasedExpr.As.IsEmpty()
+			if isAliasExpr && colExpr.Name.Equal(aliasedExpr.As) {
+				return e, aliasedExpr.Expr, nil
 			}
 		}
 	}
@@ -252,15 +296,11 @@ func (qp *QueryProjection) toString() string {
 	}
 
 	for _, expr := range qp.SelectExprs {
-		e := sqlparser.String(expr.Col.Expr)
+		e := sqlparser.String(expr.Col)
 
 		if expr.Aggr {
 			e = "aggr: " + e
 		}
-
-		if !expr.Col.As.IsEmpty() {
-			e += " AS " + expr.Col.As.String()
-		}
 		out.Select = append(out.Select, e)
 	}
 
diff --git a/go/vt/vtgate/planbuilder/abstract/subquery.go b/go/vt/vtgate/planbuilder/abstract/subquery.go
index e10b271974..277e9dcb9a 100644
--- a/go/vt/vtgate/planbuilder/abstract/subquery.go
+++ b/go/vt/vtgate/planbuilder/abstract/subquery.go
@@ -58,14 +58,14 @@ func (s *SubQuery) UnsolvedPredicates(semTable *semantics.SemTable) []sqlparser.
 	var result []sqlparser.Expr
 
 	for _, expr := range s.Outer.UnsolvedPredicates(semTable) {
-		deps := semTable.Dependencies(expr)
+		deps := semTable.DirectDeps(expr)
 		if !deps.IsSolvedBy(ts) {
 			result = append(result, expr)
 		}
 	}
 	for _, inner := range s.Inner {
 		for _, expr := range inner.Inner.UnsolvedPredicates(semTable) {
-			deps := semTable.Dependencies(expr)
+			deps := semTable.DirectDeps(expr)
 			if !deps.IsSolvedBy(ts) {
 				result = append(result, expr)
 			}
diff --git a/go/vt/vtgate/planbuilder/abstract/vindex.go b/go/vt/vtgate/planbuilder/abstract/vindex.go
index 892fb802ee..47c3ac1b84 100644
--- a/go/vt/vtgate/planbuilder/abstract/vindex.go
+++ b/go/vt/vtgate/planbuilder/abstract/vindex.go
@@ -57,7 +57,7 @@ const vindexUnsupported = "unsupported: where clause for vindex function must be
 // PushPredicate implements the Operator interface
 func (v *Vindex) PushPredicate(expr sqlparser.Expr, semTable *semantics.SemTable) error {
 	for _, e := range sqlparser.SplitAndExpression(nil, expr) {
-		deps := semTable.BaseTableDependencies(e)
+		deps := semTable.RecursiveDeps(e)
 		if deps.NumberOfTables() > 1 {
 			return vterrors.Errorf(vtrpcpb.Code_UNIMPLEMENTED, vindexUnsupported+" (multiple tables involved)")
 		}
diff --git a/go/vt/vtgate/planbuilder/derivedtree.go b/go/vt/vtgate/planbuilder/derivedtree.go
index 32ae9ab085..8a60065333 100644
--- a/go/vt/vtgate/planbuilder/derivedtree.go
+++ b/go/vt/vtgate/planbuilder/derivedtree.go
@@ -27,6 +27,9 @@ type derivedTree struct {
 	query sqlparser.SelectStatement
 	inner queryTree
 	alias string
+
+	// columns needed to feed other plans
+	columns []*sqlparser.ColName
 }
 
 var _ queryTree = (*derivedTree)(nil)
@@ -45,35 +48,62 @@ func (d *derivedTree) clone() queryTree {
 	return &other
 }
 
-func (d *derivedTree) pushOutputColumns(names []*sqlparser.ColName, _ *semantics.SemTable) (offsets []int, err error) {
+func (d *derivedTree) pushOutputColumns(names []*sqlparser.ColName, semTable *semantics.SemTable) (offsets []int, err error) {
+	var noQualifierNames []*sqlparser.ColName
+	if len(names) == 0 {
+		return
+	}
 	for _, name := range names {
-		offset, err := d.findOutputColumn(name)
+		i, err := d.findOutputColumn(name)
 		if err != nil {
 			return nil, err
 		}
-		offsets = append(offsets, offset)
+		if i > -1 {
+			offsets = append(offsets, i)
+			continue
+		}
+		offsets = append(offsets, len(d.columns))
+		d.columns = append(d.columns, name)
+		noQualifierNames = append(noQualifierNames, sqlparser.NewColName(name.Name.String()))
+	}
+	if len(noQualifierNames) > 0 {
+		_, _ = d.inner.pushOutputColumns(noQualifierNames, semTable)
 	}
 	return
 }
 
+// findOutputColumn returns the index on which the given name is found in the slice of
+// *sqlparser.SelectExprs of the derivedTree. The *sqlparser.SelectExpr must be of type
+// *sqlparser.AliasedExpr and match the given name.
+// If name is not present but the query's select expressions contain a *sqlparser.StarExpr
+// the function will return no error and an index equal to -1.
+// If name is not present and the query does not have a *sqlparser.StarExpr, the function
+// will return an unknown column error.
 func (d *derivedTree) findOutputColumn(name *sqlparser.ColName) (int, error) {
+	hasStar := false
 	for j, exp := range sqlparser.GetFirstSelect(d.query).SelectExprs {
-		ae, ok := exp.(*sqlparser.AliasedExpr)
-		if !ok {
-			return 0, vterrors.Errorf(vtrpcpb.Code_INTERNAL, "expected AliasedExpr")
-		}
-		if !ae.As.IsEmpty() && ae.As.Equal(name.Name) {
-			return j, nil
-		}
-		if ae.As.IsEmpty() {
-			col, ok := ae.Expr.(*sqlparser.ColName)
-			if !ok {
-				return 0, vterrors.Errorf(vtrpcpb.Code_UNIMPLEMENTED, "complex expression needs column alias: %s", sqlparser.String(ae))
-			}
-			if name.Name.Equal(col.Name) {
+		switch exp := exp.(type) {
+		case *sqlparser.AliasedExpr:
+			if !exp.As.IsEmpty() && exp.As.Equal(name.Name) {
 				return j, nil
 			}
+			if exp.As.IsEmpty() {
+				col, ok := exp.Expr.(*sqlparser.ColName)
+				if !ok {
+					return 0, vterrors.Errorf(vtrpcpb.Code_UNIMPLEMENTED, "complex expression needs column alias: %s", sqlparser.String(exp))
+				}
+				if name.Name.Equal(col.Name) {
+					return j, nil
+				}
+			}
+		case *sqlparser.StarExpr:
+			hasStar = true
 		}
 	}
+
+	// we have found a star but no matching *sqlparser.AliasedExpr, thus we return -1 with no error.
+	if hasStar {
+		return -1, nil
+	}
 	return 0, vterrors.NewErrorf(vtrpcpb.Code_NOT_FOUND, vterrors.BadFieldError, "Unknown column '%s' in 'field list'", name.Name.String())
 }
diff --git a/go/vt/vtgate/planbuilder/gen4_planner.go b/go/vt/vtgate/planbuilder/gen4_planner.go
index b17ac73a36..3bc37e64d2 100644
--- a/go/vt/vtgate/planbuilder/gen4_planner.go
+++ b/go/vt/vtgate/planbuilder/gen4_planner.go
@@ -218,7 +218,7 @@ func planHorizon(ctx planningContext, plan logicalPlan, in sqlparser.SelectState
 			return nil, ctx.semTable.ProjectionErr
 		}
 		if isRoute && rb.isSingleShard() {
-			err = createSingleShardRoutePlan(node, rb)
+			err = planSingleShardRoutePlan(node, rb)
 		} else {
 			plan, err = planOrderByOnUnion(ctx, plan, node)
 		}
diff --git a/go/vt/vtgate/planbuilder/horizon_planning.go b/go/vt/vtgate/planbuilder/horizon_planning.go
index 8d4cb12f7b..ba77c8039b 100644
--- a/go/vt/vtgate/planbuilder/horizon_planning.go
+++ b/go/vt/vtgate/planbuilder/horizon_planning.go
@@ -39,13 +39,13 @@ type horizonPlanning struct {
 }
 
 func (hp *horizonPlanning) planHorizon(ctx planningContext, plan logicalPlan) (logicalPlan, error) {
-	rb, ok := plan.(*route)
-	if !ok && ctx.semTable.ProjectionErr != nil {
+	rb, isRoute := plan.(*route)
+	if !isRoute && ctx.semTable.ProjectionErr != nil {
 		return nil, ctx.semTable.ProjectionErr
 	}
 
-	if ok && rb.isSingleShard() {
-		err := createSingleShardRoutePlan(hp.sel, rb)
+	if isRoute && rb.isSingleShard() {
+		err := planSingleShardRoutePlan(hp.sel, rb)
 		if err != nil {
 			return nil, err
 		}
@@ -63,7 +63,10 @@ func (hp *horizonPlanning) planHorizon(ctx planningContext, plan logicalPlan) (l
 		return nil, err
 	}
 
-	if hp.qp.NeedsAggregation() || hp.sel.Having != nil {
+	needAggrOrHaving := hp.qp.NeedsAggregation() || hp.sel.Having != nil
+	canShortcut := isRoute && !needAggrOrHaving && len(hp.qp.OrderExprs) == 0
+
+	if needAggrOrHaving {
 		plan, err = hp.planAggregations(ctx, plan)
 		if err != nil {
 			return nil, err
@@ -76,24 +79,35 @@ func (hp *horizonPlanning) planHorizon(ctx planningContext, plan logicalPlan) (l
 				eSimpleProj:       &engine.SimpleProjection{},
 			}
 		}
-		for _, e := range hp.qp.SelectExprs {
-			if _, _, err := pushProjection(e.Col, plan, ctx.semTable, true, false); err != nil {
+
+		if canShortcut {
+			err = planSingleShardRoutePlan(hp.sel, rb)
+			if err != nil {
+				return nil, err
+			}
+		} else {
+			err = pushProjections(ctx, plan, hp.qp.SelectExprs)
+			if err != nil {
 				return nil, err
 			}
 		}
 	}
 
-	if len(hp.qp.OrderExprs) > 0 {
-		plan, err = hp.planOrderBy(ctx, hp.qp.OrderExprs, plan)
-		if err != nil {
-			return nil, err
+	// If we have done the shortcut that means we already planned order by
+	// and group by, thus we don't need to do it again.
+	if !canShortcut {
+		if len(hp.qp.OrderExprs) > 0 {
+			plan, err = hp.planOrderBy(ctx, hp.qp.OrderExprs, plan)
+			if err != nil {
+				return nil, err
+			}
 		}
-	}
 
-	if hp.qp.CanPushDownSorting && hp.vtgateGrouping {
-		plan, err = hp.planOrderByUsingGroupBy(ctx, plan)
-		if err != nil {
-			return nil, err
+		if hp.qp.CanPushDownSorting && hp.vtgateGrouping {
+			plan, err = hp.planGroupByUsingOrderBy(ctx, plan)
+			if err != nil {
+				return nil, err
+			}
 		}
 	}
 
@@ -110,6 +124,19 @@ func (hp *horizonPlanning) planHorizon(ctx planningContext, plan logicalPlan) (l
 	return plan, nil
 }
 
+func pushProjections(ctx planningContext, plan logicalPlan, selectExprs []abstract.SelectExpr) error {
+	for _, e := range selectExprs {
+		aliasExpr, err := e.GetAliasedExpr()
+		if err != nil {
+			return err
+		}
+		if _, _, err := pushProjection(aliasExpr, plan, ctx.semTable, true, false); err != nil {
+			return err
+		}
+	}
+	return nil
+}
+
 func (hp *horizonPlanning) truncateColumnsIfNeeded(plan logicalPlan) error {
 	if !hp.needsTruncation {
 		return nil
@@ -162,7 +189,7 @@ func pushProjection(expr *sqlparser.AliasedExpr, plan logicalPlan, semTable *sem
 	case *joinGen4:
 		lhsSolves := node.Left.ContainsTables()
 		rhsSolves := node.Right.ContainsTables()
-		deps := semTable.BaseTableDependencies(expr.Expr)
+		deps := semTable.RecursiveDeps(expr.Expr)
 		var column int
 		var appended bool
 		passDownReuseCol := reuseCol
@@ -242,7 +269,7 @@ func removeKeyspaceFromColName(expr *sqlparser.AliasedExpr) *sqlparser.AliasedEx
 }
 
 func checkIfAlreadyExists(expr *sqlparser.AliasedExpr, node sqlparser.SelectStatement, semTable *semantics.SemTable) int {
-	exprDep := semTable.BaseTableDependencies(expr.Expr)
+	exprDep := semTable.RecursiveDeps(expr.Expr)
 	// Here to find if the expr already exists in the SelectStatement, we have 3 cases
 	// input is a Select -> In this case we want to search in the select
 	// input is a Union -> In this case we want to search in the First Select of the Union
@@ -258,7 +285,7 @@ func checkIfAlreadyExists(expr *sqlparser.AliasedExpr, node sqlparser.SelectStat
 
 		selectExprCol, isSelectExprCol := selectExpr.Expr.(*sqlparser.ColName)
 		exprCol, isExprCol := expr.Expr.(*sqlparser.ColName)
-		selectExprDep := semTable.BaseTableDependencies(selectExpr.Expr)
+		selectExprDep := semTable.RecursiveDeps(selectExpr.Expr)
 
 		// Check that the two expressions have the same dependencies
 		if selectExprDep != exprDep {
@@ -307,16 +334,21 @@ func (hp *horizonPlanning) planAggregations(ctx planningContext, plan logicalPla
 	}
 
 	for _, e := range hp.qp.SelectExprs {
+		aliasExpr, err := e.GetAliasedExpr()
+		if err != nil {
+			return nil, err
+		}
+
 		// push all expression if they are non-aggregating or the plan is not ordered aggregated plan.
 		if !e.Aggr || oa == nil {
-			_, _, err := pushProjection(e.Col, plan, ctx.semTable, true, false)
+			_, _, err := pushProjection(aliasExpr, plan, ctx.semTable, true, false)
 			if err != nil {
 				return nil, err
 			}
 			continue
 		}
 
-		fExpr, isFunc := e.Col.Expr.(*sqlparser.FuncExpr)
+		fExpr, isFunc := aliasExpr.Expr.(*sqlparser.FuncExpr)
 		if !isFunc {
 			return nil, vterrors.Errorf(vtrpcpb.Code_UNIMPLEMENTED, "unsupported: in scatter query: complex aggregate expression")
 		}
@@ -383,7 +415,10 @@ func (hp *horizonPlanning) planAggregations(ctx planningContext, plan logicalPla
 	if _, planIsRoute := plan.(*route); !planIsRoute {
 		// if we had to build up additional operators around the route, we have to fail this query
 		for _, expr := range hp.qp.SelectExprs {
-			colExpr := expr.Col.Expr
+			colExpr, err := expr.GetExpr()
+			if err != nil {
+				return nil, err
+			}
 			if !sqlparser.IsAggregation(colExpr) && sqlparser.ContainsAggregation(colExpr) {
 				return nil, vterrors.New(vtrpcpb.Code_UNIMPLEMENTED, "unsupported: in scatter query: complex aggregate expression")
 			}
@@ -402,15 +437,18 @@ func (hp *horizonPlanning) createPushExprAndAlias(
 	opcode engine.AggregateOpcode,
 	oa *orderedAggregate,
 ) (*sqlparser.AliasedExpr, string, engine.AggregateOpcode) {
-	pushExpr := expr.Col
+	aliasExpr, isAlias := expr.Col.(*sqlparser.AliasedExpr)
+	if !isAlias {
+		return nil, "", 0
+	}
 	var alias string
-	if expr.Col.As.IsEmpty() {
-		alias = sqlparser.String(expr.Col.Expr)
+	if aliasExpr.As.IsEmpty() {
+		alias = sqlparser.String(aliasExpr.Expr)
 	} else {
-		alias = expr.Col.As.String()
+		alias = aliasExpr.As.String()
 	}
 	if handleDistinct {
-		pushExpr = innerAliased
+		aliasExpr = innerAliased
 
 		switch opcode {
 		case engine.AggregateCount:
@@ -428,7 +466,7 @@ func (hp *horizonPlanning) createPushExprAndAlias(
 		}
 		hp.qp.GroupByExprs = append(hp.qp.GroupByExprs, by)
 	}
-	return pushExpr, alias, opcode
+	return aliasExpr, alias, opcode
 }
 
 func hasUniqueVindex(vschema ContextVSchema, semTable *semantics.SemTable, groupByExprs []abstract.GroupBy) bool {
@@ -472,7 +510,7 @@ func planGroupByGen4(groupExpr abstract.GroupBy, plan logicalPlan, semTable *sem
 	}
 }
 
-func (hp *horizonPlanning) planOrderByUsingGroupBy(ctx planningContext, plan logicalPlan) (logicalPlan, error) {
+func (hp *horizonPlanning) planGroupByUsingOrderBy(ctx planningContext, plan logicalPlan) (logicalPlan, error) {
 	var orderExprs []abstract.OrderBy
 	for _, groupExpr := range hp.qp.GroupByExprs {
 		addExpr := true
@@ -498,7 +536,7 @@ func (hp *horizonPlanning) planOrderByUsingGroupBy(ctx planningContext, plan log
 func (hp *horizonPlanning) planOrderBy(ctx planningContext, orderExprs []abstract.OrderBy, plan logicalPlan) (logicalPlan, error) {
 	switch plan := plan.(type) {
 	case *route:
-		newPlan, truncate, err := planOrderByForRoute(orderExprs, plan, ctx.semTable)
+		newPlan, truncate, err := planOrderByForRoute(orderExprs, plan, ctx.semTable, hp.qp.HasStar)
 		if err != nil {
 			return nil, err
 		}
@@ -558,9 +596,13 @@ func (hp *horizonPlanning) planOrderBy(ctx planningContext, orderExprs []abstrac
 	}
 }
 
-func planOrderByForRoute(orderExprs []abstract.OrderBy, plan *route, semTable *semantics.SemTable) (logicalPlan, bool, error) {
+func planOrderByForRoute(orderExprs []abstract.OrderBy, plan *route, semTable *semantics.SemTable, hasStar bool) (logicalPlan, bool, error) {
 	origColCount := plan.Select.GetColumnCount()
 	for _, order := range orderExprs {
+		err := checkOrderExprCanBePlannedInScatter(plan, order, hasStar)
+		if err != nil {
+			return nil, false, err
+		}
 		plan.Select.AddOrder(order.Inner)
 		if sqlparser.IsNull(order.Inner.Expr) {
 			continue
@@ -579,6 +621,27 @@ func planOrderByForRoute(orderExprs []abstract.OrderBy, plan *route, semTable *s
 	return plan, origColCount != plan.Select.GetColumnCount(), nil
 }
 
+// checkOrderExprCanBePlannedInScatter verifies that the given order by expression can be planned.
+// It checks if the expression exists in the plan's select list when the query is a scatter.
+func checkOrderExprCanBePlannedInScatter(plan *route, order abstract.OrderBy, hasStar bool) error {
+	if !hasStar {
+		return nil
+	}
+	sel := sqlparser.GetFirstSelect(plan.Select)
+	found := false
+	for _, expr := range sel.SelectExprs {
+		aliasedExpr, isAliasedExpr := expr.(*sqlparser.AliasedExpr)
+		if isAliasedExpr && sqlparser.EqualsExpr(aliasedExpr.Expr, order.Inner.Expr) {
+			found = true
+			break
+		}
+	}
+	if !found {
+		return vterrors.New(vtrpcpb.Code_UNIMPLEMENTED, "unsupported: in scatter query: order by must reference a column in the select list: "+sqlparser.String(order.Inner))
+	}
+	return nil
+}
+
 // wrapAndPushExpr pushes the expression and weighted_string function to the plan using semantics.SemTable
 // It returns (expr offset, weight_string offset, new_column added, error)
 func wrapAndPushExpr(expr sqlparser.Expr, weightStrExpr sqlparser.Expr, plan logicalPlan, semTable *semantics.SemTable) (int, int, bool, error) {
@@ -707,7 +770,7 @@ func (hp *horizonPlanning) createMemorySortPlan(ctx planningContext, plan logica
 
 func allLeft(orderExprs []abstract.OrderBy, semTable *semantics.SemTable, lhsTables semantics.TableSet) bool {
 	for _, expr := range orderExprs {
-		exprDependencies := semTable.BaseTableDependencies(expr.Inner.Expr)
+		exprDependencies := semTable.RecursiveDeps(expr.Inner.Expr)
 		if !exprDependencies.IsSolvedBy(lhsTables) {
 			return false
 		}
@@ -749,9 +812,13 @@ func (hp *horizonPlanning) planDistinctOA(currPlan *orderedAggregate) (logicalPl
 		eaggr: eaggr,
 	}
 	for _, sExpr := range hp.qp.SelectExprs {
+		expr, err := sExpr.GetExpr()
+		if err != nil {
+			return nil, err
+		}
 		found := false
 		for _, grpParam := range currPlan.eaggr.GroupByKeys {
-			if sqlparser.EqualsExpr(sExpr.Col.Expr, grpParam.Expr) {
+			if sqlparser.EqualsExpr(expr, grpParam.Expr) {
 				found = true
 				eaggr.GroupByKeys = append(eaggr.GroupByKeys, grpParam)
 				break
@@ -761,7 +828,7 @@ func (hp *horizonPlanning) planDistinctOA(currPlan *orderedAggregate) (logicalPl
 			continue
 		}
 		for _, aggrParam := range currPlan.eaggr.Aggregates {
-			if sqlparser.EqualsExpr(sExpr.Col.Expr, aggrParam.Expr) {
+			if sqlparser.EqualsExpr(expr, aggrParam.Expr) {
 				found = true
 				eaggr.GroupByKeys = append(eaggr.GroupByKeys, &engine.GroupByParams{KeyCol: aggrParam.Col, WeightStringCol: -1})
 				break
@@ -778,11 +845,15 @@ func (hp *horizonPlanning) addDistinct(ctx planningContext, plan logicalPlan) (l
 	eaggr := &engine.OrderedAggregate{}
 	var orderExprs []abstract.OrderBy
 	for index, sExpr := range hp.qp.SelectExprs {
-		if isAmbiguousOrderBy(index, sExpr.Col.As, hp.qp.SelectExprs) {
-			return nil, vterrors.Errorf(vtrpcpb.Code_UNIMPLEMENTED, "generating order by clause: ambiguous symbol reference: %s", sqlparser.String(sExpr.Col.As))
+		aliasExpr, err := sExpr.GetAliasedExpr()
+		if err != nil {
+			return nil, err
+		}
+		if isAmbiguousOrderBy(index, aliasExpr.As, hp.qp.SelectExprs) {
+			return nil, vterrors.Errorf(vtrpcpb.Code_UNIMPLEMENTED, "generating order by clause: ambiguous symbol reference: %s", sqlparser.String(aliasExpr.As))
 		}
 		grpParam := &engine.GroupByParams{KeyCol: index, WeightStringCol: -1}
-		_, wOffset, added, err := wrapAndPushExpr(sExpr.Col.Expr, sExpr.Col.Expr, plan, ctx.semTable)
+		_, wOffset, added, err := wrapAndPushExpr(aliasExpr.Expr, aliasExpr.Expr, plan, ctx.semTable)
 		if err != nil {
 			return nil, err
 		}
@@ -791,15 +862,15 @@ func (hp *horizonPlanning) addDistinct(ctx planningContext, plan logicalPlan) (l
 		eaggr.GroupByKeys = append(eaggr.GroupByKeys, grpParam)
 
 		var inner sqlparser.Expr
-		if !sExpr.Col.As.IsEmpty() {
-			inner = sqlparser.NewColName(sExpr.Col.As.String())
-			ctx.semTable.CopyDependencies(sExpr.Col.Expr, inner)
+		if !aliasExpr.As.IsEmpty() {
+			inner = sqlparser.NewColName(aliasExpr.As.String())
+			ctx.semTable.CopyDependencies(aliasExpr.Expr, inner)
 		} else {
-			inner = sExpr.Col.Expr
+			inner = aliasExpr.Expr
 		}
 		orderExprs = append(orderExprs, abstract.OrderBy{
 			Inner:         &sqlparser.Order{Expr: inner},
-			WeightStrExpr: sExpr.Col.Expr},
+			WeightStrExpr: aliasExpr.Expr},
 		)
 	}
 	innerPlan, err := hp.planOrderBy(ctx, orderExprs, plan)
@@ -825,9 +896,14 @@ func isAmbiguousOrderBy(index int, col sqlparser.ColIdent, exprs []abstract.Sele
 		if i == index {
 			continue
 		}
-		alias := expr.Col.As
+		aliasExpr, isAlias := expr.Col.(*sqlparser.AliasedExpr)
+		if !isAlias {
+			// TODO: handle star expression error
+			return true
+		}
+		alias := aliasExpr.As
 		if alias.IsEmpty() {
-			if col, ok := expr.Col.Expr.(*sqlparser.ColName); ok {
+			if col, ok := aliasExpr.Expr.(*sqlparser.ColName); ok {
 				alias = col.Name
 			}
 		}
@@ -840,7 +916,12 @@ func isAmbiguousOrderBy(index int, col sqlparser.ColIdent, exprs []abstract.Sele
 
 func selectHasUniqueVindex(vschema ContextVSchema, semTable *semantics.SemTable, sel []abstract.SelectExpr) bool {
 	for _, expr := range sel {
-		if exprHasUniqueVindex(vschema, semTable, expr.Col.Expr) {
+		exp, err := expr.GetExpr()
+		if err != nil {
+			// TODO: handle star expression error
+			return false
+		}
+		if exprHasUniqueVindex(vschema, semTable, exp) {
 			return true
 		}
 	}
diff --git a/go/vt/vtgate/planbuilder/jointree.go b/go/vt/vtgate/planbuilder/jointree.go
index c905903056..4f9c217585 100644
--- a/go/vt/vtgate/planbuilder/jointree.go
+++ b/go/vt/vtgate/planbuilder/jointree.go
@@ -59,7 +59,7 @@ func (jp *joinTree) pushOutputColumns(columns []*sqlparser.ColName, semTable *se
 	var lhs, rhs []*sqlparser.ColName
 	for _, col := range columns {
 		col.Qualifier.Qualifier = sqlparser.NewTableIdent("")
-		if semTable.BaseTableDependencies(col).IsSolvedBy(jp.lhs.tableID()) {
+		if semTable.RecursiveDeps(col).IsSolvedBy(jp.lhs.tableID()) {
 			lhs = append(lhs, col)
 			toTheLeft = append(toTheLeft, true)
 		} else {
diff --git a/go/vt/vtgate/planbuilder/querytree_transformers.go b/go/vt/vtgate/planbuilder/querytree_transformers.go
index e973958448..a4b470070b 100644
--- a/go/vt/vtgate/planbuilder/querytree_transformers.go
+++ b/go/vt/vtgate/planbuilder/querytree_transformers.go
@@ -142,8 +142,15 @@ func transformDerivedPlan(ctx planningContext, n *derivedTree) (logicalPlan, err
 		Expr: derivedTable,
 		As:   sqlparser.NewTableIdent(n.alias),
 	}
+	selectExprs := sqlparser.SelectExprs{}
+	for _, colName := range n.columns {
+		selectExprs = append(selectExprs, &sqlparser.AliasedExpr{
+			Expr: colName,
+		})
+	}
 	rb.Select = &sqlparser.Select{
-		From: []sqlparser.TableExpr{tblExpr},
+		From:        []sqlparser.TableExpr{tblExpr},
+		SelectExprs: selectExprs,
 	}
 	return plan, nil
 }
diff --git a/go/vt/vtgate/planbuilder/route_planning.go b/go/vt/vtgate/planbuilder/route_planning.go
index 75570d2944..e2d3b3e20d 100644
--- a/go/vt/vtgate/planbuilder/route_planning.go
+++ b/go/vt/vtgate/planbuilder/route_planning.go
@@ -253,7 +253,7 @@ func rewriteSubqueryDependenciesForJoin(otherTree queryTree, outerTree *joinTree
 		switch node := sqlNode.(type) {
 		case *sqlparser.ColName:
 			// check weather the column name belongs to the other side of the join tree
-			if ctx.semTable.Dependencies(node).IsSolvedBy(otherTree.tableID()) {
+			if ctx.semTable.DirectDeps(node).IsSolvedBy(otherTree.tableID()) {
 				// get the bindVariable for that column name and replace it in the subquery
 				bindVar := node.CompliantName()
 				cursor.Replace(sqlparser.NewArgument(bindVar))
@@ -307,7 +307,7 @@ func exprHasUniqueVindex(vschema ContextVSchema, semTable *semantics.SemTable, e
 	if !isCol {
 		return false
 	}
-	ts := semTable.BaseTableDependencies(expr)
+	ts := semTable.RecursiveDeps(expr)
 	tableInfo, err := semTable.TableInfoFor(ts)
 	if err != nil {
 		return false
@@ -331,7 +331,7 @@ func exprHasUniqueVindex(vschema ContextVSchema, semTable *semantics.SemTable, e
 	return false
 }
 
-func createSingleShardRoutePlan(sel sqlparser.SelectStatement, rb *route) error {
+func planSingleShardRoutePlan(sel sqlparser.SelectStatement, rb *route) error {
 	err := stripDownQuery(sel, rb.Select)
 	if err != nil {
 		return err
@@ -345,6 +345,15 @@ func createSingleShardRoutePlan(sel sqlparser.SelectStatement, rb *route) error
 	return nil
 }
 
+func removeKeyspaceFromSelectExpr(expr sqlparser.SelectExpr, ast *sqlparser.Select, i int) {
+	switch expr := expr.(type) {
+	case *sqlparser.AliasedExpr:
+		ast.SelectExprs[i] = removeKeyspaceFromColName(expr)
+	case *sqlparser.StarExpr:
+		expr.TableName.Qualifier = sqlparser.NewTableIdent("")
+	}
+}
+
 func stripDownQuery(from, to sqlparser.SelectStatement) error {
 	var err error
 
@@ -360,6 +369,9 @@ func stripDownQuery(from, to sqlparser.SelectStatement) error {
 		toNode.OrderBy = node.OrderBy
 		toNode.Comments = node.Comments
 		toNode.SelectExprs = node.SelectExprs
+		for i, expr := range toNode.SelectExprs {
+			removeKeyspaceFromSelectExpr(expr, toNode, i)
+		}
 	case *sqlparser.Union:
 		toNode, ok := to.(*sqlparser.Union)
 		if !ok {
@@ -471,12 +483,16 @@ func pushJoinPredicate(ctx planningContext, exprs []sqlparser.Expr, tree queryTr
 	}
 }
 
-func breakPredicateInLHSandRHS(expr sqlparser.Expr, semTable *semantics.SemTable, lhs semantics.TableSet) (bvNames []string, columns []*sqlparser.ColName, predicate sqlparser.Expr, err error) {
+func breakPredicateInLHSandRHS(
+	expr sqlparser.Expr,
+	semTable *semantics.SemTable,
+	lhs semantics.TableSet,
+) (bvNames []string, columns []*sqlparser.ColName, predicate sqlparser.Expr, err error) {
 	predicate = sqlparser.CloneExpr(expr)
 	_ = sqlparser.Rewrite(predicate, nil, func(cursor *sqlparser.Cursor) bool {
 		switch node := cursor.Node().(type) {
 		case *sqlparser.ColName:
-			deps := semTable.BaseTableDependencies(node)
+			deps := semTable.RecursiveDeps(node)
 			if deps == 0 {
 				err = vterrors.Errorf(vtrpcpb.Code_INTERNAL, "unknown column. has the AST been copied?")
 				return false
@@ -782,7 +798,7 @@ func findColumnVindex(ctx planningContext, a *routeTree, exp sqlparser.Expr) vin
 		if !isCol {
 			continue
 		}
-		leftDep := ctx.semTable.BaseTableDependencies(expr)
+		leftDep := ctx.semTable.RecursiveDeps(expr)
 		_ = visitRelations(a.tables, func(rel relation) (bool, error) {
 			rb, isRoute := rel.(*routeTable)
 			if !isRoute {
@@ -1058,7 +1074,7 @@ func createRoutePlanForOuter(ctx planningContext, aRoute, bRoute *routeTree, new
 	tables := bRoute.tables
 	// we are doing an outer join where the outer part contains multiple tables - we have to turn the outer part into a join or two
 	for _, predicate := range bRoute.predicates {
-		deps := ctx.semTable.BaseTableDependencies(predicate)
+		deps := ctx.semTable.RecursiveDeps(predicate)
 		aTbl, bTbl, newTables := findTables(deps, tables)
 		tables = newTables
 		if aTbl != nil && bTbl != nil {
@@ -1115,7 +1131,7 @@ func gen4ValEqual(ctx planningContext, a, b sqlparser.Expr) bool {
 				return false
 			}
 
-			return ctx.semTable.Dependencies(a) == ctx.semTable.Dependencies(b)
+			return ctx.semTable.DirectDeps(a) == ctx.semTable.DirectDeps(b)
 		}
 	case sqlparser.Argument:
 		b, ok := b.(sqlparser.Argument)
diff --git a/go/vt/vtgate/planbuilder/routetree.go b/go/vt/vtgate/planbuilder/routetree.go
index bf92657fc5..1e117783da 100644
--- a/go/vt/vtgate/planbuilder/routetree.go
+++ b/go/vt/vtgate/planbuilder/routetree.go
@@ -463,7 +463,7 @@ func (rp *routeTree) haveMatchingVindex(
 	newVindexFound := false
 	for _, v := range rp.vindexPreds {
 		// check that the
-		if !ctx.semTable.Dependencies(column).IsSolvedBy(v.tableID) {
+		if !ctx.semTable.DirectDeps(column).IsSolvedBy(v.tableID) {
 			continue
 		}
 		cols := len(v.colVindex.Columns)
diff --git a/go/vt/vtgate/semantics/analyzer.go b/go/vt/vtgate/semantics/analyzer.go
index 4a574d9160..d72dad6073 100644
--- a/go/vt/vtgate/semantics/analyzer.go
+++ b/go/vt/vtgate/semantics/analyzer.go
@@ -45,13 +45,15 @@ type analyzer struct {
 
 // newAnalyzer create the semantic analyzer
 func newAnalyzer(dbName string, si SchemaInformation) *analyzer {
+	// TODO  dependencies between these components are a little tangled. We should try to clean up
 	s := newScoper()
 	a := &analyzer{
 		scoper: s,
 		tables: newTableCollector(s, si, dbName),
 		typer:  newTyper(),
 	}
-
+	s.org = a
+	a.tables.org = a
 	a.binder = newBinder(s, a, a.tables, a.typer)
 
 	return a
@@ -88,23 +90,23 @@ func Analyze(statement sqlparser.SelectStatement, currentDb string, si SchemaInf
 
 func (a analyzer) newSemTable(statement sqlparser.SelectStatement) *SemTable {
 	return &SemTable{
-		ExprBaseTableDeps: a.binder.exprRecursiveDeps,
-		ExprDeps:          a.binder.exprDeps,
-		exprTypes:         a.typer.exprTypes,
-		Tables:            a.tables.Tables,
-		selectScope:       a.scoper.rScope,
-		ProjectionErr:     a.projErr,
-		Comments:          statement.GetComments(),
-		SubqueryMap:       a.binder.subqueryMap,
-		SubqueryRef:       a.binder.subqueryRef,
-		ColumnEqualities:  map[columnName][]sqlparser.Expr{},
+		Recursive:        a.binder.recursive,
+		Direct:           a.binder.direct,
+		exprTypes:        a.typer.exprTypes,
+		Tables:           a.tables.Tables,
+		selectScope:      a.scoper.rScope,
+		ProjectionErr:    a.projErr,
+		Comments:         statement.GetComments(),
+		SubqueryMap:      a.binder.subqueryMap,
+		SubqueryRef:      a.binder.subqueryRef,
+		ColumnEqualities: map[columnName][]sqlparser.Expr{},
 	}
 }
 
 func (a *analyzer) setError(err error) {
 	prErr, ok := err.(ProjError)
 	if ok {
-		a.projErr = prErr.inner
+		a.projErr = prErr.Inner
 		return
 	}
 
@@ -127,8 +129,10 @@ func (a *analyzer) analyzeDown(cursor *sqlparser.Cursor) bool {
 			a.setError(err)
 			return true
 		}
-
-		a.scoper.down(cursor)
+		if err := a.scoper.down(cursor); err != nil {
+			a.setError(err)
+			return true
+		}
 	} else { // after expand star
 		if err := checkUnionColumns(cursor); err != nil {
 			a.setError(err)
@@ -155,7 +159,7 @@ func checkForStar(s sqlparser.SelectExprs) error {
 		_, isStar := expr.(*sqlparser.StarExpr)
 		if isStar {
 			return ProjError{
-				inner: vterrors.Errorf(vtrpcpb.Code_NOT_FOUND, "can't handle * between UNIONs"),
+				Inner: vterrors.Errorf(vtrpcpb.Code_NOT_FOUND, "can't handle * between UNIONs"),
 			}
 		}
 	}
@@ -247,7 +251,7 @@ type originable interface {
 }
 
 func (a *analyzer) depsForExpr(expr sqlparser.Expr) (TableSet, *querypb.Type) {
-	ts := a.binder.exprRecursiveDeps.Dependencies(expr)
+	ts := a.binder.recursive.Dependencies(expr)
 	qt, isFound := a.typer.exprTypes[expr]
 	if !isFound {
 		return ts, nil
@@ -255,20 +259,6 @@ func (a *analyzer) depsForExpr(expr sqlparser.Expr) (TableSet, *querypb.Type) {
 	return ts, &qt
 }
 
-func (v *vTableInfo) checkForDuplicates() error {
-	for i, name := range v.columnNames {
-		for j, name2 := range v.columnNames {
-			if i == j {
-				continue
-			}
-			if name == name2 {
-				return vterrors.NewErrorf(vtrpcpb.Code_INVALID_ARGUMENT, vterrors.DupFieldName, "Duplicate column name '%s'", name)
-			}
-		}
-	}
-	return nil
-}
-
 func (a *analyzer) analyze(statement sqlparser.Statement) error {
 	_ = sqlparser.Rewrite(statement, a.analyzeDown, a.analyzeUp)
 	return a.err
@@ -317,29 +307,6 @@ func checkForInvalidConstructs(cursor *sqlparser.Cursor) error {
 	return nil
 }
 
-func createVTableInfoForExpressions(expressions sqlparser.SelectExprs) *vTableInfo {
-	vTbl := &vTableInfo{}
-	for _, selectExpr := range expressions {
-		expr, ok := selectExpr.(*sqlparser.AliasedExpr)
-		if !ok {
-			continue
-		}
-		vTbl.cols = append(vTbl.cols, expr.Expr)
-		if expr.As.IsEmpty() {
-			switch expr := expr.Expr.(type) {
-			case *sqlparser.ColName:
-				// for projections, we strip out the qualifier and keep only the column name
-				vTbl.columnNames = append(vTbl.columnNames, expr.Name.String())
-			default:
-				vTbl.columnNames = append(vTbl.columnNames, sqlparser.String(expr))
-			}
-		} else {
-			vTbl.columnNames = append(vTbl.columnNames, expr.As.String())
-		}
-	}
-	return vTbl
-}
-
 func (a *analyzer) shouldContinue() bool {
 	return a.err == nil
 }
@@ -362,9 +329,9 @@ func Gen4NotSupportedF(format string, args ...interface{}) error {
 // ProjError is used to mark an error as something that should only be returned
 // if the planner fails to merge everything down to a single route
 type ProjError struct {
-	inner error
+	Inner error
 }
 
 func (p ProjError) Error() string {
-	return p.inner.Error()
+	return p.Inner.Error()
 }
diff --git a/go/vt/vtgate/semantics/binder.go b/go/vt/vtgate/semantics/binder.go
index 16c7c62e45..7dbba6bf04 100644
--- a/go/vt/vtgate/semantics/binder.go
+++ b/go/vt/vtgate/semantics/binder.go
@@ -17,12 +17,8 @@ limitations under the License.
 package semantics
 
 import (
-	"fmt"
-
 	"vitess.io/vitess/go/vt/vtgate/engine"
 
-	querypb "vitess.io/vitess/go/vt/proto/query"
-
 	vtrpcpb "vitess.io/vitess/go/vt/proto/vtrpc"
 	"vitess.io/vitess/go/vt/sqlparser"
 	"vitess.io/vitess/go/vt/vterrors"
@@ -33,26 +29,26 @@ import (
 // While doing this, it will also find the types for columns and
 // store these in the typer:s expression map
 type binder struct {
-	exprRecursiveDeps ExprDependencies
-	exprDeps          ExprDependencies
-	scoper            *scoper
-	tc                *tableCollector
-	org               originable
-	typer             *typer
-	subqueryMap       map[*sqlparser.Select][]*subquery
-	subqueryRef       map[*sqlparser.Subquery]*subquery
+	recursive   ExprDependencies
+	direct      ExprDependencies
+	scoper      *scoper
+	tc          *tableCollector
+	org         originable
+	typer       *typer
+	subqueryMap map[*sqlparser.Select][]*subquery
+	subqueryRef map[*sqlparser.Subquery]*subquery
 }
 
 func newBinder(scoper *scoper, org originable, tc *tableCollector, typer *typer) *binder {
 	return &binder{
-		exprRecursiveDeps: map[sqlparser.Expr]TableSet{},
-		exprDeps:          map[sqlparser.Expr]TableSet{},
-		scoper:            scoper,
-		org:               org,
-		tc:                tc,
-		typer:             typer,
-		subqueryMap:       map[*sqlparser.Select][]*subquery{},
-		subqueryRef:       map[*sqlparser.Subquery]*subquery{},
+		recursive:   map[sqlparser.Expr]TableSet{},
+		direct:      map[sqlparser.Expr]TableSet{},
+		scoper:      scoper,
+		org:         org,
+		tc:          tc,
+		typer:       typer,
+		subqueryMap: map[*sqlparser.Select][]*subquery{},
+		subqueryRef: map[*sqlparser.Subquery]*subquery{},
 	}
 }
 
@@ -82,14 +78,14 @@ func (b *binder) down(cursor *sqlparser.Cursor) error {
 		b.subqueryMap[currScope.selectStmt] = append(b.subqueryMap[currScope.selectStmt], sq)
 		b.subqueryRef[node] = sq
 	case *sqlparser.ColName:
-		baseTableTS, ts, typ, err := b.resolveColumn(node, b.scoper.currentScope())
+		deps, err := b.resolveColumn(node, b.scoper.currentScope())
 		if err != nil {
 			return err
 		}
-		b.exprRecursiveDeps[node] = baseTableTS
-		b.exprDeps[node] = ts
-		if typ != nil {
-			b.typer.setTypeFor(node, *typ)
+		b.recursive[node] = deps.recursive
+		b.direct[node] = deps.direct
+		if deps.typ != nil {
+			b.typer.setTypeFor(node, *deps.typ)
 		}
 	case *sqlparser.FuncExpr:
 		// need special handling so that any lingering `*` expressions are bound to all local tables
@@ -107,105 +103,81 @@ func (b *binder) down(cursor *sqlparser.Cursor) error {
 			}
 			ts |= b.tc.tableSetFor(table.GetExpr())
 		}
-		b.exprRecursiveDeps[node] = ts
-		b.exprDeps[node] = ts
+		b.recursive[node] = ts
+		b.direct[node] = ts
 	}
 	return nil
 }
 
-func (b *binder) resolveColumn(colName *sqlparser.ColName, current *scope) (TableSet, TableSet, *querypb.Type, error) {
+func (b *binder) resolveColumn(colName *sqlparser.ColName, current *scope) (deps dependency, err error) {
 	if colName.Qualifier.IsEmpty() {
-		return b.resolveUnQualifiedColumn(current, colName)
+		deps, err = b.resolveUnQualifiedColumn(current, colName)
+	} else {
+		deps, err = b.resolveQualifiedColumn(current, colName)
+	}
+
+	if err != nil {
+		if err == ambigousErr {
+			err = vterrors.Errorf(vtrpcpb.Code_INVALID_ARGUMENT, "Column '%s' in field list is ambiguous", sqlparser.String(colName))
+		}
+		return dependency{}, err
 	}
-	return b.resolveQualifiedColumn(current, colName)
+	return deps, nil
 }
 
 // resolveQualifiedColumn handles column expressions where the table is explicitly stated
-func (b *binder) resolveQualifiedColumn(current *scope, expr *sqlparser.ColName) (TableSet, TableSet, *querypb.Type, error) {
+func (b *binder) resolveQualifiedColumn(current *scope, expr *sqlparser.ColName) (dependency, error) {
 	// search up the scope stack until we find a match
 	for current != nil {
-		for _, table := range current.tables {
-			if !table.Matches(expr.Qualifier) {
-				continue
-			}
-			if table.IsActualTable() {
-				actualTable, ts, typ := b.resolveQualifiedColumnOnActualTable(table, expr)
-				return actualTable, ts, typ, nil
-			}
-			recursiveTs, typ, err := table.RecursiveDepsFor(expr, b.org, len(current.tables) == 1)
-			if err != nil {
-				return 0, 0, nil, err
-			}
-			if recursiveTs == nil {
-				return 0, 0, nil, vterrors.NewErrorf(vtrpcpb.Code_INVALID_ARGUMENT, vterrors.BadFieldError, "symbol %s not found", sqlparser.String(expr))
-			}
-
-			ts, err := table.DepsFor(expr, b.org, len(current.tables) == 1)
-			if err != nil {
-				return 0, 0, nil, err
-			}
-			return *recursiveTs, *ts, typ, nil
+		deps, err := b.resolveColumnInScope(current, expr, func(table TableInfo) bool {
+			return !table.Matches(expr.Qualifier)
+		})
+		if err != nil {
+			return dependency{}, err
+		}
+		if !deps.Empty() {
+			return deps.Get()
 		}
 		current = current.parent
 	}
-	return 0, 0, nil, vterrors.NewErrorf(vtrpcpb.Code_INVALID_ARGUMENT, vterrors.BadFieldError, "symbol %s not found", sqlparser.String(expr))
+	return dependency{}, vterrors.NewErrorf(vtrpcpb.Code_INVALID_ARGUMENT, vterrors.BadFieldError, "symbol %s not found", sqlparser.String(expr))
 }
 
 // resolveUnQualifiedColumn handles column that do not specify which table they belong to
-func (b *binder) resolveUnQualifiedColumn(current *scope, expr *sqlparser.ColName) (TableSet, TableSet, *querypb.Type, error) {
-	var tspRecursive, tsp *TableSet
-	var typp *querypb.Type
-
-	for current != nil && tspRecursive == nil {
-		for _, tbl := range current.tables {
-			recursiveTs, typ, err := tbl.RecursiveDepsFor(expr, b.org, len(current.tables) == 1)
-			if err != nil {
-				return 0, 0, nil, err
-			}
-			if recursiveTs != nil && tspRecursive != nil {
-				return 0, 0, nil, vterrors.NewErrorf(vtrpcpb.Code_INVALID_ARGUMENT, vterrors.NonUniqError, fmt.Sprintf("Column '%s' in field list is ambiguous", sqlparser.String(expr)))
-			}
-			if recursiveTs != nil {
-				tspRecursive = recursiveTs
-				typp = typ
-			}
-			if tbl.IsActualTable() {
-				tsp = tspRecursive
-				continue
-			}
-			ts, err := tbl.DepsFor(expr, b.org, len(current.tables) == 1)
-			if err != nil {
-				return 0, 0, nil, err
-			}
-			if ts != nil {
-				tsp = ts
-			}
+func (b *binder) resolveUnQualifiedColumn(current *scope, expr *sqlparser.ColName) (dependency, error) {
+	for current != nil {
+		deps, err := b.resolveColumnInScope(current, expr, nil)
+		if err != nil {
+			return dependency{}, err
+		}
+		if !deps.Empty() {
+			return deps.Get()
 		}
-
 		current = current.parent
 	}
-
-	if tspRecursive == nil {
-		return 0, 0, nil, ProjError{vterrors.NewErrorf(vtrpcpb.Code_INVALID_ARGUMENT, vterrors.NonUniqError, fmt.Sprintf("Column '%s' in field list is ambiguous", sqlparser.String(expr)))}
-	}
-
-	if tsp == nil {
-		return *tspRecursive, 0, typp, nil
-	}
-	return *tspRecursive, *tsp, typp, nil
+	return dependency{}, vterrors.NewErrorf(vtrpcpb.Code_INVALID_ARGUMENT, vterrors.BadFieldError, "symbol %s not found", sqlparser.String(expr))
 }
 
-func (b *binder) resolveQualifiedColumnOnActualTable(table TableInfo, expr *sqlparser.ColName) (TableSet, TableSet, *querypb.Type) {
-	ts := b.tc.tableSetFor(table.GetExpr())
-	for _, colInfo := range table.GetColumns() {
-		if expr.Name.EqualString(colInfo.Name) {
-			// A column can't be of type NULL, that is the default value indicating that we dont know the actual type
-			// But expressions can be of NULL type, so we use nil to represent an unknown type
-			if colInfo.Type == querypb.Type_NULL_TYPE {
-				return ts, ts, nil
-			}
-			return ts, ts, &colInfo.Type
+func (b *binder) resolveColumnInScope(current *scope, expr *sqlparser.ColName, skipTable func(table TableInfo) bool) (dependencies, error) {
+	var deps dependencies = &nothing{}
+	for _, table := range current.tables {
+		if skipTable != nil && skipTable(table) {
+			continue
+		}
+		thisDeps, err := table.Dependencies(expr.Name.String(), b.org)
+		if err != nil {
+			return nil, err
+		}
+		deps, err = thisDeps.Merge(deps)
+		if err != nil {
+			return nil, err
+		}
+	}
+	if deps, isUncertain := deps.(*uncertain); isUncertain && deps.fail {
+		// if we have a failure from uncertain, we matched the column to multiple non-authoritative tables
+		return nil, ProjError{
+			Inner: vterrors.Errorf(vtrpcpb.Code_INVALID_ARGUMENT, "Column '%s' in field list is ambiguous", sqlparser.String(expr)),
 		}
 	}
-	return ts, ts, nil
+	return deps, nil
 }
diff --git a/go/vt/vtgate/semantics/dependencies.go b/go/vt/vtgate/semantics/dependencies.go
new file mode 100644
index 0000000000..b1aa5102ad
--- /dev/null
+++ b/go/vt/vtgate/semantics/dependencies.go
@@ -0,0 +1,129 @@
+/*
+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 semantics
+
+import (
+	querypb "vitess.io/vitess/go/vt/proto/query"
+	vtrpcpb "vitess.io/vitess/go/vt/proto/vtrpc"
+	"vitess.io/vitess/go/vt/vterrors"
+)
+
+type (
+	dependencies interface {
+		Empty() bool
+		Get() (dependency, error)
+		Merge(dependencies) (dependencies, error)
+	}
+	dependency struct {
+		direct    TableSet
+		recursive TableSet
+		typ       *querypb.Type
+	}
+	nothing struct{}
+	certain struct {
+		dependency
+	}
+	uncertain struct {
+		dependency
+		fail bool
+	}
+)
+
+var ambigousErr = vterrors.Errorf(vtrpcpb.Code_INVALID_ARGUMENT, "ambiguous")
+
+func createCertain(direct TableSet, recursive TableSet, qt *querypb.Type) *certain {
+	return &certain{
+		dependency: dependency{
+			direct:    direct,
+			recursive: recursive,
+			typ:       qt,
+		},
+	}
+}
+
+func createUncertain(direct TableSet, recursive TableSet) *uncertain {
+	return &uncertain{
+		dependency: dependency{
+			direct:    direct,
+			recursive: recursive,
+		},
+	}
+}
+
+var _ dependencies = (*nothing)(nil)
+var _ dependencies = (*certain)(nil)
+var _ dependencies = (*uncertain)(nil)
+
+func (u *uncertain) Empty() bool {
+	return false
+}
+
+func (u *uncertain) Get() (dependency, error) {
+	if u.fail {
+		return dependency{}, ambigousErr
+	}
+	return u.dependency, nil
+}
+
+func (u *uncertain) Merge(d dependencies) (dependencies, error) {
+	switch d := d.(type) {
+	case *nothing:
+		return u, nil
+	case *uncertain:
+		if d.recursive == u.recursive {
+			return u, nil
+		}
+		u.fail = true
+		return u, nil
+	case *certain:
+		return d, nil
+	}
+	return nil, ambigousErr
+}
+
+func (c *certain) Empty() bool {
+	return false
+}
+
+func (c *certain) Get() (dependency, error) {
+	return c.dependency, nil
+}
+
+func (c *certain) Merge(d dependencies) (dependencies, error) {
+	switch d := d.(type) {
+	case *nothing, *uncertain:
+		return c, nil
+	case *certain:
+		if d.recursive == c.recursive {
+			return c, nil
+		}
+	}
+
+	return nil, ambigousErr
+}
+
+func (n *nothing) Empty() bool {
+	return true
+}
+
+func (n *nothing) Get() (dependency, error) {
+	return dependency{}, nil
+}
+
+func (n *nothing) Merge(d dependencies) (dependencies, error) {
+	return d, nil
+}
diff --git a/go/vt/vtgate/semantics/derived_table.go b/go/vt/vtgate/semantics/derived_table.go
new file mode 100644
index 0000000000..3423d13166
--- /dev/null
+++ b/go/vt/vtgate/semantics/derived_table.go
@@ -0,0 +1,159 @@
+/*
+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 semantics
+
+import (
+	vtrpcpb "vitess.io/vitess/go/vt/proto/vtrpc"
+	"vitess.io/vitess/go/vt/sqlparser"
+	"vitess.io/vitess/go/vt/vterrors"
+	"vitess.io/vitess/go/vt/vtgate/vindexes"
+)
+
+type derivedTable struct {
+	tableName   string
+	ASTNode     *sqlparser.AliasedTableExpr
+	columnNames []string
+	cols        []sqlparser.Expr
+	tables      TableSet
+}
+
+var _ TableInfo = (*derivedTable)(nil)
+
+func createDerivedTableForExpressions(expressions sqlparser.SelectExprs, tables []TableInfo, org originable) *derivedTable {
+	vTbl := &derivedTable{}
+	for _, selectExpr := range expressions {
+		switch expr := selectExpr.(type) {
+		case *sqlparser.AliasedExpr:
+			vTbl.cols = append(vTbl.cols, expr.Expr)
+			if expr.As.IsEmpty() {
+				switch expr := expr.Expr.(type) {
+				case *sqlparser.ColName:
+					// for projections, we strip out the qualifier and keep only the column name
+					vTbl.columnNames = append(vTbl.columnNames, expr.Name.String())
+				default:
+					vTbl.columnNames = append(vTbl.columnNames, sqlparser.String(expr))
+				}
+			} else {
+				vTbl.columnNames = append(vTbl.columnNames, expr.As.String())
+			}
+		case *sqlparser.StarExpr:
+			for _, table := range tables {
+				vTbl.tables |= table.GetTables(org)
+			}
+		}
+	}
+	return vTbl
+}
+
+// Dependencies implements the TableInfo interface
+func (dt *derivedTable) Dependencies(colName string, org originable) (dependencies, error) {
+	for i, name := range dt.columnNames {
+		if name != colName {
+			continue
+		}
+		recursiveDeps, qt := org.depsForExpr(dt.cols[i])
+
+		directDeps := recursiveDeps
+		if dt.ASTNode != nil {
+			directDeps = org.tableSetFor(dt.ASTNode)
+		}
+		return createCertain(directDeps, recursiveDeps, qt), nil
+	}
+
+	if !dt.hasStar() {
+		return &nothing{}, nil
+	}
+
+	recursive := dt.tables
+	direct := org.tableSetFor(dt.ASTNode)
+
+	return createUncertain(direct, recursive), nil
+}
+
+// IsInfSchema implements the TableInfo interface
+func (dt *derivedTable) IsInfSchema() bool {
+	return false
+}
+
+// IsActualTable implements the TableInfo interface
+func (dt *derivedTable) IsActualTable() bool {
+	return false
+}
+
+func (dt *derivedTable) Matches(name sqlparser.TableName) bool {
+	return dt.tableName == name.Name.String() && name.Qualifier.IsEmpty()
+}
+
+func (dt *derivedTable) Authoritative() bool {
+	return true
+}
+
+func (dt *derivedTable) Name() (sqlparser.TableName, error) {
+	return dt.ASTNode.TableName()
+}
+
+func (dt *derivedTable) GetExpr() *sqlparser.AliasedTableExpr {
+	return dt.ASTNode
+}
+
+// GetVindexTable implements the TableInfo interface
+func (dt *derivedTable) GetVindexTable() *vindexes.Table {
+	return nil
+}
+
+func (dt *derivedTable) GetColumns() []ColumnInfo {
+	cols := make([]ColumnInfo, 0, len(dt.columnNames))
+	for _, col := range dt.columnNames {
+		cols = append(cols, ColumnInfo{
+			Name: col,
+		})
+	}
+	return cols
+}
+
+func (dt *derivedTable) hasStar() bool {
+	return dt.tables > 0
+}
+
+// GetTables implements the TableInfo interface
+func (dt *derivedTable) GetTables(org originable) TableSet {
+	return dt.tables
+}
+
+// GetExprFor implements the TableInfo interface
+func (dt *derivedTable) GetExprFor(s string) (sqlparser.Expr, error) {
+	for i, colName := range dt.columnNames {
+		if colName == s {
+			return dt.cols[i], nil
+		}
+	}
+	return nil, vterrors.NewErrorf(vtrpcpb.Code_NOT_FOUND, vterrors.BadFieldError, "Unknown column '%s' in 'field list'", s)
+}
+
+func (dt *derivedTable) checkForDuplicates() error {
+	for i, name := range dt.columnNames {
+		for j, name2 := range dt.columnNames {
+			if i == j {
+				continue
+			}
+			if name == name2 {
+				return vterrors.NewErrorf(vtrpcpb.Code_INVALID_ARGUMENT, vterrors.DupFieldName, "Duplicate column name '%s'", name)
+			}
+		}
+	}
+	return nil
+}
diff --git a/go/vt/vtgate/semantics/early_rewriter.go b/go/vt/vtgate/semantics/early_rewriter.go
index 79e1cff4df..b12f24e927 100644
--- a/go/vt/vtgate/semantics/early_rewriter.go
+++ b/go/vt/vtgate/semantics/early_rewriter.go
@@ -58,7 +58,7 @@ func (r *earlyRewriter) rewrite(cursor *sqlparser.Cursor) bool {
 				r.err = err
 				return false
 			}
-			if !starExpanded {
+			if !starExpanded || colNames == nil {
 				selExprs = append(selExprs, selectExpr)
 				continue
 			}
@@ -103,12 +103,28 @@ func (r *earlyRewriter) rewrite(cursor *sqlparser.Cursor) bool {
 		if !aliasedExpr.As.IsEmpty() {
 			cursor.Replace(sqlparser.NewColName(aliasedExpr.As.String()))
 		} else {
-			cursor.Replace(aliasedExpr.Expr)
+			expr := realCloneOfColNames(aliasedExpr.Expr)
+			cursor.Replace(expr)
 		}
 	}
 	return true
 }
 
+// realCloneOfColNames clones all the expressions including ColName.
+// Since sqlparser.CloneRefOfColName does not clone col names, this method is needed.
+func realCloneOfColNames(expr sqlparser.Expr) sqlparser.Expr {
+	return sqlparser.Rewrite(sqlparser.CloneExpr(expr), func(cursor *sqlparser.Cursor) bool {
+		switch exp := cursor.Node().(type) {
+		case *sqlparser.ColName:
+			newColName := *exp
+			newColName.Name = sqlparser.CloneColIdent(exp.Name)
+			newColName.Qualifier = sqlparser.CloneTableName(exp.Qualifier)
+			cursor.Replace(&newColName)
+		}
+		return true
+	}, nil).(sqlparser.Expr)
+}
+
 func expandTableColumns(tables []TableInfo, starExpr *sqlparser.StarExpr) (bool, sqlparser.SelectExprs, error) {
 	unknownTbl := true
 	var colNames sqlparser.SelectExprs
diff --git a/go/vt/vtgate/semantics/real_table.go b/go/vt/vtgate/semantics/real_table.go
new file mode 100644
index 0000000000..391b3412ae
--- /dev/null
+++ b/go/vt/vtgate/semantics/real_table.go
@@ -0,0 +1,89 @@
+/*
+Copyright 2020 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 semantics
+
+import (
+	vtrpcpb "vitess.io/vitess/go/vt/proto/vtrpc"
+	"vitess.io/vitess/go/vt/sqlparser"
+	"vitess.io/vitess/go/vt/vterrors"
+	"vitess.io/vitess/go/vt/vtgate/vindexes"
+)
+
+// RealTable contains the alias table expr and vindex table
+type RealTable struct {
+	dbName, tableName string
+	ASTNode           *sqlparser.AliasedTableExpr
+	Table             *vindexes.Table
+	isInfSchema       bool
+}
+
+var _ TableInfo = (*RealTable)(nil)
+
+// Dependencies implements the TableInfo interface
+func (r *RealTable) Dependencies(colName string, org originable) (dependencies, error) {
+	return depsForAliasedAndRealTables(colName, org, r.ASTNode, r.GetColumns(), r.Authoritative())
+}
+
+// GetTables implements the TableInfo interface
+func (r *RealTable) GetTables(org originable) TableSet {
+	return org.tableSetFor(r.ASTNode)
+}
+
+// GetExprFor implements the TableInfo interface
+func (r *RealTable) GetExprFor(s string) (sqlparser.Expr, error) {
+	return nil, vterrors.Errorf(vtrpcpb.Code_INTERNAL, "Unknown column '%s' in 'field list'", s)
+}
+
+// IsInfSchema implements the TableInfo interface
+func (r *RealTable) IsInfSchema() bool {
+	return r.isInfSchema
+}
+
+// IsActualTable implements the TableInfo interface
+func (r *RealTable) IsActualTable() bool {
+	return true
+}
+
+// GetColumns implements the TableInfo interface
+func (r *RealTable) GetColumns() []ColumnInfo {
+	return vindexTableToColumnInfo(r.Table)
+}
+
+// GetExpr implements the TableInfo interface
+func (r *RealTable) GetExpr() *sqlparser.AliasedTableExpr {
+	return r.ASTNode
+}
+
+// GetVindexTable implements the TableInfo interface
+func (r *RealTable) GetVindexTable() *vindexes.Table {
+	return r.Table
+}
+
+// Name implements the TableInfo interface
+func (r *RealTable) Name() (sqlparser.TableName, error) {
+	return r.ASTNode.TableName()
+}
+
+// Authoritative implements the TableInfo interface
+func (r *RealTable) Authoritative() bool {
+	return r.Table != nil && r.Table.ColumnListAuthoritative
+}
+
+// Matches implements the TableInfo interface
+func (r *RealTable) Matches(name sqlparser.TableName) bool {
+	return (name.Qualifier.IsEmpty() || name.Qualifier.String() == r.dbName) && r.tableName == name.Name.String()
+}
diff --git a/go/vt/vtgate/semantics/scoper.go b/go/vt/vtgate/semantics/scoper.go
index 10afefc4e3..7f909de68b 100644
--- a/go/vt/vtgate/semantics/scoper.go
+++ b/go/vt/vtgate/semantics/scoper.go
@@ -19,6 +19,10 @@ package semantics
 import (
 	"reflect"
 
+	vtrpcpb "vitess.io/vitess/go/vt/proto/vtrpc"
+	"vitess.io/vitess/go/vt/vterrors"
+	"vitess.io/vitess/go/vt/vtgate/engine"
+
 	"vitess.io/vitess/go/vt/sqlparser"
 )
 
@@ -29,6 +33,7 @@ type scoper struct {
 	wScope       map[*sqlparser.Select]*scope
 	sqlNodeScope map[scopeKey]*scope
 	scopes       []*scope
+	org          originable
 
 	// These scopes are only used for rewriting ORDER BY 1 and GROUP BY 1
 	specialExprScopes map[*sqlparser.Literal]*scope
@@ -57,8 +62,9 @@ func newScoper() *scoper {
 	}
 }
 
-func (s *scoper) down(cursor *sqlparser.Cursor) {
-	switch node := cursor.Node().(type) {
+func (s *scoper) down(cursor *sqlparser.Cursor) error {
+	node := cursor.Node()
+	switch node := node.(type) {
 	case *sqlparser.Select:
 		currScope := newScope(s.currentScope())
 		s.push(currScope)
@@ -86,14 +92,18 @@ func (s *scoper) down(cursor *sqlparser.Cursor) {
 			break
 		}
 
+		// adding a VTableInfo for each SELECT, so it can be used by GROUP BY, HAVING, ORDER BY
+		// the VTableInfo we are creating here should not be confused with derived tables' VTableInfo
 		wScope, exists := s.wScope[sel]
 		if !exists {
 			break
 		}
-
-		wScope.tables = append(wScope.tables, createVTableInfoForExpressions(node))
+		wScope.tables = append(wScope.tables, createVTableInfoForExpressions(node, s.currentScope().tables, s.org))
 	case sqlparser.OrderBy:
-		s.changeScopeForNode(cursor, scopeKey{node: cursor.Parent(), typ: orderBy})
+		err := s.changeScopeForNode(cursor, scopeKey{node: cursor.Parent(), typ: orderBy})
+		if err != nil {
+			return err
+		}
 		for _, order := range node {
 			lit := keepIntLiteral(order.Expr)
 			if lit != nil {
@@ -101,7 +111,10 @@ func (s *scoper) down(cursor *sqlparser.Cursor) {
 			}
 		}
 	case sqlparser.GroupBy:
-		s.changeScopeForNode(cursor, scopeKey{node: cursor.Parent(), typ: groupBy})
+		err := s.changeScopeForNode(cursor, scopeKey{node: cursor.Parent(), typ: groupBy})
+		if err != nil {
+			return err
+		}
 		for _, expr := range node {
 			lit := keepIntLiteral(expr)
 			if lit != nil {
@@ -112,8 +125,9 @@ func (s *scoper) down(cursor *sqlparser.Cursor) {
 		if node.Type != sqlparser.HavingClause {
 			break
 		}
-		s.changeScopeForNode(cursor, scopeKey{node: cursor.Parent(), typ: having})
+		return s.changeScopeForNode(cursor, scopeKey{node: cursor.Parent(), typ: having})
 	}
+	return nil
 }
 
 func keepIntLiteral(e sqlparser.Expr) *sqlparser.Literal {
@@ -128,7 +142,8 @@ func keepIntLiteral(e sqlparser.Expr) *sqlparser.Literal {
 }
 
 func (s *scoper) up(cursor *sqlparser.Cursor) error {
-	switch node := cursor.Node().(type) {
+	node := cursor.Node()
+	switch node := node.(type) {
 	case *sqlparser.Select, sqlparser.OrderBy, sqlparser.GroupBy:
 		s.popScope()
 	case *sqlparser.Where:
@@ -207,7 +222,7 @@ func (s *scoper) upPost(cursor *sqlparser.Cursor) error {
 	return nil
 }
 
-func (s *scoper) changeScopeForNode(cursor *sqlparser.Cursor, k scopeKey) {
+func (s *scoper) changeScopeForNode(cursor *sqlparser.Cursor, k scopeKey) error {
 	switch parent := cursor.Parent().(type) {
 	case *sqlparser.Select:
 		// In ORDER BY, GROUP BY and HAVING, we can see both the scope in the FROM part of the query, and the SELECT columns created
@@ -221,16 +236,34 @@ func (s *scoper) changeScopeForNode(cursor *sqlparser.Cursor, k scopeKey) {
 		nScope.selectStmt = incomingScope.selectStmt
 
 		if s.rScope[parent] != incomingScope {
-			panic("BUG: scope counts did not match")
+			return vterrors.Errorf(vtrpcpb.Code_INTERNAL, "BUG: scope counts did not match")
 		}
 	case *sqlparser.Union:
 		nScope := newScope(nil)
-		nScope.selectStmt = sqlparser.GetFirstSelect(parent)
+		firstSelect := sqlparser.GetFirstSelect(parent.FirstStatement)
+		nScope.selectStmt = firstSelect
+		tableInfo := createVTableInfoForExpressions(firstSelect.SelectExprs, nil /*needed for star expressions*/, s.org)
+		nScope.tables = append(nScope.tables, tableInfo)
+
+		for _, unionSelect := range parent.UnionSelects {
+			// TODO: this can probably be optimised
+			sel := sqlparser.GetFirstSelect(unionSelect.Statement)
+			thisTableInfo := createVTableInfoForExpressions(sel.SelectExprs, nil /*needed for star expressions*/, s.org)
+			if len(tableInfo.cols) != len(thisTableInfo.cols) {
+				return engine.ErrWrongNumberOfColumnsInSelect
+			}
+			for i, col := range tableInfo.cols {
+				// at this stage, we don't store the actual dependencies, we only store the expressions.
+				// only later will we walk the expression tree and figure out the deps. so, we need to create a
+				// composite expression that contains all the expressions in the SELECTs that this UNION consists of
+				tableInfo.cols[i] = sqlparser.AndExpressions(col, thisTableInfo.cols[i])
+			}
+		}
+
 		s.push(nScope)
 		s.sqlNodeScope[k] = nScope
-	default:
-		return
 	}
+	return nil
 }
 
 func (s *scoper) currentScope() *scope {
diff --git a/go/vt/vtgate/semantics/semantic_state.go b/go/vt/vtgate/semantics/semantic_state.go
index 99f32d509d..1613c2b2f9 100644
--- a/go/vt/vtgate/semantics/semantic_state.go
+++ b/go/vt/vtgate/semantics/semantic_state.go
@@ -17,6 +17,8 @@ limitations under the License.
 package semantics
 
 import (
+	"strings"
+
 	"vitess.io/vitess/go/vt/key"
 	querypb "vitess.io/vitess/go/vt/proto/query"
 	topodatapb "vitess.io/vitess/go/vt/proto/topodata"
@@ -39,15 +41,11 @@ type (
 		GetColumns() []ColumnInfo
 		IsActualTable() bool
 
-		// RecursiveDepsFor returns a pointer to the table set for the table that this column belongs to, if it can be found
-		// if the column is not found, nil will be returned instead. If the column is a derived table column, this method
-		// will recursively find the dependencies of the expression inside the derived table
-		RecursiveDepsFor(col *sqlparser.ColName, org originable, single bool) (*TableSet, *querypb.Type, error)
+		Dependencies(colName string, org originable) (dependencies, error)
 
-		// DepsFor finds the table that a column depends on. No recursing is done on derived tables
-		DepsFor(col *sqlparser.ColName, org originable, single bool) (*TableSet, error)
 		IsInfSchema() bool
 		GetExprFor(s string) (sqlparser.Expr, error)
+		GetTables(org originable) TableSet
 	}
 
 	// ColumnInfo contains information about columns
@@ -56,14 +54,6 @@ type (
 		Type querypb.Type
 	}
 
-	// RealTable contains the alias table expr and vindex table
-	RealTable struct {
-		dbName, tableName string
-		ASTNode           *sqlparser.AliasedTableExpr
-		Table             *vindexes.Table
-		isInfSchema       bool
-	}
-
 	// AliasedTable contains the alias table expr and vindex table
 	AliasedTable struct {
 		tableName   string
@@ -72,15 +62,6 @@ type (
 		isInfSchema bool
 	}
 
-	// vTableInfo is used to represent projected results, not real tables. It is used for
-	// ORDER BY, GROUP BY and HAVING that need to access result columns, and also for derived tables.
-	vTableInfo struct {
-		tableName   string
-		ASTNode     *sqlparser.AliasedTableExpr
-		columnNames []string
-		cols        []sqlparser.Expr
-	}
-
 	// VindexTable contains a vindexes.Vindex and a TableInfo. The former represents the vindex
 	// we are keeping information about, and the latter represents the additional table information
 	// (usually a RealTable or an AliasedTable) of our vindex.
@@ -104,14 +85,14 @@ type (
 		// This is only a real error if we are unable to plan the query as a single route
 		ProjectionErr error
 
-		// ExprBaseTableDeps contains the dependencies from the expression to the actual tables
+		// Recursive contains the dependencies from the expression to the actual tables
 		// in the query (i.e. not including derived tables). If an expression is a column on a derived table,
 		// this map will contain the accumulated dependencies for the column expression inside the derived table
-		ExprBaseTableDeps ExprDependencies
+		Recursive ExprDependencies
 
-		// ExprDeps keeps information about dependencies for expressions, no matter if they are
-		// against real tables or derived tables
-		ExprDeps ExprDependencies
+		// Direct keeps information about the closest dependency for an expression.
+		// It does not recurse inside derived tables and the like to find the original dependencies
+		Direct ExprDependencies
 
 		exprTypes   map[sqlparser.Expr]querypb.Type
 		selectScope map[*sqlparser.Select]*scope
@@ -147,145 +128,59 @@ type (
 	}
 )
 
-// GetExprFor implements the TableInfo interface
-func (v *VindexTable) GetExprFor(s string) (sqlparser.Expr, error) {
-	panic("implement me")
-}
-
-// CopyDependencies copies the dependencies from one expression into the other
-func (st *SemTable) CopyDependencies(from, to sqlparser.Expr) {
-	st.ExprBaseTableDeps[to] = st.BaseTableDependencies(from)
-	st.ExprDeps[to] = st.Dependencies(from)
-}
-
-// GetExprFor implements the TableInfo interface
-func (v *vTableInfo) GetExprFor(s string) (sqlparser.Expr, error) {
-	for i, colName := range v.columnNames {
-		if colName == s {
-			return v.cols[i], nil
-		}
-	}
-	return nil, vterrors.NewErrorf(vtrpcpb.Code_NOT_FOUND, vterrors.BadFieldError, "Unknown column '%s' in 'field list'", s)
-}
+var (
+	// ErrMultipleTables refers to an error happening when something should be used only for single tables
+	ErrMultipleTables = vterrors.Errorf(vtrpcpb.Code_INTERNAL, "[BUG] should only be used for single tables")
+)
 
-// GetExprFor implements the TableInfo interface
-func (a *AliasedTable) GetExprFor(s string) (sqlparser.Expr, error) {
-	return nil, vterrors.Errorf(vtrpcpb.Code_INTERNAL, "Unknown column '%s' in 'field list'", s)
+// Dependencies implements the TableInfo interface
+func (v *VindexTable) Dependencies(colName string, org originable) (dependencies, error) {
+	return v.Table.Dependencies(colName, org)
 }
 
-// GetExprFor implements the TableInfo interface
-func (r *RealTable) GetExprFor(s string) (sqlparser.Expr, error) {
-	return nil, vterrors.Errorf(vtrpcpb.Code_INTERNAL, "Unknown column '%s' in 'field list'", s)
+// Dependencies implements the TableInfo interface
+func (a *AliasedTable) Dependencies(colName string, org originable) (dependencies, error) {
+	return depsForAliasedAndRealTables(colName, org, a.ASTNode, a.GetColumns(), a.Authoritative())
 }
 
-// RecursiveDepsFor implements the TableInfo interface
-func (v *vTableInfo) RecursiveDepsFor(col *sqlparser.ColName, org originable, single bool) (*TableSet, *querypb.Type, error) {
-	if !col.Qualifier.IsEmpty() && (v.ASTNode == nil || v.tableName != col.Qualifier.Name.String()) {
-		// if we have a table qualifier in the expression, we know that it is not referencing an aliased table
-		return nil, nil, nil
-	}
-	var tsF TableSet
-	var qtF *querypb.Type
-	found := false
-	for i, colName := range v.columnNames {
-		if col.Name.String() == colName {
-			ts, qt := org.depsForExpr(v.cols[i])
-			if !found {
-				tsF = ts
-				qtF = qt
-			} else if tsF != ts {
-				// the column does not resolve to the same TableSet. Therefore, it is an ambiguous column reference.
-				return nil, nil, vterrors.NewErrorf(vtrpcpb.Code_INVALID_ARGUMENT, vterrors.NonUniqError, "Column '%s' is ambiguous", colName)
-			}
-			found = true
+func depsForAliasedAndRealTables(colName string, org originable, node *sqlparser.AliasedTableExpr, columns []ColumnInfo, authoritative bool) (dependencies, error) {
+	ts := org.tableSetFor(node)
+	for _, info := range columns {
+		if strings.EqualFold(info.Name, colName) {
+			return createCertain(ts, ts, &info.Type), nil
 		}
 	}
-	if found {
-		return &tsF, qtF, nil
-	}
-	return nil, nil, nil
-}
 
-// DepsFor implements the TableInfo interface
-func (v *vTableInfo) DepsFor(col *sqlparser.ColName, org originable, _ bool) (*TableSet, error) {
-	if v.ASTNode == nil {
-		return nil, nil
+	if authoritative {
+		return &nothing{}, nil
 	}
-	if !col.Qualifier.IsEmpty() && (v.ASTNode == nil || v.tableName != col.Qualifier.Name.String()) {
-		// if we have a table qualifier in the expression, we know that it is not referencing an aliased table
-		return nil, nil
-	}
-	for _, colName := range v.columnNames {
-		if col.Name.String() == colName {
-			ts := org.tableSetFor(v.ASTNode)
-			return &ts, nil
-		}
-	}
-	return nil, nil
-}
-
-// RecursiveDepsFor implements the TableInfo interface
-func (a *AliasedTable) RecursiveDepsFor(col *sqlparser.ColName, org originable, single bool) (*TableSet, *querypb.Type, error) {
-	return depsFor(col, org, single, a.ASTNode, a.GetColumns(), a.Authoritative())
+	return createUncertain(ts, ts), nil
 }
 
-// DepsFor implements the TableInfo interface
-func (a *AliasedTable) DepsFor(col *sqlparser.ColName, org originable, single bool) (*TableSet, error) {
-	ts, _, err := a.RecursiveDepsFor(col, org, single)
-	return ts, err
+// GetTables implements the TableInfo interface
+func (v *VindexTable) GetTables(org originable) TableSet {
+	return v.Table.GetTables(org)
 }
 
-// RecursiveDepsFor implements the TableInfo interface
-func (r *RealTable) RecursiveDepsFor(col *sqlparser.ColName, org originable, single bool) (*TableSet, *querypb.Type, error) {
-	return depsFor(col, org, single, r.ASTNode, r.GetColumns(), r.Authoritative())
+// GetTables implements the TableInfo interface
+func (a *AliasedTable) GetTables(org originable) TableSet {
+	return org.tableSetFor(a.ASTNode)
 }
 
-// DepsFor implements the TableInfo interface
-func (r *RealTable) DepsFor(col *sqlparser.ColName, org originable, single bool) (*TableSet, error) {
-	ts, _, err := r.RecursiveDepsFor(col, org, single)
-	return ts, err
+// GetExprFor implements the TableInfo interface
+func (v *VindexTable) GetExprFor(_ string) (sqlparser.Expr, error) {
+	panic("implement me")
 }
 
-// depsFor implements the TableInfo interface for RealTable and AliasedTable
-func depsFor(
-	col *sqlparser.ColName,
-	org originable,
-	single bool,
-	astNode *sqlparser.AliasedTableExpr,
-	cols []ColumnInfo,
-	authoritative bool,
-) (*TableSet, *querypb.Type, error) {
-	// if we know that we are the only table in the scope, there is no doubt - the column must belong to the table
-	if single {
-		ts := org.tableSetFor(astNode)
-
-		for _, info := range cols {
-			if col.Name.EqualString(info.Name) {
-				return &ts, &info.Type, nil
-			}
-		}
-
-		if authoritative {
-			// if we are authoritative and we can't find the column, we should fail
-			return nil, nil, vterrors.NewErrorf(vtrpcpb.Code_NOT_FOUND, vterrors.BadFieldError, "Unknown column '%s' in 'field list'", col.Name.String())
-		}
-
-		// it's probably the correct table, but we don't have enough info to be sure or figure out the type of the column
-		return &ts, nil, nil
-	}
-
-	for _, info := range cols {
-		if col.Name.EqualString(info.Name) {
-			ts := org.tableSetFor(astNode)
-			return &ts, &info.Type, nil
-		}
-	}
-	return nil, nil, nil
+// CopyDependencies copies the dependencies from one expression into the other
+func (st *SemTable) CopyDependencies(from, to sqlparser.Expr) {
+	st.Recursive[to] = st.RecursiveDeps(from)
+	st.Direct[to] = st.DirectDeps(from)
 }
 
-// IsInfSchema implements the TableInfo interface
-func (v *vTableInfo) IsInfSchema() bool {
-	return false
+// GetExprFor implements the TableInfo interface
+func (a *AliasedTable) GetExprFor(s string) (sqlparser.Expr, error) {
+	return nil, vterrors.Errorf(vtrpcpb.Code_INTERNAL, "Unknown column '%s' in 'field list'", s)
 }
 
 // IsInfSchema implements the TableInfo interface
@@ -293,67 +188,19 @@ func (a *AliasedTable) IsInfSchema() bool {
 	return a.isInfSchema
 }
 
-// IsInfSchema implements the TableInfo interface
-func (r *RealTable) IsInfSchema() bool {
-	return r.isInfSchema
-}
-
-// IsActualTable implements the TableInfo interface
-func (v *vTableInfo) IsActualTable() bool {
-	return false
-}
-
 // IsActualTable implements the TableInfo interface
 func (a *AliasedTable) IsActualTable() bool {
 	return true
 }
 
-// IsActualTable implements the TableInfo interface
-func (r *RealTable) IsActualTable() bool {
-	return true
-}
-
-var _ TableInfo = (*RealTable)(nil)
 var _ TableInfo = (*AliasedTable)(nil)
-var _ TableInfo = (*vTableInfo)(nil)
 var _ TableInfo = (*VindexTable)(nil)
 
-func (v *vTableInfo) Matches(name sqlparser.TableName) bool {
-	return v.tableName == name.Name.String() && name.Qualifier.IsEmpty()
-}
-
-func (v *vTableInfo) Authoritative() bool {
-	return true
-}
-
-func (v *vTableInfo) Name() (sqlparser.TableName, error) {
-	return v.ASTNode.TableName()
-}
-
-func (v *vTableInfo) GetExpr() *sqlparser.AliasedTableExpr {
-	return v.ASTNode
-}
-
-// GetVindexTable implements the TableInfo interface
-func (v *vTableInfo) GetVindexTable() *vindexes.Table {
-	return nil
-}
-
 // GetVindexTable implements the TableInfo interface
 func (v *VindexTable) GetVindexTable() *vindexes.Table {
 	return v.Table.GetVindexTable()
 }
 
-func (v *vTableInfo) GetColumns() []ColumnInfo {
-	cols := make([]ColumnInfo, 0, len(v.columnNames))
-	for _, col := range v.columnNames {
-		cols = append(cols, ColumnInfo{
-			Name: col,
-		})
-	}
-	return cols
-}
-
 func vindexTableToColumnInfo(tbl *vindexes.Table) []ColumnInfo {
 	if tbl == nil {
 		return nil
@@ -416,41 +263,6 @@ func (a *AliasedTable) Matches(name sqlparser.TableName) bool {
 	return a.tableName == name.Name.String() && name.Qualifier.IsEmpty()
 }
 
-// GetColumns implements the TableInfo interface
-func (r *RealTable) GetColumns() []ColumnInfo {
-	return vindexTableToColumnInfo(r.Table)
-}
-
-// GetExpr implements the TableInfo interface
-func (r *RealTable) GetExpr() *sqlparser.AliasedTableExpr {
-	return r.ASTNode
-}
-
-// GetVindexTable implements the TableInfo interface
-func (r *RealTable) GetVindexTable() *vindexes.Table {
-	return r.Table
-}
-
-// Name implements the TableInfo interface
-func (r *RealTable) Name() (sqlparser.TableName, error) {
-	return r.ASTNode.TableName()
-}
-
-// Authoritative implements the TableInfo interface
-func (r *RealTable) Authoritative() bool {
-	return r.Table != nil && r.Table.ColumnListAuthoritative
-}
-
-// Matches implements the TableInfo interface
-func (r *RealTable) Matches(name sqlparser.TableName) bool {
-	if !name.Qualifier.IsEmpty() {
-		if r.dbName != name.Qualifier.String() {
-			return false
-		}
-	}
-	return r.tableName == name.Name.String()
-}
-
 // Matches implements the TableInfo interface
 func (v *VindexTable) Matches(name sqlparser.TableName) bool {
 	return v.Table.Matches(name)
@@ -481,16 +293,6 @@ func (v *VindexTable) IsActualTable() bool {
 	return true
 }
 
-// RecursiveDepsFor implements the TableInfo interface
-func (v *VindexTable) RecursiveDepsFor(col *sqlparser.ColName, org originable, single bool) (*TableSet, *querypb.Type, error) {
-	return v.Table.RecursiveDepsFor(col, org, single)
-}
-
-// DepsFor implements the TableInfo interface
-func (v *VindexTable) DepsFor(col *sqlparser.ColName, org originable, single bool) (*TableSet, error) {
-	return v.Table.DepsFor(col, org, single)
-}
-
 // IsInfSchema implements the TableInfo interface
 func (v *VindexTable) IsInfSchema() bool {
 	return v.Table.IsInfSchema()
@@ -498,7 +300,7 @@ func (v *VindexTable) IsInfSchema() bool {
 
 // NewSemTable creates a new empty SemTable
 func NewSemTable() *SemTable {
-	return &SemTable{ExprBaseTableDeps: map[sqlparser.Expr]TableSet{}, ColumnEqualities: map[columnName][]sqlparser.Expr{}}
+	return &SemTable{Recursive: map[sqlparser.Expr]TableSet{}, ColumnEqualities: map[columnName][]sqlparser.Expr{}}
 }
 
 // TableSetFor returns the bitmask for this particular table
@@ -514,24 +316,24 @@ func (st *SemTable) TableSetFor(t *sqlparser.AliasedTableExpr) TableSet {
 // TableInfoFor returns the table info for the table set. It should contains only single table.
 func (st *SemTable) TableInfoFor(id TableSet) (TableInfo, error) {
 	if id.NumberOfTables() > 1 {
-		return nil, vterrors.Errorf(vtrpcpb.Code_INTERNAL, "[BUG] should only be used for single tables")
+		return nil, ErrMultipleTables
 	}
 	return st.Tables[id.TableOffset()], nil
 }
 
-// BaseTableDependencies return the table dependencies of the expression.
-func (st *SemTable) BaseTableDependencies(expr sqlparser.Expr) TableSet {
-	return st.ExprBaseTableDeps.Dependencies(expr)
+// RecursiveDeps return the table dependencies of the expression.
+func (st *SemTable) RecursiveDeps(expr sqlparser.Expr) TableSet {
+	return st.Recursive.Dependencies(expr)
 }
 
-// Dependencies return the table dependencies of the expression.
-func (st *SemTable) Dependencies(expr sqlparser.Expr) TableSet {
-	return st.ExprDeps.Dependencies(expr)
+// DirectDeps return the table dependencies of the expression.
+func (st *SemTable) DirectDeps(expr sqlparser.Expr) TableSet {
+	return st.Direct.Dependencies(expr)
 }
 
 // AddColumnEquality adds a relation of the given colName to the ColumnEqualities map
 func (st *SemTable) AddColumnEquality(colName *sqlparser.ColName, expr sqlparser.Expr) {
-	ts := st.ExprDeps.Dependencies(colName)
+	ts := st.Direct.Dependencies(colName)
 	columnName := columnName{
 		Table:      ts,
 		ColumnName: colName.Name.String(),
@@ -546,9 +348,9 @@ func (st *SemTable) GetExprAndEqualities(expr sqlparser.Expr) []sqlparser.Expr {
 	result := []sqlparser.Expr{expr}
 	switch expr := expr.(type) {
 	case *sqlparser.ColName:
-		table := st.Dependencies(expr)
-		key := columnName{Table: table, ColumnName: expr.Name.String()}
-		result = append(result, st.ColumnEqualities[key]...)
+		table := st.DirectDeps(expr)
+		k := columnName{Table: table, ColumnName: expr.Name.String()}
+		result = append(result, st.ColumnEqualities[k]...)
 	}
 	return result
 }
@@ -556,7 +358,7 @@ func (st *SemTable) GetExprAndEqualities(expr sqlparser.Expr) []sqlparser.Expr {
 // TableInfoForExpr returns the table info of the table that this expression depends on.
 // Careful: this only works for expressions that have a single table dependency
 func (st *SemTable) TableInfoForExpr(expr sqlparser.Expr) (TableInfo, error) {
-	return st.TableInfoFor(st.ExprDeps.Dependencies(expr))
+	return st.TableInfoFor(st.Direct.Dependencies(expr))
 }
 
 // GetSelectTables returns the table in the select.
@@ -569,7 +371,7 @@ func (st *SemTable) GetSelectTables(node *sqlparser.Select) []TableInfo {
 func (st *SemTable) AddExprs(tbl *sqlparser.AliasedTableExpr, cols sqlparser.SelectExprs) {
 	tableSet := st.TableSetFor(tbl)
 	for _, col := range cols {
-		st.ExprBaseTableDeps[col.(*sqlparser.AliasedExpr).Expr] = tableSet
+		st.Recursive[col.(*sqlparser.AliasedExpr).Expr] = tableSet
 	}
 }
 
@@ -618,13 +420,19 @@ func newScope(parent *scope) *scope {
 }
 
 func (s *scope) addTable(info TableInfo) error {
-	for _, scopeTable := range s.tables {
-		scopeTableName, err := scopeTable.Name()
+	name, err := info.Name()
+	if err != nil {
+		return err
+	}
+	tblName := name.Name.String()
+	for _, table := range s.tables {
+		name, err := table.Name()
 		if err != nil {
 			return err
 		}
-		if info.Matches(scopeTableName) {
-			return vterrors.NewErrorf(vtrpcpb.Code_INVALID_ARGUMENT, vterrors.NonUniqTable, "Not unique table/alias: '%s'", scopeTableName.Name.String())
+
+		if tblName == name.Name.String() {
+			return vterrors.NewErrorf(vtrpcpb.Code_INVALID_ARGUMENT, vterrors.NonUniqTable, "Not unique table/alias: '%s'", name.Name.String())
 		}
 	}
 	s.tables = append(s.tables, info)
diff --git a/go/vt/vtgate/semantics/table_collector.go b/go/vt/vtgate/semantics/table_collector.go
index 0201b834c4..4fbf4f49de 100644
--- a/go/vt/vtgate/semantics/table_collector.go
+++ b/go/vt/vtgate/semantics/table_collector.go
@@ -28,6 +28,7 @@ type tableCollector struct {
 	scoper    *scoper
 	si        SchemaInformation
 	currentDb string
+	org       originable
 }
 
 func newTableCollector(scoper *scoper, si SchemaInformation, currentDb string) *tableCollector {
@@ -48,7 +49,8 @@ func (tc *tableCollector) up(cursor *sqlparser.Cursor) error {
 	case *sqlparser.DerivedTable:
 		switch sel := t.Select.(type) {
 		case *sqlparser.Select:
-			tableInfo := createVTableInfoForExpressions(sel.SelectExprs)
+			tables := tc.scoper.wScope[sel]
+			tableInfo := createDerivedTableForExpressions(sqlparser.GetFirstSelect(sel).SelectExprs, tables.tables, tc.org)
 			if err := tableInfo.checkForDuplicates(); err != nil {
 				return err
 			}
@@ -61,7 +63,8 @@ func (tc *tableCollector) up(cursor *sqlparser.Cursor) error {
 			return scope.addTable(tableInfo)
 
 		case *sqlparser.Union:
-			tableInfo := createVTableInfoForExpressions(sqlparser.GetFirstSelect(sel).SelectExprs)
+			tables := tc.scoper.wScope[sel.FirstStatement.(*sqlparser.Select)]
+			tableInfo := createDerivedTableForExpressions(sqlparser.GetFirstSelect(sel).SelectExprs, tables.tables, tc.org)
 			if err := tableInfo.checkForDuplicates(); err != nil {
 				return err
 			}
diff --git a/go/vt/vtgate/semantics/vtable.go b/go/vt/vtgate/semantics/vtable.go
new file mode 100644
index 0000000000..01fead65b0
--- /dev/null
+++ b/go/vt/vtgate/semantics/vtable.go
@@ -0,0 +1,156 @@
+/*
+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 semantics
+
+import (
+	vtrpcpb "vitess.io/vitess/go/vt/proto/vtrpc"
+	"vitess.io/vitess/go/vt/sqlparser"
+	"vitess.io/vitess/go/vt/vterrors"
+	"vitess.io/vitess/go/vt/vtgate/vindexes"
+)
+
+// vTableInfo is used to represent projected results, not real tables. It is used for
+// ORDER BY, GROUP BY and HAVING that need to access result columns
+type vTableInfo struct {
+	tableName   string
+	columnNames []string
+	cols        []sqlparser.Expr
+	tables      TableSet
+}
+
+var _ TableInfo = (*vTableInfo)(nil)
+
+// Dependencies implements the TableInfo interface
+func (v *vTableInfo) Dependencies(colName string, org originable) (dependencies, error) {
+	var deps dependencies = &nothing{}
+	var err error
+	for i, name := range v.columnNames {
+		if name != colName {
+			continue
+		}
+		recursiveDeps, qt := org.depsForExpr(v.cols[i])
+
+		var directDeps TableSet
+		/*
+				If we find a match, it means the query looks something like:
+				SELECT 1 as x FROM t1 ORDER BY/GROUP BY x - d/r: 0/0
+				SELECT t1.x as x FROM t1 ORDER BY/GROUP BY x - d/r: 0/1
+				SELECT x FROM t1 ORDER BY/GROUP BY x - d/r: 1/1
+
+			    Now, after figuring out the recursive deps
+		*/
+		if recursiveDeps.NumberOfTables() > 0 {
+			directDeps = recursiveDeps
+		}
+
+		newDeps := createCertain(directDeps, recursiveDeps, qt)
+		deps, err = deps.Merge(newDeps)
+		if err != nil {
+			return nil, err
+		}
+	}
+	if deps.Empty() && v.hasStar() {
+		return createUncertain(v.tables, v.tables), nil
+	}
+	return deps, nil
+}
+
+// IsInfSchema implements the TableInfo interface
+func (v *vTableInfo) IsInfSchema() bool {
+	return false
+}
+
+// IsActualTable implements the TableInfo interface
+func (v *vTableInfo) IsActualTable() bool {
+	return false
+}
+
+func (v *vTableInfo) Matches(name sqlparser.TableName) bool {
+	return v.tableName == name.Name.String() && name.Qualifier.IsEmpty()
+}
+
+func (v *vTableInfo) Authoritative() bool {
+	return true
+}
+
+func (v *vTableInfo) Name() (sqlparser.TableName, error) {
+	return sqlparser.TableName{}, vterrors.Errorf(vtrpcpb.Code_INTERNAL, "oh noes")
+}
+
+func (v *vTableInfo) GetExpr() *sqlparser.AliasedTableExpr {
+	return nil
+}
+
+// GetVindexTable implements the TableInfo interface
+func (v *vTableInfo) GetVindexTable() *vindexes.Table {
+	return nil
+}
+
+func (v *vTableInfo) GetColumns() []ColumnInfo {
+	cols := make([]ColumnInfo, 0, len(v.columnNames))
+	for _, col := range v.columnNames {
+		cols = append(cols, ColumnInfo{
+			Name: col,
+		})
+	}
+	return cols
+}
+
+func (v *vTableInfo) hasStar() bool {
+	return v.tables > 0
+}
+
+// GetTables implements the TableInfo interface
+func (v *vTableInfo) GetTables(org originable) TableSet {
+	return v.tables
+}
+
+// GetExprFor implements the TableInfo interface
+func (v *vTableInfo) GetExprFor(s string) (sqlparser.Expr, error) {
+	for i, colName := range v.columnNames {
+		if colName == s {
+			return v.cols[i], nil
+		}
+	}
+	return nil, vterrors.NewErrorf(vtrpcpb.Code_NOT_FOUND, vterrors.BadFieldError, "Unknown column '%s' in 'field list'", s)
+}
+
+func createVTableInfoForExpressions(expressions sqlparser.SelectExprs, tables []TableInfo, org originable) *vTableInfo {
+	vTbl := &vTableInfo{}
+	for _, selectExpr := range expressions {
+		switch expr := selectExpr.(type) {
+		case *sqlparser.AliasedExpr:
+			vTbl.cols = append(vTbl.cols, expr.Expr)
+			if expr.As.IsEmpty() {
+				switch expr := expr.Expr.(type) {
+				case *sqlparser.ColName:
+					// for projections, we strip out the qualifier and keep only the column name
+					vTbl.columnNames = append(vTbl.columnNames, expr.Name.String())
+				default:
+					vTbl.columnNames = append(vTbl.columnNames, sqlparser.String(expr))
+				}
+			} else {
+				vTbl.columnNames = append(vTbl.columnNames, expr.As.String())
+			}
+		case *sqlparser.StarExpr:
+			for _, table := range tables {
+				vTbl.tables |= table.GetTables(org)
+			}
+		}
+	}
+	return vTbl
+}


Test patch:
diff --git a/go/vt/vtgate/planbuilder/abstract/queryprojection_test.go b/go/vt/vtgate/planbuilder/abstract/queryprojection_test.go
index 96b018c91d..0977ff854e 100644
--- a/go/vt/vtgate/planbuilder/abstract/queryprojection_test.go
+++ b/go/vt/vtgate/planbuilder/abstract/queryprojection_test.go
@@ -36,8 +36,7 @@ func TestQP(t *testing.T) {
 		expOrder []OrderBy
 	}{
 		{
-			sql:    "select * from user",
-			expErr: "gen4 does not yet support: *sqlparser.StarExpr in select list",
+			sql: "select * from user",
 		},
 		{
 			sql:    "select next value from user_seq",
diff --git a/go/vt/vtgate/planbuilder/testdata/aggr_cases.txt b/go/vt/vtgate/planbuilder/testdata/aggr_cases.txt
index 87dcd0edc5..b792eed458 100644
--- a/go/vt/vtgate/planbuilder/testdata/aggr_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/aggr_cases.txt
@@ -755,7 +755,7 @@ Gen4 plan same as above
     "Table": "`user`"
   }
 }
-Gen4 error: Expression of SELECT list is not in GROUP BY clause and contains nonaggregated column 'val' which is not functionally dependent on columns in GROUP BY clause; this is incompatible with sql_mode=only_full_group_by
+Gen4 error: Expression of SELECT list is not in GROUP BY clause and contains nonaggregated column 'val as id' which is not functionally dependent on columns in GROUP BY clause; this is incompatible with sql_mode=only_full_group_by
 
 # group by a unique vindex where it should skip non-aliased expressions.
 "select *, id, 1+count(*) from user group by id"
@@ -2203,9 +2203,9 @@ Gen4 plan same as above
           "Name": "user",
           "Sharded": true
         },
-        "FieldQuery": "select col1, col2, weight_string(col1), weight_string(col2) from `user` where 1 != 1",
+        "FieldQuery": "select col1, col2, weight_string(col1), weight_string(col2) from `user` where 1 != 1 group by col1, col2",
         "OrderBy": "(0|2) ASC, (1|3) ASC",
-        "Query": "select distinct col1, col2, weight_string(col1), weight_string(col2) from `user` order by col1 asc, col2 asc",
+        "Query": "select distinct col1, col2, weight_string(col1), weight_string(col2) from `user` group by col1, col2 order by col1 asc, col2 asc",
         "Table": "`user`"
       }
     ]
diff --git a/go/vt/vtgate/planbuilder/testdata/filter_cases.txt b/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
index 4f31c23bba..d216a9c648 100644
--- a/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
@@ -2123,22 +2123,6 @@ Gen4 plan same as above
 }
 Gen4 plan same as above
 
-# outer and inner subquery route reference the same "uu.id" name
-# but they refer to different things. The first reference is to the outermost query,
-# and the second reference is to the innermost 'from' subquery.
-# This query will never work as the inner derived table is only selecting one of the column
-"select id2 from user uu where id in (select id from user where id = uu.id and user.col in (select col from (select id from user_extra where user_id = 5) uu where uu.user_id = uu.id))"
-"unsupported: cross-shard correlated subquery"
-Gen4 error: symbol uu.user_id not found
-
-# outer and inner subquery route reference the same "uu.id" name
-# but they refer to different things. The first reference is to the outermost query,
-# and the second reference is to the innermost 'from' subquery.
-# changed to project all the columns from the derived tables.
-"select id2 from user uu where id in (select id from user where id = uu.id and user.col in (select col from (select col, id, user_id from user_extra where user_id = 5) uu where uu.user_id = uu.id))"
-"unsupported: cross-shard correlated subquery"
-Gen4 plan same as above
-
 # Select with equals null
 "select id from music where id = null"
 {
diff --git a/go/vt/vtgate/planbuilder/testdata/from_cases.txt b/go/vt/vtgate/planbuilder/testdata/from_cases.txt
index 0dbd2316ad..9ee168b908 100644
--- a/go/vt/vtgate/planbuilder/testdata/from_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/from_cases.txt
@@ -162,6 +162,7 @@ Gen4 plan same as above
     "Table": "`user`"
   }
 }
+Gen4 plan same as above
 
 # routing rules where table name matches, and there's an alias.
 "select * from second_user.user as a"
@@ -180,6 +181,7 @@ Gen4 plan same as above
     "Table": "`user`"
   }
 }
+Gen4 plan same as above
 
 # routing rules where table name does not match, and there's no alias.
 "select * from route1"
@@ -198,6 +200,7 @@ Gen4 plan same as above
     "Table": "`user`"
   }
 }
+Gen4 plan same as above
 
 # routing rules where table name does not match, and there's an alias.
 "select * from route1 as a"
@@ -216,6 +219,7 @@ Gen4 plan same as above
     "Table": "`user`"
   }
 }
+Gen4 plan same as above
 
 # routing rules with primary targeting
 "select * from primary_redirect"
@@ -234,6 +238,7 @@ Gen4 plan same as above
     "Table": "`user`"
   }
 }
+Gen4 plan same as above
 
 # routing rules bad table
 "select * from bad_table"
@@ -1986,21 +1991,7 @@ Gen4 error: symbol t.col not found
     "Table": "`user`"
   }
 }
-{
-  "QueryType": "SELECT",
-  "Original": "select id from (select id+col as foo from route1) as t where foo = 5",
-  "Instructions": {
-    "OperatorType": "Route",
-    "Variant": "SelectScatter",
-    "Keyspace": {
-      "Name": "user",
-      "Sharded": true
-    },
-    "FieldQuery": "select id from (select id + col as foo from `user` as route1 where 1 != 1) as t where 1 != 1",
-    "Query": "select id from (select id + col as foo from `user` as route1 where id + col = 5) as t",
-    "Table": "`user`"
-  }
-}
+"symbol id not found"
 
 # push predicate on joined derived tables
 "select t.id from (select id, textcol1 as baz from route1) as t join (select id, textcol1+textcol1 as baz from user) as s ON t.id = s.id WHERE t.baz = '3' AND s.baz = '3'"
@@ -3973,3 +3964,22 @@ Gen4 plan same as above
     "Table": "information_schema.key_column_usage, information_schema.referential_constraints"
   }
 }
+
+# select star from derived table on expandable and unsharded table
+"select u.* from (select * from unsharded) u"
+{
+  "QueryType": "SELECT",
+  "Original": "select u.* from (select * from unsharded) u",
+  "Instructions": {
+    "OperatorType": "Route",
+    "Variant": "SelectUnsharded",
+    "Keyspace": {
+      "Name": "main",
+      "Sharded": false
+    },
+    "FieldQuery": "select u.* from (select * from unsharded where 1 != 1) as u where 1 != 1",
+    "Query": "select u.* from (select * from unsharded) as u",
+    "Table": "unsharded"
+  }
+}
+Gen4 plan same as above
diff --git a/go/vt/vtgate/planbuilder/testdata/postprocess_cases.txt b/go/vt/vtgate/planbuilder/testdata/postprocess_cases.txt
index 601c21c8bf..c914592767 100644
--- a/go/vt/vtgate/planbuilder/testdata/postprocess_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/postprocess_cases.txt
@@ -34,7 +34,8 @@
 # ambiguous symbol reference
 "select user.col1, user_extra.col1 from user join user_extra having col1 = 2"
 "ambiguous symbol reference: col1"
-Gen4 error: Column 'col1' is ambiguous
+Gen4 error: Column 'col1' in field list is ambiguous
+# TODO: this should be 'Column 'col1' in having clause is ambiguous'
 
 # non-ambiguous symbol reference
 "select user.col1, user_extra.col1 from user join user_extra having user_extra.col1 = 2"
@@ -1578,6 +1579,7 @@ Gen4 plan same as above
     ]
   }
 }
+Gen4 plan same as above
 
 # scatter limit after pullout subquery
 "select col from user where col in (select col1 from user) limit 1"
diff --git a/go/vt/vtgate/planbuilder/testdata/select_cases.txt b/go/vt/vtgate/planbuilder/testdata/select_cases.txt
index a24cb92e26..7c1bd45a0f 100644
--- a/go/vt/vtgate/planbuilder/testdata/select_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/select_cases.txt
@@ -34,6 +34,7 @@ Gen4 plan same as above
     "Table": "`user`"
   }
 }
+Gen4 plan same as above
 
 # unqualified '*' expression for simple route
 "select * from user"
@@ -52,6 +53,7 @@ Gen4 plan same as above
     "Table": "`user`"
   }
 }
+Gen4 plan same as above
 
 # select with timeout directive sets QueryTimeout in the route
 "select /*vt+ QUERY_TIMEOUT_MS=1000 */ * from user"
@@ -70,6 +72,7 @@ Gen4 plan same as above
     "Table": "`user`"
   }
 }
+Gen4 plan same as above
 
 # select aggregation with timeout directive sets QueryTimeout in the route
 "select /*vt+ QUERY_TIMEOUT_MS=1000 */ count(*) from user"
@@ -141,6 +144,7 @@ Gen4 plan same as above
     ]
   }
 }
+Gen4 plan same as above
 
 # select with partial scatter directive
 "select /*vt+ SCATTER_ERRORS_AS_WARNINGS */ * from user"
@@ -160,6 +164,7 @@ Gen4 plan same as above
     "Table": "`user`"
   }
 }
+Gen4 plan same as above
 
 # select aggregation with partial scatter directive
 "select /*vt+ SCATTER_ERRORS_AS_WARNINGS=1 */ count(*) from user"
@@ -283,6 +288,7 @@ Gen4 plan same as above
     ]
   }
 }
+Gen4 plan same as above
 
 # qualified '*' expression for simple route
 "select user.* from user"
@@ -301,6 +307,7 @@ Gen4 plan same as above
     "Table": "`user`"
   }
 }
+Gen4 plan same as above
 
 # fully qualified '*' expression for simple route
 "select user.user.* from user.user"
@@ -319,6 +326,7 @@ Gen4 plan same as above
     "Table": "`user`"
   }
 }
+Gen4 plan same as above
 
 # select * from authoritative table
 "select * from authoritative"
@@ -958,6 +966,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/planbuilder/testdata/systemtables_cases.txt b/go/vt/vtgate/planbuilder/testdata/systemtables_cases.txt
index 40f2aae40c..ade8525a6e 100644
--- a/go/vt/vtgate/planbuilder/testdata/systemtables_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/systemtables_cases.txt
@@ -606,6 +606,23 @@ Gen4 plan same as above
     "Table": "information_schema.`tables`"
   }
 }
+{
+  "QueryType": "SELECT",
+  "Original": "SELECT table_name FROM (SELECT * FROM information_schema.tables WHERE table_schema = 'table_schema') _subquery WHERE _subquery.table_type = 'table_type' AND _subquery.table_name = 'table_name'",
+  "Instructions": {
+    "OperatorType": "Route",
+    "Variant": "SelectDBA",
+    "Keyspace": {
+      "Name": "main",
+      "Sharded": false
+    },
+    "FieldQuery": "select table_name from (select * from information_schema.`tables` where 1 != 1) as _subquery where 1 != 1",
+    "Query": "select table_name from (select * from information_schema.`tables` where table_schema = :__vtschemaname and _subquery.table_type = 'table_type' and _subquery.table_name = :_subquery_table_name) as _subquery",
+    "SysTableTableName": "[_subquery_table_name:VARBINARY(\"table_name\")]",
+    "SysTableTableSchema": "[VARBINARY(\"table_schema\")]",
+    "Table": "information_schema.`tables`"
+  }
+}
 
 # two predicates specifying the database for the same table work if the database is the same
 "SELECT cc.constraint_name AS 'name' FROM information_schema.check_constraints cc  WHERE cc.constraint_schema = 'a' AND cc.table_schema = 'a'"
@@ -801,3 +818,126 @@ Gen4 plan same as above
   }
 }
 Gen4 plan same as above
+
+# expand star with information schema
+"select x.table_name from (select a.* from information_schema.key_column_usage a) x"
+{
+  "QueryType": "SELECT",
+  "Original": "select x.table_name from (select a.* from information_schema.key_column_usage a) x",
+  "Instructions": {
+    "OperatorType": "Route",
+    "Variant": "SelectDBA",
+    "Keyspace": {
+      "Name": "main",
+      "Sharded": false
+    },
+    "FieldQuery": "select x.table_name from (select a.* from information_schema.key_column_usage as a where 1 != 1) as x where 1 != 1",
+    "Query": "select x.table_name from (select a.* from information_schema.key_column_usage as a) as x",
+    "Table": "information_schema.key_column_usage"
+  }
+}
+Gen4 plan same as above
+
+# expand star with information schema in a derived table
+"select x.table_name from (select a.* from information_schema.key_column_usage a) x join user on x.id = user.id"
+{
+  "QueryType": "SELECT",
+  "Original": "select x.table_name from (select a.* from information_schema.key_column_usage a) x join user on x.id = user.id",
+  "Instructions": {
+    "OperatorType": "Join",
+    "Variant": "Join",
+    "JoinColumnIndexes": "-1",
+    "JoinVars": {
+      "x_id": 1
+    },
+    "TableName": "information_schema.key_column_usage_`user`",
+    "Inputs": [
+      {
+        "OperatorType": "Route",
+        "Variant": "SelectDBA",
+        "Keyspace": {
+          "Name": "main",
+          "Sharded": false
+        },
+        "FieldQuery": "select x.table_name, x.id from (select a.* from information_schema.key_column_usage as a where 1 != 1) as x where 1 != 1",
+        "Query": "select x.table_name, x.id from (select a.* from information_schema.key_column_usage as a) as x",
+        "Table": "information_schema.key_column_usage"
+      },
+      {
+        "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 = :x_id",
+        "Table": "`user`",
+        "Values": [
+          ":x_id"
+        ],
+        "Vindex": "user_index"
+      }
+    ]
+  }
+}
+{
+  "QueryType": "SELECT",
+  "Original": "select x.table_name from (select a.* from information_schema.key_column_usage a) x join user on x.id = user.id",
+  "Instructions": {
+    "OperatorType": "Join",
+    "Variant": "Join",
+    "JoinColumnIndexes": "-2",
+    "JoinVars": {
+      "x_id": 0
+    },
+    "TableName": "information_schema.key_column_usage_`user`",
+    "Inputs": [
+      {
+        "OperatorType": "Route",
+        "Variant": "SelectDBA",
+        "Keyspace": {
+          "Name": "main",
+          "Sharded": false
+        },
+        "FieldQuery": "select x.id, x.table_name from (select a.* from information_schema.key_column_usage as a where 1 != 1) as x where 1 != 1",
+        "Query": "select x.id, x.table_name from (select a.* from information_schema.key_column_usage as a) as x",
+        "Table": "information_schema.key_column_usage"
+      },
+      {
+        "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 = :x_id",
+        "Table": "`user`",
+        "Values": [
+          ":x_id"
+        ],
+        "Vindex": "user_index"
+      }
+    ]
+  }
+}
+
+# join of information_schema queries with select stars exprs
+"select a.*, b.* from information_schema.a a, information_schema.b b"
+{
+  "QueryType": "SELECT",
+  "Original": "select a.*, b.* from information_schema.a a, information_schema.b b",
+  "Instructions": {
+    "OperatorType": "Route",
+    "Variant": "SelectDBA",
+    "Keyspace": {
+      "Name": "main",
+      "Sharded": false
+    },
+    "FieldQuery": "select a.*, b.* from information_schema.a as a, information_schema.b as b where 1 != 1",
+    "Query": "select a.*, b.* from information_schema.a as a, information_schema.b as b",
+    "Table": "information_schema.a, information_schema.b"
+  }
+}
+Gen4 plan same as above
diff --git a/go/vt/vtgate/planbuilder/testdata/tpch_cases.txt b/go/vt/vtgate/planbuilder/testdata/tpch_cases.txt
index a4d14fe5a0..2c7629cc2a 100644
--- a/go/vt/vtgate/planbuilder/testdata/tpch_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/tpch_cases.txt
@@ -111,170 +111,11 @@ Gen4 error: unsupported: cross-shard correlated subquery
 
 # TPC-H query 4
 "select o_orderpriority, count(*) as order_count from orders where o_orderdate >= date('1993-07-01') and o_orderdate < date('1993-07-01') + interval '3' month and exists ( select * from lineitem where l_orderkey = o_orderkey and l_commitdate < l_receiptdate ) group by o_orderpriority order by o_orderpriority"
-"unsupported: cross-shard query with aggregates"
-"gen4 does not yet support: *sqlparser.StarExpr in select list"
+"symbol o_orderkey not found in table or subquery"
 
 # TPC-H query 5
 "select n_name, sum(l_extendedprice * (1 - l_discount)) as revenue from customer, orders, lineitem, supplier, nation, region where c_custkey = o_custkey and l_orderkey = o_orderkey and l_suppkey = s_suppkey and c_nationkey = s_nationkey and s_nationkey = n_nationkey and n_regionkey = r_regionkey and r_name = 'ASIA' and o_orderdate >= date('1994-01-01') and o_orderdate < date('1994-01-01') + interval '1' year group by n_name order by revenue desc"
 "unsupported: cross-shard query with aggregates"
-# Gen4 output was commented out, using two joinVars introduces flakiness
-# {
-#   "QueryType": "SELECT",
-#   "Original": "select n_name, sum(l_extendedprice * (1 - l_discount)) as revenue from customer, orders, lineitem, supplier, nation, region where c_custkey = o_custkey and l_orderkey = o_orderkey and l_suppkey = s_suppkey and c_nationkey = s_nationkey and s_nationkey = n_nationkey and n_regionkey = r_regionkey and r_name = 'ASIA' and o_orderdate \u003e= date('1994-01-01') and o_orderdate \u003c date('1994-01-01') + interval '1' year group by n_name order by revenue desc",
-#   "Instructions": {
-#     "OperatorType": "Sort",
-#     "Variant": "Memory",
-#     "OrderBy": "1 DESC",
-#     "ResultColumns": 2,
-#     "Inputs": [
-#       {
-#         "OperatorType": "Aggregate",
-#         "Variant": "Ordered",
-#         "Aggregates": "sum(1) AS revenue",
-#         "GroupBy": "(0|2)",
-#         "Inputs": [
-#           {
-#             "OperatorType": "Join",
-#             "Variant": "Join",
-#             "JoinColumnIndexes": "-2,1,-3",
-#             "JoinVars": {
-#               "n_nationkey": 0
-#             },
-#             "TableName": "nation_region_orders_customer_lineitem_supplier",
-#             "Inputs": [
-#               {
-#                 "OperatorType": "Join",
-#                 "Variant": "Join",
-#                 "JoinColumnIndexes": "-2,-3,-4",
-#                 "JoinVars": {
-#                   "n_nationkey": 0,
-#                   "n_regionkey": 0
-#                 },
-#                 "TableName": "nation_region",
-#                 "Inputs": [
-#                   {
-#                     "OperatorType": "Route",
-#                     "Variant": "SelectScatter",
-#                     "Keyspace": {
-#                       "Name": "main",
-#                       "Sharded": true
-#                     },
-#                     "FieldQuery": "select n_regionkey, n_nationkey, n_name, weight_string(n_name) from nation where 1 != 1",
-#                     "OrderBy": "(2|3) ASC",
-#                     "Query": "select n_regionkey, n_nationkey, n_name, weight_string(n_name) from nation order by n_name asc",
-#                     "Table": "nation"
-#                   },
-#                   {
-#                     "OperatorType": "Route",
-#                     "Variant": "SelectEqualUnique",
-#                     "Keyspace": {
-#                       "Name": "main",
-#                       "Sharded": true
-#                     },
-#                     "FieldQuery": "select 1 from region where 1 != 1",
-#                     "Query": "select 1 from region where r_name = 'ASIA' and r_regionkey = :n_regionkey",
-#                     "Table": "region",
-#                     "Values": [
-#                       ":n_regionkey"
-#                     ],
-#                     "Vindex": "hash"
-#                   }
-#                 ]
-#               },
-#               {
-#                 "OperatorType": "Join",
-#                 "Variant": "Join",
-#                 "JoinColumnIndexes": "1",
-#                 "JoinVars": {
-#                   "c_nationkey": 1,
-#                   "o_orderkey": 0
-#                 },
-#                 "TableName": "orders_customer_lineitem_supplier",
-#                 "Inputs": [
-#                   {
-#                     "OperatorType": "Join",
-#                     "Variant": "Join",
-#                     "JoinVars": {
-#                       "o_custkey": 0,
-#                       "o_orderkey": 0
-#                     },
-#                     "TableName": "orders_customer",
-#                     "Inputs": [
-#                       {
-#                         "OperatorType": "Route",
-#                         "Variant": "SelectScatter",
-#                         "Keyspace": {
-#                           "Name": "main",
-#                           "Sharded": true
-#                         },
-#                         "FieldQuery": "select o_custkey, o_orderkey from orders where 1 != 1",
-#                         "Query": "select o_custkey, o_orderkey from orders where o_orderdate \u003e= date('1994-01-01') and o_orderdate \u003c date('1994-01-01') + interval '1' year",
-#                         "Table": "orders"
-#                       },
-#                       {
-#                         "OperatorType": "Route",
-#                         "Variant": "SelectEqualUnique",
-#                         "Keyspace": {
-#                           "Name": "main",
-#                           "Sharded": true
-#                         },
-#                         "FieldQuery": "select c_nationkey from customer where 1 != 1",
-#                         "Query": "select c_nationkey from customer where c_custkey = :o_custkey",
-#                         "Table": "customer",
-#                         "Values": [
-#                           ":o_custkey"
-#                         ],
-#                         "Vindex": "hash"
-#                       }
-#                     ]
-#                   },
-#                   {
-#                     "OperatorType": "Join",
-#                     "Variant": "Join",
-#                     "JoinColumnIndexes": "-3",
-#                     "JoinVars": {
-#                       "l_orderkey": 0,
-#                       "l_suppkey": 0
-#                     },
-#                     "TableName": "lineitem_supplier",
-#                     "Inputs": [
-#                       {
-#                         "OperatorType": "Route",
-#                         "Variant": "SelectScatter",
-#                         "Keyspace": {
-#                           "Name": "main",
-#                           "Sharded": true
-#                         },
-#                         "FieldQuery": "select l_suppkey, l_orderkey, sum(l_extendedprice * (1 - l_discount)) as revenue from lineitem where 1 != 1",
-#                         "Query": "select l_suppkey, l_orderkey, sum(l_extendedprice * (1 - l_discount)) as revenue from lineitem",
-#                         "Table": "lineitem"
-#                       },
-#                       {
-#                         "OperatorType": "Route",
-#                         "Variant": "SelectEqualUnique",
-#                         "Keyspace": {
-#                           "Name": "main",
-#                           "Sharded": true
-#                         },
-#                         "FieldQuery": "select 1 from supplier where 1 != 1",
-#                         "Query": "select 1 from supplier where s_suppkey = :l_suppkey and :l_orderkey = :o_orderkey and s_nationkey = :c_nationkey and s_nationkey = :n_nationkey",
-#                         "Table": "supplier",
-#                         "Values": [
-#                           ":l_suppkey"
-#                         ],
-#                         "Vindex": "hash"
-#                       }
-#                     ]
-#                   }
-#                 ]
-#               }
-#             ]
-#           }
-#         ]
-#       }
-#     ]
-#   }
-# }
 
 # TPC-H query 6
 "select sum(l_extendedprice * l_discount) as revenue from lineitem where l_shipdate >= date('1994-01-01') and l_shipdate < date('1994-01-01') + interval '1' year and l_discount between 0.06 - 0.01 and 0.06 + 0.01 and l_quantity < 24"
@@ -657,12 +498,11 @@ Gen4 plan same as above
 # TPC-H query 16
 "select p_brand, p_type, p_size, count(distinct ps_suppkey) as supplier_cnt from partsupp, part where p_partkey = ps_partkey and p_brand <> 'Brand#45' and p_type not like 'MEDIUM POLISHED%' and p_size in (49, 14, 23, 45, 19, 3, 36, 9) and ps_suppkey not in ( select s_suppkey from supplier where s_comment like '%Customer%Complaints%' ) group by p_brand, p_type, p_size order by supplier_cnt desc, p_brand, p_type, p_size"
 "unsupported: cross-shard query with aggregates"
-"gen4 does not yet support: group by on: *planbuilder.pulloutSubquery"
 
 # TPC-H query 17
 "select sum(l_extendedprice) / 7.0 as avg_yearly from lineitem, part where p_partkey = l_partkey and p_brand = 'Brand#23' and p_container = 'MED BOX' and l_quantity < ( select 0.2 * avg(l_quantity) from lineitem where l_partkey = p_partkey )"
-"unsupported: in scatter query: complex aggregate expression"
-Gen4 plan same as above
+"symbol p_partkey not found in table or subquery"
+Gen4 error: unsupported: cross-shard correlated subquery
 
 # TPC-H query 18
 "select c_name, c_custkey, o_orderkey, o_orderdate, o_totalprice, sum(l_quantity) from customer, orders, lineitem where o_orderkey in ( select l_orderkey from lineitem group by l_orderkey having sum(l_quantity) > 300 ) and c_custkey = o_custkey and o_orderkey = l_orderkey group by c_name, c_custkey, o_orderkey, o_orderdate, o_totalprice order by o_totalprice desc, o_orderdate limit 100"
@@ -721,8 +561,8 @@ Gen4 plan same as above
 
 # TPC-H query 20
 "select s_name, s_address from supplier, nation where s_suppkey in ( select ps_suppkey from partsupp where ps_partkey in ( select p_partkey from part where p_name like 'forest%' ) and ps_availqty > ( select 0.5 * sum(l_quantity) from lineitem where l_partkey = ps_partkey and l_suppkey = ps_suppkey and l_shipdate >= date('1994-01-01') and l_shipdate < date('1994-01-01') + interval '1' year ) ) and s_nationkey = n_nationkey and n_name = 'CANADA' order by s_name"
-"unsupported: in scatter query: complex aggregate expression"
-Gen4 plan same as above
+"symbol ps_partkey not found in table or subquery"
+Gen4 error: unsupported: cross-shard correlated subquery
 
 # TPC-H query 21
 "select s_name, count(*) as numwait from supplier, lineitem l1, orders, nation where s_suppkey = l1.l_suppkey and o_orderkey = l1.l_orderkey and o_orderstatus = 'F' and l1.l_receiptdate > l1.l_commitdate and exists ( select * from lineitem l2 where l2.l_orderkey = l1.l_orderkey and l2.l_suppkey <> l1.l_suppkey ) and not exists ( select * from lineitem l3 where l3.l_orderkey = l1.l_orderkey and l3.l_suppkey <> l1.l_suppkey and l3.l_receiptdate > l3.l_commitdate ) and s_nationkey = n_nationkey and n_name = 'SAUDI ARABIA' group by s_name order by numwait desc, s_name limit 100"
@@ -731,5 +571,5 @@ Gen4 plan same as above
 
 # TPC-H query 22
 "select cntrycode, count(*) as numcust, sum(c_acctbal) as totacctbal from ( select substring(c_phone from 1 for 2) as cntrycode, c_acctbal from customer where substring(c_phone from 1 for 2) in ('13', '31', '23', '29', '30', '18', '17') and c_acctbal > ( select avg(c_acctbal) from customer where c_acctbal > 0.00 and substring(c_phone from 1 for 2) in ('13', '31', '23', '29', '30', '18', '17') ) and not exists ( select * from orders where o_custkey = c_custkey ) ) as custsale group by cntrycode order by cntrycode"
-"unsupported: in scatter query: complex aggregate expression"
-"gen4 does not yet support: *sqlparser.StarExpr in select list"
+"symbol c_custkey not found in table or subquery"
+Gen4 error: unsupported: cross-shard correlated subquery
diff --git a/go/vt/vtgate/planbuilder/testdata/tpch_schema_test.json b/go/vt/vtgate/planbuilder/testdata/tpch_schema_test.json
index 6f8887d849..6934f03d25 100644
--- a/go/vt/vtgate/planbuilder/testdata/tpch_schema_test.json
+++ b/go/vt/vtgate/planbuilder/testdata/tpch_schema_test.json
@@ -49,7 +49,8 @@
             {
               "name": "n_comment"
             }
-          ]
+          ],
+          "column_list_authoritative": true
         },
         "region": {
           "column_vindexes": [
@@ -68,7 +69,8 @@
             {
               "name": "r_comment"
             }
-          ]
+          ],
+          "column_list_authoritative": true
         },
         "part": {
           "column_vindexes": [
@@ -105,7 +107,8 @@
             {
               "name": "p_comment"
             }
-          ]
+          ],
+          "column_list_authoritative": true
         },
         "supplier": {
           "column_vindexes": [
@@ -136,7 +139,8 @@
             {
               "name": "s_comment"
             }
-          ]
+          ],
+          "column_list_authoritative": true
         },
         "partsupp": {
           "column_vindexes": [
@@ -161,7 +165,8 @@
             {
               "name": "ps_comment"
             }
-          ]
+          ],
+          "column_list_authoritative": true
         },
         "partsupp_map": {
           "column_vindexes": [
@@ -203,7 +208,8 @@
             {
               "name": "c_comment"
             }
-          ]
+          ],
+          "column_list_authoritative": true
         },
         "orders": {
           "column_vindexes": [
@@ -240,7 +246,8 @@
             {
               "name": "o_comment"
             }
-          ]
+          ],
+          "column_list_authoritative": true
         },
         "lineitem": {
           "column_vindexes": [
@@ -298,7 +305,8 @@
             {
               "name": "l_comment"
             }
-          ]
+          ],
+          "column_list_authoritative": true
         },
         "lineitem_map": {
           "column_vindexes": [
@@ -306,7 +314,8 @@
               "column": "l_orderkey",
               "name": "md5"
             }
-          ]
+          ],
+          "column_list_authoritative": true
         },
         "revenue0": {
           "column_vindexes": [
@@ -322,7 +331,8 @@
             {
               "name": "total_revenue"
             }
-          ]
+          ],
+          "column_list_authoritative": true
         }
       }
     }
diff --git a/go/vt/vtgate/planbuilder/testdata/union_cases.txt b/go/vt/vtgate/planbuilder/testdata/union_cases.txt
index 5604fab343..af6aa38bad 100644
--- a/go/vt/vtgate/planbuilder/testdata/union_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/union_cases.txt
@@ -206,6 +206,7 @@ Gen4 plan same as above
     "Table": "`user`"
   }
 }
+Gen4 plan same as above
 
 # union operations in derived table, without star expression (FROM)¡
 "select col1,col2 from (select col1, col2 from user union all select col1, col2 from user_extra) as t"
diff --git a/go/vt/vtgate/planbuilder/testdata/unsupported_cases.txt b/go/vt/vtgate/planbuilder/testdata/unsupported_cases.txt
index 4e78335b18..65e39039e3 100644
--- a/go/vt/vtgate/planbuilder/testdata/unsupported_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/unsupported_cases.txt
@@ -79,10 +79,12 @@ Gen4 plan same as above
 # * expresson not allowed for cross-shard joins
 "select * from user join user_extra"
 "unsupported: '*' expression in cross-shard query"
+Gen4 plan same as above
 
 # Group by column number, used with non-aliased expression (duplicated code)
 "select * from user group by 1"
 "unsupported: '*' expression in cross-shard query"
+"cannot use column offsets in group statement when using `*`"
 
 # Filtering on scatter aggregates
 "select count(*) a from user having a >10"
@@ -404,6 +406,7 @@ Gen4 plan same as above
 # Multi shard query using into outfile s3
 "select * from user into outfile s3 'out_file_name'"
 "INTO is not supported on sharded keyspace"
+Gen4 plan same as above
 
 # create view with Cannot auto-resolve for cross-shard joins
 "create view user.view_a as select col from user join user_extra"
@@ -436,6 +439,7 @@ Gen4 plan same as above
 # create view with incompatible keyspaces
 "create view main.view_a as select * from user.user_extra"
 "Select query does not belong to the same keyspace as the view statement"
+Gen4 plan same as above
 
 # table_schema OR predicate
 # It is unsupported because we do not route queries to multiple keyspaces right now
@@ -548,3 +552,24 @@ Gen4 error: unsupported: filtering on results of aggregates
   }
 }
 Gen4 error: unsupported: filtering on results of aggregates
+
+# subquery of information_schema with itself and star expression in outer select
+"select a.*, u.id from information_schema.a a, user u where a.id in (select * from information_schema.b)"
+"unsupported: '*' expression in cross-shard query"
+Gen4 plan same as above
+
+# outer and inner subquery route reference the same "uu.id" name
+# but they refer to different things. The first reference is to the outermost query,
+# and the second reference is to the innermost 'from' subquery.
+# This query will never work as the inner derived table is only selecting one of the column
+"select id2 from user uu where id in (select id from user where id = uu.id and user.col in (select col from (select id from user_extra where user_id = 5) uu where uu.user_id = uu.id))"
+"unsupported: cross-shard correlated subquery"
+Gen4 error: unsupported: unable to split predicates to derived table: uu.user_id = uu.id
+
+# outer and inner subquery route reference the same "uu.id" name
+# but they refer to different things. The first reference is to the outermost query,
+# and the second reference is to the innermost 'from' subquery.
+# changed to project all the columns from the derived tables.
+"select id2 from user uu where id in (select id from user where id = uu.id and user.col in (select col from (select col, id, user_id from user_extra where user_id = 5) uu where uu.user_id = uu.id))"
+"unsupported: cross-shard correlated subquery"
+Gen4 plan same as above
diff --git a/go/vt/vtgate/semantics/analyzer_test.go b/go/vt/vtgate/semantics/analyzer_test.go
index 4fc3ec945c..700189db0e 100644
--- a/go/vt/vtgate/semantics/analyzer_test.go
+++ b/go/vt/vtgate/semantics/analyzer_test.go
@@ -1,5 +1,5 @@
 /*
-Copyright 2020 The Vitess Authors.
+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.
@@ -19,15 +19,12 @@ package semantics
 import (
 	"testing"
 
-	querypb "vitess.io/vitess/go/vt/proto/query"
-
-	"vitess.io/vitess/go/vt/vtgate/vindexes"
-
 	"github.com/stretchr/testify/assert"
-
 	"github.com/stretchr/testify/require"
 
+	querypb "vitess.io/vitess/go/vt/proto/query"
 	"vitess.io/vitess/go/vt/sqlparser"
+	"vitess.io/vitess/go/vt/vtgate/vindexes"
 )
 
 const T0 TableSet = 0
@@ -37,7 +34,7 @@ const (
 	T1 TableSet = 1 << iota
 	T2
 	T3
-	_ // T4 is not used in the tests
+	T4
 	T5
 )
 
@@ -84,7 +81,7 @@ from x as t`,
 			// extract the first expression from the subquery (which should be the second expression in the outer query)
 			sel2 := sel.SelectExprs[1].(*sqlparser.AliasedExpr).Expr.(*sqlparser.Subquery).Select.(*sqlparser.Select)
 			exp := extract(sel2, 0)
-			s1 := semTable.BaseTableDependencies(exp)
+			s1 := semTable.RecursiveDeps(exp)
 			require.NoError(t, semTable.ProjectionErr)
 			// if scoping works as expected, we should be able to see the inner table being used by the inner expression
 			assert.Equal(t, tc.deps, s1)
@@ -109,8 +106,8 @@ func TestBindingSingleTablePositive(t *testing.T) {
 			ts := semTable.TableSetFor(t1)
 			assert.EqualValues(t, 1, ts)
 
-			assert.Equal(t, T1, semTable.BaseTableDependencies(extract(sel, 0)), query)
-			assert.Equal(t, T1, semTable.Dependencies(extract(sel, 0)), query)
+			assert.Equal(t, T1, semTable.RecursiveDeps(extract(sel, 0)), query)
+			assert.Equal(t, T1, semTable.DirectDeps(extract(sel, 0)), query)
 		})
 	}
 }
@@ -122,6 +119,7 @@ func TestBindingSingleTableNegative(t *testing.T) {
 		"select ks.tabl.col from d.tabl",
 		"select d.tabl.col from ks.tabl",
 		"select foo.col from d.tabl",
+		"select tabl.col from d.tabl as t",
 	}
 	for _, query := range queries {
 		t.Run(query, func(t *testing.T) {
@@ -133,62 +131,55 @@ func TestBindingSingleTableNegative(t *testing.T) {
 	}
 }
 
-func TestOrderByBindingSingleTable(t *testing.T) {
-	t.Run("positive tests", func(t *testing.T) {
-		tcases := []struct {
-			sql  string
-			deps TableSet
-		}{{
-			"select col from tabl order by col",
-			T1,
-		}, {
-			"select col from tabl order by tabl.col",
-			T1,
-		}, {
-
-			"select col from tabl order by d.tabl.col",
-			T1,
-		}, {
-			"select col from tabl order by 1",
-			T1,
-		}, {
-			"select col as c from tabl order by c",
-			T1,
-		}, {
-			"select 1 as c from tabl order by c",
-			T0,
-		}}
-		for _, tc := range tcases {
-			t.Run(tc.sql, func(t *testing.T) {
-				stmt, semTable := parseAndAnalyze(t, tc.sql, "d")
-				sel, _ := stmt.(*sqlparser.Select)
-				order := sel.OrderBy[0].Expr
-				d := semTable.BaseTableDependencies(order)
-				require.Equal(t, tc.deps, d, tc.sql)
-			})
-		}
-	})
-}
+func TestOrderByBindingTable(t *testing.T) {
+	tcases := []struct {
+		sql  string
+		deps TableSet
+	}{{
+		"select col from tabl order by col",
+		T1,
+	}, {
+		"select col from tabl order by tabl.col",
+		T1,
+	}, {
+		"select col from tabl order by d.tabl.col",
+		T1,
+	}, {
+		"select col from tabl order by 1",
+		T1,
+	}, {
+		"select col as c from tabl order by c",
+		T1,
+	}, {
+		"select 1 as c from tabl order by c",
+		T0,
+	}, {
+		"select name, name from t1, t2 order by name",
+		T2,
+	}, {
+		"(select id from t1) union (select uid from t2) order by id",
+		T1 | T2,
+	}, {
+		"select id from t1 union (select uid from t2) order by 1",
+		T1 | T2,
+	}}
+	for _, tc := range tcases {
+		t.Run(tc.sql, func(t *testing.T) {
+			stmt, semTable := parseAndAnalyze(t, tc.sql, "d")
 
-func TestOrderByBindingMultiTable(t *testing.T) {
-	t.Run("positive tests", func(t *testing.T) {
-		tcases := []struct {
-			sql  string
-			deps TableSet
-		}{{
-			"select name, name from t1, t2 order by name",
-			T2,
-		}}
-		for _, tc := range tcases {
-			t.Run(tc.sql, func(t *testing.T) {
-				stmt, semTable := parseAndAnalyze(t, tc.sql, "d")
-				sel, _ := stmt.(*sqlparser.Select)
-				order := sel.OrderBy[0].Expr
-				d := semTable.BaseTableDependencies(order)
-				require.Equal(t, tc.deps, d, tc.sql)
-			})
-		}
-	})
+			var order sqlparser.Expr
+			switch stmt := stmt.(type) {
+			case *sqlparser.Select:
+				order = stmt.OrderBy[0].Expr
+			case *sqlparser.Union:
+				order = stmt.OrderBy[0].Expr
+			default:
+				t.Fail()
+			}
+			d := semTable.RecursiveDeps(order)
+			require.Equal(t, tc.deps, d, tc.sql)
+		})
+	}
 }
 
 func TestGroupByBinding(t *testing.T) {
@@ -223,15 +214,15 @@ func TestGroupByBinding(t *testing.T) {
 		"select t1.id from t1, t2 group by id",
 		T1,
 	}, {
-		"select t.id from t, t1 group by id",
-		T1,
+		"select id from t, t1 group by id",
+		T2,
 	}}
 	for _, tc := range tcases {
 		t.Run(tc.sql, func(t *testing.T) {
 			stmt, semTable := parseAndAnalyze(t, tc.sql, "d")
 			sel, _ := stmt.(*sqlparser.Select)
 			grp := sel.GroupBy[0]
-			d := semTable.BaseTableDependencies(grp)
+			d := semTable.RecursiveDeps(grp)
 			require.Equal(t, tc.deps, d, tc.sql)
 		})
 	}
@@ -274,13 +265,16 @@ func TestHavingBinding(t *testing.T) {
 	}, {
 		"select t.id, count(*) as a from t, t1 group by t.id having a = 1",
 		T1 | T2,
+	}, {
+		sql:  "select u2.a, u1.a from u1, u2 having u2.a = 2",
+		deps: T2,
 	}}
 	for _, tc := range tcases {
 		t.Run(tc.sql, func(t *testing.T) {
 			stmt, semTable := parseAndAnalyze(t, tc.sql, "d")
 			sel, _ := stmt.(*sqlparser.Select)
 			hvng := sel.Having.Expr
-			d := semTable.BaseTableDependencies(hvng)
+			d := semTable.RecursiveDeps(hvng)
 			require.Equal(t, tc.deps, d, tc.sql)
 		})
 	}
@@ -302,7 +296,7 @@ func TestBindingSingleAliasedTable(t *testing.T) {
 				ts := semTable.TableSetFor(t1)
 				assert.EqualValues(t, 1, ts)
 
-				d := semTable.BaseTableDependencies(extract(sel, 0))
+				d := semTable.RecursiveDeps(extract(sel, 0))
 				require.Equal(t, T1, d, query)
 			})
 		}
@@ -345,8 +339,8 @@ func TestUnion(t *testing.T) {
 	assert.EqualValues(t, 1, ts1)
 	assert.EqualValues(t, 2, ts2)
 
-	d1 := semTable.BaseTableDependencies(extract(sel1, 0))
-	d2 := semTable.BaseTableDependencies(extract(sel2, 0))
+	d1 := semTable.RecursiveDeps(extract(sel1, 0))
+	d2 := semTable.RecursiveDeps(extract(sel2, 0))
 	assert.Equal(t, T1, d1)
 	assert.Equal(t, T2, d2)
 }
@@ -392,6 +386,37 @@ func fakeSchemaInfo() *FakeSI {
 	return si
 }
 
+func TestSubqueryBinding(t *testing.T) {
+	queries := []struct {
+		query    string
+		expected TableSet
+	}{{
+		query:    "select * from user u where exists (select * from user order by col)",
+		expected: T2,
+	}, {
+		query:    "select * from user u where exists (select * from user order by user.col)",
+		expected: T2,
+	}, {
+		query:    "select * from user u where exists (select * from user order by u.col)",
+		expected: T1,
+	}}
+
+	for _, tc := range queries {
+		t.Run(tc.query, func(t *testing.T) {
+			ast, err := sqlparser.Parse(tc.query)
+			require.NoError(t, err)
+
+			sel := ast.(*sqlparser.Select)
+			st, err := Analyze(sel, "dbName", fakeSchemaInfo())
+			require.NoError(t, err)
+			exists := sel.Where.Expr.(*sqlparser.ExistsExpr)
+			expr := exists.Subquery.Select.(*sqlparser.Select).OrderBy[0].Expr
+			require.Equal(t, tc.expected, st.DirectDeps(expr))
+			require.Equal(t, tc.expected, st.RecursiveDeps(expr))
+		})
+	}
+}
+
 func TestUnionWithOrderBy(t *testing.T) {
 	query := "select col1 from tabl1 union (select col2 from tabl2) order by 1"
 
@@ -407,89 +432,85 @@ func TestUnionWithOrderBy(t *testing.T) {
 	assert.EqualValues(t, 1, ts1)
 	assert.EqualValues(t, 2, ts2)
 
-	d1 := semTable.BaseTableDependencies(extract(sel1, 0))
-	d2 := semTable.BaseTableDependencies(extract(sel2, 0))
+	d1 := semTable.RecursiveDeps(extract(sel1, 0))
+	d2 := semTable.RecursiveDeps(extract(sel2, 0))
 	assert.Equal(t, T1, d1)
 	assert.Equal(t, T2, d2)
 }
 
-func TestBindingMultiTable(t *testing.T) {
-	t.Run("positive tests", func(t *testing.T) {
-
-		type testCase struct {
-			query string
-			deps  TableSet
-		}
-		queries := []testCase{{
-			query: "select t.col from t, s",
-			deps:  T1,
-		}, {
-			query: "select s.col from t join s",
-			deps:  T2,
-		}, {
-			query: "select max(t.col+s.col) from t, s",
-			deps:  T1 | T2,
-		}, {
-			query: "select max(t.col+s.col) from t join s",
-			deps:  T1 | T2,
-		}, {
-			query: "select case t.col when s.col then r.col else u.col end from t, s, r, w, u",
-			deps:  T1 | T2 | T3 | T5,
-			// }, {
-			//	// make sure that we don't let sub-query Dependencies leak out by mistake
-			//	query: "select t.col + (select 42 from s) from t",
-			//	deps:  T1,
-			// }, {
-			//	query: "select (select 42 from s where r.id = s.id) from r",
-			//	deps:  T1 | T2,
-		}, {
-			query: "select X.col from t as X, s as S",
-			deps:  T1,
-		}, {
-			query: "select X.col+S.col from t as X, s as S",
-			deps:  T1 | T2,
-		}, {
-			query: "select max(X.col+S.col) from t as X, s as S",
-			deps:  T1 | T2,
-		}, {
-			query: "select max(X.col+s.col) from t as X, s",
-			deps:  T1 | T2,
-		}, {
-			query: "select b.t.col from b.t, t",
-			deps:  T1,
-		}, {
-			query: "select u1.a + u2.a from u1, u2",
-			deps:  T1 | T2,
-		}}
-		for _, query := range queries {
-			t.Run(query.query, func(t *testing.T) {
-				stmt, semTable := parseAndAnalyze(t, query.query, "user")
-				sel, _ := stmt.(*sqlparser.Select)
-				assert.Equal(t, query.deps, semTable.BaseTableDependencies(extract(sel, 0)), query.query)
-			})
-		}
-	})
+func TestBindingMultiTablePositive(t *testing.T) {
+	type testCase struct {
+		query string
+		deps  TableSet
+	}
+	queries := []testCase{{
+		query: "select t.col from t, s",
+		deps:  T1,
+	}, {
+		query: "select s.col from t join s",
+		deps:  T2,
+	}, {
+		query: "select max(t.col+s.col) from t, s",
+		deps:  T1 | T2,
+	}, {
+		query: "select max(t.col+s.col) from t join s",
+		deps:  T1 | T2,
+	}, {
+		query: "select case t.col when s.col then r.col else u.col end from t, s, r, w, u",
+		deps:  T1 | T2 | T3 | T5,
+		// }, {
+		//	// make sure that we don't let sub-query Dependencies leak out by mistake
+		//	query: "select t.col + (select 42 from s) from t",
+		//	dependencies:  T1,
+		// }, {
+		//	query: "select (select 42 from s where r.id = s.id) from r",
+		//	dependencies:  T1 | T2,
+	}, {
+		query: "select X.col from t as X, s as S",
+		deps:  T1,
+	}, {
+		query: "select X.col+S.col from t as X, s as S",
+		deps:  T1 | T2,
+	}, {
+		query: "select max(X.col+S.col) from t as X, s as S",
+		deps:  T1 | T2,
+	}, {
+		query: "select max(X.col+s.col) from t as X, s",
+		deps:  T1 | T2,
+	}, {
+		query: "select u1.a + u2.a from u1, u2",
+		deps:  T1 | T2,
+	}}
+	for _, query := range queries {
+		t.Run(query.query, func(t *testing.T) {
+			stmt, semTable := parseAndAnalyze(t, query.query, "user")
+			sel, _ := stmt.(*sqlparser.Select)
+			assert.Equal(t, query.deps, semTable.RecursiveDeps(extract(sel, 0)), query.query)
+		})
+	}
+}
 
-	t.Run("negative tests", func(t *testing.T) {
-		queries := []string{
-			"select 1 from d.tabl, d.tabl",
-			"select 1 from d.tabl, tabl",
-			"select 1 from user join user_extra user",
-		}
-		for _, query := range queries {
-			t.Run(query, func(t *testing.T) {
-				parse, err := sqlparser.Parse(query)
-				require.NoError(t, err)
-				_, err = Analyze(parse.(sqlparser.SelectStatement), "d", &FakeSI{
-					Tables: map[string]*vindexes.Table{
-						"tabl": {Name: sqlparser.NewTableIdent("tabl")},
-						"foo":  {Name: sqlparser.NewTableIdent("foo")},
-					},
-				})
-				require.Error(t, err)
+func TestBindingMultiTableNegative(t *testing.T) {
+	queries := []string{
+		"select 1 from d.tabl, d.tabl",
+		"select 1 from d.tabl, tabl",
+		"select 1 from user join user_extra user",
+		"select t.col from k.t, t",
+		"select b.t.col from b.t, t",
+	}
+	for _, query := range queries {
+		t.Run(query, func(t *testing.T) {
+			parse, err := sqlparser.Parse(query)
+			require.NoError(t, err)
+			_, err = Analyze(parse.(sqlparser.SelectStatement), "d", &FakeSI{
+				Tables: map[string]*vindexes.Table{
+					"tabl": {Name: sqlparser.NewTableIdent("tabl")},
+					"foo":  {Name: sqlparser.NewTableIdent("foo")},
+				},
 			})
-		}
-	})
+			require.Error(t, err)
+		})
+	}
 }
 
 func TestBindingSingleDepPerTable(t *testing.T) {
@@ -497,7 +518,7 @@ func TestBindingSingleDepPerTable(t *testing.T) {
 	stmt, semTable := parseAndAnalyze(t, query, "")
 	sel, _ := stmt.(*sqlparser.Select)
 
-	d := semTable.BaseTableDependencies(extract(sel, 0))
+	d := semTable.RecursiveDeps(extract(sel, 0))
 	assert.Equal(t, 1, d.NumberOfTables(), "size wrong")
 	assert.Equal(t, T1, d)
 }
@@ -536,12 +557,14 @@ func TestMissingTable(t *testing.T) {
 }
 
 func TestUnknownColumnMap2(t *testing.T) {
-	query := "select col from a, b"
+	varchar := querypb.Type_VARCHAR
+	int := querypb.Type_INT32
+
 	authoritativeTblA := vindexes.Table{
 		Name: sqlparser.NewTableIdent("a"),
 		Columns: []vindexes.Column{{
 			Name: sqlparser.NewColIdent("col2"),
-			Type: querypb.Type_VARCHAR,
+			Type: varchar,
 		}},
 		ColumnListAuthoritative: true,
 	}
@@ -549,7 +572,7 @@ func TestUnknownColumnMap2(t *testing.T) {
 		Name: sqlparser.NewTableIdent("b"),
 		Columns: []vindexes.Column{{
 			Name: sqlparser.NewColIdent("col"),
-			Type: querypb.Type_VARCHAR,
+			Type: varchar,
 		}},
 		ColumnListAuthoritative: true,
 	}
@@ -561,7 +584,7 @@ func TestUnknownColumnMap2(t *testing.T) {
 		Name: sqlparser.NewTableIdent("a"),
 		Columns: []vindexes.Column{{
 			Name: sqlparser.NewColIdent("col"),
-			Type: querypb.Type_INT32,
+			Type: int,
 		}},
 		ColumnListAuthoritative: true,
 	}
@@ -569,71 +592,61 @@ func TestUnknownColumnMap2(t *testing.T) {
 		Name: sqlparser.NewTableIdent("b"),
 		Columns: []vindexes.Column{{
 			Name: sqlparser.NewColIdent("col"),
-			Type: querypb.Type_INT32,
+			Type: int,
 		}},
 		ColumnListAuthoritative: true,
 	}
 
-	varchar := querypb.Type_VARCHAR
-	int := querypb.Type_INT32
-
-	parse, _ := sqlparser.Parse(query)
-	expr := extract(parse.(*sqlparser.Select), 0)
 	tests := []struct {
 		name   string
 		schema map[string]*vindexes.Table
 		err    bool
 		typ    *querypb.Type
-	}{
-		{
-			name:   "no info about tables",
-			schema: map[string]*vindexes.Table{"a": {}, "b": {}},
-			err:    true,
-		},
-		{
-			name:   "non authoritative columns",
-			schema: map[string]*vindexes.Table{"a": &nonAuthoritativeTblA, "b": &nonAuthoritativeTblA},
-			err:    true,
-		},
-		{
-			name:   "non authoritative columns - one authoritative and one not",
-			schema: map[string]*vindexes.Table{"a": &nonAuthoritativeTblA, "b": &authoritativeTblB},
-			err:    false,
-			typ:    &varchar,
-		},
-		{
-			name:   "non authoritative columns - one authoritative and one not",
-			schema: map[string]*vindexes.Table{"a": &authoritativeTblA, "b": &nonAuthoritativeTblB},
-			err:    false,
-			typ:    &varchar,
-		},
-		{
-			name:   "authoritative columns",
-			schema: map[string]*vindexes.Table{"a": &authoritativeTblA, "b": &authoritativeTblB},
-			err:    false,
-			typ:    &varchar,
-		},
-		{
-			name:   "authoritative columns",
-			schema: map[string]*vindexes.Table{"a": &authoritativeTblA, "b": &authoritativeTblBWithInt},
-			err:    false,
-			typ:    &int,
-		},
-		{
-			name:   "authoritative columns with overlap",
-			schema: map[string]*vindexes.Table{"a": &authoritativeTblAWithConflict, "b": &authoritativeTblB},
-			err:    true,
-		},
-	}
+	}{{
+		name:   "no info about tables",
+		schema: map[string]*vindexes.Table{"a": {}, "b": {}},
+		err:    true,
+	}, {
+		name:   "non authoritative columns",
+		schema: map[string]*vindexes.Table{"a": &nonAuthoritativeTblA, "b": &nonAuthoritativeTblA},
+		err:    true,
+	}, {
+		name:   "non authoritative columns - one authoritative and one not",
+		schema: map[string]*vindexes.Table{"a": &nonAuthoritativeTblA, "b": &authoritativeTblB},
+		err:    false,
+		typ:    &varchar,
+	}, {
+		name:   "non authoritative columns - one authoritative and one not",
+		schema: map[string]*vindexes.Table{"a": &authoritativeTblA, "b": &nonAuthoritativeTblB},
+		err:    false,
+		typ:    &varchar,
+	}, {
+		name:   "authoritative columns",
+		schema: map[string]*vindexes.Table{"a": &authoritativeTblA, "b": &authoritativeTblB},
+		err:    false,
+		typ:    &varchar,
+	}, {
+		name:   "authoritative columns",
+		schema: map[string]*vindexes.Table{"a": &authoritativeTblA, "b": &authoritativeTblBWithInt},
+		err:    false,
+		typ:    &int,
+	}, {
+		name:   "authoritative columns with overlap",
+		schema: map[string]*vindexes.Table{"a": &authoritativeTblAWithConflict, "b": &authoritativeTblB},
+		err:    true,
+	}}
+	query := "select col from a, b"
+	parse, _ := sqlparser.Parse(query)
+	expr := extract(parse.(*sqlparser.Select), 0)
+
 	for _, test := range tests {
 		t.Run(test.name, func(t *testing.T) {
 			si := &FakeSI{Tables: test.schema}
 			tbl, err := Analyze(parse.(sqlparser.SelectStatement), "", si)
-			require.NoError(t, err)
-
 			if test.err {
-				require.Error(t, tbl.ProjectionErr)
+				require.True(t, err != nil || tbl.ProjectionErr != nil)
 			} else {
+				require.NoError(t, err)
 				require.NoError(t, tbl.ProjectionErr)
 				typ := tbl.TypeFor(expr)
 				assert.Equal(t, test.typ, typ)
@@ -713,7 +726,7 @@ func TestScopingWDerivedTables(t *testing.T) {
 		expectation          TableSet
 	}{
 		{
-			query:                "select id from (select id from user where id = 5) as t",
+			query:                "select id from (select x as id from user) as t",
 			recursiveExpectation: T1,
 			expectation:          T2,
 		}, {
@@ -749,6 +762,72 @@ func TestScopingWDerivedTables(t *testing.T) {
 			query:                "select t.baz = 1 from (select id as baz from user) as t",
 			expectation:          T2,
 			recursiveExpectation: T1,
+		}, {
+			query:                "select t.id from (select * from user, music) as t",
+			expectation:          T3,
+			recursiveExpectation: T1 | T2,
+		}, {
+			query:                "select t.id from (select * from user, music) as t order by t.id",
+			expectation:          T3,
+			recursiveExpectation: T1 | T2,
+		}, {
+			query:                "select t.id from (select * from user) as t join user as u on t.id = u.id",
+			expectation:          T2,
+			recursiveExpectation: T1,
+		}, {
+			query:                "select t.col1 from t3 ua join (select t1.id, t1.col1 from t1 join t2) as t",
+			expectation:          T4,
+			recursiveExpectation: T2,
+		}, {
+			query:        "select uu.test from (select id from t1) uu",
+			errorMessage: "symbol uu.test not found",
+		}, {
+			query:        "select uu.id from (select id as col from t1) uu",
+			errorMessage: "symbol uu.id not found",
+		}, {
+			query:        "select uu.id from (select id as col from t1) uu",
+			errorMessage: "symbol uu.id not found",
+		}, {
+			query:                "select uu.id from (select id from t1) as uu where exists (select * from t2 as uu where uu.id = uu.uid)",
+			expectation:          T2,
+			recursiveExpectation: T1,
+		}, {
+			query:                "select 1 from user uu where exists (select 1 from user where exists (select 1 from (select 1 from t1) uu where uu.user_id = uu.id))",
+			expectation:          T0,
+			recursiveExpectation: T0,
+		}}
+	for _, query := range queries {
+		t.Run(query.query, func(t *testing.T) {
+			parse, err := sqlparser.Parse(query.query)
+			require.NoError(t, err)
+			st, err := Analyze(parse.(sqlparser.SelectStatement), "user", &FakeSI{
+				Tables: map[string]*vindexes.Table{
+					"t": {Name: sqlparser.NewTableIdent("t")},
+				},
+			})
+			if query.errorMessage != "" {
+				require.EqualError(t, err, query.errorMessage)
+			} else {
+				require.NoError(t, err)
+				sel := parse.(*sqlparser.Select)
+				assert.Equal(t, query.recursiveExpectation, st.RecursiveDeps(extract(sel, 0)), "RecursiveDeps")
+				assert.Equal(t, query.expectation, st.DirectDeps(extract(sel, 0)), "DirectDeps")
+			}
+		})
+	}
+}
+
+func TestScopingWComplexDerivedTables(t *testing.T) {
+	queries := []struct {
+		query            string
+		errorMessage     string
+		rightExpectation TableSet
+		leftExpectation  TableSet
+	}{
+		{
+			query:            "select 1 from user uu where exists (select 1 from user where exists (select 1 from (select 1 from t1) uu where uu.user_id = uu.id))",
+			rightExpectation: T1,
+			leftExpectation:  T1,
 		},
 	}
 	for _, query := range queries {
@@ -765,8 +844,11 @@ func TestScopingWDerivedTables(t *testing.T) {
 			} else {
 				require.NoError(t, err)
 				sel := parse.(*sqlparser.Select)
-				assert.Equal(t, query.recursiveExpectation, st.BaseTableDependencies(extract(sel, 0)))
-				assert.Equal(t, query.expectation, st.Dependencies(extract(sel, 0)))
+				comparisonExpr := sel.Where.Expr.(*sqlparser.ExistsExpr).Subquery.Select.(*sqlparser.Select).Where.Expr.(*sqlparser.ExistsExpr).Subquery.Select.(*sqlparser.Select).Where.Expr.(*sqlparser.ComparisonExpr)
+				left := comparisonExpr.Left
+				right := comparisonExpr.Right
+				assert.Equal(t, query.leftExpectation, st.RecursiveDeps(left), "Left RecursiveDeps")
+				assert.Equal(t, query.rightExpectation, st.RecursiveDeps(right), "Right RecursiveDeps")
 			}
 		})
 	}
@@ -807,8 +889,8 @@ func TestScopingWVindexTables(t *testing.T) {
 			} else {
 				require.NoError(t, err)
 				sel := parse.(*sqlparser.Select)
-				assert.Equal(t, query.recursiveExpectation, st.BaseTableDependencies(extract(sel, 0)))
-				assert.Equal(t, query.expectation, st.Dependencies(extract(sel, 0)))
+				assert.Equal(t, query.recursiveExpectation, st.RecursiveDeps(extract(sel, 0)))
+				assert.Equal(t, query.expectation, st.DirectDeps(extract(sel, 0)))
 			}
 		})
 	}
diff --git a/go/vt/vtgate/semantics/early_rewriter_test.go b/go/vt/vtgate/semantics/early_rewriter_test.go
index 7865b49d4b..effa80e2b4 100644
--- a/go/vt/vtgate/semantics/early_rewriter_test.go
+++ b/go/vt/vtgate/semantics/early_rewriter_test.go
@@ -217,14 +217,14 @@ func TestSemTableDependenciesAfterExpandStar(t *testing.T) {
 			assert.Equal(t, tcase.expSQL, sqlparser.String(selectStatement))
 			if tcase.otherTbl != -1 {
 				assert.NotEqual(t,
-					semTable.BaseTableDependencies(selectStatement.SelectExprs[tcase.otherTbl].(*sqlparser.AliasedExpr).Expr),
-					semTable.BaseTableDependencies(selectStatement.SelectExprs[tcase.expandedCol].(*sqlparser.AliasedExpr).Expr),
+					semTable.RecursiveDeps(selectStatement.SelectExprs[tcase.otherTbl].(*sqlparser.AliasedExpr).Expr),
+					semTable.RecursiveDeps(selectStatement.SelectExprs[tcase.expandedCol].(*sqlparser.AliasedExpr).Expr),
 				)
 			}
 			if tcase.sameTbl != -1 {
 				assert.Equal(t,
-					semTable.BaseTableDependencies(selectStatement.SelectExprs[tcase.sameTbl].(*sqlparser.AliasedExpr).Expr),
-					semTable.BaseTableDependencies(selectStatement.SelectExprs[tcase.expandedCol].(*sqlparser.AliasedExpr).Expr),
+					semTable.RecursiveDeps(selectStatement.SelectExprs[tcase.sameTbl].(*sqlparser.AliasedExpr).Expr),
+					semTable.RecursiveDeps(selectStatement.SelectExprs[tcase.expandedCol].(*sqlparser.AliasedExpr).Expr),
 				)
 			}
 		})