Repository: vitessio/vitess
Pull request #11317 (2022-09-22 09:55:08)

Fix complex predicates being pulled into `ON` conditions for `LEFT JOIN` statements.
## Description

Complex `WHERE` predicates for joined tables (stuff along the lines of `(lhs.a = ... OR rhs.b = ...)` or even just `lhs.a = rhs.b`) are pulled into the join conditions. This makes sense for `INNER JOIN` statements, but for `LEFT JOIN` statements this will cause the result to be totally wrong.

This PR fixes this issue by performing this movement of predicates only for non-`LEFT JOIN`s. On top of that, we now also detect more cases where `LEFT JOIN`s can be transformed to `INNER JOIN`s due to "null intolerant" comparisons (e.g. `lhs.a = rhs.b` in the `WHERE` condition allows rewriting a left join between `lhs` and `rhs` to an inner join).

```sql
SELECT music.id FROM music LEFT OUTER JOIN user ON music.user_id = user.id WHERE (user.name = 'Trent Reznor' OR music.genre = 'pop') AND music.user_id = 5
```

had the following plan generated:

```json
{
  "QueryType": "SELECT",
  "Original": "SELECT music.id FROM music LEFT OUTER JOIN user ON music.user_id = user.id WHERE (user.name = 'Trent Reznor' OR music.genre = 'pop') AND music.user_id = 5",
  "Instructions": {
    "OperatorType": "Route",
    "Variant": "EqualUnique",
    "Keyspace": {
      "Name": "user",
      "Sharded": true
    },
    "FieldQuery": "select music.id from music left join `user` on music.user_id = `user`.id and (`user`.`name` = 'Trent Reznor' or music.genre = 'pop') where 1 != 1",
    "Query": "select music.id from music left join `user` on music.user_id = `user`.id and (`user`.`name` = 'Trent Reznor' or music.genre = 'pop') where music.user_id = 5",
    "Table": "`user`, music",
    "Values": [
      "INT64(5)"
    ],
    "Vindex": "user_index"
  },
  "TablesUsed": [
    "user.music",
    "user.user"
  ]
}
```

the executed query became:

```sql
select music.id from music left join `user` on music.user_id = `user`.id and (`user`.`name` = 'Trent Reznor' or music.genre = 'pop') where music.user_id = 5
```

Which has a very different meaning from the original query.

The new plan looks like this:

```json
{
  "QueryType": "SELECT",
  "Original": "SELECT music.id FROM music LEFT OUTER JOIN user ON music.user_id = user.id WHERE (user.name = 'Trent Reznor' OR music.genre = 'pop') AND music.user_id = 5",
  "Instructions": {
    "OperatorType": "Route",
    "Variant": "EqualUnique",
    "Keyspace": {
      "Name": "user",
      "Sharded": true
    },
    "FieldQuery": "select music.id from music left join `user` on music.user_id = `user`.id where 1 != 1",
    "Query": "select music.id from music left join `user` on music.user_id = `user`.id where music.user_id = 5 and (`user`.`name` = 'Trent Reznor' or music.genre = 'pop')",
    "Table": "`user`, music",
    "Values": [
      "INT64(5)"
    ],
    "Vindex": "user_index"
  },
  "TablesUsed": [
    "user.music",
    "user.user"
  ]
}
```

And the predicates are kept in the `WHERE` part of the query.

## Related Issue(s)

Fixes https://github.com/vitessio/vitess/issues/11275

## Checklist

-   [ ] "Backport me!" label has been added if this change should be backported
-   [ ] Tests were added or are not required
-   [ ] Documentation was added or is not required

## Deployment Notes

<!-- Notes regarding deployment of the contained body of work. These should note any db migrations, etc. -->


vitess-bot[bot]: ### Review Checklist
            
Hello reviewers! :wave: Please follow this checklist when reviewing this Pull Request.

#### General
- [ ] Ensure that the Pull Request has a descriptive title.
- [ ] If this is a change that users need to know about, please apply the `release notes (needs details)` label so that merging is blocked unless the summary release notes document is included.
- [ ] If a new flag is being introduced, review whether it is really needed. The flag names should be clear and intuitive (as far as possible), and the flag's help should be descriptive. Additionally, flag names should use dashes (`-`) as word separators rather than underscores (`_`).
- [ ] If a workflow is added or modified, each items in `Jobs` should be named in order to mark it as `required`. If the workflow should be required, the GitHub Admin should be notified.

#### Bug fixes
- [ ] There should be at least one unit or end-to-end test.
- [ ] The Pull Request description should either include a link to an issue that describes the bug OR an actual description of the bug and how to reproduce, along with a description of the fix.

#### Non-trivial changes
- [ ] There should be some code comments as to why things are implemented the way they are.

#### New/Existing features
- [ ] Should be documented, either by modifying the existing documentation or creating new documentation.
- [ ] New features should have a link to a feature request issue or an RFC that documents the use cases, corner cases and test cases.

#### Backward compatibility            
- [ ] Protobuf changes should be wire-compatible.
- [ ] Changes to `_vt` tables and RPCs need to be backward compatible.
- [ ] `vtctl` command output order should be stable and `awk`-able.


Patch:
diff --git a/go/vt/vtgate/engine/route.go b/go/vt/vtgate/engine/route.go
index d233b7f640..2c4fe3442c 100644
--- a/go/vt/vtgate/engine/route.go
+++ b/go/vt/vtgate/engine/route.go
@@ -434,7 +434,7 @@ func (route *Route) sort(in *sqltypes.Result) (*sqltypes.Result, error) {
 		return true
 	})
 
-	return out, err
+	return out.Truncate(route.TruncateColumnCount), err
 }
 
 func (route *Route) description() PrimitiveDescription {
diff --git a/go/vt/vtgate/planbuilder/abstract/join.go b/go/vt/vtgate/planbuilder/abstract/join.go
index 55ad992f3e..b15c0b780d 100644
--- a/go/vt/vtgate/planbuilder/abstract/join.go
+++ b/go/vt/vtgate/planbuilder/abstract/join.go
@@ -46,22 +46,10 @@ func (j *Join) PushPredicate(expr sqlparser.Expr, semTable *semantics.SemTable)
 		}
 		j.LHS = lhs
 		return j, nil
+
 	case deps.IsSolvedBy(j.RHS.TableID()):
-		// we are looking for predicates like `tbl.col = <>` or `<> = tbl.col`,
-		// where tbl is on the rhs of the left outer join
-		if cmp, isCmp := expr.(*sqlparser.ComparisonExpr); isCmp && cmp.Operator != sqlparser.NullSafeEqualOp &&
-			(sqlparser.IsColName(cmp.Left) && semTable.RecursiveDeps(cmp.Left).IsSolvedBy(j.RHS.TableID()) ||
-				sqlparser.IsColName(cmp.Right) && semTable.RecursiveDeps(cmp.Right).IsSolvedBy(j.RHS.TableID())) {
-			// When the predicate we are pushing is using information from an outer table, we can
-			// check whether the predicate is "null-intolerant" or not. Null-intolerant in this context means that
-			// the predicate will not return true if the table columns are null.
-			// Since an outer join is an inner join with the addition of all the rows from the left-hand side that
-			// matched no rows on the right-hand, if we are later going to remove all the rows where the right-hand
-			// side did not match, we might as well turn the join into an inner join.
-
-			// This is based on the paper "Canonical Abstraction for Outerjoin Optimization" by J Rao et al
-			j.LeftJoin = false
-		}
+		j.tryConvertToInnerJoin(expr, semTable)
+
 		if !j.LeftJoin {
 			rhs, err := j.RHS.PushPredicate(expr, semTable)
 			if err != nil {
@@ -70,19 +58,68 @@ func (j *Join) PushPredicate(expr sqlparser.Expr, semTable *semantics.SemTable)
 			j.RHS = rhs
 			return j, err
 		}
+
 		op := &Filter{
 			Source:     j,
 			Predicates: []sqlparser.Expr{expr},
 		}
 		return op, nil
+
 	case deps.IsSolvedBy(j.LHS.TableID().Merge(j.RHS.TableID())):
-		j.Predicate = sqlparser.AndExpressions(j.Predicate, expr)
-		return j, nil
+		j.tryConvertToInnerJoin(expr, semTable)
+
+		if !j.LeftJoin {
+			j.Predicate = sqlparser.AndExpressions(j.Predicate, expr)
+			return j, nil
+		}
+
+		op := &Filter{
+			Source:     j,
+			Predicates: []sqlparser.Expr{expr},
+		}
+		return op, nil
 	}
 
 	return nil, vterrors.Errorf(vtrpcpb.Code_INTERNAL, "Cannot push predicate: %s", sqlparser.String(expr))
 }
 
+// When a predicate uses information from an outer table, we can convert from an outer join to an inner join
+// if the predicate is "null-intolerant".
+//
+// Null-intolerant in this context means that the predicate will not be true if the table columns are null.
+//
+// Since an outer join is an inner join with the addition of all the rows from the left-hand side that
+// matched no rows on the right-hand, if we are later going to remove all the rows where the right-hand
+// side did not match, we might as well turn the join into an inner join.
+//
+// This is based on the paper "Canonical Abstraction for Outerjoin Optimization" by J Rao et al
+func (j *Join) tryConvertToInnerJoin(expr sqlparser.Expr, semTable *semantics.SemTable) {
+	if !j.LeftJoin {
+		return
+	}
+
+	switch expr := expr.(type) {
+	case *sqlparser.ComparisonExpr:
+		if expr.Operator == sqlparser.NullSafeEqualOp {
+			return
+		}
+
+		if sqlparser.IsColName(expr.Left) && semTable.RecursiveDeps(expr.Left).IsSolvedBy(j.RHS.TableID()) ||
+			sqlparser.IsColName(expr.Right) && semTable.RecursiveDeps(expr.Right).IsSolvedBy(j.RHS.TableID()) {
+			j.LeftJoin = false
+		}
+
+	case *sqlparser.IsExpr:
+		if expr.Right != sqlparser.IsNotNullOp {
+			return
+		}
+
+		if sqlparser.IsColName(expr.Left) && semTable.RecursiveDeps(expr.Left).IsSolvedBy(j.RHS.TableID()) {
+			j.LeftJoin = false
+		}
+	}
+}
+
 // TableID implements the Operator interface
 func (j *Join) TableID() semantics.TableSet {
 	return j.RHS.TableID().Merge(j.LHS.TableID())


Test patch:
diff --git a/go/test/endtoend/vtgate/queries/orderby/without_schematracker/main_test.go b/go/test/endtoend/vtgate/queries/orderby/without_schematracker/main_test.go
new file mode 100644
index 0000000000..00221e9c9f
--- /dev/null
+++ b/go/test/endtoend/vtgate/queries/orderby/without_schematracker/main_test.go
@@ -0,0 +1,95 @@
+/*
+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 orderby
+
+import (
+	_ "embed"
+	"flag"
+	"fmt"
+	"os"
+	"testing"
+
+	"vitess.io/vitess/go/test/endtoend/utils"
+
+	"vitess.io/vitess/go/mysql"
+	"vitess.io/vitess/go/test/endtoend/cluster"
+)
+
+var (
+	clusterInstance *cluster.LocalProcessCluster
+	vtParams        mysql.ConnParams
+	mysqlParams     mysql.ConnParams
+	keyspaceName    = "ks_orderby"
+	cell            = "test_orderby"
+
+	//go:embed schema.sql
+	schemaSQL string
+
+	//go:embed vschema.json
+	vschema string
+)
+
+func TestMain(m *testing.M) {
+	defer cluster.PanicHandler(nil)
+	flag.Parse()
+
+	exitCode := func() int {
+		clusterInstance = cluster.NewCluster(cell, "localhost")
+		defer clusterInstance.Teardown()
+
+		// Start topo server
+		err := clusterInstance.StartTopo()
+		if err != nil {
+			return 1
+		}
+
+		// Start keyspace
+		keyspace := &cluster.Keyspace{
+			Name:      keyspaceName,
+			SchemaSQL: schemaSQL,
+			VSchema:   vschema,
+		}
+		clusterInstance.VtGateExtraArgs = []string{"--schema_change_signal=false"}
+		err = clusterInstance.StartKeyspace(*keyspace, []string{"-80", "80-"}, 1, true)
+		if err != nil {
+			return 1
+		}
+
+		clusterInstance.VtGateExtraArgs = append(clusterInstance.VtGateExtraArgs, "--enable_system_settings=true")
+		// Start vtgate
+		err = clusterInstance.StartVtgate()
+		if err != nil {
+			return 1
+		}
+
+		vtParams = mysql.ConnParams{
+			Host: clusterInstance.Hostname,
+			Port: clusterInstance.VtgateMySQLPort,
+		}
+
+		// create mysql instance and connection parameters
+		conn, closer, err := utils.NewMySQL(clusterInstance, keyspaceName, schemaSQL)
+		if err != nil {
+			fmt.Println(err)
+			return 1
+		}
+		defer closer()
+		mysqlParams = conn
+		return m.Run()
+	}()
+	os.Exit(exitCode)
+}
diff --git a/go/test/endtoend/vtgate/queries/orderby/without_schematracker/orderby_test.go b/go/test/endtoend/vtgate/queries/orderby/without_schematracker/orderby_test.go
new file mode 100644
index 0000000000..77a2ceeb51
--- /dev/null
+++ b/go/test/endtoend/vtgate/queries/orderby/without_schematracker/orderby_test.go
@@ -0,0 +1,58 @@
+/*
+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 orderby
+
+import (
+	"testing"
+
+	"vitess.io/vitess/go/test/endtoend/utils"
+
+	"github.com/stretchr/testify/require"
+
+	"vitess.io/vitess/go/test/endtoend/cluster"
+)
+
+func start(t *testing.T) (utils.MySQLCompare, func()) {
+	mcmp, err := utils.NewMySQLCompare(t, vtParams, mysqlParams)
+	require.NoError(t, err)
+
+	deleteAll := func() {
+		_, _ = utils.ExecAllowError(t, mcmp.VtConn, "set workload = oltp")
+
+		tables := []string{"user"}
+		for _, table := range tables {
+			_, _ = mcmp.ExecAndIgnore("delete from " + table)
+		}
+	}
+
+	deleteAll()
+
+	return mcmp, func() {
+		deleteAll()
+		mcmp.Close()
+		cluster.PanicHandler(t)
+	}
+}
+
+func TestSimpleOrderBy(t *testing.T) {
+	mcmp, closer := start(t)
+	defer closer()
+
+	mcmp.Exec("insert into user(id, name) values (0,'Apa'),(1,'Banan'),(3,'Ceasar'),(4,'David')")
+	mcmp.AssertMatches(`SELECT name FROM user WHERE id in (0,4) ORDER BY name ASC`,
+		`[[VARCHAR("Apa")] [VARCHAR("David)]]`)
+}
diff --git a/go/test/endtoend/vtgate/queries/orderby/without_schematracker/schema.sql b/go/test/endtoend/vtgate/queries/orderby/without_schematracker/schema.sql
new file mode 100644
index 0000000000..5274203d7c
--- /dev/null
+++ b/go/test/endtoend/vtgate/queries/orderby/without_schematracker/schema.sql
@@ -0,0 +1,6 @@
+create table user
+(
+    id bigint,
+    name varchar(10),
+    primary key (id)
+) Engine = InnoDB;
\ No newline at end of file
diff --git a/go/test/endtoend/vtgate/queries/orderby/without_schematracker/vschema.json b/go/test/endtoend/vtgate/queries/orderby/without_schematracker/vschema.json
new file mode 100644
index 0000000000..8e040df5af
--- /dev/null
+++ b/go/test/endtoend/vtgate/queries/orderby/without_schematracker/vschema.json
@@ -0,0 +1,25 @@
+{
+  "sharded": true,
+  "vindexes": {
+    "user_index": {
+      "type": "hash",
+      "owner": "user"
+    }
+  },
+  "tables": {
+    "user": {
+      "column_vindexes": [
+        {
+          "column": "Id",
+          "name": "user_index"
+        }
+      ],
+      "columns": [
+        {
+          "name": "id",
+          "type": "INT64"
+        }
+      ]
+    }
+  }
+}
\ No newline at end of file
diff --git a/go/vt/vtgate/planbuilder/testdata/filter_cases.txt b/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
index 83edf5118f..75ef917849 100644
--- a/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
+++ b/go/vt/vtgate/planbuilder/testdata/filter_cases.txt
@@ -5965,6 +5965,114 @@ Gen4 plan same as above
 }
 Gen4 plan same as above
 
+# For left joins, where conditions using both sides of the join are not pulled into the join conditions
+"SELECT music.id FROM music LEFT OUTER JOIN user ON music.user_id = user.id WHERE (user.name = 'Trent Reznor' OR music.genre = 'pop') AND music.user_id = 5"
+{
+  "QueryType": "SELECT",
+  "Original": "SELECT music.id FROM music LEFT OUTER JOIN user ON music.user_id = user.id WHERE (user.name = 'Trent Reznor' OR music.genre = 'pop') AND music.user_id = 5",
+  "Instructions": {
+    "OperatorType": "Route",
+    "Variant": "EqualUnique",
+    "Keyspace": {
+      "Name": "user",
+      "Sharded": true
+    },
+    "FieldQuery": "select music.id from music left join `user` on music.user_id = `user`.id where 1 != 1",
+    "Query": "select music.id from music left join `user` on music.user_id = `user`.id where music.user_id = 5 and (`user`.`name` = 'Trent Reznor' or music.genre = 'pop')",
+    "Table": "`user`, music",
+    "Values": [
+      "INT64(5)"
+    ],
+    "Vindex": "user_index"
+  },
+  "TablesUsed": [
+    "user.music",
+    "user.user"
+  ]
+}
+Gen4 plan same as above
+
+# For left joins, where conditions using both sides of the join are not pulled into the join conditions (swapped order)
+"SELECT music.id FROM music LEFT OUTER JOIN user ON music.user_id = user.id WHERE music.user_id = 5 AND (user.name = 'Trent Reznor' OR music.genre = 'pop')"
+{
+  "QueryType": "SELECT",
+  "Original": "SELECT music.id FROM music LEFT OUTER JOIN user ON music.user_id = user.id WHERE music.user_id = 5 AND (user.name = 'Trent Reznor' OR music.genre = 'pop')",
+  "Instructions": {
+    "OperatorType": "Route",
+    "Variant": "EqualUnique",
+    "Keyspace": {
+      "Name": "user",
+      "Sharded": true
+    },
+    "FieldQuery": "select music.id from music left join `user` on music.user_id = `user`.id where 1 != 1",
+    "Query": "select music.id from music left join `user` on music.user_id = `user`.id where music.user_id = 5 and (`user`.`name` = 'Trent Reznor' or music.genre = 'pop')",
+    "Table": "`user`, music",
+    "Values": [
+      "INT64(5)"
+    ],
+    "Vindex": "user_index"
+  },
+  "TablesUsed": [
+    "user.music",
+    "user.user"
+  ]
+}
+Gen4 plan same as above
+
+# For left joins, null intolerant where conditions using both sides of the join are transformed to inner joins
+"SELECT music.id FROM music LEFT OUTER JOIN user ON music.user_id = user.id WHERE music.user_id = 5 AND music.componist = user.name"
+{
+  "QueryType": "SELECT",
+  "Original": "SELECT music.id FROM music LEFT OUTER JOIN user ON music.user_id = user.id WHERE music.user_id = 5 AND music.componist = user.name",
+  "Instructions": {
+    "OperatorType": "Route",
+    "Variant": "EqualUnique",
+    "Keyspace": {
+      "Name": "user",
+      "Sharded": true
+    },
+    "FieldQuery": "select music.id from music, `user` where 1 != 1",
+    "Query": "select music.id from music, `user` where music.user_id = 5 and music.user_id = `user`.id and music.componist = `user`.`name`",
+    "Table": "`user`, music",
+    "Values": [
+      "INT64(5)"
+    ],
+    "Vindex": "user_index"
+  },
+  "TablesUsed": [
+    "user.music",
+    "user.user"
+  ]
+}
+Gen4 plan same as above
+
+# For left joins, null intolerant where conditions using `IS NOT NULL` allow outer join simplification
+"SELECT music.id FROM music LEFT OUTER JOIN user ON user.id = music.user_id WHERE music.user_id = 5 AND user.id IS NOT NULL"
+{
+  "QueryType": "SELECT",
+  "Original": "SELECT music.id FROM music LEFT OUTER JOIN user ON user.id = music.user_id WHERE music.user_id = 5 AND user.id IS NOT NULL",
+  "Instructions": {
+    "OperatorType": "Route",
+    "Variant": "EqualUnique",
+    "Keyspace": {
+      "Name": "user",
+      "Sharded": true
+    },
+    "FieldQuery": "select music.id from music, `user` where 1 != 1",
+    "Query": "select music.id from music, `user` where music.user_id = 5 and `user`.id is not null and `user`.id = music.user_id",
+    "Table": "`user`, music",
+    "Values": [
+      "INT64(5)"
+    ],
+    "Vindex": "user_index"
+  },
+  "TablesUsed": [
+    "user.music",
+    "user.user"
+  ]
+}
+Gen4 plan same as above
+
 # optimize ORs to IN route op codes #1
 "select col from user where id = 1 or id = 2"
 {