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

Status: RESOLVED FIXED

(Firefox :: Sync, enhancement)

Description

[Lina Butler [:lina]]

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*.

Comment 1

[Lina Butler [:lina]]

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.

Comment 2

[Lina Butler [:lina]]

Attachment: Bug 1436215 - Remove left joins on the Sync merge states table when recording bookmark observer notifications.

Review commit: https://reviewboard.mozilla.org/r/218264/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/218264/

Comment 3

[Lina Butler [:lina]]

Attachment: Bug 1436215 - Stage outgoing weak uploads in a separate table to avoid an expensive left join.

Review commit: https://reviewboard.mozilla.org/r/218266/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/218266/

Comment 4

[Lina Butler [:lina]]

Attachment: Bug 1436215 - Avoid cascading deletes for text foreign keys in the mirror.

These can take minutes to run, while using integer foreign keys takes
milliseconds. The only time we delete from the mirror is in `reset`,
so we can make this more efficient by clearing the `structure` table
first, so that there are no foreign key references to clean up when we
clear `items`. For `itemsToUpload`, we can simply use integer IDs
everywhere.

Review commit: https://reviewboard.mozilla.org/r/218268/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/218268/

Comment 5

[Lina Butler [:lina]]

Mark, please feel free to forward these reviews to Mak if that's more comfortable for you. :-)

Comment 6

[Lina Butler [:lina]]

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.

Comment 7

[Lina Butler [:lina]]

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.

Comment 8

[Mark Hammond [:markh] [:mhammond]]

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

Comment 9

[Mark Hammond [:markh] [:mhammond]]

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

Comment 10

[Mark Hammond [:markh] [:mhammond]]

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!

Comment 11

[Lina Butler [:lina]]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=d0238aadae0958c5ebee4e8183a538e8ab194914

Comment 12

[Pulsebot]

Pushed by [e-mail]:
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

Comment 13

[Cristian Brindusan [:cbrindusan]]

https://hg.mozilla.org/mozilla-central/rev/49d13ed109ab
https://hg.mozilla.org/mozilla-central/rev/fd7646a7efe7
https://hg.mozilla.org/mozilla-central/rev/b5de8b5cd288