--- a/toolkit/components/places/Bookmarks.jsm
+++ b/toolkit/components/places/Bookmarks.jsm
@@ -77,16 +77,18 @@ XPCOMUtils.defineLazyModuleGetter(this, 
                                   "resource://gre/modules/Sqlite.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "PlacesUtils",
                                   "resource://gre/modules/PlacesUtils.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "PlacesSyncUtils",
                                   "resource://gre/modules/PlacesSyncUtils.jsm");
 
 const MATCH_ANYWHERE_UNMODIFIED = Ci.mozIPlacesAutoComplete.MATCH_ANYWHERE_UNMODIFIED;
 const BEHAVIOR_BOOKMARK = Ci.mozIPlacesAutoComplete.BEHAVIOR_BOOKMARK;
+// The maximum number of bound parameters per SQLite query.
+const SQLITE_MAX_VARIABLE_NUMBER = 999;
 
 var Bookmarks = Object.freeze({
   /**
    * Item's type constants.
    * These should stay consistent with nsINavBookmarksService.idl
    */
   TYPE_BOOKMARK: 1,
   TYPE_FOLDER: 2,
@@ -1156,45 +1158,72 @@ function removeBookmark(item, options) {
 function reorderChildren(parent, orderedChildrenGuids) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: updateBookmark",
     db => db.executeTransaction(function* () {
       // Select all of the direct children for the given parent.
       let children = yield fetchBookmarksByParent({ parentGuid: parent.guid });
       if (!children.length)
         return undefined;
 
+      // Build a map of GUIDs to indices for fast lookups in the comparator
+      // function.
+      let guidIndices = new Map();
+      for (let i = 0; i < orderedChildrenGuids.length; ++i) {
+        let guid = orderedChildrenGuids[i];
+        guidIndices.set(guid, i);
+      }
+
       // Reorder the children array according to the specified order, provided
       // GUIDs come first, others are appended in somehow random order.
       children.sort((a, b) => {
-        let i = orderedChildrenGuids.indexOf(a.guid);
-        let j = orderedChildrenGuids.indexOf(b.guid);
         // This works provided fetchBookmarksByParent returns sorted children.
-        if (i == -1 && j == -1)
+        if (!guidIndices.has(a.guid) && !guidIndices.has(b.guid)) {
           return 0;
-        return (i != -1 && j != -1 && i < j) || (i != -1 && j == -1) ? -1 : 1;
+        }
+        if (!guidIndices.has(a.guid)) {
+          return 1;
+        }
+        if (!guidIndices.has(b.guid)) {
+          return -1;
+        }
+        return guidIndices.get(a.guid) < guidIndices.get(b.guid) ? -1 : 1;
        });
 
+      // To do the update in a single step, we build a temporary
+      // (guid, position) sorting table.  We then use count() in the sorting
+      // table to avoid skipping values when no more existing GUIDs have been
+      // provided.
+      yield db.executeCached(
+        `CREATE TEMP TABLE moz_bookmarks_reorder_sorting(g TEXT, p INTEGER)`);
+
+      // SQLite limits the number of bound parameters per query, so we chunk
+      // the sorted children array to fit as many values as we can.
+      const maxValuesPerChunk = Math.floor(SQLITE_MAX_VARIABLE_NUMBER / 2);
+      for (let startIndex = 0; startIndex < children.length; startIndex += maxValuesPerChunk) {
+        let valuesPerChunk = Math.min(maxValuesPerChunk, children.length - startIndex);
+        let params = [];
+        for (let i = 0; i < valuesPerChunk; ++i) {
+          params.push(children[startIndex + i].guid, startIndex + i);
+        }
+        yield db.execute(
+          `INSERT INTO moz_bookmarks_reorder_sorting(g, p)
+           VALUES ${new Array(valuesPerChunk).fill("(?, ?)").join()}
+          `, params);
+      }
+
       // Update the bookmarks position now.  If any unknown guid have been
       // inserted meanwhile, its position will be set to -position, and we'll
       // handle it later.
-      // To do the update in a single step, we build a VALUES (guid, position)
-      // table.  We then use count() in the sorting table to avoid skipping values
-      // when no more existing GUIDs have been provided.
-      let valuesTable = children.map((child, i) => `("${child.guid}", ${i})`)
-                                .join();
-      yield db.execute(
-        `WITH sorting(g, p) AS (
-           VALUES ${valuesTable}
-         )
-         UPDATE moz_bookmarks SET position = (
+      yield db.executeCached(
+        `UPDATE moz_bookmarks SET position = (
            SELECT CASE count(*) WHEN 0 THEN -position
                                        ELSE count(*) - 1
                   END
-           FROM sorting a
-           JOIN sorting b ON b.p <= a.p
+           FROM moz_bookmarks_reorder_sorting a
+           JOIN moz_bookmarks_reorder_sorting b ON b.p <= a.p
            WHERE a.g = guid
          )
          WHERE parent = :parentId
         `, { parentId: parent._id});
 
       // Update position of items that could have been inserted in the meanwhile.
       // Since this can happen rarely and it's only done for schema coherence
       // resonds, we won't notify about these changes.
@@ -1213,16 +1242,18 @@ function reorderChildren(parent, ordered
          END
         `);
 
       yield db.executeCached(
         `UPDATE moz_bookmarks SET position = -1 WHERE position < 0`);
 
       yield db.executeCached(`DROP TRIGGER moz_bookmarks_reorder_trigger`);
 
+      yield db.executeCached(`DROP TABLE moz_bookmarks_reorder_sorting`);
+
       return children;
     }.bind(this))
   );
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 // Helpers.
 

--- a/toolkit/components/places/PlacesSyncUtils.jsm
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -104,67 +104,36 @@ const BookmarkSyncUtils = PlacesSyncUtil
     let db = yield PlacesUtils.promiseDBConnection();
     let children = yield fetchAllChildren(db, parentGuid);
     return children.map(child =>
       BookmarkSyncUtils.guidToSyncId(child.guid)
     );
   }),
 
   /**
-   * Reorders a folder's children, based on their order in the array of GUIDs.
-   * This method is similar to `Bookmarks.reorder`, but leaves missing entries
-   * in place instead of moving them to the end of the folder.
+   * Reorders a folder's children, based on their order in the array of sync
+   * IDs.
    *
    * Sync uses this method to reorder all synced children after applying all
    * incoming records.
    *
    */
   order: Task.async(function* (parentSyncId, childSyncIds) {
     PlacesUtils.SYNC_BOOKMARK_VALIDATORS.syncId(parentSyncId);
     if (!childSyncIds.length) {
       return;
     }
-    for (let syncId of childSyncIds) {
-      PlacesUtils.SYNC_BOOKMARK_VALIDATORS.syncId(syncId);
-    }
     let parentGuid = BookmarkSyncUtils.syncIdToGuid(parentSyncId);
-
     if (parentGuid == PlacesUtils.bookmarks.rootGuid) {
       // Reordering roots doesn't make sense, but Sync will do this on the
       // first sync.
       return;
     }
-    yield PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: order",
-      Task.async(function* (db) {
-        let children = yield fetchAllChildren(db, parentGuid);
-        if (!children.length) {
-          return;
-        }
-
-        // Reorder the list, ignoring missing children.
-        let delta = 0;
-        for (let i = 0; i < childSyncIds.length; ++i) {
-          let guid = BookmarkSyncUtils.syncIdToGuid(childSyncIds[i]);
-          let child = findChildByGuid(children, guid);
-          if (!child) {
-            delta++;
-            BookmarkSyncLog.trace(`order: Ignoring missing child ${
-              childSyncIds[i]}`);
-            continue;
-          }
-          let newIndex = i - delta;
-          updateChildIndex(children, child, newIndex);
-        }
-        children.sort((a, b) => a.index - b.index);
-
-        // Update positions.
-        let orderedChildrenGuids = children.map(({ guid }) => guid);
-        yield PlacesUtils.bookmarks.reorder(parentGuid, orderedChildrenGuids);
-      })
-    );
+    let orderedChildrenGuids = childSyncIds.map(BookmarkSyncUtils.syncIdToGuid);
+    return PlacesUtils.bookmarks.reorder(parentGuid, orderedChildrenGuids);
   }),
 
   /**
    * Removes an item from the database.
    */
   remove: Task.async(function* (syncId) {
     let guid = BookmarkSyncUtils.syncIdToGuid(syncId);
     if (guid in ROOT_GUID_TO_SYNC_ID) {
@@ -368,41 +337,16 @@ var fetchAllChildren = Task.async(functi
     id: row.getResultByName("id"),
     parentId: row.getResultByName("parent"),
     index: row.getResultByName("position"),
     type: row.getResultByName("type"),
     guid: row.getResultByName("guid"),
   }));
 });
 
-function findChildByGuid(children, guid) {
-  return children.find(child => child.guid == guid);
-}
-
-function findChildByIndex(children, index) {
-  return children.find(child => child.index == index);
-}
-
-// Sets a child record's index and updates its sibling's indices.
-function updateChildIndex(children, child, newIndex) {
-  let siblings = [];
-  let lowIndex = Math.min(child.index, newIndex);
-  let highIndex = Math.max(child.index, newIndex);
-  for (; lowIndex < highIndex; ++lowIndex) {
-    let sibling = findChildByIndex(children, lowIndex);
-    siblings.push(sibling);
-  }
-
-  let sign = newIndex < child.index ? +1 : -1;
-  for (let sibling of siblings) {
-    sibling.index += sign;
-  }
-  child.index = newIndex;
-}
-
 // A helper for whenever we want to know if a GUID doesn't exist in the places
 // database. Primarily used to detect orphans on incoming records.
 var GUIDMissing = Task.async(function* (guid) {
   try {
     yield PlacesUtils.promiseItemId(guid);
     return false;
   } catch (ex) {
     if (ex.message == "no item found for the given GUID") {

--- a/toolkit/components/places/tests/unit/test_sync_utils.js
+++ b/toolkit/components/places/tests/unit/test_sync_utils.js
@@ -166,16 +166,57 @@ add_task(function* test_order() {
       PlacesUtils.bookmarks.menuGuid);
     deepEqual(childSyncIds, [guids.childBmk, guids.siblingBmk, guids.siblingSep,
       guids.siblingFolder], "Nonexistent children should be ignored");
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
 });
 
+add_task(function* test_order_reverse() {
+  do_print("Insert bookmark");
+  // Inserting a batch of 3k bookmarks using `PlacesUtils.bookmarks.insert` is
+  // very slow, and uses a transaction per call. For speed, we insert 3k rows
+  // in a single transaction.
+  yield PlacesUtils.withConnectionWrapper("test_order_reverse", db => {
+    return db.executeTransaction(function* () {
+      let time = PlacesUtils.toPRTime(new Date());
+      for (let position = 0; position < 3000; ++position) {
+        // We insert folders instead of bookmarks to avoid updating
+        // `moz_places`.
+        yield db.executeCached(`
+          INSERT INTO moz_bookmarks (type, parent, position, dateAdded,
+                                     lastModified, guid)
+          VALUES (:type, :parentId, :position, :time,
+                  :time, GENERATE_GUID())`,
+          { type: PlacesUtils.bookmarks.TYPE_FOLDER,
+            parentId: PlacesUtils.bookmarksMenuFolderId,
+            position, time });
+      }
+    });
+  });
+
+  // Test the worst case performance by reversing all children. It takes 12
+  // seconds on a fast dev machine (2013 rMBP) to reverse 3k bookmarks, so this
+  // test might time out on infra.
+  do_print("Reverse children");
+  let childSyncIds = yield PlacesSyncUtils.bookmarks.fetchChildSyncIds(
+    PlacesUtils.bookmarks.menuGuid);
+  childSyncIds.reverse();
+  yield PlacesSyncUtils.bookmarks.order(PlacesUtils.bookmarks.menuGuid,
+    childSyncIds);
+
+  let newChildSyncIds = yield PlacesSyncUtils.bookmarks.fetchChildSyncIds(
+    PlacesUtils.bookmarks.menuGuid);
+  deepEqual(childSyncIds, newChildSyncIds,
+    "Should reverse all children of folder");
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
 add_task(function* test_changeGuid_invalid() {
   yield rejects(PlacesSyncUtils.bookmarks.changeGuid(makeGuid()),
     "Should require a new GUID");
   yield rejects(PlacesSyncUtils.bookmarks.changeGuid(makeGuid(), "!@#$"),
     "Should reject invalid GUIDs");
   yield rejects(PlacesSyncUtils.bookmarks.changeGuid(makeGuid(), makeGuid()),
     "Should reject nonexistent item GUIDs");
   yield rejects(