--- a/toolkit/components/places/Database.cpp
+++ b/toolkit/components/places/Database.cpp
@@ -459,17 +459,17 @@ Database::Init()
     rv = updateSQLiteStatistics(MainConn());
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   // Initialize here all the items that are not part of the on-disk database,
   // like views, temp triggers or temp tables.  The database should not be
   // considered corrupt if any of the following fails.
 
-  rv = InitTempTriggers();
+  rv = InitTempEntities();
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Notify we have finished database initialization.
   // Enqueue the notification, so if we init another service that requires
   // nsNavHistoryService we don't recursive try to get it.
   RefPtr<PlacesEvent> completeEvent =
     new PlacesEvent(TOPIC_PLACES_INIT_COMPLETE);
   rv = NS_DispatchToMainThread(completeEvent);
@@ -1010,28 +1010,32 @@ Database::InitFunctions()
   NS_ENSURE_SUCCESS(rv, rv);
   rv = FrecencyNotificationFunction::create(mMainConn);
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
-Database::InitTempTriggers()
+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_PLACES_AFTERINSERT_TRIGGER);
   NS_ENSURE_SUCCESS(rv, rv);
+  rv = mMainConn->ExecuteSimpleSQL(CREATE_UPDATEHOSTS_TEMP);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = mMainConn->ExecuteSimpleSQL(CREATE_UPDATEHOSTS_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);
 
   rv = mMainConn->ExecuteSimpleSQL(CREATE_BOOKMARKS_FOREIGNCOUNT_AFTERDELETE_TRIGGER);

--- a/toolkit/components/places/Database.h
+++ b/toolkit/components/places/Database.h
@@ -237,19 +237,19 @@ protected:
   nsresult CreateBookmarkRoots();
 
   /**
    * Initializes additionale SQLite functions, defined in SQLFunctions.h
    */
   nsresult InitFunctions();
 
   /**
-   * Initializes triggers defined in nsPlacesTriggers.h
+   * Initializes temp entities, like triggers, tables, views...
    */
-  nsresult InitTempTriggers();
+  nsresult InitTempEntities();
 
   /**
    * Helpers used by schema upgrades.
    */
   nsresult MigrateV13Up();
   nsresult MigrateV15Up();
   nsresult MigrateV17Up();
   nsresult MigrateV18Up();

--- a/toolkit/components/places/History.cpp
+++ b/toolkit/components/places/History.cpp
@@ -1879,26 +1879,39 @@ private:
       NS_ENSURE_STATE(stmt);
       mozStorageStatementScoper scoper(stmt);
       bool hasResult;
       MOZ_ASSERT(NS_SUCCEEDED(stmt->ExecuteStep(&hasResult)) && !hasResult,
                  "Trying to remove a non-oprhan place from the database");
     }
 #endif
 
-    nsCString query("DELETE FROM moz_places "
-                    "WHERE id IN (");
-    query.Append(placeIdsToRemove);
-    query.Append(')');
-
-    nsCOMPtr<mozIStorageStatement> stmt = mHistory->GetStatement(query);
-    NS_ENSURE_STATE(stmt);
-    mozStorageStatementScoper scoper(stmt);
-    nsresult rv = stmt->Execute();
-    NS_ENSURE_SUCCESS(rv, rv);
+    {
+      nsCString query("DELETE FROM moz_places "
+                      "WHERE id IN (");
+      query.Append(placeIdsToRemove);
+      query.Append(')');
+
+      nsCOMPtr<mozIStorageStatement> stmt = mHistory->GetStatement(query);
+      NS_ENSURE_STATE(stmt);
+      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");
+      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;
   }
 
   mozIStorageConnection* mDBConn;
   bool mHasTransitionType;
   nsCString mWhereClause;
 

--- a/toolkit/components/places/History.jsm
+++ b/toolkit/components/places/History.jsm
@@ -496,18 +496,22 @@ var clear = Task.async(function* (db) {
  * @param idList: (Array of integers)
  *      The `moz_places` identifiers for the places to remove.
  * @return (Promise)
  */
 var removePagesById = Task.async(function*(db, idList) {
   if (idList.length == 0) {
     return;
   }
+  // Note, we are already in a transaction, since callers create it.
   yield db.execute(`DELETE FROM moz_places
                     WHERE id IN ( ${ sqlList(idList) } )`);
+  // Hosts accumulated during the places delete are updated through a trigger
+  // (see nsPlacesTriggers.h).
+  yield db.execute(`DELETE FROM moz_updatehosts_temp`);
 });
 
 /**
  * Clean up pages whose history has been modified, by either
  * removing them entirely (if they are marked for removal,
  * typically because all visits have been removed and there
  * are no more foreign keys such as bookmarks) or updating
  * their frecency (otherwise).

--- a/toolkit/components/places/nsNavHistory.cpp
+++ b/toolkit/components/places/nsNavHistory.cpp
@@ -2450,16 +2450,23 @@ nsNavHistory::CleanupPlacesOnVisitsDelet
     NS_LITERAL_CSTRING(
       "DELETE FROM moz_places WHERE id IN ( "
         ) + filteredPlaceIds + NS_LITERAL_CSTRING(
       ") "
     )
   );
   NS_ENSURE_SUCCESS(rv, rv);
 
+  // Hosts accumulated during the places delete are updated through a trigger
+  // (see nsPlacesTriggers.h).
+  rv = mDB->MainConn()->ExecuteSimpleSQL(
+    NS_LITERAL_CSTRING("DELETE FROM moz_updatehosts_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.
   for (int32_t i = 0; i < URIs.Count(); ++i) {
     NOTIFY_OBSERVERS(mCanNotify, mCacheObservers, mObservers,
                      nsINavHistoryObserver,

--- a/toolkit/components/places/nsPlacesExpiration.js
+++ b/toolkit/components/places/nsPlacesExpiration.js
@@ -236,16 +236,25 @@ const EXPIRATION_QUERIES = {
             WHERE h.last_visit_date IS NULL
               AND h.foreign_count = 0
               AND v.id IS NULL
             LIMIT :limit_uris
           )`,
     actions: ACTION.CLEAR_HISTORY
   },
 
+  // Hosts accumulated during the places delete are updated through a trigger
+  // (see nsPlacesTriggers.h).
+  QUERY_UPDATE_HOSTS: {
+    sql: `DELETE FROM moz_updatehosts_temp`,
+    actions: ACTION.CLEAR_HISTORY | ACTION.TIMED | ACTION.TIMED_OVERLIMIT |
+             ACTION.SHUTDOWN_DIRTY | ACTION.IDLE_DIRTY | ACTION.IDLE_DAILY |
+             ACTION.DEBUG
+  },
+
   // Expire orphan icons from the database.
   QUERY_EXPIRE_FAVICONS: {
     sql: `DELETE FROM moz_favicons WHERE id IN (
             SELECT f.id FROM moz_favicons f
             LEFT JOIN moz_places h ON f.id = h.favicon_id
             WHERE h.favicon_id IS NULL
             LIMIT :limit_favicons
           )`,

--- a/toolkit/components/places/nsPlacesTables.h
+++ b/toolkit/components/places/nsPlacesTables.h
@@ -139,9 +139,20 @@
 //       nsPlacesAutoComplete.js.
 #define CREATE_MOZ_OPENPAGES_TEMP NS_LITERAL_CSTRING( \
   "CREATE TEMP TABLE moz_openpages_temp (" \
     "  url TEXT PRIMARY KEY" \
     ", open_count INTEGER" \
   ")" \
 )
 
+// 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 (" \
+    "  host TEXT PRIMARY KEY " \
+  ") WITHOUT ROWID " \
+)
+
 #endif // __nsPlacesTables_h__

--- a/toolkit/components/places/nsPlacesTriggers.h
+++ b/toolkit/components/places/nsPlacesTriggers.h
@@ -105,30 +105,49 @@
        "FROM ( " \
           "SELECT fixup_url(get_unreversed_host(NEW.rev_host)) AS host " \
         ") AS match " \
       ") " \
     "); " \
   "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.
 #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)" \
+    "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 " \
+  "BEGIN " \
     "DELETE FROM moz_hosts " \
-    "WHERE host = fixup_url(get_unreversed_host(OLD.rev_host)) " \
+    "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.' " \
       "); " \
     "UPDATE moz_hosts " \
     "SET prefix = (" HOSTS_PREFIX_PRIORITY_FRAGMENT ") " \
-    "WHERE host = fixup_url(get_unreversed_host(OLD.rev_host)); " \
+    "WHERE host = OLD.host; " \
   "END" \
 )
 
 // For performance reasons the host frecency is updated only when the page
 // frecency changes by a meaningful percentage.  This is because the frecency
 // decay algorithm requires to update all the frecencies at once, causing a
 // too high overhead, while leaving the ordering unchanged.
 #define CREATE_PLACES_AFTERUPDATE_FRECENCY_TRIGGER NS_LITERAL_CSTRING( \