Issue Details (XML | Word | Printable)

Key: CORE-3317
Type: Bug Bug
Status: Closed Closed
Resolution: Fixed
Priority: Major Major
Assignee: Vlad Khorsun
Reporter: Rajko Thon
Votes: 0
Watchers: 3
Operations

If you were logged in you would be able to see more operations.
Firebird Core

Success of deleting rows depending on order of row insertion

Created: 28/Jan/11 10:22 AM   Updated: 18/Sep/16 09:22 PM
Component/s: Engine
Affects Version/s: 2.1.0, 2.0.4, 2.1.1, 2.0.5, 2.1.2, 2.1.3, 1.5.6, 3.0 Initial, 2.0.6, 2.5.0
Fix Version/s: 3.0 Alpha 1, 4.0 Initial, 3.0.0

File Attachments: 1. File script_01.sql (2 kB)
2. File script_02.sql (2 kB)

Environment:
Firebird-Server 2.5.0.26074
Windows XP 32Bit Servicepack 1
Issue Links:
Relate

QA Status: Covered by another test(s)
Test Details: See test core_3362_basic.fbt


 Description  « Hide

--- 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 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 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 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:
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 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 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;


 All   Comments   Change History   Subversion Commits      Sort Order: Ascending order - Click to sort in descending order
Dmitry Yemanov added a comment - 28/Jan/11 10:40 AM
It looks like a duplicate for CORE-634. 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.

Rajko Thon added a comment - 28/Jan/11 05:31 PM
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.

Dmitry Yemanov added a comment - 28/Jan/11 05:50 PM
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.

Philip Williams added a comment - 28/Jan/11 07:01 PM
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.