Thread: Nested loop does not preserve order. Why?

Nested loop does not preserve order. Why?

From
Alexey Bashtanov
Date:
Hello!

Let us have a table T(A, B), an index on T(B, A) and a much smaller
table V(B).

stat-dev1/ui_dev_16 12:27:07 > create table u as select a, a % 1000 b
from generate_series(1, 10000000) a;
SELECT 10000000
stat-dev1/ui_dev_16 12:27:28 > create table v as select distinct b from
u where b % 100 = 1;
SELECT 10
stat-dev1/ui_dev_16 12:27:41 > analyze t;
ANALYZE
stat-dev1/ui_dev_16 12:27:42 > analyze v;
ANALYZE
stat-dev1/ui_dev_16 12:27:45 > create index u_i on u(b,a);
CREATE INDEX

And we are looking for all rows of T that have B present in V and sorted
by B, A.
The most natural way to obtain them would be to take all records from V
ordered by B, and to perform an index-only scan on T for each B.
But not for postgresql :(

stat-dev1/ui_dev_16 12:28:57 > EXPLAIN ANALYZE select b, a from u where
b in (select b from v) order by b, a;
                                                          QUERY PLAN

-----------------------------------------------------------------------------------------------------------------------------
  Sort  (cost=879810.77..892310.77 rows=5000000 width=8) (actual
time=4728.831..4756.802 rows=100000 loops=1)
    Sort Key: u.b, u.a
    Sort Method: external merge  Disk: 1760kB
    ->  Hash Join  (cost=1.35..186749.35 rows=5000000 width=8) (actual
time=0.121..4568.170 rows=100000 loops=1)
          Hash Cond: (u.b = v.b)
          ->  Seq Scan on u  (cost=0.00..144248.00 rows=10000000
width=8) (actual time=0.027..2294.474 rows=10000000 loops=1)
          ->  Hash  (cost=1.23..1.23 rows=10 width=4) (actual
time=0.071..0.071 rows=10 loops=1)
                Buckets: 1024  Batches: 1  Memory Usage: 1kB
                ->  HashAggregate  (cost=1.12..1.23 rows=10 width=4)
(actual time=0.062..0.063 rows=10 loops=1)
                      ->  Seq Scan on v  (cost=0.00..1.10 rows=10
width=4) (actual time=0.050..0.052 rows=10 loops=1)
  Total runtime: 4771.817 ms
(11 rows)

Replacing IN by EXISTS changes nothing. Putting an ORDER BY clause into
IN(...) unsurprisingly does not help.
The only way to obtain the desired plan I found is to rewrite the query:

stat-dev1/ui_dev_16 12:29:06 > set enable_bitmapscan to off;
SET
stat-dev1/ui_dev_16 12:29:11 > set enable_seqscan to off;
SET
stat-dev1/ui_dev_16 12:29:13 > EXPLAIN ANALYZE select b, a from u where
b = any((select array_agg(b) from v)::int[]) order by b, a;
QUERY PLAN

-------------------------------------------------------------------------------------------------------------------------------------------
  Index Only Scan using u_i on u (cost=10000000001.58..10000315253.45
rows=99551 width=8) (actual time=0.078..103.239 rows=100000 loops=1)
    Index Cond: (b = ANY ($0))
    Heap Fetches: 100000
    InitPlan 1 (returns $0)
      ->  Aggregate  (cost=10000000001.13..10000000001.14 rows=1
width=4) (actual time=0.018..0.018 rows=1 loops=1)
            ->  Seq Scan on v (cost=10000000000.00..10000000001.10
rows=10 width=4) (actual time=0.006..0.009 rows=10 loops=1)
  Total runtime: 119.929 ms
(7 rows)

The plan I expect for the original query is something like that:

   Nested Loop Preserving Order (cost=1.85..317895.69 rows=100000 width=8)
     ->  HashAggregate  (cost=1.42..1.52 rows=10 width=4)
           ->  Sort  (cost=1.27..1.29 rows=10 width=4)
                 Sort Key: v.b
                 ->  Seq Scan on v  (cost=0.00..1.10 rows=10 width=4)
     ->  Index Only Scan using u_i on u  (cost=0.43..31689.42 rows=10000
width=8)
           Index Cond: (b = v.b)

But if we try to hint postgresql we will realize that nested loop does
not preserve order (see below). Why?

stat-dev1/ui_dev_16 12:42:32 > set enable_bitmapscan to off;
SET
Time: 0,895 ms
stat-dev1/ui_dev_16 12:42:33 > set enable_hashjoin to off;
SET
Time: 0,762 ms
stat-dev1/ui_dev_16 12:42:36 > EXPLAIN select b, a from u where b in
(select b from v order by b) order by b, a;
                                       QUERY PLAN
--------------------------------------------------------------------------------------
  Sort  (cost=326200.51..326450.51 rows=100000 width=8)
    Sort Key: u.b, u.a
    ->  Nested Loop  (cost=1.85..317895.69 rows=100000 width=8)
          ->  HashAggregate  (cost=1.42..1.52 rows=10 width=4)
                ->  Sort  (cost=1.27..1.29 rows=10 width=4)
                      Sort Key: v.b
                      ->  Seq Scan on v  (cost=0.00..1.10 rows=10 width=4)
          ->  Index Only Scan using u_i on u  (cost=0.43..31689.42
rows=10000 width=8)
                Index Cond: (b = v.b)
(9 rows)

Re: Nested loop does not preserve order. Why?

From
Tom Lane
Date:
Alexey Bashtanov <bashtanov@imap.cc> writes:
> Let us have a table T(A, B), an index on T(B, A) and a much smaller
> table V(B).
> And we are looking for all rows of T that have B present in V and sorted
> by B, A.
> The most natural way to obtain them would be to take all records from V
> ordered by B, and to perform an index-only scan on T for each B.
> But not for postgresql :(

AFAICS, what you're wishing is that given a plan like

    nestloop
      Join condition: x = y
      -> path ordered by x
      -> path ordered by y, z

the planner would realize that the output of the nestloop is ordered
by y,z.  Right now it only realizes that the output is ordered by x
(and hence also by y); this means it thinks it needs an additional
sort step.

As stated, though, this deduction about ordering is false.  To make it
true, you need the additional assumption that the outer relation is
unique in x (plus assumptions about the equality operators in question
all being compatible with the sort ordering).

Right now, the planner doesn't really track uniqueness so there's
no practical way to do this.  There's a patch in the current commitfest
that wants to add tracking of unique sort orders, so if that gets in
we might have appropriate infrastructure.  But even then, this seems
like a mighty narrow and unusual corner case; I can't recall ever
seeing a request for such behavior before.  So I doubt we'd do it
unless the deduction turns out to be basically free, which seems
unlikely.

Having said that, there does seem to be something fishy going on
here.  If I add an index on v.b to your example, and drop the
explicit request to sort on a, I can get this:

EXPLAIN select b, a from u where
b in (select b from v) order by b;
                                          QUERY PLAN
-----------------------------------------------------------------------------------------------
 Sort  (cost=13802.17..14052.17 rows=100000 width=8)
   Sort Key: u.b
   ->  Nested Loop  (cost=8.89..4128.85 rows=100000 width=8)
         ->  Unique  (cost=8.45..8.50 rows=10 width=4)
               ->  Sort  (cost=8.45..8.48 rows=10 width=4)
                     Sort Key: v.b
                     ->  Index Only Scan using v_b_idx on v  (cost=0.14..8.29 rows=10 width=4)
         ->  Index Only Scan using u_i on u  (cost=0.43..312.04 rows=10000 width=8)
               Index Cond: (b = v.b)
 Planning time: 0.481 ms
(10 rows)

I'd have expected the planner to realize that neither of
those sort steps are necessary.  Will investigate.

            regards, tom lane