Investigate Bookmarks::Reorder behavior with several thousands bookmarks

ASSIGNED
Assigned to

Status

()

P2
normal
ASSIGNED
2 years ago
6 months ago

People

(Reporter: mak, Assigned: mak)

Tracking

(Blocks: 1 bug, {perf})

Trunk
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox54 affected)

Details

(Whiteboard: [fxsearch])

(Assignee)

Description

2 years ago
It can build very large temporary values tables, we should investigate both performance and stability.
(Assignee)

Comment 1

2 years ago
ni myself to not lose track of this.
Flags: needinfo?(mak77)
Could we use a TEMP TABLE instead of WITH?
(Assignee)

Comment 3

2 years ago
(In reply to Kit Cambridge [:kitcambridge] from comment #2)
> Could we use a TEMP TABLE instead of WITH?

Yes, it's one of the possibilities. But we should first figure out if we can reproduce the crash in bug 1309696, and then try to understand if it's effectively more efficient, now that VALUES would work properly (https://bugzilla.mozilla.org/show_bug.cgi?id=1309696#c29). How to measure that is still TBD, maybe we could profile the 2 approaches. Clock time could also be a simple first step, if one approach takes double the time than the other one, there isn't much to discuss.
(Assignee)

Comment 4

2 years ago
I'll try to reproduce the crash and see.
Assignee: nobody → mak77
Flags: needinfo?(mak77)
(Assignee)

Comment 5

2 years ago
So, using a temp table doesn't really help, because we still need to populate it. To do that we either need to use VALUES, and we're back to the starting point, or use a lot of inserts, and then the overhead may be measurable. And using a TEMP table from a quick wall clock check doesn't help.
Bug 483318 could maybe help, but I'm not completely sure it wouldn't still hit the large VALUES case.

I was evaluating doing this in chunks, but the self-join on the reorder table requires the table to be complete, thus we can't use WITH, and if we use a temp table, we may have to also populate it in chunks. All of this sounds like lots of complication, and reorder would still be too slow.

I wonder if we should give up on making reorder take a list of guids, and rather just order by title, that would probably make the whole thing much simpler.
And it wouldn't fire onItemMoved, it would rather fire a new onChildrenReordered (Chrome-parity) notification, or something like that.

At this point, I don't have any short term ideas to solve this without the Sqlite update (that we'll try to uplift).
Since Sync is the only consumer, and the other consumer will be the the UI (that sorts by title), would my proposal (only sort by title, or by a provided enum) and notification work for you?
Flags: needinfo?(kit)
(Assignee)

Comment 6

2 years ago
The issue I could see here, is that it may be hard to skip sorting like we did in bug 1324503. I'd probably suggest we try to first design a sorting that works for your needs, and then later verify how to satisfy the single UI need. Any ideas of an algorithm that would satisfy Sync is welcome.
(Assignee)

Updated

2 years ago
Blocks: 1319530
(Assignee)

Comment 7

2 years ago
The UI sorting is currently done in a little bit special way, and that may complicate things. This is why we implemented reorder the way it is:
1. we sort between separators. Practically if there's a separator between group A and B, we sort group A and B separately.
2. Folders come before bookmarks.
3. Finally we use localeCompare.

These add complications to do the whole thing in SQL, even just the localeCompare would require the ICU extension.
Unfortunately, I don't think that would work, unless we also prevent people from dragging and dropping to reorder bookmarks in the UI. Sync "just" syncs the order of a folder's children. If we enforced sorting all bookmarks by title, URL, date modified, etc., we could change `reorder` to behave as you suggest. As long as we allow people to order their own bookmarks, though, we have to sync and apply the full order.
Flags: needinfo?(kit)
(Assignee)

Comment 9

2 years ago
(In reply to Kit Cambridge [:kitcambridge] from comment #8)
> Unfortunately, I don't think that would work, unless we also prevent people
> from dragging and dropping to reorder bookmarks in the UI. Sync "just" syncs
> the order of a folder's children.

So, this means every time even a single bookmark is moved, Sync does a full reorder on the other side?
Flags: needinfo?(kit)
(Assignee)

Comment 10

2 years ago
note that, regardless, I'd like to move this to a single notification. Would that work for Sync? I see it still listens to onItemMoved in various points (I actually thought with tracking in Places the observer wasn't needed anymore).
(In reply to Marco Bonardo [::mak] from comment #5)
> So, using a temp table doesn't really help, because we still need to
> populate it. To do that we either need to use VALUES, and we're back to the
> starting point, or use a lot of inserts, and then the overhead may be
> measurable.

That's what I was thinking. We do lots of inserts, chunking by `SQLITE_MAX_VARIABLE_NUMBER`, and using binding params to keep the query size down. That would still increase the wall clock time, but we'll only end up with a single statement for the common case. For 10k bookmarks, that's 11 statements to fill the table.
(In reply to Marco Bonardo [::mak] from comment #9)
> So, this means every time even a single bookmark is moved, Sync does a full
> reorder on the other side?

Yes. :-( Sync stores the order of the child GUIDs in the parent's record (something like `{ id: "toolbar", type: "folder", children: ["childguid001", "childguid002", ...] }`). On the other side, it passes the children array directly to `PlacesUtils.bookmarks.reorder`.

(In reply to Marco Bonardo [::mak] from comment #10)
> note that, regardless, I'd like to move this to a single notification. Would
> that work for Sync? I see it still listens to onItemMoved in various points
> (I actually thought with tracking in Places the observer wasn't needed
> anymore).

That's totally fine. Sync only uses the observer notifications to know when to sync, not what to sync.
Flags: needinfo?(kit)
(Assignee)

Comment 13

2 years ago
(In reply to Kit Cambridge [:kitcambridge] from comment #12)
> (In reply to Marco Bonardo [::mak] from comment #9)
> > So, this means every time even a single bookmark is moved, Sync does a full
> > reorder on the other side?
> 
> Yes. :-( Sync stores the order of the child GUIDs in the parent's record
> (something like `{ id: "toolbar", type: "folder", children: ["childguid001",
> "childguid002", ...] }`). On the other side, it passes the children array
> directly to `PlacesUtils.bookmarks.reorder`.

Since we have the original array and the expected one, we could do a pre-analysis and run a few update() calls instead of a full reorder, when the number of moves is smaller than a threshold (something like <= 5). It would be much cheaper in cases where the folder has a lot of children, like this case.
We'll have to suppress onItemMoved notifications for this special path, we'll always fire onChildrenReordered when reorder is invoked.
(Assignee)

Updated

2 years ago
Priority: P1 → P2
Whiteboard: [fxsearch]
(Assignee)

Updated

2 years ago
Status: NEW → ASSIGNED
(Assignee)

Updated

2 years ago
Keywords: perf
FWIW, I've been running with 19k bookmarks and was trying to work out why sync was hanging. It turns out that reordering 10k bookmarks ended up getting killed after 4 minutes, before aborting with:

> console.error: 
>   Message: Error: Transaction timeout, most likely caused by unresolved pending work.
>   Stack:
>     executeTransaction/promise</timeoutPromise</<@resource://gre/modules/Sqlite.jsm:646:33
> setTimeout_timer@resource://gre/modules/Timer.jsm:30:5

Subsequent attempts to reorder a far smaller number of children also hung, but harder - I *suspect* that the timeout killer isn't really cleaning up (ie, I'm not sure if the original timed-out reorder is still happening - CPU is at 100% and it's been well over 10 minutes now). The initial hang appears to be the "with sorting" query at http://searchfox.org/mozilla-central/rev/5e1e8d2f244bd8c210a578ff1f65c3b720efe34e/toolkit/components/places/Bookmarks.jsm#1874
(Assignee)

Comment 15

2 years ago
just as a data fact, our users don't have that many bookmarks. Only 0.8% has more than 8k, and I suspect many of those are tags created by add-ons.
(Assignee)

Comment 16

2 years ago
yes, the timeout unblocks the Sqlite.jsm queue, but doesn't stop the work. If a query is on-flight there's no safe way to stop it. There is an API for that, but it's risky since it stops any ongoing work, so it could be misused and cause coherency issues.
Duplicate of this bug: 1385604
Duplicate of this bug: 1397163
You need to log in before you can comment on or make changes to this bug.