Repository: vitessio/vitess
Pull request #8905 (2021-09-29 15:04:05)

gen4: implement a growable semantics.TableSet
## Description

This was requested by @systay on Slack. We need a `TableSet` data structure that can support more than 64 tables. We're doing this right here in the smallest possible space: `TableSet` is now 16 bytes large and packs a small, single-word bitmap that is used when the set contains less than 64 tables, and a pointer to an implementation of an arbitrarily large set.

This implementation is pretty straightforward -- I don't believe it can be optimized further like we'd do in C/C++/Rust. For completeness, these kind of implementations are usually done like this in non-GC'ed languages:

Instead of the 16-byte `struct` we have here with `struct TableSet{ small uint64; large *largeTableSet }`, we'd have a single-field struct with a single word in it: `struct TableSet { set uintptr }`. When trying to read or write to this set, we'd check `if ts.set & 0x1 != 0`; if this is true, then we have a 63 bit tableset by doing `ts.set >> 1`. If it's false, then we'd have a large tableset by doing `(*largeTableSet)(ts.set)`. This works in practice because memory allocators will never return pointers with a 1-off alignment (their minimal alignment is at the very least the system's word size, 4/8), so we can store a bitmap in the pointer as long as the last bit of the bitmap is always `1`. :ok_hand: 

...Of course this doesn't work in a garbage collected language like Go because if you leave a `*largeTableSet` pointed at by an `uintptr`, the GC won't find it and it'll be freed on a later GC pass. So we don't get to to pack pointers and we need to run with 16-byte `TableSet`s. 

Good enough!

cc @systay @frouioui  

## 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/vtgate/planbuilder/abstract/concatenate.go b/go/vt/vtgate/planbuilder/abstract/concatenate.go
index 3e9418bb16..a09a8370ab 100644
--- a/go/vt/vtgate/planbuilder/abstract/concatenate.go
+++ b/go/vt/vtgate/planbuilder/abstract/concatenate.go
@@ -38,7 +38,7 @@ var _ Operator = (*Concatenate)(nil)
 func (c *Concatenate) TableID() semantics.TableSet {
 	var tableSet semantics.TableSet
 	for _, source := range c.Sources {
-		tableSet |= source.TableID()
+		tableSet.MergeInPlace(source.TableID())
 	}
 	return tableSet
 }
diff --git a/go/vt/vtgate/planbuilder/abstract/querygraph.go b/go/vt/vtgate/planbuilder/abstract/querygraph.go
index 64487d63fb..770247c263 100644
--- a/go/vt/vtgate/planbuilder/abstract/querygraph.go
+++ b/go/vt/vtgate/planbuilder/abstract/querygraph.go
@@ -78,7 +78,7 @@ func (qg *QueryGraph) TableID() semantics.TableSet {
 func (qg *QueryGraph) GetPredicates(lhs, rhs semantics.TableSet) []sqlparser.Expr {
 	var allExprs []sqlparser.Expr
 	for tableSet, exprs := range qg.innerJoins {
-		if tableSet.IsSolvedBy(lhs|rhs) &&
+		if tableSet.IsSolvedBy(lhs.Merge(rhs)) &&
 			tableSet.IsOverlapping(rhs) &&
 			tableSet.IsOverlapping(lhs) {
 			allExprs = append(allExprs, exprs...)
diff --git a/go/vt/vtgate/planbuilder/concantenatetree.go b/go/vt/vtgate/planbuilder/concantenatetree.go
index 58f3f5706c..bc32ecd280 100644
--- a/go/vt/vtgate/planbuilder/concantenatetree.go
+++ b/go/vt/vtgate/planbuilder/concantenatetree.go
@@ -38,7 +38,7 @@ var _ queryTree = (*concatenateTree)(nil)
 func (c *concatenateTree) tableID() semantics.TableSet {
 	var tableSet semantics.TableSet
 	for _, source := range c.sources {
-		tableSet |= source.tableID()
+		tableSet.MergeInPlace(source.tableID())
 	}
 	return tableSet
 }
diff --git a/go/vt/vtgate/planbuilder/concatenateGen4.go b/go/vt/vtgate/planbuilder/concatenateGen4.go
index 50be9658c9..8a9e3300ba 100644
--- a/go/vt/vtgate/planbuilder/concatenateGen4.go
+++ b/go/vt/vtgate/planbuilder/concatenateGen4.go
@@ -100,7 +100,7 @@ func (c *concatenateGen4) Rewrite(inputs ...logicalPlan) error {
 func (c *concatenateGen4) ContainsTables() semantics.TableSet {
 	var tableSet semantics.TableSet
 	for _, source := range c.sources {
-		tableSet |= source.ContainsTables()
+		tableSet.MergeInPlace(source.ContainsTables())
 	}
 	return tableSet
 }
diff --git a/go/vt/vtgate/planbuilder/jointree.go b/go/vt/vtgate/planbuilder/jointree.go
index c687d89bbb..2c01263e7b 100644
--- a/go/vt/vtgate/planbuilder/jointree.go
+++ b/go/vt/vtgate/planbuilder/jointree.go
@@ -37,7 +37,7 @@ type joinTree struct {
 var _ queryTree = (*joinTree)(nil)
 
 func (jp *joinTree) tableID() semantics.TableSet {
-	return jp.lhs.tableID() | jp.rhs.tableID()
+	return jp.lhs.tableID().Merge(jp.rhs.tableID())
 }
 
 func (jp *joinTree) clone() queryTree {
diff --git a/go/vt/vtgate/planbuilder/querytree.go b/go/vt/vtgate/planbuilder/querytree.go
index bb6dfe5167..2d9e792fa4 100644
--- a/go/vt/vtgate/planbuilder/querytree.go
+++ b/go/vt/vtgate/planbuilder/querytree.go
@@ -129,9 +129,9 @@ func (p parenTables) tableNames() []string {
 }
 
 func (p parenTables) tableID() semantics.TableSet {
-	res := semantics.TableSet(0)
+	var res semantics.TableSet
 	for _, r := range p {
-		res = res.Merge(r.tableID())
+		res.MergeInPlace(r.tableID())
 	}
 	return res
 }
diff --git a/go/vt/vtgate/planbuilder/route_planning.go b/go/vt/vtgate/planbuilder/route_planning.go
index b9770a625a..f21422d8f2 100644
--- a/go/vt/vtgate/planbuilder/route_planning.go
+++ b/go/vt/vtgate/planbuilder/route_planning.go
@@ -273,7 +273,7 @@ func mergeSubQuery(ctx *planningContext, outer *routeTree, inner *routeTree, sub
 	err := sqlparser.Walk(func(node sqlparser.SQLNode) (kontinue bool, err error) {
 		switch n := node.(type) {
 		case *sqlparser.AliasedTableExpr:
-			outer.solved |= ctx.semTable.TableSetFor(n)
+			outer.solved.MergeInPlace(ctx.semTable.TableSetFor(n))
 		}
 		return true, nil
 	}, subq.SelectStatement)
@@ -508,7 +508,7 @@ func breakPredicateInLHSandRHS(
 		switch node := cursor.Node().(type) {
 		case *sqlparser.ColName:
 			deps := semTable.RecursiveDeps(node)
-			if deps == 0 {
+			if deps.NumberOfTables() == 0 {
 				err = vterrors.Errorf(vtrpcpb.Code_INTERNAL, "unknown column. has the AST been copied?")
 				return false
 			}
@@ -534,7 +534,7 @@ func mergeOrJoinInner(ctx *planningContext, lhs, rhs queryTree, joinPredicates [
 }
 
 func mergeOrJoin(ctx *planningContext, lhs, rhs queryTree, joinPredicates []sqlparser.Expr, inner bool) (queryTree, error) {
-	newTabletSet := lhs.tableID() | rhs.tableID()
+	newTabletSet := lhs.tableID().Merge(rhs.tableID())
 
 	merger := func(a, b *routeTree) (*routeTree, error) {
 		if inner {
@@ -1200,7 +1200,7 @@ func (p parenTables) Len() int {
 }
 
 func (p parenTables) Less(i, j int) bool {
-	return p[i].tableID() < p[j].tableID()
+	return p[i].tableID().TableOffset() < p[j].tableID().TableOffset()
 }
 
 func (p parenTables) Swap(i, j int) {
diff --git a/go/vt/vtgate/planbuilder/subquerytree.go b/go/vt/vtgate/planbuilder/subquerytree.go
index 328c336c32..013beaf922 100644
--- a/go/vt/vtgate/planbuilder/subquerytree.go
+++ b/go/vt/vtgate/planbuilder/subquerytree.go
@@ -35,7 +35,7 @@ type subqueryTree struct {
 var _ queryTree = (*subqueryTree)(nil)
 
 func (s *subqueryTree) tableID() semantics.TableSet {
-	return s.inner.tableID() | s.outer.tableID()
+	return s.inner.tableID().Merge(s.outer.tableID())
 }
 
 func (s *subqueryTree) cost() int {
diff --git a/go/vt/vtgate/semantics/binder.go b/go/vt/vtgate/semantics/binder.go
index 82daff9e75..cdd94cb139 100644
--- a/go/vt/vtgate/semantics/binder.go
+++ b/go/vt/vtgate/semantics/binder.go
@@ -96,11 +96,11 @@ func (b *binder) down(cursor *sqlparser.Cursor) error {
 			break
 		}
 		scope := b.scoper.currentScope()
-		ts := TableSet(0)
+		var ts TableSet
 		for _, table := range scope.tables {
 			expr := table.getExpr()
 			if expr != nil {
-				ts |= b.tc.tableSetFor(expr)
+				ts.MergeInPlace(b.tc.tableSetFor(expr))
 			}
 		}
 		b.recursive[node] = ts
diff --git a/go/vt/vtgate/semantics/derived_table.go b/go/vt/vtgate/semantics/derived_table.go
index 0367a5fff0..560d4789e5 100644
--- a/go/vt/vtgate/semantics/derived_table.go
+++ b/go/vt/vtgate/semantics/derived_table.go
@@ -52,7 +52,7 @@ func createDerivedTableForExpressions(expressions sqlparser.SelectExprs, tables
 			}
 		case *sqlparser.StarExpr:
 			for _, table := range tables {
-				vTbl.tables |= table.getTableSet(org)
+				vTbl.tables.MergeInPlace(table.getTableSet(org))
 			}
 		}
 	}
@@ -121,7 +121,7 @@ func (dt *derivedTable) getColumns() []ColumnInfo {
 }
 
 func (dt *derivedTable) hasStar() bool {
-	return dt.tables > 0
+	return dt.tables.NumberOfTables() > 0
 }
 
 // GetTables implements the TableInfo interface
diff --git a/go/vt/vtgate/semantics/semantic_state.go b/go/vt/vtgate/semantics/semantic_state.go
index 01a9f0734d..6f3c4b65f1 100644
--- a/go/vt/vtgate/semantics/semantic_state.go
+++ b/go/vt/vtgate/semantics/semantic_state.go
@@ -63,11 +63,6 @@ type (
 		Type querypb.Type
 	}
 
-	// TableSet is how a set of tables is expressed.
-	// Tables get unique bits assigned in the order that they are encountered during semantic analysis
-	TableSet uint64 // we can only join 64 tables with this underlying data type
-	// TODO : change uint64 to struct to support arbitrary number of tables.
-
 	// ExprDependencies stores the tables that an expression depends on as a map
 	ExprDependencies map[sqlparser.Expr]TableSet
 
@@ -135,18 +130,19 @@ func NewSemTable() *SemTable {
 func (st *SemTable) TableSetFor(t *sqlparser.AliasedTableExpr) TableSet {
 	for idx, t2 := range st.Tables {
 		if t == t2.getExpr() {
-			return 1 << idx
+			return SingleTableSet(idx)
 		}
 	}
-	return 0
+	return 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 {
+	offset := id.TableOffset()
+	if offset < 0 {
 		return nil, ErrMultipleTables
 	}
-	return st.Tables[id.TableOffset()], nil
+	return st.Tables[offset], nil
 }
 
 // RecursiveDeps return the table dependencies of the expression.
@@ -232,7 +228,7 @@ func (d ExprDependencies) Dependencies(expr sqlparser.Expr) TableSet {
 
 		set, found := d[expr]
 		if found {
-			deps |= set
+			deps.MergeInPlace(set)
 		}
 
 		// if we found a cached value, there is no need to continue down to visit children
@@ -243,52 +239,6 @@ func (d ExprDependencies) Dependencies(expr sqlparser.Expr) TableSet {
 	return deps
 }
 
-// IsOverlapping returns true if at least one table exists in both sets
-func (ts TableSet) IsOverlapping(b TableSet) bool { return ts&b != 0 }
-
-// IsSolvedBy returns true if all of `ts` is contained in `b`
-func (ts TableSet) IsSolvedBy(b TableSet) bool { return ts&b == ts }
-
-// NumberOfTables returns the number of bits set
-func (ts TableSet) NumberOfTables() int {
-	// Brian Kernighan’s Algorithm
-	count := 0
-	for ts > 0 {
-		ts &= ts - 1
-		count++
-	}
-	return count
-}
-
-// TableOffset returns the offset in the Tables array from TableSet
-func (ts TableSet) TableOffset() int {
-	offset := 0
-	for ts > 1 {
-		ts = ts >> 1
-		offset++
-	}
-	return offset
-}
-
-// Constituents returns an slice with all the
-// individual tables in their own TableSet identifier
-func (ts TableSet) Constituents() (result []TableSet) {
-	mask := ts
-
-	for mask > 0 {
-		maskLeft := mask & (mask - 1)
-		constituent := mask ^ maskLeft
-		mask = maskLeft
-		result = append(result, constituent)
-	}
-	return
-}
-
-// Merge creates a TableSet that contains both inputs
-func (ts TableSet) Merge(other TableSet) TableSet {
-	return ts | other
-}
-
 // RewriteDerivedExpression rewrites all the ColName instances in the supplied expression with
 // the expressions behind the column definition of the derived table
 // SELECT foo FROM (SELECT id+42 as foo FROM user) as t
diff --git a/go/vt/vtgate/semantics/table_collector.go b/go/vt/vtgate/semantics/table_collector.go
index 06e879dae5..bf91457c47 100644
--- a/go/vt/vtgate/semantics/table_collector.go
+++ b/go/vt/vtgate/semantics/table_collector.go
@@ -136,7 +136,7 @@ func newVindexTable(t sqlparser.TableIdent) *vindexes.Table {
 func (tc *tableCollector) tableSetFor(t *sqlparser.AliasedTableExpr) TableSet {
 	for i, t2 := range tc.Tables {
 		if t == t2.getExpr() {
-			return TableSet(1 << i)
+			return SingleTableSet(i)
 		}
 	}
 	panic("unknown table")
diff --git a/go/vt/vtgate/semantics/tabletset.go b/go/vt/vtgate/semantics/tabletset.go
new file mode 100644
index 0000000000..54aab332eb
--- /dev/null
+++ b/go/vt/vtgate/semantics/tabletset.go
@@ -0,0 +1,319 @@
+/*
+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 (
+	"fmt"
+	"math/bits"
+)
+
+type largeTableSet struct {
+	tables []uint64
+}
+
+func (ts *largeTableSet) overlapsSmall(small uint64) bool {
+	return ts.tables[0]&uint64(small) != 0
+}
+
+func minlen(a, b []uint64) int {
+	if len(a) < len(b) {
+		return len(a)
+	}
+	return len(b)
+}
+
+func (ts *largeTableSet) overlaps(b *largeTableSet) bool {
+	min := minlen(ts.tables, b.tables)
+	for t := 0; t < min; t++ {
+		if ts.tables[t]&b.tables[t] != 0 {
+			return true
+		}
+	}
+	return false
+}
+
+func (ts *largeTableSet) containsSmall(small uint64) bool {
+	return small&ts.tables[0] == small
+}
+
+func (ts *largeTableSet) isContainedBy(b *largeTableSet) bool {
+	if len(ts.tables) > len(b.tables) {
+		return false
+	}
+	for i, t := range ts.tables {
+		if t&b.tables[i] != t {
+			return false
+		}
+	}
+	return true
+}
+
+func (ts *largeTableSet) popcount() (count int) {
+	for _, t := range ts.tables {
+		count += bits.OnesCount64(t)
+	}
+	return
+}
+
+func (ts *largeTableSet) merge(other *largeTableSet) *largeTableSet {
+	small, large := ts.tables, other.tables
+	if len(small) > len(large) {
+		small, large = large, small
+	}
+
+	merged := make([]uint64, len(large))
+	m := 0
+
+	for m < len(small) {
+		merged[m] = small[m] | large[m]
+		m++
+	}
+	for m < len(large) {
+		merged[m] = large[m]
+		m++
+	}
+
+	return &largeTableSet{merged}
+}
+
+func (ts *largeTableSet) mergeSmall(small uint64) *largeTableSet {
+	merged := make([]uint64, len(ts.tables))
+	copy(merged, ts.tables)
+	merged[0] |= small
+	return &largeTableSet{merged}
+}
+
+func (ts *largeTableSet) mergeInPlace(other *largeTableSet) {
+	if len(other.tables) > len(ts.tables) {
+		merged := make([]uint64, len(other.tables))
+		copy(merged, ts.tables)
+		ts.tables = merged
+	}
+	for i := range other.tables {
+		ts.tables[i] |= other.tables[i]
+	}
+}
+
+func (ts *largeTableSet) mergeSmallInPlace(small uint64) {
+	ts.tables[0] |= small
+}
+
+func (ts *largeTableSet) tableOffset() (offset int) {
+	var found bool
+	for chunk, t := range ts.tables {
+		if t == 0 {
+			continue
+		}
+		if found || bits.OnesCount64(t) != 1 {
+			return -1
+		}
+		offset = chunk*64 + bits.TrailingZeros64(t)
+		found = true
+	}
+	return
+}
+
+func (ts *largeTableSet) add(tableidx int) {
+	chunk := tableidx / 64
+	offset := tableidx % 64
+
+	if len(ts.tables) <= chunk {
+		tables := make([]uint64, chunk+1)
+		copy(tables, ts.tables)
+		ts.tables = tables
+	}
+
+	ts.tables[chunk] |= 1 << offset
+}
+
+func (ts *largeTableSet) foreach(callback func(int)) {
+	for idx, bitset := range ts.tables {
+		for bitset != 0 {
+			t := bitset & -bitset
+			r := bits.TrailingZeros64(bitset)
+			callback(idx*64 + r)
+			bitset ^= t
+		}
+	}
+}
+
+func newLargeTableSet(small uint64, tableidx int) *largeTableSet {
+	chunk := tableidx / 64
+	offset := tableidx % 64
+
+	tables := make([]uint64, chunk+1)
+	tables[0] = small
+	tables[chunk] |= 1 << offset
+
+	return &largeTableSet{tables}
+}
+
+// TableSet is how a set of tables is expressed.
+// Tables get unique bits assigned in the order that they are encountered during semantic analysis.
+// This TableSet implementation is optimized for sets of less than 64 tables, but can grow to support an arbitrary
+// large amount of tables.
+type TableSet struct {
+	small uint64
+	large *largeTableSet
+}
+
+func (ts TableSet) Format(f fmt.State, verb rune) {
+	first := true
+	fmt.Fprintf(f, "TableSet{")
+	ts.ForEachTable(func(tid int) {
+		if first {
+			fmt.Fprintf(f, "%d", tid)
+			first = false
+		} else {
+			fmt.Fprintf(f, ",%d", tid)
+		}
+	})
+	fmt.Fprintf(f, "}")
+}
+
+// IsOverlapping returns true if at least one table exists in both sets
+func (ts TableSet) IsOverlapping(other TableSet) bool {
+	switch {
+	case ts.large == nil && other.large == nil:
+		return ts.small&other.small != 0
+	case ts.large == nil:
+		return other.large.overlapsSmall(ts.small)
+	case other.large == nil:
+		return ts.large.overlapsSmall(other.small)
+	default:
+		return ts.large.overlaps(other.large)
+	}
+}
+
+// IsSolvedBy returns true if all of `ts` is contained in `other`
+func (ts TableSet) IsSolvedBy(other TableSet) bool {
+	switch {
+	case ts.large == nil && other.large == nil:
+		return ts.small&other.small == ts.small
+	case ts.large == nil:
+		return other.large.containsSmall(ts.small)
+	case other.large == nil:
+		// if we're a large table and other is not, we cannot be contained by other
+		return false
+	default:
+		return ts.large.isContainedBy(other.large)
+	}
+}
+
+// NumberOfTables returns the number of bits set
+func (ts TableSet) NumberOfTables() int {
+	if ts.large == nil {
+		return bits.OnesCount64(ts.small)
+	}
+	return ts.large.popcount()
+}
+
+// TableOffset returns the offset in the Tables array from TableSet
+func (ts TableSet) TableOffset() int {
+	if ts.large == nil {
+		if bits.OnesCount64(ts.small) != 1 {
+			return -1
+		}
+		return bits.TrailingZeros64(ts.small)
+	}
+	return ts.large.tableOffset()
+}
+
+// ForEachTable calls the given callback with the indices for all tables in this TableSet
+func (ts TableSet) ForEachTable(callback func(int)) {
+	if ts.large == nil {
+		bitset := ts.small
+		for bitset != 0 {
+			t := bitset & -bitset
+			callback(bits.TrailingZeros64(bitset))
+			bitset ^= t
+		}
+	} else {
+		ts.large.foreach(callback)
+	}
+}
+
+// Constituents returns a slice with the indices for all tables in this TableSet
+func (ts TableSet) Constituents() (result []int) {
+	ts.ForEachTable(func(t int) {
+		result = append(result, t)
+	})
+	return
+}
+
+// Merge creates a TableSet that contains both inputs
+func (ts TableSet) Merge(other TableSet) TableSet {
+	switch {
+	case ts.large == nil && other.large == nil:
+		return TableSet{small: ts.small | other.small}
+	case ts.large == nil:
+		return TableSet{large: other.large.mergeSmall(ts.small)}
+	case other.large == nil:
+		return TableSet{large: ts.large.mergeSmall(other.small)}
+	default:
+		return TableSet{large: ts.large.merge(other.large)}
+	}
+}
+
+// MergeInPlace merges all the tables in `other` into this TableSet
+func (ts *TableSet) MergeInPlace(other TableSet) {
+	switch {
+	case ts.large == nil && other.large == nil:
+		ts.small |= other.small
+	case ts.large == nil:
+		ts.large = other.large.mergeSmall(ts.small)
+	case other.large == nil:
+		ts.large.mergeSmallInPlace(other.small)
+	default:
+		ts.large.mergeInPlace(other.large)
+	}
+}
+
+// AddTable adds the given table to this set
+func (ts *TableSet) AddTable(tableidx int) {
+	switch {
+	case ts.large == nil && tableidx < 64:
+		ts.small |= 1 << tableidx
+	case ts.large == nil:
+		ts.large = newLargeTableSet(ts.small, tableidx)
+	default:
+		ts.large.add(tableidx)
+	}
+}
+
+// SingleTableSet creates a TableSet that contains only the given table
+func SingleTableSet(tableidx int) TableSet {
+	if tableidx < 64 {
+		return TableSet{small: 1 << tableidx}
+	}
+	return TableSet{large: newLargeTableSet(0x0, tableidx)}
+}
+
+// MergeTableSets merges all the given TableSet into a single one
+func MergeTableSets(tss ...TableSet) (result TableSet) {
+	for _, t := range tss {
+		result.MergeInPlace(t)
+	}
+	return
+}
+
+func TableSetFromIds(tids ...int) (ts TableSet) {
+	for _, tid := range tids {
+		ts.AddTable(tid)
+	}
+	return
+}
diff --git a/go/vt/vtgate/semantics/vtable.go b/go/vt/vtgate/semantics/vtable.go
index 9d4984812f..59ac6a072d 100644
--- a/go/vt/vtgate/semantics/vtable.go
+++ b/go/vt/vtgate/semantics/vtable.go
@@ -106,7 +106,7 @@ func (v *vTableInfo) getColumns() []ColumnInfo {
 }
 
 func (v *vTableInfo) hasStar() bool {
-	return v.tables > 0
+	return v.tables.NumberOfTables() > 0
 }
 
 // GetTables implements the TableInfo interface
@@ -155,7 +155,7 @@ func selectExprsToInfos(
 			}
 		case *sqlparser.StarExpr:
 			for _, table := range tables {
-				ts |= table.getTableSet(org)
+				ts.MergeInPlace(table.getTableSet(org))
 			}
 		}
 	}


Test patch:
diff --git a/go/vt/vtgate/planbuilder/abstract/operator_test.go b/go/vt/vtgate/planbuilder/abstract/operator_test.go
index 0bf45509a7..83505a578c 100644
--- a/go/vt/vtgate/planbuilder/abstract/operator_test.go
+++ b/go/vt/vtgate/planbuilder/abstract/operator_test.go
@@ -192,7 +192,7 @@ func (qt *QueryTable) testString() string {
 		where = " where " + strings.Join(preds, " and ")
 	}
 
-	return fmt.Sprintf("\t%d:%s%s%s", qt.TableID, sqlparser.String(qt.Table), alias, where)
+	return fmt.Sprintf("\t%v:%s%s%s", qt.TableID, sqlparser.String(qt.Table), alias, where)
 }
 
 func (qg *QueryGraph) testString() string {
@@ -208,17 +208,13 @@ func (qg *QueryGraph) crossPredicateString() string {
 	}
 	var joinPreds []string
 	for deps, predicates := range qg.innerJoins {
-		var tables []string
-		for _, id := range deps.Constituents() {
-			tables = append(tables, fmt.Sprintf("%d", id))
-		}
 		var expressions []string
 		for _, expr := range predicates {
 			expressions = append(expressions, sqlparser.String(expr))
 		}
-		tableConcat := strings.Join(tables, ":")
+
 		exprConcat := strings.Join(expressions, " and ")
-		joinPreds = append(joinPreds, fmt.Sprintf("\t%s - %s", tableConcat, exprConcat))
+		joinPreds = append(joinPreds, fmt.Sprintf("\t%v - %s", deps, exprConcat))
 	}
 	sort.Strings(joinPreds)
 	return fmt.Sprintf("\nJoinPredicates:\n%s", strings.Join(joinPreds, "\n"))
diff --git a/go/vt/vtgate/planbuilder/abstract/operator_test_data.txt b/go/vt/vtgate/planbuilder/abstract/operator_test_data.txt
index 548eec0af7..2970ce7863 100644
--- a/go/vt/vtgate/planbuilder/abstract/operator_test_data.txt
+++ b/go/vt/vtgate/planbuilder/abstract/operator_test_data.txt
@@ -2,15 +2,15 @@
 Concatenate(distinct) {
 	QueryGraph: {
 	Tables:
-		1:unsharded
+		TableSet{0}:unsharded
 	},
 	QueryGraph: {
 	Tables:
-		2:unsharded_auto
+		TableSet{1}:unsharded_auto
 	},
 	QueryGraph: {
 	Tables:
-		4:`user`
+		TableSet{2}:`user`
 	}
 }
 
@@ -18,11 +18,11 @@ select id from unsharded union select id from unsharded_auto
 Concatenate(distinct) {
 	QueryGraph: {
 	Tables:
-		1:unsharded
+		TableSet{0}:unsharded
 	},
 	QueryGraph: {
 	Tables:
-		2:unsharded_auto
+		TableSet{1}:unsharded_auto
 	}
 }
 
@@ -30,11 +30,11 @@ select id from unsharded union all select id from unsharded_auto
 Concatenate {
 	QueryGraph: {
 	Tables:
-		1:unsharded
+		TableSet{0}:unsharded
 	},
 	QueryGraph: {
 	Tables:
-		2:unsharded_auto
+		TableSet{1}:unsharded_auto
 	}
 }
 
@@ -43,17 +43,17 @@ Concatenate(distinct) {
 	Concatenate {
 		QueryGraph: {
 		Tables:
-			1:unsharded
+			TableSet{0}:unsharded
 		},
 		QueryGraph: {
 		Tables:
-			2:unsharded_auto
+			TableSet{1}:unsharded_auto
 		},
 		limit 10
 	},
 	QueryGraph: {
 	Tables:
-		4:x
+		TableSet{2}:x
 	},
 	order by id asc
 }
@@ -62,15 +62,15 @@ Concatenate(distinct) {
 Concatenate {
 	QueryGraph: {
 	Tables:
-		1:unsharded
+		TableSet{0}:unsharded
 	},
 	QueryGraph: {
 	Tables:
-		2:unsharded_auto
+		TableSet{1}:unsharded_auto
 	},
 	QueryGraph: {
 	Tables:
-		4:x
+		TableSet{2}:x
 	}
 }
 
@@ -78,15 +78,15 @@ Concatenate {
 Concatenate(distinct) {
 	QueryGraph: {
 	Tables:
-		1:unsharded
+		TableSet{0}:unsharded
 	},
 	QueryGraph: {
 	Tables:
-		2:unsharded_auto
+		TableSet{1}:unsharded_auto
 	},
 	QueryGraph: {
 	Tables:
-		4:x
+		TableSet{2}:x
 	}
 }
 
@@ -95,63 +95,63 @@ Concatenate {
 	Concatenate(distinct) {
 		QueryGraph: {
 		Tables:
-			1:unsharded
+			TableSet{0}:unsharded
 		},
 		QueryGraph: {
 		Tables:
-			2:unsharded_auto
+			TableSet{1}:unsharded_auto
 		}
 	},
 	QueryGraph: {
 	Tables:
-		4:x
+		TableSet{2}:x
 	}
 }
 
 select * from t
 QueryGraph: {
 Tables:
-	1:t
+	TableSet{0}:t
 }
 
 select t.c from t,y,z where t.c = y.c and (t.a = z.a or t.a = y.a) and 1 < 2
 QueryGraph: {
 Tables:
-	1:t
-	2:y
-	4:z
+	TableSet{0}:t
+	TableSet{1}:y
+	TableSet{2}:z
 JoinPredicates:
-	1:2 - t.c = y.c
-	1:2:4 - t.a = z.a or t.a = y.a
+	TableSet{0,1,2} - t.a = z.a or t.a = y.a
+	TableSet{0,1} - t.c = y.c
 ForAll: 1 < 2
 }
 
 select t.c from t join y on t.id = y.t_id join z on t.id = z.t_id where t.name = 'foo' and y.col = 42 and z.baz = 101
 QueryGraph: {
 Tables:
-	1:t where t.`name` = 'foo'
-	2:y where y.col = 42
-	4:z where z.baz = 101
+	TableSet{0}:t where t.`name` = 'foo'
+	TableSet{1}:y where y.col = 42
+	TableSet{2}:z where z.baz = 101
 JoinPredicates:
-	1:2 - t.id = y.t_id
-	1:4 - t.id = z.t_id
+	TableSet{0,1} - t.id = y.t_id
+	TableSet{0,2} - t.id = z.t_id
 }
 
 select t.c from t,y,z where t.name = 'foo' and y.col = 42 and z.baz = 101 and t.id = y.t_id and t.id = z.t_id
 QueryGraph: {
 Tables:
-	1:t where t.`name` = 'foo'
-	2:y where y.col = 42
-	4:z where z.baz = 101
+	TableSet{0}:t where t.`name` = 'foo'
+	TableSet{1}:y where y.col = 42
+	TableSet{2}:z where z.baz = 101
 JoinPredicates:
-	1:2 - t.id = y.t_id
-	1:4 - t.id = z.t_id
+	TableSet{0,1} - t.id = y.t_id
+	TableSet{0,2} - t.id = z.t_id
 }
 
 select 1 from t where '1' = 1 and 12 = '12'
 QueryGraph: {
 Tables:
-	1:t
+	TableSet{0}:t
 ForAll: '1' = 1 and 12 = '12'
 }
 
@@ -159,11 +159,11 @@ select 1 from t left join s on t.id = s.id
 OuterJoin: {
 	Inner: 	QueryGraph: {
 	Tables:
-		1:t
+		TableSet{0}:t
 	}
 	Outer: 	QueryGraph: {
 	Tables:
-		2:s
+		TableSet{1}:s
 	}
 	Predicate: t.id = s.id
 }
@@ -171,21 +171,21 @@ OuterJoin: {
 select 1 from t join s on t.id = s.id and t.name = s.name
 QueryGraph: {
 Tables:
-	1:t
-	2:s
+	TableSet{0}:t
+	TableSet{1}:s
 JoinPredicates:
-	1:2 - t.id = s.id and t.`name` = s.`name`
+	TableSet{0,1} - t.id = s.id and t.`name` = s.`name`
 }
 
 select 1 from t left join s on t.id = s.id where t.name = 'Mister'
 OuterJoin: {
 	Inner: 	QueryGraph: {
 	Tables:
-		1:t where t.`name` = 'Mister'
+		TableSet{0}:t where t.`name` = 'Mister'
 	}
 	Outer: 	QueryGraph: {
 	Tables:
-		2:s
+		TableSet{1}:s
 	}
 	Predicate: t.id = s.id
 }
@@ -194,11 +194,11 @@ select 1 from t right join s on t.id = s.id
 OuterJoin: {
 	Inner: 	QueryGraph: {
 	Tables:
-		2:s
+		TableSet{1}:s
 	}
 	Outer: 	QueryGraph: {
 	Tables:
-		1:t
+		TableSet{0}:t
 	}
 	Predicate: t.id = s.id
 }
@@ -208,22 +208,22 @@ Join: {
 	LHS: 	OuterJoin: {
 		Inner: 	QueryGraph: {
 		Tables:
-			1:a
+			TableSet{0}:a
 		}
 		Outer: 	QueryGraph: {
 		Tables:
-			2:b
+			TableSet{1}:b
 		}
 		Predicate: a.id = b.id
 	}
 	RHS: 	OuterJoin: {
 		Inner: 	QueryGraph: {
 		Tables:
-			4:c
+			TableSet{2}:c
 		}
 		Outer: 	QueryGraph: {
 		Tables:
-			8:d
+			TableSet{3}:d
 		}
 		Predicate: c.id = d.id
 	}
@@ -235,7 +235,7 @@ Derived t: {
 	Query: select 42 as id from tbl
 	Inner:	QueryGraph: {
 	Tables:
-		1:tbl
+		TableSet{0}:tbl
 	}
 }
 
@@ -245,14 +245,14 @@ Join: {
 		Query: select id from tbl limit 10
 		Inner:	QueryGraph: {
 		Tables:
-			1:tbl
+			TableSet{0}:tbl
 		}
 	}
 	RHS: 	Derived s: {
 		Query: select foo, count(*) from usr group by foo
 		Inner:	QueryGraph: {
 		Tables:
-			4:usr
+			TableSet{2}:usr
 		}
 	}
 	Predicate: t.id = s.foo
@@ -265,26 +265,26 @@ SubQuery: {
 		Type: PulloutValue
 		Query: 	QueryGraph: {
 		Tables:
-			2:dual
+			TableSet{1}:dual
 		}
 	}
 	{
 		Type: PulloutExists
 		Query: 	QueryGraph: {
 		Tables:
-			4:dual
+			TableSet{2}:dual
 		}
 	}
 	{
 		Type: PulloutIn
 		Query: 	QueryGraph: {
 		Tables:
-			8:dual
+			TableSet{3}:dual
 		}
 	}]
 	Outer: 	QueryGraph: {
 	Tables:
-		1:t where id in (select 1 from dual)
+		TableSet{0}:t where id in (select 1 from dual)
 	ForAll: exists (select 1 from dual)
 	}
 }
@@ -296,16 +296,16 @@ SubQuery: {
 		Type: PulloutValue
 		Query: 	QueryGraph: {
 		Tables:
-			2:user_extra
+			TableSet{1}:user_extra
 		JoinPredicates:
-			1:2 - id = u.id
+			TableSet{0,1} - id = u.id
 		}
 	}]
 	Outer: 	QueryGraph: {
 	Tables:
-		1:`user` AS u
+		TableSet{0}:`user` AS u
 	JoinPredicates:
-		1:2 - u.id = (select id from user_extra where id = u.id)
+		TableSet{0,1} - u.id = (select id from user_extra where id = u.id)
 	}
 }
 
@@ -323,7 +323,7 @@ Join: {
 	}
 	RHS: 	QueryGraph: {
 	Tables:
-		2:`user` AS u
+		TableSet{1}:`user` AS u
 	}
 	Predicate: ui.id = u.id
 }
@@ -341,11 +341,11 @@ select 1 from a union select 2 from b
 Concatenate(distinct) {
 	QueryGraph: {
 	Tables:
-		1:a
+		TableSet{0}:a
 	},
 	QueryGraph: {
 	Tables:
-		2:b
+		TableSet{1}:b
 	}
 }
 
@@ -353,15 +353,15 @@ select 1 from a union select 2 from b union select 3 from c
 Concatenate(distinct) {
 	QueryGraph: {
 	Tables:
-		1:a
+		TableSet{0}:a
 	},
 	QueryGraph: {
 	Tables:
-		2:b
+		TableSet{1}:b
 	},
 	QueryGraph: {
 	Tables:
-		4:c
+		TableSet{2}:c
 	}
 }
 
@@ -370,20 +370,20 @@ Concatenate {
 	Concatenate(distinct) {
 		QueryGraph: {
 		Tables:
-			1:a
+			TableSet{0}:a
 		},
 		QueryGraph: {
 		Tables:
-			2:b
+			TableSet{1}:b
 		},
 		QueryGraph: {
 		Tables:
-			4:c
+			TableSet{2}:c
 		}
 	},
 	QueryGraph: {
 	Tables:
-		8:d
+		TableSet{3}:d
 	}
 }
 
@@ -391,11 +391,11 @@ select id from unsharded union select id from unsharded_auto order by id
 Concatenate(distinct) {
 	QueryGraph: {
 	Tables:
-		1:unsharded
+		TableSet{0}:unsharded
 	},
 	QueryGraph: {
 	Tables:
-		2:unsharded_auto
+		TableSet{1}:unsharded_auto
 	},
 	order by id asc
 }
diff --git a/go/vt/vtgate/planbuilder/route_planning_test.go b/go/vt/vtgate/planbuilder/route_planning_test.go
index 4f2a72bdc1..3d0dcea57e 100644
--- a/go/vt/vtgate/planbuilder/route_planning_test.go
+++ b/go/vt/vtgate/planbuilder/route_planning_test.go
@@ -54,6 +54,8 @@ func selectScatter(solved semantics.TableSet, keyspace *vindexes.Keyspace) *rout
 	}
 }
 
+var ts = semantics.TableSetFromIds
+
 func TestMergeJoins(t *testing.T) {
 	t.Skip("?")
 	ks := &vindexes.Keyspace{Name: "apa", Sharded: false}
@@ -65,36 +67,36 @@ func TestMergeJoins(t *testing.T) {
 	}
 
 	tests := []testCase{{
-		l:        unsharded(1, ks),
-		r:        unsharded(2, ks),
-		expected: unsharded(1|2, ks),
+		l:        unsharded(ts(0), ks),
+		r:        unsharded(ts(1), ks),
+		expected: unsharded(ts(0, 1), ks),
 	}, {
-		l:        unsharded(1, ks),
-		r:        unsharded(2, ks2),
+		l:        unsharded(ts(0), ks),
+		r:        unsharded(ts(1), ks2),
 		expected: nil,
 	}, {
-		l:        unsharded(2, ks),
-		r:        unsharded(1, ks2),
+		l:        unsharded(ts(1), ks),
+		r:        unsharded(ts(0), ks2),
 		expected: nil,
 	}, {
-		l:        selectDBA(1, ks),
-		r:        selectDBA(2, ks),
-		expected: selectDBA(1|2, ks),
+		l:        selectDBA(ts(0), ks),
+		r:        selectDBA(ts(1), ks),
+		expected: selectDBA(ts(0, 1), ks),
 	}, {
-		l:        selectDBA(1, ks),
-		r:        selectDBA(2, ks2),
-		expected: selectDBA(1|2, ks),
+		l:        selectDBA(ts(0), ks),
+		r:        selectDBA(ts(1), ks2),
+		expected: selectDBA(ts(0, 1), ks),
 	}, {
-		l:        selectDBA(2, ks),
-		r:        selectDBA(1, ks2),
-		expected: selectDBA(1|2, ks),
+		l:        selectDBA(ts(1), ks),
+		r:        selectDBA(ts(0), ks2),
+		expected: selectDBA(ts(0, 1), ks),
 	}, {
-		l:        unsharded(1, ks),
-		r:        selectDBA(2, ks),
+		l:        unsharded(ts(0), ks),
+		r:        selectDBA(ts(1), ks),
 		expected: nil,
 	}, {
-		l: selectScatter(1, ks),
-		r: selectScatter(2, ks),
+		l: selectScatter(ts(0), ks),
+		r: selectScatter(ts(1), ks),
 		predicates: []sqlparser.Expr{
 			equals(colName("t1", "id"), colName("t2", "id")),
 		},
@@ -130,28 +132,28 @@ func TestCreateRoutePlanForOuter(t *testing.T) {
 	assert := assert.New(t)
 	m1 := &routeTable{
 		qtable: &abstract.QueryTable{
-			TableID: semantics.TableSet(1),
+			TableID: ts(0),
 			Table:   sqlparser.TableName{},
 		},
 		vtable: &vindexes.Table{},
 	}
 	m2 := &routeTable{
 		qtable: &abstract.QueryTable{
-			TableID: semantics.TableSet(2),
+			TableID: ts(1),
 			Table:   sqlparser.TableName{},
 		},
 		vtable: &vindexes.Table{},
 	}
 	m3 := &routeTable{
 		qtable: &abstract.QueryTable{
-			TableID: semantics.TableSet(4),
+			TableID: ts(2),
 			Table:   sqlparser.TableName{},
 		},
 		vtable: &vindexes.Table{},
 	}
 	a := &routeTree{
 		routeOpCode: engine.SelectUnsharded,
-		solved:      semantics.TableSet(1),
+		solved:      ts(0),
 		tables:      []relation{m1},
 	}
 	col1 := sqlparser.NewColNameWithQualifier("id", sqlparser.TableName{
@@ -162,7 +164,7 @@ func TestCreateRoutePlanForOuter(t *testing.T) {
 	})
 	b := &routeTree{
 		routeOpCode: engine.SelectUnsharded,
-		solved:      semantics.TableSet(6),
+		solved:      ts(1, 2),
 		tables:      []relation{m2, m3},
 		predicates:  []sqlparser.Expr{equals(col1, col2)},
 	}
diff --git a/go/vt/vtgate/semantics/analyzer_test.go b/go/vt/vtgate/semantics/analyzer_test.go
index 1f5b89095b..467af9c6a4 100644
--- a/go/vt/vtgate/semantics/analyzer_test.go
+++ b/go/vt/vtgate/semantics/analyzer_test.go
@@ -27,15 +27,15 @@ import (
 	"vitess.io/vitess/go/vt/vtgate/vindexes"
 )
 
-const T0 TableSet = 0
+var T0 TableSet
 
-const (
+var (
 	// Just here to make outputs more readable
-	T1 TableSet = 1 << iota
-	T2
-	T3
-	T4
-	T5
+	T1 = SingleTableSet(0)
+	T2 = SingleTableSet(1)
+	T3 = SingleTableSet(2)
+	T4 = SingleTableSet(3)
+	T5 = SingleTableSet(4)
 )
 
 func extract(in *sqlparser.Select, idx int) sqlparser.Expr {
@@ -61,7 +61,7 @@ func TestBindingSingleTablePositive(t *testing.T) {
 			sel, _ := stmt.(*sqlparser.Select)
 			t1 := sel.From[0].(*sqlparser.AliasedTableExpr)
 			ts := semTable.TableSetFor(t1)
-			assert.EqualValues(t, 1, ts)
+			assert.Equal(t, SingleTableSet(0), ts)
 
 			recursiveDeps := semTable.RecursiveDeps(extract(sel, 0))
 			assert.Equal(t, T1, recursiveDeps, query)
@@ -87,7 +87,7 @@ func TestBindingSingleAliasedTablePositive(t *testing.T) {
 			sel, _ := stmt.(*sqlparser.Select)
 			t1 := sel.From[0].(*sqlparser.AliasedTableExpr)
 			ts := semTable.TableSetFor(t1)
-			assert.EqualValues(t, 1, ts)
+			assert.Equal(t, SingleTableSet(0), ts)
 
 			recursiveDeps := semTable.RecursiveDeps(extract(sel, 0))
 			require.Equal(t, T1, recursiveDeps, query)
@@ -155,15 +155,15 @@ func TestBindingMultiTablePositive(t *testing.T) {
 		numberOfTables: 1,
 	}, {
 		query:          "select max(t.col+s.col) from t, s",
-		deps:           T1 | T2,
+		deps:           MergeTableSets(T1, T2),
 		numberOfTables: 2,
 	}, {
 		query:          "select max(t.col+s.col) from t join s",
-		deps:           T1 | T2,
+		deps:           MergeTableSets(T1, T2),
 		numberOfTables: 2,
 	}, {
 		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,
+		deps:           MergeTableSets(T1, T2, T3, T5),
 		numberOfTables: 4,
 		// }, {
 		// TODO: move to subquery
@@ -175,7 +175,7 @@ func TestBindingMultiTablePositive(t *testing.T) {
 		// 	deps:  T1 | T2,
 	}, {
 		query:          "select u1.a + u2.a from u1, u2",
-		deps:           T1 | T2,
+		deps:           MergeTableSets(T1, T2),
 		numberOfTables: 2,
 	}}
 	for _, query := range queries {
@@ -201,15 +201,15 @@ func TestBindingMultiAliasedTablePositive(t *testing.T) {
 		numberOfTables: 1,
 	}, {
 		query:          "select X.col+S.col from t as X, s as S",
-		deps:           T1 | T2,
+		deps:           MergeTableSets(T1, T2),
 		numberOfTables: 2,
 	}, {
 		query:          "select max(X.col+S.col) from t as X, s as S",
-		deps:           T1 | T2,
+		deps:           MergeTableSets(T1, T2),
 		numberOfTables: 2,
 	}, {
 		query:          "select max(X.col+s.col) from t as X, s",
-		deps:           T1 | T2,
+		deps:           MergeTableSets(T1, T2),
 		numberOfTables: 2,
 	}}
 	for _, query := range queries {
@@ -583,25 +583,25 @@ func TestOrderByBindingTable(t *testing.T) {
 		T2,
 	}, {
 		"(select id from t1) union (select uid from t2) order by id",
-		T1 | T2,
+		MergeTableSets(T1, T2),
 	}, {
 		"select id from t1 union (select uid from t2) order by 1",
-		T1 | T2,
+		MergeTableSets(T1, T2),
 	}, {
 		"select id from t1 union select uid from t2 union (select name from t) order by 1",
-		T1 | T2 | T3,
+		MergeTableSets(T1, T2, T3),
 	}, {
 		"select a.id from t1 as a union (select uid from t2) order by 1",
-		T1 | T2,
+		MergeTableSets(T1, T2),
 	}, {
 		"select b.id as a from t1 as b union (select uid as c from t2) order by 1",
-		T1 | T2,
+		MergeTableSets(T1, T2),
 	}, {
 		"select a.id from t1 as a union (select uid from t2, t union (select name from t) order by 1) order by 1",
-		T1 | T2 | T4,
+		MergeTableSets(T1, T2, T4),
 	}, {
 		"select a.id from t1 as a union (select uid from t2, t union (select name from t) order by 1) order by id",
-		T1 | T2 | T4,
+		MergeTableSets(T1, T2, T4),
 	}}
 	for _, tc := range tcases {
 		t.Run(tc.sql, func(t *testing.T) {
@@ -719,7 +719,7 @@ func TestHavingBinding(t *testing.T) {
 		T1,
 	}, {
 		"select t.id, count(*) as a from t, t1 group by t.id having a = 1",
-		T1 | T2,
+		MergeTableSets(T1, T2),
 	}, {
 		sql:  "select u2.a, u1.a from u1, u2 having u2.a = 2",
 		deps: T2,
@@ -747,8 +747,8 @@ func TestUnionCheckFirstAndLastSelectsDeps(t *testing.T) {
 	t2 := sel2.From[0].(*sqlparser.AliasedTableExpr)
 	ts1 := semTable.TableSetFor(t1)
 	ts2 := semTable.TableSetFor(t2)
-	assert.EqualValues(t, 1, ts1)
-	assert.EqualValues(t, 2, ts2)
+	assert.Equal(t, SingleTableSet(0), ts1)
+	assert.Equal(t, SingleTableSet(1), ts2)
 
 	d1 := semTable.RecursiveDeps(extract(sel1, 0))
 	d2 := semTable.RecursiveDeps(extract(sel2, 0))
@@ -819,8 +819,8 @@ func TestUnionWithOrderBy(t *testing.T) {
 	t2 := sel2.From[0].(*sqlparser.AliasedTableExpr)
 	ts1 := semTable.TableSetFor(t1)
 	ts2 := semTable.TableSetFor(t2)
-	assert.EqualValues(t, 1, ts1)
-	assert.EqualValues(t, 2, ts2)
+	assert.Equal(t, SingleTableSet(0), ts1)
+	assert.Equal(t, SingleTableSet(1), ts2)
 
 	d1 := semTable.RecursiveDeps(extract(sel1, 0))
 	d2 := semTable.RecursiveDeps(extract(sel2, 0))
@@ -875,11 +875,11 @@ func TestScopingWDerivedTables(t *testing.T) {
 		}, {
 			query:                "select t.id from (select * from user, music) as t",
 			expectation:          T3,
-			recursiveExpectation: T1 | T2,
+			recursiveExpectation: MergeTableSets(T1, T2),
 		}, {
 			query:                "select t.id from (select * from user, music) as t order by t.id",
 			expectation:          T3,
-			recursiveExpectation: T1 | T2,
+			recursiveExpectation: MergeTableSets(T1, T2),
 		}, {
 			query:                "select t.id from (select * from user) as t join user as u on t.id = u.id",
 			expectation:          T2,
@@ -982,8 +982,8 @@ func TestScopingWVindexTables(t *testing.T) {
 			expectation:          T1,
 		}, {
 			query:                "select u.id + t.id from t as t join user_index as u where u.id = 1 and u.id = t.id",
-			recursiveExpectation: T1 | T2,
-			expectation:          T1 | T2,
+			recursiveExpectation: MergeTableSets(T1, T2),
+			expectation:          MergeTableSets(T1, T2),
 		},
 	}
 	for _, query := range queries {
diff --git a/go/vt/vtgate/semantics/tabletset_test.go b/go/vt/vtgate/semantics/tabletset_test.go
index 4ca005ae99..c901f23974 100644
--- a/go/vt/vtgate/semantics/tabletset_test.go
+++ b/go/vt/vtgate/semantics/tabletset_test.go
@@ -17,38 +17,42 @@ limitations under the License.
 package semantics
 
 import (
+	"math/rand"
 	"testing"
 
 	"github.com/stretchr/testify/assert"
 )
 
-const (
-	F1 TableSet = 1 << iota
-	F2
-	F3
+var (
+	F1 = SingleTableSet(0)
+	F2 = SingleTableSet(1)
+	F3 = SingleTableSet(2)
+
+	F12  = F1.Merge(F2)
+	F123 = F12.Merge(F3)
 )
 
 func TestTableSet_IsOverlapping(t *testing.T) {
-	assert.True(t, (F1 | F2).IsOverlapping(F1|F2))
-	assert.True(t, F1.IsOverlapping(F1|F2))
-	assert.True(t, (F1 | F2).IsOverlapping(F1))
-	assert.False(t, F3.IsOverlapping(F1|F2))
-	assert.False(t, (F1 | F2).IsOverlapping(F3))
+	assert.True(t, F12.IsOverlapping(F12))
+	assert.True(t, F1.IsOverlapping(F12))
+	assert.True(t, F12.IsOverlapping(F1))
+	assert.False(t, F3.IsOverlapping(F12))
+	assert.False(t, F12.IsOverlapping(F3))
 }
 
 func TestTableSet_IsSolvedBy(t *testing.T) {
-	assert.True(t, F1.IsSolvedBy(F1|F2))
-	assert.False(t, (F1 | F2).IsSolvedBy(F1))
-	assert.False(t, F3.IsSolvedBy(F1|F2))
-	assert.False(t, (F1 | F2).IsSolvedBy(F3))
+	assert.True(t, F1.IsSolvedBy(F12))
+	assert.False(t, (F12).IsSolvedBy(F1))
+	assert.False(t, F3.IsSolvedBy(F12))
+	assert.False(t, (F12).IsSolvedBy(F3))
 }
 
 func TestTableSet_Constituents(t *testing.T) {
-	assert.Equal(t, []TableSet{F1, F2, F3}, (F1 | F2 | F3).Constituents())
-	assert.Equal(t, []TableSet{F1, F2}, (F1 | F2).Constituents())
-	assert.Equal(t, []TableSet{F1, F3}, (F1 | F3).Constituents())
-	assert.Equal(t, []TableSet{F2, F3}, (F2 | F3).Constituents())
-	assert.Empty(t, TableSet(0).Constituents())
+	assert.Equal(t, []int{0, 1, 2}, (F123).Constituents())
+	assert.Equal(t, []int{0, 1}, (F12).Constituents())
+	assert.Equal(t, []int{0, 2}, (F1.Merge(F3)).Constituents())
+	assert.Equal(t, []int{1, 2}, (F2.Merge(F3)).Constituents())
+	assert.Empty(t, TableSet{}.Constituents())
 }
 
 func TestTableSet_TableOffset(t *testing.T) {
@@ -56,3 +60,82 @@ func TestTableSet_TableOffset(t *testing.T) {
 	assert.Equal(t, 1, F2.TableOffset())
 	assert.Equal(t, 2, F3.TableOffset())
 }
+
+func TestTableSet_LargeTablesConstituents(t *testing.T) {
+	const GapSize = 32
+
+	var ts TableSet
+	var expected []int
+	var table int
+
+	for t := 0; t < 256; t++ {
+		table += rand.Intn(GapSize) + 1
+		expected = append(expected, table)
+		ts.AddTable(table)
+	}
+
+	assert.Equal(t, expected, ts.Constituents())
+}
+
+func TestTabletSet_LargeMergeInPlace(t *testing.T) {
+	const SetRange = 256
+	const Blocks = 64
+
+	var tablesets = make([]TableSet, 64)
+
+	for i := range tablesets {
+		ts := &tablesets[i]
+		setrng := i * SetRange
+
+		for tid := 0; tid < SetRange; tid++ {
+			ts.AddTable(setrng + tid)
+		}
+	}
+
+	var result TableSet
+	for _, ts := range tablesets {
+		result.MergeInPlace(ts)
+	}
+
+	var expected = make([]int, SetRange*Blocks)
+	for tid := range expected {
+		expected[tid] = tid
+	}
+
+	assert.Equal(t, expected, result.Constituents())
+}
+
+func TestTabletSet_LargeMerge(t *testing.T) {
+	const SetRange = 256
+	const Blocks = 64
+
+	var tablesets = make([]TableSet, 64)
+
+	for i := range tablesets {
+		ts := &tablesets[i]
+		setrng := i * SetRange
+
+		for tid := 0; tid < SetRange; tid++ {
+			ts.AddTable(setrng + tid)
+		}
+	}
+
+	var result TableSet
+	for _, ts := range tablesets {
+		result = result.Merge(ts)
+	}
+
+	var expected = make([]int, SetRange*Blocks)
+	for tid := range expected {
+		expected[tid] = tid
+	}
+
+	assert.Equal(t, expected, result.Constituents())
+}
+
+func TestTableSet_LargeOffset(t *testing.T) {
+	for tid := 0; tid < 1024; tid++ {
+		ts := SingleTableSet(tid)
+		assert.Equal(t, tid, ts.TableOffset())
+	}
+}