--- a/browser/components/places/tests/chrome/test_0_bug510634.xul
+++ b/browser/components/places/tests/chrome/test_0_bug510634.xul
@@ -49,18 +49,17 @@
 
       // The query-property is set on the title column for each row.
       let titleColumn = tree.treeBoxObject.columns.getColumnAt(0);
 
       // Open All Bookmarks
       tree.selectItems([PlacesUtils.virtualAllBookmarksGuid]);
       PlacesUtils.asContainer(tree.selectedNode).containerOpen = true;
       is(tree.selectedNode.uri,
-         "place:type=" + Ci.nsINavHistoryQueryOptions.RESULTS_AS_ROOTS_QUERY +
-         "&queryType=" + Ci.nsINavHistoryQueryOptions.QUERY_TYPE_BOOKMARKS,
+         "place:type=" + Ci.nsINavHistoryQueryOptions.RESULTS_AS_ROOTS_QUERY,
          "Opened All Bookmarks");
 
       const topLevelGuids = [
         PlacesUtils.virtualHistoryGuid,
         PlacesUtils.virtualDownloadsGuid,
         PlacesUtils.virtualTagsGuid,
         PlacesUtils.virtualAllBookmarksGuid
       ];

--- a/toolkit/components/places/nsNavHistory.cpp
+++ b/toolkit/components/places/nsNavHistory.cpp
@@ -758,99 +758,16 @@ nsNavHistory::NormalizeTime(uint32_t aRe
       break;
     default:
       NS_NOTREACHED("Invalid relative time");
       return 0;
   }
   return ref + aOffset;
 }
 
-// nsNavHistory::GetUpdateRequirements
-//
-//    Returns conditions for query update.
-//
-//    QUERYUPDATE_TIME:
-//      This query is only limited by an inclusive time range on the first
-//      query object. The caller can quickly evaluate the time itself if it
-//      chooses. This is even simpler than "simple" below.
-//    QUERYUPDATE_SIMPLE:
-//      This query is evaluatable using EvaluateQueryForNode to do live
-//      updating.
-//    QUERYUPDATE_COMPLEX:
-//      This query is not evaluatable using EvaluateQueryForNode. When something
-//      happens that this query updates, you will need to re-run the query.
-//    QUERYUPDATE_COMPLEX_WITH_BOOKMARKS:
-//      A complex query that additionally has dependence on bookmarks. All
-//      bookmark-dependent queries fall under this category.
-//    QUERYUPDATE_MOBILEPREF:
-//      A complex query but only updates when the mobile preference changes.
-//    QUERYUPDATE_NONE:
-//      A query that never updates, e.g. the left-pane root query.
-//
-//    aHasSearchTerms will be set to true if the query has any dependence on
-//    keywords. When there is no dependence on keywords, we can handle title
-//    change operations as simple instead of complex.
-
-uint32_t
-nsNavHistory::GetUpdateRequirements(const RefPtr<nsNavHistoryQuery>& aQuery,
-                                    nsNavHistoryQueryOptions* aOptions,
-                                    bool* aHasSearchTerms)
-{
-  // first check if there are search terms
-  bool hasSearchTerms = *aHasSearchTerms = !aQuery->SearchTerms().IsEmpty();
-
-  bool nonTimeBasedItems = false;
-  bool domainBasedItems = false;
-
-  if (aQuery->Folders().Length() > 0 ||
-      aQuery->OnlyBookmarked() ||
-      aQuery->Tags().Length() > 0 ||
-      (aOptions->QueryType() == nsINavHistoryQueryOptions::QUERY_TYPE_BOOKMARKS &&
-        hasSearchTerms)) {
-    return QUERYUPDATE_COMPLEX_WITH_BOOKMARKS;
-  }
-
-  // Note: we don't currently have any complex non-bookmarked items, but these
-  // are expected to be added. Put detection of these items here.
-  if (hasSearchTerms ||
-      !aQuery->Domain().IsVoid() ||
-      aQuery->Uri() != nullptr)
-    nonTimeBasedItems = true;
-
-  if (!aQuery->Domain().IsVoid())
-    domainBasedItems = true;
-
-  if (aOptions->ResultType() ==
-        nsINavHistoryQueryOptions::RESULTS_AS_TAG_QUERY)
-      return QUERYUPDATE_COMPLEX_WITH_BOOKMARKS;
-
-  if (aOptions->ResultType() ==
-        nsINavHistoryQueryOptions::RESULTS_AS_ROOTS_QUERY)
-      return QUERYUPDATE_MOBILEPREF;
-
-  if (aOptions->ResultType() ==
-        nsINavHistoryQueryOptions::RESULTS_AS_LEFT_PANE_QUERY)
-      return QUERYUPDATE_NONE;
-
-  // Whenever there is a maximum number of results,
-  // and we are not a bookmark query we must requery. This
-  // is because we can't generally know if any given addition/change causes
-  // the item to be in the top N items in the database.
-  if (aOptions->MaxResults() > 0)
-    return QUERYUPDATE_COMPLEX;
-
-  if (domainBasedItems)
-    return QUERYUPDATE_HOST;
-  if (!nonTimeBasedItems)
-    return QUERYUPDATE_TIME;
-
-  return QUERYUPDATE_SIMPLE;
-}
-
-
 // nsNavHistory::EvaluateQueryForNode
 //
 //    This runs the node through the given query to see if satisfies the
 //    query conditions. Not every query parameters are handled by this code,
 //    but we handle the most common ones so that performance is better.
 //
 //    We assume that the time on the node is the time that we want to compare.
 //    This is not necessarily true because URL nodes have the last access time,
@@ -1253,17 +1170,20 @@ nsNavHistory::ExecuteQuery(nsINavHistory
       // This is a perf hack to generate an empty query that skips filtering.
       options->SetExcludeItems(true);
     }
   }
 
   if (!rootNode) {
     // Either this is not a folder shortcut, or is a broken one.  In both cases
     // just generate a query node.
-    rootNode = new nsNavHistoryQueryResultNode(EmptyCString(),
+    nsAutoCString queryUri;
+    nsresult rv = QueryToQueryString(query, options, queryUri);
+    NS_ENSURE_SUCCESS(rv, rv);
+    rootNode = new nsNavHistoryQueryResultNode(EmptyCString(), 0, queryUri,
                                                query, options);
   }
 
   // Create the result that will hold nodes.  Inject batching status into it.
   RefPtr<nsNavHistoryResult> result = new nsNavHistoryResult(rootNode,
                                                              query, options,
                                                              isBatching());
   result.forget(_retval);
@@ -3887,28 +3807,28 @@ nsNavHistory::QueryRowToResult(int64_t i
         // concrete folder title).
         if (!aTitle.IsEmpty()) {
           resultNode->mTitle = aTitle;
         }
       }
     }
     else {
       // This is a regular query.
-      resultNode = new nsNavHistoryQueryResultNode(aTitle, aTime, queryObj, optionsObj);
+      resultNode = new nsNavHistoryQueryResultNode(aTitle, aTime, aURI, queryObj, optionsObj);
       resultNode->mItemId = itemId;
       resultNode->mBookmarkGuid = aBookmarkGuid;
     }
   }
 
   if (NS_FAILED(rv)) {
     NS_WARNING("Generating a generic empty node for a broken query!");
     // This is a broken query, that either did not parse or points to not
     // existing data.  We don't want to return failure since that will kill the
     // whole result.  Instead make a generic empty query node.
-    resultNode = new nsNavHistoryQueryResultNode(aTitle, aURI);
+    resultNode = new nsNavHistoryQueryResultNode(aTitle, 0, aURI, queryObj, optionsObj);
     resultNode->mItemId = itemId;
     resultNode->mBookmarkGuid = aBookmarkGuid;
     // This is a perf hack to generate an empty query that skips filtering.
     resultNode->GetAsQuery()->Options()->SetExcludeItems(true);
   }
 
   resultNode.forget(aNode);
   return NS_OK;

--- a/toolkit/components/places/nsNavHistory.h
+++ b/toolkit/components/places/nsNavHistory.h
@@ -292,20 +292,16 @@ public:
                                    const nsAString& aValue,
                                    const nsACString& aGUID);
 
   /**
    * Returns current number of days stored in history.
    */
   int32_t GetDaysOfHistory();
 
-  // used by query result nodes to update: see comment on body of CanLiveUpdateQuery
-  static uint32_t GetUpdateRequirements(const RefPtr<nsNavHistoryQuery>& aQuery,
-                                        nsNavHistoryQueryOptions* aOptions,
-                                        bool* aHasSearchTerms);
   bool EvaluateQueryForNode(const RefPtr<nsNavHistoryQuery>& aQuery,
                               nsNavHistoryQueryOptions* aOptions,
                               nsNavHistoryResultNode* aNode);
 
   static nsresult AsciiHostNameFromHostString(const nsACString& aHostName,
                                               nsACString& aAscii);
   void DomainNameFromURI(nsIURI* aURI,
                          nsACString& aDomainName);

--- a/toolkit/components/places/nsNavHistoryQuery.cpp
+++ b/toolkit/components/places/nsNavHistoryQuery.cpp
@@ -237,17 +237,16 @@ namespace PlacesFolderConversion {
       // It wasn't one of our named constants, so just convert it to a string.
       aQuery.AppendInt(aFolderID);
     }
 
     return NS_OK;
   }
 } // namespace PlacesFolderConversion
 
-
 NS_IMETHODIMP
 nsNavHistory::QueryStringToQuery(const nsACString& aQueryString,
                                  nsINavHistoryQuery** _query,
                                  nsINavHistoryQueryOptions** _options)
 {
   NS_ENSURE_ARG_POINTER(_query);
   NS_ENSURE_ARG_POINTER(_options);
 
@@ -272,20 +271,21 @@ nsNavHistory::QueryStringToQuery(const n
 NS_IMETHODIMP
 nsNavHistory::QueryToQueryString(nsINavHistoryQuery *aQuery,
                                  nsINavHistoryQueryOptions* aOptions,
                                  nsACString& aQueryString)
 {
   NS_ENSURE_ARG(aQuery);
   NS_ENSURE_ARG(aOptions);
 
-  nsCOMPtr<nsNavHistoryQueryOptions> options = do_QueryInterface(aOptions);
-  NS_ENSURE_TRUE(options, NS_ERROR_INVALID_ARG);
+  RefPtr<nsNavHistoryQuery> query = do_QueryObject(aQuery);
+  NS_ENSURE_STATE(query);
+  RefPtr<nsNavHistoryQueryOptions> options = do_QueryObject(aOptions);
+  NS_ENSURE_STATE(options);
 
-  nsCOMPtr<nsNavHistoryQuery> query = do_QueryObject(aQuery);
   nsAutoCString queryString;
   bool hasIt;
 
   // begin time
   query->GetHasBeginTime(&hasIt);
   if (hasIt) {
     AppendInt64KeyValueIfNonzero(queryString,
                                  NS_LITERAL_CSTRING(QUERYKEY_BEGIN_TIME),

--- a/toolkit/components/places/nsNavHistoryResult.cpp
+++ b/toolkit/components/places/nsNavHistoryResult.cpp
@@ -54,32 +54,116 @@
     *aInstancePtr = this; \
     return NS_OK; \
   } else
 
 // Number of changes to handle separately in a batch.  If more changes are
 // requested the node will switch to full refresh mode.
 #define MAX_BATCH_CHANGES_BEFORE_REFRESH 5
 
+using namespace mozilla;
+using namespace mozilla::places;
+
+namespace {
+
+/**
+ * Returns conditions for query update.
+ *    QUERYUPDATE_TIME:
+ *      This query is only limited by an inclusive time range on the first
+ *      query object. The caller can quickly evaluate the time itself if it
+ *      chooses. This is even simpler than "simple" below.
+ *    QUERYUPDATE_SIMPLE:
+ *      This query is evaluatable using EvaluateQueryForNode to do live
+ *      updating.
+ *    QUERYUPDATE_COMPLEX:
+ *      This query is not evaluatable using EvaluateQueryForNode. When something
+ *      happens that this query updates, you will need to re-run the query.
+ *    QUERYUPDATE_COMPLEX_WITH_BOOKMARKS:
+ *      A complex query that additionally has dependence on bookmarks. All
+ *      bookmark-dependent queries fall under this category.
+ *    QUERYUPDATE_MOBILEPREF:
+ *      A complex query but only updates when the mobile preference changes.
+ *    QUERYUPDATE_NONE:
+ *      A query that never updates, e.g. the left-pane root query.
+ *
+ *    aHasSearchTerms will be set to true if the query has any dependence on
+ *    keywords. When there is no dependence on keywords, we can handle title
+ *    change operations as simple instead of complex.
+ */
+uint32_t
+getUpdateRequirements(const RefPtr<nsNavHistoryQuery>& aQuery,
+                      const RefPtr<nsNavHistoryQueryOptions>& aOptions,
+                      bool* aHasSearchTerms)
+{
+  // first check if there are search terms
+  bool hasSearchTerms = *aHasSearchTerms = !aQuery->SearchTerms().IsEmpty();
+
+  bool nonTimeBasedItems = false;
+  bool domainBasedItems = false;
+
+  if (aQuery->Folders().Length() > 0 ||
+      aQuery->OnlyBookmarked() ||
+      aQuery->Tags().Length() > 0 ||
+      (aOptions->QueryType() == nsINavHistoryQueryOptions::QUERY_TYPE_BOOKMARKS &&
+        hasSearchTerms)) {
+    return QUERYUPDATE_COMPLEX_WITH_BOOKMARKS;
+  }
+
+  // Note: we don't currently have any complex non-bookmarked items, but these
+  // are expected to be added. Put detection of these items here.
+  if (hasSearchTerms ||
+      !aQuery->Domain().IsVoid() ||
+      aQuery->Uri() != nullptr)
+    nonTimeBasedItems = true;
+
+  if (!aQuery->Domain().IsVoid())
+    domainBasedItems = true;
+
+  if (aOptions->ResultType() ==
+        nsINavHistoryQueryOptions::RESULTS_AS_TAG_QUERY)
+      return QUERYUPDATE_COMPLEX_WITH_BOOKMARKS;
+
+  if (aOptions->ResultType() ==
+        nsINavHistoryQueryOptions::RESULTS_AS_ROOTS_QUERY)
+      return QUERYUPDATE_MOBILEPREF;
+
+  if (aOptions->ResultType() ==
+        nsINavHistoryQueryOptions::RESULTS_AS_LEFT_PANE_QUERY)
+      return QUERYUPDATE_NONE;
+
+  // Whenever there is a maximum number of results,
+  // and we are not a bookmark query we must requery. This
+  // is because we can't generally know if any given addition/change causes
+  // the item to be in the top N items in the database.
+  if (aOptions->MaxResults() > 0)
+    return QUERYUPDATE_COMPLEX;
+
+  if (domainBasedItems)
+    return QUERYUPDATE_HOST;
+  if (!nonTimeBasedItems)
+    return QUERYUPDATE_TIME;
+
+  return QUERYUPDATE_SIMPLE;
+}
+
 // Emulate string comparison (used for sorting) for PRTime and int.
 inline int32_t ComparePRTime(PRTime a, PRTime b)
 {
   if (a < b)
     return -1;
   else if (a > b)
     return 1;
   return 0;
 }
 inline int32_t CompareIntegers(uint32_t a, uint32_t b)
 {
   return a - b;
 }
 
-using namespace mozilla;
-using namespace mozilla::places;
+} // anonymous namespace
 
 NS_IMPL_CYCLE_COLLECTION(nsNavHistoryResultNode, mParent)
 
 NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(nsNavHistoryResultNode)
   NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsINavHistoryResultNode)
   NS_INTERFACE_MAP_ENTRY(nsINavHistoryResultNode)
 NS_INTERFACE_MAP_END
 
@@ -298,30 +382,16 @@ NS_IMPL_ADDREF_INHERITED(nsNavHistoryCon
 NS_IMPL_RELEASE_INHERITED(nsNavHistoryContainerResultNode, nsNavHistoryResultNode)
 
 NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(nsNavHistoryContainerResultNode)
   NS_INTERFACE_MAP_STATIC_AMBIGUOUS(nsNavHistoryContainerResultNode)
   NS_INTERFACE_MAP_ENTRY(nsINavHistoryContainerResultNode)
 NS_INTERFACE_MAP_END_INHERITING(nsNavHistoryResultNode)
 
 nsNavHistoryContainerResultNode::nsNavHistoryContainerResultNode(
-    const nsACString& aURI, const nsACString& aTitle, uint32_t aContainerType,
-    nsNavHistoryQueryOptions* aOptions) :
-  nsNavHistoryResultNode(aURI, aTitle, 0, 0),
-  mResult(nullptr),
-  mContainerType(aContainerType),
-  mExpanded(false),
-  mOptions(aOptions),
-  mAsyncCanceledState(NOT_CANCELED)
-{
-  MOZ_ASSERT(mOptions);
-  MOZ_ALWAYS_SUCCEEDS(mOptions->Clone(getter_AddRefs(mOriginalOptions)));
-}
-
-nsNavHistoryContainerResultNode::nsNavHistoryContainerResultNode(
     const nsACString& aURI, const nsACString& aTitle,
     PRTime aTime, uint32_t aContainerType,
     nsNavHistoryQueryOptions* aOptions) :
   nsNavHistoryResultNode(aURI, aTitle, 0, aTime),
   mResult(nullptr),
   mContainerType(aContainerType),
   mExpanded(false),
   mOptions(aOptions),
@@ -1685,65 +1755,30 @@ nsNavHistoryContainerResultNode::GetChil
  * a message without doing a requery.  For complex changes or complex queries,
  * we give up and requery.
  */
 NS_IMPL_ISUPPORTS_INHERITED(nsNavHistoryQueryResultNode,
                             nsNavHistoryContainerResultNode,
                             nsINavHistoryQueryResultNode)
 
 nsNavHistoryQueryResultNode::nsNavHistoryQueryResultNode(
-    const nsACString& aTitle, const nsACString& aQueryURI) :
-  nsNavHistoryContainerResultNode(aQueryURI, aTitle,
-                                  nsNavHistoryResultNode::RESULT_TYPE_QUERY,
-                                  new nsNavHistoryQueryOptions()),
-  mLiveUpdate(QUERYUPDATE_COMPLEX_WITH_BOOKMARKS),
-  mHasSearchTerms(false),
-  mContentsValid(false),
-  mBatchChanges(0)
-{
-}
-
-nsNavHistoryQueryResultNode::nsNavHistoryQueryResultNode(
-    const nsACString& aTitle, const RefPtr<nsNavHistoryQuery>& aQuery,
-    nsNavHistoryQueryOptions* aOptions) :
-  nsNavHistoryContainerResultNode(EmptyCString(), aTitle,
-                                  nsNavHistoryResultNode::RESULT_TYPE_QUERY,
-                                  aOptions),
+    const nsACString& aTitle,
+    PRTime aTime,
+    const nsACString& aQueryURI,
+    const RefPtr<nsNavHistoryQuery>& aQuery,
+    const RefPtr<nsNavHistoryQueryOptions>& aOptions)
+  : nsNavHistoryContainerResultNode(aQueryURI, aTitle, aTime,
+                                    nsNavHistoryResultNode::RESULT_TYPE_QUERY,
+                                    aOptions),
   mQuery(aQuery),
+  mLiveUpdate(getUpdateRequirements(aQuery, aOptions, &mHasSearchTerms)),
   mContentsValid(false),
   mBatchChanges(0),
   mTransitions(aQuery->Transitions())
 {
-  nsNavHistory* history = nsNavHistory::GetHistoryService();
-  NS_ASSERTION(history, "History service missing");
-  if (history) {
-    mLiveUpdate = history->GetUpdateRequirements(mQuery, mOptions,
-                                                 &mHasSearchTerms);
-  }
-}
-
-nsNavHistoryQueryResultNode::nsNavHistoryQueryResultNode(
-    const nsACString& aTitle,
-    PRTime aTime,
-    const RefPtr<nsNavHistoryQuery>& aQuery,
-    nsNavHistoryQueryOptions* aOptions) :
-  nsNavHistoryContainerResultNode(EmptyCString(), aTitle, aTime,
-                                  nsNavHistoryResultNode::RESULT_TYPE_QUERY,
-                                  aOptions),
-  mQuery(aQuery),
-  mContentsValid(false),
-  mBatchChanges(0),
-  mTransitions(aQuery->Transitions())
-{
-  nsNavHistory* history = nsNavHistory::GetHistoryService();
-  NS_ASSERTION(history, "History service missing");
-  if (history) {
-    mLiveUpdate = history->GetUpdateRequirements(mQuery, mOptions,
-                                                 &mHasSearchTerms);
-  }
 }
 
 nsNavHistoryQueryResultNode::~nsNavHistoryQueryResultNode() {
   // Remove this node from result's observers.  We don't need to be notified
   // anymore.
   if (mResult && mResult->mAllBookmarksObservers.Contains(this))
     mResult->RemoveAllBookmarksObserver(this);
   if (mResult && mResult->mHistoryObservers.Contains(this))
@@ -1906,18 +1941,16 @@ nsNavHistoryQueryResultNode::GetHasChild
 
 /**
  * This doesn't just return mURI because in the case of queries that may
  * be lazily constructed from the query objects.
  */
 NS_IMETHODIMP
 nsNavHistoryQueryResultNode::GetUri(nsACString& aURI)
 {
-  nsresult rv = VerifyQuerySerialized();
-  NS_ENSURE_SUCCESS(rv, rv);
   aURI = mURI;
   return NS_OK;
 }
 
 
 NS_IMETHODIMP
 nsNavHistoryQueryResultNode::GetFolderItemId(int64_t* aItemId)
 {
@@ -1929,19 +1962,16 @@ NS_IMETHODIMP
 nsNavHistoryQueryResultNode::GetTargetFolderGuid(nsACString& aGuid) {
   aGuid = EmptyCString();
   return NS_OK;
 }
 
 NS_IMETHODIMP
 nsNavHistoryQueryResultNode::GetQuery(nsINavHistoryQuery** _query)
 {
-  nsresult rv = VerifyQueryParsed();
-  NS_ENSURE_SUCCESS(rv, rv);
-
   nsCOMPtr<nsINavHistoryQuery> query = do_QueryInterface(mQuery);
   query.forget(_query);
   return NS_OK;
 }
 
 
 NS_IMETHODIMP
 nsNavHistoryQueryResultNode::GetQueryOptions(nsINavHistoryQueryOptions** _options)
@@ -1953,87 +1983,33 @@ nsNavHistoryQueryResultNode::GetQueryOpt
 }
 
 /**
  * Safe options getter, ensures query is parsed first.
  */
 nsNavHistoryQueryOptions*
 nsNavHistoryQueryResultNode::Options()
 {
-  nsresult rv = VerifyQueryParsed();
-  if (NS_FAILED(rv))
-    return nullptr;
   MOZ_ASSERT(mOptions, "Options invalid, cannot generate from URI");
   return mOptions;
 }
 
-
-nsresult
-nsNavHistoryQueryResultNode::VerifyQueryParsed()
-{
-  if (mQuery) {
-    MOZ_ASSERT(mOriginalOptions && mOptions,
-               "A result with a parsed query must have options");
-    return NS_OK;
-  }
-  NS_ASSERTION(!mURI.IsEmpty(),
-               "Query nodes must have either a URI or query/options");
-
-  nsNavHistory* history = nsNavHistory::GetHistoryService();
-  NS_ENSURE_TRUE(history, NS_ERROR_OUT_OF_MEMORY);
-
-  nsCOMPtr<nsINavHistoryQuery> query;
-  nsCOMPtr<nsINavHistoryQueryOptions> options;
-  nsresult rv = history->QueryStringToQuery(mURI, getter_AddRefs(query),
-                                            getter_AddRefs(options));
-  NS_ENSURE_SUCCESS(rv, rv);
-  mOptions = do_QueryObject(options);
-  NS_ENSURE_STATE(mOptions);
-  mQuery = do_QueryObject(query);
-  NS_ENSURE_STATE(mQuery);
-  mLiveUpdate = history->GetUpdateRequirements(mQuery, mOptions,
-                                               &mHasSearchTerms);
-  return NS_OK;
-}
-
-
-nsresult
-nsNavHistoryQueryResultNode::VerifyQuerySerialized()
-{
-  if (!mURI.IsEmpty()) {
-    return NS_OK;
-  }
-  MOZ_ASSERT(mQuery && mOptions,
-             "Query nodes must have either a URI or query/options");
-
-  nsNavHistory* history = nsNavHistory::GetHistoryService();
-  NS_ENSURE_TRUE(history, NS_ERROR_OUT_OF_MEMORY);
-  nsCOMPtr<nsINavHistoryQuery> query = do_QueryInterface(mQuery);
-  nsresult rv = history->QueryToQueryString(query, mOriginalOptions, mURI);
-  NS_ENSURE_SUCCESS(rv, rv);
-  NS_ENSURE_STATE(!mURI.IsEmpty());
-  return NS_OK;
-}
-
-
 nsresult
 nsNavHistoryQueryResultNode::FillChildren()
 {
-  NS_ASSERTION(!mContentsValid,
-               "Don't call FillChildren when contents are valid");
-  NS_ASSERTION(mChildren.Count() == 0,
-               "We are trying to fill children when there already are some");
-
+  MOZ_ASSERT(!mContentsValid,
+             "Don't call FillChildren when contents are valid");
+  MOZ_ASSERT(mChildren.Count() == 0,
+             "We are trying to fill children when there already are some");
+  NS_ENSURE_STATE(mQuery && mOptions);
+
+  // get the results from the history service
   nsNavHistory* history = nsNavHistory::GetHistoryService();
   NS_ENSURE_TRUE(history, NS_ERROR_OUT_OF_MEMORY);
-
-  // get the results from the history service
-  nsresult rv = VerifyQueryParsed();
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = history->GetQueryResults(this, mQuery, mOptions, &mChildren);
+  nsresult rv = history->GetQueryResults(this, mQuery, mOptions, &mChildren);
   NS_ENSURE_SUCCESS(rv, rv);
 
   // it is important to call FillStats to fill in the parents on all
   // nodes and the result node pointers on the containers
   FillStats();
 
   uint16_t sortType = GetSortType();
 
@@ -2932,17 +2908,17 @@ nsNavHistoryQueryResultNode::OnItemMoved
 NS_IMPL_ISUPPORTS_INHERITED(nsNavHistoryFolderResultNode,
                             nsNavHistoryContainerResultNode,
                             nsINavHistoryQueryResultNode,
                             mozIStorageStatementCallback)
 
 nsNavHistoryFolderResultNode::nsNavHistoryFolderResultNode(
     const nsACString& aTitle, nsNavHistoryQueryOptions* aOptions,
     int64_t aFolderId) :
-  nsNavHistoryContainerResultNode(EmptyCString(), aTitle,
+  nsNavHistoryContainerResultNode(EmptyCString(), aTitle, 0,
                                   nsNavHistoryResultNode::RESULT_TYPE_FOLDER,
                                   aOptions),
   mContentsValid(false),
   mTargetFolderItemId(aFolderId),
   mIsRegisteredFolderObserver(false)
 {
   mItemId = aFolderId;
 }
@@ -3053,17 +3029,16 @@ nsNavHistoryFolderResultNode::GetUri(nsA
     aURI = mURI;
     return NS_OK;
   }
 
   nsCOMPtr<nsINavHistoryQuery> query;
   nsresult rv = GetQuery(getter_AddRefs(query));
   NS_ENSURE_SUCCESS(rv, rv);
 
-  // make array of our 1 query
   nsNavHistory* history = nsNavHistory::GetHistoryService();
   NS_ENSURE_TRUE(history, NS_ERROR_OUT_OF_MEMORY);
   rv = history->QueryToQueryString(query, mOriginalOptions, mURI);
   NS_ENSURE_SUCCESS(rv, rv);
   aURI = mURI;
   return NS_OK;
 }
 
@@ -3537,17 +3512,16 @@ nsNavHistoryFolderResultNode::OnItemAdde
     NS_ENSURE_TRUE(bookmarks, NS_ERROR_OUT_OF_MEMORY);
     rv = bookmarks->ResultNodeForContainer(aItemId,
                                            new nsNavHistoryQueryOptions(),
                                            getter_AddRefs(node));
     NS_ENSURE_SUCCESS(rv, rv);
   }
   else if (aItemType == nsINavBookmarksService::TYPE_SEPARATOR) {
     node = new nsNavHistorySeparatorResultNode();
-    NS_ENSURE_TRUE(node, NS_ERROR_OUT_OF_MEMORY);
     node->mItemId = aItemId;
     node->mBookmarkGuid = aGUID;
     node->mDateAdded = aDateAdded;
     node->mLastModified = aDateAdded;
   }
 
   node->mBookmarkIndex = aIndex;
 

--- a/toolkit/components/places/nsNavHistoryResult.h
+++ b/toolkit/components/places/nsNavHistoryResult.h
@@ -422,19 +422,16 @@ NS_DEFINE_STATIC_IID_ACCESSOR(nsNavHisto
   { 0x6e3bf8d3, 0x22aa, 0x4065, { 0x86, 0xbc, 0x37, 0x46, 0xb5, 0xb3, 0x2c, 0xe8 } }
 
 class nsNavHistoryContainerResultNode : public nsNavHistoryResultNode,
                                         public nsINavHistoryContainerResultNode
 {
 public:
   nsNavHistoryContainerResultNode(
     const nsACString& aURI, const nsACString& aTitle,
-    uint32_t aContainerType, nsNavHistoryQueryOptions* aOptions);
-  nsNavHistoryContainerResultNode(
-    const nsACString& aURI, const nsACString& aTitle,
     PRTime aTime, uint32_t aContainerType, nsNavHistoryQueryOptions* aOptions);
 
   virtual nsresult Refresh();
 
   NS_DECLARE_STATIC_IID_ACCESSOR(NS_NAVHISTORYCONTAINERRESULTNODE_IID)
 
   NS_DECL_ISUPPORTS_INHERITED
   NS_DECL_CYCLE_COLLECTION_CLASS_INHERITED(nsNavHistoryContainerResultNode, nsNavHistoryResultNode)
@@ -614,24 +611,20 @@ NS_DEFINE_STATIC_IID_ACCESSOR(nsNavHisto
 //    bookmark notifications.
 
 class nsNavHistoryQueryResultNode final : public nsNavHistoryContainerResultNode,
                                           public nsINavHistoryQueryResultNode,
                                           public nsINavBookmarkObserver
 {
 public:
   nsNavHistoryQueryResultNode(const nsACString& aTitle,
-                              const nsACString& aQueryURI);
-  nsNavHistoryQueryResultNode(const nsACString& aTitle,
+                              PRTime aTime,
+                              const nsACString& aQueryURI,
                               const RefPtr<nsNavHistoryQuery>& aQuery,
-                              nsNavHistoryQueryOptions* aOptions);
-  nsNavHistoryQueryResultNode(const nsACString& aTitle,
-                              PRTime aTime,
-                              const RefPtr<nsNavHistoryQuery>& aQuery,
-                              nsNavHistoryQueryOptions* aOptions);
+                              const RefPtr<nsNavHistoryQueryOptions>& aOptions);
 
   NS_DECL_ISUPPORTS_INHERITED
   NS_FORWARD_COMMON_RESULTNODE_TO_BASE
   NS_IMETHOD GetType(uint32_t* type) override
     { *type = nsNavHistoryResultNode::RESULT_TYPE_QUERY; return NS_OK; }
   NS_IMETHOD GetUri(nsACString& aURI) override; // does special lazy creation
   NS_FORWARD_CONTAINERNODE_EXCEPT_HASCHILDREN
   NS_IMETHOD GetHasChildren(bool* aHasChildren) override;
@@ -650,26 +643,19 @@ public:
   // query nodes when the visited uri belongs to them. If no such query exists,
   // the history result creates a new query node dynamically.
   nsresult OnVisit(nsIURI* aURI, int64_t aVisitId, PRTime aTime,
                    uint32_t aTransitionType, bool aHidden,
                    uint32_t* aAdded);
   virtual void OnRemoving() override;
 
 public:
-  // This constructs lazily mURI from mQuery and mOptions.
-  // Either this or mQuery/mOptions should be valid.
-  nsresult VerifyQuerySerialized();
-
-  // This may be constructed lazily from mURI, call VerifyQueryParsed.
-  // Either this or mURI should be valid.
   RefPtr<nsNavHistoryQuery> mQuery;
   uint32_t mLiveUpdate; // one of QUERYUPDATE_* in nsNavHistory.h
   bool mHasSearchTerms;
-  nsresult VerifyQueryParsed();
 
   // safe options getter, ensures query is parsed
   nsNavHistoryQueryOptions* Options();
 
   // this indicates whether the query contents are valid, they don't go away
   // after the container is closed until a notification comes in
   bool mContentsValid;
 

--- a/toolkit/components/places/tests/PlacesTestUtils.jsm
+++ b/toolkit/components/places/tests/PlacesTestUtils.jsm
@@ -386,9 +386,31 @@ var PlacesTestUtils = Object.freeze({
   clearMetadata() {
     return PlacesUtils.withConnectionWrapper("PlacesTestUtils: clearMetadata",
       async db => {
         await db.execute(`DELETE FROM moz_meta`);
         PlacesUtils.metadata.cache.clear();
       }
     );
   },
+
+  /**
+   * Compares 2 place: URLs ignoring the order of their params.
+   * @param url1 First URL to compare
+   * @param url2 Second URL to compare
+   * @return whether the URLs are the same
+   */
+  ComparePlacesURIs(url1, url2) {
+    url1 = url1 instanceof Ci.nsIURI ? url1.spec : new URL(url1);
+    if (url1.protocol != "place:")
+      throw new Error("Expected a place: uri, got " + url1.href);
+    url2 = url2 instanceof Ci.nsIURI ? url2.spec : new URL(url2);
+    if (url2.protocol != "place:")
+      throw new Error("Expected a place: uri, got " + url2.href);
+    let tokens1 = url1.pathname.split("&").sort().join("&");
+    let tokens2 = url2.pathname.split("&").sort().join("&");
+    if (tokens1 != tokens2) {
+      dump(`Failed comparison between:\n${tokens1}\n${tokens2}\n`);
+      return false;
+    }
+    return true;
+  },
 });

--- a/toolkit/components/places/tests/queries/test_results-as-left-pane.js
+++ b/toolkit/components/places/tests/queries/test_results-as-left-pane.js
@@ -7,21 +7,21 @@ const expectedRoots = [{
   uri: `place:sort=${Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING}&type=${Ci.nsINavHistoryQueryOptions.RESULTS_AS_DATE_QUERY}`,
   guid: "history____v",
 }, {
   title: "OrganizerQueryDownloads",
   uri: `place:transition=${Ci.nsINavHistoryService.TRANSITION_DOWNLOAD}&sort=${Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING}`,
   guid: "downloads__v",
 }, {
   title: "TagsFolderTitle",
-  uri: `place:sort=${Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING}&type=${Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAG_QUERY}&queryType=1`,
+  uri: `place:sort=${Ci.nsINavHistoryQueryOptions.SORT_BY_TITLE_ASCENDING}&type=${Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAG_QUERY}`,
   guid: "tags_______v",
 }, {
   title: "OrganizerQueryAllBookmarks",
-  uri: `place:type=${Ci.nsINavHistoryQueryOptions.RESULTS_AS_ROOTS_QUERY}&queryType=1`,
+  uri: `place:type=${Ci.nsINavHistoryQueryOptions.RESULTS_AS_ROOTS_QUERY}`,
   guid: "allbms_____v",
 }];
 
 const placesStrings = Services.strings.createBundle("chrome://places/locale/places.properties");
 
 function getLeftPaneQuery() {
   var query = PlacesUtils.history.getNewQuery();
 
@@ -33,18 +33,18 @@ function getLeftPaneQuery() {
   var result = PlacesUtils.history.executeQuery(query, options);
   return result.root;
 }
 
 function assertExpectedChildren(root, expectedChildren) {
   Assert.equal(root.childCount, expectedChildren.length, "Should have the expected number of children.");
 
   for (let i = 0; i < root.childCount; i++) {
-    Assert.equal(root.getChild(i).uri, expectedChildren[i].uri,
-                 "Should have the correct uri for root ${i}");
+    Assert.ok(PlacesTestUtils.ComparePlacesURIs(root.getChild(i).uri, expectedChildren[i].uri),
+              "Should have the correct uri for root ${i}");
     Assert.equal(root.getChild(i).title, placesStrings.GetStringFromName(expectedChildren[i].title),
                  "Should have the correct title for root ${i}");
     Assert.equal(root.getChild(i).bookmarkGuid, expectedChildren[i].guid);
   }
 }
 
 /**
  * This test will test the basic RESULTS_AS_ROOTS_QUERY, that simply returns,