Обсуждение: BUG #18060: Left joining rows using random() function in join condition doesn't work as expected.

The following bug has been logged on the website:

Bug reference:      18060
Logged by:          James Inform
Email address:      james.inform@pharmapp.de
PostgreSQL version: 15.4
Operating system:   Linux and Mac
Description:

/*
    PostgreSQL 14.9 / 15.4 on Linux and Mac
    
    Left joining rows using random() function in join condition
    doesn't work as expected.
   
   
    I have encountered this while I was trying randomly left join a record
of a source table
    with exactly with one record of a link table.
    
    Just execute the create statements under 1.
    
    Then execute the select under 2. multiple times and watch thee
results.
 */

-- 1. Generate two tables (source and link) with 1000 rows having gapless
ids
create temp table source as
select source_id, 'source' as source_name from generate_series(1,1000) as
source_id
;

create temp table link as
select link_id, 'link' as link_name from generate_series(1,1000) as
link_id
;

-- 2. Execute this query multiple time and you will see results where:
-- * no rows from link are joined
-- * extactly one row is joined
-- * multiple rows are joined

select * from source left join link on link_id = 1 + (random()*500)::int8
order by 1

/*
I would expect always exactly one row to be joined. 
Instead I get 1, none or multiple.

Is this an error or am I doing something wrong?
*/

PG Bug reporting form <noreply@postgresql.org> writes:
> -- 2. Execute this query multiple time and you will see results where:
> -- * no rows from link are joined
> -- * extactly one row is joined
> -- * multiple rows are joined

> select * from source left join link on link_id = 1 + (random()*500)::int8
> order by 1

> /*
> I would expect always exactly one row to be joined. 
> Instead I get 1, none or multiple.

I see no bug here: instead, your expectation is faulty.  The
given join condition is unstable by definition, but it would
have to be at least stable to produce the results you expect.

Formally, the definition of a SQL join is "evaluate the join's ON
condition for each pair of rows in the cross product of the two
input relations, and return the row pair(s) that satisfy the ON".
So with a random() join condition, anywhere from none to all of
the join pairs involving a given LHS row might get returned,
because the random() function will produce a different value
for each join pair.

You could shove the random() call into a materialized CTE if
the semantics you want are that a single random() result is
used across the entire query.  If you want one random() result
to be used for all join pairs involving a given LHS row, but
different ones for different LHS rows, you could probably
make that happen with some hack involving LATERAL.  But I'm
too lazy to work it out for you.

            regards, tom lane

That explains the behavior.

I thought that the random() was "executed" one time per row, but that is 
not the case.

So, thanks for your quick response.


PG Bug reporting form <noreply@postgresql.org> writes:
>> -- 2. Execute this query multiple time and you will see results where:
>> -- * no rows from link are joined
>> -- * extactly one row is joined
>> -- * multiple rows are joined
>> select * from source left join link on link_id = 1 + (random()*500)::int8
>> order by 1
>> /*
>> I would expect always exactly one row to be joined.
>> Instead I get 1, none or multiple.
> I see no bug here: instead, your expectation is faulty.  The
> given join condition is unstable by definition, but it would
> have to be at least stable to produce the results you expect.
>
> Formally, the definition of a SQL join is "evaluate the join's ON
> condition for each pair of rows in the cross product of the two
> input relations, and return the row pair(s) that satisfy the ON".
> So with a random() join condition, anywhere from none to all of
> the join pairs involving a given LHS row might get returned,
> because the random() function will produce a different value
> for each join pair.
>
> You could shove the random() call into a materialized CTE if
> the semantics you want are that a single random() result is
> used across the entire query.  If you want one random() result
> to be used for all join pairs involving a given LHS row, but
> different ones for different LHS rows, you could probably
> make that happen with some hack involving LATERAL.  But I'm
> too lazy to work it out for you.
>
>             regards, tom lane

Just looked at the results again.

They look strange. When I execute the query multiple times I get three 
kinds of results:
- NO match on all columns
- THE SAME match on all columns
- THREE DIFFERENT columns that are repeated for all the 1000 rows.

With your explanation there should be randomly assigned rows appearing, 
but the seems to be a pattern. At least more than those three different 
ones.

Have you executed my example and looked at the results?
If not, please give it a try. Nothing looks random there.

> PG Bug reporting form <noreply@postgresql.org> writes:
>> -- 2. Execute this query multiple time and you will see results where:
>> -- * no rows from link are joined
>> -- * extactly one row is joined
>> -- * multiple rows are joined
>> select * from source left join link on link_id = 1 + (random()*500)::int8
>> order by 1
>> /*
>> I would expect always exactly one row to be joined.
>> Instead I get 1, none or multiple.
> I see no bug here: instead, your expectation is faulty.  The
> given join condition is unstable by definition, but it would
> have to be at least stable to produce the results you expect.
>
> Formally, the definition of a SQL join is "evaluate the join's ON
> condition for each pair of rows in the cross product of the two
> input relations, and return the row pair(s) that satisfy the ON".
> So with a random() join condition, anywhere from none to all of
> the join pairs involving a given LHS row might get returned,
> because the random() function will produce a different value
> for each join pair.
>
> You could shove the random() call into a materialized CTE if
> the semantics you want are that a single random() result is
> used across the entire query.  If you want one random() result
> to be used for all join pairs involving a given LHS row, but
> different ones for different LHS rows, you could probably
> make that happen with some hack involving LATERAL.  But I'm
> too lazy to work it out for you.
>
>             regards, tom lane

On Mon, 21 Aug 2023 at 06:26, James Inform <james.inform@pharmapp.de> wrote:
>
> Just looked at the results again.
>
> They look strange. When I execute the query multiple times I get three
> kinds of results:
> - NO match on all columns
> - THE SAME match on all columns
> - THREE DIFFERENT columns that are repeated for all the 1000 rows.
>
> With your explanation there should be randomly assigned rows appearing,
> but the seems to be a pattern. At least more than those three different
> ones.
>
> Have you executed my example and looked at the results?
> If not, please give it a try. Nothing looks random there.

You might expect that the "link_id = 1 + (random()*500)::int8" is
evaluated as a join qual because you put it in the ON clause, but
PostgreSQL will distribute these quals to the lowest location that
they can be evaluated. Since the only column that's mentioned in your
join expression belongs to the "link" table, then the qual is
evaluated at the scan level for that relation. You'll notice this if
you look at the EXPLAIN output.

The reason you sometimes get no matches is simply that on that
execution of the query, the random number didn't happen to line up
with any of the particular link_ids on any of the scanned tuples.

The reason you sometimes get the same match is that 1 tuple happened
to match the random number during the scan, and that tuple was joined
to 1000 times on your effective clauseless join.

The reason you see three different columns being matches it is that 3
tuples happened to match your random expression during the scan and
the clauseless join joined all three, resulting in 3000 rows rather
than 1000 rows in the final output.

The link table is only scanned once due to the Material node in the
Nested Loop join.  If you did: SET enable_material = off; then the
scan would be performed once per row in the "source" table.  That
would mean the random() function would be executed 1 million times
instead of 1 thousand times.

It might take you a while, but if you tried enough times, all the
planets would align and "link_id = 1 + (random()*500)::int8" would
happen to match all tuples during the scan.  The query would then
return 1 million rows.

PostgreSQL wouldn't have pushed your ON qual down to the scan level if
you'd included some column from the "source" table in the expression.
I'm not sure what good it'd do you, but you'd see different results
using something like "link_id = source_id * 0 + 1 +
(random()*5)::int8" (note the multiplication by 0)

David

Thank you David for this detailled explanation.

Makes things very clear.


David Rowley schrieb am 20.08.23 um 23:04:
> On Mon, 21 Aug 2023 at 06:26, James Inform <james.inform@pharmapp.de> wrote:
>> Just looked at the results again.
>>
>> They look strange. When I execute the query multiple times I get three
>> kinds of results:
>> - NO match on all columns
>> - THE SAME match on all columns
>> - THREE DIFFERENT columns that are repeated for all the 1000 rows.
>>
>> With your explanation there should be randomly assigned rows appearing,
>> but the seems to be a pattern. At least more than those three different
>> ones.
>>
>> Have you executed my example and looked at the results?
>> If not, please give it a try. Nothing looks random there.
> You might expect that the "link_id = 1 + (random()*500)::int8" is
> evaluated as a join qual because you put it in the ON clause, but
> PostgreSQL will distribute these quals to the lowest location that
> they can be evaluated. Since the only column that's mentioned in your
> join expression belongs to the "link" table, then the qual is
> evaluated at the scan level for that relation. You'll notice this if
> you look at the EXPLAIN output.
>
> The reason you sometimes get no matches is simply that on that
> execution of the query, the random number didn't happen to line up
> with any of the particular link_ids on any of the scanned tuples.
>
> The reason you sometimes get the same match is that 1 tuple happened
> to match the random number during the scan, and that tuple was joined
> to 1000 times on your effective clauseless join.
>
> The reason you see three different columns being matches it is that 3
> tuples happened to match your random expression during the scan and
> the clauseless join joined all three, resulting in 3000 rows rather
> than 1000 rows in the final output.
>
> The link table is only scanned once due to the Material node in the
> Nested Loop join.  If you did: SET enable_material = off; then the
> scan would be performed once per row in the "source" table.  That
> would mean the random() function would be executed 1 million times
> instead of 1 thousand times.
>
> It might take you a while, but if you tried enough times, all the
> planets would align and "link_id = 1 + (random()*500)::int8" would
> happen to match all tuples during the scan.  The query would then
> return 1 million rows.
>
> PostgreSQL wouldn't have pushed your ON qual down to the scan level if
> you'd included some column from the "source" table in the expression.
> I'm not sure what good it'd do you, but you'd see different results
> using something like "link_id = source_id * 0 + 1 +
> (random()*5)::int8" (note the multiplication by 0)
>
> David