opt: do not push LIMIT into the scan of a virtual table

Mark Sirek · Mark Sirek · commit 1d82da6ba0d2 · 2022-04-05T10:17:26.000-07:00
Fixes #78578 Previously, a LIMIT operation could be pushed into the scan of a virtual table with an ORDER BY clause. This was inadequate because in-order scans of virtual indexes aren't supported. When an index that should provide the order requested by a query is used, a sort is actually produced under the covers: ``` EXPLAIN(vec) SELECT oid, typname FROM pg_type ORDER BY OID; info ---------------------------------- │ └ Node 1 └ *colexec.sortOp └ *sql.planNodeToRowSource ``` Functions `CanLimitFilteredScan` and `GenerateLimitedScans` are modified to avoid pushing LIMIT operations into ordered scans of virtual indexes. Release justification: Low risk fix for incorrect results in queries involving virtual system tables. Release note (bug fix): LIMIT queries with an ORDER BY clause which scan the index of a virtual system tables, such as `pg_type`, could previously return incorrect results. This is corrected by teaching the optimizer that LIMIT operations cannot be pushed into ordered scans of virtual indexes.
diff --git a/pkg/sql/logictest/testdata/logic_test/limit b/pkg/sql/logictest/testdata/logic_test/limit
@@ -351,3 +351,10 @@ SELECT * FROM t ORDER BY v, w LIMIT 3;
 6  -36  216
 4  -16  94
 2  -4   8
+
+query IT
+SELECT oid::INT, typname FROM pg_type ORDER BY oid LIMIT 3
+----
+16  bool
+17  bytea
+18  char
diff --git a/pkg/sql/opt/exec/execbuilder/testdata/limit b/pkg/sql/opt/exec/execbuilder/testdata/limit
@@ -527,3 +527,42 @@ vectorized: true
           estimated row count: 100 - 1,001 (100% of the table; stats collected <hidden> ago)
           table: a@a_i_j_idx
           spans: FULL SCAN
+
+# A limit cannot be pushed into the scan of a virtual table with ORDER BY.
+query T
+EXPLAIN SELECT oid, typname FROM pg_type ORDER BY oid LIMIT 10
+----
+distribution: local
+vectorized: true
+·
+• limit
+│ count: 10
+│
+└── • virtual table
+      table: pg_type@pg_type_oid_idx
+
+# A limit can be pushed into the scan of a virtual table without ORDER BY.
+query T
+EXPLAIN SELECT oid, typname FROM pg_type LIMIT 10
+----
+distribution: local
+vectorized: true
+·
+• virtual table
+  table: pg_type@primary
+  limit: 10
+
+# A limit cannot be pushed into the constrained scan of a virtual table with
+# ORDER BY.
+query T
+EXPLAIN SELECT oid, typname FROM pg_type WHERE OID BETWEEN 1 AND 1000 ORDER BY oid LIMIT 10
+----
+distribution: local
+vectorized: true
+·
+• limit
+│ count: 10
+│
+└── • virtual table
+      table: pg_type@pg_type_oid_idx
+      spans: [/1 - /1000]
diff --git a/pkg/sql/opt/memo/expr.go b/pkg/sql/opt/memo/expr.go
@@ -668,6 +668,12 @@ func (s *ScanPrivate) IsFullIndexScan(md *opt.Metadata) bool {
 		s.HardLimit == 0
 }
 
+// IsVirtualTable returns true if the table being scanned is a virtual table.
+func (s *ScanPrivate) IsVirtualTable(md *opt.Metadata) bool {
+	tab := md.Table(s.Table)
+	return tab.IsVirtualTable()
+}
+
 // IsLocking returns true if the ScanPrivate is configured to use a row-level
 // locking mode. This can be the case either because the Scan is in the scope of
 // a SELECT .. FOR [KEY] UPDATE/SHARE clause or because the Scan was configured
diff --git a/pkg/sql/opt/xform/limit_funcs.go b/pkg/sql/opt/xform/limit_funcs.go
@@ -60,7 +60,14 @@ func (c *CustomFuncs) CanLimitFilteredScan(
 		// unconstrained scans on non-partial indexes.
 		return false
 	}
-
+	// Virtual indexes are not sorted, but are presented to the optimizer as
+	// sorted, and have a sort automatically applied to them on the output of the
+	// scan. Since this implicit sort happens after the scan, we can't place a
+	// hard limit on the scan if the query semantics require a sort order on the
+	// entire relation.
+	if scanPrivate.IsVirtualTable(md) && !required.Any() {
+		return false
+	}
 	ok, _ := ordering.ScanPrivateCanProvide(c.e.mem.Metadata(), scanPrivate, &required)
 	return ok
 }
@@ -87,6 +94,14 @@ func (c *CustomFuncs) CanLimitFilteredScan(
 func (c *CustomFuncs) GenerateLimitedScans(
 	grp memo.RelExpr, scanPrivate *memo.ScanPrivate, limit tree.Datum, required props.OrderingChoice,
 ) {
+	// Virtual indexes are not sorted, but are presented to the optimizer as
+	// sorted, and have a sort automatically applied to them on the output of the
+	// scan. Since this implicit sort happens after the scan, we can't place a
+	// hard limit on the scan if the query semantics require a sort order on the
+	// entire relation.
+	if scanPrivate.IsVirtualTable(c.e.mem.Metadata()) && !required.Any() {
+		return
+	}
 	limitVal := int64(*limit.(*tree.DInt))
 
 	var pkCols opt.ColSet
