BUG #19408: Bad plan for UNION ALL subquery with outer WHERE, ORDER BY, LIMIT, and separate indexes

The following bug has been logged on the website:

Bug reference: 19408
Logged by: Anthony Cloutier
Email address: link_xliv(at)hotmail(dot)com
PostgreSQL version: 16.12
Operating system: Windows 11 Enterprise; Version 24H2 (26100.4652)
Description:

Consider a query of the following form:
```
SELECT *
FROM
(
SELECT * FROM t1
UNION ALL
SELECT * FROM t2
<more UNION ALL'd tables...>
) sub
WHERE <condition>
ORDER BY <sort>
LIMIT <len>;
```

The query planner generates a very suboptimal plan under the following
circumstances:
- Each table has an index supporting the WHERE clause
- Each table has a different index supporting the ORDER BY clause
- WHERE clause has a very low selectivity for some but not all of the tables
involved

### Example setup

```
CREATE TABLE t1 AS
SELECT i AS x, repeat(chr(floor(random() * 26)::int + 65), 500) AS y
FROM generate_series(1, 10000000) i;

CREATE TABLE t2 AS
SELECT i % 10 + 1 AS x, repeat(chr(floor(random() * 26)::int + 65), 500) AS
y
FROM generate_series(1, 10000000) i;

CREATE INDEX ON t1 (x);
CREATE INDEX ON t1 (y);
CREATE INDEX ON t2 (x);
CREATE INDEX ON t2 (y);

ANALYZE t1, t2;
```

### Observed behavior

Very suboptimal plan for example query:
```
test=# EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM (SELECT x, y FROM t1 UNION
ALL SELECT x, y FROM t2) sub WHERE x = 1 ORDER BY y LIMIT 100;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=1.63..4966.36 rows=100 width=508) (actual
time=564182.937..564239.095 rows=100 loops=1)
Buffers: shared hit=197 read=4459324 dirtied=2748884 written=2535251
-> Merge Append (cost=1.63..50128867.22 rows=1009700 width=508) (actual
time=564182.936..564239.062 rows=100 loops=1)
Sort Key: t1.y
Buffers: shared hit=197 read=4459324 dirtied=2748884
written=2535251
-> Index Scan using t1_y_idx on t1 (cost=0.81..25058270.67 rows=1
width=508) (actual time=564181.032..564181.032 rows=1 loops=1)
Filter: (x = 1)
Rows Removed by Filter: 5766512
Buffers: shared hit=197 read=4458562 dirtied=2748884
written=2534615
-> Index Scan using t2_y_idx on t2 (cost=0.81..25060499.54
rows=1009699 width=508) (actual time=1.838..57.832 rows=100 loops=1)
Filter: (x = 1)
Rows Removed by Filter: 910
Buffers: shared read=762 written=636
Planning:
Buffers: shared hit=64 read=4
Planning Time: 71.917 ms
Execution Time: 564239.163 ms
(17 lignes)
```

### Expected behavior

When I add some useless computation to the example query, the planner comes
up with the more sensible plan:
```
test=# EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM (SELECT x, y || '' AS y FROM
t1 UNION ALL SELECT x, y FROM t2) sub WHERE x = 1 ORDER BY y LIMIT 100;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=382199.71..384685.17 rows=100 width=508) (actual
time=0.332..1.352 rows=100 loops=1)
Buffers: shared hit=763 read=3
-> Merge Append (cost=382199.71..25477006.09 rows=1009668 width=508)
(actual time=0.331..1.343 rows=100 loops=1)
Sort Key: ((t1.y || ''::text))
Buffers: shared hit=763 read=3
-> Sort (cost=8.46..8.47 rows=1 width=36) (actual
time=0.281..0.281 rows=1 loops=1)
Sort Key: ((t1.y || ''::text))
Sort Method: quicksort Memory: 26kB
Buffers: shared hit=1 read=3
-> Index Scan using t1_x_idx on t1 (cost=0.43..8.46 rows=1
width=36) (actual time=0.269..0.270 rows=1 loops=1)
Index Cond: (x = 1)
Buffers: shared hit=1 read=3
-> Index Scan using t2_y_idx on t2 (cost=0.81..25059710.66
rows=1009667 width=508) (actual time=0.023..0.997 rows=100 loops=1)
Filter: (x = 1)
Rows Removed by Filter: 910
Buffers: shared hit=762
Planning:
Buffers: shared hit=5 read=3
Planning Time: 144.037 ms
Execution Time: 1.561 ms
(20 lignes)
```

This is the plan I would expect for the first query, without having to
resort to any hack.

### Additional info

The better plan for the modified query leads me to believe the planner is
capable of generating different subplans for t1 and t2. Yet it doesn't in
the case of the original query, although its row estimates look fine. Also,
when performing a similar query on t1 or t2 individually, the planner
appears to make the appropriate decision in each case:
```
test=# EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM (SELECT x, y FROM t1) sub
WHERE x = 1 ORDER BY y LIMIT 100;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Limit (cost=8.46..8.47 rows=1 width=508) (actual time=0.086..0.087 rows=1
loops=1)
Buffers: shared hit=4
-> Sort (cost=8.46..8.47 rows=1 width=508) (actual time=0.085..0.085
rows=1 loops=1)
Sort Key: t1.y
Sort Method: quicksort Memory: 26kB
Buffers: shared hit=4
-> Index Scan using t1_x_idx on t1 (cost=0.43..8.45 rows=1
width=508) (actual time=0.072..0.073 rows=1 loops=1)
Index Cond: (x = 1)
Buffers: shared hit=4
Planning Time: 0.180 ms
Execution Time: 0.108 ms
(11 lignes)

test=# EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM (SELECT x, y FROM t2) sub
WHERE x = 1 ORDER BY y LIMIT 100;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.81..1107.88 rows=100 width=508) (actual time=0.025..0.595
rows=100 loops=1)
Buffers: shared hit=762
-> Index Scan using t2_y_idx on t2 (cost=0.81..11177683.57 rows=1009667
width=508) (actual time=0.024..0.589 rows=100 loops=1)
Filter: (x = 1)
Rows Removed by Filter: 910
Buffers: shared hit=762
Planning Time: 0.128 ms
Execution Time: 0.609 ms
(8 lignes)
```

I've also come up with this rewrite of the example query, which feels more
right than the useless computation hack, although it results in a slightly
different plan and requires repeating the WHERE, ORDER BY and LIMIT clauses
multiple times:
```
test=# EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM ((SELECT x, y FROM t1 WHERE
x = 1 ORDER BY y LIMIT 100) UNION ALL (SELECT x, y FROM t2 WHERE x = 1 ORDER
BY y LIMIT 100)) sub ORDER BY y LIMIT 100;
QUERY
PLAN
------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=9.28..1106.39 rows=100 width=508) (actual time=0.078..1.003
rows=100 loops=1)
Buffers: shared hit=766
-> Merge Append (cost=9.28..1117.36 rows=101 width=508) (actual
time=0.077..0.995 rows=100 loops=1)
Sort Key: t1.y
Buffers: shared hit=766
-> Limit (cost=8.46..8.47 rows=1 width=508) (actual
time=0.049..0.049 rows=1 loops=1)
Buffers: shared hit=4
-> Sort (cost=8.46..8.47 rows=1 width=508) (actual
time=0.048..0.049 rows=1 loops=1)
Sort Key: t1.y
Sort Method: quicksort Memory: 26kB
Buffers: shared hit=4
-> Index Scan using t1_x_idx on t1 (cost=0.43..8.45
rows=1 width=508) (actual time=0.018..0.019 rows=1 loops=1)
Index Cond: (x = 1)
Buffers: shared hit=4
-> Limit (cost=0.81..1107.88 rows=100 width=508) (actual
time=0.015..0.898 rows=100 loops=1)
Buffers: shared hit=762
-> Index Scan using t2_y_idx on t2 (cost=0.81..11177683.57
rows=1009667 width=508) (actual time=0.015..0.890 rows=100 loops=1)
Filter: (x = 1)
Rows Removed by Filter: 910
Buffers: shared hit=762
Planning Time: 0.200 ms
Execution Time: 1.035 ms
(22 lignes)
```

I'm aware that each table could have a single index on (x, y) to support
both the WHERE and ORDER BY clauses, and then the best plan would become
quite obvious to the planner, without the need for any hack or rewrite. But
besides the fact that I'd rather not have a multitude of indexes for all the
filtering and sorting combinations that my application offers, this will not
work for a condition not supported by a btree, e.g. `x LIKE '%search%'`.