Bug 20257 - IDBCursor should walk on secondary ordering of index value
Summary: IDBCursor should walk on secondary ordering of index value
Status: RESOLVED MOVED
Alias: None
Product: WebAppsWG
Classification: Unclassified
Component: Indexed Database API (show other bugs)
Version: unspecified
Hardware: All All
: P2 normal
Target Milestone: ---
Assignee: This bug has no owner yet - up for the taking
QA Contact: public-webapps-bugzilla
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2012-12-05 23:20 UTC by Kyaw Tun
Modified: 2015-06-15 23:56 UTC (History)
4 users (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Kyaw Tun 2012-12-05 23:20:58 UTC
Index records are stored in ascending order of key (index key) followed by
ascending order of value (primary key).

However, current IndexedDB API expose retrieving only by index key.

For example, the following operation on ‘tag‘ index of ‘article’ object
store  will retrieve the first occurrent of index key ‘javascript’.

IDBCursor_article_tag.continue(‘javascript’)

Suppose, we have thousand of articles having tag to ‘javascript’, to find
the match we have to walk step-by-step.

IDBCursor_article_tag.continue()

This take linear time whereas it is possible with log time on database
engine. Additionally we are making unnecessary callbacks back-and-ford
between js and database engine.

Such use case is common on filtered query and join operations. In these
case, index key is held constance while walking on primary keys.

It will be good if IndexedDB API provide like:

IDBCursor_article_tag.continue(index_key, primary_key)

It is a bit strange since the result is again primary_key. We already know
primary_key from other filter condition.

This method is also useful for cursor resume process.

This discussion can be found in http://lists.w3.org/Archives/Public/public-webapps/2012OctDec/0654.html
Comment 1 Joshua Bell 2012-12-05 23:56:19 UTC
+1 - Chromium has also received this feedback from developers.

Resolving for later, but it's an obvious win for IDB v2.
Comment 2 Joshua Bell 2013-08-26 22:22:16 UTC
So let's say you had this index:

index key primary key
========= ===========
"a" ..... 1
"a" ..... 2
"a" ..... 3
"b" ..... 1
"b" ..... 2
"b" ..... 3
"b" ..... 4

Assume an API of the form:

void continue(optional any key, optional any primaryKey);

If you have a cursor pointing at the second index entry (index key = "a", primary key = 2), what would you expect the outcome of these operations to be - including exception, new cursor position (key/primary key) or null?

cursor.continue() => { key: "a", primaryKey: 3 }
cursor.continue("a") => exception (key is less than or equal to current key)
cursor.continue("b") => { key: "b", primaryKey: 1 }
cursor.continue("c") => null
cursor.continue("a", 3) => ???
cursor.continue("a", 4) => ???
cursor.continue("b", 1) => ???
cursor.continue("b", 4) => ???
cursor.continue("b", 5) => ???
cursor.continue("c", 1) => ???
cursor.continue(null, 1) => ???
cursor.continue(null, 2) => ???
cursor.continue(null, 3) => ???
cursor.continue(null, 4) => ???
cursor.continue(null, 5) => ???

Are there other "interesting" cases that I'm missing?
Comment 3 Kyaw Tun 2013-08-26 22:59:20 UTC
curent position ("a", 2)

cursor.continue() => { key: "a", primaryKey: 3 }
cursor.continue("a") => exception (key is less than or equal to current key)
cursor.continue("b") => { key: "b", primaryKey: 1 }
cursor.continue("c") => null
cursor.continue("a", 3) => ("a", 3)
cursor.continue("a", 4) => ("b", 1)
cursor.continue("b", 1) => ("b", 1)
cursor.continue("b", 4) => ("b", 4)
cursor.continue("b", 5) => null
cursor.continue("c", 1) => null
cursor.continue(null, 1) => exception, invalid cursor position
cursor.continue(null, 2) => exception
cursor.continue(null, 3) => exception
cursor.continue(null, 4) => exception
cursor.continue(null, 5) => exception
Comment 4 Kyaw Tun 2013-08-26 23:18:28 UTC
Are there other "interesting" cases: filtering multiple field

Suppose we have two indexes

IndexA

index key primary key
========= ===========
"a" ..... 1
"a" ..... 2
"a" ..... 3
"b" ..... 1
"b" ..... 2
"b" ..... 3
"b" ..... 4

IndexB

index key primary key
========= ===========
"B" ..... 3
"B" ..... 5

We want to query record WHERE IndexA = "b" IndexB = "B"

cursorA = IndexA.openKeyCursor(IDKeyRange.only("b")) 
cursorB = IndexB.openKeyCursor(IDKeyRange.only("B")) 

cursorA => ("b", 1)
cursorB => ("B", 3)

since, primary key of cursorA is lower than cursorB, we continue on cursorA.

cursorA.continue("b", 3) => ("b", 3)

since, primary key of cursorA and cursor B are same, we get a result.
result.push(ObjectStore.get(3))

find, next result

cursorA.continue() => ("b", 4)
cursorB.continue() => ("B", 5)

since, primary key of cursorA is lower than cursorB, we continue on cursorA.

cursorA.continue("b", 5) => null

No more result to be found.

Notice that, number of steps require to get the result is independent of record size, but depend on result size.
Comment 5 Joshua Bell 2013-08-26 23:45:46 UTC
Thanks! This matches my expectations except that...

(In reply to comment #3)
> cursor.continue(null, 1) => exception, invalid cursor position
> cursor.continue(null, 2) => exception
> cursor.continue(null, 3) => exception
> cursor.continue(null, 4) => exception
> cursor.continue(null, 5) => exception

I was thinking that cursor.continue(null, pk) could be a shortcut for cursor.continue(cursor.key, pk). I'm not sure that's super useful, though.
Comment 6 Kyaw Tun 2013-08-27 11:36:38 UTC
One thing I worry about is detection for this feature.

Invoking continue with two arguments on an unsupported browser causes error. While, it is not possible to detect the feature without invoking it.
Comment 7 Joshua Bell 2013-08-27 15:30:21 UTC
(In reply to comment #6)
> One thing I worry about is detection for this feature.
> 
> Invoking continue with two arguments on an unsupported browser causes error.
> While, it is not possible to detect the feature without invoking it.

Yep.

For the record, an API that Jonas suggested was:

cursor.continue(my_key, { primaryKey: my_primary_key } );

... but that has the same issue. I'm not sure what the state-of-the-art is in defining feature-testable APIs that take options dictionaries.
Comment 8 Joshua Bell 2013-08-28 16:35:45 UTC
I spun up a public-script-coord thread at http://lists.w3.org/Archives/Public/public-script-coord/2013JulSep/0490.html

Consensus for this feature seems to be that it should be a new method (e.g. continueWithPrimaryKey) rather than an overload.

...

Any thoughts on polyfilling this? It seems like you'd need to override the built-in openCursor methods to capture the IDBRequest, and when continueWithPrimaryKey is called the polyfill would "unhook" the success handler (so this assumes you're using request.onsuccess not request.addEventListener), iterate the cursor, then reattach the success listener and call it with the event.

Re-using the request for cursors appears to be a design flaw here. :(
Comment 9 Kyaw Tun 2013-08-29 01:15:49 UTC
Polyfill may not worth it, in this case.

However, polyfill will be easy and efficient if the API is change to

cursor.continue(effective_key) 
cursor.continuePrimary(primary_key) 

For example:

curent position ("a", 2)

cursor.continuePrimary() => exception, key require
cursor.continuePrimary(3) => ("a", 3)
cursor.continuePrimary(4) => ("b", 1)
cursor.continue() => ("b", 2)
cursor.continuePrimary(3) => ("b", 3)
cursor.continuePrimary(5) => null
Comment 10 Joshua Bell 2013-08-29 18:26:19 UTC
Try it - the operation is easy, but polyfilling the behavior is difficult, i.e. not firing events on the request until the polyfill is done iterating, then firing the event when it has.
Comment 11 Kyaw Tun 2013-08-30 02:31:29 UTC
Yes, but continuePrimary is doing only one thing. So it is easier to implement polyfill. It is not necessary to attach and detach events handlers. Also polyfill will not introduce new bug to continue function.
Comment 12 Alec Flett 2013-11-09 00:07:34 UTC
I spent some time noodling on this and I think the example in comment 4 is the most compelling. I'm not sure I buy the initial description as a useful case (because for that specific usecase, it seems like you'd really just want to call .get(primaryKey) and examine the indexed value. A cursor doesn't buy you much here.

so for the inner-join-on-indexed-values, I think it would also be useful to have this on IDBIndex.open[Key]Cursor as well - so that you don't have to open a cursor in a bad place if you already have the primary key that you're jumping to.
Comment 13 Joshua Bell 2015-04-23 15:57:54 UTC
IDBCursor#continuePrimaryKey() is implemented in Chrome (behind and experimental flag). We haven't touched the openCursor/openKeyCursor methods yet, though.
Comment 14 Joshua Bell 2015-06-15 23:56:22 UTC
Now tracked as: https://github.com/w3c/IndexedDB/issues/14

One issue noted in that bug: What does this mean for "nextunique" and (more complicated) "prevunique"

(but please put comments on that issue instead)