Bug 1467627 - Calculate origin frecency as the sum of all URL frecencies instead of the max. r?mak draft
authorDrew Willcoxon <adw@mozilla.com>
Wed, 04 Jul 2018 14:01:28 -0700
changeset 814305 dd11047a0d7d5e2274799f0c2a89e9b6c6ea3c63
parent 812548 a009b5249a4b78a889fdc5ffcf55ad51715cc686
push id115148
push userbmo:adw@mozilla.com
push dateWed, 04 Jul 2018 21:07:14 +0000
reviewersmak
bugs1467627
milestone63.0a1
Bug 1467627 - Calculate origin frecency as the sum of all URL frecencies instead of the max. r?mak MozReview-Commit-ID: KZi9C7olvsj
browser/base/content/test/urlbar/browser_urlbarAutoFillTrimURLs.js
toolkit/components/places/Bookmarks.jsm
toolkit/components/places/Database.cpp
toolkit/components/places/Database.h
toolkit/components/places/History.cpp
toolkit/components/places/History.jsm
toolkit/components/places/PlacesDBUtils.jsm
toolkit/components/places/SyncedBookmarksMirror.jsm
toolkit/components/places/UnifiedComplete.js
toolkit/components/places/nsINavHistoryService.idl
toolkit/components/places/nsNavHistory.cpp
toolkit/components/places/nsNavHistory.h
toolkit/components/places/nsPlacesTables.h
toolkit/components/places/nsPlacesTriggers.h
toolkit/components/places/tests/maintenance/test_preventive_maintenance.js
toolkit/components/places/tests/migration/head_migration.js
toolkit/components/places/tests/migration/test_current_from_v47.js
toolkit/components/places/tests/unit/test_frecency_stats.js
toolkit/components/places/tests/unit/test_origins.js
toolkit/components/places/tests/unit/test_origins_parsing.js
toolkit/components/places/tests/unit/test_sql_function_origin.js
toolkit/components/places/tests/unit/xpcshell.ini
--- a/browser/base/content/test/urlbar/browser_urlbarAutoFillTrimURLs.js
+++ b/browser/base/content/test/urlbar/browser_urlbarAutoFillTrimURLs.js
@@ -9,23 +9,24 @@ add_task(async function setup() {
     Services.prefs.clearUserPref(PREF_TRIMURL);
     Services.prefs.clearUserPref(PREF_AUTOFILL);
     await PlacesUtils.history.clear();
     gURLBar.handleRevert();
   });
   Services.prefs.setBoolPref(PREF_TRIMURL, true);
   Services.prefs.setBoolPref(PREF_AUTOFILL, true);
 
+  await PlacesUtils.bookmarks.eraseEverything();
+  await PlacesUtils.history.clear();
+
   // Adding a tab would hit switch-to-tab, so it's safer to just add a visit.
   await PlacesTestUtils.addVisits([{
     uri: "http://www.autofilltrimurl.com/whatever",
-    transition: Ci.nsINavHistoryService.TRANSITION_TYPED,
   }, {
     uri: "https://www.secureautofillurl.com/whatever",
-    transition: Ci.nsINavHistoryService.TRANSITION_TYPED,
   }]);
 });
 
 async function promiseSearch(searchtext) {
   gURLBar.focus();
   gURLBar.inputField.value = searchtext.substr(0, searchtext.length - 1);
   EventUtils.sendString(searchtext.substr(-1, 1));
   await promiseSearchComplete();
--- a/toolkit/components/places/Bookmarks.jsm
+++ b/toolkit/components/places/Bookmarks.jsm
@@ -2540,16 +2540,20 @@ var updateFrecency = async function(db, 
   }
   // We just use the hashes, since updating a few additional urls won't hurt.
   await db.execute(
     `UPDATE moz_places
      SET hidden = (url_hash BETWEEN hash("place", "prefix_lo") AND hash("place", "prefix_hi")),
          frecency = ${frecencyClause}
      WHERE url_hash IN ( ${urlQuery} )
     `);
+
+  // Trigger frecency updates for all affected origins.
+  await db.executeCached(`DELETE FROM moz_updateoriginsupdate_temp`);
+
   if (collapseNotifications) {
     let observers = PlacesUtils.history.getObservers();
     notify(observers, "onManyFrecenciesChanged");
   }
 };
 
 /**
  * Removes any orphan annotation entries.
--- a/toolkit/components/places/Database.cpp
+++ b/toolkit/components/places/Database.cpp
@@ -72,17 +72,17 @@
 // * IE didn't support urls longer than 2083 chars
 // * Sitemaps protocol used to support a maximum of 2048 chars
 // * Various SEO guides suggest to not go over 2000 chars
 // * Various apps/services are known to have issues over 2000 chars
 // * RFC 2616 - HTTP/1.1 suggests being cautious about depending
 //   on URI lengths above 255 bytes
 #define PREF_HISTORY_MAXURLLEN_DEFAULT 2000
 
-#define PREF_MIGRATE_V48_FRECENCIES "places.database.migrateV48Frecencies"
+#define PREF_MIGRATE_V52_ORIGIN_FRECENCIES "places.database.migrateV52OriginFrecencies"
 
 // Maximum size for the WAL file.
 // For performance reasons this should be as large as possible, so that more
 // transactions can fit into it, and the checkpoint cost is paid less often.
 // At the same time, since we use synchronous = NORMAL, an fsync happens only
 // at checkpoint time, so we don't want the WAL to grow too much and risk to
 // lose all the contained transactions on a crash.
 #define DATABASE_MAX_WAL_BYTES 2048000
@@ -1146,17 +1146,17 @@ Database::InitSchema(bool* aDatabaseMigr
       MOZ_ALWAYS_SUCCEEDS(mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
         "VACUUM favicons"
       )));
     }
     if (mShouldConvertIconPayloads) {
       mShouldConvertIconPayloads = false;
       nsFaviconService::ConvertUnsupportedPayloads(mMainConn);
     }
-    MigrateV48Frecencies();
+    MigrateV52OriginFrecencies();
   });
 
   // We are going to update the database, so everything from now on should be in
   // a transaction for performances.
   mozStorageTransaction transaction(mMainConn, false);
 
   if (databaseInitialized) {
     // Migration How-to:
@@ -1308,16 +1308,23 @@ Database::InitSchema(bool* aDatabaseMigr
 
       if (currentSchemaVersion < 51) {
         rv = MigrateV51Up();
         NS_ENSURE_SUCCESS(rv, rv);
       }
 
       // Firefox 62 uses schema version 51.
 
+      if (currentSchemaVersion < 52) {
+        rv = MigrateV52Up();
+        NS_ENSURE_SUCCESS(rv, rv);
+      }
+
+      // Firefox 63 uses schema version 52.
+
       // Schema Upgrades must add migration code here.
       // >>> IMPORTANT! <<<
       // NEVER MIX UP SYNC AND ASYNC EXECUTION IN MIGRATORS, YOU MAY LOCK THE
       // CONNECTION AND CAUSE FURTHER STEPS TO FAIL.
       // In case, set a bool and do the async work in the ScopeExit guard just
       // before the migration steps.
     }
   }
@@ -1619,16 +1626,20 @@ Database::InitTempEntities()
   rv = mMainConn->ExecuteSimpleSQL(CREATE_PLACES_AFTERINSERT_TRIGGER);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = mMainConn->ExecuteSimpleSQL(CREATE_UPDATEORIGINSDELETE_TEMP);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = mMainConn->ExecuteSimpleSQL(CREATE_UPDATEORIGINSDELETE_AFTERDELETE_TRIGGER);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = mMainConn->ExecuteSimpleSQL(CREATE_PLACES_AFTERDELETE_TRIGGER);
   NS_ENSURE_SUCCESS(rv, rv);
+  rv = mMainConn->ExecuteSimpleSQL(CREATE_UPDATEORIGINSUPDATE_TEMP);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = mMainConn->ExecuteSimpleSQL(CREATE_UPDATEORIGINSUPDATE_AFTERDELETE_TRIGGER);
+  NS_ENSURE_SUCCESS(rv, rv);
   rv = mMainConn->ExecuteSimpleSQL(CREATE_PLACES_AFTERUPDATE_FRECENCY_TRIGGER);
   NS_ENSURE_SUCCESS(rv, rv);
 
   rv = mMainConn->ExecuteSimpleSQL(CREATE_BOOKMARKS_FOREIGNCOUNT_AFTERDELETE_TRIGGER);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = mMainConn->ExecuteSimpleSQL(CREATE_BOOKMARKS_FOREIGNCOUNT_AFTERINSERT_TRIGGER);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = mMainConn->ExecuteSimpleSQL(CREATE_BOOKMARKS_FOREIGNCOUNT_AFTERUPDATE_TRIGGER);
@@ -2369,130 +2380,35 @@ Database::MigrateV48Up() {
     "UPDATE moz_places "
     "SET origin_id = ( "
       "SELECT id FROM moz_origins "
       "WHERE prefix = get_prefix(url) AND host = get_host_and_port(url) "
     "); "
   ));
   NS_ENSURE_SUCCESS(rv, rv);
 
-  // Setting this pref will cause InitSchema to begin async migration of
-  // frecencies to moz_origins.  The reason we don't defer the other steps
-  // above, like we do this one here, is because we want to make sure that the
-  // main data in moz_origins, prefix and host, are coherent in relation to
-  // moz_places.
-  Unused << Preferences::SetBool(PREF_MIGRATE_V48_FRECENCIES, true);
-
   // From this point on, nobody should use moz_hosts again.  Empty it so that we
   // don't leak the user's history, but don't remove it yet so that the user can
   // downgrade.
   rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
     "DELETE FROM moz_hosts; "
   ));
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
-namespace {
-
-class MigrateV48FrecenciesRunnable final : public Runnable
-{
-public:
-  NS_DECL_NSIRUNNABLE
-  explicit MigrateV48FrecenciesRunnable(mozIStorageConnection* aDBConn);
-private:
-  nsCOMPtr<mozIStorageConnection> mDBConn;
-};
-
-MigrateV48FrecenciesRunnable::MigrateV48FrecenciesRunnable(mozIStorageConnection* aDBConn)
-  : Runnable("places::MigrateV48FrecenciesRunnable")
-  , mDBConn(aDBConn)
-{
-}
-
-NS_IMETHODIMP
-MigrateV48FrecenciesRunnable::Run()
-{
-  if (NS_IsMainThread()) {
-    // Migration done.  Clear the pref.
-    Unused << Preferences::ClearUser(PREF_MIGRATE_V48_FRECENCIES);
-    return NS_OK;
-  }
-
-  // We do the work in chunks, or the wal journal may grow too much.
-  nsCOMPtr<mozIStorageStatement> updateStmt;
-  nsresult rv = mDBConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
-    "UPDATE moz_origins "
-    "SET frecency = ( "
-      "SELECT MAX(frecency) "
-      "FROM moz_places "
-      "WHERE moz_places.origin_id = moz_origins.id "
-    ") "
-    "WHERE rowid IN ( "
-      "SELECT rowid "
-      "FROM moz_origins "
-      "WHERE frecency = -1 "
-      "LIMIT 400 "
-    ") "
-  ));
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  nsCOMPtr<mozIStorageStatement> selectStmt;
-  rv = mDBConn->CreateStatement(NS_LITERAL_CSTRING(
-    "SELECT id FROM moz_origins WHERE frecency = -1 "
-  ), getter_AddRefs(selectStmt));
-  NS_ENSURE_SUCCESS(rv, rv);
-  bool hasResult = false;
-  rv = selectStmt->ExecuteStep(&hasResult);
-  NS_ENSURE_SUCCESS(rv, rv);
-  if (hasResult) {
-    // There are more results to handle. Re-dispatch to the same thread for the
-    // next chunk.
-    return NS_DispatchToCurrentThread(this);
-  }
-
-  // Re-dispatch to the main-thread to flip the migration pref.
-  return NS_DispatchToMainThread(this);
-}
-
-} // namespace
-
-void
-Database::MigrateV48Frecencies()
-{
-  MOZ_ASSERT(NS_IsMainThread());
-
-  if (!Preferences::GetBool(PREF_MIGRATE_V48_FRECENCIES)) {
-    return;
-  }
-
-  RefPtr<MigrateV48FrecenciesRunnable> runnable =
-    new MigrateV48FrecenciesRunnable(mMainConn);
-  nsCOMPtr<nsIEventTarget> target = do_GetInterface(mMainConn);
-  MOZ_ASSERT(target);
-  Unused << target->Dispatch(runnable, NS_DISPATCH_NORMAL);
-}
-
 nsresult
 Database::MigrateV49Up() {
-  // Calculate initial frecency stats, which should have been done as part of
-  // the v48 migration but wasn't.
-  nsNavHistory *navHistory = nsNavHistory::GetHistoryService();
-  NS_ENSURE_STATE(navHistory);
-  nsresult rv = navHistory->RecalculateFrecencyStats(nullptr);
-  NS_ENSURE_SUCCESS(rv, rv);
-
   // These hidden preferences were added along with the v48 migration as part of
   // the frecency stats implementation but are now replaced with entries in the
   // moz_meta table.
   Unused << Preferences::ClearUser("places.frecency.stats.count");
   Unused << Preferences::ClearUser("places.frecency.stats.sum");
   Unused << Preferences::ClearUser("places.frecency.stats.sumOfSquares");
-
   return NS_OK;
 }
 
 nsresult
 Database::MigrateV50Up() {
   // Convert the existing queries. We don't have REGEX available, so the simplest
   // thing to do is to pull the urls out, and process them manually.
   nsCOMPtr<mozIStorageStatement> stmt;
@@ -2648,16 +2564,141 @@ Database::MigrateV51Up()
   rv = stmt->BindUTF8StringByName(NS_LITERAL_CSTRING("anno_name"),  LAST_USED_ANNO);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = stmt->Execute();
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
+namespace {
+
+class MigrateV52OriginFrecenciesRunnable final : public Runnable
+{
+public:
+  NS_DECL_NSIRUNNABLE
+  explicit MigrateV52OriginFrecenciesRunnable(mozIStorageConnection* aDBConn);
+private:
+  nsCOMPtr<mozIStorageConnection> mDBConn;
+};
+
+MigrateV52OriginFrecenciesRunnable::MigrateV52OriginFrecenciesRunnable(mozIStorageConnection* aDBConn)
+  : Runnable("places::MigrateV52OriginFrecenciesRunnable")
+  , mDBConn(aDBConn)
+{
+}
+
+NS_IMETHODIMP
+MigrateV52OriginFrecenciesRunnable::Run()
+{
+  if (NS_IsMainThread()) {
+    // Migration done.  Clear the pref.
+    Unused << Preferences::ClearUser(PREF_MIGRATE_V52_ORIGIN_FRECENCIES);
+
+    // Now that frecencies have been migrated, recalculate the origin frecency
+    // stats.
+    nsNavHistory *navHistory = nsNavHistory::GetHistoryService();
+    NS_ENSURE_STATE(navHistory);
+    nsresult rv = navHistory->RecalculateOriginFrecencyStats(nullptr);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    return NS_OK;
+  }
+
+  // We do the work in chunks, or the wal journal may grow too much.
+  nsresult rv = mDBConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+    "UPDATE moz_origins "
+    "SET frecency = ( "
+      "SELECT CAST(TOTAL(frecency) AS INTEGER) "
+      "FROM moz_places "
+      "WHERE frecency > 0 AND moz_places.origin_id = moz_origins.id "
+    ") "
+    "WHERE id IN ( "
+      "SELECT id "
+      "FROM moz_origins "
+      "WHERE frecency < 0 "
+      "LIMIT 400 "
+    ") "
+  ));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  nsCOMPtr<mozIStorageStatement> selectStmt;
+  rv = mDBConn->CreateStatement(NS_LITERAL_CSTRING(
+    "SELECT 1 "
+    "FROM moz_origins "
+    "WHERE frecency < 0 "
+    "LIMIT 1 "
+  ), getter_AddRefs(selectStmt));
+  NS_ENSURE_SUCCESS(rv, rv);
+  bool hasResult = false;
+  rv = selectStmt->ExecuteStep(&hasResult);
+  NS_ENSURE_SUCCESS(rv, rv);
+  if (hasResult) {
+    // There are more results to handle. Re-dispatch to the same thread for the
+    // next chunk.
+    return NS_DispatchToCurrentThread(this);
+  }
+
+  // Re-dispatch to the main-thread to flip the migration pref.
+  return NS_DispatchToMainThread(this);
+}
+
+} // namespace
+
+void
+Database::MigrateV52OriginFrecencies()
+{
+  MOZ_ASSERT(NS_IsMainThread());
+
+  if (!Preferences::GetBool(PREF_MIGRATE_V52_ORIGIN_FRECENCIES)) {
+    // The migration has already been completed.
+    return;
+  }
+
+  RefPtr<MigrateV52OriginFrecenciesRunnable> runnable(
+    new MigrateV52OriginFrecenciesRunnable(mMainConn));
+  nsCOMPtr<nsIEventTarget> target(do_GetInterface(mMainConn));
+  MOZ_ASSERT(target);
+  Unused << target->Dispatch(runnable, NS_DISPATCH_NORMAL);
+}
+
+nsresult
+Database::MigrateV52Up()
+{
+  // Before this migration, moz_origin.frecency is the max frecency of all
+  // places with the origin.  After this migration, it's the sum of frecencies
+  // of all places with the origin.
+  //
+  // Setting this pref will cause InitSchema to begin async migration, via
+  // MigrateV52OriginFrecencies.  When that migration is done, origin frecency
+  // stats are recalculated (see MigrateV52OriginFrecenciesRunnable::Run).
+  Unused << Preferences::SetBool(PREF_MIGRATE_V52_ORIGIN_FRECENCIES, true);
+
+  // Set all origin frecencies to -1 so that MigrateV52OriginFrecenciesRunnable
+  // will migrate them.
+  nsresult rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+    "UPDATE moz_origins SET frecency = -1 "
+  ));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  // This migration also renames these moz_meta keys that keep track of frecency
+  // stats.  (That happens when stats are recalculated.)  Delete the old ones.
+  rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+    "DELETE FROM moz_meta "
+    "WHERE key IN ( "
+      "'frecency_count', "
+      "'frecency_sum', "
+      "'frecency_sum_of_squares' "
+    ") "
+  ));
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return NS_OK;
+}
+
 
 nsresult
 Database::ConvertOldStyleQuery(nsCString& aURL)
 {
   AutoTArray<QueryKeyValuePair, 8> tokens;
   nsresult rv = TokenizeQueryString(aURL, &tokens);
   NS_ENSURE_SUCCESS(rv, rv);
 
--- a/toolkit/components/places/Database.h
+++ b/toolkit/components/places/Database.h
@@ -14,17 +14,17 @@
 #include "mozilla/storage/StatementCache.h"
 #include "mozilla/Attributes.h"
 #include "nsIEventTarget.h"
 #include "Shutdown.h"
 #include "nsCategoryCache.h"
 
 // This is the schema version. Update it at any schema change and add a
 // corresponding migrateVxx method below.
-#define DATABASE_SCHEMA_VERSION 51
+#define DATABASE_SCHEMA_VERSION 52
 
 // Fired after Places inited.
 #define TOPIC_PLACES_INIT_COMPLETE "places-init-complete"
 // This topic is received when the profile is about to be lost.  Places does
 // initial shutdown work and notifies TOPIC_PLACES_SHUTDOWN to all listeners.
 // Any shutdown work that requires the Places APIs should happen here.
 #define TOPIC_PROFILE_CHANGE_TEARDOWN "profile-change-teardown"
 // Fired when Places is shutting down.  Any code should stop accessing Places
@@ -333,18 +333,19 @@ protected:
   nsresult MigrateV44Up();
   nsresult MigrateV45Up();
   nsresult MigrateV46Up();
   nsresult MigrateV47Up();
   nsresult MigrateV48Up();
   nsresult MigrateV49Up();
   nsresult MigrateV50Up();
   nsresult MigrateV51Up();
+  nsresult MigrateV52Up();
 
-  void MigrateV48Frecencies();
+  void MigrateV52OriginFrecencies();
 
   nsresult UpdateBookmarkRootTitles();
 
   friend class ConnectionShutdownBlocker;
 
   int64_t CreateMobileRoot();
   nsresult ConvertOldStyleQuery(nsCString& aURL);
   nsresult GetItemsWithAnno(const nsACString& aAnnoName, int32_t aItemType,
--- a/toolkit/components/places/History.cpp
+++ b/toolkit/components/places/History.cpp
@@ -1162,25 +1162,35 @@ public:
       }
 
       // If we get here, we must have been successful adding/updating this
       // visit/place, so update the count:
       mSuccessfulUpdatedCount++;
     }
 
     {
-      // Trigger an update for all the hosts of the places we inserted
+      // Trigger insertions for all the new origins of the places we inserted.
       nsAutoCString query("DELETE FROM moz_updateoriginsinsert_temp");
       nsCOMPtr<mozIStorageStatement> stmt = mHistory->GetStatement(query);
       NS_ENSURE_STATE(stmt);
       mozStorageStatementScoper scoper(stmt);
       nsresult rv = stmt->Execute();
       NS_ENSURE_SUCCESS(rv, rv);
     }
 
+    {
+      // Trigger frecency updates for all those origins.
+      nsAutoCString query("DELETE FROM moz_updateoriginsupdate_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);
 
     // If we don't need to chunk the notifications, just notify using the
     // original mPlaces array.
     if (!shouldChunkNotifications) {
       nsCOMPtr<nsIRunnable> event = new NotifyManyVisitsObservers(mPlaces);
       rv = NS_DispatchToMainThread(event);
--- a/toolkit/components/places/History.jsm
+++ b/toolkit/components/places/History.jsm
@@ -760,16 +760,18 @@ var invalidateFrecencies = async functio
      ) WHERE id in (${ ids })`
   );
   await db.execute(
     `UPDATE moz_places
      SET hidden = 0
      WHERE id in (${ ids })
      AND frecency <> 0`
   );
+  // Trigger frecency updates for all affected origins.
+  await db.execute(`DELETE FROM moz_updateoriginsupdate_temp`);
 };
 
 // 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`);
@@ -819,16 +821,19 @@ var clear = async function(db) {
 
   // Clear the registered embed visits.
   PlacesUtils.history.clearEmbedVisits();
 
   let observers = PlacesUtils.history.getObservers();
   notify(observers, "onClearHistory");
   // Notify frecency change observers.
   notify(observers, "onManyFrecenciesChanged");
+
+  // Trigger frecency updates for all affected origins.
+  await db.execute(`DELETE FROM moz_updateoriginsupdate_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/PlacesDBUtils.jsm
+++ b/toolkit/components/places/PlacesDBUtils.jsm
@@ -35,17 +35,17 @@ var PlacesDBUtils = {
    *         - logs: an array of strings containing the messages logged by the task.
    */
   async maintenanceOnIdle() {
     let tasks = [
       this.checkIntegrity,
       this.invalidateCaches,
       this.checkCoherence,
       this._refreshUI,
-      this.frecencyStats,
+      this.originFrecencyStats,
       this.incrementalVacuum
     ];
     let telemetryStartTime = Date.now();
     let taskStatusMap = await PlacesDBUtils.runTasks(tasks);
 
     Services.prefs.setIntPref("places.database.lastMaintenance",
                                parseInt(Date.now() / 1000));
     Services.telemetry.getHistogramById("PLACES_IDLE_MAINTENANCE_TIME_MS")
@@ -67,17 +67,17 @@ var PlacesDBUtils = {
    *         - logs: an array of strings containing the messages logged by the task.
    */
   async checkAndFixDatabase() {
     let tasks = [
       this.checkIntegrity,
       this.invalidateCaches,
       this.checkCoherence,
       this.expire,
-      this.frecencyStats,
+      this.originFrecencyStats,
       this.vacuum,
       this.stats,
       this._refreshUI,
     ];
     return PlacesDBUtils.runTasks(tasks);
   },
 
   /**
@@ -859,24 +859,24 @@ var PlacesDBUtils = {
     } catch (ex) {
       throw new Error("Unable to collect stats.");
     }
 
     return logs;
   },
 
   /**
-   * Recalculates statistical data on the frecencies in the database.
+   * Recalculates statistical data on the origin frecencies in the database.
    *
    * @return {Promise} resolves when statistics are collected.
    */
-  frecencyStats() {
+  originFrecencyStats() {
     return new Promise(resolve => {
-      PlacesUtils.history.recalculateFrecencyStats(() => resolve([
-        "Recalculated frecency stats"
+      PlacesUtils.history.recalculateOriginFrecencyStats(() => resolve([
+        "Recalculated origin frecency stats"
       ]));
     });
   },
 
   /**
    * Collects telemetry data and reports it to Telemetry.
    *
    * Note: although this function isn't actually async, we keep it async to
--- a/toolkit/components/places/SyncedBookmarksMirror.jsm
+++ b/toolkit/components/places/SyncedBookmarksMirror.jsm
@@ -2106,16 +2106,19 @@ async function initializeTempMirrorEntit
     AFTER DELETE ON itemsToRemove
     BEGIN
       /* Recalculate frecencies. */
       UPDATE moz_places SET
         frecency = -1
       WHERE id = (SELECT fk FROM moz_bookmarks
                   WHERE guid = OLD.guid);
 
+      /* Trigger frecency updates for all affected origins. */
+      DELETE FROM moz_updateoriginsupdate_temp;
+
       /* Remove annos for the deleted items. */
       DELETE FROM moz_items_annos
       WHERE item_id = (SELECT id FROM moz_bookmarks
                        WHERE guid = OLD.guid);
 
       /* Don't reupload tombstones for items that are already deleted on the
          server. */
       DELETE FROM moz_bookmarks_deleted
--- a/toolkit/components/places/UnifiedComplete.js
+++ b/toolkit/components/places/UnifiedComplete.js
@@ -261,19 +261,19 @@ const QUERYINDEX_ORIGIN_FRECENCY = 3;
 // the frecency mean plus one standard deviation.  This is inlined directly in
 // the SQL (as opposed to being a custom Sqlite function for example) in order
 // to be as efficient as possible.  The MAX() is to make sure that places with
 // <= 0 frecency are never autofilled.
 const SQL_AUTOFILL_WITH = `
   WITH
   frecency_stats(count, sum, squares) AS (
     SELECT
-      CAST((SELECT IFNULL(value, 0.0) FROM moz_meta WHERE key = "frecency_count") AS REAL),
-      CAST((SELECT IFNULL(value, 0.0) FROM moz_meta WHERE key = "frecency_sum") AS REAL),
-      CAST((SELECT IFNULL(value, 0.0) FROM moz_meta WHERE key = "frecency_sum_of_squares") AS REAL)
+      CAST((SELECT IFNULL(value, 0.0) FROM moz_meta WHERE key = "origin_frecency_count") AS REAL),
+      CAST((SELECT IFNULL(value, 0.0) FROM moz_meta WHERE key = "origin_frecency_sum") AS REAL),
+      CAST((SELECT IFNULL(value, 0.0) FROM moz_meta WHERE key = "origin_frecency_sum_of_squares") AS REAL)
   ),
   autofill_frecency_threshold(value) AS (
     SELECT MAX(1,
       CASE count
       WHEN 0 THEN 0.0
       WHEN 1 THEN sum
       ELSE (sum / count) + sqrt((squares - ((sum * sum) / count)) / count)
       END
--- a/toolkit/components/places/nsINavHistoryService.idl
+++ b/toolkit/components/places/nsINavHistoryService.idl
@@ -1300,24 +1300,24 @@ interface nsINavHistoryService : nsISupp
    * @param aSpec
    *        The URI spec to hash.
    * @param aMode
    *        The hash mode: `""` (default), `"prefix_lo"`, or `"prefix_hi"`.
    */
   unsigned long long hashURL(in ACString aSpec, [optional] in ACString aMode);
 
   /**
-   * Resets and recalculates the frecency statistics that are kept in the
+   * Resets and recalculates the origin frecency statistics that are kept in the
    * moz_meta table.
    *
    * @param aCallback
    *        Called when the recalculation is complete.  The arguments passed to
    *        the observer are not defined.
    */
-  void recalculateFrecencyStats([optional] in nsIObserver aCallback);
+  void recalculateOriginFrecencyStats([optional] in nsIObserver aCallback);
 
   /**
    * The database connection used by Places.
    */
   readonly attribute mozIStorageConnection DBConnection;
 
   /**
    * Asynchronously executes the statement created from a query.
--- a/toolkit/components/places/nsNavHistory.cpp
+++ b/toolkit/components/places/nsNavHistory.cpp
@@ -585,71 +585,69 @@ nsNavHistory::DispatchFrecencyChangedNot
       const_cast<nsNavHistory*>(this),
       &nsNavHistory::NotifyFrecencyChanged,
       aSpec, aNewFrecency, aGUID, aHidden, aLastVisitDate
     )
   );
 }
 
 NS_IMETHODIMP
-nsNavHistory::RecalculateFrecencyStats(nsIObserver *aCallback)
+nsNavHistory::RecalculateOriginFrecencyStats(nsIObserver *aCallback)
 {
   RefPtr<nsNavHistory> self(this);
   nsMainThreadPtrHandle<nsIObserver> callback(
     !aCallback ? nullptr :
     new nsMainThreadPtrHolder<nsIObserver>(
-      "nsNavHistory::RecalculateFrecencyStats callback",
+      "nsNavHistory::RecalculateOriginFrecencyStats callback",
       aCallback
     )
   );
 
   nsCOMPtr<mozIStorageConnection> conn = mDB->MainConn();
   nsCOMPtr<nsIEventTarget> target = do_GetInterface(conn);
   MOZ_ASSERT(target);
   nsresult rv = target->Dispatch(NS_NewRunnableFunction(
-    "nsNavHistory::RecalculateFrecencyStats",
+    "nsNavHistory::RecalculateOriginFrecencyStats",
     [self, callback] {
-      Unused << self->RecalculateFrecencyStatsInternal();
+      Unused << self->RecalculateOriginFrecencyStatsInternal();
       Unused << NS_DispatchToMainThread(NS_NewRunnableFunction(
-        "nsNavHistory::RecalculateFrecencyStats callback",
+        "nsNavHistory::RecalculateOriginFrecencyStats callback",
         [callback] {
           if (callback) {
             Unused << callback->Observe(nullptr, "", nullptr);
           }
         }
       ));
     }
   ));
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
-nsNavHistory::RecalculateFrecencyStatsInternal()
+nsNavHistory::RecalculateOriginFrecencyStatsInternal()
 {
   nsCOMPtr<mozIStorageConnection> conn(mDB->MainConn());
   NS_ENSURE_STATE(conn);
 
   nsresult rv = conn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
-    "INSERT OR REPLACE INTO moz_meta (key, value) " \
-    "SELECT '" MOZ_META_KEY_FRECENCY_COUNT "' AS key, COUNT(*) AS value " \
-    "FROM moz_places " \
-    "WHERE id >= 0 AND frecency > 0 " \
-    "UNION "\
-    "SELECT '" MOZ_META_KEY_FRECENCY_SUM "' AS key, IFNULL(SUM(frecency), 0) AS value " \
-    "FROM moz_places " \
-    "WHERE id >= 0 AND frecency > 0 " \
-    "UNION " \
-    "SELECT '" MOZ_META_KEY_FRECENCY_SUM_OF_SQUARES "' AS key, IFNULL(SUM(frecency_squared), 0) AS value " \
-    "FROM ( " \
-      "SELECT frecency * frecency AS frecency_squared " \
-      "FROM moz_places " \
-      "WHERE id >= 0 AND frecency > 0 " \
-    "); "
+    "INSERT OR REPLACE INTO moz_meta(key, value) VALUES "
+    "( "
+      "'" MOZ_META_KEY_ORIGIN_FRECENCY_COUNT "' , "
+      "(SELECT COUNT(*) FROM moz_origins WHERE frecency > 0) "
+    "), "
+    "( "
+      "'" MOZ_META_KEY_ORIGIN_FRECENCY_SUM "', "
+      "(SELECT TOTAL(frecency) FROM moz_origins WHERE frecency > 0) "
+    "), "
+    "( "
+      "'" MOZ_META_KEY_ORIGIN_FRECENCY_SUM_OF_SQUARES "' , "
+      "(SELECT TOTAL(frecency * frecency) FROM moz_origins WHERE frecency > 0) "
+    ") "
   ));
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 Atomic<int64_t> nsNavHistory::sLastInsertedPlaceId(0);
 Atomic<int64_t> nsNavHistory::sLastInsertedVisitId(0);
@@ -877,16 +875,23 @@ nsNavHistory::invalidateFrecencies(const
     invalidFrecenciesSQLFragment
   );
   NS_ENSURE_STATE(stmt);
 
   nsCOMPtr<mozIStoragePendingStatement> ps;
   nsresult rv = stmt->ExecuteAsync(cb, getter_AddRefs(ps));
   NS_ENSURE_SUCCESS(rv, rv);
 
+  // Trigger frecency updates for affected origins.
+  nsCOMPtr<mozIStorageAsyncStatement> updateOriginFrecenciesStmt =
+    mDB->GetAsyncStatement("DELETE FROM moz_updateoriginsupdate_temp");
+  NS_ENSURE_STATE(updateOriginFrecenciesStmt);
+  rv = updateOriginFrecenciesStmt->ExecuteAsync(nullptr, getter_AddRefs(ps));
+  NS_ENSURE_SUCCESS(rv, rv);
+
   return NS_OK;
 }
 
 
 // Call this method before visiting a URL in order to help determine the
 // transition type of the visit.
 //
 // @see MarkPageAsTyped
@@ -3750,16 +3755,23 @@ nsNavHistory::UpdateFrecency(int64_t aPl
   };
   RefPtr<AsyncStatementCallbackNotifier> cb =
     new AsyncStatementCallbackNotifier(TOPIC_FRECENCY_UPDATED);
   nsCOMPtr<mozIStoragePendingStatement> ps;
   rv = conn->ExecuteAsync(stmts, ArrayLength(stmts), cb,
                                      getter_AddRefs(ps));
   NS_ENSURE_SUCCESS(rv, rv);
 
+  // Trigger frecency updates for all affected origins.
+  nsCOMPtr<mozIStorageAsyncStatement> updateOriginFrecenciesStmt =
+    mDB->GetAsyncStatement("DELETE FROM moz_updateoriginsupdate_temp");
+  NS_ENSURE_STATE(updateOriginFrecenciesStmt);
+  rv = updateOriginFrecenciesStmt->ExecuteAsync(nullptr, getter_AddRefs(ps));
+  NS_ENSURE_SUCCESS(rv, rv);
+
   return NS_OK;
 }
 
 
 namespace {
 
 class FixInvalidFrecenciesCallback : public AsyncStatementCallbackNotifier
 {
@@ -3794,16 +3806,24 @@ nsNavHistory::FixInvalidFrecencies()
   );
   NS_ENSURE_STATE(stmt);
 
   RefPtr<FixInvalidFrecenciesCallback> callback =
     new FixInvalidFrecenciesCallback();
   nsCOMPtr<mozIStoragePendingStatement> ps;
   (void)stmt->ExecuteAsync(callback, getter_AddRefs(ps));
 
+  // Trigger frecency updates for affected origins.
+  nsCOMPtr<mozIStorageAsyncStatement> updateOriginFrecenciesStmt =
+    mDB->GetAsyncStatement("DELETE FROM moz_updateoriginsupdate_temp");
+  NS_ENSURE_STATE(updateOriginFrecenciesStmt);
+  nsresult rv =
+    updateOriginFrecenciesStmt->ExecuteAsync(nullptr, getter_AddRefs(ps));
+  NS_ENSURE_SUCCESS(rv, rv);
+
   return NS_OK;
 }
 
 
 #ifdef MOZ_XUL
 
 nsresult
 nsNavHistory::AutoCompleteFeedback(int32_t aIndex,
--- a/toolkit/components/places/nsNavHistory.h
+++ b/toolkit/components/places/nsNavHistory.h
@@ -633,17 +633,17 @@ protected:
   int32_t mDefaultVisitBonus;
   int32_t mUnvisitedBookmarkBonus;
   int32_t mUnvisitedTypedBonus;
   int32_t mReloadVisitBonus;
 
   void DecayFrecencyCompleted(uint16_t reason);
   uint32_t mDecayFrecencyPendingCount;
 
-  nsresult RecalculateFrecencyStatsInternal();
+  nsresult RecalculateOriginFrecencyStatsInternal();
 
   // in nsNavHistoryQuery.cpp
   nsresult TokensToQuery(const nsTArray<mozilla::places::QueryKeyValuePair>& aTokens,
                          nsNavHistoryQuery* aQuery,
                          nsNavHistoryQueryOptions* aOptions);
 
   int64_t mTagsFolder;
 
--- a/toolkit/components/places/nsPlacesTables.h
+++ b/toolkit/components/places/nsPlacesTables.h
@@ -151,39 +151,59 @@
   "CREATE TEMP TABLE moz_openpages_temp (" \
     "  url TEXT" \
     ", 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_updateoriginsdelete_temp
-// will take care of updating the moz_origin_hosts table for every modified
-// host. See CREATE_PLACES_AFTERDELETE_TRIGGER in nsPlacestriggers.h for
-// details.
-#define CREATE_UPDATEORIGINSDELETE_TEMP NS_LITERAL_CSTRING( \
-  "CREATE TEMP TABLE moz_updateoriginsdelete_temp ( " \
-    "origin_id INTEGER PRIMARY KEY, " \
-    "host TEXT " \
-  ") " \
-)
-
-// This table is used in a similar way to moz_updateoriginsdelete_temp, but for
-// inserts, and triggered via moz_places_afterinsert_trigger.
+// This table is used, along with moz_places_afterinsert_trigger, to update
+// origins after places removals. During an INSERT into moz_places, origins are
+// accumulated in this table, then a DELETE FROM moz_updateoriginsinsert_temp
+// will take care of updating the moz_origins table for every new origin. See
+// CREATE_PLACES_AFTERINSERT_TRIGGER in nsPlacestriggers.h for details.
 #define CREATE_UPDATEORIGINSINSERT_TEMP NS_LITERAL_CSTRING( \
   "CREATE TEMP TABLE moz_updateoriginsinsert_temp ( " \
     "place_id INTEGER PRIMARY KEY, " \
     "prefix TEXT NOT NULL, " \
-    "host TEXT NOT NULL " \
+    "host TEXT NOT NULL, " \
+    "frecency INTEGER NOT NULL " \
   ") " \
 )
 
+// This table is used in a similar way to moz_updateoriginsinsert_temp, but for
+// deletes, and triggered via moz_places_afterdelete_trigger.
+//
+// When rows are added to this table, moz_places.origin_id may be null.  That's
+// why this table uses prefix + host as its primary key, not origin_id.
+#define CREATE_UPDATEORIGINSDELETE_TEMP NS_LITERAL_CSTRING( \
+  "CREATE TEMP TABLE moz_updateoriginsdelete_temp ( " \
+    "prefix TEXT NOT NULL, " \
+    "host TEXT NOT NULL, " \
+    "frecency_delta INTEGER NOT NULL, " \
+    "PRIMARY KEY (prefix, host) " \
+  ") WITHOUT ROWID " \
+)
+
+// This table is used in a similar way to moz_updateoriginsinsert_temp, but for
+// updates to places' frecencies, and triggered via
+// moz_places_afterupdate_frecency_trigger.
+//
+// When rows are added to this table, moz_places.origin_id may be null.  That's
+// why this table uses prefix + host as its primary key, not origin_id.
+#define CREATE_UPDATEORIGINSUPDATE_TEMP NS_LITERAL_CSTRING( \
+  "CREATE TEMP TABLE moz_updateoriginsupdate_temp ( " \
+    "prefix TEXT NOT NULL, " \
+    "host TEXT NOT NULL, " \
+    "frecency_delta INTEGER NOT NULL, " \
+    "PRIMARY KEY (prefix, host) " \
+  ") 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
 // created with a different places.sqlite (not just in case of a user messing
 // up with the profile, but also in case of corruption).
 #define CREATE_MOZ_PAGES_W_ICONS NS_LITERAL_CSTRING( \
   "CREATE TABLE moz_pages_w_icons ( " \
@@ -230,13 +250,13 @@
 #define CREATE_MOZ_META NS_LITERAL_CSTRING( \
   "CREATE TABLE moz_meta (" \
     "key TEXT PRIMARY KEY, " \
     "value NOT NULL" \
   ") WITHOUT ROWID " \
 )
 
 // Keys in the moz_meta table.
-#define MOZ_META_KEY_FRECENCY_COUNT "frecency_count"
-#define MOZ_META_KEY_FRECENCY_SUM "frecency_sum"
-#define MOZ_META_KEY_FRECENCY_SUM_OF_SQUARES "frecency_sum_of_squares"
+#define MOZ_META_KEY_ORIGIN_FRECENCY_COUNT "origin_frecency_count"
+#define MOZ_META_KEY_ORIGIN_FRECENCY_SUM "origin_frecency_sum"
+#define MOZ_META_KEY_ORIGIN_FRECENCY_SUM_OF_SQUARES "origin_frecency_sum_of_squares"
 
 #endif // __nsPlacesTables_h__
--- a/toolkit/components/places/nsPlacesTriggers.h
+++ b/toolkit/components/places/nsPlacesTriggers.h
@@ -43,153 +43,161 @@
       "visit_count = visit_count - (SELECT OLD.visit_type NOT IN (" EXCLUDED_VISIT_TYPES ")), "\
       "last_visit_date = (SELECT visit_date FROM moz_historyvisits " \
                          "WHERE place_id = OLD.place_id " \
                          "ORDER BY visit_date DESC LIMIT 1) " \
     "WHERE id = OLD.place_id;" \
   "END" \
 )
 
-// The next few triggers are a workaround for the lack of FOR EACH STATEMENT in
-// Sqlite, until bug 871908 can be fixed properly.
+// This macro is a helper for the next several triggers.  It updates the origin
+// frecency stats.  Use it as follows.  Before changing an origin's frecency,
+// call the macro and pass "-" (subtraction) as the argument.  That will update
+// the stats by deducting the origin's current contribution to them.  And then
+// after you change the origin's frecency, call the macro again, this time
+// passing "+" (addition) as the argument.  That will update the stats by adding
+// the origin's new contribution to them.
+#define UPDATE_ORIGIN_FRECENCY_STATS(op) \
+  "INSERT OR REPLACE INTO moz_meta(key, value) " \
+  "SELECT '" MOZ_META_KEY_ORIGIN_FRECENCY_COUNT "', " \
+         "IFNULL((SELECT value FROM moz_meta WHERE key = '" \
+                    MOZ_META_KEY_ORIGIN_FRECENCY_COUNT "'), 0) " \
+         op " CAST(frecency > 0 AS INT) " \
+  "FROM moz_origins WHERE prefix = OLD.prefix AND host = OLD.host " \
+  "UNION " \
+  "SELECT '" MOZ_META_KEY_ORIGIN_FRECENCY_SUM "', " \
+         "IFNULL((SELECT value FROM moz_meta WHERE key = '" \
+                    MOZ_META_KEY_ORIGIN_FRECENCY_SUM "'), 0) " \
+         op " MAX(frecency, 0) " \
+  "FROM moz_origins WHERE prefix = OLD.prefix AND host = OLD.host " \
+  "UNION " \
+  "SELECT '" MOZ_META_KEY_ORIGIN_FRECENCY_SUM_OF_SQUARES "', " \
+         "IFNULL((SELECT value FROM moz_meta WHERE key = '" \
+                    MOZ_META_KEY_ORIGIN_FRECENCY_SUM_OF_SQUARES "'), 0) " \
+         op " (MAX(frecency, 0) * MAX(frecency, 0)) " \
+  "FROM moz_origins WHERE prefix = OLD.prefix AND host = OLD.host "
+
+// The next several 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
 // origins 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 moz_origins.
+// update moz_origins and the origin frecency stats. As a consequence, we also
+// do this for updates to moz_places.frecency in order to make sure that changes
+// to origins are serialized.
+//
 // Note this way we lose atomicity, crashing between the 2 queries may break the
 // tables' 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.
+// transaction. Regardless, this is still better than hanging the browser for
+// several minutes on a fast machine.
+
+// This trigger runs on inserts into moz_places.
 #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 IGNORE INTO moz_updateoriginsinsert_temp (place_id, prefix, host) " \
-    "VALUES (NEW.id, get_prefix(NEW.url), get_host_and_port(NEW.url)); " \
+    "INSERT OR IGNORE INTO moz_updateoriginsinsert_temp (place_id, prefix, host, frecency) " \
+    "VALUES (NEW.id, get_prefix(NEW.url), get_host_and_port(NEW.url), NEW.frecency); " \
   "END" \
 )
-
-// This fragment updates frecency stats after a moz_places row is deleted.
-#define UPDATE_FRECENCY_STATS_AFTER_DELETE \
-  "INSERT OR REPLACE INTO moz_meta(key, value) VALUES " \
-  "( " \
-    "'" MOZ_META_KEY_FRECENCY_COUNT "', " \
-    "CAST((SELECT IFNULL(value, 0) FROM moz_meta WHERE key = '" MOZ_META_KEY_FRECENCY_COUNT "') AS INTEGER) " \
-      "- (CASE WHEN OLD.frecency <= 0 OR OLD.id < 0 THEN 0 ELSE 1 END) " \
-  "), " \
-  "( " \
-    "'" MOZ_META_KEY_FRECENCY_SUM "', " \
-    "CAST((SELECT IFNULL(value, 0) FROM moz_meta WHERE key = '" MOZ_META_KEY_FRECENCY_SUM "') AS INTEGER) " \
-      "- (CASE WHEN OLD.frecency <= 0 OR OLD.id < 0 THEN 0 ELSE OLD.frecency END) " \
-  "), " \
-  "( " \
-    "'" MOZ_META_KEY_FRECENCY_SUM_OF_SQUARES "', " \
-    "CAST((SELECT IFNULL(value, 0) FROM moz_meta WHERE key = '" MOZ_META_KEY_FRECENCY_SUM_OF_SQUARES "') AS INTEGER) " \
-      "- (CASE WHEN OLD.frecency <= 0 OR OLD.id < 0 THEN 0 ELSE OLD.frecency * OLD.frecency END) " \
-  "); "
-
-// This fragment updates frecency stats after frecency changes in a moz_places
-// row.  It's the same as UPDATE_FRECENCY_STATS_AFTER_DELETE except it accounts
-// for NEW values.
-#define UPDATE_FRECENCY_STATS_AFTER_UPDATE \
-  "INSERT OR REPLACE INTO moz_meta(key, value) VALUES " \
-  "( " \
-    "'" MOZ_META_KEY_FRECENCY_COUNT "', " \
-    "CAST(IFNULL((SELECT value FROM moz_meta WHERE key = '" MOZ_META_KEY_FRECENCY_COUNT "'), 0) AS INTEGER) " \
-      "- (CASE WHEN OLD.frecency <= 0 OR OLD.id < 0 THEN 0 ELSE 1 END) " \
-      "+ (CASE WHEN NEW.frecency <= 0 OR NEW.id < 0 THEN 0 ELSE 1 END) " \
-  "), " \
-  "( " \
-    "'" MOZ_META_KEY_FRECENCY_SUM "', " \
-    "CAST(IFNULL((SELECT value FROM moz_meta WHERE key = '" MOZ_META_KEY_FRECENCY_SUM "'), 0) AS INTEGER) " \
-      "- (CASE WHEN OLD.frecency <= 0 OR OLD.id < 0 THEN 0 ELSE OLD.frecency END) " \
-      "+ (CASE WHEN NEW.frecency <= 0 OR NEW.id < 0 THEN 0 ELSE NEW.frecency END) " \
-  "), " \
-  "( " \
-    "'" MOZ_META_KEY_FRECENCY_SUM_OF_SQUARES "', " \
-    "CAST(IFNULL((SELECT value FROM moz_meta WHERE key = '" MOZ_META_KEY_FRECENCY_SUM_OF_SQUARES "'), 0) AS INTEGER) " \
-      "- (CASE WHEN OLD.frecency <= 0 OR OLD.id < 0 THEN 0 ELSE OLD.frecency * OLD.frecency END) " \
-      "+ (CASE WHEN NEW.frecency <= 0 OR NEW.id < 0 THEN 0 ELSE NEW.frecency * NEW.frecency END) " \
-  "); "
-
-// See CREATE_PLACES_AFTERINSERT_TRIGGER. For each delete in moz_places we
-// add the origin to moz_updateoriginsdelete_temp - we then delete everything
-// from moz_updateoriginsdelete_temp, allowing us to run a trigger only once
-// per origin.
-#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_updateoriginsdelete_temp (origin_id, host) " \
-    "VALUES (OLD.origin_id, get_host_and_port(OLD.url)); " \
-    UPDATE_FRECENCY_STATS_AFTER_DELETE \
-  "END" \
-)
-
-// See CREATE_PLACES_AFTERINSERT_TRIGGER. This is the trigger that we want
-// to ensure gets run for each origin that we insert into moz_places.
+// This trigger corresponds to the previous trigger.  It runs on deletes on
+// moz_updateoriginsinsert_temp -- logically, after inserts on moz_places.
 #define CREATE_UPDATEORIGINSINSERT_AFTERDELETE_TRIGGER NS_LITERAL_CSTRING( \
   "CREATE TEMP TRIGGER moz_updateoriginsinsert_afterdelete_trigger " \
   "AFTER DELETE ON moz_updateoriginsinsert_temp FOR EACH ROW " \
   "BEGIN " \
-    "INSERT OR IGNORE INTO moz_origins (prefix, host, frecency) " \
-    "VALUES (OLD.prefix, OLD.host, 0); " \
+    /* Deduct the origin's current contribution to frecency stats */ \
+    UPDATE_ORIGIN_FRECENCY_STATS("-") "; " \
+    "INSERT INTO moz_origins (prefix, host, frecency) " \
+    "VALUES (OLD.prefix, OLD.host, MAX(OLD.frecency, 0)) " \
+    "ON CONFLICT(prefix, host) DO UPDATE " \
+    "SET frecency = frecency + OLD.frecency " \
+    "WHERE OLD.frecency > 0; " \
+    /* Add the origin's new contribution to frecency stats */ \
+    UPDATE_ORIGIN_FRECENCY_STATS("+") "; " \
     "UPDATE moz_places SET origin_id = ( " \
       "SELECT id " \
       "FROM moz_origins " \
       "WHERE prefix = OLD.prefix AND host = OLD.host " \
     ") " \
     "WHERE id = OLD.place_id; " \
-    "UPDATE moz_origins SET frecency = ( " \
-      "SELECT IFNULL(MAX(frecency), 0) " \
-      "FROM moz_places " \
-      "WHERE moz_places.origin_id = moz_origins.id " \
-    ") " \
-    "WHERE prefix = OLD.prefix AND host = OLD.host; " \
   "END" \
 )
 
-// See CREATE_PLACES_AFTERINSERT_TRIGGER. This is the trigger that we want
-// to ensure gets run for each origin that we delete from moz_places.
+// This trigger runs on deletes on moz_places.
+#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 INTO moz_updateoriginsdelete_temp (prefix, host, frecency_delta) " \
+    "VALUES (get_prefix(OLD.url), get_host_and_port(OLD.url), -MAX(OLD.frecency, 0)) " \
+    "ON CONFLICT(prefix, host) DO UPDATE " \
+    "SET frecency_delta = frecency_delta - OLD.frecency " \
+    "WHERE OLD.frecency > 0; " \
+  "END " \
+)
+// This trigger corresponds to the previous trigger.  It runs on deletes on
+// moz_updateoriginsdelete_temp -- logically, after deletes on moz_places.
 #define CREATE_UPDATEORIGINSDELETE_AFTERDELETE_TRIGGER NS_LITERAL_CSTRING( \
   "CREATE TEMP TRIGGER moz_updateoriginsdelete_afterdelete_trigger " \
   "AFTER DELETE ON moz_updateoriginsdelete_temp FOR EACH ROW " \
   "BEGIN " \
+    /* Deduct the origin's current contribution to frecency stats */ \
+    UPDATE_ORIGIN_FRECENCY_STATS("-") "; " \
+    "UPDATE moz_origins SET frecency = frecency + OLD.frecency_delta " \
+    "WHERE prefix = OLD.prefix AND host = OLD.host; " \
     "DELETE FROM moz_origins " \
-    "WHERE id = OLD.origin_id " \
-      "AND id NOT IN (SELECT origin_id FROM moz_places); " \
+    "WHERE prefix = OLD.prefix AND host = OLD.host AND NOT EXISTS ( " \
+      "SELECT id FROM moz_places " \
+      "WHERE origin_id = moz_origins.id " \
+      "LIMIT 1 " \
+    "); " \
+    /* Add the origin's new contribution to frecency stats */ \
+    UPDATE_ORIGIN_FRECENCY_STATS("+") "; " \
     "DELETE FROM moz_icons " \
     "WHERE fixed_icon_url_hash = hash(fixup_url(OLD.host || '/favicon.ico')) " \
-      "AND fixup_url(icon_url) = fixup_url(OLD.host || '/favicon.ico') "\
+      "AND fixup_url(icon_url) = fixup_url(OLD.host || '/favicon.ico') " \
       "AND NOT EXISTS (SELECT 1 FROM moz_origins WHERE host = OLD.host " \
                                                    "OR host = fixup_url(OLD.host)); " \
   "END" \
 )
 
-// This trigger keeps frecencies in the moz_origins table in sync with
-// frecencies in moz_places.  However, we skip this when frecency changes are
-// due to frecency decay since (1) decay updates all frecencies at once, so this
-// trigger would run for each moz_place, which would be expensive; and (2) decay
-// does not change the ordering of frecencies since all frecencies decay by the
-// same percentage.
+// This trigger runs on updates to moz_places.frecency.
+//
+// However, we skip this when frecency changes are due to frecency decay since
+// (1) decay updates all frecencies at once, so this trigger would run for each
+// moz_place, which would be expensive; and (2) decay does not change the
+// ordering of frecencies since all frecencies decay by the same percentage.
 #define CREATE_PLACES_AFTERUPDATE_FRECENCY_TRIGGER NS_LITERAL_CSTRING( \
   "CREATE TEMP TRIGGER moz_places_afterupdate_frecency_trigger " \
   "AFTER UPDATE OF frecency ON moz_places FOR EACH ROW " \
-  "WHEN NEW.frecency >= 0 AND NOT is_frecency_decaying() " \
+  "WHEN NOT is_frecency_decaying() " \
   "BEGIN " \
+    "INSERT INTO moz_updateoriginsupdate_temp (prefix, host, frecency_delta) " \
+    "VALUES (get_prefix(NEW.url), get_host_and_port(NEW.url), MAX(NEW.frecency, 0) - MAX(OLD.frecency, 0)) " \
+    "ON CONFLICT(prefix, host) DO UPDATE " \
+    "SET frecency_delta = frecency_delta + EXCLUDED.frecency_delta; " \
+  "END " \
+)
+// This trigger corresponds to the previous trigger.  It runs on deletes on
+// moz_updateoriginsupdate_temp -- logically, after updates to
+// moz_places.frecency.
+#define CREATE_UPDATEORIGINSUPDATE_AFTERDELETE_TRIGGER NS_LITERAL_CSTRING( \
+  "CREATE TEMP TRIGGER moz_updateoriginsupdate_afterdelete_trigger " \
+  "AFTER DELETE ON moz_updateoriginsupdate_temp FOR EACH ROW " \
+  "BEGIN " \
+    /* Deduct the origin's current contribution to frecency stats */ \
+    UPDATE_ORIGIN_FRECENCY_STATS("-") "; " \
     "UPDATE moz_origins " \
-    "SET frecency = ( " \
-      "SELECT IFNULL(MAX(frecency), 0) " \
-      "FROM moz_places " \
-      "WHERE moz_places.origin_id = moz_origins.id " \
-    ") " \
-    "WHERE id = NEW.origin_id; " \
-    UPDATE_FRECENCY_STATS_AFTER_UPDATE \
+    "SET frecency = frecency + OLD.frecency_delta " \
+    "WHERE prefix = OLD.prefix AND host = OLD.host; " \
+    /* Add the origin's new contribution to frecency stats */ \
+    UPDATE_ORIGIN_FRECENCY_STATS("+") "; " \
   "END" \
 )
 
 /**
  * This trigger removes a row from moz_openpages_temp when open_count reaches 0.
  *
  * @note this should be kept up-to-date with the definition in
  *       nsPlacesAutoComplete.js
--- a/toolkit/components/places/tests/maintenance/test_preventive_maintenance.js
+++ b/toolkit/components/places/tests/maintenance/test_preventive_maintenance.js
@@ -23,16 +23,17 @@ var mDBConn = hs.DBConnection;
 // Helpers
 
 var defaultBookmarksMaxId = 0;
 async function cleanDatabase() {
   // First clear any bookmarks the "proper way" to ensure caches like GuidHelper
   // are properly cleared.
   await PlacesUtils.bookmarks.eraseEverything();
   mDBConn.executeSimpleSQL("DELETE FROM moz_places");
+  mDBConn.executeSimpleSQL("DELETE FROM moz_origins");
   mDBConn.executeSimpleSQL("DELETE FROM moz_historyvisits");
   mDBConn.executeSimpleSQL("DELETE FROM moz_anno_attributes");
   mDBConn.executeSimpleSQL("DELETE FROM moz_annos");
   mDBConn.executeSimpleSQL("DELETE FROM moz_items_annos");
   mDBConn.executeSimpleSQL("DELETE FROM moz_inputhistory");
   mDBConn.executeSimpleSQL("DELETE FROM moz_keywords");
   mDBConn.executeSimpleSQL("DELETE FROM moz_icons");
   mDBConn.executeSimpleSQL("DELETE FROM moz_pages_w_icons");
@@ -1685,40 +1686,40 @@ tests.push({
     }
   },
 });
 
 // ------------------------------------------------------------------------------
 
 tests.push({
   name: "T.1",
-  desc: "history.recalculateFrecencyStats() is called",
+  desc: "history.recalculateOriginFrecencyStats() is called",
 
   async setup() {
     let urls = [
-      "http://example.com/1",
-      "http://example.com/2",
-      "http://example.com/3",
+      "http://example1.com/",
+      "http://example2.com/",
+      "http://example3.com/",
     ];
     await PlacesTestUtils.addVisits(urls.map(u => ({ uri: u })));
 
     this._frecencies = urls.map(u => frecencyForUrl(u));
 
     let stats = await this._promiseStats();
     Assert.equal(stats.count, this._frecencies.length, "Sanity check");
     Assert.equal(stats.sum, this._sum(this._frecencies), "Sanity check");
     Assert.equal(stats.squares, this._squares(this._frecencies), "Sanity check");
 
     await PlacesUtils.withConnectionWrapper(
       "T.1",
       db => db.execute(`
         INSERT OR REPLACE INTO moz_meta VALUES
-        ('frecency_count', 99),
-        ('frecency_sum', 99999),
-        ('frecency_sum_of_squares', 99999 * 99999);
+        ('origin_frecency_count', 99),
+        ('origin_frecency_sum', 99999),
+        ('origin_frecency_sum_of_squares', 99999 * 99999);
       `)
     );
 
     stats = await this._promiseStats();
     Assert.equal(stats.count, 99);
     Assert.equal(stats.sum, 99999);
     Assert.equal(stats.squares, 99999 * 99999);
   },
@@ -1737,19 +1738,19 @@ tests.push({
   _squares(frecs) {
     return frecs.reduce((memo, f) => memo + (f * f), 0);
   },
 
   async _promiseStats() {
     let db = await PlacesUtils.promiseDBConnection();
     let rows = await db.execute(`
       SELECT
-        IFNULL((SELECT value FROM moz_meta WHERE key = "frecency_count"), 0),
-        IFNULL((SELECT value FROM moz_meta WHERE key = "frecency_sum"), 0),
-        IFNULL((SELECT value FROM moz_meta WHERE key = "frecency_sum_of_squares"), 0)
+        IFNULL((SELECT value FROM moz_meta WHERE key = "origin_frecency_count"), 0),
+        IFNULL((SELECT value FROM moz_meta WHERE key = "origin_frecency_sum"), 0),
+        IFNULL((SELECT value FROM moz_meta WHERE key = "origin_frecency_sum_of_squares"), 0)
     `);
     return {
       count: rows[0].getResultByIndex(0),
       sum: rows[0].getResultByIndex(1),
       squares: rows[0].getResultByIndex(2),
     };
   },
 });
--- a/toolkit/components/places/tests/migration/head_migration.js
+++ b/toolkit/components/places/tests/migration/head_migration.js
@@ -10,17 +10,17 @@ ChromeUtils.import("resource://gre/modul
   /* import-globals-from ../head_common.js */
   let commonFile = do_get_file("../head_common.js", false);
   let uri = Services.io.newFileURI(commonFile);
   Services.scriptloader.loadSubScript(uri.spec, this);
 }
 
 // Put any other stuff relative to this test folder below.
 
-const CURRENT_SCHEMA_VERSION = 51;
+const CURRENT_SCHEMA_VERSION = 52;
 const FIRST_UPGRADABLE_SCHEMA_VERSION = 30;
 
 async function assertAnnotationsRemoved(db, expectedAnnos) {
   for (let anno of expectedAnnos) {
     let rows = await db.execute(`
       SELECT id FROM moz_anno_attributes
       WHERE name = :anno
     `, {anno});
--- a/toolkit/components/places/tests/migration/test_current_from_v47.js
+++ b/toolkit/components/places/tests/migration/test_current_from_v47.js
@@ -15,18 +15,18 @@ add_task(async function database_is_vali
                PlacesUtils.history.DATABASE_STATUS_UPGRADED);
 
   let db = await PlacesUtils.promiseDBConnection();
   Assert.equal((await db.getSchemaVersion()), CURRENT_SCHEMA_VERSION);
 
   // Now wait for moz_origins.frecency to be populated before continuing with
   // other test tasks.
   await TestUtils.waitForCondition(() => {
-    return !Services.prefs.getBoolPref("places.database.migrateV48Frecencies", false);
-  }, "Waiting for v48 origin frecencies to be migrated", 100, 3000);
+    return !Services.prefs.getBoolPref("places.database.migrateV52OriginFrecencies", false);
+  }, "Waiting for v52 origin frecencies to be migrated", 100, 3000);
 });
 
 
 // moz_origins should be populated.
 add_task(async function test_origins() {
   let db = await PlacesUtils.promiseDBConnection();
 
   // Collect origins.
@@ -47,74 +47,68 @@ add_task(async function test_origins() {
   rows = await db.execute(`
     SELECT get_prefix(url) AS prefix, get_host_and_port(url) AS host,
            origin_id, frecency
     FROM moz_places;
   `);
   Assert.notEqual(rows.length, 0);
 
   let seenOriginIDs = [];
-  let maxFrecencyByOriginID = {};
+  let frecenciesByOriginID = {};
 
   // Make sure moz_places.origin_id refers to the right origins.
   for (let row of rows) {
     let originID = row.getResultByName("origin_id");
     let origin = origins.find(o => o.id == originID);
     Assert.ok(origin);
     Assert.equal(origin.prefix, row.getResultByName("prefix"));
     Assert.equal(origin.host, row.getResultByName("host"));
 
     seenOriginIDs.push(originID);
 
     let frecency = row.getResultByName("frecency");
-    if (!(originID in maxFrecencyByOriginID)) {
-      maxFrecencyByOriginID[originID] = frecency;
-    } else {
-      maxFrecencyByOriginID[originID] =
-        Math.max(frecency, maxFrecencyByOriginID[originID]);
-    }
+    frecenciesByOriginID[originID] = frecenciesByOriginID[originID] || 0;
+    frecenciesByOriginID[originID] += frecency;
   }
 
   for (let origin of origins) {
     // Make sure each origin corresponds to at least one moz_place.
     Assert.ok(seenOriginIDs.includes(origin.id));
 
-    // moz_origins.frecency should be the max frecency of all moz_places with
-    // the origin.
-    Assert.equal(origin.frecency, maxFrecencyByOriginID[origin.id]);
+    // moz_origins.frecency should be the sum of frecencies of all moz_places
+    // with the origin.
+    Assert.equal(origin.frecency, frecenciesByOriginID[origin.id]);
   }
 
   // Make sure moz_hosts was emptied.
   rows = await db.execute(`
     SELECT *
     FROM moz_hosts;
   `);
   Assert.equal(rows.length, 0);
 });
 
 
 // Frecency stats should have been collected.
 add_task(async function test_frecency_stats() {
   let db = await PlacesUtils.promiseDBConnection();
 
-  // Collect positive frecencies from moz_places.
+  // Collect positive frecencies from moz_origins.
   let rows = await db.execute(`
-    SELECT frecency
-    FROM moz_places
-    WHERE id >= 0 AND frecency > 0;
+    SELECT frecency FROM moz_origins WHERE frecency > 0
   `);
   Assert.notEqual(rows.length, 0);
   let frecencies = rows.map(r => r.getResultByName("frecency"));
 
   // Collect stats.
   rows = await db.execute(`
     SELECT
-      (SELECT value FROM moz_meta WHERE key = "frecency_count"),
-      (SELECT value FROM moz_meta WHERE key = "frecency_sum"),
-      (SELECT value FROM moz_meta WHERE key = "frecency_sum_of_squares")
+      (SELECT value FROM moz_meta WHERE key = "origin_frecency_count"),
+      (SELECT value FROM moz_meta WHERE key = "origin_frecency_sum"),
+      (SELECT value FROM moz_meta WHERE key = "origin_frecency_sum_of_squares")
   `);
   let count = rows[0].getResultByIndex(0);
   let sum = rows[0].getResultByIndex(1);
   let squares = rows[0].getResultByIndex(2);
 
   Assert.equal(count, frecencies.length);
   Assert.equal(sum, frecencies.reduce((memo, f) => memo + f, 0));
   Assert.equal(squares, frecencies.reduce((memo, f) => memo + (f * f), 0));
deleted file mode 100644
--- a/toolkit/components/places/tests/unit/test_frecency_stats.js
+++ /dev/null
@@ -1,120 +0,0 @@
-/* This Source Code Form is subject to the terms of the Mozilla Public
- * License, v. 2.0. If a copy of the MPL was not distributed with this
- * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
-
-"use strict";
-
-add_task(async function init() {
-  await cleanUp();
-});
-
-
-// Adds/removes some visits and bookmarks and makes sure the stats are updated.
-add_task(async function basic() {
-  await checkStats([]);
-
-  let frecenciesByURL = {};
-  let urls = [0, 1, 2].map(i => "http://example.com/" + i);
-
-  // Add a URL 0 visit.
-  await PlacesTestUtils.addVisits([{ uri: urls[0] }]);
-  frecenciesByURL[urls[0]] = frecencyForUrl(urls[0]);
-  Assert.ok(frecenciesByURL[urls[0]] > 0, "Sanity check");
-
-  await checkStats(frecenciesByURL);
-
-  // Add a URL 1 visit.
-  await PlacesTestUtils.addVisits([{ uri: urls[1] }]);
-  frecenciesByURL[urls[1]] = frecencyForUrl(urls[1]);
-  Assert.ok(frecenciesByURL[urls[1]] > 0, "Sanity check");
-
-  await checkStats(frecenciesByURL);
-
-  // Add a URL 2 visit.
-  await PlacesTestUtils.addVisits([{ uri: urls[2] }]);
-  frecenciesByURL[urls[2]] = frecencyForUrl(urls[2]);
-  Assert.ok(frecenciesByURL[urls[2]] > 0, "Sanity check");
-
-  await checkStats(frecenciesByURL);
-
-  // Add another URL 2 visit.
-  await PlacesTestUtils.addVisits([{ uri: urls[2] }]);
-  frecenciesByURL[urls[2]] = frecencyForUrl(urls[2]);
-  Assert.ok(frecenciesByURL[urls[2]] > 0, "Sanity check");
-
-  await checkStats(frecenciesByURL);
-
-  // Remove URL 2's visits.
-  await PlacesUtils.history.remove([urls[2]]);
-  delete frecenciesByURL[urls[2]];
-
-  await checkStats(frecenciesByURL);
-
-  // Bookmark URL 1.
-  let parentGuid =
-    await PlacesUtils.promiseItemGuid(PlacesUtils.unfiledBookmarksFolderId);
-  let bookmark = await PlacesUtils.bookmarks.insert({
-    parentGuid,
-    title: "A bookmark",
-    url: NetUtil.newURI(urls[1]),
-  });
-  await PlacesUtils.promiseItemId(bookmark.guid);
-
-  frecenciesByURL[urls[1]] = frecencyForUrl(urls[1]);
-  Assert.ok(frecenciesByURL[urls[1]] > 0, "Sanity check");
-
-  await checkStats(frecenciesByURL);
-
-  // Remove URL 1's visit.
-  await PlacesUtils.history.remove([urls[1]]);
-  frecenciesByURL[urls[1]] = frecencyForUrl(urls[1]);
-  Assert.ok(frecenciesByURL[urls[1]] > 0, "Sanity check");
-
-  await checkStats(frecenciesByURL);
-
-  // Remove URL 1's bookmark.  Also need to call history.remove() again to
-  // remove the URL from moz_places.  Otherwise it sticks around and keeps
-  // contributing to the frecency stats.
-  await PlacesUtils.bookmarks.remove(bookmark);
-  await PlacesUtils.history.remove(urls[1]);
-  delete frecenciesByURL[urls[1]];
-
-  await checkStats(frecenciesByURL);
-
-  // Remove URL 0.
-  await PlacesUtils.history.remove([urls[0]]);
-  delete frecenciesByURL[urls[0]];
-
-  await checkStats(frecenciesByURL);
-
-  await cleanUp();
-});
-
-
-async function checkStats(frecenciesByURL) {
-  let stats = await promiseStats();
-  let fs = Object.values(frecenciesByURL);
-  Assert.equal(stats.count, fs.length);
-  Assert.equal(stats.sum, fs.reduce((memo, f) => memo + f, 0));
-  Assert.equal(stats.squares, fs.reduce((memo, f) => memo + (f * f), 0));
-}
-
-async function promiseStats() {
-  let db = await PlacesUtils.promiseDBConnection();
-  let rows = await db.execute(`
-    SELECT
-      IFNULL((SELECT value FROM moz_meta WHERE key = "frecency_count"), 0),
-      IFNULL((SELECT value FROM moz_meta WHERE key = "frecency_sum"), 0),
-      IFNULL((SELECT value FROM moz_meta WHERE key = "frecency_sum_of_squares"), 0)
-  `);
-  return {
-    count: rows[0].getResultByIndex(0),
-    sum: rows[0].getResultByIndex(1),
-    squares: rows[0].getResultByIndex(2),
-  };
-}
-
-async function cleanUp() {
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesUtils.history.clear();
-}
--- a/toolkit/components/places/tests/unit/test_origins.js
+++ b/toolkit/components/places/tests/unit/test_origins.js
@@ -1,187 +1,704 @@
 /* Any copyright is dedicated to the Public Domain.
    http://creativecommons.org/publicdomain/zero/1.0/ */
 
-// Makes sure the moz_origins table is updated correctly.
+// Makes sure the moz_origins table and origin frecency stats are updated
+// correctly.
+
+"use strict";
+
+// Visiting a URL with a new origin should immediately update moz_origins.
+add_task(async function visit() {
+  await checkDB([]);
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example.com/" },
+  ]);
+  await checkDB([
+    ["http://", "example.com", ["http://example.com/"]],
+  ]);
+  await PlacesUtils.history.remove("http://example.com/");
+  await checkDB([]);
+  await cleanUp();
+});
+
+
+// Repeatedly visiting a URL with an initially new origin should update
+// moz_origins (with the correct frecency).
+add_task(async function visitRepeatedly() {
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example.com/" },
+    { uri: "http://example.com/" },
+    { uri: "http://example.com/" },
+  ]);
+  await checkDB([
+    ["http://", "example.com", ["http://example.com/"]],
+  ]);
+  await PlacesUtils.history.remove("http://example.com/");
+  await checkDB([]);
+  await cleanUp();
+});
+
 
-// Comprehensive prefix and origin parsing test.
-add_task(async function parsing() {
-  let prefixes = [
-    "http://",
-    "https://",
-    "ftp://",
-    "foo://",
-    "bar:",
-  ];
+// Same as previous, but visits are added sequentially.
+add_task(async function visitRepeatedlySequential() {
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example.com/" },
+  ]);
+  await checkDB([
+    ["http://", "example.com", ["http://example.com/"]],
+  ]);
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example.com/" },
+  ]);
+  await checkDB([
+    ["http://", "example.com", ["http://example.com/"]],
+  ]);
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example.com/" },
+  ]);
+  await checkDB([
+    ["http://", "example.com", ["http://example.com/"]],
+  ]);
+  await PlacesUtils.history.remove("http://example.com/");
+  await checkDB([]);
+  await cleanUp();
+});
+
+
+// After removing an origin's URLs, visiting a URL with the origin should
+// immediately update moz_origins.
+add_task(async function vistAfterDelete() {
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example.com/" },
+  ]);
+  await PlacesUtils.history.remove("http://example.com/");
+  await checkDB([]);
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example.com/" },
+  ]);
+  await checkDB([
+    ["http://", "example.com", ["http://example.com/"]],
+  ]);
+  await PlacesUtils.history.remove("http://example.com/");
+  await checkDB([]);
+  await cleanUp();
+});
+
+
+// Visiting different URLs with the same origin should update moz_origins, and
+// moz_origins.frecency should be the sum of the URL frecencies.
+add_task(async function visitDifferentURLsSameOrigin() {
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example.com/1" },
+    { uri: "http://example.com/2" },
+    { uri: "http://example.com/3" },
+  ]);
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/1",
+      "http://example.com/2",
+      "http://example.com/3",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example.com/1");
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/2",
+      "http://example.com/3",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example.com/2");
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/3",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example.com/3");
+  await checkDB([]);
+  await cleanUp();
+});
+
 
-  let userinfos = [
-    "",
-    "user:pass@",
-    "user:pass:word@",
-    "user:@",
-  ];
+// Same as previous, but visits are added sequentially.
+add_task(async function visitDifferentURLsSameOriginSequential() {
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example.com/1" },
+  ]);
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/1",
+    ]],
+  ]);
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example.com/2" },
+  ]);
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/1",
+      "http://example.com/2",
+    ]],
+  ]);
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example.com/3" },
+  ]);
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/1",
+      "http://example.com/2",
+      "http://example.com/3",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example.com/1");
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/2",
+      "http://example.com/3",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example.com/2");
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/3",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example.com/3");
+  await checkDB([]);
+  await cleanUp();
+});
 
-  let ports = [
-    "",
-    ":8888",
-  ];
+
+// Repeatedly visiting different URLs with the same origin should update
+// moz_origins (with the correct frecencies), and moz_origins.frecency should be
+// the sum of the URL frecencies.
+add_task(async function visitDifferentURLsSameOriginRepeatedly() {
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example.com/1" },
+    { uri: "http://example.com/1" },
+    { uri: "http://example.com/1" },
+    { uri: "http://example.com/2" },
+    { uri: "http://example.com/2" },
+    { uri: "http://example.com/3" },
+  ]);
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/1",
+      "http://example.com/2",
+      "http://example.com/3",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example.com/1");
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/2",
+      "http://example.com/3",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example.com/2");
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/3",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example.com/3");
+  await checkDB([]);
+  await cleanUp();
+});
+
 
-  let paths = [
-    "",
+// Visiting URLs with different origins should update moz_origins.
+add_task(async function visitDifferentOrigins() {
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example1.com/" },
+    { uri: "http://example2.com/" },
+    { uri: "http://example3.com/" },
+  ]);
+  await checkDB([
+    ["http://", "example1.com", ["http://example1.com/"]],
+    ["http://", "example2.com", ["http://example2.com/"]],
+    ["http://", "example3.com", ["http://example3.com/"]],
+  ]);
+  await PlacesUtils.history.remove("http://example1.com/");
+  await checkDB([
+    ["http://", "example2.com", ["http://example2.com/"]],
+    ["http://", "example3.com", ["http://example3.com/"]],
+  ]);
+  await PlacesUtils.history.remove("http://example2.com/");
+  await checkDB([
+    ["http://", "example3.com", ["http://example3.com/"]],
+  ]);
+  await PlacesUtils.history.remove("http://example3.com/");
+  await checkDB([]);
+  await cleanUp();
+});
+
 
-    "/",
-    "/1",
-    "/1/2",
+// Same as previous, but visits are added sequentially.
+add_task(async function visitDifferentOriginsSequential() {
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example1.com/" },
+  ]);
+  await checkDB([
+    ["http://", "example1.com", ["http://example1.com/"]],
+  ]);
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example2.com/" },
+  ]);
+  await checkDB([
+    ["http://", "example1.com", ["http://example1.com/"]],
+    ["http://", "example2.com", ["http://example2.com/"]],
+  ]);
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example3.com/" },
+  ]);
+  await checkDB([
+    ["http://", "example1.com", ["http://example1.com/"]],
+    ["http://", "example2.com", ["http://example2.com/"]],
+    ["http://", "example3.com", ["http://example3.com/"]],
+  ]);
+  await PlacesUtils.history.remove("http://example1.com/");
+  await checkDB([
+    ["http://", "example2.com", ["http://example2.com/"]],
+    ["http://", "example3.com", ["http://example3.com/"]],
+  ]);
+  await PlacesUtils.history.remove("http://example2.com/");
+  await checkDB([
+    ["http://", "example3.com", ["http://example3.com/"]],
+  ]);
+  await PlacesUtils.history.remove("http://example3.com/");
+  await checkDB([]);
+  await cleanUp();
+});
 
-    "?",
-    "?1",
-    "#",
-    "#1",
+
+// Repeatedly visiting URLs with different origins should update moz_origins
+// (with the correct frecencies).
+add_task(async function visitDifferentOriginsRepeatedly() {
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example1.com/" },
+    { uri: "http://example1.com/" },
+    { uri: "http://example1.com/" },
+    { uri: "http://example2.com/" },
+    { uri: "http://example2.com/" },
+    { uri: "http://example3.com/" },
+  ]);
+  await checkDB([
+    ["http://", "example1.com", ["http://example1.com/"]],
+    ["http://", "example2.com", ["http://example2.com/"]],
+    ["http://", "example3.com", ["http://example3.com/"]],
+  ]);
+  await PlacesUtils.history.remove("http://example1.com/");
+  await checkDB([
+    ["http://", "example2.com", ["http://example2.com/"]],
+    ["http://", "example3.com", ["http://example3.com/"]],
+  ]);
+  await PlacesUtils.history.remove("http://example2.com/");
+  await checkDB([
+    ["http://", "example3.com", ["http://example3.com/"]],
+  ]);
+  await PlacesUtils.history.remove("http://example3.com/");
+  await checkDB([]);
+  await cleanUp();
+});
+
 
-    "/?",
-    "/1?",
-    "/?1",
-    "/1?2",
+// Visiting URLs, some with the same and some with different origins, should
+// update moz_origins.
+add_task(async function visitDifferentOriginsDifferentURLs() {
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example1.com/1" },
+    { uri: "http://example1.com/2" },
+    { uri: "http://example1.com/3" },
+    { uri: "http://example2.com/1" },
+    { uri: "http://example2.com/2" },
+    { uri: "http://example3.com/1" },
+  ]);
+  await checkDB([
+    ["http://", "example1.com", [
+      "http://example1.com/1",
+      "http://example1.com/2",
+      "http://example1.com/3",
+    ]],
+    ["http://", "example2.com", [
+      "http://example2.com/1",
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example1.com/1");
+  await checkDB([
+    ["http://", "example1.com", [
+      "http://example1.com/2",
+      "http://example1.com/3",
+    ]],
+    ["http://", "example2.com", [
+      "http://example2.com/1",
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example1.com/2");
+  await checkDB([
+    ["http://", "example1.com", [
+      "http://example1.com/3",
+    ]],
+    ["http://", "example2.com", [
+      "http://example2.com/1",
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example1.com/3");
+  await checkDB([
+    ["http://", "example2.com", [
+      "http://example2.com/1",
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example2.com/1");
+  await checkDB([
+    ["http://", "example2.com", [
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example2.com/2");
+  await checkDB([
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example3.com/1");
+  await checkDB([]);
+});
 
-    "/#",
-    "/1#",
-    "/#1",
-    "/1#2",
-
-    "/?#",
-    "/1?#",
-    "/?1#",
-    "/?#1",
-    "/1?2#",
-    "/1?#2",
-    "/?1#2",
-  ];
 
-  for (let userinfo of userinfos) {
-    for (let port of ports) {
-      for (let path of paths) {
-        info(`Testing userinfo='${userinfo}' port='${port}' path='${path}'`);
-        let prefixAndHostPorts = prefixes.map(prefix =>
-          [prefix, "example.com" + port]
-        );
-        let uris = prefixAndHostPorts.map(([prefix, hostPort]) =>
-          prefix + userinfo + hostPort + path
-        );
+// Same as previous, but visits are added sequentially.
+add_task(async function visitDifferentOriginsDifferentURLsSequential() {
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example1.com/1" },
+  ]);
+  await checkDB([
+    ["http://", "example1.com", [
+      "http://example1.com/1",
+    ]],
+  ]);
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example1.com/2" },
+  ]);
+  await checkDB([
+    ["http://", "example1.com", [
+      "http://example1.com/1",
+      "http://example1.com/2",
+    ]],
+  ]);
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example1.com/3" },
+  ]);
+  await checkDB([
+    ["http://", "example1.com", [
+      "http://example1.com/1",
+      "http://example1.com/2",
+      "http://example1.com/3",
+    ]],
+  ]);
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example2.com/1" },
+  ]);
+  await checkDB([
+    ["http://", "example1.com", [
+      "http://example1.com/1",
+      "http://example1.com/2",
+      "http://example1.com/3",
+    ]],
+    ["http://", "example2.com", [
+      "http://example2.com/1",
+    ]],
+  ]);
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example2.com/2" },
+  ]);
+  await checkDB([
+    ["http://", "example1.com", [
+      "http://example1.com/1",
+      "http://example1.com/2",
+      "http://example1.com/3",
+    ]],
+    ["http://", "example2.com", [
+      "http://example2.com/1",
+      "http://example2.com/2",
+    ]],
+  ]);
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example3.com/1" },
+  ]);
+  await checkDB([
+    ["http://", "example1.com", [
+      "http://example1.com/1",
+      "http://example1.com/2",
+      "http://example1.com/3",
+    ]],
+    ["http://", "example2.com", [
+      "http://example2.com/1",
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example1.com/1");
+  await checkDB([
+    ["http://", "example1.com", [
+      "http://example1.com/2",
+      "http://example1.com/3",
+    ]],
+    ["http://", "example2.com", [
+      "http://example2.com/1",
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example1.com/2");
+  await checkDB([
+    ["http://", "example1.com", [
+      "http://example1.com/3",
+    ]],
+    ["http://", "example2.com", [
+      "http://example2.com/1",
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example1.com/3");
+  await checkDB([
+    ["http://", "example2.com", [
+      "http://example2.com/1",
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example2.com/1");
+  await checkDB([
+    ["http://", "example2.com", [
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example2.com/2");
+  await checkDB([
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example3.com/1");
+  await checkDB([]);
+});
 
-        await PlacesTestUtils.addVisits(uris.map(uri => ({ uri })));
-        await checkDB(prefixAndHostPorts);
 
-        // Remove each URI, one at a time, and make sure the remaining origins
-        // in the database are correct.
-        for (let i = 0; i < uris.length; i++) {
-          await PlacesUtils.history.remove(uris[i]);
-          await checkDB(prefixAndHostPorts.slice(i + 1,
-                                                 prefixAndHostPorts.length));
-        }
-        await cleanUp();
-      }
-    }
-  }
+// Repeatedly visiting URLs, some with the same and some with different origins,
+// should update moz_origins (with the correct frecencies).
+add_task(async function visitDifferentOriginsDifferentURLsRepeatedly() {
+  await PlacesTestUtils.addVisits([
+    { uri: "http://example1.com/1" },
+    { uri: "http://example1.com/1" },
+    { uri: "http://example1.com/1" },
+    { uri: "http://example1.com/2" },
+    { uri: "http://example1.com/2" },
+    { uri: "http://example1.com/3" },
+    { uri: "http://example2.com/1" },
+    { uri: "http://example2.com/1" },
+    { uri: "http://example2.com/1" },
+    { uri: "http://example2.com/2" },
+    { uri: "http://example2.com/2" },
+    { uri: "http://example3.com/1" },
+    { uri: "http://example3.com/1" },
+  ]);
+  await checkDB([
+    ["http://", "example1.com", [
+      "http://example1.com/1",
+      "http://example1.com/2",
+      "http://example1.com/3",
+    ]],
+    ["http://", "example2.com", [
+      "http://example2.com/1",
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example1.com/1");
+  await checkDB([
+    ["http://", "example1.com", [
+      "http://example1.com/2",
+      "http://example1.com/3",
+    ]],
+    ["http://", "example2.com", [
+      "http://example2.com/1",
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example1.com/2");
+  await checkDB([
+    ["http://", "example1.com", [
+      "http://example1.com/3",
+    ]],
+    ["http://", "example2.com", [
+      "http://example2.com/1",
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example1.com/3");
+  await checkDB([
+    ["http://", "example2.com", [
+      "http://example2.com/1",
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example2.com/1");
+  await checkDB([
+    ["http://", "example2.com", [
+      "http://example2.com/2",
+    ]],
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example2.com/2");
+  await checkDB([
+    ["http://", "example3.com", [
+      "http://example3.com/1",
+    ]],
+  ]);
+  await PlacesUtils.history.remove("http://example3.com/1");
+  await checkDB([]);
 });
 
 
 // Makes sure URIs with the same TLD but different www subdomains are recognized
 // as different origins.  Makes sure removing one doesn't remove the others.
 add_task(async function www1() {
   await PlacesTestUtils.addVisits([
     { uri: "http://example.com/" },
     { uri: "http://www.example.com/" },
     { uri: "http://www.www.example.com/" },
   ]);
   await checkDB([
-    ["http://", "example.com"],
-    ["http://", "www.example.com"],
-    ["http://", "www.www.example.com"],
+    ["http://", "example.com", ["http://example.com/"]],
+    ["http://", "www.example.com", ["http://www.example.com/"]],
+    ["http://", "www.www.example.com", ["http://www.www.example.com/"]],
   ]);
   await PlacesUtils.history.remove("http://example.com/");
   await checkDB([
-    ["http://", "www.example.com"],
-    ["http://", "www.www.example.com"],
+    ["http://", "www.example.com", ["http://www.example.com/"]],
+    ["http://", "www.www.example.com", ["http://www.www.example.com/"]],
   ]);
   await PlacesUtils.history.remove("http://www.example.com/");
   await checkDB([
-    ["http://", "www.www.example.com"],
+    ["http://", "www.www.example.com", ["http://www.www.example.com/"]],
   ]);
   await PlacesUtils.history.remove("http://www.www.example.com/");
   await checkDB([
   ]);
   await cleanUp();
 });
 
 
 // Same as www1, but removes URIs in a different order.
 add_task(async function www2() {
   await PlacesTestUtils.addVisits([
     { uri: "http://example.com/" },
     { uri: "http://www.example.com/" },
     { uri: "http://www.www.example.com/" },
   ]);
   await checkDB([
-    ["http://", "example.com"],
-    ["http://", "www.example.com"],
-    ["http://", "www.www.example.com"],
+    ["http://", "example.com", ["http://example.com/"]],
+    ["http://", "www.example.com", ["http://www.example.com/"]],
+    ["http://", "www.www.example.com", ["http://www.www.example.com/"]],
   ]);
   await PlacesUtils.history.remove("http://www.www.example.com/");
   await checkDB([
-    ["http://", "example.com"],
-    ["http://", "www.example.com"],
+    ["http://", "example.com", ["http://example.com/"]],
+    ["http://", "www.example.com", ["http://www.example.com/"]],
   ]);
   await PlacesUtils.history.remove("http://www.example.com/");
   await checkDB([
-    ["http://", "example.com"],
+    ["http://", "example.com", ["http://example.com/"]],
   ]);
   await PlacesUtils.history.remove("http://example.com/");
   await checkDB([
   ]);
   await cleanUp();
 });
 
 
 // Makes sure removing an origin without a port doesn't remove the same host
 // with a port.
 add_task(async function ports1() {
   await PlacesTestUtils.addVisits([
     { uri: "http://example.com/" },
     { uri: "http://example.com:8888/" },
   ]);
   await checkDB([
-    ["http://", "example.com"],
-    ["http://", "example.com:8888"],
+    ["http://", "example.com", ["http://example.com/"]],
+    ["http://", "example.com:8888", ["http://example.com:8888/"]],
   ]);
   await PlacesUtils.history.remove("http://example.com/");
   await checkDB([
-    ["http://", "example.com:8888"],
+    ["http://", "example.com:8888", ["http://example.com:8888/"]],
   ]);
   await PlacesUtils.history.remove("http://example.com:8888/");
   await checkDB([
   ]);
   await cleanUp();
 });
 
 
 // Makes sure removing an origin with a port doesn't remove the same host
 // without a port.
 add_task(async function ports2() {
   await PlacesTestUtils.addVisits([
     { uri: "http://example.com/" },
     { uri: "http://example.com:8888/" },
   ]);
   await checkDB([
-    ["http://", "example.com"],
-    ["http://", "example.com:8888"],
+    ["http://", "example.com", ["http://example.com/"]],
+    ["http://", "example.com:8888", ["http://example.com:8888/"]],
   ]);
   await PlacesUtils.history.remove("http://example.com:8888/");
   await checkDB([
-    ["http://", "example.com"],
+    ["http://", "example.com", ["http://example.com/"]],
   ]);
   await PlacesUtils.history.remove("http://example.com/");
   await checkDB([
   ]);
   await cleanUp();
 });
 
 
@@ -202,141 +719,349 @@ add_task(async function duplicates() {
     { uri: "http://www.www.example.com/dupe" },
     { uri: "https://example.com/dupe" },
     { uri: "ftp://example.com/dupe" },
     { uri: "foo://example.com/dupe" },
     { uri: "bar:example.com/dupe" },
     { uri: "http://example.com:8888/dupe" },
   ]);
   await checkDB([
-    ["http://", "example.com"],
-    ["http://", "www.example.com"],
-    ["http://", "www.www.example.com"],
-    ["https://", "example.com"],
-    ["ftp://", "example.com"],
-    ["foo://", "example.com"],
-    ["bar:", "example.com"],
-    ["http://", "example.com:8888"],
+    ["http://", "example.com", [
+      "http://example.com/",
+      "http://example.com/dupe",
+    ]],
+    ["http://", "www.example.com", [
+      "http://www.example.com/",
+      "http://www.example.com/dupe",
+    ]],
+    ["http://", "www.www.example.com", [
+      "http://www.www.example.com/",
+      "http://www.www.example.com/dupe",
+    ]],
+    ["https://", "example.com", [
+      "https://example.com/",
+      "https://example.com/dupe",
+    ]],
+    ["ftp://", "example.com", [
+      "ftp://example.com/",
+      "ftp://example.com/dupe",
+    ]],
+    ["foo://", "example.com", [
+      "foo://example.com/",
+      "foo://example.com/dupe",
+    ]],
+    ["bar:", "example.com", [
+      "bar:example.com/",
+      "bar:example.com/dupe",
+    ]],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
 
   await PlacesUtils.history.remove("http://example.com/");
   await checkDB([
-    ["http://", "example.com"],
-    ["http://", "www.example.com"],
-    ["http://", "www.www.example.com"],
-    ["https://", "example.com"],
-    ["ftp://", "example.com"],
-    ["foo://", "example.com"],
-    ["bar:", "example.com"],
-    ["http://", "example.com:8888"],
+    ["http://", "example.com", [
+      "http://example.com/dupe",
+    ]],
+    ["http://", "www.example.com", [
+      "http://www.example.com/",
+      "http://www.example.com/dupe",
+    ]],
+    ["http://", "www.www.example.com", [
+      "http://www.www.example.com/",
+      "http://www.www.example.com/dupe",
+    ]],
+    ["https://", "example.com", [
+      "https://example.com/",
+      "https://example.com/dupe",
+    ]],
+    ["ftp://", "example.com", [
+      "ftp://example.com/",
+      "ftp://example.com/dupe",
+    ]],
+    ["foo://", "example.com", [
+      "foo://example.com/",
+      "foo://example.com/dupe",
+    ]],
+    ["bar:", "example.com", [
+      "bar:example.com/",
+      "bar:example.com/dupe",
+    ]],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
   await PlacesUtils.history.remove("http://example.com/dupe");
   await checkDB([
-    ["http://", "www.example.com"],
-    ["http://", "www.www.example.com"],
-    ["https://", "example.com"],
-    ["ftp://", "example.com"],
-    ["foo://", "example.com"],
-    ["bar:", "example.com"],
-    ["http://", "example.com:8888"],
+    ["http://", "www.example.com", [
+      "http://www.example.com/",
+      "http://www.example.com/dupe",
+    ]],
+    ["http://", "www.www.example.com", [
+      "http://www.www.example.com/",
+      "http://www.www.example.com/dupe",
+    ]],
+    ["https://", "example.com", [
+      "https://example.com/",
+      "https://example.com/dupe",
+    ]],
+    ["ftp://", "example.com", [
+      "ftp://example.com/",
+      "ftp://example.com/dupe",
+    ]],
+    ["foo://", "example.com", [
+      "foo://example.com/",
+      "foo://example.com/dupe",
+    ]],
+    ["bar:", "example.com", [
+      "bar:example.com/",
+      "bar:example.com/dupe",
+    ]],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
 
   await PlacesUtils.history.remove("http://www.example.com/");
   await checkDB([
-    ["http://", "www.example.com"],
-    ["http://", "www.www.example.com"],
-    ["https://", "example.com"],
-    ["ftp://", "example.com"],
-    ["foo://", "example.com"],
-    ["bar:", "example.com"],
-    ["http://", "example.com:8888"],
+    ["http://", "www.example.com", [
+      "http://www.example.com/dupe",
+    ]],
+    ["http://", "www.www.example.com", [
+      "http://www.www.example.com/",
+      "http://www.www.example.com/dupe",
+    ]],
+    ["https://", "example.com", [
+      "https://example.com/",
+      "https://example.com/dupe",
+    ]],
+    ["ftp://", "example.com", [
+      "ftp://example.com/",
+      "ftp://example.com/dupe",
+    ]],
+    ["foo://", "example.com", [
+      "foo://example.com/",
+      "foo://example.com/dupe",
+    ]],
+    ["bar:", "example.com", [
+      "bar:example.com/",
+      "bar:example.com/dupe",
+    ]],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
   await PlacesUtils.history.remove("http://www.example.com/dupe");
   await checkDB([
-    ["http://", "www.www.example.com"],
-    ["https://", "example.com"],
-    ["ftp://", "example.com"],
-    ["foo://", "example.com"],
-    ["bar:", "example.com"],
-    ["http://", "example.com:8888"],
+    ["http://", "www.www.example.com", [
+      "http://www.www.example.com/",
+      "http://www.www.example.com/dupe",
+    ]],
+    ["https://", "example.com", [
+      "https://example.com/",
+      "https://example.com/dupe",
+    ]],
+    ["ftp://", "example.com", [
+      "ftp://example.com/",
+      "ftp://example.com/dupe",
+    ]],
+    ["foo://", "example.com", [
+      "foo://example.com/",
+      "foo://example.com/dupe",
+    ]],
+    ["bar:", "example.com", [
+      "bar:example.com/",
+      "bar:example.com/dupe",
+    ]],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
 
   await PlacesUtils.history.remove("http://www.www.example.com/");
   await checkDB([
-    ["http://", "www.www.example.com"],
-    ["https://", "example.com"],
-    ["ftp://", "example.com"],
-    ["foo://", "example.com"],
-    ["bar:", "example.com"],
-    ["http://", "example.com:8888"],
+    ["http://", "www.www.example.com", [
+      "http://www.www.example.com/dupe",
+    ]],
+    ["https://", "example.com", [
+      "https://example.com/",
+      "https://example.com/dupe",
+    ]],
+    ["ftp://", "example.com", [
+      "ftp://example.com/",
+      "ftp://example.com/dupe",
+    ]],
+    ["foo://", "example.com", [
+      "foo://example.com/",
+      "foo://example.com/dupe",
+    ]],
+    ["bar:", "example.com", [
+      "bar:example.com/",
+      "bar:example.com/dupe",
+    ]],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
   await PlacesUtils.history.remove("http://www.www.example.com/dupe");
   await checkDB([
-    ["https://", "example.com"],
-    ["ftp://", "example.com"],
-    ["foo://", "example.com"],
-    ["bar:", "example.com"],
-    ["http://", "example.com:8888"],
+    ["https://", "example.com", [
+      "https://example.com/",
+      "https://example.com/dupe",
+    ]],
+    ["ftp://", "example.com", [
+      "ftp://example.com/",
+      "ftp://example.com/dupe",
+    ]],
+    ["foo://", "example.com", [
+      "foo://example.com/",
+      "foo://example.com/dupe",
+    ]],
+    ["bar:", "example.com", [
+      "bar:example.com/",
+      "bar:example.com/dupe",
+    ]],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
 
   await PlacesUtils.history.remove("https://example.com/");
   await checkDB([
-    ["https://", "example.com"],
-    ["ftp://", "example.com"],
-    ["foo://", "example.com"],
-    ["bar:", "example.com"],
-    ["http://", "example.com:8888"],
+    ["https://", "example.com", [
+      "https://example.com/dupe",
+    ]],
+    ["ftp://", "example.com", [
+      "ftp://example.com/",
+      "ftp://example.com/dupe",
+    ]],
+    ["foo://", "example.com", [
+      "foo://example.com/",
+      "foo://example.com/dupe",
+    ]],
+    ["bar:", "example.com", [
+      "bar:example.com/",
+      "bar:example.com/dupe",
+    ]],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
   await PlacesUtils.history.remove("https://example.com/dupe");
   await checkDB([
-    ["ftp://", "example.com"],
-    ["foo://", "example.com"],
-    ["bar:", "example.com"],
-    ["http://", "example.com:8888"],
+    ["ftp://", "example.com", [
+      "ftp://example.com/",
+      "ftp://example.com/dupe",
+    ]],
+    ["foo://", "example.com", [
+      "foo://example.com/",
+      "foo://example.com/dupe",
+    ]],
+    ["bar:", "example.com", [
+      "bar:example.com/",
+      "bar:example.com/dupe",
+    ]],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
 
   await PlacesUtils.history.remove("ftp://example.com/");
   await checkDB([
-    ["ftp://", "example.com"],
-    ["foo://", "example.com"],
-    ["bar:", "example.com"],
-    ["http://", "example.com:8888"],
+    ["ftp://", "example.com", [
+      "ftp://example.com/dupe",
+    ]],
+    ["foo://", "example.com", [
+      "foo://example.com/",
+      "foo://example.com/dupe",
+    ]],
+    ["bar:", "example.com", [
+      "bar:example.com/",
+      "bar:example.com/dupe",
+    ]],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
   await PlacesUtils.history.remove("ftp://example.com/dupe");
   await checkDB([
-    ["foo://", "example.com"],
-    ["bar:", "example.com"],
-    ["http://", "example.com:8888"],
+    ["foo://", "example.com", [
+      "foo://example.com/",
+      "foo://example.com/dupe",
+    ]],
+    ["bar:", "example.com", [
+      "bar:example.com/",
+      "bar:example.com/dupe",
+    ]],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
 
   await PlacesUtils.history.remove("foo://example.com/");
   await checkDB([
-    ["foo://", "example.com"],
-    ["bar:", "example.com"],
-    ["http://", "example.com:8888"],
+    ["foo://", "example.com", [
+      "foo://example.com/dupe",
+    ]],
+    ["bar:", "example.com", [
+      "bar:example.com/",
+      "bar:example.com/dupe",
+    ]],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
   await PlacesUtils.history.remove("foo://example.com/dupe");
   await checkDB([
-    ["bar:", "example.com"],
-    ["http://", "example.com:8888"],
+    ["bar:", "example.com", [
+      "bar:example.com/",
+      "bar:example.com/dupe",
+    ]],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
 
   await PlacesUtils.history.remove("bar:example.com/");
   await checkDB([
-    ["bar:", "example.com"],
-    ["http://", "example.com:8888"],
+    ["bar:", "example.com", [
+      "bar:example.com/dupe",
+    ]],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
   await PlacesUtils.history.remove("bar:example.com/dupe");
   await checkDB([
-    ["http://", "example.com:8888"],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/",
+      "http://example.com:8888/dupe",
+    ]],
   ]);
 
   await PlacesUtils.history.remove("http://example.com:8888/");
   await checkDB([
-    ["http://", "example.com:8888"],
+    ["http://", "example.com:8888", [
+      "http://example.com:8888/dupe",
+    ]],
   ]);
   await PlacesUtils.history.remove("http://example.com:8888/dupe");
   await checkDB([
   ]);
 
   await cleanUp();
 });
 
@@ -350,23 +1075,23 @@ add_task(async function addRemoveBookmar
   ];
   for (let url of urls) {
     bookmarks.push(await PlacesUtils.bookmarks.insert({
       url,
       parentGuid: PlacesUtils.bookmarks.unfiledGuid,
     }));
   }
   await checkDB([
-    ["http://", "example.com"],
-    ["http://", "www.example.com"],
+    ["http://", "example.com", ["http://example.com/"]],
+    ["http://", "www.example.com", ["http://www.example.com/"]],
   ]);
   await PlacesUtils.bookmarks.remove(bookmarks[0]);
   await PlacesUtils.history.clear();
   await checkDB([
-    ["http://", "www.example.com"],
+    ["http://", "www.example.com", ["http://www.example.com/"]],
   ]);
   await PlacesUtils.bookmarks.remove(bookmarks[1]);
   await PlacesUtils.history.clear();
   await checkDB([
   ]);
   await cleanUp();
 });
 
@@ -380,38 +1105,215 @@ add_task(async function changeBookmarks(
   ];
   for (let url of urls) {
     bookmarks.push(await PlacesUtils.bookmarks.insert({
       url,
       parentGuid: PlacesUtils.bookmarks.unfiledGuid,
     }));
   }
   await checkDB([
-    ["http://", "example.com"],
-    ["http://", "www.example.com"],
+    ["http://", "example.com", ["http://example.com/"]],
+    ["http://", "www.example.com", ["http://www.example.com/"]],
   ]);
   await PlacesUtils.bookmarks.update({
     url: "http://www.example.com/",
     guid: bookmarks[0].guid,
   });
   await PlacesUtils.history.clear();
   await checkDB([
-    ["http://", "www.example.com"],
+    ["http://", "www.example.com", ["http://www.example.com/"]],
   ]);
   await cleanUp();
 });
 
 
+// A slightly more complex test to make sure origin frecency stats are updated
+// when visits and bookmarks are added and removed.
+add_task(async function moreOriginFrecencyStats() {
+  await checkDB([]);
+
+  // Add a URL 0 visit.
+  await PlacesTestUtils.addVisits([{ uri: "http://example.com/0" }]);
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/0",
+    ]],
+  ]);
+
+  // Add a URL 1 visit.
+  await PlacesTestUtils.addVisits([{ uri: "http://example.com/1" }]);
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/0",
+      "http://example.com/1",
+    ]],
+  ]);
+
+  // Add a URL 2 visit.
+  await PlacesTestUtils.addVisits([{ uri: "http://example.com/2" }]);
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/0",
+      "http://example.com/1",
+      "http://example.com/2",
+    ]],
+  ]);
+
+  // Add another URL 2 visit.
+  await PlacesTestUtils.addVisits([{ uri: "http://example.com/2" }]);
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/0",
+      "http://example.com/1",
+      "http://example.com/2",
+    ]],
+  ]);
+
+  // Remove URL 2's visits.
+  await PlacesUtils.history.remove(["http://example.com/2"]);
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/0",
+      "http://example.com/1",
+    ]],
+  ]);
+
+  // Bookmark URL 1.
+  let parentGuid =
+    await PlacesUtils.promiseItemGuid(PlacesUtils.unfiledBookmarksFolderId);
+  let bookmark = await PlacesUtils.bookmarks.insert({
+    parentGuid,
+    title: "A bookmark",
+    url: NetUtil.newURI("http://example.com/1"),
+  });
+  await PlacesUtils.promiseItemId(bookmark.guid);
+
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/0",
+      "http://example.com/1",
+    ]],
+  ]);
+
+  // Remove URL 1's visit.
+  await PlacesUtils.history.remove(["http://example.com/1"]);
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/0",
+      "http://example.com/1",
+    ]],
+  ]);
+
+  // Remove URL 1's bookmark.  Also need to call history.remove() again to
+  // remove the URL from moz_places.  Otherwise it sticks around and keeps
+  // contributing to the frecency stats.
+  await PlacesUtils.bookmarks.remove(bookmark);
+  await PlacesUtils.history.remove("http://example.com/1");
+  await checkDB([
+    ["http://", "example.com", [
+      "http://example.com/0",
+    ]],
+  ]);
+
+  // Remove URL 0.
+  await PlacesUtils.history.remove(["http://example.com/0"]);
+  await checkDB([
+  ]);
+
+  await cleanUp();
+});
+
+
+/**
+ * Returns the expected frecency of the origin of the given URLs, i.e., the sum
+ * of their frecencies.  Each URL is expected to have the same origin.
+ *
+ * @param  urls
+ *         An array of URL strings.
+ * @return The expected origin frecency.
+ */
+function expectedOriginFrecency(urls) {
+  return urls.reduce((sum, url) => sum + Math.max(frecencyForUrl(url), 0), 0);
+}
+
+/**
+ * Asserts that the moz_origins table and the origin frecency stats are correct.
+ *
+ * @param expectedOrigins
+ *        An array of expected origins.  Each origin in the array is itself an
+ *        array that looks like this:
+ *          [prefix, host, [url1, url2, ..., urln]]
+ *        The element at index 2 is an array of all the URLs with the origin.
+ *        If you don't care about checking frecencies and origin frecency stats,
+ *        this element can be `undefined`.
+ */
 async function checkDB(expectedOrigins) {
   let db = await PlacesUtils.promiseDBConnection();
   let rows = await db.execute(`
-    SELECT prefix, host
+    SELECT prefix, host, frecency
     FROM moz_origins
     ORDER BY id ASC
   `);
-  let actual = rows.map(r => [r.getString(0), r.getString(1)]);
-  Assert.deepEqual(actual, expectedOrigins);
+  let checkFrecencies = !expectedOrigins.length || expectedOrigins[0][2] !== undefined;
+  let actualOrigins = rows.map(row => {
+    let o = [];
+    for (let c = 0; c < (checkFrecencies ? 3 : 2); c++) {
+      o.push(row.getResultByIndex(c));
+    }
+    return o;
+  });
+  expectedOrigins = expectedOrigins.map(o => {
+    return o.slice(0, 2).concat(
+      checkFrecencies ? expectedOriginFrecency(o[2]) : []
+    );
+  });
+  Assert.deepEqual(actualOrigins, expectedOrigins);
+  if (checkFrecencies) {
+    await checkStats(expectedOrigins.map(o => o[2]).filter(o => o > 0));
+  }
+}
+
+/**
+ * Asserts that the origin frecency stats are correct.
+ *
+ * @param expectedOriginFrecencies
+ *        An array of expected origin frecencies.
+ */
+async function checkStats(expectedOriginFrecencies) {
+  let stats = await promiseStats();
+  Assert.equal(
+    stats.count,
+    expectedOriginFrecencies.length
+  );
+  Assert.equal(
+    stats.sum,
+    expectedOriginFrecencies.reduce((sum, f) => sum + f, 0)
+  );
+  Assert.equal(
+    stats.squares,
+    expectedOriginFrecencies.reduce((squares, f) => squares + (f * f), 0)
+  );
+}
+
+/**
+ * Returns the origin frecency stats.
+ *
+ * @return An object: { count, sum, squares }
+ */
+async function promiseStats() {
+  let db = await PlacesUtils.promiseDBConnection();
+  let rows = await db.execute(`
+    SELECT
+      IFNULL((SELECT value FROM moz_meta WHERE key = "origin_frecency_count"), 0),
+      IFNULL((SELECT value FROM moz_meta WHERE key = "origin_frecency_sum"), 0),
+      IFNULL((SELECT value FROM moz_meta WHERE key = "origin_frecency_sum_of_squares"), 0)
+  `);
+  return {
+    count: rows[0].getResultByIndex(0),
+    sum: rows[0].getResultByIndex(1),
+    squares: rows[0].getResultByIndex(2),
+  };
 }
 
 async function cleanUp() {
   await PlacesUtils.bookmarks.eraseEverything();
   await PlacesUtils.history.clear();
 }
new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/unit/test_origins_parsing.js
@@ -0,0 +1,118 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// This test is a companion to test_origins.js.  It adds many URLs to the
+// database and makes sure that their prefixes and hosts are correctly parsed.
+// This test can take a while to run, which is why it's split out from
+// test_origins.js.
+
+"use strict";
+
+add_task(async function parsing() {
+  let prefixes = [
+    "http://",
+    "https://",
+    "ftp://",
+    "foo://",
+    "bar:",
+  ];
+
+  let userinfos = [
+    "",
+    "user:pass@",
+    "user:pass:word@",
+    "user:@",
+  ];
+
+  let ports = [
+    "",
+    ":8888",
+  ];
+
+  let paths = [
+    "",
+
+    "/",
+    "/1",
+    "/1/2",
+
+    "?",
+    "?1",
+    "#",
+    "#1",
+
+    "/?",
+    "/1?",
+    "/?1",
+    "/1?2",
+
+    "/#",
+    "/1#",
+    "/#1",
+    "/1#2",
+
+    "/?#",
+    "/1?#",
+    "/?1#",
+    "/?#1",
+    "/1?2#",
+    "/1?#2",
+    "/?1#2",
+  ];
+
+  for (let userinfo of userinfos) {
+    for (let port of ports) {
+      for (let path of paths) {
+        info(`Testing userinfo='${userinfo}' port='${port}' path='${path}'`);
+        let expectedOrigins = prefixes.map(prefix =>
+          [prefix, "example.com" + port]
+        );
+        let uris = expectedOrigins.map(([prefix, hostPort]) =>
+          prefix + userinfo + hostPort + path
+        );
+
+        await PlacesTestUtils.addVisits(uris.map(uri => ({ uri })));
+        await checkDB(expectedOrigins);
+
+        // Remove each URI, one at a time, and make sure the remaining origins
+        // in the database are correct.
+        for (let i = 0; i < uris.length; i++) {
+          await PlacesUtils.history.remove(uris[i]);
+          await checkDB(expectedOrigins.slice(i + 1, expectedOrigins.length));
+        }
+        await cleanUp();
+      }
+    }
+  }
+  await checkDB([]);
+});
+
+
+/**
+ * Asserts that the moz_origins table is correct.
+ *
+ * @param expectedOrigins
+ *        An array of expected origins.  Each origin in the array is itself an
+ *        array that looks like this: [prefix, host]
+ */
+async function checkDB(expectedOrigins) {
+  let db = await PlacesUtils.promiseDBConnection();
+  let rows = await db.execute(`
+    SELECT prefix, host
+    FROM moz_origins
+    ORDER BY id ASC
+  `);
+  let actualOrigins = rows.map(row => {
+    let o = [];
+    for (let c = 0; c < 2; c++) {
+      o.push(row.getResultByIndex(c));
+    }
+    return o;
+  });
+  Assert.deepEqual(actualOrigins, expectedOrigins);
+}
+
+async function cleanUp() {
+  await PlacesUtils.bookmarks.eraseEverything();
+  await PlacesUtils.history.clear();
+}
--- a/toolkit/components/places/tests/unit/test_sql_function_origin.js
+++ b/toolkit/components/places/tests/unit/test_sql_function_origin.js
@@ -1,17 +1,18 @@
 /* Any copyright is dedicated to the Public Domain.
    http://creativecommons.org/publicdomain/zero/1.0/ */
 
 // Tests the origin-related SQL functions, which are:
 // * get_host_and_port
 // * get_prefix
 // * strip_prefix_and_userinfo
 
-add_task(async function test() {
+// Tests actual URL strings.
+add_task(async function urls() {
   let sets = [
     ["http:"],
     ["", "//"],
     ["", "user@", "user:@", "user:pass@", "user:pass:word@"],
     ["example.com"],
     ["", ":8888"],
     ["", "/", "/foo"],
     ["", "?", "?bar"],
@@ -30,16 +31,38 @@ add_task(async function test() {
         SELECT ${func}("${spec}");
       `);
       let value = rows[0].getString(0);
       Assert.equal(value, expectedValue, `function=${func} spec="${spec}"`);
     }
   }
 });
 
+
+// Tests strings that aren't URLs.
+add_task(async function nonURLs() {
+  let db = await PlacesUtils.promiseDBConnection();
+
+  let value = (await db.execute(`
+    SELECT get_prefix("hello");
+  `))[0].getString(0);
+  Assert.equal(value, "");
+
+  value = (await db.execute(`
+    SELECT get_host_and_port("hello");
+  `))[0].getString(0);
+  Assert.equal(value, "hello");
+
+  value = (await db.execute(`
+    SELECT strip_prefix_and_userinfo("hello");
+  `))[0].getString(0);
+  Assert.equal(value, "hello");
+});
+
+
 function permute(sets = []) {
   if (!sets.length) {
     return [[]];
   }
   let firstSet = sets[0];
   let otherSets = sets.slice(1);
   let permutedSequences = [];
   let otherPermutedSequences = permute(otherSets);
--- a/toolkit/components/places/tests/unit/xpcshell.ini
+++ b/toolkit/components/places/tests/unit/xpcshell.ini
@@ -54,17 +54,16 @@ skip-if = os == "linux" # Bug 821781
 [test_bookmarks_restore_notification.js]
 [test_broken_folderShortcut_result.js]
 [test_browserhistory.js]
 [test_bug636917_isLivemark.js]
 [test_childlessTags.js]
 [test_download_history.js]
 [test_frecency.js]
 [test_frecency_decay.js]
-[test_frecency_stats.js]
 [test_frecency_zero_updated.js]
 [test_getChildIndex.js]
 [test_hash.js]
 [test_history.js]
 [test_history_clear.js]
 [test_history_notifications.js]
 [test_history_observer.js]
 [test_history_sidebar.js]
@@ -81,16 +80,17 @@ support-files = missingBuiltIn.sqlite
 [test_missing_root_folder.js]
 support-files = noRoot.sqlite
 [test_mozIAsyncLivemarks.js]
 [test_multi_word_tags.js]
 [test_nsINavHistoryViewer.js]
 [test_null_interfaces.js]
 [test_onItemChanged_tags.js]
 [test_origins.js]
+[test_origins_parsing.js]
 [test_pageGuid_bookmarkGuid.js]
 [test_frecency_observers.js]
 [test_placeURIs.js]
 [test_PlacesUtils_annotations.js]
 [test_PlacesUtils_invalidateCachedGuidFor.js]
 [test_PlacesUtils_isRootItem.js]
 [test_promiseBookmarksTree.js]
 [test_resolveNullBookmarkTitles.js]