728783 - Provide an efficient method to batch-update bookmark positions

Status: VERIFIED FIXED

(Firefox for Android Graveyard :: General, defect)

Description

[Richard Newman [:rnewman]]

I know how to do this: UPDATE using a CASE statement, and we can hack this through a CP URI that takes the GUID => position map as a ContentValues object!

Comment 1

[Richard Newman [:rnewman]]

Attachment: Proposed patch. v1

It builds… now let's see if it works!

Comment 2

[Richard Newman [:rnewman]]

Attachment: Proposed patch. v2

Only one stupid error! Not too bad :D

I have tests that cover this, but you'll have to take my word for it :/

Comment 3

[Lucas Rocha (:lucasr)]

Comment on attachment 598785 [details] [diff] [review]
Proposed patch. v2

Review of attachment 598785 [details] [diff] [review]:
-----------------------------------------------------------------

I'm mixed about this patch. I understand that it's a handy shortcut but would it be better to simply use batched updates instead? I know this is not implemented yet, just thinking about what's the proper long-term path to follow here. I'd like to get some answers before giving r+.

::: mobile/android/base/db/BrowserProvider.java.in
@@ +1032,5 @@
> +     *
> +     * The provided selectionArgs is expected to be an implicit mapping from
> +     * GUID to new position.
> +     */
> +    int updateBookmarkPositions(Uri uri, String[] selectionArgs) {

I wonder why you're not using ContentValues instead of selectionArgs here? It would look a bit more natural to use it...

@@ +1046,5 @@
> +        System.arraycopy(selectionArgs, 0, args, 0, guidsCount);
> +        System.arraycopy(selectionArgs, 0, args, guidsCount, guidsCount);
> +
> +        StringBuilder b = new StringBuilder("UPDATE " + TABLE_BOOKMARKS +
> +                                            " SET " + Bookmarks.POSITION + " = CASE guid");

Strictly speaking, you'd have to ensure all guids are children of the same parent. Maybe ensure the selection has PARENT = some_id?

Comment 4

[Richard Newman [:rnewman]]

Thanks Lucas!

> I'm mixed about this patch.

Yeah, me too :D

> I understand that it's a handy shortcut but
> would it be better to simply use batched updates instead?

Even with batching there'd be multiple queries within the same transaction, and there would also be a ton of ContentValues allocated and processed.

(I actually started this patch by using ContentValues to pass in the indices.)

There are only two ways to achieve what I'm trying to do. For the record, that's "make the position column for a set of items in the store match an external array of GUIDs".

Sync will be calling this update for (worst-case, which is currently "every time") every folder it downloads on each sync. On a first sync, that's every folder, updating the position of every item in the entire database.

(We will set positions as we go, but of course we won't always see folders first, and if there are local items we need to merge the sequences.)


The first way is:

  UPDATE SET position = 3 WHERE _ID IN ('abc', 'def')
  UPDATE SET position = 4 WHERE _ID IN ('ghi')
  ...


This can only be achieved by using cr.applyBatch, which will involve allocating one ContentProviderOperation, one selectionArgs, and one ContentValues per index in the best case, asymptotically to one each of those objects per *record* if we don't have access to all of the children we need to set in one go.

(That is, if we're reordering folder by folder, we issue one UPDATE per *item*. If we're reordering a number of folders, we can reduce that to one UPDATE per index, at the risk of making the calling code slightly hairier and allocating more arrays.)


The second is

  UPDATE SET position = CASE guid
    WHEN 'abc' THEN 3
    WHEN 'def' THEN 3
    WHEN "ghi' THEN 4
  WHERE guid IN ('abc', 'def', 'ghi')


Obviously this requires only one query. In principle this can update the entire database at once; in practice, we're working folder-by-folder.

This cannot be achieved through the CR/CP API, because the update operations only admit simple ContentValues.


I went for the second approach, of course.


The question then becomes "how can I pass in an ordered sequence of GUIDs in a single call through the CR API?".

There are only two sane ways: a ContentValues mapping GUID to index (more general, but requires more processing and allows errors, such as out-of-order sequences with duplicates), or using selectionArgs as a way to get an array of strings from calling code to the CP. Because we always want to set a contiguous, 0-indexed sequence of positions, passing in an array seemed like the right hack.


The ultimate, general approach is for callers to suck it up, allocate a bunch of objects, and do things item-by-item, using batching to reduce round-trip overhead. 

This is such a high-throughput special case that I figured it was worth… special-casing.


> > +    int updateBookmarkPositions(Uri uri, String[] selectionArgs) {
> 
> I wonder why you're not using ContentValues instead of selectionArgs here?
> It would look a bit more natural to use it...

Partly explained above, but using an array gives us a natural, complete, 0-indexed order; using ContentValues is much less efficient and requires more validation and processing on each end.

(That is, ContentValues is a HashMap, so we'd be allocating a pile of Entry objects, a pile of Longs, etc., only to walk the ContentValues with an iterator on the other end to… populate an array of Strings!)

Would it be better if I renamed the argument to "guids"?


> Strictly speaking, you'd have to ensure all guids are children of the same
> parent.

Not really "have to" -- the operation is valid (if less meaningful) without it, and pre-UPDATE validation is expensive.

> Maybe ensure the selection has PARENT = some_id?

There's no selection per se; only a lookup by GUID using IN. We could add a "parent =" clause, but all that would do is _not_ set the positions of items that aren't correctly parented… which would leave gaps in the ones that are, and I'm not sure that buys us much.

That is, if we're ever going to hit this error case, then we could already be overlaying existing items with this query, and Fennec is OK with that.

We could check the row count by calling changes() within the same transaction, and roll back and try to throw some kind of exception, but I don't think that would buy us much either for the expense.

Comment 5

[Lucas Rocha (:lucasr)]

Comment on attachment 598785 [details] [diff] [review]
Proposed patch. v2

> Would it be better if I renamed the argument to "guids"?

Yes, it would make it clearer.

Ok, I think the throughput gain is worth the hack here. I just don't want us to abuse it and add a lot of those things in our CP (given that we're mangling the CP API to do something very... unique).

Could you please a comment somewhere where we handle the POSITIONS URI explaining why this "shortcut" was added? Reference to this bug report would be useful too. Just for future reference.

Comment 6

[Richard Newman [:rnewman]]

Attachment: Patch with review comments addressed.

Added comments, renamed argument. Uploading for posterity.

Also addressed minor safety fear by short-circuit-returning if any of the items in the array is null. Should never come up, but if it does this will have fewer unintended consequences.

Comment 7

[Richard Newman [:rnewman]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/20e74fdabf54

Comment 8

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/20e74fdabf54

Comment 9

[Paul Feher]

Verified fixed on:
Nightly Fennec 13.0a1 (2012-03-02)
20120302031112
http://hg.mozilla.org/mozilla-central/rev/3a7b9e61c263