Bug 1467627 - Calculate origin frecency as the sum of all URL frecencies instead of the max. r=mak
authorDrew Willcoxon <adw@mozilla.com>
Wed, 04 Jul 2018 14:01:28 -0700
changeset 425144 5c31149518e382ce0ea150f04377a797bc3bbb15
parent 425143 2a15405f40575993a010dd204a4b4c1f781d9d17
child 425145 4312952f4b2a9d7aaf1ce6cbd2c2fb2834711f7d
push id104984
push useraciure@mozilla.com
push dateThu, 05 Jul 2018 09:55:01 +0000
treeherdermozilla-inbound@35ae03d7cf2d [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmak
bugs1467627
milestone63.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
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
@@ -2539,16 +2539,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);
@@ -2370,130 +2381,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;
@@ -2649,16 +2565,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
@@ -2088,16 +2088,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
@@ -632,17 +632,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]