The Places side of this Dogear issue. Dogear now flags local folders with structure changes, and emits completion ops for us to apply. This means we can avoid repeated full table scans on the local tree.

Another quick win: fetch_{local, remote}_tree runs a full table scan, anyway...and fetch_new_{local, remote}_contents runs the same scan again. We can avoid the second scan entirely, for both local and remote contents, by inflating content info as we build the tree! 🎉

This commit reduces the number of database writes and table scans
needed to merge synced bookmarks.

• Remove fetchNew{Local, Remote}Contents. Fetching the tree already
  scans the table, so we can piggyback on it to fetch content info for
  deduping.
• Store completion ops in temp tables to only update changed parts of
  the local tree, and remove the mergeStates table and views.
• Replace the itemsToMerge view with an indexed itemsToApply temp
  table.
• Replace the updateGuidsAndSyncFlags trigger with a changeGuidOps
  table and a changeGuids trigger.
• Replace the updateLocalItems trigger with an apply_remote_items
  function to bulk upsert new and updated items.
• Replace the structureToMerge view with an
  applyNewLocalStructureOps table that holds parents and positions
  for moved items, and an applyNewLocalStructure trigger to update
  them.
• Remove tombstones for revived items, update change counters, and flag
  mirror items as merged directly in update_local_items_in_places,
  instead of indirecting through temp tables.
• Don't mark items flagged for reupload as merged, since we'll write
  them back to the mirror after upload.
• Use a scalar subquery instead of a join in the localTags view to
  look up the tags root ID.
• Replace relatedIdsToReupload with a Store::prepare method that
  flags all bookmarks with keyword-URL mismatches for reupload.
• Trigger frecency updates for origins once, not for every item.

This also fixes some edge cases:

• Update root positions correctly after deleting a non-syncable root
  or item.
• Keyword-URL mismatches may reupload more items than before, but now
  ensure that all bookmarks with the same URL have the same keyword.
• Only set items with deduped GUIDs to SYNC_STATUS_NORMAL after
  merging.
• Bump the last modified time for modified items only.

Before this change, the bookmarks mirror used a cloned Places
connection for reads and writes. This avoided interleaving writes from
Sync and other Places consumers, where mozStorageTransaction or
Sqlite.jsm would see that a transaction was already in progress, and
execute statements as part of that transaction.

However, using a separate connection caused write contention, wedging
the main connection in an infinite SQLITE_BUSY retry loop. This
blocked all writes to Places until shutdown, at which point we'd hang
waiting to shut down the async thread. Bug 1435446 reduced this, but
didn't eliminate the hangs entirely.

Since the mirror first landed, we've made three changes, to the point
that using the main connection is feasible now:

1. Merging and application happen in Rust. This means we run everything
   on the async thread, so no other async statements can run during
   merging.
2. Most uses of the synchronous bookmarks API have been removed. The
   only remaining caller is the tagging service, and we never sync the
   tags root.
3. We only update parents and positions for items that actually changed,
   instead of walking the entire tree.

To that end, this commit removes the cloned connection, and uses the
main Places connection directly.

Depends on D39889

Most of the slow merges we've seen have been on Windows, I'll post some benchmarks with a copy of my Places DB (4k+ bookmarks, probably fragmented since I haven't ANALYZEd it recently) later this week.

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

https://hg.mozilla.org/mozilla-central/rev/338b1c471939
https://hg.mozilla.org/mozilla-central/rev/663b94830a6b