Re: BUG #15007: LIMIT not respected in sub-queries

On Thu 2018-01-18 00:08:31 +0100, Tomas Vondra wrote:

<snip>

> I went through the test case, and I think I know what's going on. The
> script did not reproduce the issue for me, but I think I've been able to
> tweak the query to use a plan producing more issues.
> 
> The key is to force a particular join order, and disable operations that
> would materialize intermediate results of the t1 scan. That is, we want
> something like this:
> 
>    -> nestloop
>        -> nestloop t2 + t3
>        -> seq scan t1
> 
> Firstly, I've replaced the dynamic random() condition with a static one:
> 
>     random() <= 0.5
> 
> this is not strictly necessary, but it simplifies the plan. We need the
> random() call though, as I'll explain later.
> 
> Then I've disabled a bunch of plan nodes that would materialize results
> of the t1 seq scan:
> 
>     set enable_material = off;
>     set enable_sort = off;
>     set enable_hashjoin = off;
> 
> And finally, I've disabled join reordering by setting
> 
>     set join_collapse_limit = 1;
> 
> Now, if you rewrite the query like this (which essentially just forces a
> particular join order, when combined with join_collapse_limit=1, nothing
> else):
> 
> explain analyze SELECT * FROM
> (t3 JOIN t2 USING (t2_id)) JOIN
> (SELECT * FROM t1
>  WHERE t1_id IS NOT NULL AND
>  t1_id < 100 AND
>  t1_val LIKE 'h%' AND
>  random() <= 0.5
>  LIMIT 5
> ) AS t1
> ON t3.t1_id = t1.t1_id
> WHERE t2.t2_val LIKE 'he%';
> 
> you will get plans like this:
> 
> 
>                               QUERY PLAN
> ------------------------------------------------------------------------
>  Nested Loop  (cost=0.00..31.41 rows=5 width=21)
>               (actual time=0.052..1.825 rows=7 loops=1)
>    Join Filter: (t3.t1_id = t1.t1_id)
>    Rows Removed by Join Filter: 73
>    ->  Nested Loop  (cost=0.00..16.10 rows=16 width=14)
>                     (actual time=0.030..0.917 rows=16 loops=1)
>          Join Filter: (t3.t2_id = t2.t2_id)
>          Rows Removed by Join Filter: 160
>          ->  Seq Scan on t2  (cost=0.00..1.14 rows=11 width=10)
>                              (actual time=0.015..0.041 rows=11 loops=1)
>                Filter: ((t2_val)::text ~~ 'he%'::text)
>          ->  Seq Scan on t3  (cost=0.00..1.16 rows=16 width=8)
>                              (actual time=0.003..0.037 rows=16 loops=11)
>    ->  Limit  (cost=0.00..0.84 rows=5 width=7)
>               (actual time=0.008..0.037 rows=5 loops=16)
>          ->  Seq Scan on t1  (cost=0.00..1.52 rows=9 width=7)
>                              (actual time=0.004..0.016 rows=5 loops=16)
>                Filter: ((t1_id IS NOT NULL) AND (t1_id < 100) AND
>                         ((t1_val)::text ~~ 'h%'::text) AND
>                          (random() <= '0.5'::double precision))
>                Rows Removed by Filter: 5
>  Planning time: 0.625 ms
>  Execution time: 1.911 ms
> (15 rows)
> 
> 
> This should be equivalent to the original query, and should produce the
> same results (modulo random() of course).
> 
> But notice it actually does produce 7 rows!
> 
>  Nested Loop  (cost=0.00..31.41 rows=5 width=21)
>               (actual time=0.052..1.825 rows=7 loops=1)
>                                              ^
> 
> The problem is that it ends up executing the sequential scan on t1
> repeatedly (because it's the inner relation in a nested loop), and
> because random() is volatile, the results of the scan are likely different.
> 
> Each rescan individually still respects the LIMIT, but when combined
> result may be larger - there may be more unique IDs, matching additional
> rows from the other tables.
> 
> > 
> > I believe a better way to write this query would be to use a CTE.
> > 
> 
> Yes, that will stabilize the output of the random() function,
> eliminating the nondeterminism during rescans.

Wow, thank you for the great explanation of what is going on!

It sounds like this is not really a bug then and is just something to be
expected when using LIMIT with such volatile joins.

I suppose I expected that if there is a LIMIT then that would be the
maximum number of rows the subquery would ever provide. The planner would
have to force materializing/stabilizing in such cases it sounds like. Maybe
that is not possible or not a good idea. It does seem like a pretty edge
case.

Thanks again!