BUG #16676: SELECT ... FETCH FIRST ROW WITH TIES FOR UPDATE SKIP LOCKED locks rows it doesn't return

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

BUG #16676: SELECT ... FETCH FIRST ROW WITH TIES FOR UPDATE SKIP LOCKED locks rows it doesn't return

PG Bug reporting form
The following bug has been logged on the website:

Bug reference:      16676
Logged by:          David Christensen
Email address:      [hidden email]
PostgreSQL version: 13.0
Operating system:   OS X
Description:        

Test case (found when demonstrating a queue mechanism for batches):

create table queue (id int generated always as identity, batch_id int not
null);

insert into queue (batch_id) values (1),(1),(2),(3);

postgres=# select * from queue;
 id | batch_id
----+----------
  1 |        1
  2 |        1
  3 |        2
  4 |        3
(4 rows)

-- backend 1:

postgres=# begin;
BEGIN
postgres=*# select * from queue order by batch_id fetch first row with ties
for update skip locked;
 id | batch_id
----+----------
  1 |        1
  2 |        1
(2 rows)

-- backend 2:

postgres=# select * from queue order by batch_id fetch first row with ties
for update skip locked;      
 id | batch_id
----+----------
  4 |        3
(1 row)

-- QED

As you can see, the row id 3 with batch_id 2 is not returned as would be
implied by the strict ordering and the skipped locks.  The working theory
here is the FETCH FIRST ROW WITH TIES locks the rows before deciding if they
should be included or not.

Reply | Threaded
Open this post in threaded view
|

Re: BUG #16676: SELECT ... FETCH FIRST ROW WITH TIES FOR UPDATE SKIP LOCKED locks rows it doesn't return

David Christensen
Proposed fix:


Reorder Limit/LockRows nodes to prevent locking extra tuples in FETCH FIRST WITH TIES

Reference bug report: 16676

1 file changed, 12 insertions(+), 12 deletions(-)
src/backend/optimizer/plan/planner.c | 24 ++++++++++++------------

modified   src/backend/optimizer/plan/planner.c
@@ -2293,6 +2293,18 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
  {
  Path   *path = (Path *) lfirst(lc);

+ /*
+ * If there is a LIMIT/OFFSET clause, add the LIMIT node.
+ */
+ if (limit_needed(parse))
+ {
+ path = (Path *) create_limit_path(root, final_rel, path,
+  parse->limitOffset,
+  parse->limitCount,
+  parse->limitOption,
+  offset_est, count_est);
+ }
+
  /*
  * If there is a FOR [KEY] UPDATE/SHARE clause, add the LockRows node.
  * (Note: we intentionally test parse->rowMarks not root->rowMarks
@@ -2307,18 +2319,6 @@ grouping_planner(PlannerInfo *root, bool inheritance_update,
  assign_special_exec_param(root));
  }

- /*
- * If there is a LIMIT/OFFSET clause, add the LIMIT node.
- */
- if (limit_needed(parse))
- {
- path = (Path *) create_limit_path(root, final_rel, path,
-  parse->limitOffset,
-  parse->limitCount,
-  parse->limitOption,
-  offset_est, count_est);
- }
-
  /*
  * If this is an INSERT/UPDATE/DELETE, and we're not being called from
  * inheritance_planner, add the ModifyTable node.



signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: BUG #16676: SELECT ... FETCH FIRST ROW WITH TIES FOR UPDATE SKIP LOCKED locks rows it doesn't return

Tom Lane-2
David Christensen <[hidden email]> writes:
> Proposed fix:
> Reorder Limit/LockRows nodes to prevent locking extra tuples in FETCH FIRST WITH TIES

Isn't that going to break more cases than it fixes?

                        regards, tom lane


Reply | Threaded
Open this post in threaded view
|

Re: BUG #16676: SELECT ... FETCH FIRST ROW WITH TIES FOR UPDATE SKIP LOCKED locks rows it doesn't return

David Christensen
> On Oct 19, 2020, at 6:07 PM, Tom Lane <[hidden email]> wrote:
>
> David Christensen <[hidden email]> writes:
>> Proposed fix:
>> Reorder Limit/LockRows nodes to prevent locking extra tuples in FETCH FIRST WITH TIES
>
> Isn't that going to break more cases than it fixes?

In the case of Limit, isn’t LockRows supposed to only lock the number of actual rows returned?

What are the scenarios that this might break and do you have any ideas for alternate fixes?

David

Reply | Threaded
Open this post in threaded view
|

Re: BUG #16676: SELECT ... FETCH FIRST ROW WITH TIES FOR UPDATE SKIP LOCKED locks rows it doesn't return

David Christensen
> On Oct 19, 2020, at 6:59 PM, David Christensen <[hidden email]> wrote:
>
>> On Oct 19, 2020, at 6:07 PM, Tom Lane <[hidden email]> wrote:
>>
>> David Christensen <[hidden email]> writes:
>>> Proposed fix:
>>> Reorder Limit/LockRows nodes to prevent locking extra tuples in FETCH FIRST WITH TIES
>>
>> Isn't that going to break more cases than it fixes?
>
> In the case of Limit, isn’t LockRows supposed to only lock the number of actual rows returned?
>
> What are the scenarios that this might break and do you have any ideas for alternate fixes?

Will now that I think about it, if the LockRows node is responsible for skipping locked rows, etc then my proposed solution is clearly wrong.

Maybe splitting LockRows into two nodes, one for locking and one for emitting unlocked nodes then interleaving Limit in between? (Or only doing something along these lines for this admittedly narrow use case. )

Open to ideas on the appropriate fix.

David

Reply | Threaded
Open this post in threaded view
|

Re: BUG #16676: SELECT ... FETCH FIRST ROW WITH TIES FOR UPDATE SKIP LOCKED locks rows it doesn't return

Álvaro Herrera
On 2020-Oct-19, David Christensen wrote:

> > On Oct 19, 2020, at 6:59 PM, David Christensen <[hidden email]> wrote:
> >
> >> On Oct 19, 2020, at 6:07 PM, Tom Lane <[hidden email]> wrote:
> >>
> >> David Christensen <[hidden email]> writes:
> >>> Proposed fix:
> >>> Reorder Limit/LockRows nodes to prevent locking extra tuples in FETCH FIRST WITH TIES
> >>
> >> Isn't that going to break more cases than it fixes?
> >
> > In the case of Limit, isn’t LockRows supposed to only lock the number of actual rows returned?
> >
> > What are the scenarios that this might break and do you have any ideas for alternate fixes?
>
> Will now that I think about it, if the LockRows node is responsible
> for skipping locked rows, etc then my proposed solution is clearly
> wrong.

I tried your proposed patch yesterday and found that the second query
returns no rows rather than two rows, which is not an improvement.

> Maybe splitting LockRows into two nodes, one for locking and one for
> emitting unlocked nodes then interleaving Limit in between? (Or only
> doing something along these lines for this admittedly narrow use case.)

I was having a similar idea, but the main reason I don't think it's a
good fix is that we can't backpatch such a change to pg13.

I was thinking if it was possible to modify Limit so that it would
"peek" into its child node without "actually reading".  But that's not
possible in our executor implementation AFAIK -- you only have
ExecProcNode as an interface, there's no way to affect what happens
underneath.

Maybe an approach is to forbid a FOR UPDATE clause in a query that has a
LIMIT WITH TIES clause; so we'd force the user to write a subquery for
LIMIT WITH TIES and then apply FOR UPDATE to an outer query.  However,
I'm surprised to find that we have *two* LockRows nodes when doing that:

explain select * from (select * from queue order by batch_id fetch first 2 rows with ties) t for update skip locked;
                                       QUERY PLAN                                      
────────────────────────────────────────────────────────────────────────────────────────
 LockRows  (cost=55.20..55.27 rows=2 width=40)
   ->  Subquery Scan on t  (cost=55.20..55.25 rows=2 width=40)
         ->  Limit  (cost=55.20..55.23 rows=2 width=14)
               ->  LockRows  (cost=55.20..83.45 rows=2260 width=14)
                     ->  Sort  (cost=55.20..60.85 rows=2260 width=14)
                           Sort Key: queue.batch_id
                           ->  Seq Scan on queue  (cost=0.00..32.60 rows=2260 width=14)
(7 filas)

and of course, we still have the behavior where the third row is
skipped.



Reply | Threaded
Open this post in threaded view
|

Re: BUG #16676: SELECT ... FETCH FIRST ROW WITH TIES FOR UPDATE SKIP LOCKED locks rows it doesn't return

Tom Lane-2
Alvaro Herrera <[hidden email]> writes:
> On 2020-Oct-19, David Christensen wrote:
>> Maybe splitting LockRows into two nodes, one for locking and one for
>> emitting unlocked nodes then interleaving Limit in between? (Or only
>> doing something along these lines for this admittedly narrow use case.)

> I was having a similar idea, but the main reason I don't think it's a
> good fix is that we can't backpatch such a change to pg13.

Um, why not?  I don't have a position yet on whether this is a good way
to fix it; but if we did do it, AFAICS the only thing we'd have to be
careful of in v13 is not renumbering existing NodeTag values.

If your concern is just that EXPLAIN plans will look different, the same
could be said of David's other proposal.

                        regards, tom lane


Reply | Threaded
Open this post in threaded view
|

Re: BUG #16676: SELECT ... FETCH FIRST ROW WITH TIES FOR UPDATE SKIP LOCKED locks rows it doesn't return

David Christensen
> On Oct 20, 2020, at 9:16 AM, Tom Lane <[hidden email]> wrote:

>
> Alvaro Herrera <[hidden email]> writes:
>> On 2020-Oct-19, David Christensen wrote:
>>> Maybe splitting LockRows into two nodes, one for locking and one for
>>> emitting unlocked nodes then interleaving Limit in between? (Or only
>>> doing something along these lines for this admittedly narrow use case.)
>
>> I was having a similar idea, but the main reason I don't think it's a
>> good fix is that we can't backpatch such a change to pg13.
>
> Um, why not?  I don't have a position yet on whether this is a good way
> to fix it; but if we did do it, AFAICS the only thing we'd have to be
> careful of in v13 is not renumbering existing NodeTag values.
>
> If your concern is just that EXPLAIN plans will look different, the same
> could be said of David's other proposal.
If we can determine the scope to which these different nodes might be used and make it so it still uses the existing node structure for most existing cases (i.e., maybe an additional parameter to create_lockrows_plan or similar) then that might work; AFAIK, this is the first time we’ve had to consider this sort of thing (though I do wonder if there might be something in window functions which might bump into this sort of issue).

I’m working on an isolation test to formalize this failure, which I can do as a separate patch if we want to have this prior to implementing a fix.

--
David Christensen
Senior Software and Database Engineer
End Point Corporation
[hidden email]
785-727-1171



signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: BUG #16676: SELECT ... FETCH FIRST ROW WITH TIES FOR UPDATE SKIP LOCKED locks rows it doesn't return

David Christensen
> On Oct 20, 2020, at 9:23 AM, David Christensen <[hidden email]> wrote:

>
>> On Oct 20, 2020, at 9:16 AM, Tom Lane <[hidden email]> wrote:
>>
>> Alvaro Herrera <[hidden email]> writes:
>>> On 2020-Oct-19, David Christensen wrote:
>>>> Maybe splitting LockRows into two nodes, one for locking and one for
>>>> emitting unlocked nodes then interleaving Limit in between? (Or only
>>>> doing something along these lines for this admittedly narrow use case.)
>>
>>> I was having a similar idea, but the main reason I don't think it's a
>>> good fix is that we can't backpatch such a change to pg13.
>>
>> Um, why not?  I don't have a position yet on whether this is a good way
>> to fix it; but if we did do it, AFAICS the only thing we'd have to be
>> careful of in v13 is not renumbering existing NodeTag values.
>>
>> If your concern is just that EXPLAIN plans will look different, the same
>> could be said of David's other proposal.
>
> If we can determine the scope to which these different nodes might be used and make it so it still uses the existing node structure for most existing cases (i.e., maybe an additional parameter to create_lockrows_plan or similar) then that might work; AFAIK, this is the first time we’ve had to consider this sort of thing (though I do wonder if there might be something in window functions which might bump into this sort of issue).
>
> I’m working on an isolation test to formalize this failure, which I can do as a separate patch if we want to have this prior to implementing a fix.
Enclosed is the (currently failing) isolation test for the expected behavior.



--
David Christensen
Senior Software and Database Engineer
End Point Corporation
[hidden email]
785-727-1171




0001-Add-isolation-test-for-FETCH-FIRST-ROW-WITH-TIES-FOR.patch (3K) Download Attachment
signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: BUG #16676: SELECT ... FETCH FIRST ROW WITH TIES FOR UPDATE SKIP LOCKED locks rows it doesn't return

David Christensen
In reply to this post by David Christensen
> On Oct 19, 2020, at 7:33 PM, David Christensen <[hidden email]> wrote:
>
> Maybe splitting LockRows into two nodes, one for locking and one for emitting unlocked nodes then interleaving Limit in between? (Or only doing something along these lines for this admittedly narrow use case. )

This does appear to be quite a bit harder than originally hoped for on the surface; creating a node to “pass-thru” unlocked tuples without locking them would require building out some additional infrastructure that does not appear to be present in all AMs; something to allow a test for locks without actually calling table_tuple_lock() formally. Perhaps adding a param to indicate “test” only—not sure if something like similar to heapam's “test_lockmode_for_conflict()” is something we’d need to had.  (Or even a new lock mode which doesn’t create RowMarks but skips any conflicting modes.)

That said, I think it might be worth trying to go down the road of “forbid this behavior”, particularly if a workaround is available.  Perhaps looking into why Álvaro’s plan was generating the multiple LockRows nodes would be more fruitful and less likely to cause backpatching pain.

David
--
David Christensen
Senior Software and Database Engineer
End Point Corporation
[hidden email]
785-727-1171




signature.asc (849 bytes) Download Attachment