--- a/toolkit/components/places/FaviconHelpers.cpp
+++ b/toolkit/components/places/FaviconHelpers.cpp
@@ -189,24 +189,25 @@ SetIconInfo(const RefPtr<Database>& aDB,
     ids.push_back(id);
   }
   if (aMustReplace && ids.empty()) {
     return NS_ERROR_NOT_AVAILABLE;
   }
 
   nsCOMPtr<mozIStorageStatement> insertStmt = aDB->GetStatement(
     "INSERT INTO moz_icons "
-      "(icon_url, fixed_icon_url_hash, width, expire_ms, data) "
-    "VALUES (:url, hash(fixup_url(:url)), :width, :expire, :data) "
+      "(icon_url, fixed_icon_url_hash, width, root, expire_ms, data) "
+    "VALUES (:url, hash(fixup_url(:url)), :width, :root, :expire, :data) "
   );
   NS_ENSURE_STATE(insertStmt);
   nsCOMPtr<mozIStorageStatement> updateStmt = aDB->GetStatement(
     "UPDATE moz_icons SET width = :width, "
                          "expire_ms = :expire, "
-                         "data = :data "
+                         "data = :data, "
+                         "root = :root "
     "WHERE id = :id "
   );
   NS_ENSURE_STATE(updateStmt);
 
   for (auto& payload : aIcon.payloads) {
     // Sanity checks.
     MOZ_ASSERT(payload.mimeType.EqualsLiteral(PNG_MIME_TYPE) ||
               payload.mimeType.EqualsLiteral(SVG_MIME_TYPE),
@@ -227,31 +228,39 @@ SetIconInfo(const RefPtr<Database>& aDB,
       rv = updateStmt->BindInt64ByName(NS_LITERAL_CSTRING("id"), id);
       NS_ENSURE_SUCCESS(rv, rv);
       rv = updateStmt->BindInt32ByName(NS_LITERAL_CSTRING("width"),
                                        payload.width);
       NS_ENSURE_SUCCESS(rv, rv);
       rv = updateStmt->BindInt64ByName(NS_LITERAL_CSTRING("expire"),
                                        aIcon.expiration / 1000);
       NS_ENSURE_SUCCESS(rv, rv);
+      rv = updateStmt->BindInt32ByName(NS_LITERAL_CSTRING("root"),
+                                       aIcon.rootIcon);
+      NS_ENSURE_SUCCESS(rv, rv);
       rv = updateStmt->BindBlobByName(NS_LITERAL_CSTRING("data"),
                                 TO_INTBUFFER(payload.data),
                                 payload.data.Length());
+      NS_ENSURE_SUCCESS(rv, rv);
       rv = updateStmt->Execute();
       NS_ENSURE_SUCCESS(rv, rv);
       // Set the new payload id.
       payload.id = id;
     } else {
       // Insert a new entry.
       mozStorageStatementScoper scoper(insertStmt);
       rv = URIBinder::Bind(insertStmt, NS_LITERAL_CSTRING("url"), aIcon.spec);
       NS_ENSURE_SUCCESS(rv, rv);
       rv = insertStmt->BindInt32ByName(NS_LITERAL_CSTRING("width"),
                                        payload.width);
       NS_ENSURE_SUCCESS(rv, rv);
+
+      rv = insertStmt->BindInt32ByName(NS_LITERAL_CSTRING("root"),
+                                       aIcon.rootIcon);
+      NS_ENSURE_SUCCESS(rv, rv);
       rv = insertStmt->BindInt64ByName(NS_LITERAL_CSTRING("expire"),
                                        aIcon.expiration / 1000);
       NS_ENSURE_SUCCESS(rv, rv);
       rv = insertStmt->BindBlobByName(NS_LITERAL_CSTRING("data"),
                                 TO_INTBUFFER(payload.data),
                                 payload.data.Length());
       NS_ENSURE_SUCCESS(rv, rv);
       rv = insertStmt->Execute();
@@ -301,17 +310,17 @@ FetchIconInfo(const RefPtr<Database>& aD
 
   if (_icon.status & ICON_STATUS_CACHED) {
     // The icon data has already been set by ReplaceFaviconData.
     return NS_OK;
   }
 
   nsCOMPtr<mozIStorageStatement> stmt = aDB->GetStatement(
     "/* do not warn (bug no: not worth having a compound index) */ "
-    "SELECT id, expire_ms, data, width "
+    "SELECT id, expire_ms, data, width, root "
     "FROM moz_icons "
     "WHERE fixed_icon_url_hash = hash(fixup_url(:url)) "
       "AND icon_url = :url "
     "ORDER BY width DESC "
   );
   NS_ENSURE_STATE(stmt);
   mozStorageStatementScoper scoper(stmt);
 
@@ -335,29 +344,33 @@ FetchIconInfo(const RefPtr<Database>& aD
       MOZ_ASSERT(NS_SUCCEEDED(rv));
       _icon.expiration = expire_ms * 1000;
     }
 
     uint8_t* data;
     uint32_t dataLen = 0;
     rv = stmt->GetBlob(2, &dataLen, &data);
     MOZ_ASSERT(NS_SUCCEEDED(rv));
+    payload.data.Adopt(TO_CHARBUFFER(data), dataLen);
 
-    payload.data.Adopt(TO_CHARBUFFER(data), dataLen);
     int32_t width;
     rv = stmt->GetInt32(3, &width);
     MOZ_ASSERT(NS_SUCCEEDED(rv));
     payload.width = width;
-
     if (payload.width == UINT16_MAX) {
       payload.mimeType.AssignLiteral(SVG_MIME_TYPE);
     } else {
       payload.mimeType.AssignLiteral(PNG_MIME_TYPE);
     }
 
+    int32_t rootIcon;
+    rv = stmt->GetInt32(4, &rootIcon);
+    MOZ_ASSERT(NS_SUCCEEDED(rv));
+    _icon.rootIcon = rootIcon;
+
     if (aPreferredWidth == 0 || _icon.payloads.Length() == 0) {
       _icon.payloads.AppendElement(payload);
     } else if (payload.width >= aPreferredWidth) {
       // Only retain the best matching payload.
       _icon.payloads.ReplaceElementAt(0, payload);
     } else {
       break;
     }
@@ -371,64 +384,54 @@ FetchIconPerSpec(const RefPtr<Database>&
                  const nsACString& aPageSpec,
                  const nsACString& aPageHost,
                  IconData& aIconData,
                  uint16_t aPreferredWidth)
 {
   MOZ_ASSERT(!aPageSpec.IsEmpty(), "Page spec must not be empty.");
   MOZ_ASSERT(!NS_IsMainThread());
 
-  enum IconType {
-    ePerfectMatch,
-    eRootMatch
-  };
-
+  // This selects both associated and root domain icons, ordered by width,
+  // where an associated icon has priority over a root domain icon.
+  // Regardless, note that while this way we are far more efficient, we lost
+  // associations with root domain icons, so it's possible we'll return one
+  // for a specific size when an associated icon for that size doesn't exist.
   nsCOMPtr<mozIStorageStatement> stmt = aDB->GetStatement(
     "/* do not warn (bug no: not worth having a compound index) */ "
-    "SELECT width, icon_url, :type_perfect_match AS type "
+    "SELECT width, icon_url, root "
     "FROM moz_icons i "
     "JOIN moz_icons_to_pages ON i.id = icon_id "
     "JOIN moz_pages_w_icons p ON p.id = page_id "
     "WHERE page_url_hash = hash(:url) AND page_url = :url "
     "UNION ALL "
-    "SELECT width, icon_url, :type_root_match AS type " // Fallback root domain icon.
+    "SELECT width, icon_url, root "
     "FROM moz_icons i "
     "WHERE fixed_icon_url_hash = hash(fixup_url(:root_icon_url)) "
-    "ORDER BY type ASC, width DESC "
+    "ORDER BY width DESC, root ASC "
   );
   NS_ENSURE_STATE(stmt);
   mozStorageStatementScoper scoper(stmt);
 
-  nsresult rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("type_perfect_match"),
-                                      ePerfectMatch);
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("type_root_match"), eRootMatch);
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = URIBinder::Bind(stmt, NS_LITERAL_CSTRING("url"), aPageSpec);
+  nsresult rv = URIBinder::Bind(stmt, NS_LITERAL_CSTRING("url"), aPageSpec);
   NS_ENSURE_SUCCESS(rv, rv);
   nsAutoCString rootIconFixedUrl(aPageHost);
   if (!rootIconFixedUrl.IsEmpty()) {
     rootIconFixedUrl.AppendLiteral("/favicon.ico");
   }
   rv = stmt->BindUTF8StringByName(NS_LITERAL_CSTRING("root_icon_url"),
                                   rootIconFixedUrl);
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Return the biggest icon close to the preferred width. It may be bigger
   // or smaller if the preferred width isn't found.
   bool hasResult;
   while (NS_SUCCEEDED(stmt->ExecuteStep(&hasResult)) && hasResult) {
     int32_t width;
     rv = stmt->GetInt32(0, &width);
-    int32_t t;
-    rv = stmt->GetInt32(2, &t);
-    NS_ENSURE_SUCCESS(rv, rv);
-    IconType type = t == 0 ? ePerfectMatch : eRootMatch;
-    if (!aIconData.spec.IsEmpty() &&
-        (width < aPreferredWidth || type == eRootMatch)) {
+    if (!aIconData.spec.IsEmpty() && width < aPreferredWidth) {
       // We found the best match, or we already found a match so we don't need
       // to fallback to the root domain icon.
       break;
     }
     rv = stmt->GetUTF8String(1, aIconData.spec);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
@@ -825,80 +828,85 @@ AsyncAssociateIconToPage::Run()
   // don't know where the page comes from.  Not doing so we may end adding
   // a page that otherwise we'd explicitly ignore, like a POST or an error page.
   if (mPage.placeId == 0) {
     rv = transaction.Commit();
     NS_ENSURE_SUCCESS(rv, rv);
     return NS_OK;
   }
 
-  // The page may have associated payloads already, and those could have to be
-  // expired. For example at a certain point a page could decide to stop serving
-  // its usual 16px and 32px pngs, and use an svg instead.
-  // On the other side, we could also be in the process of adding more payloads
-  // to this page, and we should not expire the payloads we just added.
-  // For this, we use the expiration field as an indicator and remove relations
-  // based on it being elapsed. We don't remove orphan icons at this time since
-  // it would have a cost. The privacy hit is limited since history removal
-  // methods already expire orphan icons.
-  if (mPage.id != 0)  {
-    nsCOMPtr<mozIStorageStatement> stmt;
-    stmt = DB->GetStatement(
-      "DELETE FROM moz_icons_to_pages WHERE icon_id IN ( "
-        "SELECT icon_id FROM moz_icons_to_pages "
-        "JOIN moz_icons i ON icon_id = i.id "
-        "WHERE page_id = :page_id "
-          "AND expire_ms < strftime('%s','now','localtime','start of day','-7 days','utc') * 1000 "
-      ") "
-    );
-    NS_ENSURE_STATE(stmt);
-    mozStorageStatementScoper scoper(stmt);
-    rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("page_id"), mPage.id);
-    NS_ENSURE_SUCCESS(rv, rv);
-    rv = stmt->Execute();
-    NS_ENSURE_SUCCESS(rv, rv);
-  } else {
-    // We need to create the page entry.
-    // By default, we use the place id for the insertion. While we can't
-    // guarantee 1:1 mapping, in general it should do.
+  // Don't associate pages to root domain icons, since those will be returned
+  // regardless.  This saves a lot of work and database space since we don't
+  // need to store urls and relations.
+  if (!mIcon.rootIcon) {
+    // The page may have associated payloads already, and those could have to be
+    // expired. For example at a certain point a page could decide to stop serving
+    // its usual 16px and 32px pngs, and use an svg instead.
+    // On the other side, we could also be in the process of adding more payloads
+    // to this page, and we should not expire the payloads we just added.
+    // For this, we use the expiration field as an indicator and remove relations
+    // based on it being elapsed. We don't remove orphan icons at this time since
+    // it would have a cost. The privacy hit is limited since history removal
+    // methods already expire orphan icons.
+    if (mPage.id != 0)  {
+      nsCOMPtr<mozIStorageStatement> stmt;
+      stmt = DB->GetStatement(
+        "DELETE FROM moz_icons_to_pages WHERE icon_id IN ( "
+          "SELECT icon_id FROM moz_icons_to_pages "
+          "JOIN moz_icons i ON icon_id = i.id "
+          "WHERE page_id = :page_id "
+            "AND expire_ms < strftime('%s','now','localtime','start of day','-7 days','utc') * 1000 "
+        ") "
+      );
+      NS_ENSURE_STATE(stmt);
+      mozStorageStatementScoper scoper(stmt);
+      rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("page_id"), mPage.id);
+      NS_ENSURE_SUCCESS(rv, rv);
+      rv = stmt->Execute();
+      NS_ENSURE_SUCCESS(rv, rv);
+    } else {
+      // We need to create the page entry.
+      // By default, we use the place id for the insertion. While we can't
+      // guarantee 1:1 mapping, in general it should do.
+      nsCOMPtr<mozIStorageStatement> stmt;
+      stmt = DB->GetStatement(
+        "INSERT OR IGNORE INTO moz_pages_w_icons (page_url, page_url_hash) "
+        "VALUES (:page_url, hash(:page_url)) "
+      );
+      NS_ENSURE_STATE(stmt);
+      mozStorageStatementScoper scoper(stmt);
+      rv = URIBinder::Bind(stmt, NS_LITERAL_CSTRING("page_url"), mPage.spec);
+      NS_ENSURE_SUCCESS(rv, rv);
+      rv = stmt->Execute();
+      NS_ENSURE_SUCCESS(rv, rv);
+    }
+
+    // Then we can create the relations.
     nsCOMPtr<mozIStorageStatement> stmt;
     stmt = DB->GetStatement(
-      "INSERT OR IGNORE INTO moz_pages_w_icons (page_url, page_url_hash) "
-      "VALUES (:page_url, hash(:page_url)) "
+      "INSERT OR IGNORE INTO moz_icons_to_pages (page_id, icon_id) "
+      "VALUES ((SELECT id from moz_pages_w_icons WHERE page_url_hash = hash(:page_url) AND page_url = :page_url), "
+              ":icon_id) "
     );
     NS_ENSURE_STATE(stmt);
-    mozStorageStatementScoper scoper(stmt);
-    rv = URIBinder::Bind(stmt, NS_LITERAL_CSTRING("page_url"), mPage.spec);
-    NS_ENSURE_SUCCESS(rv, rv);
-    rv = stmt->Execute();
-    NS_ENSURE_SUCCESS(rv, rv);
-  }
 
-  // Then we can create the relations.
-  nsCOMPtr<mozIStorageStatement> stmt;
-  stmt = DB->GetStatement(
-    "INSERT OR IGNORE INTO moz_icons_to_pages (page_id, icon_id) "
-    "VALUES ((SELECT id from moz_pages_w_icons WHERE page_url_hash = hash(:page_url) AND page_url = :page_url), "
-            ":icon_id) "
-  );
-  NS_ENSURE_STATE(stmt);
-
-  // For some reason using BindingParamsArray here fails execution, so we must
-  // execute the statements one by one.
-  // In the future we may want to investigate the reasons, sounds like related
-  // to contraints.
-  for (const auto& payload : mIcon.payloads) {
-    mozStorageStatementScoper scoper(stmt);
-    nsCOMPtr<mozIStorageBindingParams> params;
-    rv = URIBinder::Bind(stmt, NS_LITERAL_CSTRING("page_url"), mPage.spec);
-    NS_ENSURE_SUCCESS(rv, rv);
-    rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("icon_id"), payload.id);
-    NS_ENSURE_SUCCESS(rv, rv);
-    rv = stmt->Execute();
-    NS_ENSURE_SUCCESS(rv, rv);
+    // For some reason using BindingParamsArray here fails execution, so we must
+    // execute the statements one by one.
+    // In the future we may want to investigate the reasons, sounds like related
+    // to contraints.
+    for (const auto& payload : mIcon.payloads) {
+      mozStorageStatementScoper scoper(stmt);
+      nsCOMPtr<mozIStorageBindingParams> params;
+      rv = URIBinder::Bind(stmt, NS_LITERAL_CSTRING("page_url"), mPage.spec);
+      NS_ENSURE_SUCCESS(rv, rv);
+      rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("icon_id"), payload.id);
+      NS_ENSURE_SUCCESS(rv, rv);
+      rv = stmt->Execute();
+      NS_ENSURE_SUCCESS(rv, rv);
+    }
   }
 
   mIcon.status |= ICON_STATUS_ASSOCIATED;
 
   rv = transaction.Commit();
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Finally, dispatch an event to the main thread to notify observers.
@@ -1226,17 +1234,17 @@ FetchAndConvertUnsupportedPayloads::Conv
   // TODO (bug 1346139): this should probably be unified with the function that
   // will handle additions optimization off the main thread.
   MOZ_ASSERT(!NS_IsMainThread());
   *aWidth = 0;
 
   // Exclude invalid mime types.
   if (aPayload.Length() == 0 ||
       !imgLoader::SupportImageWithMimeType(PromiseFlatCString(aMimeType).get(),
-                                           AcceptedMimeTypes::IMAGES)) {
+                                           AcceptedMimeTypes::IMAGES_AND_DOCUMENTS)) {
     return NS_ERROR_FAILURE;
   }
 
   // If it's an SVG, there's nothing to optimize or convert.
   if (aMimeType.EqualsLiteral(SVG_MIME_TYPE)) {
     *aWidth = UINT16_MAX;
     return NS_OK;
   }

--- a/toolkit/components/places/FaviconHelpers.h
+++ b/toolkit/components/places/FaviconHelpers.h
@@ -82,23 +82,25 @@ struct IconPayload
  * Represents an icon entry.
  */
 struct IconData
 {
   IconData()
   : expiration(0)
   , fetchMode(FETCH_NEVER)
   , status(ICON_STATUS_UNKNOWN)
+  , rootIcon(0)
   {
   }
 
   nsCString spec;
   PRTime expiration;
   enum AsyncFaviconFetchMode fetchMode;
   uint16_t status; // This is a bitset, see ICON_STATUS_* defines above.
+  uint8_t rootIcon;
   nsTArray<IconPayload> payloads;
 };
 
 /**
  * Data cache for a page entry.
  */
 struct PageData
 {

--- a/toolkit/components/places/History.jsm
+++ b/toolkit/components/places/History.jsm
@@ -700,17 +700,17 @@ var cleanupPages = Task.async(function*(
     // Hosts accumulated during the places delete are updated through a trigger
     // (see nsPlacesTriggers.h).
     yield db.executeCached(`DELETE FROM moz_updatehosts_temp`);
 
     // Expire orphans.
     yield db.executeCached(`DELETE FROM moz_pages_w_icons
                             WHERE page_url_hash NOT IN (SELECT url_hash FROM moz_places)`);
     yield db.executeCached(`DELETE FROM moz_icons
-                            WHERE id NOT IN (SELECT icon_id FROM moz_icons_to_pages)`);
+                            WHERE root = 0 AND id NOT IN (SELECT icon_id FROM moz_icons_to_pages)`);
     yield db.execute(`DELETE FROM moz_annos
                       WHERE place_id IN ( ${ idsList } )`);
     yield db.execute(`DELETE FROM moz_inputhistory
                       WHERE place_id IN ( ${ idsList } )`);
   }
 });
 
 /**

--- a/toolkit/components/places/PlacesDBUtils.jsm
+++ b/toolkit/components/places/PlacesDBUtils.jsm
@@ -597,17 +597,17 @@ this.PlacesDBUtils = {
     // E.1 remove orphan icon entries.
     let deleteOrphanIconPages = DBConn.createAsyncStatement(
       `DELETE FROM moz_pages_w_icons WHERE page_url_hash NOT IN (
          SELECT url_hash FROM moz_places
        )`);
     cleanupStatements.push(deleteOrphanIconPages);
 
     let deleteOrphanIcons = DBConn.createAsyncStatement(
-      `DELETE FROM moz_icons WHERE id NOT IN (
+      `DELETE FROM moz_icons WHERE root = 0 AND id NOT IN (
          SELECT icon_id FROM moz_icons_to_pages
        )`);
     cleanupStatements.push(deleteOrphanIcons);
 
     // MOZ_HISTORYVISITS
     // F.1 remove orphan visits
     let deleteOrphanVisits = DBConn.createAsyncStatement(
       `DELETE FROM moz_historyvisits WHERE id IN (

--- a/toolkit/components/places/nsFaviconService.cpp
+++ b/toolkit/components/places/nsFaviconService.cpp
@@ -333,16 +333,21 @@ nsFaviconService::SetAndFetchFaviconForP
   UnassociatedIconHashKey* iconKey = mUnassociatedIcons.GetEntry(aFaviconURI);
   if (iconKey) {
     icon = iconKey->iconData;
     mUnassociatedIcons.RemoveEntry(iconKey);
   } else {
     icon.fetchMode = aForceReload ? FETCH_ALWAYS : FETCH_IF_MISSING;
     rv = aFaviconURI->GetSpec(icon.spec);
     NS_ENSURE_SUCCESS(rv, rv);
+    nsAutoCString path;
+    rv = aFaviconURI->GetPath(path);
+    if (NS_SUCCEEDED(rv) && path.EqualsLiteral("/favicon.ico")) {
+      icon.rootIcon = 1;
+    }
   }
 
   // If the page url points to an image, the icon's url will be the same.
   // TODO (Bug 403651): store a resample of the image.  For now avoid that
   // for database size and UX concerns.
   // Don't store favicons for error pages too.
   if (icon.spec.Equals(page.spec) ||
       icon.spec.Equals(FAVICON_ERRORPAGE_URL)) {
@@ -373,17 +378,17 @@ nsFaviconService::ReplaceFaviconData(nsI
                                     PRTime aExpiration)
 {
   MOZ_ASSERT(NS_IsMainThread());
   NS_ENSURE_ARG(aFaviconURI);
   NS_ENSURE_ARG(aData);
   NS_ENSURE_ARG(aDataLen > 0);
   NS_ENSURE_ARG(aMimeType.Length() > 0);
   NS_ENSURE_ARG(imgLoader::SupportImageWithMimeType(PromiseFlatCString(aMimeType).get(),
-                                                     AcceptedMimeTypes::IMAGES));
+                                                     AcceptedMimeTypes::IMAGES_AND_DOCUMENTS));
 
   if (aExpiration == 0) {
     aExpiration = PR_Now() + MAX_FAVICON_EXPIRATION;
   }
 
   UnassociatedIconHashKey* iconKey = mUnassociatedIcons.PutEntry(aFaviconURI);
   if (!iconKey) {
     return NS_ERROR_OUT_OF_MEMORY;
@@ -401,20 +406,28 @@ nsFaviconService::ReplaceFaviconData(nsI
   }
 
   IconData* iconData = &(iconKey->iconData);
   iconData->expiration = aExpiration;
   iconData->status = ICON_STATUS_CACHED;
   iconData->fetchMode = FETCH_NEVER;
   nsresult rv = aFaviconURI->GetSpec(iconData->spec);
   NS_ENSURE_SUCCESS(rv, rv);
+  nsAutoCString path;
+  rv = aFaviconURI->GetPath(path);
+  if (NS_SUCCEEDED(rv) && path.EqualsLiteral("/favicon.ico")) {
+    iconData->rootIcon = 1;
+  }
 
   IconPayload payload;
   payload.mimeType = aMimeType;
   payload.data.Assign(TO_CHARBUFFER(aData), aDataLen);
+  if (payload.mimeType.EqualsLiteral(SVG_MIME_TYPE)) {
+    payload.width = UINT16_MAX;
+  }
   // There may already be a previous payload, so ensure to only have one.
   iconData->payloads.Clear();
   iconData->payloads.AppendElement(payload);
 
   rv = OptimizeIconSizes(*iconData);
   NS_ENSURE_SUCCESS(rv, rv);
 
   // If there's not valid payload, don't store the icon into to the database.

--- a/toolkit/components/places/nsNavHistory.cpp
+++ b/toolkit/components/places/nsNavHistory.cpp
@@ -2491,16 +2491,28 @@ nsNavHistory::CleanupPlacesOnVisitsDelet
     NS_LITERAL_CSTRING(
       "DELETE FROM moz_places WHERE id IN ( "
         ) + filteredPlaceIds + NS_LITERAL_CSTRING(
       ") "
     )
   );
   NS_ENSURE_SUCCESS(rv, rv);
 
+  // Expire orphan icons.
+  rv = mDB->MainConn()->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+    "DELETE FROM moz_pages_w_icons "
+    "WHERE page_url_hash NOT IN (SELECT url_hash FROM moz_places) "
+  ));
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = mDB->MainConn()->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+    "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 = 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.

--- a/toolkit/components/places/nsPlacesExpiration.js
+++ b/toolkit/components/places/nsPlacesExpiration.js
@@ -278,17 +278,17 @@ const EXPIRATION_QUERIES = {
     actions: ACTION.TIMED_OVERLIMIT | ACTION.CLEAR_HISTORY |
              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 id NOT IN (
+          WHERE root = 0 AND id NOT IN (
             SELECT icon_id FROM moz_icons_to_pages
           )`,
     actions: ACTION.TIMED_OVERLIMIT | ACTION.CLEAR_HISTORY |
              ACTION.SHUTDOWN_DIRTY | ACTION.IDLE_DIRTY | ACTION.IDLE_DAILY |
              ACTION.DEBUG
   },
 
   // Expire orphan page annotations from the database.

--- a/toolkit/components/places/nsPlacesTables.h
+++ b/toolkit/components/places/nsPlacesTables.h
@@ -186,16 +186,17 @@
 // We are considering squared icons for simplicity, so storing only one size.
 // For svg payloads, width will be set to 65535 (UINT16_MAX).
 #define CREATE_MOZ_ICONS NS_LITERAL_CSTRING( \
   "CREATE TABLE moz_icons ( " \
     "id INTEGER PRIMARY KEY, " \
     "icon_url TEXT NOT NULL, " \
     "fixed_icon_url_hash INTEGER NOT NULL, " \
     "width INTEGER NOT NULL DEFAULT 0, " \
+    "root INTEGER NOT NULL DEFAULT 0, " \
     "color INTEGER, " \
     "expire_ms INTEGER NOT NULL DEFAULT 0, " \
     "data BLOB " \
   ") " \
 )
 
 // This table maintains relations between icons and pages.
 // Each page can have multiple icons, and each icon can be used by multiple

--- a/toolkit/components/places/nsPlacesTriggers.h
+++ b/toolkit/components/places/nsPlacesTriggers.h
@@ -141,18 +141,20 @@
         "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 = OLD.host; " \
     "DELETE FROM moz_icons " \
-    "WHERE fixed_icon_url_hash = hash(OLD.host || '/favicon.ico') " \
-      "AND fixup_url(icon_url) = OLD.host || '/favicon.ico';" \
+    "WHERE fixed_icon_url_hash = hash(fixup_url(OLD.host || '/favicon.ico')) " \
+      "AND fixup_url(icon_url) = fixup_url(OLD.host || '/favicon.ico') "\
+      "AND NOT EXISTS (SELECT 1 FROM moz_hosts WHERE host = OLD.host " \
+                                                 "OR host = fixup_url(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( \

new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/favicons/test_root_icons.js
@@ -0,0 +1,85 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+/**
+ * This file tests root icons associations and expiration
+ */
+
+add_task(function* () {
+  let pageURI = NetUtil.newURI("http://www.places.test/page/");
+  yield PlacesTestUtils.addVisits(pageURI);
+  let faviconURI = NetUtil.newURI("http://www.places.test/favicon.ico");
+  PlacesUtils.favicons.replaceFaviconDataFromDataURL(
+    faviconURI, SMALLPNG_DATA_URI.spec, 0, Services.scriptSecurityManager.getSystemPrincipal());
+  yield setFaviconForPage(pageURI, faviconURI);
+
+  // Sanity checks.
+  Assert.equal(yield getFaviconUrlForPage(pageURI), faviconURI.spec);
+  Assert.equal(yield getFaviconUrlForPage("https://places.test/somethingelse/"),
+               faviconURI.spec);
+
+  // Check database entries.
+  let db = yield PlacesUtils.promiseDBConnection();
+  let rows = yield db.execute("SELECT * FROM moz_icons");
+  Assert.equal(rows.length, 1, "There should only be 1 icon entry");
+  Assert.equal(rows[0].getResultByName("root"), 1, "It should be marked as a root icon");
+  rows = yield db.execute("SELECT * FROM moz_pages_w_icons");
+  Assert.equal(rows.length, 0, "There should be no page entry");
+  rows = yield db.execute("SELECT * FROM moz_icons_to_pages");
+  Assert.equal(rows.length, 0, "There should be no relation entry");
+
+  // Add another pages to the same host. The icon should not be removed.
+  yield PlacesTestUtils.addVisits("http://places.test/page2/");
+  yield PlacesUtils.history.remove(pageURI);
+
+  // Still works since the icon has not been removed.
+  Assert.equal(yield getFaviconUrlForPage(pageURI), faviconURI.spec);
+
+  // Remove all the pages for the given domain.
+  yield PlacesUtils.history.remove("http://places.test/page2/");
+  // The icon should be removed along with the domain.
+  rows = yield db.execute("SELECT * FROM moz_icons");
+  Assert.equal(rows.length, 0, "The icon should have been removed");
+});
+
+add_task(function* test_removePagesByTimeframe() {
+  // Add a visit in the past with no directly associated icon.
+  yield PlacesTestUtils.addVisits({uri: "http://www.places.test/old/", visitDate: new Date(Date.now() - 86400000)});
+  let pageURI = NetUtil.newURI("http://www.places.test/page/");
+  yield PlacesTestUtils.addVisits(pageURI);
+  let faviconURI = NetUtil.newURI("http://www.places.test/page/favicon.ico");
+  let rootIconURI = NetUtil.newURI("http://www.places.test/favicon.ico");
+  PlacesUtils.favicons.replaceFaviconDataFromDataURL(
+    faviconURI, SMALLSVG_DATA_URI.spec, 0, Services.scriptSecurityManager.getSystemPrincipal());
+  yield setFaviconForPage(pageURI, faviconURI);
+  PlacesUtils.favicons.replaceFaviconDataFromDataURL(
+    rootIconURI, SMALLPNG_DATA_URI.spec, 0, Services.scriptSecurityManager.getSystemPrincipal());
+  yield setFaviconForPage(pageURI, rootIconURI);
+
+  // Sanity checks.
+  Assert.equal(yield getFaviconUrlForPage(pageURI),
+               faviconURI.spec, "Should get the biggest icon");
+  Assert.equal(yield getFaviconUrlForPage(pageURI, 1),
+               rootIconURI.spec, "Should get the smallest icon");
+  Assert.equal(yield getFaviconUrlForPage("http://www.places.test/old/"),
+               rootIconURI.spec, "Should get the root icon");
+
+  PlacesUtils.history.removePagesByTimeframe(
+    PlacesUtils.toPRTime(Date.now() - 20000),
+    PlacesUtils.toPRTime(new Date())
+  );
+
+  // Check database entries.
+  let db = yield PlacesUtils.promiseDBConnection();
+  let rows = yield db.execute("SELECT * FROM moz_icons");
+  Assert.equal(rows.length, 1, "There should only be 1 icon entry");
+  Assert.equal(rows[0].getResultByName("root"), 1, "It should be marked as a root icon");
+  rows = yield db.execute("SELECT * FROM moz_pages_w_icons");
+  Assert.equal(rows.length, 0, "There should be no page entry");
+  rows = yield db.execute("SELECT * FROM moz_icons_to_pages");
+  Assert.equal(rows.length, 0, "There should be no relation entry");
+
+  PlacesUtils.history.removePagesByTimeframe(0, PlacesUtils.toPRTime(new Date()));
+  rows = yield db.execute("SELECT * FROM moz_icons");
+  Assert.equal(rows.length, 0, "There should be no icon entry");
+});

--- a/toolkit/components/places/tests/favicons/xpcshell.ini
+++ b/toolkit/components/places/tests/favicons/xpcshell.ini
@@ -30,9 +30,10 @@ support-files =
 [test_getFaviconDataForPage.js]
 [test_getFaviconURLForPage.js]
 [test_moz-anno_favicon_mime_type.js]
 [test_multiple_frames.js]
 [test_page-icon_protocol.js]
 [test_query_result_favicon_changed_on_child.js]
 [test_replaceFaviconData.js]
 [test_replaceFaviconDataFromDataURL.js]
+[test_root_icons.js]
 [test_svg_favicon.js]