Skip to content

Commit 9c7f522

Browse files
tglsfdctglsfdc
committed
Optimize joins when the inner relation can be proven unique.
If there can certainly be no more than one matching inner row for a given outer row, then the executor can move on to the next outer row as soon as it's found one match; there's no need to continue scanning the inner relation for this outer row. This saves useless scanning in nestloop and hash joins. In merge joins, it offers the opportunity to skip mark/restore processing, because we know we have not advanced past the first possible match for the next outer row. Of course, the devil is in the details: the proof of uniqueness must depend only on joinquals (not otherquals), and if we want to skip mergejoin mark/restore then it must depend only on merge clauses. To avoid adding more planning overhead than absolutely necessary, the present patch errs in the conservative direction: there are cases where inner_unique or skip_mark_restore processing could be used, but it will not do so because it's not sure that the uniqueness proof depended only on "safe" clauses. This could be improved later. David Rowley, reviewed and rather heavily editorialized on by me Discussion: https://postgr.es/m/CAApHDvqF6Sw-TK98bW48TdtFJ+3a7D2mFyZ7++=D-RyPsL76gw@mail.gmail.com
1 parent f13a912 commit 9c7f522

File tree

26 files changed

+987
-206
lines changed

26 files changed

+987
-206
lines changed

‎contrib/citext/expected/citext.out

+1-1
Original file line numberDiff line numberDiff line change
@@ -2336,8 +2336,8 @@ SELECT *
23362336
WHERE t.id IS NULL OR m.id IS NULL;
23372337
id | name | id | name
23382338
----+------+----+------
2339-
| | 2 | Two
23402339
2 | two | |
2340+
| | 2 | Two
23412341
(2 rows)
23422342

23432343
REFRESH MATERIALIZED VIEW CONCURRENTLY citext_matview;

‎contrib/citext/expected/citext_1.out

+1-1
Original file line numberDiff line numberDiff line change
@@ -2336,8 +2336,8 @@ SELECT *
23362336
WHERE t.id IS NULL OR m.id IS NULL;
23372337
id | name | id | name
23382338
----+------+----+------
2339-
| | 2 | Two
23402339
2 | two | |
2340+
| | 2 | Two
23412341
(2 rows)
23422342

23432343
REFRESH MATERIALIZED VIEW CONCURRENTLY citext_matview;

‎contrib/postgres_fdw/expected/postgres_fdw.out

+37-32
Original file line numberDiff line numberDiff line change
@@ -396,13 +396,14 @@ EXPLAIN (VERBOSE, COSTS OFF)
396396
Output: t1.c1, t2."C 1"
397397
-> Merge Join
398398
Output: t1.c1, t2."C 1"
399+
Inner Unique: true
399400
Merge Cond: (t1.c1 = t2."C 1")
400401
-> Foreign Scan on public.ft2 t1
401402
Output: t1.c1
402403
Remote SQL: SELECT "C 1" FROM "S 1"."T 1" ORDER BY "C 1" ASC NULLS LAST
403404
-> Index Only Scan using t1_pkey on "S 1"."T 1" t2
404405
Output: t2."C 1"
405-
(10 rows)
406+
(11 rows)
406407

407408
SELECT t1.c1, t2."C 1" FROM ft2 t1 JOIN "S 1"."T 1" t2 ON (t1.c1 = t2."C 1") OFFSET 100 LIMIT 10;
408409
c1 | C 1
@@ -429,13 +430,14 @@ EXPLAIN (VERBOSE, COSTS OFF)
429430
Output: t1.c1, t2."C 1"
430431
-> Merge Left Join
431432
Output: t1.c1, t2."C 1"
433+
Inner Unique: true
432434
Merge Cond: (t1.c1 = t2."C 1")
433435
-> Foreign Scan on public.ft2 t1
434436
Output: t1.c1
435437
Remote SQL: SELECT "C 1" FROM "S 1"."T 1" ORDER BY "C 1" ASC NULLS LAST
436438
-> Index Only Scan using t1_pkey on "S 1"."T 1" t2
437439
Output: t2."C 1"
438-
(10 rows)
440+
(11 rows)
439441

440442
SELECT t1.c1, t2."C 1" FROM ft2 t1 LEFT JOIN "S 1"."T 1" t2 ON (t1.c1 = t2."C 1") OFFSET 100 LIMIT 10;
441443
c1 | C 1
@@ -462,14 +464,15 @@ EXPLAIN (VERBOSE, COSTS OFF)
462464
Output: t1."C 1"
463465
-> Merge Right Join
464466
Output: t1."C 1"
467+
Inner Unique: true
465468
Merge Cond: (t3.c1 = t1."C 1")
466469
-> Foreign Scan
467470
Output: t3.c1
468471
Relations: (public.ft1 t2) INNER JOIN (public.ft2 t3)
469472
Remote SQL: SELECT r3."C 1" FROM ("S 1"."T 1" r2 INNER JOIN "S 1"."T 1" r3 ON (((r2."C 1" = r3."C 1")))) ORDER BY r2."C 1" ASC NULLS LAST
470473
-> Index Only Scan using t1_pkey on "S 1"."T 1" t1
471474
Output: t1."C 1"
472-
(11 rows)
475+
(12 rows)
473476

474477
SELECT t1."C 1" FROM "S 1"."T 1" t1 left join ft1 t2 join ft2 t3 on (t2.c1 = t3.c1) on (t3.c1 = t1."C 1") OFFSET 100 LIMIT 10;
475478
C 1
@@ -497,14 +500,15 @@ EXPLAIN (VERBOSE, COSTS OFF)
497500
Output: t1."C 1", t2.c1, t3.c1
498501
-> Merge Right Join
499502
Output: t1."C 1", t2.c1, t3.c1
503+
Inner Unique: true
500504
Merge Cond: (t3.c1 = t1."C 1")
501505
-> Foreign Scan
502506
Output: t3.c1, t2.c1
503507
Relations: (public.ft2 t3) LEFT JOIN (public.ft1 t2)
504508
Remote SQL: SELECT r3."C 1", r2."C 1" FROM ("S 1"."T 1" r3 LEFT JOIN "S 1"."T 1" r2 ON (((r2."C 1" = r3."C 1")))) ORDER BY r3."C 1" ASC NULLS LAST
505509
-> Index Only Scan using t1_pkey on "S 1"."T 1" t1
506510
Output: t1."C 1"
507-
(11 rows)
511+
(12 rows)
508512

509513
SELECT t1."C 1", t2.c1, t3.c1 FROM "S 1"."T 1" t1 left join ft1 t2 full join ft2 t3 on (t2.c1 = t3.c1) on (t3.c1 = t1."C 1") OFFSET 100 LIMIT 10;
510514
C 1 | c1 | c1
@@ -530,14 +534,15 @@ EXPLAIN (VERBOSE, COSTS OFF)
530534
Output: t1."C 1", t2.c1, t3.c1
531535
-> Merge Full Join
532536
Output: t1."C 1", t2.c1, t3.c1
537+
Inner Unique: true
533538
Merge Cond: (t3.c1 = t1."C 1")
534539
-> Foreign Scan
535540
Output: t2.c1, t3.c1
536541
Relations: (public.ft1 t2) FULL JOIN (public.ft2 t3)
537542
Remote SQL: SELECT r2."C 1", r3."C 1" FROM ("S 1"."T 1" r2 FULL JOIN "S 1"."T 1" r3 ON (((r2."C 1" = r3."C 1")))) ORDER BY r3."C 1" ASC NULLS LAST
538543
-> Index Only Scan using t1_pkey on "S 1"."T 1" t1
539544
Output: t1."C 1"
540-
(11 rows)
545+
(12 rows)
541546

542547
SELECT t1."C 1", t2.c1, t3.c1 FROM "S 1"."T 1" t1 full join ft1 t2 full join ft2 t3 on (t2.c1 = t3.c1) on (t3.c1 = t1."C 1") OFFSET 100 LIMIT 10;
543548
C 1 | c1 | c1
@@ -1844,8 +1849,8 @@ SELECT t1.ctid, t1, t2, t1.c1 FROM ft1 t1 JOIN ft2 t2 ON (t1.c1 = t2.c1) ORDER B
18441849
-- SEMI JOIN, not pushed down
18451850
EXPLAIN (VERBOSE, COSTS OFF)
18461851
SELECT t1.c1 FROM ft1 t1 WHERE EXISTS (SELECT 1 FROM ft2 t2 WHERE t1.c1 = t2.c1) ORDER BY t1.c1 OFFSET 100 LIMIT 10;
1847-
QUERY PLAN
1848-
---------------------------------------------------------------------------------------------
1852+
QUERY PLAN
1853+
---------------------------------------------------------------------------------------
18491854
Limit
18501855
Output: t1.c1
18511856
-> Merge Semi Join
@@ -1854,12 +1859,10 @@ SELECT t1.c1 FROM ft1 t1 WHERE EXISTS (SELECT 1 FROM ft2 t2 WHERE t1.c1 = t2.c1)
18541859
-> Foreign Scan on public.ft1 t1
18551860
Output: t1.c1
18561861
Remote SQL: SELECT "C 1" FROM "S 1"."T 1" ORDER BY "C 1" ASC NULLS LAST
1857-
-> Materialize
1862+
-> Foreign Scan on public.ft2 t2
18581863
Output: t2.c1
1859-
-> Foreign Scan on public.ft2 t2
1860-
Output: t2.c1
1861-
Remote SQL: SELECT "C 1" FROM "S 1"."T 1" ORDER BY "C 1" ASC NULLS LAST
1862-
(13 rows)
1864+
Remote SQL: SELECT "C 1" FROM "S 1"."T 1" ORDER BY "C 1" ASC NULLS LAST
1865+
(11 rows)
18631866

18641867
SELECT t1.c1 FROM ft1 t1 WHERE EXISTS (SELECT 1 FROM ft2 t2 WHERE t1.c1 = t2.c1) ORDER BY t1.c1 OFFSET 100 LIMIT 10;
18651868
c1
@@ -1889,12 +1892,10 @@ SELECT t1.c1 FROM ft1 t1 WHERE NOT EXISTS (SELECT 1 FROM ft2 t2 WHERE t1.c1 = t2
18891892
-> Foreign Scan on public.ft1 t1
18901893
Output: t1.c1
18911894
Remote SQL: SELECT "C 1" FROM "S 1"."T 1" ORDER BY "C 1" ASC NULLS LAST
1892-
-> Materialize
1895+
-> Foreign Scan on public.ft2 t2
18931896
Output: t2.c2
1894-
-> Foreign Scan on public.ft2 t2
1895-
Output: t2.c2
1896-
Remote SQL: SELECT c2 FROM "S 1"."T 1" ORDER BY c2 ASC NULLS LAST
1897-
(13 rows)
1897+
Remote SQL: SELECT c2 FROM "S 1"."T 1" ORDER BY c2 ASC NULLS LAST
1898+
(11 rows)
18981899

18991900
SELECT t1.c1 FROM ft1 t1 WHERE NOT EXISTS (SELECT 1 FROM ft2 t2 WHERE t1.c1 = t2.c2) ORDER BY t1.c1 OFFSET 100 LIMIT 10;
19001901
c1
@@ -3121,6 +3122,7 @@ select count(*), x.b from ft1, (select c2 a, sum(c1) b from ft1 group by c2) x w
31213122
Group Key: x.b
31223123
-> Hash Join
31233124
Output: x.b
3125+
Inner Unique: true
31243126
Hash Cond: (ft1.c2 = x.a)
31253127
-> Foreign Scan on public.ft1
31263128
Output: ft1.c2
@@ -3133,7 +3135,7 @@ select count(*), x.b from ft1, (select c2 a, sum(c1) b from ft1 group by c2) x w
31333135
Output: ft1_1.c2, (sum(ft1_1.c1))
31343136
Relations: Aggregate on (public.ft1)
31353137
Remote SQL: SELECT c2, sum("C 1") FROM "S 1"."T 1" GROUP BY c2
3136-
(20 rows)
3138+
(21 rows)
31373139

31383140
select count(*), x.b from ft1, (select c2 a, sum(c1) b from ft1 group by c2) x where ft1.c2 = x.a group by x.b order by 1, 2;
31393141
count | b
@@ -3252,6 +3254,7 @@ select sum(q.a), count(q.b) from ft4 left join (select 13, avg(ft1.c1), sum(ft2.
32523254
Output: sum(q.a), count(q.b)
32533255
-> Nested Loop Left Join
32543256
Output: q.a, q.b
3257+
Inner Unique: true
32553258
Join Filter: ((ft4.c1)::numeric <= q.b)
32563259
-> Foreign Scan on public.ft4
32573260
Output: ft4.c1, ft4.c2, ft4.c3
@@ -3264,7 +3267,7 @@ select sum(q.a), count(q.b) from ft4 left join (select 13, avg(ft1.c1), sum(ft2.
32643267
Output: 13, (avg(ft1.c1)), NULL::bigint
32653268
Relations: Aggregate on ((public.ft2) LEFT JOIN (public.ft1))
32663269
Remote SQL: SELECT 13, avg(r1."C 1"), NULL::bigint FROM ("S 1"."T 1" r2 LEFT JOIN "S 1"."T 1" r1 ON (((r1."C 1" = r2."C 1"))))
3267-
(16 rows)
3270+
(17 rows)
32683271

32693272
select sum(q.a), count(q.b) from ft4 left join (select 13, avg(ft1.c1), sum(ft2.c1) from ft1 right join ft2 on (ft1.c1 = ft2.c1)) q(a, b, c) on (ft4.c1 <= q.b);
32703273
sum | count
@@ -4048,20 +4051,18 @@ explain (verbose, costs off) select * from ft3 where f2 = 'foo' COLLATE "C";
40484051

40494052
explain (verbose, costs off) select * from ft3 f, loct3 l
40504053
where f.f3 = l.f3 COLLATE "POSIX" and l.f1 = 'foo';
4051-
QUERY PLAN
4052-
-------------------------------------------------------------
4053-
Hash Join
4054+
QUERY PLAN
4055+
---------------------------------------------------------
4056+
Nested Loop
40544057
Output: f.f1, f.f2, f.f3, l.f1, l.f2, l.f3
4055-
Hash Cond: ((f.f3)::text = (l.f3)::text)
4058+
Join Filter: ((f.f3)::text = (l.f3)::text)
4059+
-> Index Scan using loct3_f1_key on public.loct3 l
4060+
Output: l.f1, l.f2, l.f3
4061+
Index Cond: (l.f1 = 'foo'::text)
40564062
-> Foreign Scan on public.ft3 f
40574063
Output: f.f1, f.f2, f.f3
40584064
Remote SQL: SELECT f1, f2, f3 FROM public.loct3
4059-
-> Hash
4060-
Output: l.f1, l.f2, l.f3
4061-
-> Index Scan using loct3_f1_key on public.loct3 l
4062-
Output: l.f1, l.f2, l.f3
4063-
Index Cond: (l.f1 = 'foo'::text)
4064-
(11 rows)
4065+
(9 rows)
40654066

40664067
-- ===================================================================
40674068
-- test writable foreign table stuff
@@ -6541,6 +6542,7 @@ select * from bar where f1 in (select f1 from foo) for update;
65416542
Output: bar.f1, bar.f2, bar.ctid, bar.*, bar.tableoid, foo.ctid, foo.*, foo.tableoid
65426543
-> Hash Join
65436544
Output: bar.f1, bar.f2, bar.ctid, bar.*, bar.tableoid, foo.ctid, foo.*, foo.tableoid
6545+
Inner Unique: true
65446546
Hash Cond: (bar.f1 = foo.f1)
65456547
-> Append
65466548
-> Seq Scan on public.bar
@@ -6559,7 +6561,7 @@ select * from bar where f1 in (select f1 from foo) for update;
65596561
-> Foreign Scan on public.foo2
65606562
Output: foo2.ctid, foo2.*, foo2.tableoid, foo2.f1
65616563
Remote SQL: SELECT f1, f2, f3, ctid FROM public.loct1
6562-
(22 rows)
6564+
(23 rows)
65636565

65646566
select * from bar where f1 in (select f1 from foo) for update;
65656567
f1 | f2
@@ -6578,6 +6580,7 @@ select * from bar where f1 in (select f1 from foo) for share;
65786580
Output: bar.f1, bar.f2, bar.ctid, bar.*, bar.tableoid, foo.ctid, foo.*, foo.tableoid
65796581
-> Hash Join
65806582
Output: bar.f1, bar.f2, bar.ctid, bar.*, bar.tableoid, foo.ctid, foo.*, foo.tableoid
6583+
Inner Unique: true
65816584
Hash Cond: (bar.f1 = foo.f1)
65826585
-> Append
65836586
-> Seq Scan on public.bar
@@ -6596,7 +6599,7 @@ select * from bar where f1 in (select f1 from foo) for share;
65966599
-> Foreign Scan on public.foo2
65976600
Output: foo2.ctid, foo2.*, foo2.tableoid, foo2.f1
65986601
Remote SQL: SELECT f1, f2, f3, ctid FROM public.loct1
6599-
(22 rows)
6602+
(23 rows)
66006603

66016604
select * from bar where f1 in (select f1 from foo) for share;
66026605
f1 | f2
@@ -6618,6 +6621,7 @@ update bar set f2 = f2 + 100 where f1 in (select f1 from foo);
66186621
Remote SQL: UPDATE public.loct2 SET f2 = $2 WHERE ctid = $1
66196622
-> Hash Join
66206623
Output: bar.f1, (bar.f2 + 100), bar.ctid, foo.ctid, foo.*, foo.tableoid
6624+
Inner Unique: true
66216625
Hash Cond: (bar.f1 = foo.f1)
66226626
-> Seq Scan on public.bar
66236627
Output: bar.f1, bar.f2, bar.ctid
@@ -6634,6 +6638,7 @@ update bar set f2 = f2 + 100 where f1 in (select f1 from foo);
66346638
Remote SQL: SELECT f1, f2, f3, ctid FROM public.loct1
66356639
-> Hash Join
66366640
Output: bar2.f1, (bar2.f2 + 100), bar2.f3, bar2.ctid, foo.ctid, foo.*, foo.tableoid
6641+
Inner Unique: true
66376642
Hash Cond: (bar2.f1 = foo.f1)
66386643
-> Foreign Scan on public.bar2
66396644
Output: bar2.f1, bar2.f2, bar2.f3, bar2.ctid
@@ -6649,7 +6654,7 @@ update bar set f2 = f2 + 100 where f1 in (select f1 from foo);
66496654
-> Foreign Scan on public.foo2
66506655
Output: foo2.ctid, foo2.*, foo2.tableoid, foo2.f1
66516656
Remote SQL: SELECT f1, f2, f3, ctid FROM public.loct1
6652-
(37 rows)
6657+
(39 rows)
66536658

66546659
update bar set f2 = f2 + 100 where f1 in (select f1 from foo);
66556660
select tableoid::regclass, * from bar order by 1,2;

‎src/backend/commands/explain.c

+17
Original file line numberDiff line numberDiff line change
@@ -1343,6 +1343,23 @@ ExplainNode(PlanState *planstate, List *ancestors,
13431343
if (es->verbose)
13441344
show_plan_tlist(planstate, ancestors, es);
13451345

1346+
/* unique join */
1347+
switch (nodeTag(plan))
1348+
{
1349+
case T_NestLoop:
1350+
case T_MergeJoin:
1351+
case T_HashJoin:
1352+
/* try not to be too chatty about this in text mode */
1353+
if (es->format != EXPLAIN_FORMAT_TEXT ||
1354+
(es->verbose && ((Join *) plan)->inner_unique))
1355+
ExplainPropertyBool("Inner Unique",
1356+
((Join *) plan)->inner_unique,
1357+
es);
1358+
break;
1359+
default:
1360+
break;
1361+
}
1362+
13461363
/* quals, sort keys, etc */
13471364
switch (nodeTag(plan))
13481365
{

‎src/backend/executor/nodeHashjoin.c

+10-3
Original file line numberDiff line numberDiff line change
@@ -288,10 +288,11 @@ ExecHashJoin(HashJoinState *node)
288288
}
289289

290290
/*
291-
* In a semijoin, we'll consider returning the first
292-
* match, but after that we're done with this outer tuple.
291+
* If we only need to join to the first matching inner
292+
* tuple, then consider returning this one, but after that
293+
* continue with next outer tuple.
293294
*/
294-
if (node->js.jointype == JOIN_SEMI)
295+
if (node->js.single_match)
295296
node->hj_JoinState = HJ_NEED_NEW_OUTER;
296297

297298
if (otherqual == NULL || ExecQual(otherqual, econtext))
@@ -435,6 +436,12 @@ ExecInitHashJoin(HashJoin *node, EState *estate, int eflags)
435436
ExecInitResultTupleSlot(estate, &hjstate->js.ps);
436437
hjstate->hj_OuterTupleSlot = ExecInitExtraTupleSlot(estate);
437438

439+
/*
440+
* detect whether we need only consider the first matching inner tuple
441+
*/
442+
hjstate->js.single_match = (node->join.inner_unique ||
443+
node->join.jointype == JOIN_SEMI);
444+
438445
/* set up null tuples for outer joins, if needed */
439446
switch (node->join.jointype)
440447
{

0 commit comments

Comments
 (0)