--- a/toolkit/components/places/Bookmarks.jsm
+++ b/toolkit/components/places/Bookmarks.jsm
@@ -1429,20 +1429,20 @@ Task.async(function* (db, folderGuids, o
          UNION ALL
          SELECT id FROM moz_bookmarks
          JOIN descendants ON parent = did
        )
        SELECT b.id AS _id, b.parent AS _parentId, b.position AS 'index',
               b.type, url, b.guid, p.guid AS parentGuid, b.dateAdded,
               b.lastModified, b.title, p.parent AS _grandParentId,
               NULL AS _childCount
-       FROM moz_bookmarks b
+       FROM descendants
+       JOIN moz_bookmarks b ON did = b.id
        JOIN moz_bookmarks p ON p.id = b.parent
-       LEFT JOIN moz_places h ON b.fk = h.id
-       WHERE b.id IN descendants`, { folderGuid });
+       LEFT JOIN moz_places h ON b.fk = h.id`, { folderGuid });
 
     itemsRemoved = itemsRemoved.concat(rowsToItemsArray(rows));
 
     yield db.executeCached(
       `WITH RECURSIVE
        descendants(did) AS (
          SELECT b.id FROM moz_bookmarks b
          JOIN moz_bookmarks p ON b.parent = p.id

--- a/toolkit/components/places/tests/bookmarks/test_bookmarks_eraseEverything.js
+++ b/toolkit/components/places/tests/bookmarks/test_bookmarks_eraseEverything.js
@@ -76,11 +76,37 @@ add_task(function* test_eraseEverything_
   // Ensure the roots have not been removed.
   Assert.ok(yield PlacesUtils.bookmarks.fetch(PlacesUtils.bookmarks.unfiledGuid));
   Assert.ok(yield PlacesUtils.bookmarks.fetch(PlacesUtils.bookmarks.toolbarGuid));
   Assert.ok(yield PlacesUtils.bookmarks.fetch(PlacesUtils.bookmarks.menuGuid));
   Assert.ok(yield PlacesUtils.bookmarks.fetch(PlacesUtils.bookmarks.tagsGuid));
   Assert.ok(yield PlacesUtils.bookmarks.fetch(PlacesUtils.bookmarks.rootGuid));
 });
 
-function run_test() {
-  run_next_test();
-}
+add_task(function* test_eraseEverything_reparented() {
+  // Create a folder with 1 bookmark in it...
+  let folder1 = yield PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+    type: PlacesUtils.bookmarks.TYPE_FOLDER
+  });
+  let bookmark1 = yield PlacesUtils.bookmarks.insert({
+    parentGuid: folder1.guid,
+    url: "http://example.com/"
+  });
+  // ...and a second folder.
+  let folder2 = yield PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+    type: PlacesUtils.bookmarks.TYPE_FOLDER
+  });
+
+  // Reparent the bookmark to the 2nd folder.
+  bookmark1.parentGuid = folder2.guid;
+  yield PlacesUtils.bookmarks.update(bookmark1);
+
+  // Erase everything.
+  yield PlacesUtils.bookmarks.eraseEverything();
+
+  // All the above items should no longer be in the GUIDHelper cache.
+  for (let guid of [folder1.guid, bookmark1.guid, folder2.guid]) {
+    yield Assert.rejects(PlacesUtils.promiseItemId(guid),
+                         /no item found for the given GUID/);
+  }
+});

--- a/toolkit/components/places/tests/bookmarks/test_bookmarks_notifications.js
+++ b/toolkit/components/places/tests/bookmarks/test_bookmarks_notifications.js
@@ -358,42 +358,87 @@ add_task(function* eraseEverything_notif
                                                     parentGuid: PlacesUtils.bookmarks.menuGuid,
                                                     url: new URL("http://example.com/") });
   let menuBmId = yield PlacesUtils.promiseItemId(menuBm.guid);
   let menuBmParentId = yield PlacesUtils.promiseItemId(menuBm.parentGuid);
 
   let observer = expectNotifications();
   yield PlacesUtils.bookmarks.eraseEverything();
 
+  // Bookmarks should always be notified before their parents.
   observer.check([ { name: "onItemRemoved",
+                     arguments: [ itemId, parentId, bm.index, bm.type,
+                                  bm.url, bm.guid, bm.parentGuid,
+                                  Ci.nsINavBookmarksService.SOURCE_DEFAULT ] },
+                   { name: "onItemRemoved",
                      arguments: [ folder2Id, folder2ParentId, folder2.index,
                                   folder2.type, null, folder2.guid,
                                   folder2.parentGuid,
                                   Ci.nsINavBookmarksService.SOURCE_DEFAULT ] },
                    { name: "onItemRemoved",
-                     arguments: [ itemId, parentId, bm.index, bm.type,
-                                  bm.url, bm.guid, bm.parentGuid,
-                                  Ci.nsINavBookmarksService.SOURCE_DEFAULT ] },
-                   { name: "onItemRemoved",
                      arguments: [ folder1Id, folder1ParentId, folder1.index,
                                   folder1.type, null, folder1.guid,
                                   folder1.parentGuid,
                                   Ci.nsINavBookmarksService.SOURCE_DEFAULT ] },
                    { name: "onItemRemoved",
                      arguments: [ menuBmId, menuBmParentId,
                                   menuBm.index, menuBm.type,
                                   menuBm.url, menuBm.guid,
                                   menuBm.parentGuid,
                                   Ci.nsINavBookmarksService.SOURCE_DEFAULT ] },
                     { name: "onItemRemoved",
                      arguments: [ toolbarBmId, toolbarBmParentId,
                                   toolbarBm.index, toolbarBm.type,
                                   toolbarBm.url, toolbarBm.guid,
                                   toolbarBm.parentGuid,
-                                  Ci.nsINavBookmarksService.SOURCE_DEFAULT ] }
+                                  Ci.nsINavBookmarksService.SOURCE_DEFAULT ] },
+                 ]);
+});
+
+add_task(function* eraseEverything_reparented_notification() {
+  // Let's start from a clean situation.
+  yield PlacesUtils.bookmarks.eraseEverything();
+
+  let folder1 = yield PlacesUtils.bookmarks.insert({ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+                                                     parentGuid: PlacesUtils.bookmarks.unfiledGuid });
+  let folder1Id = yield PlacesUtils.promiseItemId(folder1.guid);
+  let folder1ParentId = yield PlacesUtils.promiseItemId(folder1.parentGuid);
+
+  let bm = yield PlacesUtils.bookmarks.insert({ type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+                                                parentGuid: folder1.guid,
+                                                url: new URL("http://example.com/") });
+  let itemId = yield PlacesUtils.promiseItemId(bm.guid);
+
+  let folder2 = yield PlacesUtils.bookmarks.insert({ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+                                                     parentGuid: PlacesUtils.bookmarks.unfiledGuid });
+  let folder2Id = yield PlacesUtils.promiseItemId(folder2.guid);
+  let folder2ParentId = yield PlacesUtils.promiseItemId(folder2.parentGuid);
+
+  bm.parentGuid = folder2.guid;
+  bm = yield PlacesUtils.bookmarks.update(bm);
+  let parentId = yield PlacesUtils.promiseItemId(bm.parentGuid);
+
+  let observer = expectNotifications();
+  yield PlacesUtils.bookmarks.eraseEverything();
+
+  // Bookmarks should always be notified before their parents.
+  observer.check([ { name: "onItemRemoved",
+                     arguments: [ itemId, parentId, bm.index, bm.type,
+                                  bm.url, bm.guid, bm.parentGuid,
+                                  Ci.nsINavBookmarksService.SOURCE_DEFAULT ] },
+                   { name: "onItemRemoved",
+                     arguments: [ folder2Id, folder2ParentId, folder2.index,
+                                  folder2.type, null, folder2.guid,
+                                  folder2.parentGuid,
+                                  Ci.nsINavBookmarksService.SOURCE_DEFAULT ] },
+                   { name: "onItemRemoved",
+                     arguments: [ folder1Id, folder1ParentId, folder1.index,
+                                  folder1.type, null, folder1.guid,
+                                  folder1.parentGuid,
+                                  Ci.nsINavBookmarksService.SOURCE_DEFAULT ] },
                  ]);
 });
 
 add_task(function* reorder_notification() {
   let bookmarks = [
     { type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
       url: "http://example1.com/",
       parentGuid: PlacesUtils.bookmarks.unfiledGuid

--- a/toolkit/components/places/tests/bookmarks/test_bookmarks_remove.js
+++ b/toolkit/components/places/tests/bookmarks/test_bookmarks_remove.js
@@ -185,15 +185,15 @@ add_task(function* remove_separator() {
 
 add_task(function* test_nested_content_fails_when_not_allowed() {
   let folder1 = yield PlacesUtils.bookmarks.insert({ parentGuid: PlacesUtils.bookmarks.unfiledGuid,
                                                      type: PlacesUtils.bookmarks.TYPE_FOLDER,
                                                      title: "a folder" });
   let folder2 = yield PlacesUtils.bookmarks.insert({ parentGuid: folder1.guid,
                                                      type: PlacesUtils.bookmarks.TYPE_FOLDER,
                                                      title: "a folder" });
-  Assert.rejects(PlacesUtils.bookmarks.remove(folder1, {preventRemovalOfNonEmptyFolders: true}),
-                 /Cannot remove a non-empty folder./);
+  yield Assert.rejects(PlacesUtils.bookmarks.remove(folder1, {preventRemovalOfNonEmptyFolders: true}),
+                       /Cannot remove a non-empty folder./);
 });
 
 function run_test() {
   run_next_test();
 }