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

On 01/19/2018 02:55 AM, Will Storey wrote:
> 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.
>

The volatile part here is not the join, but the random function during
rescans of a relation. But yeah, I don't think this qualifies as a bug.

>
> 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.
>

Yes, something like that would be necessary. I don't know how difficult
that would be, though.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services