Relationship regression: Removing and inserting an object breaks the relationship

[ksuther]

A change in 0b1dba8ca8ec4342cee4734f6c82d70bc5ad8c55 broke the following situation:

1. Create an automatic relationship with yapDatabaseRelationshipEdges (a destination edge with YDB_DeleteSourceIfDestinationDeleted)
2. Use setObject:forKey:inCollection: to add the objects which creates the relationship
3. Remove the destination objects with removeObjectForKey: (which adds the IDs to deletedOrder in the relationship extension)
4. Add new destination objects with setObject:forKey: and also replace the original source object with setObject:forKey:
5. The next time the relationships are flushed, deletedOrder contains the deleted ID even though the object was re-created. The result is the relationship is broken, but the objects are left in the database.

Before 0b1dba8ca8ec4342cee4734f6c82d70bc5ad8c55, this was handled in handleInsertObject:forCollectionKey:withMetadata:rowid: by checking deletedInfo and removing any rows that were reinserted (https://github.com/yapstudios/YapDatabase/blob/b5edcb84c03d2557c8375feab1ba7e54830a77be/YapDatabase/Extensions/Relationships/YapDatabaseRelationshipTransaction.m#L3080).

I'm not sure why that check was removed, but I believe that's the source of the change in behavior.

[ksuther]

Also, if I copy and paste the last part of the implementation of handleInsertObject:forCollectionKey:withMetadata:rowid: from 2.7 into 2.8, the behavior returns to what I would expect.

[robbiehanson]

After looking this over, it appears the problem is much worse than expected. The issue is "rowid recycling". That is, sqlite appears to use a "free rowid pool". So if, for example, rowid 16 is deleted, and then another object is inserted (during the same transaction), then the inserted row will get rowid 16.

I'm not sure why that check was removed

It was removed because, as I was updating the code, I noticed the check didn't make any sense. If (collection, key) is removed from the database, and then inserted again, there's no guarantees that it will receive the same rowid. In fact, it's highly likely the rowid will change. You can test this in the following manner:

[transaction removeObjectForKey:@"A" inCollection:nil];
[transaction removeObjectForKey:@"B" inCollection:nil];
[transaction setObject:@"B" forKey:@"B" inCollection:nil];
[transaction setObject:@"A" forKey:@"A" inCollection:nil];

In the above scenario, "A" and "B" will swap rowids.

This doesn't affect most extensions (or the core database) because deletes are handled immediately. But the relationship extension, with it's queue & flush logic, presents a problem. In other words, its going to require some significant changes to properly fix this problem. I'm looking forward to doing it. Especially since finding a proper solution now will prevent future extensions from going down this flawed architecture road. But it's going to take me a little while to get there (because of other responsibilities). So I've moved it to 2.8.3, as 2.8.2 already has several fixes I'd like to get out the door.

[ksuther]

Thanks for the explanation. Is this something I should worry about in 2.7.x as well? I didn't notice this until I tried out 2.8.

[robbiehanson]

Unfortunately, all versions of YapDatabaseRelationship have had this bug.

[ksuther]

Thanks, good to know. In case anyone else runs into this, I worked around this by not calling removeObjectForKey: on keys that were about to be re-added.

So instead of:

[transaction removeObjectForKey:@"A" inCollection:@"x"];
[transaction removeObjectForKey:@"B" inCollection:@"x"];
[transaction removeObjectForKey:@"C" inCollection:@"x"];
[transaction setObject:a forKey:@"A" inCollection:@"x"];
[transaction setObject:b forKey:@"B" inCollection:@"x"];

I'm doing

NSMutableArray *keysToRemove = [@[@"A", @"B", @"C"] mutableCopy];
[transaction setObject:b forKey:@"A" inCollection:@"x"];
[keysToRemove removeObject:@"A"];
[transaction setObject:b forKey:@"B" inCollection:@"x"];
[keysToRemove removeObject:@"B"];
[transaction removeObjectsForKeys:keysToRemove];

Thanks for your continued work on YapDatabase, no regrets having switched to it!

[MythicLionMan]

I've run into this issue a second time (in issue #543), and found myself investigating it again. I only wish I could remember these visits, so I could figure out what's going on more quickly :-). This time I wrote some unit tests that expose one version of it:

https://github.com/Marketcircle/YapDatabase/blob/UnitTestEdge/YapDatabaseTests/YapDatabaseTests.swift

I found another workaround for this issue (it resolves the issue in the unit tests that I wrote). Since the issue is that rowids are being re-used when objects get deleted, why not enable the AUTOINCREMENT keyword on the rowid property? This will prevent a new object from being assigned an old rowid and confusing the relationships extension.

This is a bit of a hack, and I don't know if this is a fix for all issues caused by this pattern. It also doesn't fix existing databases, but that would be possible with an update that altered the rowid property. The biggest downside is probably that it burns through ROWIDs faster, but that doesn't seem to be an issue with the intended use cases of YapDatabase.

This solution is imperfect, but if a major change is required to fix this properly, ensuring that ROWIDs are unique is an easy solution while a redesign of the relationship extension is contemplated.