--- a/toolkit/components/places/History.jsm
+++ b/toolkit/components/places/History.jsm
@@ -769,18 +769,21 @@ var clear = async function(db) {
     // 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`);
 
     // 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 root = 0 AND id NOT IN (SELECT icon_id FROM moz_icons_to_pages)`);
+    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
+                            )`);
 
     // Expire annotations.
     await db.execute(`DELETE FROM moz_items_annos WHERE expiration = :expire_session`,
                      { expire_session: Ci.nsIAnnotationService.EXPIRE_SESSION });
     await db.execute(`DELETE FROM moz_annos WHERE id in (
                         SELECT a.id FROM moz_annos a
                         LEFT JOIN moz_places h ON a.place_id = h.id
                         WHERE h.id IS NULL
@@ -838,38 +841,44 @@ var clear = async function(db) {
  *          - hasForeign: (boolean) If `true`, the page has at least
  *              one foreign reference (i.e. a bookmark), so the page should
  *              be kept and its frecency updated.
  * @return (Promise)
  */
 var cleanupPages = async function(db, pages) {
   await invalidateFrecencies(db, pages.filter(p => p.hasForeign || p.hasVisits).map(p => p.id));
 
-  let pageIdsToRemove = pages.filter(p => !p.hasForeign && !p.hasVisits).map(p => p.id);
-  if (pageIdsToRemove.length > 0) {
-    let idsList = sqlList(pageIdsToRemove);
-    // 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`);
+  let pagesToRemove = pages.filter(p => !p.hasForeign && !p.hasVisits);
+  if (pagesToRemove.length == 0)
+    return;
+
+  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`);
 
-    // Expire orphans.
-    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 root = 0 AND id NOT IN (SELECT icon_id FROM moz_icons_to_pages)`);
-    await db.execute(`DELETE FROM moz_annos
-                      WHERE place_id IN ( ${ idsList } )`);
-    await db.execute(`DELETE FROM moz_inputhistory
-                      WHERE place_id IN ( ${ idsList } )`);
-  }
+  // 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
+                            SELECT icon_id FROM moz_icons_to_pages
+                          )`);
+
+  await db.execute(`DELETE FROM moz_annos
+                    WHERE place_id IN ( ${ idsList } )`);
+  await db.execute(`DELETE FROM moz_inputhistory
+                    WHERE place_id IN ( ${ idsList } )`);
 };
 
 /**
  * Notify observers that pages have been removed/updated.
  *
  * @param db: (Sqlite connection)
  *      The database.
  * @param pages: (Array of objects)
@@ -1077,29 +1086,30 @@ var removeVisitsByFilter = async functio
     let pages = [];
     await db.executeTransaction(async function() {
       // 2. Remove all offending visits.
       await db.execute(`DELETE FROM moz_historyvisits
                         WHERE id IN (${ sqlList(visitsToRemove) } )`);
 
       // 3. Find out which pages have been orphaned
       await db.execute(
-        `SELECT id, url, guid,
+        `SELECT id, url, url_hash, guid,
           (foreign_count != 0) AS has_foreign,
           (last_visit_date NOTNULL) as has_visits
          FROM moz_places
          WHERE id IN (${ sqlList([...pagesToInspect]) })`,
          null,
          row => {
            let page = {
              id:  row.getResultByName("id"),
              guid: row.getResultByName("guid"),
              hasForeign: row.getResultByName("has_foreign"),
              hasVisits: row.getResultByName("has_visits"),
              url: new URL(row.getResultByName("url")),
+             hash: row.getResultByName("url_hash"),
            };
            pages.push(page);
          });
 
       // 4. Clean up and notify
       await cleanupPages(db, pages);
     });
 
@@ -1156,17 +1166,17 @@ var removeByFilter = async function(db, 
         `h.rev_host = :hostName`;
       params.hostName = revHost;
     }
   }
 
   // 3. Find out what needs to be removed
   let fragmentArray = [hostFilterSQLFragment, dateFilterSQLFragment];
   let query =
-      `SELECT h.id, url, rev_host, guid, title, frecency, foreign_count
+      `SELECT h.id, url, url_hash, rev_host, guid, title, frecency, foreign_count
        FROM moz_places h WHERE
        (${ fragmentArray.filter(f => f !== "").join(") AND (") })`;
   let onResultData = onResult ? [] : null;
   let pages = [];
   let hasPagesToRemove = false;
 
   await db.executeCached(
     query,
@@ -1179,17 +1189,18 @@ var removeByFilter = async function(db, 
       let id = row.getResultByName("id");
       let guid = row.getResultByName("guid");
       let url = row.getResultByName("url");
       let page = {
         id,
         guid,
         hasForeign,
         hasVisits: false,
-        url: new URL(url)
+        url: new URL(url),
+        hash: row.getResultByName("url_hash"),
       };
       pages.push(page);
       if (onResult) {
         onResultData.push({
           guid,
           title: row.getResultByName("title"),
           frecency: row.getResultByName("frecency"),
           url: new URL(url)
@@ -1219,17 +1230,17 @@ var removeByFilter = async function(db, 
 
   return hasPagesToRemove;
 };
 
 // Inner implementation of History.remove.
 var remove = async function(db, {guids, urls}, onResult = null) {
   // 1. Find out what needs to be removed
   let query =
-    `SELECT id, url, guid, foreign_count, title, frecency
+    `SELECT id, url, url_hash, guid, foreign_count, title, frecency
      FROM moz_places
      WHERE guid IN (${ sqlList(guids) })
         OR (url_hash IN (${ urls.map(u => "hash(" + JSON.stringify(u) + ")").join(",") })
             AND url IN (${ sqlList(urls) }))
     `;
 
   let onResultData = onResult ? [] : null;
   let pages = [];
@@ -1243,16 +1254,17 @@ var remove = async function(db, {guids, 
     let guid = row.getResultByName("guid");
     let url = row.getResultByName("url");
     let page = {
       id,
       guid,
       hasForeign,
       hasVisits: false,
       url: new URL(url),
+      hash: row.getResultByName("url_hash"),
     };
     pages.push(page);
     if (onResult) {
       onResultData.push({
         guid,
         title: row.getResultByName("title"),
         frecency: row.getResultByName("frecency"),
         url: new URL(url)

--- a/toolkit/components/places/PlacesDBUtils.jsm
+++ b/toolkit/components/places/PlacesDBUtils.jsm
@@ -709,18 +709,20 @@ this.PlacesDBUtils = {
       `DELETE FROM moz_pages_w_icons WHERE page_url_hash NOT IN (
          SELECT url_hash FROM moz_places
        )`
     };
     cleanupStatements.push(deleteOrphanIconPages);
 
     let deleteOrphanIcons = {
       query:
-      `DELETE FROM moz_icons WHERE root = 0 AND id NOT IN (
-         SELECT icon_id FROM moz_icons_to_pages
+      `DELETE FROM moz_icons WHERE id IN (
+        SELECT id FROM moz_icons WHERE root = 0
+        EXCEPT
+        SELECT icon_id FROM moz_icons_to_pages
        )`
     };
     cleanupStatements.push(deleteOrphanIcons);
 
     // MOZ_HISTORYVISITS
     // F.1 remove orphan visits
     let deleteOrphanVisits = {
       query:

--- a/toolkit/components/places/nsPlacesExpiration.js
+++ b/toolkit/components/places/nsPlacesExpiration.js
@@ -247,18 +247,19 @@ const EXPIRATION_QUERIES = {
             SELECT url_hash FROM moz_places
           )`,
     actions: 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_icons
-          WHERE root = 0 AND id NOT IN (
+    sql: `DELETE FROM moz_icons WHERE id IN (
+            SELECT id FROM moz_icons WHERE root = 0
+            EXCEPT
             SELECT icon_id FROM moz_icons_to_pages
           )`,
     actions: ACTION.TIMED_OVERLIMIT | ACTION.SHUTDOWN_DIRTY |
              ACTION.IDLE_DIRTY | ACTION.IDLE_DAILY | ACTION.DEBUG
   },
 
   // Expire orphan page annotations from the database.
   QUERY_EXPIRE_ANNOS: {