--- a/toolkit/components/places/SyncedBookmarksMirror.jsm
+++ b/toolkit/components/places/SyncedBookmarksMirror.jsm
@@ -172,18 +172,20 @@ class SyncedBookmarksMirror {
           await db.execute(`ATTACH :mirrorPath AS mirror`,
                            { mirrorPath: options.path });
         } else {
           MirrorLog.warn("Unrecoverable error attaching mirror to Places", ex);
           throw ex;
         }
       }
       await db.execute(`PRAGMA foreign_keys = ON`);
-      await migrateMirrorSchema(db);
-      await initializeTempMirrorEntities(db);
+      await db.executeTransaction(async function() {
+        await migrateMirrorSchema(db);
+        await initializeTempMirrorEntities(db);
+      });
     } catch (ex) {
       options.recordTelemetryEvent("mirror", "open", "error",
                                    { why: "initialize" });
       await db.close();
       throw ex;
     }
     return new SyncedBookmarksMirror(db, options);
   }
@@ -1621,16 +1623,33 @@ class SyncedBookmarksMirror {
    * Inflates Sync records for all staged outgoing items.
    *
    * @return {Object.<String, BookmarkChangeRecord>}
    *         A changeset containing Sync record cleartexts for outgoing items
    *         and tombstones, keyed by their Sync record IDs.
    */
   async fetchLocalChangeRecords() {
     let changeRecords = {};
+    let childRecordIdsByLocalParentId = new Map();
+
+    let childGuidRows = await this.db.execute(`
+      SELECT parentId, guid FROM structureToUpload
+      ORDER BY parentId, position`);
+
+    for (let row of childGuidRows) {
+      let localParentId = row.getResultByName("parentId");
+      let childRecordId = PlacesSyncUtils.bookmarks.guidToRecordId(
+        row.getResultByName("guid"));
+      if (childRecordIdsByLocalParentId.has(localParentId)) {
+        let childRecordIds = childRecordIdsByLocalParentId.get(localParentId);
+        childRecordIds.push(childRecordId);
+      } else {
+        childRecordIdsByLocalParentId.set(localParentId, [childRecordId]);
+      }
+    }
 
     let itemRows = await this.db.execute(`
       SELECT id, syncChangeCounter, guid, isDeleted, type, isQuery,
              smartBookmarkName, IFNULL(tagFolderName, "") AS tagFolderName,
              loadInSidebar, keyword, tags, url, IFNULL(title, "") AS title,
              description, feedURL, siteURL, position, parentGuid,
              IFNULL(parentTitle, "") AS parentTitle, dateAdded
       FROM itemsToUpload`);
@@ -1758,25 +1777,19 @@ class SyncedBookmarksMirror {
             parentName: row.getResultByName("parentTitle"),
             dateAdded,
             title: row.getResultByName("title"),
           };
           let description = row.getResultByName("description");
           if (description) {
             folderCleartext.description = description;
           }
-          let childGuidRows = await this.db.executeCached(`
-            SELECT guid FROM structureToUpload
-            WHERE parentId = :id
-            ORDER BY position`,
-            { id: row.getResultByName("id") });
-          folderCleartext.children = childGuidRows.map(row => {
-            let childGuid = row.getResultByName("guid");
-            return PlacesSyncUtils.bookmarks.guidToRecordId(childGuid);
-          });
+          let localId = row.getResultByName("id");
+          let childRecordIds = childRecordIdsByLocalParentId.get(localId);
+          folderCleartext.children = childRecordIds || [];
           changeRecords[recordId] = new BookmarkChangeRecord(
             syncChangeCounter, folderCleartext);
           continue;
         }
 
         case PlacesUtils.bookmarks.TYPE_SEPARATOR: {
           let separatorCleartext = {
             id: recordId,
@@ -1849,27 +1862,25 @@ function isDatabaseCorrupt(error) {
 }
 
 /**
  * Migrates the mirror database schema to the latest version.
  *
  * @param {Sqlite.OpenedConnection} db
  *        The mirror database connection.
  */
-function migrateMirrorSchema(db) {
-  return db.executeTransaction(async function() {
-    let currentSchemaVersion = await db.getSchemaVersion("mirror");
-    if (currentSchemaVersion < 1) {
-      await initializeMirrorDatabase(db);
-    }
-    // Downgrading from a newer profile to an older profile rolls back the
-    // schema version, but leaves all new columns in place. We'll run the
-    // migration logic again on the next upgrade.
-    await db.setSchemaVersion(MIRROR_SCHEMA_VERSION, "mirror");
-  });
+async function migrateMirrorSchema(db) {
+  let currentSchemaVersion = await db.getSchemaVersion("mirror");
+  if (currentSchemaVersion < 1) {
+    await initializeMirrorDatabase(db);
+  }
+  // Downgrading from a newer profile to an older profile rolls back the
+  // schema version, but leaves all new columns in place. We'll run the
+  // migration logic again on the next upgrade.
+  await db.setSchemaVersion(MIRROR_SCHEMA_VERSION, "mirror");
 }
 
 /**
  * Initializes a new mirror database, creating persistent tables, indexes, and
  * roots.
  *
  * @param {Sqlite.OpenedConnection} db
  *        The mirror database connection.

--- a/toolkit/components/places/tests/sync/test_bookmark_deletion.js
+++ b/toolkit/components/places/tests/sync/test_bookmark_deletion.js
@@ -582,23 +582,16 @@ add_task(async function test_move_to_new
   await PlacesUtils.bookmarks.eraseEverything();
   await PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(async function test_nonexistent_on_one_side() {
   let buf = await openMirror("nonexistent_on_one_side");
 
   info("Set up empty mirror");
-  // Previous tests change the menu's date added time; reset it to a predictable
-  // value.
-  let menuDateAdded = new Date();
-  await PlacesUtils.bookmarks.update({
-    guid: PlacesUtils.bookmarks.menuGuid,
-    dateAdded: menuDateAdded,
-  });
   await PlacesTestUtils.markBookmarksAsSynced();
 
   // A doesn't exist in the mirror.
   info("Create local tombstone for nonexistent remote item A");
   await PlacesUtils.bookmarks.insert({
     guid: "bookmarkAAAA",
     parentGuid: PlacesUtils.bookmarks.menuGuid,
     title: "A",
@@ -617,30 +610,33 @@ add_task(async function test_nonexistent
     deleted: true
   }]);
 
   info("Apply remote");
   let changesToUpload = await buf.apply();
   deepEqual(await buf.fetchUnmergedGuids(), ["bookmarkBBBB"],
     "Should leave B unmerged");
 
+  let menuInfo = await PlacesUtils.bookmarks.fetch(
+    PlacesUtils.bookmarks.menuGuid);
+
   // We should still upload a record for the menu, since we changed its
   // children when we added then removed A.
   deepEqual(changesToUpload, {
     menu: {
       tombstone: false,
       counter: 2,
       synced: false,
       cleartext: {
         id: "menu",
         type: "folder",
         parentid: "places",
         hasDupe: true,
         parentName: "",
-        dateAdded: menuDateAdded.getTime(),
+        dateAdded: menuInfo.dateAdded.getTime(),
         title: BookmarksMenuTitle,
         children: [],
       },
     },
   });
 
   await buf.finalize();
   await PlacesUtils.bookmarks.eraseEverything();