--- a/toolkit/components/places/nsNavHistoryResult.cpp
+++ b/toolkit/components/places/nsNavHistoryResult.cpp
@@ -128,17 +128,20 @@ getUpdateRequirements(const RefPtr<nsNav
   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)
+  uint16_t sortingMode = aOptions->SortingMode();
+  if (aOptions->MaxResults() > 0 &&
+      sortingMode != nsINavHistoryQueryOptions::SORT_BY_DATE_ASCENDING &&
+      sortingMode != nsINavHistoryQueryOptions::SORT_BY_DATE_DESCENDING)
     return QUERYUPDATE_COMPLEX;
 
   if (domainBasedItems)
     return QUERYUPDATE_HOST;
   if (!nonTimeBasedItems)
     return QUERYUPDATE_TIME;
 
   return QUERYUPDATE_SIMPLE;
@@ -2431,16 +2434,20 @@ static nsresult setHistoryDetailsCallbac
  */
 nsresult
 nsNavHistoryQueryResultNode::OnVisit(nsIURI* aURI, int64_t aVisitId,
                                      PRTime aTime, uint32_t aTransitionType,
                                      bool aHidden, uint32_t* aAdded)
 {
   if (aHidden && !mOptions->IncludeHidden())
     return NS_OK;
+  // Skip the notification if the query is filtered by specific transition types
+  // and this visit has a different one.
+  if (mTransitions.Length() > 0 && !mTransitions.Contains(aTransitionType))
+    return NS_OK;
 
   nsNavHistoryResult* result = GetResult();
   NS_ENSURE_STATE(result);
   if (result->mBatchInProgress &&
       ++mBatchChanges > MAX_BATCH_CHANGES_BEFORE_REFRESH) {
     nsresult rv = Refresh();
     NS_ENSURE_SUCCESS(rv, rv);
     return NS_OK;
@@ -2491,35 +2498,49 @@ nsNavHistoryQueryResultNode::OnVisit(nsI
           return NS_OK; // after our time range
       }
       // Now we know that our visit satisfies the time range, fall through to
       // the QUERYUPDATE_SIMPLE case below.
       MOZ_FALLTHROUGH;
     }
 
     case QUERYUPDATE_SIMPLE: {
-      // If the query is filtered by some transitions, skip the
-      // update if aTransitionType doesn't match any of them.
-      if (mTransitions.Length() > 0 && !mTransitions.Contains(aTransitionType))
-        return NS_OK;
-
       // The history service can tell us whether the new item should appear
       // in the result.  We first have to construct a node for it to check.
       RefPtr<nsNavHistoryResultNode> addition;
       nsresult rv = history->VisitIdToResultNode(aVisitId, mOptions,
                                                  getter_AddRefs(addition));
       NS_ENSURE_SUCCESS(rv, rv);
       if (!addition) {
         // Certain result types manage the nodes by themselves.
         return NS_OK;
       }
       addition->mTransitionType = aTransitionType;
       if (!evaluateQueryForNode(mQuery, mOptions, addition))
         return NS_OK; // don't need to include in our query
 
+      // Optimization for a common case: if the query has maxResults and is
+      // sorted by date, get the current boundaries and check if the added visit
+      // would fit.
+      // Later, we may have to remove the last child to respect maxResults.
+      if (mOptions->MaxResults() &&
+          static_cast<uint32_t>(mChildren.Count()) >= mOptions->MaxResults()) {
+        uint16_t sortType = GetSortType();
+        if (sortType == nsINavHistoryQueryOptions::SORT_BY_DATE_ASCENDING &&
+            aTime > std::max(mChildren[0]->mTime,
+                             mChildren[mChildren.Count() -1]->mTime)) {
+          return NS_OK;
+        }
+        if (sortType == nsINavHistoryQueryOptions::SORT_BY_DATE_DESCENDING &&
+            aTime < std::min(mChildren[0]->mTime,
+                             mChildren[mChildren.Count() -1]->mTime)) {
+          return NS_OK;
+        }
+      }
+
       if (mOptions->ResultType() == nsNavHistoryQueryOptions::RESULTS_AS_VISIT) {
         // If this is a visit type query, just insert the new visit.  We never
         // update visits, only add or remove them.
         rv = InsertSortedChild(addition);
         NS_ENSURE_SUCCESS(rv, rv);
       } else {
         uint16_t sortType = GetSortType();
         bool updateSorting =
@@ -2534,16 +2555,22 @@ nsNavHistoryQueryResultNode::OnVisit(nsI
                         setHistoryDetailsCallback,
                         const_cast<void*>(static_cast<void*>(addition.get())))) {
           // Couldn't find a node to update.
           rv = InsertSortedChild(addition);
           NS_ENSURE_SUCCESS(rv, rv);
         }
       }
 
+      // Trim the children if necessary.
+      if (mOptions->MaxResults() &&
+          static_cast<uint32_t>(mChildren.Count()) > mOptions->MaxResults()) {
+        mChildren.RemoveObjectAt(mChildren.Count() - 1);
+      }
+
       if (aAdded)
         ++(*aAdded);
 
       break;
     }
 
     case QUERYUPDATE_COMPLEX:
     case QUERYUPDATE_COMPLEX_WITH_BOOKMARKS:

new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/queries/test_downloadHistory_liveUpdate.js
@@ -0,0 +1,112 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// This test ensures that download history (filtered by transition) queries
+// don't invalidate (and requery) too often.
+
+function accumulateNotifications(result) {
+  let notifications = [];
+  let resultObserver = new Proxy(NavHistoryResultObserver, {
+    get(target, name) {
+      if (name == "check") {
+        result.removeObserver(resultObserver, false);
+        return expectedNotifications =>
+          Assert.deepEqual(notifications, expectedNotifications);
+      }
+      // ignore a few uninteresting notifications.
+      if (["QueryInterface", "containerStateChanged"].includes(name))
+        return () => {};
+      return () => {
+        notifications.push(name);
+      };
+    }
+  });
+  result.addObserver(resultObserver, false);
+  return resultObserver;
+}
+
+add_task(async function test_downloadhistory_query_notifications() {
+  const MAX_RESULTS = 5;
+  let query = PlacesUtils.history.getNewQuery();
+  query.setTransitions([PlacesUtils.history.TRANSITIONS.DOWNLOAD], 1);
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING;
+  options.maxResults = MAX_RESULTS;
+  let result = PlacesUtils.history.executeQuery(query, options);
+  let notifications = accumulateNotifications(result);
+  let root = PlacesUtils.asContainer(result.root);
+  root.containerOpen = true;
+  // Add more maxResults downloads in order.
+  let transitions = Object.values(PlacesUtils.history.TRANSITIONS);
+  for (let transition of transitions) {
+    let uri = Services.io.newURI("http://fx-search.com/" + transition);
+    await PlacesTestUtils.addVisits({ uri, transition, title: "test " + transition });
+    // For each visit also set apart:
+    //  - a bookmark
+    //  - an annotation
+    //  - an icon
+    await PlacesUtils.bookmarks.insert({
+      url: uri,
+      parentGuid: PlacesUtils.bookmarks.unfiledGuid
+    });
+    PlacesUtils.annotations.setPageAnnotation(uri, "test/anno", "testValue", 0,
+                                              PlacesUtils.annotations.EXPIRE_WITH_HISTORY);
+    await PlacesTestUtils.addFavicons(new Map([[uri.spec, SMALLPNG_DATA_URI.spec]]));
+  }
+  // Remove all the visits one by one.
+  for (let transition of transitions) {
+    let uri = Services.io.newURI("http://fx-search.com/" + transition);
+    await PlacesUtils.history.remove(uri);
+  }
+  root.containerOpen = false;
+  // We pretty much don't want to see invalidateContainer here, because that
+  // means we requeried.
+  // We also don't want to see changes caused by filtered-out transition types.
+  notifications.check(["nodeHistoryDetailsChanged",
+                       "nodeInserted",
+                       "nodeTitleChanged",
+                       "nodeIconChanged",
+                       "nodeRemoved"]);
+});
+
+add_task(async function test_downloadhistory_query_filtering() {
+  const MAX_RESULTS = 3;
+  let query = PlacesUtils.history.getNewQuery();
+  query.setTransitions([PlacesUtils.history.TRANSITIONS.DOWNLOAD], 1);
+  let options = PlacesUtils.history.getNewQueryOptions();
+  options.sortingMode = Ci.nsINavHistoryQueryOptions.SORT_BY_DATE_DESCENDING;
+  options.maxResults = MAX_RESULTS;
+  let result = PlacesUtils.history.executeQuery(query, options);
+  let root = PlacesUtils.asContainer(result.root);
+  root.containerOpen = true;
+  Assert.equal(root.childCount, 0, "No visits found");
+  // Add more than maxResults downloads.
+  let uris = [];
+  // Define a monotonic visit date to ensure results order stability.
+  let visitDate = Date.now() * 1000;
+  for (let i = 0; i < MAX_RESULTS + 1; ++i, visitDate += 1000) {
+    let uri = `http://fx-search.com/download/${i}`;
+    await PlacesTestUtils.addVisits({
+      uri,
+      transition: PlacesUtils.history.TRANSITIONS.DOWNLOAD,
+      visitDate
+    });
+    uris.push(uri);
+  }
+  // Add an older download visit out of the maxResults timeframe.
+  await PlacesTestUtils.addVisits({
+    uri: `http://fx-search.com/download/unordered`,
+    transition: PlacesUtils.history.TRANSITIONS.DOWNLOAD,
+    visitDate: new Date(Date.now() - 7200000)
+  });
+
+  Assert.equal(root.childCount, MAX_RESULTS, "Result should be limited");
+  // Invert the uris array because we are sorted by date descending.
+  uris.reverse();
+  for (let i = 0; i < root.childCount; ++i) {
+    let node = root.getChild(i);
+    Assert.equal(node.uri, uris[i], "Found the expected uri");
+  }
+
+  root.containerOpen = false;
+});

--- a/toolkit/components/places/tests/queries/xpcshell.ini
+++ b/toolkit/components/places/tests/queries/xpcshell.ini
@@ -3,16 +3,17 @@ head = head_queries.js
 skip-if = toolkit == 'android'
 
 [test_415716.js]
 [test_abstime-annotation-domain.js]
 [test_abstime-annotation-uri.js]
 [test_async.js]
 [test_bookmarks.js]
 [test_containersQueries_sorting.js]
+[test_downloadHistory_liveUpdate.js]
 [test_excludeQueries.js]
 [test_history_queries_tags_liveUpdate.js]
 [test_history_queries_titles_liveUpdate.js]
 [test_onlyBookmarked.js]
 [test_options_inherit.js]
 [test_query_uri_liveupdate.js]
 [test_queryMultipleFolder.js]
 [test_querySerialization.js]