--- a/toolkit/components/places/nsNavBookmarks.cpp
+++ b/toolkit/components/places/nsNavBookmarks.cpp
@@ -9,16 +9,17 @@
 #include "nsAnnotationService.h"
 #include "nsPlacesMacros.h"
 #include "Helpers.h"
 
 #include "nsAppDirectoryServiceDefs.h"
 #include "nsNetUtil.h"
 #include "nsUnicharUtils.h"
 #include "nsPrintfCString.h"
+#include "nsQueryObject.h"
 #include "mozilla/Preferences.h"
 #include "mozilla/storage.h"
 
 #include "GeckoProfiler.h"
 
 using namespace mozilla;
 
 // These columns sit to the right of the kGetInfoIndex_* columns.
@@ -2202,25 +2203,27 @@ nsNavBookmarks::OnPageChanged(nsIURI* aU
     // Favicons may be set to either pure URIs or to folder URIs
     bool isPlaceURI;
     rv = aURI->SchemeIs("place", &isPlaceURI);
     NS_ENSURE_SUCCESS(rv, rv);
     if (isPlaceURI) {
       nsNavHistory* history = nsNavHistory::GetHistoryService();
       NS_ENSURE_TRUE(history, NS_ERROR_OUT_OF_MEMORY);
 
-      nsCOMArray<nsNavHistoryQuery> queries;
-      nsCOMPtr<nsNavHistoryQueryOptions> options;
-      rv = history->QueryStringToQueryArray(changeData.bookmark.url,
-                                            &queries, getter_AddRefs(options));
+      nsCOMPtr<nsINavHistoryQuery> query;
+      nsCOMPtr<nsINavHistoryQueryOptions> options;
+      rv = history->QueryStringToQuery(changeData.bookmark.url,
+                                       getter_AddRefs(query),
+                                       getter_AddRefs(options));
       NS_ENSURE_SUCCESS(rv, rv);
 
-      if (queries.Count() == 1 && queries[0]->Folders().Length() == 1) {
+      RefPtr<nsNavHistoryQuery> queryObj = do_QueryObject(query);
+      if (queryObj->Folders().Length() == 1) {
         // Fetch missing data.
-        rv = FetchItemInfo(queries[0]->Folders()[0], changeData.bookmark);
+        rv = FetchItemInfo(queryObj->Folders()[0], changeData.bookmark);
         NS_ENSURE_SUCCESS(rv, rv);
         NotifyItemChanged(changeData);
       }
     }
     else {
       RefPtr< AsyncGetBookmarksForURI<ItemChangeMethod, ItemChangeData> > notifier =
         new AsyncGetBookmarksForURI<ItemChangeMethod, ItemChangeData>(this, &nsNavBookmarks::NotifyItemChanged, changeData);
       notifier->Init();

--- a/toolkit/components/places/nsNavHistory.cpp
+++ b/toolkit/components/places/nsNavHistory.cpp
@@ -3964,34 +3964,35 @@ nsNavHistory::QueryRowToResult(int64_t i
                                nsNavHistoryResultNode** aNode)
 {
   // Only assert if the itemId is set. In some cases (e.g. virtual queries), we
   // have a guid, but not an itemId.
   if (itemId != -1) {
     MOZ_ASSERT(!aBookmarkGuid.IsEmpty());
   }
 
-  nsCOMArray<nsNavHistoryQuery> queries;
-  nsCOMPtr<nsNavHistoryQueryOptions> options;
-  nsresult rv = QueryStringToQueryArray(aURI, &queries,
-                                        getter_AddRefs(options));
-
+  nsCOMPtr<nsINavHistoryQuery> query;
+  nsCOMPtr<nsINavHistoryQueryOptions> options;
+  nsresult rv = QueryStringToQuery(aURI, getter_AddRefs(query),
+                                   getter_AddRefs(options));
   RefPtr<nsNavHistoryResultNode> resultNode;
+  RefPtr<nsNavHistoryQuery> queryObj = do_QueryObject(query);
+  NS_ENSURE_STATE(queryObj);
+  RefPtr<nsNavHistoryQueryOptions> optionsObj = do_QueryObject(options);
+  NS_ENSURE_STATE(optionsObj);
   // If this failed the query does not parse correctly, let the error pass and
   // handle it later.
   if (NS_SUCCEEDED(rv)) {
     // Check if this is a folder shortcut, so we can take a faster path.
-    RefPtr<nsNavHistoryQuery> query = do_QueryObject(queries[0]);
-    NS_ENSURE_STATE(query);
-    int64_t targetFolderId = GetSimpleBookmarksQueryFolder(query, options);
+    int64_t targetFolderId = GetSimpleBookmarksQueryFolder(queryObj, optionsObj);
     if (targetFolderId) {
       nsNavBookmarks *bookmarks = nsNavBookmarks::GetBookmarksService();
       NS_ENSURE_TRUE(bookmarks, NS_ERROR_OUT_OF_MEMORY);
 
-      rv = bookmarks->ResultNodeForContainer(targetFolderId, options,
+      rv = bookmarks->ResultNodeForContainer(targetFolderId, optionsObj,
                                              getter_AddRefs(resultNode));
       // If this failed the shortcut is pointing to nowhere, let the error pass
       // and handle it later.
       if (NS_SUCCEEDED(rv)) {
         // At this point the node is set up like a regular folder node. Here
         // we make the necessary change to make it a folder shortcut.
         resultNode->GetAsFolder()->mTargetFolderItemId = targetFolderId;
         resultNode->mItemId = itemId;
@@ -4003,17 +4004,19 @@ 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, queries, options);
+      nsCOMArray<nsNavHistoryQuery> queries;
+      queries.AppendObject(queryObj);
+      resultNode = new nsNavHistoryQueryResultNode(aTitle, aTime, queries, 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

--- a/toolkit/components/places/nsNavHistory.h
+++ b/toolkit/components/places/nsNavHistory.h
@@ -316,21 +316,16 @@ public:
   nsresult BeginUpdateBatch();
   nsresult EndUpdateBatch();
 
   // The level of batches' nesting, 0 when no batches are open.
   int32_t mBatchLevel;
   // Current active transaction for a batch.
   mozStorageTransaction* mBatchDBTransaction;
 
-  // better alternative to QueryStringToQueries (in nsNavHistoryQuery.cpp)
-  nsresult QueryStringToQueryArray(const nsACString& aQueryString,
-                                   nsCOMArray<nsNavHistoryQuery>* aQueries,
-                                   nsNavHistoryQueryOptions** aOptions);
-
   typedef nsDataHashtable<nsCStringHashKey, nsCString> StringHash;
 
   /**
    * Indicates if it is OK to notify history observers or not.
    *
    * @return true if it is OK to notify, false otherwise.
    */
   bool canNotify() { return mCanNotify; }
@@ -640,19 +635,19 @@ protected:
   int32_t mTempRedirectVisitBonus;
   int32_t mRedirectSourceVisitBonus;
   int32_t mDefaultVisitBonus;
   int32_t mUnvisitedBookmarkBonus;
   int32_t mUnvisitedTypedBonus;
   int32_t mReloadVisitBonus;
 
   // in nsNavHistoryQuery.cpp
-  nsresult TokensToQueries(const nsTArray<QueryKeyValuePair>& aTokens,
-                           nsCOMArray<nsNavHistoryQuery>* aQueries,
-                           nsNavHistoryQueryOptions* aOptions);
+  nsresult TokensToQuery(const nsTArray<QueryKeyValuePair>& aTokens,
+                         nsNavHistoryQuery* aQuery,
+                         nsNavHistoryQueryOptions* aOptions);
 
   int64_t mTagsFolder;
 
   int32_t mDaysOfHistory;
   int64_t mLastCachedStartOfDay;
   int64_t mLastCachedEndOfDay;
 
   // Used to enable and disable the observer notifications

--- a/toolkit/components/places/nsNavHistoryQuery.cpp
+++ b/toolkit/components/places/nsNavHistoryQuery.cpp
@@ -237,83 +237,43 @@ 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
 
-//    From C++ places code, you should use QueryStringToQueryArray, this is
-//    the harder-to-use XPCOM version.
 
 NS_IMETHODIMP
 nsNavHistory::QueryStringToQuery(const nsACString& aQueryString,
                                  nsINavHistoryQuery** _query,
                                  nsINavHistoryQueryOptions** _options)
 {
   NS_ENSURE_ARG_POINTER(_query);
   NS_ENSURE_ARG_POINTER(_options);
 
-  nsCOMPtr<nsNavHistoryQueryOptions> options;
-  nsCOMArray<nsNavHistoryQuery> queries;
-  nsresult rv = QueryStringToQueryArray(aQueryString, &queries,
-                                        getter_AddRefs(options));
+  nsTArray<QueryKeyValuePair> tokens;
+  nsresult rv = TokenizeQueryString(aQueryString, &tokens);
   NS_ENSURE_SUCCESS(rv, rv);
 
-  nsCOMPtr<nsINavHistoryQuery> query;
-  if (queries.Count() == 0) {
-    NS_WARNING("Invalid Places query: ");
-    NS_WARNING(PromiseFlatCString(aQueryString).get());
-    query = new nsNavHistoryQuery();
-    options = new nsNavHistoryQueryOptions();
-  } else {
-    query = do_QueryInterface(queries[0]);
-  }
-  MOZ_ASSERT(query);
-  query.forget(_query);
-  options.forget(_options);
-  return NS_OK;
-}
-
-
-// nsNavHistory::QueryStringToQueryArray
-//
-//    An internal version of QueryStringToQueries that fills a COM array for
-//    ease-of-use.
-
-nsresult
-nsNavHistory::QueryStringToQueryArray(const nsACString& aQueryString,
-                                      nsCOMArray<nsNavHistoryQuery>* aQueries,
-                                      nsNavHistoryQueryOptions** aOptions)
-{
-  nsresult rv;
-  aQueries->Clear();
-  *aOptions = nullptr;
-
-  RefPtr<nsNavHistoryQueryOptions> options(new nsNavHistoryQueryOptions());
-  if (! options)
-    return NS_ERROR_OUT_OF_MEMORY;
-
-  nsTArray<QueryKeyValuePair> tokens;
-  rv = TokenizeQueryString(aQueryString, &tokens);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = TokensToQueries(tokens, aQueries, options);
+  RefPtr<nsNavHistoryQueryOptions> options = new nsNavHistoryQueryOptions();
+  RefPtr<nsNavHistoryQuery> query = new nsNavHistoryQuery();
+  rv = TokensToQuery(tokens, query, options);
+  MOZ_ASSERT(NS_SUCCEEDED(rv), "The query string should be valid");
   if (NS_FAILED(rv)) {
     NS_WARNING("Unable to parse the query string: ");
     NS_WARNING(PromiseFlatCString(aQueryString).get());
-    return rv;
   }
 
-  options.forget(aOptions);
+  options.forget(_options);
+  query.forget(_query);
   return NS_OK;
 }
 
-
 NS_IMETHODIMP
 nsNavHistory::QueryToQueryString(nsINavHistoryQuery *aQuery,
                                  nsINavHistoryQueryOptions* aOptions,
                                  nsACString& aQueryString)
 {
   NS_ENSURE_ARG(aQuery);
   NS_ENSURE_ARG(aOptions);
 
@@ -591,92 +551,84 @@ TokenizeQueryString(const nsACString& aQ
   if (query.Length() - keyFirstIndex > 1) {
     if (! aTokens->AppendElement(QueryKeyValuePair(query, keyFirstIndex,
                                                    equalsIndex, query.Length())))
       return NS_ERROR_OUT_OF_MEMORY;
   }
   return NS_OK;
 }
 
-// nsNavHistory::TokensToQueries
-
 nsresult
-nsNavHistory::TokensToQueries(const nsTArray<QueryKeyValuePair>& aTokens,
-                              nsCOMArray<nsNavHistoryQuery>* aQueries,
-                              nsNavHistoryQueryOptions* aOptions)
+nsNavHistory::TokensToQuery(const nsTArray<QueryKeyValuePair>& aTokens,
+                            nsNavHistoryQuery* aQuery,
+                            nsNavHistoryQueryOptions* aOptions)
 {
   nsresult rv;
 
-  nsCOMPtr<nsNavHistoryQuery> query(new nsNavHistoryQuery());
-  if (! query)
-    return NS_ERROR_OUT_OF_MEMORY;
-  if (! aQueries->AppendObject(query))
-    return NS_ERROR_OUT_OF_MEMORY;
-
   if (aTokens.Length() == 0)
-    return NS_OK; // nothing to do
+    return NS_OK;
 
   nsTArray<int64_t> folders;
   nsTArray<nsString> tags;
   nsTArray<uint32_t> transitions;
   for (uint32_t i = 0; i < aTokens.Length(); i ++) {
     const QueryKeyValuePair& kvp = aTokens[i];
 
     // begin time
     if (kvp.key.EqualsLiteral(QUERYKEY_BEGIN_TIME)) {
-      SetQueryKeyInt64(kvp.value, query, &nsINavHistoryQuery::SetBeginTime);
+      SetQueryKeyInt64(kvp.value, aQuery, &nsINavHistoryQuery::SetBeginTime);
 
     // begin time reference
     } else if (kvp.key.EqualsLiteral(QUERYKEY_BEGIN_TIME_REFERENCE)) {
-      SetQueryKeyUint32(kvp.value, query, &nsINavHistoryQuery::SetBeginTimeReference);
+      SetQueryKeyUint32(kvp.value, aQuery, &nsINavHistoryQuery::SetBeginTimeReference);
 
     // end time
     } else if (kvp.key.EqualsLiteral(QUERYKEY_END_TIME)) {
-      SetQueryKeyInt64(kvp.value, query, &nsINavHistoryQuery::SetEndTime);
+      SetQueryKeyInt64(kvp.value, aQuery, &nsINavHistoryQuery::SetEndTime);
 
     // end time reference
     } else if (kvp.key.EqualsLiteral(QUERYKEY_END_TIME_REFERENCE)) {
-      SetQueryKeyUint32(kvp.value, query, &nsINavHistoryQuery::SetEndTimeReference);
+      SetQueryKeyUint32(kvp.value, aQuery, &nsINavHistoryQuery::SetEndTimeReference);
 
     // search terms
     } else if (kvp.key.EqualsLiteral(QUERYKEY_SEARCH_TERMS)) {
       nsCString unescapedTerms = kvp.value;
       NS_UnescapeURL(unescapedTerms); // modifies input
-      rv = query->SetSearchTerms(NS_ConvertUTF8toUTF16(unescapedTerms));
+      rv = aQuery->SetSearchTerms(NS_ConvertUTF8toUTF16(unescapedTerms));
       NS_ENSURE_SUCCESS(rv, rv);
 
     // min visits
     } else if (kvp.key.EqualsLiteral(QUERYKEY_MIN_VISITS)) {
       int32_t visits = kvp.value.ToInteger(&rv);
       if (NS_SUCCEEDED(rv))
-        query->SetMinVisits(visits);
+        aQuery->SetMinVisits(visits);
       else
         NS_WARNING("Bad number for minVisits in query");
 
     // max visits
     } else if (kvp.key.EqualsLiteral(QUERYKEY_MAX_VISITS)) {
       int32_t visits = kvp.value.ToInteger(&rv);
       if (NS_SUCCEEDED(rv))
-        query->SetMaxVisits(visits);
+        aQuery->SetMaxVisits(visits);
       else
         NS_WARNING("Bad number for maxVisits in query");
 
     // onlyBookmarked flag
     } else if (kvp.key.EqualsLiteral(QUERYKEY_ONLY_BOOKMARKED)) {
-      SetQueryKeyBool(kvp.value, query, &nsINavHistoryQuery::SetOnlyBookmarked);
+      SetQueryKeyBool(kvp.value, aQuery, &nsINavHistoryQuery::SetOnlyBookmarked);
 
     // domainIsHost flag
     } else if (kvp.key.EqualsLiteral(QUERYKEY_DOMAIN_IS_HOST)) {
-      SetQueryKeyBool(kvp.value, query, &nsINavHistoryQuery::SetDomainIsHost);
+      SetQueryKeyBool(kvp.value, aQuery, &nsINavHistoryQuery::SetDomainIsHost);
 
     // domain string
     } else if (kvp.key.EqualsLiteral(QUERYKEY_DOMAIN)) {
       nsAutoCString unescapedDomain(kvp.value);
       NS_UnescapeURL(unescapedDomain); // modifies input
-      rv = query->SetDomain(unescapedDomain);
+      rv = aQuery->SetDomain(unescapedDomain);
       NS_ENSURE_SUCCESS(rv, rv);
 
     // folders
     } else if (kvp.key.EqualsLiteral(QUERYKEY_FOLDER)) {
       int64_t folder;
       if (PR_sscanf(kvp.value.get(), "%lld", &folder) == 1) {
         NS_ENSURE_TRUE(folders.AppendElement(folder), NS_ERROR_OUT_OF_MEMORY);
       } else {
@@ -691,45 +643,45 @@ nsNavHistory::TokensToQueries(const nsTA
     } else if (kvp.key.EqualsLiteral(QUERYKEY_URI)) {
       nsAutoCString unescapedUri(kvp.value);
       NS_UnescapeURL(unescapedUri); // modifies input
       nsCOMPtr<nsIURI> uri;
       nsresult rv = NS_NewURI(getter_AddRefs(uri), unescapedUri);
       if (NS_FAILED(rv)) {
         NS_WARNING("Unable to parse URI");
       }
-      rv = query->SetUri(uri);
+      rv = aQuery->SetUri(uri);
       NS_ENSURE_SUCCESS(rv, rv);
 
     // not annotation
     } else if (kvp.key.EqualsLiteral(QUERYKEY_NOTANNOTATION)) {
       nsAutoCString unescaped(kvp.value);
       NS_UnescapeURL(unescaped); // modifies input
-      query->SetAnnotationIsNot(true);
-      query->SetAnnotation(unescaped);
+      aQuery->SetAnnotationIsNot(true);
+      aQuery->SetAnnotation(unescaped);
 
     // annotation
     } else if (kvp.key.EqualsLiteral(QUERYKEY_ANNOTATION)) {
       nsAutoCString unescaped(kvp.value);
       NS_UnescapeURL(unescaped); // modifies input
-      query->SetAnnotationIsNot(false);
-      query->SetAnnotation(unescaped);
+      aQuery->SetAnnotationIsNot(false);
+      aQuery->SetAnnotation(unescaped);
 
     // tag
     } else if (kvp.key.EqualsLiteral(QUERYKEY_TAG)) {
       nsAutoCString unescaped(kvp.value);
       NS_UnescapeURL(unescaped); // modifies input
       NS_ConvertUTF8toUTF16 tag(unescaped);
       if (!tags.Contains(tag)) {
         NS_ENSURE_TRUE(tags.AppendElement(tag), NS_ERROR_OUT_OF_MEMORY);
       }
 
     // not tags
     } else if (kvp.key.EqualsLiteral(QUERYKEY_NOTTAGS)) {
-      SetQueryKeyBool(kvp.value, query, &nsINavHistoryQuery::SetTagsAreNot);
+      SetQueryKeyBool(kvp.value, aQuery, &nsINavHistoryQuery::SetTagsAreNot);
 
     // transition
     } else if (kvp.key.EqualsLiteral(QUERYKEY_TRANSITION)) {
       uint32_t transition = kvp.value.ToInteger(&rv);
       if (NS_SUCCEEDED(rv)) {
         if (!transitions.Contains(transition))
           NS_ENSURE_TRUE(transitions.AppendElement(transition),
                          NS_ERROR_OUT_OF_MEMORY);
@@ -791,25 +743,25 @@ nsNavHistory::TokensToQueries(const nsTA
     // unknown key
     } else {
       NS_WARNING("TokensToQueries(), ignoring unknown key: ");
       NS_WARNING(kvp.key.get());
     }
   }
 
   if (folders.Length() != 0)
-    query->SetFolders(folders.Elements(), folders.Length());
+    aQuery->SetFolders(folders.Elements(), folders.Length());
 
   if (tags.Length() > 0) {
-    rv = query->SetTags(tags);
+    rv = aQuery->SetTags(tags);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   if (transitions.Length() > 0) {
-    rv = query->SetTransitions(transitions);
+    rv = aQuery->SetTransitions(transitions);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   return NS_OK;
 }
 
 
 // ParseQueryBooleanString

--- a/toolkit/components/places/nsNavHistoryResult.cpp
+++ b/toolkit/components/places/nsNavHistoryResult.cpp
@@ -1999,20 +1999,26 @@ nsNavHistoryQueryResultNode::VerifyQueri
     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);
 
-  nsresult rv = history->QueryStringToQueryArray(mURI, &mQueries,
-                                                 getter_AddRefs(mOptions));
+  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);
+  RefPtr<nsNavHistoryQuery> queryObj = do_QueryObject(query);
+  NS_ENSURE_STATE(queryObj);
+  mQueries.AppendObject(queryObj);
   mLiveUpdate = history->GetUpdateRequirements(mQueries, mOptions,
                                                &mHasSearchTerms);
   return NS_OK;
 }
 
 
 nsresult
 nsNavHistoryQueryResultNode::VerifyQueriesSerialized()