--- a/toolkit/components/places/nsNavBookmarks.cpp
+++ b/toolkit/components/places/nsNavBookmarks.cpp
@@ -858,58 +858,16 @@ bool nsNavBookmarks::IsLivemark(int64_t 
   nsresult rv = annosvc->ItemHasAnnotation(aFolderId,
                                            FEED_URI_ANNO,
                                            &isLivemark);
   NS_ENSURE_SUCCESS(rv, false);
   return isLivemark;
 }
 
 nsresult
-nsNavBookmarks::GetDescendantFolders(int64_t aFolderId,
-                                     nsTArray<int64_t>& aDescendantFoldersArray) {
-  nsresult rv;
-  // New descendant folders will be added from this index on.
-  uint32_t startIndex = aDescendantFoldersArray.Length();
-  {
-    nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
-      "SELECT id "
-      "FROM moz_bookmarks "
-      "WHERE parent = :parent "
-      "AND type = :item_type "
-    );
-    NS_ENSURE_STATE(stmt);
-    mozStorageStatementScoper scoper(stmt);
-
-    rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("parent"), aFolderId);
-    NS_ENSURE_SUCCESS(rv, rv);
-    rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("item_type"), TYPE_FOLDER);
-    NS_ENSURE_SUCCESS(rv, rv);
-
-    bool hasMore = false;
-    while (NS_SUCCEEDED(stmt->ExecuteStep(&hasMore)) && hasMore) {
-      int64_t itemId;
-      rv = stmt->GetInt64(0, &itemId);
-      NS_ENSURE_SUCCESS(rv, rv);
-      aDescendantFoldersArray.AppendElement(itemId);
-    }
-  }
-
-  // Recursively call GetDescendantFolders for added folders.
-  // We start at startIndex since previous folders are checked
-  // by previous calls to this method.
-  uint32_t childCount = aDescendantFoldersArray.Length();
-  for (uint32_t i = startIndex; i < childCount; ++i) {
-    GetDescendantFolders(aDescendantFoldersArray[i], aDescendantFoldersArray);
-  }
-
-  return NS_OK;
-}
-
-
-nsresult
 nsNavBookmarks::GetDescendantChildren(int64_t aFolderId,
                                       const nsACString& aFolderGuid,
                                       int64_t aGrandParentId,
                                       nsTArray<BookmarkData>& aFolderChildrenArray) {
   // New children will be added from this index on.
   uint32_t startIndex = aFolderChildrenArray.Length();
   nsresult rv;
   {

--- a/toolkit/components/places/nsNavBookmarks.h
+++ b/toolkit/components/places/nsNavBookmarks.h
@@ -191,27 +191,16 @@ public:
    *
    * @param aItemId
    *        The changed item id.
    * @param aData
    *        Details about the change.
    */
   void NotifyItemChanged(const ItemChangeData& aData);
 
-  /**
-   * Recursively builds an array of descendant folders inside a given folder.
-   *
-   * @param aFolderId
-   *        The folder to fetch descendants from.
-   * @param aDescendantFoldersArray
-   *        Output array to put descendant folders id.
-   */
-  nsresult GetDescendantFolders(int64_t aFolderId,
-                                nsTArray<int64_t>& aDescendantFoldersArray);
-
   static const int32_t kGetChildrenIndex_Guid;
   static const int32_t kGetChildrenIndex_Position;
   static const int32_t kGetChildrenIndex_Type;
   static const int32_t kGetChildrenIndex_PlaceID;
   static const int32_t kGetChildrenIndex_SyncStatus;
 
   static mozilla::Atomic<int64_t> sLastInsertedItemId;
   static void StoreLastInsertedId(const nsACString& aTable,

--- a/toolkit/components/places/nsNavHistory.cpp
+++ b/toolkit/components/places/nsNavHistory.cpp
@@ -3031,38 +3031,34 @@ nsNavHistory::QueryToSelectClause(const 
           .Param(param.get())
           .Str(")");
   }
 
   // folders
   const nsTArray<int64_t>& folders = aQuery->Folders();
   if (folders.Length() > 0) {
     aOptions->SetQueryType(nsNavHistoryQueryOptions::QUERY_TYPE_BOOKMARKS);
-
-    nsTArray<int64_t> includeFolders;
-    includeFolders.AppendElements(folders);
-
-    nsNavBookmarks* bookmarks = nsNavBookmarks::GetBookmarksService();
-    NS_ENSURE_STATE(bookmarks);
-
-    for (nsTArray<int64_t>::size_type i = 0; i < folders.Length(); ++i) {
-      nsTArray<int64_t> subFolders;
-      if (NS_FAILED(bookmarks->GetDescendantFolders(folders[i], subFolders)))
-        continue;
-      includeFolders.AppendElements(subFolders);
-    }
-
-    clause.Condition("b.parent IN(");
-    for (nsTArray<int64_t>::size_type i = 0; i < includeFolders.Length(); ++i) {
-      clause.Str(nsPrintfCString("%" PRId64, includeFolders[i]).get());
-      if (i < includeFolders.Length() - 1) {
+    clause.Condition("b.parent IN( "
+                       "WITH RECURSIVE parents(id) AS ( "
+                         "VALUES ");
+    for (uint32_t i = 0; i < folders.Length(); ++i) {
+      nsPrintfCString param("(:parent%d_)", i);
+      clause.Param(param.get());
+      if (i < folders.Length() - 1) {
         clause.Str(",");
       }
     }
-    clause.Str(")");
+    clause.Str(          "UNION ALL "
+                         "SELECT b2.id "
+                         "FROM moz_bookmarks b2 "
+                         "JOIN parents p ON b2.parent = p.id "
+                         "WHERE b2.type = 2 "
+                       ") "
+                       "SELECT id FROM parents "
+                     ")");
   }
 
   if (excludeQueries) {
     // Serching by terms implicitly exclude queries and folder shortcuts.
     clause.Condition("NOT h.url_hash BETWEEN hash('place', 'prefix_lo') AND "
                                             "hash('place', 'prefix_hi')");
   }
 
@@ -3181,16 +3177,24 @@ nsNavHistory::BindQueryClauseParameters(
   // transitions
   const nsTArray<uint32_t>& transitions = aQuery->Transitions();
   for (uint32_t i = 0; i < transitions.Length(); ++i) {
     nsPrintfCString paramName("transition%d_", i);
     rv = statement->BindInt64ByName(paramName, transitions[i]);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
+  // folders
+  const nsTArray<int64_t>& folders = aQuery->Folders();
+  for (uint32_t i = 0; i < folders.Length(); ++i) {
+    nsPrintfCString paramName("parent%d_", i);
+    rv = statement->BindInt64ByName(paramName, folders[i]);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
   return NS_OK;
 }
 
 
 // nsNavHistory::ResultsAsList
 //
 
 nsresult