[Thumbnails DB] Add functionality to clear unused on-demand favicons.

components/history/core/browser/thumbnail_database.cc

Index: components/history/core/browser/thumbnail_database.cc
diff --git a/components/history/core/browser/thumbnail_database.cc b/components/history/core/browser/thumbnail_database.cc
index c8b430f4f71d8dd70f0111995c5ce74297cec7d9..3f1cab0aa7ca591d09ae210356737307d19d7616 100644
--- a/components/history/core/browser/thumbnail_database.cc
+++ b/components/history/core/browser/thumbnail_database.cc
@@ -271,6 +271,22 @@ void DatabaseErrorCallback(sql::Connection* db,
     DLOG(FATAL) << db->GetErrorMessage();
 }
 
+void DeleteOrphanagedFaviconBitmaps(sql::Connection* db) {
+  sql::Statement favicons(db->GetCachedStatement(
+      SQL_FROM_HERE,
+      "DELETE FROM favicon_bitmaps WHERE NOT EXISTS (SELECT id FROM favicons "
+      "WHERE favicon_bitmaps.icon_id = favicons.id)"));
+  favicons.Run();
+}
+
+void DeleteOrphanagedMappings(sql::Connection* db) {
+  sql::Statement mappings(db->GetCachedStatement(
+      SQL_FROM_HERE,
+      "DELETE FROM icon_mapping WHERE NOT EXISTS (SELECT id FROM favicons "
+      "WHERE favicons.id = icon_mapping.icon_id)"));
+  mappings.Run();
+}
+
 }  // namespace
 
 ThumbnailDatabase::IconMappingEnumerator::IconMappingEnumerator() {
@@ -412,6 +428,49 @@ void ThumbnailDatabase::TrimMemory(bool aggressively) {
   db_.TrimMemory(aggressively);
 }
 
+void ThumbnailDatabase::ClearOldOnDemandFavicons(

[pkotwicz, 2017/06/21 19:50:18]

Can you please add the code to call this function in this CL too? It is hard to
look at the CL without the calling code.

[jkrcal, 2017/06/22 11:22:11]

Done. I've added a feature that controls the calls (deleting icons can cause
troubles if done wrongly so I believe we should roll out it experimentally).

Later, I add metrics that helps us evaluate the effects.

+    base::Time expiration_threshold) {

[pkotwicz, 2017/06/21 19:50:17]

Maybe rename |expiration_threshold| to |deletion_threshold|

[jkrcal, 2017/06/22 11:22:11]

Done.

+  // Select all bitmaps (and their page URLs) that have not been accessed for a
+  // while. Restrict to on-demand bitmaps (i.e. with last_requested != 0).
+  sql::Statement delete_candidates(db_.GetCachedStatement(
+      SQL_FROM_HERE,
+      "SELECT favicon_bitmaps.icon_id, icon_mapping.page_url FROM "
+      "favicon_bitmaps, icon_mapping WHERE favicon_bitmaps.icon_id = "
+      "icon_mapping.icon_id AND favicon_bitmaps.last_requested>0 AND "
+      "favicon_bitmaps.last_requested<?;"));

[pkotwicz, 2017/06/21 19:50:17]

- How long does this query take? I am wondering whether the query would be
faster if it was done in multiple parts.
Part #1: Get the icon ids
Part #2: For each icon id get the page URLs

- Will this query return multiple identical (icon_id, page_url) pairs (If a
favicon is mapped to multiple favicon bitmaps)?

[jkrcal, 2017/06/22 11:22:11]

Replying to both you performance commments here. I've added two variants you
propose as variations of the current code and added unit-tests to measure time
it takes (uploaded here, will remove again in the next patch set):

Problem size                  Current     DeleteOneByOne   SelectNoJoin
(on-demans icons x page URLs)

20 icons x 20 urls            0.12s       0.12s            0.12s
20 icons x 100 urls           1.78s       1.87s            1.91s
20 icons x 200 urls           6.55s       6.56s            6.60s

500 icons  x 10 urls          10.14s      10.19s           10.44s

1000 icons x 2 urls           1.81s       1.86s            1.81s
1000 icons x 10 urls          40.84s      42.60s           >50s

2000 icons x 2 urls           6.91s       6.95s            7.11s
3000 icons x 2 urls           15.28s      15.19s           15.25s

All times are measured only once. By observation, there are fluctuations by ca.
+-2%.

As another experiment, I did a realistic small scale example 50 times and give
the average time here:
20 icons x 10 urls (50 times) 0.030s      0.026s           0.034s

It seems all options are roughly comparable. SelectNoJoin is rarely better and
performs worse for many pairs in the join. I would rule it out.

I am open to both Current and DeleteOneByOne. WDYT?

[pkotwicz, 2017/06/22 20:32:22]

Let's go with DeleteOneByOne because it is the fastest

+  delete_candidates.BindInt64(0, expiration_threshold.ToInternalValue());
+
+  // Multiple page URLs may map to the same favicon. We omit the favicon from
+  // cleaning if at least one of its associated page URLs is bookmarked.
+  std::set<FaviconBitmapID> ids_of_icons_with_some_bookmarked_page;
+  std::set<FaviconBitmapID> ids_of_icons_with_no_bookmarked_page;
+  while (delete_candidates.Step()) {
+    FaviconID icon_id = delete_candidates.ColumnInt64(0);
+    if (ids_of_icons_with_some_bookmarked_page.count(icon_id))
+      continue;
+
+    GURL page_url = GURL(delete_candidates.ColumnString(1));
+    if (backend_client_ && backend_client_->IsBookmarked(page_url)) {

[pkotwicz, 2017/06/21 19:50:18]

In my opinion, ThumbnailDatabase should not know about bookmarks. HistoryBackend
and ExpireHistoryBackend know about bookmarks though.

[jkrcal, 2017/06/22 11:22:11]

How would you like to solve that? What about passing here an interface
FaviconDeletionFilter with a single function 
  bool CanDeleteFaviconForPageUrl(const GURL& page url);

The ExpirerHistoryBackend would then create this filter using the BookmarkModel?

+      ids_of_icons_with_some_bookmarked_page.insert(icon_id);
+      ids_of_icons_with_no_bookmarked_page.erase(icon_id);
+      continue;
+    }
+
+    ids_of_icons_with_no_bookmarked_page.insert(icon_id);
+  }
+
+  for (FaviconID icon_id : ids_of_icons_with_no_bookmarked_page) {
+    sql::Statement statement(db_.GetCachedStatement(
+        SQL_FROM_HERE, "DELETE FROM favicons WHERE id=?"));
+    statement.BindInt64(0, icon_id);
+    statement.Run();

[pkotwicz, 2017/06/21 19:50:18]

Is deleting any "favicon bitmaps" and "icons" for |icon_id| faster than
DeleteOrphanagedFaviconBitmaps() and DeleteOrphanagedMappings() ?

[jkrcal, 2017/06/22 11:22:11]

See above.

+  }
+
+  // The bitmaps and mappings for all deleted favicons are deleted at once.
+  DeleteOrphanagedFaviconBitmaps(&db_);
+  DeleteOrphanagedMappings(&db_);
+}
+
 bool ThumbnailDatabase::GetFaviconBitmapIDSizes(
     favicon_base::FaviconID icon_id,
     std::vector<FaviconBitmapIDSize>* bitmap_id_sizes) {