Repository: vitessio/vitess
Pull request #8429 (2021-07-08 06:16:10)

Gen4 cost calculation tweak
## Description
When evaluating the cost of plans, gen4 was not comparing route costs correctly. This PR updates how this is done.

## 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/engine/route.go b/go/vt/vtgate/engine/route.go
index f3f169bc47..3f00ee3c92 100644
--- a/go/vt/vtgate/engine/route.go
+++ b/go/vt/vtgate/engine/route.go
@@ -210,9 +210,14 @@ func (code RouteOpcode) MarshalJSON() ([]byte, error) {
 	return json.Marshal(routeName[code])
 }
 
+// String returns a string presentation of this opcode
+func (code RouteOpcode) String() string {
+	return routeName[code]
+}
+
 // RouteType returns a description of the query routing type used by the primitive
 func (route *Route) RouteType() string {
-	return routeName[route.Opcode]
+	return route.Opcode.String()
 }
 
 // GetKeyspaceName specifies the Keyspace that this primitive routes to.
diff --git a/go/vt/vtgate/planbuilder/jointree.go b/go/vt/vtgate/planbuilder/jointree.go
index ade239ea61..dee3a07b6d 100644
--- a/go/vt/vtgate/planbuilder/jointree.go
+++ b/go/vt/vtgate/planbuilder/jointree.go
@@ -61,6 +61,13 @@ type (
 		pred  sqlparser.Expr
 	}
 
+	// cost is used to make it easy to compare the cost of two plans with each other
+	cost struct {
+		vindexCost int
+		isUnique   bool
+		opCode     engine.RouteOpcode
+	}
+
 	routePlan struct {
 		routeOpCode engine.RouteOpcode
 		solved      semantics.TableSet
@@ -76,7 +83,8 @@ type (
 		// leftJoins are the join conditions evaluated by this plan
 		leftJoins []*outerTable
 
-		// vindex and vindexValues is set if a vindex will be used for this route.
+		// these fields are set if a vindex will be used for this route
+		currentCost      cost // currentCost tracks the cost of the chosen access method
 		vindex           vindexes.Vindex
 		vindexValues     []sqltypes.PlanValue
 		vindexPredicates []sqlparser.Expr
@@ -103,6 +111,17 @@ type (
 	}
 
 	parenTables []relation
+
+	// vindexPlusPredicates is a struct used to store all the predicates that the vindex can be used to query
+	vindexPlusPredicates struct {
+		colVindex *vindexes.ColumnVindex
+		values    []sqltypes.PlanValue
+
+		// when we have the predicates found, we also know how to interact with this vindex
+		foundVindex vindexes.Vindex
+		opcode      engine.RouteOpcode
+		predicates  []sqlparser.Expr
+	}
 )
 
 // type assertions
@@ -217,17 +236,6 @@ func (rp *routePlan) cost() int {
 	return 1
 }
 
-// vindexPlusPredicates is a struct used to store all the predicates that the vindex can be used to query
-type vindexPlusPredicates struct {
-	colVindex *vindexes.ColumnVindex
-	values    []sqltypes.PlanValue
-
-	// when we have the predicates found, we also know how to interact with this vindex
-	foundVindex vindexes.Vindex
-	opcode      engine.RouteOpcode
-	predicates  []sqlparser.Expr
-}
-
 // addPredicate adds these predicates added to it. if the predicates can help,
 // they will improve the routeOpCode
 func (rp *routePlan) addPredicate(predicates ...sqlparser.Expr) error {
@@ -552,7 +560,9 @@ func (rp *routePlan) pickBestAvailableVindex() {
 			continue
 		}
 		// Choose the minimum cost vindex from the ones which are covered
-		if rp.vindex == nil || v.colVindex.Vindex.Cost() < rp.vindex.Cost() {
+		thisCost := costFor(v.foundVindex, v.opcode)
+		if rp.vindex == nil || less(thisCost, rp.currentCost) {
+			rp.currentCost = thisCost
 			rp.routeOpCode = v.opcode
 			rp.vindex = v.foundVindex
 			rp.vindexValues = v.values
@@ -633,3 +643,37 @@ func (jp *joinPlan) pushOutputColumns(columns []*sqlparser.ColName, semTable *se
 	}
 	return outputColumns
 }
+
+// costFor returns a cost struct to make route choices easier to compare
+func costFor(foundVindex vindexes.Vindex, opcode engine.RouteOpcode) cost {
+	switch opcode {
+	// For these opcodes, we should not have a vindex, so we just return the opcode as the cost
+	case engine.SelectUnsharded, engine.SelectNext, engine.SelectDBA, engine.SelectReference, engine.SelectNone, engine.SelectScatter:
+		return cost{
+			opCode: opcode,
+		}
+	}
+
+	// if we have a multiplier that is non-zero, we should have a vindex
+	if foundVindex == nil {
+		panic("expected a vindex")
+	}
+
+	return cost{
+		vindexCost: foundVindex.Cost(),
+		isUnique:   foundVindex.IsUnique(),
+		opCode:     opcode,
+	}
+}
+
+// less compares two costs and returns true if the first cost is cheaper than the second
+func less(c1, c2 cost) bool {
+	switch {
+	case c1.opCode != c2.opCode:
+		return c1.opCode < c2.opCode
+	case c1.isUnique == c2.isUnique:
+		return c1.vindexCost <= c2.vindexCost
+	default:
+		return c1.isUnique
+	}
+}


Test patch:
diff --git a/go/vt/vtgate/planbuilder/testdata/filter_cases.txt b/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
index c7642bf536..4ae8b355b6 100644
--- a/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
@@ -985,6 +985,7 @@ Gen4 plan same as above
     "Vindex": "name_user_map"
   }
 }
+Gen4 plan same as above
 
 # Route with multiple route constraints, SelectEqual is the best constraint.
 "select id from user where user.col = false and user.id in (1, 2) and user.name = 'aa'"
@@ -1007,6 +1008,7 @@ Gen4 plan same as above
     "Vindex": "name_user_map"
   }
 }
+Gen4 plan same as above
 
 # Route with multiple route constraints, SelectEqualUnique is the best constraint.
 "select id from user where user.col = 5 and user.id in (1, 2) and user.name = 'aa' and user.id = 1"