two rows can be inserted with the same value in a column that a unique constraint on that column should prevent

• Key: DERBY-4028
• Type: Bug
• Status: Resolved
• Resolution: Fixed
• Priority: Major
• Assignee: Knut Anders Hatlen
• Reporter: Glenn Bradford
• Component/s: JDBC
• Affects Version/s: 10.4.1.3
• Fix Version/s: 10.4.2.1, 10.5.1.1

Description

The following DDL allows two rows to be inserted with the same value in a column when a unique constraint on that column should prevent it. The select statement (see the end of the mail) produces:

ij> ALBUMID |RANK |YEARRELEAS&|ALBUM

--------------------------------------------------------------------------------
-----------------------------------------------------------------
11100 |1 |1945 |

13300 |1 |1966 |

2000 |7 |1974 |Songs in the Key of Life

88000 |12 |1971 |


4 rows selected

The first two rows have the same rank value of 1 despite there being a unique constraint on that column.

derby version: 10.4.1.3

Bryan Pendleton reproduced this and suggested that the problem "is related to the fairly new feature of Derby
which allows definition of a unique constraint on a null-able column".
https://issues.apache.org/jira/browse/DERBY-3330

Redefining the rank column as 'not null' made the problem go away.

I came across this after running a program that randomly makes inserts, updates, and deletes into this table. It usually takes between 500-600 DDL statements to make it happen. I then took the results and hand-pruned out as many statements as I could and tried to minimize the number of rows produced by the select statement, while still reproducing the issue. At this point it is very sensitive to any changes. For example, re-running the test after removing what appear to be redundantly inserted rows will make the problem go away, as will modifications to band and album names. It's all very strange.

A very old version of Cloudscape (3.6.9), from which I am trying to upgrade, does not have this problem.

-------------------------------------------------------------------------
drop table tra;

create table tra (
    albumId bigint,
    rank int,
    CONSTRAINT UNIQUE_RANK
        UNIQUE(rank),
    band varchar(100),
    album varchar(100),
    yearReleased int,
    CONSTRAINT PK_TOPROCKALBUMS
        PRIMARY KEY(albumId)
);

insert into tra values(1000, 1, '', '', 1966);
insert into tra values(2000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(3000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(4000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(5000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(6000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(7000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(8000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(9000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(10000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(11000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(12000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(13000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(14000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(15000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(16000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(17000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(18000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(19000, 14, 'Joni ', 'Blue', 1971);
insert into tra values(20000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(21000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(22000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(23000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(24000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(25000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(26000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(27000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(28000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(29000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(30000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(31000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(32000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(33000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(34000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(36000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(36000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(37000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(38000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(39000, 1, 'The Beatles', '', 1966);
insert into tra values(40000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(41000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(42000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(43000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(44000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(45000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(46000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(47000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(48000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(49000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(50000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(51000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(52000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(53000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(54000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(55000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(56000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(57000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(59000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(60000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(61000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(62000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(63000, 1, 'The Beatles', '', 1966);
delete from tra where rank=1;
insert into tra values(64000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(65000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(66000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(67000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(68000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(69000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(70000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(71000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(72000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(73000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(74000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(75000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(76000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(77000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(78000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(79000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
delete from tra where rank=14;
insert into tra values(80000, 14, 'Joni Mitchell', 'Blue', 1971);
insert into tra values(81000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(82000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(83000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(84000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(85000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(86000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(87000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(88000, 12, '', '', 1971);
insert into tra values(89000, 1, 'The Beatles', '', 1966);
insert into tra values(90000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(91000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(92000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(93000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(94000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(95000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(96000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(97000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(98000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(99000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(10000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(10100, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(10200, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(10300, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(10400, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(10500, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
delete from tra where rank=1;
insert into tra values(10600, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(10700, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(10800, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(10900, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(11100, 1, 'The Beatles', '', 1966);
insert into tra values(11200, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(11300, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(11400, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(11500, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(11600, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(11700, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(11800, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(11900, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(12000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(12100, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(12200, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
delete from tra where rank=14;
insert into tra values(12300, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(12400, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
update tra set yearReleased=1945 where rank=1;
insert into tra values(12500, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(12600, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(12700, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(12800, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(12900, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(13000, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(13100, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(13200, 7, 'Stevie Wonder', 'Songs in the Key of Life', 1974);
insert into tra values(13300, 1, 'The Beatles', '', 1966);
select albumId, rank, yearReleased, album from tra order by rank;
exit;

Comments

[Knut Anders Hatlen]

It seems like BTreeController.compareLeftAndRightSiblings() doesn't handle deleted records correctly. If it finds a committed deleted record with the same key, it thinks that it is OK to insert a new record with the same key. I guess this would have been an OK assumption in a unique index, but the UNIQUE constraint is backed by a non-unique index (because multiple NULLs are allowed), so if you find a deleted record you really need to move past that record and check again.

[Knut Anders Hatlen]

The attached patch (check-deleted.diff) appears to fix the reported problem. What it does is:

  1) Make BTreeController.compareRowsForInsert() return MATCH_FOUND even if the row is deleted, and say in its javadoc that callers should check if the row is deleted

  2) Make BTreeController.comparePreviousRecord() and BTreeController.compareNextRecord() check if the found record is deleted, and if it is, move on to see if an existing record can be found

  3) Make BTreeController.comparePreviousRecord() look at the record before the previous one instead of the record after the previous one if the previous doesn't match (probably a copy/paste error from compareNextRecord())

I suspect that there may be other problems in comparePreviousRecord() and compareNextRecord(). At least it looks to me as if there are paths through those methods where we latch pages and never release them. I'm not 100% convinced that the slot boundary checks are correct either, but I'll need to double check that.

I haven't run any tests on the patch, except the script that reproduced the bug, and I'm not sure if this is the correct way to fix it. But I'm posting it in case someone else wants to investigate the bug.

What I find strange, though, is that if I remove any of the failing inserts right before the insert that incorrectly succeeds, the insertion of the duplicate is correctly rejected. I thought that the rejected inserts shouldn't change anything in the B-tree, but apparently they do.

[Bryan Pendleton]

Perhaps the rejected insert causes an internal page split, and then discovers
the non-uniqueness. It then terminates the insert processing, but leaves
the split?

Or, similar, perhaps the rejected insert causes a page allocation, and then
refuses the insert but leaves the page allocated?

That is, maybe it's some sort of "physical" or "structural" change to the
BTree that doesn't "logically" change the content of the Btree, so when we
abort the user-level insert operation we leave the physical change as is?

I'm just guessing; your overall approach seems great to me, and many thanks
to the original reporter for tracking down this great repro script.

[Knut Anders Hatlen]

I guess you're right. But I still find it a bit odd that there is a difference between failing to add the value 7 to the index 119 times and failing to do so 120 times. I would have expected that the next attempt to insert the value would try to reuse the unused space allocated by the previous failed attempt rather than allocating space once more.

Out of curiosity, I tried this code:

        s.execute("create table d4028(x int unique)");
        while (true) {
            try {
                s.execute("insert into d4028 values 1");
            } catch (SQLException e) {
                System.out.println(e);
            }
        }

Even though it only inserts one row, the disk footprint just keeps growing. It's the disk footprint of the table that's growing, though, not the index, so it looks like the free space in the index is reused.

[Knut Anders Hatlen]

The problem with the growing table has been logged as DERBY-4056.

[Mike Matrigali]

I have not had time to debug this or review any of the patches.

Just wanted to say what I believe the assumptions are for the btree, so that we don't add the
wrong fixes.

A btree must be able to uniquely identify every row in the tree, it does this by comparing some
number of the columns in the tree. In the case of a unique btree it does this by comparing all
columns except for last one. In the case of a non-unique btree it does this by comparing all
collumns including the last one (which is the row id pointer of the base table). To uniquely identify
this row, whether it is deleted or not does not matter, there is meant to be code in the case of
deleted rows to wait around to make sure there is only one value with respect to these cases.

For the new feature which allows a unique constraint, but allows multiple nulls - the implementation is meant to use a "non-unique" btree. This means that rows, including deleted
rows are allowed to be duplicate. At insert time there is meant to be new code that allows duplicate null values but not other duplicates. I assume there is a bug in that new code.

[Mike Matrigali]

the code that knut's patch is going at, is the new code so very likely the right place to fix this one. Keep an eye out for the "isUniqueWithDuplicateNulls" paths.

[Knut Anders Hatlen]

Here's a simpler way to reproduce the bug:

ij> create table t (x int unique);
0 rows inserted/updated/deleted
ij> insert into t values 1,2,3;
3 rows inserted/updated/deleted
ij> delete from t where x = 2;
1 row inserted/updated/deleted
ij> update t set x = 2;
2 rows inserted/updated/deleted
ij> select * from t;
X
-----------
2
2

2 rows selected

[Knut Anders Hatlen]

Uploading an updated patch (1a) which adds test cases to NullableUniqueConstraintTest. I haven't run any other tests yet. I still suspect that there are some problems with how the latches are released in these methods, but I'll investigate more and file a separate issue if that turns out to be the case.

[Knut Anders Hatlen]

With the patch NullableUniqueConstraintTest.testMixedInsertDelete() starts failing intermittently with an exception indicating that there's an attempt to unlatch a page that is not latched. I haven't investigated whether it's a problem with the patch or if the patch has exposed some of the existing latch problems that I've mentioned.

Caused by: org.apache.derby.shared.common.sanity.AssertFailure: ASSERT FAILED
        at org.apache.derby.shared.common.sanity.SanityManager.ASSERT(SanityManager.java:98)
        at org.apache.derby.impl.store.raw.data.BasePage.unlatch(BasePage.java:1319)
        at org.apache.derby.impl.store.access.btree.ControlRow.release(ControlRow.java:926)
        at org.apache.derby.impl.store.access.btree.BTreeController.comparePreviousRecord(BTreeController.java:419)
        at org.apache.derby.impl.store.access.btree.BTreeController.compareLeftAndRightSiblings(BTreeController.java:579)
        at org.apache.derby.impl.store.access.btree.BTreeController.doIns(BTreeController.java:841)
        at org.apache.derby.impl.store.access.btree.BTreeController.insert(BTreeController.java:1289)
        at org.apache.derby.impl.store.access.btree.index.B2IController.insert(B2IController.java:210)
        at org.apache.derby.impl.sql.execute.IndexChanger.insertAndCheckDups(IndexChanger.java:439)
        at org.apache.derby.impl.sql.execute.IndexChanger.doInsert(IndexChanger.java:383)
        at org.apache.derby.impl.sql.execute.IndexChanger.insert(IndexChanger.java:589)
        at org.apache.derby.impl.sql.execute.IndexSetChanger.insert(IndexSetChanger.java:268)
        at org.apache.derby.impl.sql.execute.RowChangerImpl.insertRow(RowChangerImpl.java:453)
        at org.apache.derby.impl.sql.execute.InsertResultSet.normalInsertCore(InsertResultSet.java:1022)
        at org.apache.derby.impl.sql.execute.InsertResultSet.open(InsertResultSet.java:495)
        at org.apache.derby.impl.sql.GenericPreparedStatement.executeStmt(GenericPreparedStatement.java:416)
        at org.apache.derby.impl.sql.GenericPreparedStatement.execute(GenericPreparedStatement.java:297)
        at org.apache.derby.impl.jdbc.EmbedStatement.executeStatement(EmbedStatement.java:1235)
        ... 28 more

[Knut Anders Hatlen]

Attaching an updated patch (1b). The assert failure was caused by some changes in how the latches were released in the previous patches. I changed it back and also added comments explaining the logic behind the releasing of the latches (but I think there's still a bug there, see DERBY-4080). This change made the intermittent assert failures go away.

I'm running the regression tests now.

[Knut Anders Hatlen]

All the regression tests ran cleanly. The patch is ready for review. A description of the approach can be found in the comment dated 23/Jan/09 04:40 AM. That comment mentioned possible problems with boundary checks. Those problems were fixed in DERBY-4027. It also mentioned potential problems with releasing of latches, and those problems have now been logged as DERBY-4080 and DERBY-4081.

[Knut Anders Hatlen]

There has been interest in doing a full rewrite of the code that inserts rows in an index backing a nullable unique constraint [1], which would make this fix unnecessary. But since it's getting close to the 10.5 release and the work on the rewrite hasn't started, I'm checking in the fix anyway to ensure that it will be fixed 10.5.

Committed revision 752826.

[1] <URL:http://mail-archives.apache.org/mod_mbox/db-derby-dev/200903.mbox/[e-mail]%3E>

[Knut Anders Hatlen]

Merged to 10.4 and committed revision 754881.