W3C home > Mailing lists > Public > public-webapps@w3.org > January to March 2012

Re: [IndexedDB] Multientry and duplicate elements

From: Jonas Sicking <jonas@sicking.cc>
Date: Sun, 4 Mar 2012 02:06:52 +0100
Message-ID: <CA+c2ei-hzMx2Jf9z5Pn_miJnJfawKSjw4Y6bTTP7SyCHHLdj3Q@mail.gmail.com>
To: Israel Hilerio <israelh@microsoft.com>
Cc: "jsbell@chromium.org" <jsbell@chromium.org>, "public-webapps@w3.org" <public-webapps@w3.org>
On Fri, Mar 2, 2012 at 8:49 PM, Israel Hilerio <israelh@microsoft.com> wrote:
> We would like some clarification on this scenario.  When you say that FF
> will result on 1 index entry for each index that implies that the duplicates
> are automatically removed.  That implies that the multiEntry flag doesn’t
> take unique into consideration.  Is this correct?

Not quite.

In Firefox multiEntry indexes still honor the 'unique' constraint.
However whenever a multiEntry index adds an Array of entries to an
index, it first removes any duplicate values from the Array. Only
after that do we start inserting entries into the index. But if such
an insertion does cause a 'unique' constraint violation then we still
abort with a ConstraintError.

Let me show some examples:

store = db.createObjectStore("store");
index = store.createIndex("index", "a", { multiEntry: true } );
store.add({ x: 10 }, 1);
// Operation succeeds, store contains one entry
store.add({ a: 10 }, 2);
// Operation succeeds, store contains two entries
// index contains one entry: 10 -> 2
store.add({ a: [10, 20, 20] }, 3);
// Operation succeeds, store contains three entries
// index contains three entries: 10->2, 10->3, 20->3
store.add({ a: [30, 30, 30] }, 4);
// Operation succeeds, store contains four entries
// index contains four entries: 10->2, 10->3, 20->3, 30->4
store.put({ a: [20, 20] }, 3);
// Operation succeeds, store contains four entries
// index contains three entries: 10->2, 20->3, 30->4


Similar things happen for unique entries (assume that the transaction
has a errorhandler which calls preventDefault() on all error events so
that the transaction doesn't get aborted by the failed inserts)

store = db.createObjectStore("store");
index = store.createIndex("index", "a", { multiEntry: true, unique: true } );
store.add({ x: 10 }, 1);
// Operation succeeds, store contains one entry
store.add({ a: 10 }, 2);
// Operation succeeds, store contains two entries
// index contains one entry: 10 -> 2
store.add({ a: [10] }, 3);
// Operation fails due to the 10 key already existing in the index
store.add({ a: [20, 20, 30] }, 4);
// Operation succeeds, store contains three entries
// index contains three entries: 10->2, 20->4, 30->4
store.add({ a: [20, 40, 40] }, 5);
// Operation fails due to the 20 key already existing in the index
store.add({ a: [40, 40] }, 6);
// Operation succeeds, store contains four entries
// index contains four entries: 10->2, 20->4, 30->4, 40->6
store.put({ a: [10] }, 4);
// Operation fails due to the 10 key already existing in the index
// store still contains four entries
// index still contains four entries: 10->2, 20->4, 30->4, 40->6
store.put({ a: [10, 50] }, 2);
// Operation succeeds, store contains five entries
// index contains six entries: 10->2, 20->4, 30->4, 40->6, 50->2


To put it in spec terms:
One way to fix this would be to add the following to "Object Store
Storage Operation" step 7.4:
"Also remove any duplicate elements from /index key/ such that only
one instance of the duplicate value exists in /index key/".

Maybe also add a note which says:
"For example, the following value of /index key/ [10, 20, null, 30,
20] is converted to [10, 20, 30]"


For what it's worth, we haven't implemented this in Firefox by
preprocessing the array to remove duplicate entries. Instead we for
non-unique indexes keep a btree key'ed on indexKey + primaryKey. When
inserting into this btree we simply ignore any collisions since they
must be due to multiple identical entries in a multiEntry array.

For unique indexies we keep a btree key'ed on indexKey. If we hit a
collision when doing an insertion, and we're inserting into a
multiEntry index, we do a lookup to see what primaryKey the indexKey
maps to. If it maps to the primaryKey we're currently inserting for,
we know that it was due to a duplicate entry in the array and we just
move on with no error. If it maps to another primaryKey we roll back
the operation and fire a ConstraintError.

Let me know if there's still any scenarios that are unclear.

/ Jonas
Received on Sunday, 4 March 2012 01:07:49 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 18:49:50 GMT