Remove expensive left joins and cascading text foreign key deletes from the mirror

RESOLVED FIXED in Firefox 60

Status

()

enhancement
RESOLVED FIXED
a year ago
a year ago

People

(Reporter: lina, Assigned: lina)

Tracking

(Blocks 1 bug)

unspecified
Firefox 60
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox60 fixed)

Details

Attachments

(3 attachments)

This is currently very slow for large trees.

I created a test mirror with 40k bookmarks, and jury-rigged xpcshell to use a test profile across runs (note to future self: change https://searchfox.org/mozilla-central/rev/84cea84b12145d752e50ddca6be5462c38510e35/testing/xpcshell/runxpcshelltests.py#369-378 to point to a fixed directory).

* It took 25 seconds to insert 40k records into the mirror all at once, so bug 1435588 is definitely worth doing.

* Recording observer notifications took over 4 minutes, to the point where the test harness timed out. The LEFT JOIN here is to blame: https://searchfox.org/mozilla-central/rev/f80722d4f3bfb722c5ec53880c4a7efb71285676/toolkit/components/places/SyncedBookmarksMirror.jsm#1242-1243 Since we already know the level when we insert into `items{Added, Moved, Changed}`, we might as well make it a column in the temp table, and avoid the join entirely.

* We definitely want to break weak uploads out into a separate temp table instead of joining on `mergeStates` and `items` (https://searchfox.org/mozilla-central/rev/f80722d4f3bfb722c5ec53880c4a7efb71285676/toolkit/components/places/SyncedBookmarksMirror.jsm#1422-1423,1425-1426). For a tree with 40k bookmarks and no local changes, those joins causes the query to take over 4 minutes. Without the joins, it takes *10ms*.
Changing this bug around a bit, because the merge transaction isn't the bottleneck. With these patches, and bug 1436207, applied:

* It takes about 8 seconds to merge a mirror with 40k items (where `needsMerge = 1`) into an empty `places.sqlite`. 680ms to fetch both sides and build a merged tree, 6 seconds to merge: 1 seconds to populate `mergeStates`, 140ms to check for new tag queries (none), 820ms to insert 40k URLs into `moz_places`, 3 seconds to insert everything and fire the triggers, 280ms to update the structure, and no time for deletions. Recording all observer notifications takes 1.2 seconds, staging outgoing (nothing except the roots) take 650ms, and building records for 4 items and cleaning up temp tables takes 415ms.

* In the opposite scenario, where everything in the mirror is `needsMerge = 0` and all 40k items in Places have `syncChangeCounter = 1`, it takes about 9 seconds. 3 seconds to fetch both sides and build a merged tree. 2 seconds to merge: 1 second to populate `mergeStates`, negligible (~10ms total) time to check for new tag queries and new URLs to insert, 575ms to run the value merge triggers, 105ms for structure merge triggers, and no time for deletions. Recording observer notifications (none) takes negligible (~15ms) time to run the statements, staging takes 375ms, and building records for 40004 items and cleaning up the temp tables takes 3 seconds.

So, we reduce the merge transaction time by 3-5 seconds for a tree of 40k items if we split out recording observer notifications, staging, and building records. It might be worth it eventually, but I like that everything is encapsulated: any error and we roll the whole merge back. Splitting up the merge transaction means we'd need to keep temp state around after we merge, and we'd need another transaction to clean that up. More things that can go wrong, and potentially stale state hanging around after a failed merge, makes me nervous.

Removing the left joins and cascading deletes, on the other hand, gives us a dramatic boost. We go from not being able to finish the test at all in 4 minutes, to under 10 seconds for a large merge that looks like a first sync. That's an easy win.
Summary: Break up the mirror merge transaction and remove expensive joins → Remove expensive left joins and cascading foreign key deletes from the mirror
Comment hidden (mozreview-request)
Mark, please feel free to forward these reviews to Mak if that's more comfortable for you. :-)
Assignee

Comment 6

a year ago
mozreview-review
Comment on attachment 8948872 [details]
Bug 1436215 - Stage outgoing weak uploads in a separate table to avoid an expensive left join.

https://reviewboard.mozilla.org/r/218266/#review224054

::: toolkit/components/places/SyncedBookmarksMirror.jsm:1407
(Diff revision 1)
>                JOIN moz_bookmarks t ON t.id = e.parent
>                JOIN moz_bookmarks r ON r.id = t.parent
> -              WHERE r.guid = :tagsGuid AND
> +              WHERE b.type = :bookmarkType AND
> +                    r.guid = :tagsGuid AND
>                      e.fk = h.id),
> -             (SELECT content FROM annos WHERE itemId = b.id AND
> +             (SELECT a.content FROM moz_items_annos a

While I was here, I also inlined `annos`, and excluded annos and tags by type. In practice, this is unlikely to matter much, but, if I'm understanding the output of `EXPLAIN QUERY PLAN` correctly, SQLite can't use indexes when querying CTEs.
One more thing: frecency calculation is very expensive after a large first sync with URLs that we don't have locally yet. The URLs don't have any visits, but we do give them some weight if they're bookmarked (https://searchfox.org/mozilla-central/rev/84cea84b12145d752e50ddca6be5462c38510e35/toolkit/components/places/SQLFunctions.cpp#706,712-714,718,724,728). I'm not sure how we can avoid this yet, short of adding a `CALCULATE_FRECENCY_FOR_NEW_PLACE` function, or maybe a "base" frecency function that takes the bonus or sampled weights as inputs, instead of querying the history service.

Even though this doesn't block the merge transaction, I think it's still going to lock for the duration of the `UPDATE`, since SQLite runs bare statements in an implicit transaction.

Though it doesn't seem likely, I also wonder if recalculating frecencies for every URL where it's currently -1 (https://searchfox.org/mozilla-central/rev/84cea84b12145d752e50ddca6be5462c38510e35/toolkit/components/places/SyncedBookmarksMirror.jsm#4002-4005), and queuing up writes behind that, is what's causing us to spin and crash in bug 1435446.
Summary: Remove expensive left joins and cascading foreign key deletes from the mirror → Remove expensive left joins and cascading text foreign key deletes from the mirror

Comment 8

a year ago
mozreview-review
Comment on attachment 8948871 [details]
Bug 1436215 - Remove left joins on the Sync merge states table when recording bookmark observer notifications.

https://reviewboard.mozilla.org/r/218264/#review224440
Attachment #8948871 - Flags: review?(markh) → review+

Comment 9

a year ago
mozreview-review
Comment on attachment 8948872 [details]
Bug 1436215 - Stage outgoing weak uploads in a separate table to avoid an expensive left join.

https://reviewboard.mozilla.org/r/218266/#review224442
Attachment #8948872 - Flags: review?(markh) → review+

Comment 10

a year ago
mozreview-review
Comment on attachment 8948873 [details]
Bug 1436215 - Avoid cascading deletes for text foreign keys in the mirror.

https://reviewboard.mozilla.org/r/218268/#review224444

nice!
Attachment #8948873 - Flags: review?(markh) → review+

Comment 12

a year ago
Pushed by kcambridge@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/49d13ed109ab
Remove left joins on the Sync merge states table when recording bookmark observer notifications. r=markh
https://hg.mozilla.org/integration/autoland/rev/fd7646a7efe7
Stage outgoing weak uploads in a separate table to avoid an expensive left join. r=markh
https://hg.mozilla.org/integration/autoland/rev/b5de8b5cd288
Avoid cascading deletes for text foreign keys in the mirror. r=markh
https://hg.mozilla.org/mozilla-central/rev/49d13ed109ab
https://hg.mozilla.org/mozilla-central/rev/fd7646a7efe7
https://hg.mozilla.org/mozilla-central/rev/b5de8b5cd288
Status: ASSIGNED → RESOLVED
Last Resolved: a year ago
Resolution: --- → FIXED
Target Milestone: --- → Firefox 60
See Also: → 1443278
You need to log in before you can comment on or make changes to this bug.