--- a/services/sync/modules/engines/bookmarks.js
+++ b/services/sync/modules/engines/bookmarks.js
@@ -426,21 +426,17 @@ BookmarksEngine.prototype = {
     let mapped = this._mapDupe(item);
     this._log.debug(item.id + " mapped to " + mapped);
     // We must return a string, not an object, and the entries in the GUIDMap
     // are created via "new String()" making them an object.
     return mapped ? mapped.toString() : mapped;
   },
 
   pullAllChanges() {
-    let changeset = new BookmarksChangeset();
-    for (let id in this._store.getAllIDs()) {
-      changeset.set(id, { modified: 0, deleted: false });
-    }
-    return changeset;
+    return new BookmarksChangeset(this._store.getAllIDs());
   },
 
   pullNewChanges() {
     let modifiedGUIDs = this._getModifiedGUIDs();
     if (!modifiedGUIDs.length) {
       return new BookmarksChangeset(this._tracker.changedIDs);
     }
 
@@ -462,19 +458,17 @@ BookmarksEngine.prototype = {
                                  modifiedGUIDs.length);
 
       let query = `
         WITH RECURSIVE
         modifiedGuids(guid) AS (
           VALUES ${new Array(chunkLength).fill("(?)").join(", ")}
         ),
         syncedItems(id) AS (
-          SELECT b.id
-          FROM moz_bookmarks b
-          WHERE b.id IN (${getChangeRootIds().join(", ")})
+          VALUES ${getChangeRootIds().map(id => `(${id})`).join(", ")}
           UNION ALL
           SELECT b.id
           FROM moz_bookmarks b
           JOIN syncedItems s ON b.parent = s.id
         )
         SELECT b.guid, b.id
         FROM modifiedGuids m
         JOIN moz_bookmarks b ON b.guid = m.guid
@@ -722,23 +716,16 @@ BookmarksStore.prototype = {
     this._log.debug("Changing GUID " + oldID + " to " + newID);
 
     Async.promiseSpinningly(PlacesSyncUtils.bookmarks.changeGuid(
       BookmarkSpecialIds.syncIDToPlacesGUID(oldID),
       BookmarkSpecialIds.syncIDToPlacesGUID(newID)
     ));
   },
 
-  _getNode: function BStore__getNode(folder) {
-    let query = PlacesUtils.history.getNewQuery();
-    query.setFolders([folder], 1);
-    return PlacesUtils.history.executeQuery(
-      query, PlacesUtils.history.getNewQueryOptions()).root;
-  },
-
   _getTags: function BStore__getTags(uri) {
     try {
       if (typeof(uri) == "string")
         uri = Utils.makeURI(uri);
     } catch(e) {
       this._log.warn("Could not parse URI \"" + uri + "\": " + e);
     }
     return PlacesUtils.tagging.getTagsForURI(uri, {});
@@ -911,61 +898,40 @@ BookmarksStore.prototype = {
       let result = Async.querySpinningly(this._frecencyStm, this._frecencyCols);
       if (result.length)
         index += result[0].frecency;
     }
 
     return index;
   },
 
-  _getChildren: function BStore_getChildren(guid, items) {
-    let node = guid; // the recursion case
-    if (typeof(node) == "string") { // callers will give us the guid as the first arg
-      let nodeID = this.idForGUID(guid, true);
-      if (!nodeID) {
-        this._log.debug("No node for GUID " + guid + "; returning no children.");
-        return items;
-      }
-      node = this._getNode(nodeID);
+  getAllIDs: function BStore_getAllIDs() {
+    let items = {};
+
+    let query = `
+      WITH RECURSIVE
+      changeRootContents(id) AS (
+        VALUES ${getChangeRootIds().map(id => `(${id})`).join(", ")}
+        UNION ALL
+        SELECT b.id
+        FROM moz_bookmarks b
+        JOIN changeRootContents c ON b.parent = c.id
+      )
+      SELECT id, guid
+      FROM changeRootContents
+      JOIN moz_bookmarks USING (id)
+    `;
+
+    let statement = this._getStmt(query);
+    let results = Async.querySpinningly(statement, ["id", "guid"]);
+    for (let { id, guid } of results) {
+      let syncID = BookmarkSpecialIds.specialGUIDForId(id) || guid;
+      items[syncID] = { modified: 0, deleted: false };
     }
 
-    if (node.type == node.RESULT_TYPE_FOLDER) {
-      node.QueryInterface(Ci.nsINavHistoryQueryResultNode);
-      node.containerOpen = true;
-      try {
-        // Remember all the children GUIDs and recursively get more
-        for (let i = 0; i < node.childCount; i++) {
-          let child = node.getChild(i);
-          items[this.GUIDForId(child.itemId)] = true;
-          this._getChildren(child, items);
-        }
-      }
-      finally {
-        node.containerOpen = false;
-      }
-    }
-
-    return items;
-  },
-
-  getAllIDs: function BStore_getAllIDs() {
-    let items = {"menu": true,
-                 "toolbar": true,
-                 "unfiled": true,
-                };
-    // We also want "mobile" but only if a local mobile folder already exists
-    // (otherwise we'll later end up creating it, which we want to avoid until
-    // we actually need it.)
-    if (BookmarkSpecialIds.findMobileRoot(false)) {
-      items["mobile"] = true;
-    }
-    for (let guid of BookmarkSpecialIds.guids) {
-      if (guid != "places" && guid != "tags")
-        this._getChildren(guid, items);
-    }
     return items;
   },
 
   wipe: function BStore_wipe() {
     let cb = Async.makeSpinningCallback();
     Task.spawn(function* () {
       // Save a backup before clearing out all bookmarks.
       yield PlacesBackups.create(null, true);

--- a/services/sync/tests/unit/test_bookmark_engine.js
+++ b/services/sync/tests/unit/test_bookmark_engine.js
@@ -127,19 +127,16 @@ add_task(function* bad_record_allIDs() {
       Utils.makeURI("place:folder=1138"),
       PlacesUtils.bookmarks.DEFAULT_INDEX,
       null);
 
   do_check_true(badRecordID > 0);
   _("Record is " + badRecordID);
   _("Type: " + PlacesUtils.bookmarks.getItemType(badRecordID));
 
-  _("Fetching children.");
-  store._getChildren("toolbar", {});
-
   _("Fetching all IDs.");
   let all = store.getAllIDs();
 
   _("All IDs: " + JSON.stringify(all));
   do_check_true("menu" in all);
   do_check_true("toolbar" in all);
 
   _("Clean up.");

--- a/services/sync/tests/unit/test_bookmark_places_query_rewriting.js
+++ b/services/sync/tests/unit/test_bookmark_places_query_rewriting.js
@@ -28,25 +28,28 @@ function run_test() {
 
   let uri = "place:folder=499&type=7&queryType=1";
   let tagRecord = makeTagRecord("abcdefabcdef", uri);
 
   _("Type: " + tagRecord.type);
   _("Folder name: " + tagRecord.folderName);
   store.applyIncoming(tagRecord);
 
-  let tags = store._getNode(PlacesUtils.tagsFolderId);
-  tags.containerOpen = true;
+  let tags = PlacesUtils.getFolderContents(PlacesUtils.tagsFolderId).root;
   let tagID;
-  for (let i = 0; i < tags.childCount; ++i) {
-    let child = tags.getChild(i);
-    if (child.title == "bar")
-      tagID = child.itemId;
+  try {
+    for (let i = 0; i < tags.childCount; ++i) {
+      let child = tags.getChild(i);
+      if (child.title == "bar") {
+        tagID = child.itemId;
+      }
+    }
+  } finally {
+    tags.containerOpen = false;
   }
-  tags.containerOpen = false;
 
   _("Tag ID: " + tagID);
   let insertedRecord = store.createRecord("abcdefabcdef", "bookmarks");
   do_check_eq(insertedRecord.bmkUri, uri.replace("499", tagID));
 
   _("... but not if the type is wrong.");
   let wrongTypeURI = "place:folder=499&type=2&queryType=1";
   let wrongTypeRecord = makeTagRecord("fedcbafedcba", wrongTypeURI);