--- a/toolkit/components/places/Bookmarks.jsm
+++ b/toolkit/components/places/Bookmarks.jsm
@@ -2307,38 +2307,40 @@ function needsTombstone(item) {
 // in the `moz_bookmarks_deleted` table, and only written for "NORMAL" items.
 // After each sync, `PlacesSyncUtils.bookmarks.pushChanges` drops successfully
 // uploaded tombstones.
 function insertTombstone(db, item, syncChangeDelta) {
   if (!syncChangeDelta || !needsTombstone(item)) {
     return Promise.resolve();
   }
   return db.executeCached(`
-    INSERT INTO moz_bookmarks_deleted (guid, dateRemoved)
-    VALUES (:guid, :dateRemoved)`,
+    INSERT INTO moz_bookmarks_deleted (guid, parentGuid, dateRemoved)
+    VALUES (:guid, :parentGuid, :dateRemoved)`,
     { guid: item.guid,
+      parentGuid: item.parentGuid,
       dateRemoved: PlacesUtils.toPRTime(Date.now()) });
 }
 
 // Inserts tombstones for removed synced items.
 function insertTombstones(db, itemsRemoved, syncChangeDelta) {
   if (!syncChangeDelta) {
     return Promise.resolve();
   }
   let syncedItems = itemsRemoved.filter(needsTombstone);
   if (!syncedItems.length) {
     return Promise.resolve();
   }
   let dateRemoved = PlacesUtils.toPRTime(Date.now());
   let valuesTable = syncedItems.map(item => `(
     ${JSON.stringify(item.guid)},
+    ${JSON.stringify(item.parentGuid)},
     ${dateRemoved}
   )`).join(",");
   return db.execute(`
-    INSERT INTO moz_bookmarks_deleted (guid, dateRemoved)
+    INSERT INTO moz_bookmarks_deleted (guid, parentGuid, dateRemoved)
     VALUES ${valuesTable}`
   );
 }
 
 // Bumps the change counter for all bookmarks with URLs referenced in removed
 // tag folders.
 var addSyncChangesForRemovedTagFolders = async function(db, itemsRemoved, syncChangeDelta) {
   if (!syncChangeDelta) {

--- a/toolkit/components/places/Database.cpp
+++ b/toolkit/components/places/Database.cpp
@@ -1106,18 +1106,26 @@ Database::InitSchema(bool* aDatabaseMigr
       }
 
       // Firefox 55 uses schema version 37.
 
       if (currentSchemaVersion < 38) {
         rv = MigrateV38Up();
         NS_ENSURE_SUCCESS(rv, rv);
       }
+
       // Firefox 56 uses schema version 38.
 
+      if (currentSchemaVersion < 39) {
+        rv = MigrateV39Up();
+        NS_ENSURE_SUCCESS(rv, rv);
+      }
+
+      // Firefox 56 uses schema version 39.
+
       // Schema Upgrades must add migration code here.
 
       rv = UpdateBookmarkRootTitles();
       // We don't want a broken localization to cause us to think
       // the database is corrupt and needs to be replaced.
       MOZ_ASSERT(NS_SUCCEEDED(rv));
     }
   }
@@ -2320,16 +2328,35 @@ Database::MigrateV38Up()
     ));
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   return NS_OK;
 }
 
 nsresult
+Database::MigrateV39Up()
+{
+  MOZ_ASSERT(NS_IsMainThread());
+
+  nsCOMPtr<mozIStorageStatement> stmt;
+  nsresult rv = mMainConn->CreateStatement(NS_LITERAL_CSTRING(
+    "SELECT parentGuid FROM moz_bookmarks_deleted"
+  ), getter_AddRefs(stmt));
+  if (NS_FAILED(rv)) {
+    rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+      "ALTER TABLE moz_bookmarks_deleted ADD COLUMN parentGuid TEXT NOT NULL"
+    ));
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  return NS_OK;
+}
+
+nsresult
 Database::GetItemsWithAnno(const nsACString& aAnnoName, int32_t aItemType,
                            nsTArray<int64_t>& aItemIds)
 {
   nsCOMPtr<mozIStorageStatement> stmt;
   nsresult rv = mMainConn->CreateStatement(NS_LITERAL_CSTRING(
     "SELECT b.id FROM moz_items_annos a "
     "JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id "
     "JOIN moz_bookmarks b ON b.id = a.item_id "

--- a/toolkit/components/places/Database.h
+++ b/toolkit/components/places/Database.h
@@ -14,17 +14,17 @@
 #include "mozilla/storage/StatementCache.h"
 #include "mozilla/Attributes.h"
 #include "nsIEventTarget.h"
 #include "Shutdown.h"
 #include "nsCategoryCache.h"
 
 // This is the schema version. Update it at any schema change and add a
 // corresponding migrateVxx method below.
-#define DATABASE_SCHEMA_VERSION 38
+#define DATABASE_SCHEMA_VERSION 39
 
 // Fired after Places inited.
 #define TOPIC_PLACES_INIT_COMPLETE "places-init-complete"
 // This topic is received when the profile is about to be lost.  Places does
 // initial shutdown work and notifies TOPIC_PLACES_SHUTDOWN to all listeners.
 // Any shutdown work that requires the Places APIs should happen here.
 #define TOPIC_PROFILE_CHANGE_TEARDOWN "profile-change-teardown"
 // Fired when Places is shutting down.  Any code should stop accessing Places
@@ -298,16 +298,17 @@ protected:
   nsresult MigrateV31Up();
   nsresult MigrateV32Up();
   nsresult MigrateV33Up();
   nsresult MigrateV34Up();
   nsresult MigrateV35Up();
   nsresult MigrateV36Up();
   nsresult MigrateV37Up();
   nsresult MigrateV38Up();
+  nsresult MigrateV39Up();
 
   nsresult UpdateBookmarkRootTitles();
 
   friend class ConnectionShutdownBlocker;
 
   int64_t CreateMobileRoot();
   nsresult GetItemsWithAnno(const nsACString& aAnnoName, int32_t aItemType,
                             nsTArray<int64_t>& aItemIds);

--- a/toolkit/components/places/PlacesSyncUtils.jsm
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -419,22 +419,26 @@ const BookmarkSyncUtils = PlacesSyncUtil
                      b.syncChangeCounter + 1, b.syncStatus
               FROM moz_bookmarks b
               JOIN moz_bookmarks_tracked t ON b.guid = t.guid`);
 
             // Insert tombstones for nonexistent tracked items, using the most
             // recent deletion date for more accurate reconciliation. We assume
             // the tracked item belongs to a synced root.
             await db.executeCached(`
-              INSERT OR REPLACE INTO moz_bookmarks_deleted (guid, dateRemoved)
-              SELECT t.guid, MAX(IFNULL((SELECT dateRemoved FROM moz_bookmarks_deleted
-                                         WHERE guid = t.guid), 0), t.time)
+              INSERT OR REPLACE INTO moz_bookmarks_deleted (guid, parentGuid,
+                                                            dateRemoved)
+              SELECT t.guid, IFNULL(p.guid, :unfiledGuid),
+                     MAX(IFNULL((SELECT dateRemoved FROM moz_bookmarks_deleted
+                                 WHERE guid = t.guid), 0), t.time)
               FROM moz_bookmarks_tracked t
               LEFT JOIN moz_bookmarks b ON t.guid = b.guid
-              WHERE b.guid IS NULL`);
+              LEFT JOIN moz_bookmarks p ON p.id = b.parent
+              WHERE b.guid IS NULL`,
+              { unfiledGuid: PlacesUtils.bookmarks.unfiledGuid });
           } finally {
             await db.executeCached(`DROP TABLE moz_bookmarks_tracked`);
           }
         });
       }
     );
   },
 
@@ -2088,19 +2092,19 @@ var dedupeSyncBookmark = async function(
         { remoteParentGuid });
     }
 
     // The local, duplicate ID is always deleted on the server - but for
     // bookmarks it is a logical delete.
     let localSyncStatus = rows[0].getResultByName("syncStatus");
     if (localSyncStatus == PlacesUtils.bookmarks.SYNC_STATUS.NORMAL) {
       await db.executeCached(`
-        INSERT INTO moz_bookmarks_deleted (guid, dateRemoved)
-        VALUES (:localGuid, :modified)`,
-        { localGuid, modified });
+        INSERT INTO moz_bookmarks_deleted (guid, parentGuid, dateRemoved)
+        VALUES (:localGuid, :localParentGuid, :modified)`,
+        { localGuid, localParentGuid, modified });
     }
   });
 
   let observers = PlacesUtils.bookmarks.getObservers();
   notify(observers, "onItemChanged", [ localId, "guid", false,
                                        remoteGuid,
                                        modified,
                                        bookmarkType,

--- a/toolkit/components/places/nsNavBookmarks.cpp
+++ b/toolkit/components/places/nsNavBookmarks.cpp
@@ -1241,17 +1241,17 @@ nsNavBookmarks::RemoveFolderChildren(int
   if (syncChangeDelta) {
     nsTArray<TombstoneData> tombstones(folderChildrenArray.Length());
     PRTime dateRemoved = RoundedPRNow();
 
     for (uint32_t i = 0; i < folderChildrenArray.Length(); ++i) {
       BookmarkData& child = folderChildrenArray[i];
       if (NeedsTombstone(child)) {
         // Write tombstones for synced children.
-        TombstoneData childTombstone = {child.guid, dateRemoved};
+        TombstoneData childTombstone = {child.guid, folder.guid, dateRemoved};
         tombstones.AppendElement(childTombstone);
       }
       bool isUntagging = child.grandParentId == tagsRootId;
       if (isUntagging) {
         // Bump the change counter for all tagged bookmarks when removing a tag
         // folder.
         rv = AddSyncChangesForBookmarksWithURL(child.url, syncChangeDelta);
         NS_ENSURE_SUCCESS(rv, rv);
@@ -1847,25 +1847,28 @@ nsNavBookmarks::AddSyncChangesForBookmar
 
 nsresult
 nsNavBookmarks::InsertTombstone(const BookmarkData& aBookmark)
 {
   if (!NeedsTombstone(aBookmark)) {
     return NS_OK;
   }
   nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
-    "INSERT INTO moz_bookmarks_deleted (guid, dateRemoved) "
-    "VALUES (:guid, :date_removed)"
+    "INSERT INTO moz_bookmarks_deleted (guid, parentGuid, dateRemoved) "
+    "VALUES (:guid, :parent_guid, :date_removed)"
   );
   NS_ENSURE_STATE(stmt);
   mozStorageStatementScoper scoper(stmt);
 
   nsresult rv = stmt->BindUTF8StringByName(NS_LITERAL_CSTRING("guid"),
                                            aBookmark.guid);
   NS_ENSURE_SUCCESS(rv, rv);
+  rv = stmt->BindUTF8StringByName(NS_LITERAL_CSTRING("parent_guid"),
+                                  aBookmark.parentGuid);
+  NS_ENSURE_SUCCESS(rv, rv);
   rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("date_removed"),
                              RoundedPRNow());
   NS_ENSURE_SUCCESS(rv, rv);
 
   rv = stmt->Execute();
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
@@ -1874,46 +1877,48 @@ nsNavBookmarks::InsertTombstone(const Bo
 
 nsresult
 nsNavBookmarks::InsertTombstones(const nsTArray<TombstoneData>& aTombstones)
 {
   if (aTombstones.IsEmpty()) {
     return NS_OK;
   }
 
-  size_t maxRowsPerChunk = SQLITE_MAX_VARIABLE_NUMBER / 2;
+  size_t maxRowsPerChunk = SQLITE_MAX_VARIABLE_NUMBER / 3;
   for (uint32_t startIndex = 0; startIndex < aTombstones.Length(); startIndex += maxRowsPerChunk) {
     size_t rowsPerChunk = std::min(maxRowsPerChunk, aTombstones.Length() - startIndex);
 
     // Build a query to insert all tombstones in a single statement, chunking to
     // avoid the SQLite bound parameter limit.
     nsAutoCString tombstonesToInsert;
-    tombstonesToInsert.AppendLiteral("VALUES (?, ?)");
+    tombstonesToInsert.AppendLiteral("VALUES (?, ?, ?)");
     for (uint32_t i = 1; i < rowsPerChunk; ++i) {
-      tombstonesToInsert.AppendLiteral(", (?, ?)");
+      tombstonesToInsert.AppendLiteral(", (?, ?, ?)");
     }
 #ifdef DEBUG
-    MOZ_ASSERT(tombstonesToInsert.CountChar('?') == rowsPerChunk * 2,
+    MOZ_ASSERT(tombstonesToInsert.CountChar('?') == rowsPerChunk * 3,
                "Expected one binding param per column for each tombstone");
 #endif
 
     nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
       NS_LITERAL_CSTRING("INSERT INTO moz_bookmarks_deleted "
-        "(guid, dateRemoved) ") +
+        "(guid, parentGuid, dateRemoved) ") +
       tombstonesToInsert
     );
     NS_ENSURE_STATE(stmt);
     mozStorageStatementScoper scoper(stmt);
 
     uint32_t paramIndex = 0;
     nsresult rv;
     for (uint32_t i = 0; i < rowsPerChunk; ++i) {
       const TombstoneData& tombstone = aTombstones[startIndex + i];
       rv = stmt->BindUTF8StringByIndex(paramIndex++, tombstone.guid);
       NS_ENSURE_SUCCESS(rv, rv);
+      rv = stmt->BindUTF8StringByIndex(paramIndex++, tombstone.parentGuid);
+      NS_ENSURE_SUCCESS(rv, rv);
       rv = stmt->BindInt64ByIndex(paramIndex++, tombstone.dateRemoved);
       NS_ENSURE_SUCCESS(rv, rv);
     }
 
     rv = stmt->Execute();
     NS_ENSURE_SUCCESS(rv, rv);
   }
 

--- a/toolkit/components/places/nsNavBookmarks.h
+++ b/toolkit/components/places/nsNavBookmarks.h
@@ -56,16 +56,17 @@ namespace places {
     nsCString property;
     bool isAnnotation;
     nsCString newValue;
     nsCString oldValue;
   };
 
   struct TombstoneData {
     nsCString guid;
+    nsCString parentGuid;
     PRTime dateRemoved;
   };
 
   typedef void (nsNavBookmarks::*ItemVisitMethod)(const ItemVisitData&);
   typedef void (nsNavBookmarks::*ItemChangeMethod)(const ItemChangeData&);
 
   enum BookmarkDate {
     DATE_ADDED = 0

--- a/toolkit/components/places/nsPlacesTables.h
+++ b/toolkit/components/places/nsPlacesTables.h
@@ -118,16 +118,17 @@
 // This table stores tombstones for bookmarks with SYNC_STATUS_NORMAL. We
 // upload tombstones during a sync, and delete them from this table on success.
 // If Sync is disconnected, we'll delete all stored tombstones. If Sync is
 // never set up, we'll never write new tombstones, since all bookmarks will stay
 // in SYNC_STATUS_NEW.
 #define CREATE_MOZ_BOOKMARKS_DELETED NS_LITERAL_CSTRING( \
   "CREATE TABLE moz_bookmarks_deleted (" \
     "  guid TEXT PRIMARY KEY" \
+    ", parentGuid TEXT NOT NULL" \
     ", dateRemoved INTEGER NOT NULL DEFAULT 0" \
   ")" \
 )
 
 #define CREATE_MOZ_KEYWORDS NS_LITERAL_CSTRING( \
   "CREATE TABLE moz_keywords (" \
     "  id INTEGER PRIMARY KEY AUTOINCREMENT" \
     ", keyword TEXT UNIQUE" \