Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Success of deleting rows depending on order of row insertion [CORE3317] #3684

Closed
firebird-issue-importer opened this issue Jan 28, 2011 · 12 comments

Comments

@firebird-issue-importer

Submitted by: Rajko Thon (rthon)

Is related to CORE634
Relate to CORE3362

Attachments:
script_01.sql
script_02.sql

--- BUG: Success of deleting rows depending on order of row insertion

Environment:
  \(Firebird\-Server 2\.5\.0\.26074\)
  Windows XP 32Bit Servicepack 1

Priority: Blocker, because partial execution of deletion without error message \-\-\> delete operation not guaranteed 

Summary
-------

When deleting rows in a table not all of the expected rows are deleted. The
success of the deletion is dependent on the order of the preceding
insertion of the rows into the table.

Case-Description
----------------

We create a table "cls", which is to represent a closure-based tree
approach, as:

create table cls (
id numeric(18)
constraint cls_id_ck_c not null,
id_parent numeric(18)
constraint cls_idparent_ck_c not null,
id_child numeric(18)
constraint cls_idchild_ck_c not null,
depth numeric(18)
constraint cls_depth_ck_c not null,
constraint cls_ui1_c unique(id_parent, depth, id_child),
constraint cls_ui2_c unique(id_child, id_parent),
constraint cls_pk_c primary key (id)
);

A row in the table indicates that id_child is child to id_parent at the
level of "depth" with the columns id_parent and id_child refering to
entities in an arbitrary table. Foreign-key-relationships are not enforced.

Now we insert some rows from a live-example.

insert into cls values(1, 2, 2, 0);
insert into cls values(2, 7, 7, 0);
insert into cls values(3, 10, 10, 0);

insert into cls values(4, 2, 7, 1);
insert into cls values(5, 2, 10, 2);
insert into cls values(6, 7, 10, 1);

The first three rows represent three items in a tree as parent of
themselves at depth=0. Rows 4 to 6 represent the hierarchy in which 7 is
child of 2 at depth=1, 10 is child of 7 at depth=1 and hence 10 is child of
2 at depth=2.

Now we unparent id_child=7 by deleting all rows indicating that 7 is a
child of id_parent=2, hence id_child=10 must lose its indirect parentage to
id_parent=2 as well.

To delete the rows we use the following statement:

delete
from cls
where id in (
select http://c.id
from cls c
inner join
cls p
on c.id_parent = p.id_parent
where p.id_child = 7
and p.depth = 1
and c.depth >= 1
);

The inner select returns the id of any child that has the same parent as
id_child=7 at depth greater or equal than the depth of the row indicating
the direct parentage (>=1). In our example the statement returns rows 4 and
5. The outer delete-statement should simply delete those both rows. But
that's not what is happening. Instead only row=4 is deleted, but row=5
remains. Also no error is thrown here.

Please note that replacing the inner select-statement with the id that
shall be deleted works as expected. See enclosed script_01 for details.

Followup
--------

To understand the behaviour of the delete-statement and to possibly find
another way to delete the required rows using a single statement only, a
different approach was examined.

We use the same table and the same data as before. We also try to delete
the same rows as before, but this time by using:

for
select http://c.id
from cls c
inner join
cls p
on c.id_parent = p.id_parent
where p.id_child = 7
and p.depth = 1
and c.depth >= 1
into :v_id_to_delete
do
delete
from cls
where id = :v_id_to_delete;

The statement works nearly as expected, since both rows (4 and 5) are
deleted - BUT ONLY IF the rows are inserted into the table "cls" OUTSIDE
the scope of the executable block that contains the for-delete-statement!
If the insertion of the rows is done inside the same block or procedure,
then only row=4 is deleted, but row=5 remains. Same effect as with the
first delete!

Surprisingly, introducing an order-by-clause with descendent ordering into
the select-statement of the for-delete leads to the desired result:

for
select http://c.id
from cls c
inner join
cls p
on c.id_parent = p.id_parent
where p.id_child = 7
and p.depth = 1
and c.depth >= 1
order by
c.depth desc
into :v_id_to_delete
do
delete
from cls
where id = :v_id_to_delete;

This way both rows (4 and 5) are deleted independently of the fact if the
insertion takes place in the same block as the for-delete or not.
See enclosed script_02 for a demonstration.

However, at this point the question arose to me why the success of the
deletion should be dependent on the ordering in the for-select-delete?

This led me to try to simply REVERSE THE ORDER of the insert-statements -
and suddenly the deletion worked! But of course this demonstrates that an
operation as the deletion of rows can be dependent on preceding operations
in an non-obvious way. So I think this is a bug.

Conclusions
-----------

There seems to be a bug regarding the deletion of rows that are previously
gathered by a select-statement. It seems that if a delete is based on the
result of a select-statement, the entire statement can get in conflict with
some kind of internal mechanism that still has a kind of "hold" (??) on previous
insert-statements. This "hold" appears to be dependent on:

1) the insert taking place in the scope of the same script or the same
block as the deletion,

2) it appears to rely on the insertion taking place in descending order of
the ID in the given example.

Furthermore simply stating the rows manually seems to work too.

See enclosed script_01 and script_02 for reproducing the behaviour.
Just uncomment the corresponding sections to see all
described behaviour patterns.

For questions please contact:
mailto:rajko_thon@gmx.net
(Rajko Thon)

--- script_01 -----------------------

connect "D:\Projekte\SQL\cls_table\cls.gdb" user SYSDBA password masterkey;
drop database;
create database 'D:\Projekte\SQL\cls_table\cls.gdb' user 'SYSDBA' password 'masterkey' page_size 16384 default character set utf8;

create table cls (
id numeric(18)
constraint cls_id_ck_c not null,
id_parent numeric(18)
constraint cls_idparent_ck_c not null,
id_child numeric(18)
constraint cls_idchild_ck_c not null,
depth numeric(18)
constraint cls_depth_ck_c not null,
constraint cls_ui1_c unique(id_parent, depth, id_child),
constraint cls_ui2_c unique(id_child, id_parent),
constraint cls_pk_c primary key (id)
);

-- reversed insertion order always works
-- insert into cls values(6, 7, 10, 1);
-- insert into cls values(5, 2, 10, 2);
-- insert into cls values(4, 2, 7, 1);
-- insert into cls values(3, 10, 10, 0);
-- insert into cls values(2, 7, 7, 0);
-- insert into cls values(1, 2, 2, 0);

-- normal insertion order does not work correctly
insert into cls values(1, 2, 2, 0);
insert into cls values(2, 7, 7, 0);
insert into cls values(3, 10, 10, 0);
insert into cls values(4, 2, 7, 1);
insert into cls values(5, 2, 10, 2);
insert into cls values(6, 7, 10, 1);

commit;

-- deleting manually specified rows always works
-- delete
-- from cls
-- where id in (
-- 4, 5
-- );

-- does not work correctly
delete
from cls
where id in (
select http://c.id
from cls c
inner join
cls p
on c.id_parent = p.id_parent
where p.id_child = 7
and p.depth = 1
and c.depth >= 1
);

commit;

exit;

--- script_02

connect "D:\Projekte\SQL\cls_table\cls.gdb" user SYSDBA password masterkey;
drop database;
create database 'D:\Projekte\SQL\cls_table\cls.gdb' user 'SYSDBA' password 'masterkey' page_size 16384 default character set utf8;

create table cls (
id numeric(18)
constraint cls_id_ck_c not null,
id_parent numeric(18)
constraint cls_idparent_ck_c not null,
id_child numeric(18)
constraint cls_idchild_ck_c not null,
depth numeric(18)
constraint cls_depth_ck_c not null,
constraint cls_ui1_c unique(id_parent, depth, id_child),
constraint cls_ui2_c unique(id_child, id_parent),
constraint cls_pk_c primary key (id)
);

set term !! ;
execute block
as
declare v_id_to_delete numeric(18,0);
begin

-- reversed insertion order always works
-- insert into cls values(6, 7, 10, 1);
-- insert into cls values(5, 2, 10, 2);
-- insert into cls values(4, 2, 7, 1);
-- insert into cls values(3, 10, 10, 0);
-- insert into cls values(2, 7, 7, 0);
-- insert into cls values(1, 2, 2, 0);

-- normal does not work correctly
insert into cls values(1, 2, 2, 0);
insert into cls values(2, 7, 7, 0);
insert into cls values(3, 10, 10, 0);
insert into cls values(4, 2, 7, 1);
insert into cls values(5, 2, 10, 2);
insert into cls values(6, 7, 10, 1);

-- does not work correctly
for
select http://c.id
from cls c
inner join
cls p
on c.id_parent = p.id_parent
where p.id_child = 7
and p.depth = 1
and c.depth >= 1
-- uncomment the following two lines to have it
-- working with normal insertion order
-- order by
-- c.depth desc
into :v_id_to_delete
do
delete
from cls
where id = :v_id_to_delete;

suspend;
end !!
set term ; !!
commit;

exit;

====== Test Details ======

See test core_3362_basic.fbt

@firebird-issue-importer
Copy link
Author

@firebird-issue-importer firebird-issue-importer commented Jan 28, 2011

Modified by: Rajko Thon (rthon)

Attachment: script_01.sql [ 11891 ]

Attachment: script_02.sql [ 11892 ]

@firebird-issue-importer
Copy link
Author

@firebird-issue-importer firebird-issue-importer commented Jan 28, 2011

Commented by: @dyemanov

It looks like a duplicate for CORE634. But provided the level of the details given, I prefer to keep both tickets open.

It's a design pitfall rather than a bug, although the SQL committee would disagree. It's caused by the fact that rows are deleted one by one and the predicate (sub-query) is also evaluated row by row, and the inner select may see the "mutable" changes (deleted rows become invisible for it).

The common workaround is to use the ORDER BY clause (it's supported for DELETE statements as well as for SELECT ones) which forces the SORT plan, thus implicitly materializing the result set before deletions start to happen.

@firebird-issue-importer
Copy link
Author

@firebird-issue-importer firebird-issue-importer commented Jan 28, 2011

Modified by: @dyemanov

priority: Blocker [ 1 ] => Major [ 3 ]

Version: 2.0.6 [ 10303 ]

Version: 3.0 Initial [ 10301 ]

Version: 1.5.6 [ 10225 ]

Version: 2.1.3 [ 10302 ]

Version: 2.1.2 [ 10270 ]

Version: 2.0.5 [ 10222 ]

Version: 2.1.1 [ 10223 ]

Version: 2.0.4 [ 10211 ]

Version: 2.1.0 [ 10041 ]

Fix Version: 3.0 Alpha 1 [ 10331 ]

assignee: Vlad Khorsun [ hvlad ]

@firebird-issue-importer
Copy link
Author

@firebird-issue-importer firebird-issue-importer commented Jan 28, 2011

Modified by: @dyemanov

Link: This issue is related to CORE634 [ CORE634 ]

@firebird-issue-importer
Copy link
Author

@firebird-issue-importer firebird-issue-importer commented Jan 28, 2011

Commented by: Rajko Thon (rthon)

Thanks, that explains it of course. When the inner select may see the
"mutable" changes (deleted rows become invisible) and rows are deleted one
by one then the inner select will not be able to see row=5 anymore as soon
as row=4 is deleted. When on the other hand order-by with descendent
sorting is applied then row=5 is deleted first and the inner select will
still deliver a valid result for this case.

Now, before publishing more critical thoughts at first I want to thank you
for all your great work on such a unique database product! My "critique" is
only intended to help iron out bugs.
So, generally I would tend to agree with the SQL committee, since the
delete-operation in question contains a non-correlated subquery which would
be expected to execute once only. The same applies to the deletion using
the for-select-do-delete-statement.

Unfortunately the workaround of using an order by is only helpful in some
cases. When using the for-select-do-delete-statement it works well. But
when using the delete-statement with the non-correlated subquery it only
works when stating an order-by with descendent sorting. That is, because
using asc instead of desc firebird in this case doesn't make use of a SORT plan but
of the tables primary-key-index and obviously doesn't implicitly materialize the
result set before deletions start to happen.

@firebird-issue-importer
Copy link
Author

@firebird-issue-importer firebird-issue-importer commented Jan 28, 2011

Commented by: @dyemanov

Proper critique is surely welcome. I was just explaining how it worked since late 1980s ;-) BTW, I also agree with the SQL committee, this is why we have both tickets accepted. The draft fix is already prepared for testing, but it's unlikely to see the day light before v3.0.

@firebird-issue-importer
Copy link
Author

@firebird-issue-importer firebird-issue-importer commented Jan 28, 2011

Commented by: Philip Williams (unordained)

RE: "That is, because using asc instead of desc firebird in this case doesn't make use of a SORT plan but of the tables primary-key-index and obviously doesn't implicitly materialize the result set before deletions start to happen."

You could try "order by (id + 0) asc" or something similar. That should prevent the index from interfering.

@firebird-issue-importer
Copy link
Author

@firebird-issue-importer firebird-issue-importer commented Feb 25, 2011

Modified by: @hvlad

Link: This issue relate to CORE3362 [ CORE3362 ]

@firebird-issue-importer
Copy link
Author

@firebird-issue-importer firebird-issue-importer commented Oct 23, 2012

Modified by: @dyemanov

status: Open [ 1 ] => Resolved [ 5 ]

resolution: Fixed [ 1 ]

@firebird-issue-importer
Copy link
Author

@firebird-issue-importer firebird-issue-importer commented Jul 16, 2015

Modified by: @pavel-zotov

status: Resolved [ 5 ] => Resolved [ 5 ]

QA Status: Deferred

Test Details: Test will be implemented after changing status of CORE3362 to 'Fixed'.

@firebird-issue-importer
Copy link
Author

@firebird-issue-importer firebird-issue-importer commented Sep 19, 2016

Modified by: @pavel-zotov

status: Resolved [ 5 ] => Resolved [ 5 ]

QA Status: Deferred => Covered by another test(s)

Test Details: Test will be implemented after changing status of CORE3362 to 'Fixed'. => See test core_3362_basic.fbt

@firebird-issue-importer
Copy link
Author

@firebird-issue-importer firebird-issue-importer commented Sep 19, 2016

Modified by: @pavel-zotov

status: Resolved [ 5 ] => Closed [ 6 ]

Fix Version: 3.0.0 [ 10740 ]

Fix Version: 4.0 Initial [ 10621 ]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment