--- a/services/sync/tests/unit/test_history_store.js
+++ b/services/sync/tests/unit/test_history_store.js
@@ -177,16 +177,19 @@ add_task(async function test_null_title(
 add_task(async function test_invalid_records() {
   _("Make sure we handle invalid URLs in places databases gracefully.");
   await PlacesUtils.withConnectionWrapper("test_invalid_record", async function(db) {
     await db.execute(
       "INSERT INTO moz_places "
       + "(url, url_hash, title, rev_host, visit_count, last_visit_date) "
       + "VALUES ('invalid-uri', hash('invalid-uri'), 'Invalid URI', '.', 1, " + TIMESTAMP3 + ")"
     );
+    // Trigger the update on moz_hosts by deleting the added rows from
+    // moz_updatehostsinsert_temp
+    await db.execute("DELETE FROM moz_updatehostsinsert_temp");
     // Add the corresponding visit to retain database coherence.
     await db.execute(
       "INSERT INTO moz_historyvisits "
       + "(place_id, visit_date, visit_type, session) "
       + "VALUES ((SELECT id FROM moz_places WHERE url_hash = hash('invalid-uri') AND url = 'invalid-uri'), "
       + TIMESTAMP3 + ", " + Ci.nsINavHistoryService.TRANSITION_TYPED + ", 1)"
     );
   });

--- a/toolkit/components/places/Bookmarks.jsm
+++ b/toolkit/components/places/Bookmarks.jsm
@@ -2342,47 +2342,49 @@ async function(db, folderGuids, options)
 };
 
 /**
  * Tries to insert a new place if it doesn't exist yet.
  * @param url
  *        A valid URL object.
  * @return {Promise} resolved when the operation is complete.
  */
-function maybeInsertPlace(db, url) {
+async function maybeInsertPlace(db, url) {
   // The IGNORE conflict can trigger on `guid`.
-  return db.executeCached(
+  await db.executeCached(
     `INSERT OR IGNORE INTO moz_places (url, url_hash, rev_host, hidden, frecency, guid)
      VALUES (:url, hash(:url), :rev_host, 0, :frecency,
              IFNULL((SELECT guid FROM moz_places WHERE url_hash = hash(:url) AND url = :url),
                     GENERATE_GUID()))
     `, { url: url.href,
          rev_host: PlacesUtils.getReversedHost(url),
          frecency: url.protocol == "place:" ? 0 : -1 });
+  await db.executeCached("DELETE FROM moz_updatehostsinsert_temp");
 }
 
 /**
  * Tries to insert a new place if it doesn't exist yet.
  * @param db
  *        The database to use
  * @param urls
  *        An array with all the url objects to insert.
  * @return {Promise} resolved when the operation is complete.
  */
-function maybeInsertManyPlaces(db, urls) {
-  return db.executeCached(
+async function maybeInsertManyPlaces(db, urls) {
+  await db.executeCached(
     `INSERT OR IGNORE INTO moz_places (url, url_hash, rev_host, hidden, frecency, guid) VALUES
      (:url, hash(:url), :rev_host, 0, :frecency,
      IFNULL((SELECT guid FROM moz_places WHERE url_hash = hash(:url) AND url = :url), :maybeguid))`,
      urls.map(url => ({
        url: url.href,
        rev_host: PlacesUtils.getReversedHost(url),
        frecency: url.protocol == "place:" ? 0 : -1,
        maybeguid: PlacesUtils.history.makeGuid(),
      })));
+  await db.executeCached("DELETE FROM moz_updatehostsinsert_temp");
 }
 
 // Indicates whether we should write a tombstone for an item that has been
 // uploaded to the server. We ignore "NEW" and "UNKNOWN" items: "NEW" items
 // haven't been uploaded yet, and "UNKNOWN" items need a full reconciliation
 // with the server.
 function needsTombstone(item) {
   return item._syncStatus == Bookmarks.SYNC_STATUS.NORMAL;

--- a/toolkit/components/places/Database.cpp
+++ b/toolkit/components/places/Database.cpp
@@ -1293,21 +1293,25 @@ Database::InitTempEntities()
   MOZ_ASSERT(NS_IsMainThread());
 
   nsresult rv = mMainConn->ExecuteSimpleSQL(CREATE_HISTORYVISITS_AFTERINSERT_TRIGGER);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = mMainConn->ExecuteSimpleSQL(CREATE_HISTORYVISITS_AFTERDELETE_TRIGGER);
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Add the triggers that update the moz_hosts table as necessary.
+  rv = mMainConn->ExecuteSimpleSQL(CREATE_UPDATEHOSTSINSERT_TEMP);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = mMainConn->ExecuteSimpleSQL(CREATE_UPDATEHOSTSINSERT_AFTERDELETE_TRIGGER);
+  NS_ENSURE_SUCCESS(rv, rv);
   rv = mMainConn->ExecuteSimpleSQL(CREATE_PLACES_AFTERINSERT_TRIGGER);
   NS_ENSURE_SUCCESS(rv, rv);
-  rv = mMainConn->ExecuteSimpleSQL(CREATE_UPDATEHOSTS_TEMP);
+  rv = mMainConn->ExecuteSimpleSQL(CREATE_UPDATEHOSTSDELETE_TEMP);
   NS_ENSURE_SUCCESS(rv, rv);
-  rv = mMainConn->ExecuteSimpleSQL(CREATE_UPDATEHOSTS_AFTERDELETE_TRIGGER);
+  rv = mMainConn->ExecuteSimpleSQL(CREATE_UPDATEHOSTSDELETE_AFTERDELETE_TRIGGER);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = mMainConn->ExecuteSimpleSQL(CREATE_PLACES_AFTERDELETE_TRIGGER);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = mMainConn->ExecuteSimpleSQL(CREATE_PLACES_AFTERUPDATE_FRECENCY_TRIGGER);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = mMainConn->ExecuteSimpleSQL(CREATE_PLACES_AFTERUPDATE_TYPED_TRIGGER);
   NS_ENSURE_SUCCESS(rv, rv);
 

--- a/toolkit/components/places/History.cpp
+++ b/toolkit/components/places/History.cpp
@@ -1065,16 +1065,26 @@ public:
       // Notify about title change if needed.
       if (place.titleChanged) {
         event = new NotifyTitleObservers(place.spec, place.title, place.guid);
         rv = NS_DispatchToMainThread(event);
         NS_ENSURE_SUCCESS(rv, rv);
       }
     }
 
+    {
+      // Trigger an update for all the hosts of the places we inserted
+      nsAutoCString query("DELETE FROM moz_updatehostsinsert_temp");
+      nsCOMPtr<mozIStorageStatement> stmt = mHistory->GetStatement(query);
+      NS_ENSURE_STATE(stmt);
+      mozStorageStatementScoper scoper(stmt);
+      nsresult rv = stmt->Execute();
+      NS_ENSURE_SUCCESS(rv, rv);
+    }
+
     nsresult rv = transaction.Commit();
     NS_ENSURE_SUCCESS(rv, rv);
 
     return NS_OK;
   }
 private:
   InsertVisitedURIs(
     mozIStorageConnection* aConnection,
@@ -1844,17 +1854,17 @@ private:
       mozStorageStatementScoper scoper(stmt);
       nsresult rv = stmt->Execute();
       NS_ENSURE_SUCCESS(rv, rv);
     }
 
     {
       // Hosts accumulated during the places delete are updated through a trigger
       // (see nsPlacesTriggers.h).
-      nsAutoCString query("DELETE FROM moz_updatehosts_temp");
+      nsAutoCString query("DELETE FROM moz_updatehostsdelete_temp");
       nsCOMPtr<mozIStorageStatement> stmt = mHistory->GetStatement(query);
       NS_ENSURE_STATE(stmt);
       mozStorageStatementScoper scoper(stmt);
       nsresult rv = stmt->Execute();
       NS_ENSURE_SUCCESS(rv, rv);
     }
 
     return NS_OK;

--- a/toolkit/components/places/History.jsm
+++ b/toolkit/components/places/History.jsm
@@ -764,17 +764,17 @@ var invalidateFrecencies = async functio
 };
 
 // Inner implementation of History.clear().
 var clear = async function(db) {
   await db.executeTransaction(async function() {
     // Remove all non-bookmarked places entries first, this will speed up the
     // triggers work.
     await db.execute(`DELETE FROM moz_places WHERE foreign_count = 0`);
-    await db.execute(`DELETE FROM moz_updatehosts_temp`);
+    await db.execute(`DELETE FROM moz_updatehostsdelete_temp`);
 
     // Expire orphan icons.
     await db.executeCached(`DELETE FROM moz_pages_w_icons
                             WHERE page_url_hash NOT IN (SELECT url_hash FROM moz_places)`);
     await db.executeCached(`DELETE FROM moz_icons WHERE id IN (
                               SELECT id FROM moz_icons WHERE root = 0
                               EXCEPT
                               SELECT icon_id FROM moz_icons_to_pages
@@ -853,17 +853,17 @@ var cleanupPages = async function(db, pa
   let idsList = sqlList(pagesToRemove.map(p => p.id));
   // Note, we are already in a transaction, since callers create it.
   // Check relations regardless, to avoid creating orphans in case of
   // async race conditions.
   await db.execute(`DELETE FROM moz_places WHERE id IN ( ${ idsList } )
                     AND foreign_count = 0 AND last_visit_date ISNULL`);
   // Hosts accumulated during the places delete are updated through a trigger
   // (see nsPlacesTriggers.h).
-  await db.executeCached(`DELETE FROM moz_updatehosts_temp`);
+  await db.executeCached(`DELETE FROM moz_updatehostsdelete_temp`);
 
   // Expire orphans.
   let hashesToRemove = pagesToRemove.map(p => p.hash);
   await db.executeCached(`DELETE FROM moz_pages_w_icons
                           WHERE page_url_hash IN (${sqlList(hashesToRemove)})`);
   await db.executeCached(`DELETE FROM moz_icons WHERE id IN (
                             SELECT id FROM moz_icons WHERE root = 0
                             EXCEPT

--- a/toolkit/components/places/PlacesUtils.jsm
+++ b/toolkit/components/places/PlacesUtils.jsm
@@ -2236,27 +2236,30 @@ var Keywords = {
              SET place_id = (SELECT id FROM moz_places WHERE url_hash = hash(:url) AND url = :url),
                  post_data = :post_data
              WHERE keyword = :keyword
             `, { url: url.href, keyword, post_data: postData });
           await notifyKeywordChange(oldEntry.url.href, "", source);
         } else {
           // An entry for the given page could be missing, in such a case we need to
           // create it.  The IGNORE conflict can trigger on `guid`.
-          await db.executeCached(
-            `INSERT OR IGNORE INTO moz_places (url, url_hash, rev_host, hidden, frecency, guid)
-             VALUES (:url, hash(:url), :rev_host, 0, :frecency,
-                     IFNULL((SELECT guid FROM moz_places WHERE url_hash = hash(:url) AND url = :url),
-                            GENERATE_GUID()))
-            `, { url: url.href, rev_host: PlacesUtils.getReversedHost(url),
-                 frecency: url.protocol == "place:" ? 0 : -1 });
-          await db.executeCached(
-            `INSERT INTO moz_keywords (keyword, place_id, post_data)
-             VALUES (:keyword, (SELECT id FROM moz_places WHERE url_hash = hash(:url) AND url = :url), :post_data)
-            `, { url: url.href, keyword, post_data: postData });
+          await db.executeTransaction(async function() {
+            await db.executeCached(
+              `INSERT OR IGNORE INTO moz_places (url, url_hash, rev_host, hidden, frecency, guid)
+               VALUES (:url, hash(:url), :rev_host, 0, :frecency,
+                       IFNULL((SELECT guid FROM moz_places WHERE url_hash = hash(:url) AND url = :url),
+                              GENERATE_GUID()))
+              `, { url: url.href, rev_host: PlacesUtils.getReversedHost(url),
+                   frecency: url.protocol == "place:" ? 0 : -1 });
+            await db.executeCached("DELETE FROM moz_updatehostsinsert_temp");
+            await db.executeCached(
+              `INSERT INTO moz_keywords (keyword, place_id, post_data)
+               VALUES (:keyword, (SELECT id FROM moz_places WHERE url_hash = hash(:url) AND url = :url), :post_data)
+              `, { url: url.href, keyword, post_data: postData });
+          });
         }
 
         await PlacesSyncUtils.bookmarks.addSyncChangesForBookmarksWithURL(
           db, url, PlacesSyncUtils.bookmarks.determineSyncChangeDelta(source));
 
         cache.set(keyword, { keyword, url, postData });
 
         // In any case, notify about the new keyword.

--- a/toolkit/components/places/nsNavHistory.cpp
+++ b/toolkit/components/places/nsNavHistory.cpp
@@ -406,53 +406,64 @@ nsNavHistory::GetOrCreateIdForPage(nsIUR
 {
   nsresult rv = GetIdForPage(aURI, _pageId, _GUID);
   NS_ENSURE_SUCCESS(rv, rv);
 
   if (*_pageId != 0) {
     return NS_OK;
   }
 
-  // Create a new hidden, untyped and unvisited entry.
-  nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
-    "INSERT INTO moz_places (url, url_hash, rev_host, hidden, frecency, guid) "
-    "VALUES (:page_url, hash(:page_url), :rev_host, :hidden, :frecency, :guid) "
-  );
-  NS_ENSURE_STATE(stmt);
-  mozStorageStatementScoper scoper(stmt);
-
-  rv = URIBinder::Bind(stmt, NS_LITERAL_CSTRING("page_url"), aURI);
-  NS_ENSURE_SUCCESS(rv, rv);
-  // host (reversed with trailing period)
-  nsAutoString revHost;
-  rv = GetReversedHostname(aURI, revHost);
-  // Not all URI types have hostnames, so this is optional.
-  if (NS_SUCCEEDED(rv)) {
-    rv = stmt->BindStringByName(NS_LITERAL_CSTRING("rev_host"), revHost);
-  } else {
-    rv = stmt->BindNullByName(NS_LITERAL_CSTRING("rev_host"));
+  {
+    // Create a new hidden, untyped and unvisited entry.
+    nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
+      "INSERT INTO moz_places (url, url_hash, rev_host, hidden, frecency, guid) "
+      "VALUES (:page_url, hash(:page_url), :rev_host, :hidden, :frecency, :guid) "
+    );
+    NS_ENSURE_STATE(stmt);
+    mozStorageStatementScoper scoper(stmt);
+
+    rv = URIBinder::Bind(stmt, NS_LITERAL_CSTRING("page_url"), aURI);
+    NS_ENSURE_SUCCESS(rv, rv);
+    // host (reversed with trailing period)
+    nsAutoString revHost;
+    rv = GetReversedHostname(aURI, revHost);
+    // Not all URI types have hostnames, so this is optional.
+    if (NS_SUCCEEDED(rv)) {
+      rv = stmt->BindStringByName(NS_LITERAL_CSTRING("rev_host"), revHost);
+    } else {
+      rv = stmt->BindNullByName(NS_LITERAL_CSTRING("rev_host"));
+    }
+    NS_ENSURE_SUCCESS(rv, rv);
+    rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("hidden"), 1);
+    NS_ENSURE_SUCCESS(rv, rv);
+    nsAutoCString spec;
+    rv = aURI->GetSpec(spec);
+    NS_ENSURE_SUCCESS(rv, rv);
+    rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("frecency"),
+                               IsQueryURI(spec) ? 0 : -1);
+    NS_ENSURE_SUCCESS(rv, rv);
+    rv = GenerateGUID(_GUID);
+    NS_ENSURE_SUCCESS(rv, rv);
+    rv = stmt->BindUTF8StringByName(NS_LITERAL_CSTRING("guid"), _GUID);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    rv = stmt->Execute();
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    *_pageId = sLastInsertedPlaceId;
   }
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("hidden"), 1);
-  NS_ENSURE_SUCCESS(rv, rv);
-  nsAutoCString spec;
-  rv = aURI->GetSpec(spec);
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("frecency"),
-                             IsQueryURI(spec) ? 0 : -1);
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = GenerateGUID(_GUID);
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = stmt->BindUTF8StringByName(NS_LITERAL_CSTRING("guid"), _GUID);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = stmt->Execute();
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  *_pageId = sLastInsertedPlaceId;
+
+  {
+    // Trigger the updates to moz_hosts
+    nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
+      "DELETE FROM moz_updatehostsinsert_temp"
+    );
+    NS_ENSURE_STATE(stmt);
+    mozStorageStatementScoper scoper(stmt);
+  }
 
   return NS_OK;
 }
 
 
 void
 nsNavHistory::LoadPrefs()
 {
@@ -2513,17 +2524,17 @@ nsNavHistory::CleanupPlacesOnVisitsDelet
     "DELETE FROM moz_icons "
     "WHERE root = 0 AND id NOT IN (SELECT icon_id FROM moz_icons_to_pages) "
   ));
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Hosts accumulated during the places delete are updated through a trigger
   // (see nsPlacesTriggers.h).
   rv = conn->ExecuteSimpleSQL(
-    NS_LITERAL_CSTRING("DELETE FROM moz_updatehosts_temp")
+    NS_LITERAL_CSTRING("DELETE FROM moz_updatehostsdelete_temp")
   );
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Invalidate frecencies of touched places, since they need recalculation.
   rv = invalidateFrecencies(aPlaceIdsQueryString);
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Finally notify about the removed URIs.

--- a/toolkit/components/places/nsPlacesExpiration.js
+++ b/toolkit/components/places/nsPlacesExpiration.js
@@ -230,17 +230,17 @@ const EXPIRATION_QUERIES = {
           ) AND foreign_count = 0 AND last_visit_date ISNULL`,
     actions: ACTION.TIMED | ACTION.TIMED_OVERLIMIT | ACTION.SHUTDOWN_DIRTY |
              ACTION.IDLE_DIRTY | ACTION.IDLE_DAILY | ACTION.DEBUG
   },
 
   // Hosts accumulated during the places delete are updated through a trigger
   // (see nsPlacesTriggers.h).
   QUERY_UPDATE_HOSTS: {
-    sql: `DELETE FROM moz_updatehosts_temp`,
+    sql: `DELETE FROM moz_updatehostsdelete_temp`,
     actions: ACTION.TIMED | ACTION.TIMED_OVERLIMIT | ACTION.SHUTDOWN_DIRTY |
              ACTION.IDLE_DIRTY | ACTION.IDLE_DAILY | ACTION.DEBUG
   },
 
   // Expire orphan pages from the icons database.
   QUERY_EXPIRE_FAVICONS_PAGES: {
     sql: `DELETE FROM moz_pages_w_icons
           WHERE page_url_hash NOT IN (

--- a/toolkit/components/places/nsPlacesTables.h
+++ b/toolkit/components/places/nsPlacesTables.h
@@ -154,21 +154,29 @@
     ", userContextId INTEGER" \
     ", open_count INTEGER" \
     ", PRIMARY KEY (url, userContextId)" \
   ")" \
 )
 
 // This table is used, along with moz_places_afterdelete_trigger, to update
 // hosts after places removals. During a DELETE FROM moz_places, hosts are
-// accumulated into this table, then a DELETE FROM moz_updatehosts_temp will
-// take care of updating the moz_hosts table for every modified host.
-// See CREATE_PLACES_AFTERDELETE_TRIGGER in nsPlacestriggers.h for details.
-#define CREATE_UPDATEHOSTS_TEMP NS_LITERAL_CSTRING( \
-  "CREATE TEMP TABLE moz_updatehosts_temp (" \
+// accumulated into this table, then a DELETE FROM moz_updatehostsdelete_temp
+// will take care of updating the moz_hosts table for every modified host. See
+// CREATE_PLACES_AFTERDELETE_TRIGGER in nsPlacestriggers.h for details.
+#define CREATE_UPDATEHOSTSDELETE_TEMP NS_LITERAL_CSTRING( \
+  "CREATE TEMP TABLE moz_updatehostsdelete_temp (" \
+    "  host TEXT PRIMARY KEY " \
+  ") WITHOUT ROWID " \
+)
+
+// This table is used in a similar way to moz_updatehostsdelete_temp, but for
+// inserts, and triggered via moz_places_afterinsert_trigger.
+#define CREATE_UPDATEHOSTSINSERT_TEMP NS_LITERAL_CSTRING( \
+  "CREATE TEMP TABLE moz_updatehostsinsert_temp (" \
     "  host TEXT PRIMARY KEY " \
   ") WITHOUT ROWID " \
 )
 
 // This table would not be strictly needed for functionality since it's just
 // mimicking moz_places, though it's great for database portability.
 // With this we don't have to take care into account a bunch of database
 // mismatch cases, where places.sqlite could be mixed up with a favicons.sqlite

--- a/toolkit/components/places/nsPlacesTriggers.h
+++ b/toolkit/components/places/nsPlacesTriggers.h
@@ -52,16 +52,20 @@
  * A predicate matching pages on rev_host, based on a given host value.
  * 'host' may be either the moz_hosts.host column or an alias representing an
  * equivalent value.
  */
 #define HOST_TO_REVHOST_PREDICATE \
   "rev_host = get_unreversed_host(host || '.') || '.' " \
   "OR rev_host = get_unreversed_host(host || '.') || '.www.'"
 
+#define OLDHOST_TO_REVHOST_PREDICATE \
+  "rev_host = get_unreversed_host(OLD.host || '.') || '.' " \
+  "OR rev_host = get_unreversed_host(OLD.host || '.') || '.www.'"
+
 /**
  * Select the best prefix for a host, based on existing pages registered for it.
  * Prefixes have a priority, from the top to the bottom, so that secure pages
  * have higher priority, and more generically "www." prefixed hosts come before
  * unprefixed ones.
  * Given a host, examine associated pages and:
  *  - if at least half the typed pages start with https://www. return https://www.
  *  - if at least half the typed pages start with https:// return https://
@@ -86,61 +90,80 @@
       "WHERE (" HOST_TO_REVHOST_PREDICATE ") AND +h.typed = 1 " \
     ") THEN 'ftp://' " \
     "WHEN ( " \
       "SELECT round(avg(substr(url,1,11) = 'http://www.')) FROM moz_places h " \
       "WHERE (" HOST_TO_REVHOST_PREDICATE ") AND +h.typed = 1 " \
     ") THEN 'www.' " \
   "END "
 
-/**
- * These triggers update the hostnames table whenever moz_places changes.
- */
+// The next few triggers are a workaround for the lack of FOR EACH STATEMENT in
+// Sqlite, until bug 871908 can be fixed properly.
+// While doing inserts or deletes into moz_places, we accumulate the affected
+// hosts into a temp table. Afterwards, we delete everything from the temp
+// table, causing the AFTER DELETE trigger to fire for it, which will then
+// update the moz_hosts table.
+// Note this way we lose atomicity, crashing between the 2 queries may break the
+// hosts table coherency. So it's better to run those DELETE queries in a single
+// transaction.
+// Regardless, this is still better than hanging the browser for several minutes
+// on a fast machine.
 #define CREATE_PLACES_AFTERINSERT_TRIGGER NS_LITERAL_CSTRING( \
   "CREATE TEMP TRIGGER moz_places_afterinsert_trigger " \
   "AFTER INSERT ON moz_places FOR EACH ROW " \
   "BEGIN " \
     "SELECT store_last_inserted_id('moz_places', NEW.id); " \
-    "INSERT OR REPLACE INTO moz_hosts (id, host, frecency, typed, prefix) " \
-    "SELECT " \
-        "(SELECT id FROM moz_hosts WHERE host = fixup_url(get_unreversed_host(NEW.rev_host))), " \
-        "fixup_url(get_unreversed_host(NEW.rev_host)), " \
-        "MAX(IFNULL((SELECT frecency FROM moz_hosts WHERE host = fixup_url(get_unreversed_host(NEW.rev_host))), -1), NEW.frecency), " \
-        "MAX(IFNULL((SELECT typed FROM moz_hosts WHERE host = fixup_url(get_unreversed_host(NEW.rev_host))), 0), NEW.typed), " \
-        "(" HOSTS_PREFIX_PRIORITY_FRAGMENT \
-         "FROM ( " \
-            "SELECT fixup_url(get_unreversed_host(NEW.rev_host)) AS host " \
-          ") AS match " \
-        ") " \
-    " WHERE LENGTH(NEW.rev_host) > 1; " \
+    "INSERT OR IGNORE INTO moz_updatehostsinsert_temp (host)" \
+    "VALUES (fixup_url(get_unreversed_host(NEW.rev_host)));" \
   "END" \
 )
 
-// This is a hack to workaround the lack of FOR EACH STATEMENT in Sqlite, until
-// bug 871908 can be fixed properly.
-// We store the modified hosts in a temp table, and after every DELETE FROM
-// moz_places, we issue a DELETE FROM moz_updatehosts_temp.  The AFTER DELETE
-// trigger will then take care of updating the moz_hosts table.
-// Note this way we lose atomicity, crashing between the 2 queries may break the
-// hosts table coherency. So it's better to run those DELETE queries in a single
-// transaction.
-// Regardless, this is still better than hanging the browser for several minutes
-// on a fast machine.
+// See CREATE_PLACES_AFTERINSERT_TRIGGER. For each delete in moz_places we
+// add the host to moz_updatehostsdelete_temp - we then delete everything
+// from moz_updatehostsdelete_temp, allowing us to run a trigger only once
+// per host.
 #define CREATE_PLACES_AFTERDELETE_TRIGGER NS_LITERAL_CSTRING( \
   "CREATE TEMP TRIGGER moz_places_afterdelete_trigger " \
   "AFTER DELETE ON moz_places FOR EACH ROW " \
   "BEGIN " \
-    "INSERT OR IGNORE INTO moz_updatehosts_temp (host)" \
+    "INSERT OR IGNORE INTO moz_updatehostsdelete_temp (host)" \
     "VALUES (fixup_url(get_unreversed_host(OLD.rev_host)));" \
   "END" \
 )
 
-#define CREATE_UPDATEHOSTS_AFTERDELETE_TRIGGER NS_LITERAL_CSTRING( \
-  "CREATE TEMP TRIGGER moz_updatehosts_afterdelete_trigger " \
-  "AFTER DELETE ON moz_updatehosts_temp FOR EACH ROW " \
+// See CREATE_PLACES_AFTERINSERT_TRIGGER. This is the trigger that we want
+// to ensure gets run for each distinct host that we insert into moz_places.
+#define CREATE_UPDATEHOSTSINSERT_AFTERDELETE_TRIGGER NS_LITERAL_CSTRING( \
+  "CREATE TEMP TRIGGER moz_updatehostsinsert_afterdelete_trigger " \
+  "AFTER DELETE ON moz_updatehostsinsert_temp FOR EACH ROW " \
+  "BEGIN " \
+    "INSERT OR REPLACE INTO moz_hosts (id, host, frecency, typed, prefix) " \
+    "SELECT " \
+        "(SELECT id FROM moz_hosts WHERE host = OLD.host), " \
+        "OLD.host, " \
+        "MAX(IFNULL((SELECT frecency FROM moz_hosts WHERE host = OLD.host), -1), " \
+          "(SELECT MAX(frecency) FROM moz_places h " \
+            "WHERE (" OLDHOST_TO_REVHOST_PREDICATE "))), " \
+        "MAX(IFNULL((SELECT typed FROM moz_hosts WHERE host = OLD.host), 0), " \
+          "(SELECT MAX(typed) FROM moz_places h " \
+            "WHERE (" OLDHOST_TO_REVHOST_PREDICATE "))), " \
+        "(" HOSTS_PREFIX_PRIORITY_FRAGMENT \
+         "FROM ( " \
+            "SELECT OLD.host AS host " \
+          ")" \
+        ") " \
+    " WHERE LENGTH(OLD.host) > 1; " \
+  "END" \
+)
+
+// See CREATE_PLACES_AFTERINSERT_TRIGGER. This is the trigger that we want
+// to ensure gets run for each distinct host that we delete from moz_places.
+#define CREATE_UPDATEHOSTSDELETE_AFTERDELETE_TRIGGER NS_LITERAL_CSTRING( \
+  "CREATE TEMP TRIGGER moz_updatehostsdelete_afterdelete_trigger " \
+  "AFTER DELETE ON moz_updatehostsdelete_temp FOR EACH ROW " \
   "BEGIN " \
     "DELETE FROM moz_hosts " \
     "WHERE host = OLD.host " \
       "AND NOT EXISTS(" \
         "SELECT 1 FROM moz_places " \
           "WHERE rev_host = get_unreversed_host(host || '.') || '.' " \
              "OR rev_host = get_unreversed_host(host || '.') || '.www.' " \
       "); " \

--- a/toolkit/components/places/tests/unit/test_preventive_maintenance.js
+++ b/toolkit/components/places/tests/unit/test_preventive_maintenance.js
@@ -43,16 +43,20 @@ function cleanDatabase() {
 function addPlace(aUrl, aFavicon, aGuid = PlacesUtils.history.makeGuid()) {
   let href = new URL(aUrl || "http://www.mozilla.org").href;
   let stmt = mDBConn.createStatement(
     "INSERT INTO moz_places (url, url_hash, guid) VALUES (:url, hash(:url), :guid)");
   stmt.params.url = href;
   stmt.params.guid = aGuid;
   stmt.execute();
   stmt.finalize();
+  stmt = mDBConn.createStatement(
+    "DELETE FROM moz_updatehostsinsert_temp");
+  stmt.execute();
+  stmt.finalize();
   let id = mDBConn.lastInsertRowID;
   if (aFavicon) {
     stmt = mDBConn.createStatement(
       "INSERT INTO moz_pages_w_icons (page_url, page_url_hash) VALUES (:url, hash(:url))");
     stmt.params.url = href;
     stmt.execute();
     stmt.finalize();
     stmt = mDBConn.createStatement(