Add database to use as the source of an alternative algorithm for Network Action Prediction

BUG=98110
TEST=unit_tests:NetworkActionPredictor*,interactive_ui_tests:OmniboxViewTest*


Review URL: http://codereview.chromium.org/8241014

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@109509 0039d316-1c4b-4281-b951-d872f2087c98

23 files changed, 1340 insertions, 61 deletions

diff --git a/chrome/browser/autocomplete/autocomplete_edit.cc b/chrome/browser/autocomplete/autocomplete_edit.cc
index b9f7000..096d2ad 100644
--- a/chrome/browser/autocomplete/autocomplete_edit.cc
+++ b/chrome/browser/autocomplete/autocomplete_edit.cc
@@ -16,6 +16,7 @@
 #include "chrome/browser/autocomplete/autocomplete_popup_model.h"
 #include "chrome/browser/autocomplete/autocomplete_popup_view.h"
 #include "chrome/browser/autocomplete/keyword_provider.h"
+#include "chrome/browser/autocomplete/network_action_predictor.h"
 #include "chrome/browser/autocomplete/search_provider.h"
 #include "chrome/browser/bookmarks/bookmark_utils.h"
 #include "chrome/browser/command_updater.h"
@@ -89,8 +90,7 @@ AutocompleteEditModel::AutocompleteEditModel(
       profile_(profile),
       in_revert_(false),
       allow_exact_keyword_match_(false),
-      instant_complete_behavior_(INSTANT_COMPLETE_DELAYED),
-      network_action_predictor_(profile) {
+      instant_complete_behavior_(INSTANT_COMPLETE_DELAYED) {
 }
 
 AutocompleteEditModel::~AutocompleteEditModel() {
@@ -217,9 +217,15 @@ void AutocompleteEditModel::OnChanged() {
 
   // Confer with the NetworkActionPredictor to determine what action, if any,
   // we should take. Get the recommended action here even if we don't need it
-  // so we can get stats for anyone who is opted in to UMA.
-  NetworkActionPredictor::Action recommended_action =
-      network_action_predictor_.RecommendAction(user_text_, current_match);
+  // so we can get stats for anyone who is opted in to UMA, but only get it if
+  // the user has actually typed something to avoid constructing it before it's
+  // needed. Note: This event is triggered as part of startup when the initial
+  // tab transitions to the start page.
+  NetworkActionPredictor* network_action_predictor = user_input_in_progress() ?
+      profile_->GetNetworkActionPredictor() : NULL;
+  NetworkActionPredictor::Action recommended_action = network_action_predictor ?
+       network_action_predictor->RecommendAction(user_text_, current_match) :
+       NetworkActionPredictor::ACTION_NONE;
   UMA_HISTOGRAM_ENUMERATION("NetworkActionPredictor.Action_" +
                             prerender::GetOmniboxHistogramSuffix(),
                             recommended_action,
@@ -227,10 +233,6 @@ void AutocompleteEditModel::OnChanged() {
   if (DoInstant(current_match, &suggested_text)) {
     SetSuggestedText(suggested_text, instant_complete_behavior_);
   } else {
-    // Ignore the recommended action if Omnibox prerendering is not enabled.
-    if (!prerender::IsOmniboxEnabled(profile_))
-      recommended_action = NetworkActionPredictor::ACTION_NONE;
-
     switch (recommended_action) {
       case NetworkActionPredictor::ACTION_PRERENDER:
         DoPrerender(current_match);
@@ -1034,15 +1036,13 @@ void AutocompleteEditModel::DoPrerender(const AutocompleteMatch& match) {
   // Do not prerender if the destination URL is the same as the current URL.
   if (match.destination_url == PermanentURL())
     return;
-  if (user_input_in_progress() && popup_->IsOpen()) {
-    TabContentsWrapper* tab = controller_->GetTabContentsWrapper();
-    prerender::PrerenderManager* prerender_manager =
-        prerender::PrerenderManagerFactory::GetForProfile(tab->profile());
-    if (prerender_manager) {
-      RenderViewHost* current_host = tab->tab_contents()->render_view_host();
-      prerender_manager->AddPrerenderFromOmnibox(
-          match.destination_url, current_host->session_storage_namespace());
-    }
+  TabContentsWrapper* tab = controller_->GetTabContentsWrapper();
+  prerender::PrerenderManager* prerender_manager =
+      prerender::PrerenderManagerFactory::GetForProfile(tab->profile());
+  if (prerender_manager) {
+    RenderViewHost* current_host = tab->tab_contents()->render_view_host();
+    prerender_manager->AddPrerenderFromOmnibox(
+        match.destination_url, current_host->session_storage_namespace());
   }
 }
 
diff --git a/chrome/browser/autocomplete/autocomplete_edit.h b/chrome/browser/autocomplete/autocomplete_edit.h
index ae94f3f..f33e509 100644
--- a/chrome/browser/autocomplete/autocomplete_edit.h
+++ b/chrome/browser/autocomplete/autocomplete_edit.h
@@ -10,7 +10,6 @@
 #include "base/string16.h"
 #include "chrome/browser/autocomplete/autocomplete_controller_delegate.h"
 #include "chrome/browser/autocomplete/autocomplete_match.h"
-#include "chrome/browser/autocomplete/network_action_predictor.h"
 #include "chrome/common/instant_types.h"
 #include "content/public/common/page_transition_types.h"
 #include "googleurl/src/gurl.h"
@@ -23,7 +22,6 @@ class AutocompleteEditModel;
 class AutocompletePopupModel;
 class AutocompleteResult;
 class InstantController;
-class NetworkActionPredictor;
 class OmniboxView;
 class Profile;
 class SkBitmap;
@@ -555,9 +553,6 @@ class AutocompleteEditModel : public AutocompleteControllerDelegate {
   // Last value of InstantCompleteBehavior supplied to |SetSuggestedText|.
   InstantCompleteBehavior instant_complete_behavior_;
 
-  // Used to determine what network actions to take in different circumstances.
-  NetworkActionPredictor network_action_predictor_;
-
   DISALLOW_COPY_AND_ASSIGN(AutocompleteEditModel);
 };
 
diff --git a/chrome/browser/autocomplete/network_action_predictor.cc b/chrome/browser/autocomplete/network_action_predictor.cc
index 923f1c8..31066d2 100644
--- a/chrome/browser/autocomplete/network_action_predictor.cc
+++ b/chrome/browser/autocomplete/network_action_predictor.cc
@@ -6,15 +6,27 @@
 
 #include <math.h>
 
+#include <vector>
+
+#include "base/bind.h"
 #include "base/i18n/case_conversion.h"
 #include "base/metrics/histogram.h"
 #include "base/string_util.h"
 #include "base/utf_string_conversions.h"
+#include "chrome/browser/autocomplete/autocomplete.h"
 #include "chrome/browser/autocomplete/autocomplete_match.h"
+#include "chrome/browser/autocomplete/network_action_predictor_database.h"
 #include "chrome/browser/history/history.h"
+#include "chrome/browser/history/history_notifications.h"
 #include "chrome/browser/history/in_memory_database.h"
 #include "chrome/browser/prerender/prerender_field_trial.h"
 #include "chrome/browser/profiles/profile.h"
+#include "chrome/common/chrome_notification_types.h"
+#include "chrome/common/guid.h"
+#include "content/public/browser/browser_thread.h"
+#include "content/public/browser/notification_details.h"
+#include "content/public/browser/notification_service.h"
+#include "content/public/browser/notification_source.h"
 
 namespace {
 
@@ -23,6 +35,9 @@ const float kConfidenceCutoff[] = {
   0.5f
 };
 
+const size_t kMinimumUserTextLength = 2;
+const int kMinimumNumberOfHits = 3;
+
 COMPILE_ASSERT(arraysize(kConfidenceCutoff) ==
                NetworkActionPredictor::LAST_PREDICT_ACTION,
                ConfidenceCutoff_count_mismatch);
@@ -82,11 +97,37 @@ bool GetURLRowForAutocompleteMatch(Profile* profile,
 
 }
 
+const int NetworkActionPredictor::kMaximumDaysToKeepEntry = 14;
+
 NetworkActionPredictor::NetworkActionPredictor(Profile* profile)
-  : profile_(profile) {
+    : profile_(profile),
+      db_(new NetworkActionPredictorDatabase(profile)),
+      initialized_(false) {
+  content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE,
+      base::Bind(&NetworkActionPredictorDatabase::Initialize, db_));
+
+  // Request the in-memory database from the history to force it to load so it's
+  // available as soon as possible.
+  HistoryService* history_service =
+      profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
+  if (history_service)
+    history_service->InMemoryDatabase();
+
+  // Create local caches using the database as loaded. We will garbage collect
+  // rows from the caches and the database once the history service is
+  // available.
+  std::vector<NetworkActionPredictorDatabase::Row>* rows =
+      new std::vector<NetworkActionPredictorDatabase::Row>();
+  content::BrowserThread::PostTaskAndReply(
+      content::BrowserThread::DB, FROM_HERE,
+      base::Bind(&NetworkActionPredictorDatabase::GetAllRows, db_, rows),
+      base::Bind(&NetworkActionPredictor::CreateCaches, AsWeakPtr(),
+                 base::Owned(rows)));
+
 }
 
 NetworkActionPredictor::~NetworkActionPredictor() {
+  db_->OnPredictorDestroyed();
 }
 
 // Given a match, return a recommended action.
@@ -108,12 +149,15 @@ NetworkActionPredictor::Action NetworkActionPredictor::RecommendAction(
         confidence = ConservativeAlgorithm(url_row);
       break;
     }
+    case prerender::OMNIBOX_HEURISTIC_EXACT:
+      confidence = ExactAlgorithm(user_text, match);
+      break;
     default:
       NOTREACHED();
       break;
   };
 
-  CHECK(confidence >= 0.0 && confidence <= 1.0);
+  DCHECK(confidence >= 0.0 && confidence <= 1.0);
 
   UMA_HISTOGRAM_COUNTS_100("NetworkActionPredictor.Confidence_" +
                            prerender::GetOmniboxHistogramSuffix(),
@@ -128,11 +172,13 @@ NetworkActionPredictor::Action NetworkActionPredictor::RecommendAction(
     }
   }
 
-  // Downgrade prerender to preconnect if this is a search match.
+  // Downgrade prerender to preconnect if this is a search match or if omnibox
+  // prerendering is disabled.
   if (action == ACTION_PRERENDER &&
-      (match.type == AutocompleteMatch::SEARCH_WHAT_YOU_TYPED ||
+      ((match.type == AutocompleteMatch::SEARCH_WHAT_YOU_TYPED ||
        match.type == AutocompleteMatch::SEARCH_SUGGEST ||
-       match.type == AutocompleteMatch::SEARCH_OTHER_ENGINE)) {
+       match.type == AutocompleteMatch::SEARCH_OTHER_ENGINE) ||
+       !prerender::IsOmniboxEnabled(profile_))) {
     action = ACTION_PRECONNECT;
   }
 
@@ -156,3 +202,250 @@ bool NetworkActionPredictor::IsPreconnectable(const AutocompleteMatch& match) {
       return false;
   }
 }
+
+void NetworkActionPredictor::Observe(
+    int type,
+    const content::NotificationSource& source,
+    const content::NotificationDetails& details) {
+  switch (type) {
+    case chrome::NOTIFICATION_HISTORY_URLS_DELETED: {
+      DCHECK(initialized_);
+      const content::Details<const history::URLsDeletedDetails>
+          urls_deleted_details =
+              content::Details<const history::URLsDeletedDetails>(details);
+      if (urls_deleted_details->all_history)
+        DeleteAllRows();
+      else
+        DeleteRowsWithURLs(urls_deleted_details->urls);
+      break;
+    }
+
+    // This notification does not catch all instances of the user navigating
+    // from the Omnibox, but it does catch the cases where the dropdown is open
+    // and those are the events we're most interested in.
+    case chrome::NOTIFICATION_OMNIBOX_OPENED_URL: {
+      DCHECK(initialized_);
+      AutocompleteLog* log = content::Details<AutocompleteLog>(details).ptr();
+      if (log->text.length() < kMinimumUserTextLength)
+        break;
+
+      const string16 lower_user_text(base::i18n::ToLower(log->text));
+
+      BeginTransaction();
+      for (size_t i = 0; i < log->result.size(); ++i) {
+        const AutocompleteMatch& match(log->result.match_at(i));
+        const DBCacheKey key = { lower_user_text, match.destination_url };
+
+        bool is_hit = (i == log->selected_index);
+
+        NetworkActionPredictorDatabase::Row row;
+        row.user_text = key.user_text;
+        row.url = key.url;
+
+        DBCacheMap::iterator it = db_cache_.find(key);
+        if (it == db_cache_.end()) {
+          row.id = guid::GenerateGUID();
+          row.number_of_hits = is_hit ? 1 : 0;
+          row.number_of_misses = is_hit ? 0 : 1;
+
+          AddRow(key, row);
+        } else {
+          DCHECK(db_id_cache_.find(key) != db_id_cache_.end());
+          row.id = db_id_cache_.find(key)->second;
+          row.number_of_hits = it->second.number_of_hits + (is_hit ? 1 : 0);
+          row.number_of_misses = it->second.number_of_misses + (is_hit ? 0 : 1);
+
+          UpdateRow(it, row);
+        }
+      }
+      CommitTransaction();
+      break;
+    }
+
+    case chrome::NOTIFICATION_HISTORY_LOADED: {
+      DCHECK(!initialized_);
+      TryDeleteOldEntries(content::Details<HistoryService>(details).ptr());
+
+      notification_registrar_.Remove(this,
+                                     chrome::NOTIFICATION_HISTORY_LOADED,
+                                     content::Source<Profile>(profile_));
+      break;
+    }
+
+    default:
+      NOTREACHED() << "Unexpected notification observed.";
+      break;
+  }
+}
+
+void NetworkActionPredictor::DeleteOldIdsFromCaches(
+    history::URLDatabase* url_db,
+    std::vector<NetworkActionPredictorDatabase::Row::Id>* id_list) {
+  CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::UI));
+  DCHECK(url_db);
+  DCHECK(id_list);
+  id_list->clear();
+  for (DBCacheMap::iterator it = db_cache_.begin(); it != db_cache_.end();) {
+    history::URLRow url_row;
+
+    if ((url_db->GetRowForURL(it->first.url, &url_row) == 0) ||
+        ((base::Time::Now() - url_row.last_visit()).InDays() >
+         kMaximumDaysToKeepEntry)) {
+      const DBIdCacheMap::iterator id_it = db_id_cache_.find(it->first);
+      DCHECK(id_it != db_id_cache_.end());
+      id_list->push_back(id_it->second);
+      db_id_cache_.erase(id_it);
+      db_cache_.erase(it++);
+    } else {
+      ++it;
+    }
+  }
+}
+
+void NetworkActionPredictor::DeleteOldEntries(history::URLDatabase* url_db) {
+  CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::UI));
+  DCHECK(!initialized_);
+
+  std::vector<NetworkActionPredictorDatabase::Row::Id> ids_to_delete;
+  DeleteOldIdsFromCaches(url_db, &ids_to_delete);
+
+  content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE,
+      base::Bind(&NetworkActionPredictorDatabase::DeleteRows, db_,
+                 ids_to_delete));
+
+  // Register for notifications and set the |initialized_| flag.
+  notification_registrar_.Add(this, chrome::NOTIFICATION_OMNIBOX_OPENED_URL,
+                              content::Source<Profile>(profile_));
+  notification_registrar_.Add(this, chrome::NOTIFICATION_HISTORY_URLS_DELETED,
+                              content::Source<Profile>(profile_));
+  initialized_ = true;
+}
+
+void NetworkActionPredictor::CreateCaches(
+    std::vector<NetworkActionPredictorDatabase::Row>* rows) {
+  CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::UI));
+  DCHECK(!initialized_);
+  DCHECK(db_cache_.empty());
+  DCHECK(db_id_cache_.empty());
+
+  for (std::vector<NetworkActionPredictorDatabase::Row>::const_iterator it =
+       rows->begin(); it != rows->end(); ++it) {
+    const DBCacheKey key = { it->user_text, it->url };
+    const DBCacheValue value = { it->number_of_hits, it->number_of_misses };
+    db_cache_[key] = value;
+    db_id_cache_[key] = it->id;
+  }
+
+  // If the history service is ready, delete any old or invalid entries.
+  HistoryService* history_service =
+      profile_->GetHistoryService(Profile::EXPLICIT_ACCESS);
+  if (!TryDeleteOldEntries(history_service)) {
+    // Wait for the notification that the history service is ready and the URL
+    // DB is loaded.
+    notification_registrar_.Add(this, chrome::NOTIFICATION_HISTORY_LOADED,
+                                content::Source<Profile>(profile_));
+  }
+}
+
+bool NetworkActionPredictor::TryDeleteOldEntries(HistoryService* service) {
+  if (!service)
+    return false;
+
+  history::URLDatabase* url_db = service->InMemoryDatabase();
+  if (!url_db)
+    return false;
+
+  DeleteOldEntries(url_db);
+  return true;
+}
+
+double NetworkActionPredictor::ExactAlgorithm(
+    const string16& user_text,
+    const AutocompleteMatch& match) const {
+  const DBCacheKey key = { user_text, match.destination_url };
+  const DBCacheMap::const_iterator iter = db_cache_.find(key);
+
+  if (iter == db_cache_.end())
+    return 0.0;
+
+  const DBCacheValue& value = iter->second;
+  if (value.number_of_hits < kMinimumNumberOfHits)
+    return 0.0;
+
+  return static_cast<double>(value.number_of_hits) /
+      (value.number_of_hits + value.number_of_misses);
+}
+
+void NetworkActionPredictor::AddRow(
+    const DBCacheKey& key,
+    const NetworkActionPredictorDatabase::Row& row) {
+  if (!initialized_)
+    return;
+
+  DBCacheValue value = { row.number_of_hits, row.number_of_misses };
+  db_cache_[key] = value;
+  db_id_cache_[key] = row.id;
+  content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE,
+      base::Bind(&NetworkActionPredictorDatabase::AddRow, db_, row));
+}
+
+void NetworkActionPredictor::UpdateRow(
+    DBCacheMap::iterator it,
+    const NetworkActionPredictorDatabase::Row& row) {
+  if (!initialized_)
+    return;
+
+  DCHECK(it != db_cache_.end());
+  it->second.number_of_hits = row.number_of_hits;
+  it->second.number_of_misses = row.number_of_misses;
+  content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE,
+      base::Bind(&NetworkActionPredictorDatabase::UpdateRow, db_, row));
+}
+
+void NetworkActionPredictor::DeleteAllRows() {
+  if (!initialized_)
+    return;
+
+  db_cache_.clear();
+  db_id_cache_.clear();
+  content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE,
+      base::Bind(&NetworkActionPredictorDatabase::DeleteAllRows, db_));
+}
+
+void NetworkActionPredictor::DeleteRowsWithURLs(const std::set<GURL>& urls) {
+  if (!initialized_)
+    return;
+
+  std::vector<NetworkActionPredictorDatabase::Row::Id> id_list;
+
+  for (DBCacheMap::iterator it = db_cache_.begin(); it != db_cache_.end();) {
+    if (urls.find(it->first.url) != urls.end()) {
+      const DBIdCacheMap::iterator id_it = db_id_cache_.find(it->first);
+      DCHECK(id_it != db_id_cache_.end());
+      id_list.push_back(id_it->second);
+      db_id_cache_.erase(id_it);
+      db_cache_.erase(it++);
+    } else {
+      ++it;
+    }
+  }
+
+  content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE,
+      base::Bind(&NetworkActionPredictorDatabase::DeleteRows, db_, id_list));
+}
+
+void NetworkActionPredictor::BeginTransaction() {
+  if (!initialized_)
+    return;
+
+  content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE,
+      base::Bind(&NetworkActionPredictorDatabase::BeginTransaction, db_));
+}
+
+void NetworkActionPredictor::CommitTransaction() {
+  if (!initialized_)
+    return;
+
+  content::BrowserThread::PostTask(content::BrowserThread::DB, FROM_HERE,
+      base::Bind(&NetworkActionPredictorDatabase::CommitTransaction, db_));
+}
diff --git a/chrome/browser/autocomplete/network_action_predictor.h b/chrome/browser/autocomplete/network_action_predictor.h
index 5be8597..60d710a 100644
--- a/chrome/browser/autocomplete/network_action_predictor.h
+++ b/chrome/browser/autocomplete/network_action_predictor.h
@@ -6,14 +6,36 @@
 #define CHROME_BROWSER_AUTOCOMPLETE_NETWORK_ACTION_PREDICTOR_H_
 #pragma once
 
+#include <map>
+
+#include "base/gtest_prod_util.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/memory/weak_ptr.h"
 #include "base/string16.h"
+#include "chrome/browser/autocomplete/network_action_predictor_database.h"
+#include "content/public/browser/notification_observer.h"
+#include "content/public/browser/notification_registrar.h"
+#include "googleurl/src/gurl.h"
 
 struct AutocompleteMatch;
+class HistoryService;
 class Profile;
 
+namespace history {
+class URLDatabase;
+}
+
 // This class is responsible for determining the correct predictive network
-// action to take given for a given AutocompleteMatch and entered text.
-class NetworkActionPredictor {
+// action to take given for a given AutocompleteMatch and entered text. it uses
+// a NetworkActionPredictorDatabase accessed asynchronously on the DB thread to
+// permanently store the data used to make predictions, and keeps local caches
+// of that data to be able to make predictions synchronously on the UI thread
+// where it lives. It can be accessed as a weak pointer so that it can safely
+// use PostTaskAndReply without fear of crashes if it is destroyed before the
+// reply triggers. This is necessary during initialization.
+class NetworkActionPredictor
+    : public content::NotificationObserver,
+      public base::SupportsWeakPtr<NetworkActionPredictor> {
  public:
   enum Action {
     ACTION_PRERENDER = 0,
@@ -39,7 +61,91 @@ class NetworkActionPredictor {
   static bool IsPreconnectable(const AutocompleteMatch& match);
 
  private:
+  friend class NetworkActionPredictorTest;
+
+  struct DBCacheKey {
+    string16 user_text;
+    GURL url;
+
+    bool operator<(const DBCacheKey& rhs) const {
+      return (user_text != rhs.user_text) ?
+          (user_text < rhs.user_text) :  (url < rhs.url);
+    }
+
+    bool operator==(const DBCacheKey& rhs) const {
+      return (user_text == rhs.user_text) && (url == rhs.url);
+    }
+  };
+
+  struct DBCacheValue {
+    int number_of_hits;
+    int number_of_misses;
+  };
+
+  typedef std::map<DBCacheKey, DBCacheValue> DBCacheMap;
+  typedef std::map<DBCacheKey, NetworkActionPredictorDatabase::Row::Id>
+      DBIdCacheMap;
+
+  static const int kMaximumDaysToKeepEntry;
+
+  // NotificationObserver
+  virtual void Observe(int type,
+                       const content::NotificationSource& source,
+                       const content::NotificationDetails& details) OVERRIDE;
+
+  // Deletes any old or invalid entries from the local caches. |url_db| and
+  // |id_list| must not be NULL. Every row id deleted will be added to id_list.
+  void DeleteOldIdsFromCaches(
+      history::URLDatabase* url_db,
+      std::vector<NetworkActionPredictorDatabase::Row::Id>* id_list);
+
+  // Called to delete any old or invalid entries from the database. Called after
+  // the local caches are created once the history service is available.
+  void DeleteOldEntries(history::URLDatabase* url_db);
+
+  // Called to populate the local caches. This also calls DeleteOldEntries
+  // if the history service is available, or registers for the notification of
+  // it becoming available.
+  void CreateCaches(
+      std::vector<NetworkActionPredictorDatabase::Row>* row_buffer);
+
+  // Attempts to call DeleteOldEntries if the in-memory database has been loaded
+  // by |service|. Returns success as a boolean.
+  bool TryDeleteOldEntries(HistoryService* service);
+
+  // Uses local caches to calculate an exact percentage prediction that the user
+  // will take a particular match given what they have typed.
+  double ExactAlgorithm(const string16& user_text,
+                        const AutocompleteMatch& match) const;
+
+  // Adds a row to the database and caches.
+  void AddRow(const DBCacheKey& key,
+              const NetworkActionPredictorDatabase::Row& row);
+
+  // Updates a row in the database and the caches.
+  void UpdateRow(DBCacheMap::iterator it,
+                 const NetworkActionPredictorDatabase::Row& row);
+
+  // Removes all rows from the database and caches.
+  void DeleteAllRows();
+
+  // Removes rows from the database and caches that contain a URL in |urls|.
+  void DeleteRowsWithURLs(const std::set<GURL>& urls);
+
+  // Used to batch operations on the database.
+  void BeginTransaction();
+  void CommitTransaction();
+
   Profile* profile_;
+  scoped_refptr<NetworkActionPredictorDatabase> db_;
+  content::NotificationRegistrar notification_registrar_;
+
+  DBCacheMap db_cache_;
+  DBIdCacheMap db_id_cache_;
+
+  bool initialized_;
+
+  DISALLOW_COPY_AND_ASSIGN(NetworkActionPredictor);
 };
 
 #endif  // CHROME_BROWSER_AUTOCOMPLETE_NETWORK_ACTION_PREDICTOR_H_
diff --git a/chrome/browser/autocomplete/network_action_predictor_database.cc b/chrome/browser/autocomplete/network_action_predictor_database.cc
new file mode 100644
index 0000000..09b34fb
--- /dev/null
+++ b/chrome/browser/autocomplete/network_action_predictor_database.cc
@@ -0,0 +1,261 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "chrome/browser/autocomplete/network_action_predictor_database.h"
+
+#include "base/bind.h"
+#include "base/file_util.h"
+#include "base/logging.h"
+#include "base/metrics/histogram.h"
+#include "base/stringprintf.h"
+#include "base/utf_string_conversions.h"
+#include "chrome/browser/profiles/profile.h"
+#include "chrome/common/guid.h"
+#include "content/public/browser/browser_thread.h"
+#include "sql/statement.h"
+
+namespace {
+
+const char kNetworkActionPredictorTableName[] = "network_action_predictor";
+const FilePath::CharType kNetworkActionPredictorDatabaseName[] =
+    FILE_PATH_LITERAL("Network Action Predictor");
+
+// The maximum length allowed for strings in the database.
+const size_t kMaxDataLength = 2048;
+
+void BindRowToStatement(const NetworkActionPredictorDatabase::Row& row,
+                        sql::Statement* statement) {
+  DCHECK(guid::IsValidGUID(row.id));
+  statement->BindString(0, row.id);
+  statement->BindString16(1, row.user_text.substr(0, kMaxDataLength));
+  statement->BindString(2, row.url.spec().substr(0, kMaxDataLength));
+  statement->BindInt(3, row.number_of_hits);
+  statement->BindInt(4, row.number_of_misses);
+}
+
+bool StepAndInitializeRow(sql::Statement* statement,
+                          NetworkActionPredictorDatabase::Row* row) {
+  if (!statement->Step())
+    return false;
+
+  row->id = statement->ColumnString(0);
+  row->user_text = statement->ColumnString16(1);
+  row->url = GURL(statement->ColumnString(2));
+  row->number_of_hits = statement->ColumnInt(3);
+  row->number_of_misses = statement->ColumnInt(4);
+  return true;
+}
+
+void LogDatabaseStats(const FilePath& db_path, sql::Connection* db) {
+  int64 db_size;
+  bool success = file_util::GetFileSize(db_path, &db_size);
+  DCHECK(success) << "Failed to get file size for " << db_path.value();
+  UMA_HISTOGRAM_MEMORY_KB("NetworkActionPredictor.DatabaseSizeKB",
+                          static_cast<int>(db_size / 1024));
+
+  sql::Statement count_statement(db->GetUniqueStatement(
+      base::StringPrintf("SELECT count(id) FROM %s",
+                         kNetworkActionPredictorTableName).c_str()));
+  if (!count_statement || !count_statement.Step())
+    return;
+  UMA_HISTOGRAM_COUNTS("NetworkActionPredictor.DatabaseRowCount",
+                       count_statement.ColumnInt(0));
+}
+
+}
+
+NetworkActionPredictorDatabase::Row::Row() {
+}
+
+NetworkActionPredictorDatabase::Row::Row(const Row::Id& id,
+                                         const string16& user_text,
+                                         const GURL& url,
+                                         int number_of_hits,
+                                         int number_of_misses)
+    : id(id),
+      user_text(user_text),
+      url(url),
+      number_of_hits(number_of_hits),
+      number_of_misses(number_of_misses) {
+}
+
+NetworkActionPredictorDatabase::NetworkActionPredictorDatabase(Profile* profile)
+    : db_path_(profile->GetPath().Append(kNetworkActionPredictorDatabaseName)) {
+}
+
+NetworkActionPredictorDatabase::~NetworkActionPredictorDatabase() {
+}
+
+void NetworkActionPredictorDatabase::Initialize() {
+  CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::DB));
+  CHECK(!canceled_.IsSet());
+  db_.set_exclusive_locking();
+  if (!db_.Open(db_path_)) {
+    canceled_.Set();
+    return;
+  }
+
+  if (!db_.DoesTableExist(kNetworkActionPredictorTableName))
+    CreateTable();
+
+  LogDatabaseStats(db_path_, &db_);
+}
+
+void NetworkActionPredictorDatabase::GetRow(const Row::Id& id, Row* row) {
+  CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::DB));
+
+  if (canceled_.IsSet())
+    return;
+
+  sql::Statement statement(db_.GetCachedStatement(SQL_FROM_HERE,
+      base::StringPrintf(
+          "SELECT * FROM %s WHERE id=?",
+          kNetworkActionPredictorTableName).c_str()));
+  DCHECK(statement);
+
+  statement.BindString(0, id);
+
+  bool success = StepAndInitializeRow(&statement, row);
+  DCHECK(success) << "Failed to get row " << id << " from "
+                  << kNetworkActionPredictorTableName;
+}
+
+void NetworkActionPredictorDatabase::GetAllRows(
+    std::vector<NetworkActionPredictorDatabase::Row>* row_buffer) {
+  CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::DB));
+  CHECK(row_buffer);
+  row_buffer->clear();
+
+  if (canceled_.IsSet())
+    return;
+
+  sql::Statement statement(db_.GetCachedStatement(SQL_FROM_HERE,
+      base::StringPrintf(
+          "SELECT * FROM %s", kNetworkActionPredictorTableName).c_str()));
+  DCHECK(statement);
+
+  Row row;
+  while (StepAndInitializeRow(&statement, &row))
+    row_buffer->push_back(row);
+}
+
+void NetworkActionPredictorDatabase::AddRow(
+    const NetworkActionPredictorDatabase::Row& row) {
+  CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::DB));
+
+  if (canceled_.IsSet())
+    return;
+
+  sql::Statement statement(db_.GetCachedStatement(SQL_FROM_HERE,
+      base::StringPrintf(
+          "INSERT INTO %s "
+          "(id, user_text, url, number_of_hits, number_of_misses) "
+          "VALUES (?,?,?,?,?)", kNetworkActionPredictorTableName).c_str()));
+  DCHECK(statement);
+
+  BindRowToStatement(row, &statement);
+
+  bool success = statement.Run();
+  DCHECK(success) << "Failed to insert row " << row.id << " into "
+                  << kNetworkActionPredictorTableName;
+}
+
+void NetworkActionPredictorDatabase::UpdateRow(
+    const NetworkActionPredictorDatabase::Row& row) {
+  CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::DB));
+
+  if (canceled_.IsSet())
+    return;
+
+  sql::Statement statement(db_.GetCachedStatement(SQL_FROM_HERE,
+      base::StringPrintf(
+          "UPDATE %s "
+          "SET id=?, user_text=?, url=?, number_of_hits=?, number_of_misses=? "
+          "WHERE id=?1", kNetworkActionPredictorTableName).c_str()));
+  DCHECK(statement);
+
+  BindRowToStatement(row, &statement);
+
+  statement.Run();
+  DCHECK_GT(db_.GetLastChangeCount(), 0);
+}
+
+void NetworkActionPredictorDatabase::DeleteRow(const Row::Id& id) {
+  CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::DB));
+
+  if (canceled_.IsSet())
+    return;
+
+  DeleteRows(std::vector<Row::Id>(1, id));
+}
+
+void NetworkActionPredictorDatabase::DeleteRows(
+    const std::vector<Row::Id>& id_list) {
+  CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::DB));
+
+  if (canceled_.IsSet())
+    return;
+
+  sql::Statement statement(db_.GetUniqueStatement(base::StringPrintf(
+          "DELETE FROM %s WHERE id=?",
+          kNetworkActionPredictorTableName).c_str()));
+  DCHECK(statement);
+
+  db_.BeginTransaction();
+  for (std::vector<Row::Id>::const_iterator it = id_list.begin();
+       it != id_list.end(); ++it) {
+    statement.BindString(0, *it);
+    statement.Run();
+    statement.Reset();
+  }
+  db_.CommitTransaction();
+}
+
+void NetworkActionPredictorDatabase::DeleteAllRows() {
+  CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::DB));
+
+  if (canceled_.IsSet())
+    return;
+
+  sql::Statement statement(db_.GetCachedStatement(SQL_FROM_HERE,
+      base::StringPrintf("DELETE FROM %s",
+                         kNetworkActionPredictorTableName).c_str()));
+  DCHECK(statement);
+
+  statement.Run();
+}
+
+void NetworkActionPredictorDatabase::BeginTransaction() {
+  CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::DB));
+
+  if (canceled_.IsSet())
+    return;
+
+  db_.BeginTransaction();
+}
+
+void NetworkActionPredictorDatabase::CommitTransaction() {
+  CHECK(content::BrowserThread::CurrentlyOn(content::BrowserThread::DB));
+
+  if (canceled_.IsSet())
+    return;
+
+  db_.CommitTransaction();
+}
+
+void NetworkActionPredictorDatabase::OnPredictorDestroyed() {
+  canceled_.Set();
+}
+
+void NetworkActionPredictorDatabase::CreateTable() {
+  bool success = db_.Execute(base::StringPrintf(
+      "CREATE TABLE %s ( "
+      "id TEXT PRIMARY KEY, "
+      "user_text TEXT, "
+      "url TEXT, "
+      "number_of_hits INTEGER, "
+      "number_of_misses INTEGER)", kNetworkActionPredictorTableName).c_str());
+  DCHECK(success) << "Failed to create " << kNetworkActionPredictorTableName
+                  << " table.";
+}
diff --git a/chrome/browser/autocomplete/network_action_predictor_database.h b/chrome/browser/autocomplete/network_action_predictor_database.h
new file mode 100644
index 0000000..4ffdf43
--- /dev/null
+++ b/chrome/browser/autocomplete/network_action_predictor_database.h
@@ -0,0 +1,105 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CHROME_BROWSER_AUTOCOMPLETE_NETWORK_ACTION_PREDICTOR_DATABASE_H_
+#define CHROME_BROWSER_AUTOCOMPLETE_NETWORK_ACTION_PREDICTOR_DATABASE_H_
+#pragma once
+
+#include <ostream>
+#include <string>
+#include <vector>
+
+#include "base/file_path.h"
+#include "base/gtest_prod_util.h"
+#include "base/memory/ref_counted.h"
+#include "base/string16.h"
+#include "base/synchronization/cancellation_flag.h"
+#include "googleurl/src/gurl.h"
+#include "sql/connection.h"
+
+class Profile;
+
+// This manages the network action predictor table within the SQLite database
+// passed in to the constructor. It expects the following scheme:
+//
+// network_action_predictor
+//   id                 A unique id.
+//   user_text          What the user typed.
+//   url                The URL of the entry.
+//   number_of_hits     Number of times the entry was shown to the user and
+//                      selected.
+//   number_of_misses   Number of times the entry was shown to the user but not
+//                      selected.
+//
+// Ref-counted as it is created and destroyed on a different thread to the DB
+// thread that is required for all methods performing database access.
+class NetworkActionPredictorDatabase
+    : public base::RefCountedThreadSafe<NetworkActionPredictorDatabase> {
+ public:
+  struct Row {
+    // TODO(dominich): Make this 64-bit integer as an optimization. This
+    // requires some investigation into how to make sure the id is unique for
+    // each user_text/url pair.
+    // http://crbug.com/102020
+    typedef std::string Id;
+
+    Row();
+
+    // Only used by unit tests.
+    Row(const Id& id,
+        const string16& user_text,
+        const GURL& url,
+        int number_of_hits,
+        int number_of_misses);
+
+    Id id;
+    string16 user_text;
+    GURL url;
+    int number_of_hits;
+    int number_of_misses;
+  };
+
+  explicit NetworkActionPredictorDatabase(Profile* profile);
+
+  // Opens the database file from the profile path. Separated from the
+  // constructor to ease construction/destruction of this object on one thread
+  // but database access on the DB thread.
+  void Initialize();
+
+  void GetRow(const Row::Id& id, Row* row);
+  void GetAllRows(std::vector<Row>* row_buffer);
+
+  void AddRow(const Row& row);
+  void UpdateRow(const Row& row);
+  void DeleteRow(const Row::Id& id);
+  void DeleteRows(const std::vector<Row::Id>& id_list);
+  void DeleteAllRows();
+
+  // For batching database operations.
+  void BeginTransaction();
+  void CommitTransaction();
+
+  void OnPredictorDestroyed();
+
+ private:
+  friend class NetworkActionPredictorDatabaseTest;
+  friend class base::RefCountedThreadSafe<NetworkActionPredictorDatabase>;
+  virtual ~NetworkActionPredictorDatabase();
+
+  void CreateTable();
+
+  // TODO(dominich): Consider adding this table to one of the history databases.
+  // In memory is currently used, but adding to the on-disk visits database
+  // would allow DeleteOldEntries to be cheaper through use of a join.
+  FilePath db_path_;
+  sql::Connection db_;
+
+  // Set when the NetworkActionPredictor is destroyed so we can cancel any
+  // posted database requests.
+  base::CancellationFlag canceled_;
+
+  DISALLOW_COPY_AND_ASSIGN(NetworkActionPredictorDatabase);
+};
+
+#endif  // CHROME_BROWSER_AUTOCOMPLETE_NETWORK_ACTION_PREDICTOR_DATABASE_H_
diff --git a/chrome/browser/autocomplete/network_action_predictor_database_unittest.cc b/chrome/browser/autocomplete/network_action_predictor_database_unittest.cc
new file mode 100644
index 0000000..b4b0837
--- /dev/null
+++ b/chrome/browser/autocomplete/network_action_predictor_database_unittest.cc
@@ -0,0 +1,233 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <vector>
+
+#include "base/time.h"
+#include "base/utf_string_conversions.h"
+#include "chrome/browser/autocomplete/network_action_predictor_database.h"
+#include "chrome/test/base/testing_profile.h"
+#include "content/test/test_browser_thread.h"
+#include "sql/statement.h"
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+using base::Time;
+using base::TimeDelta;
+using content::BrowserThread;
+
+namespace {
+
+struct NetworkActionPredictorDatabase::Row test_db[] = {
+  NetworkActionPredictorDatabase::Row(
+      "BD85DBA2-8C29-49F9-84AE-48E1E90880DF",
+      ASCIIToUTF16("goog"), GURL("http://www.google.com/"),
+      1, 0),
+  NetworkActionPredictorDatabase::Row(
+      "BD85DBA2-8C29-49F9-84AE-48E1E90880E0",
+      ASCIIToUTF16("slash"), GURL("http://slashdot.org/"),
+      3, 2),
+  NetworkActionPredictorDatabase::Row(
+      "BD85DBA2-8C29-49F9-84AE-48E1E90880E1",
+      ASCIIToUTF16("news"), GURL("http://slashdot.org/"),
+      0, 1),
+};
+
+}  // end namespace
+
+class NetworkActionPredictorDatabaseTest : public testing::Test {
+ public:
+  NetworkActionPredictorDatabaseTest();
+  virtual ~NetworkActionPredictorDatabaseTest();
+
+  virtual void SetUp();
+  virtual void TearDown();
+
+  size_t CountRecords() const;
+
+  void AddAll();
+
+  bool RowsAreEqual(const NetworkActionPredictorDatabase::Row& lhs,
+                    const NetworkActionPredictorDatabase::Row& rhs) const;
+
+  TestingProfile* profile() { return &profile_; }
+
+ protected:
+
+  // Test functions that can be run against this text fixture or
+  // NetworkActionPredictorDatabaseReopenTest that inherits from this.
+  void TestAddRow();
+  void TestGetRow();
+  void TestUpdateRow();
+  void TestDeleteRow();
+  void TestDeleteRows();
+  void TestDeleteAllRows();
+
+ private:
+  TestingProfile profile_;
+  scoped_refptr<NetworkActionPredictorDatabase> db_;
+  MessageLoop loop_;
+  content::TestBrowserThread db_thread_;
+};
+
+class NetworkActionPredictorDatabaseReopenTest
+    : public NetworkActionPredictorDatabaseTest {
+ public:
+  virtual void SetUp() {
+    // By calling SetUp twice, we make sure that the table already exists for
+    // this fixture.
+    NetworkActionPredictorDatabaseTest::SetUp();
+    NetworkActionPredictorDatabaseTest::TearDown();
+    NetworkActionPredictorDatabaseTest::SetUp();
+  }
+};
+
+NetworkActionPredictorDatabaseTest::NetworkActionPredictorDatabaseTest()
+    : loop_(MessageLoop::TYPE_DEFAULT),
+      db_thread_(BrowserThread::DB, &loop_) {
+}
+
+NetworkActionPredictorDatabaseTest::~NetworkActionPredictorDatabaseTest() {
+}
+
+void NetworkActionPredictorDatabaseTest::SetUp() {
+  db_ = new NetworkActionPredictorDatabase(&profile_);
+  db_->Initialize();
+}
+
+void NetworkActionPredictorDatabaseTest::TearDown() {
+  db_ = NULL;
+}
+
+size_t NetworkActionPredictorDatabaseTest::CountRecords() const {
+  sql::Statement s(db_->db_.GetUniqueStatement(
+      "SELECT count(*) FROM network_action_predictor"));
+  EXPECT_TRUE(s.Step());
+  return static_cast<size_t>(s.ColumnInt(0));
+}
+
+void NetworkActionPredictorDatabaseTest::AddAll() {
+  for (size_t i = 0; i < arraysize(test_db); ++i)
+    db_->AddRow(test_db[i]);
+
+  EXPECT_EQ(arraysize(test_db), CountRecords());
+}
+
+bool NetworkActionPredictorDatabaseTest::RowsAreEqual(
+    const NetworkActionPredictorDatabase::Row& lhs,
+    const NetworkActionPredictorDatabase::Row& rhs) const {
+  return (lhs.id == rhs.id &&
+          lhs.user_text == rhs.user_text &&
+          lhs.url == rhs.url &&
+          lhs.number_of_hits == rhs.number_of_hits &&
+          lhs.number_of_misses == rhs.number_of_misses);
+}
+
+void NetworkActionPredictorDatabaseTest::TestAddRow() {
+  EXPECT_EQ(0U, CountRecords());
+  db_->AddRow(test_db[0]);
+  EXPECT_EQ(1U, CountRecords());
+  db_->AddRow(test_db[1]);
+  EXPECT_EQ(2U, CountRecords());
+  db_->AddRow(test_db[2]);
+  EXPECT_EQ(3U, CountRecords());
+}
+
+void NetworkActionPredictorDatabaseTest::TestGetRow() {
+  db_->AddRow(test_db[0]);
+  NetworkActionPredictorDatabase::Row row;
+  db_->GetRow(test_db[0].id, &row);
+  EXPECT_TRUE(RowsAreEqual(test_db[0], row))
+      << "Expected: Row with id " << test_db[0].id << "\n"
+      << "Got:      Row with id " << row.id;
+}
+
+void NetworkActionPredictorDatabaseTest::TestUpdateRow() {
+  AddAll();
+  NetworkActionPredictorDatabase::Row row = test_db[1];
+  row.number_of_hits = row.number_of_hits + 1;
+  db_->UpdateRow(row);
+
+  NetworkActionPredictorDatabase::Row updated_row;
+  db_->GetRow(test_db[1].id, &updated_row);
+
+  EXPECT_TRUE(RowsAreEqual(row, updated_row))
+      << "Expected: Row with id " << row.id << "\n"
+      << "Got:      Row with id " << updated_row.id;
+}
+
+void NetworkActionPredictorDatabaseTest::TestDeleteRow() {
+  AddAll();
+  db_->DeleteRow(test_db[2].id);
+  EXPECT_EQ(arraysize(test_db) - 1, CountRecords());
+}
+
+void NetworkActionPredictorDatabaseTest::TestDeleteRows() {
+  AddAll();
+  std::vector<NetworkActionPredictorDatabase::Row::Id> id_list;
+  id_list.push_back(test_db[0].id);
+  id_list.push_back(test_db[2].id);
+  db_->DeleteRows(id_list);
+  EXPECT_EQ(arraysize(test_db) - 2, CountRecords());
+
+  NetworkActionPredictorDatabase::Row row;
+  db_->GetRow(test_db[1].id, &row);
+  EXPECT_TRUE(RowsAreEqual(test_db[1], row));
+}
+
+void NetworkActionPredictorDatabaseTest::TestDeleteAllRows() {
+  AddAll();
+  db_->DeleteAllRows();
+  EXPECT_EQ(0U, CountRecords());
+}
+
+// NetworkActionPredictorDatabaseTest tests
+TEST_F(NetworkActionPredictorDatabaseTest, AddRow) {
+  TestAddRow();
+}
+
+TEST_F(NetworkActionPredictorDatabaseTest, GetRow) {
+  TestGetRow();
+}
+
+TEST_F(NetworkActionPredictorDatabaseTest, UpdateRow) {
+  TestUpdateRow();
+}
+
+TEST_F(NetworkActionPredictorDatabaseTest, DeleteRow) {
+  TestDeleteRow();
+}
+
+TEST_F(NetworkActionPredictorDatabaseTest, DeleteRows) {
+  TestDeleteRows();
+}
+
+TEST_F(NetworkActionPredictorDatabaseTest, DeleteAllRows) {
+  TestDeleteAllRows();
+}
+
+// NetworkActionPredictorDatabaseReopenTest tests
+TEST_F(NetworkActionPredictorDatabaseReopenTest, AddRow) {
+  TestAddRow();
+}
+
+TEST_F(NetworkActionPredictorDatabaseReopenTest, GetRow) {
+  TestGetRow();
+}
+
+TEST_F(NetworkActionPredictorDatabaseReopenTest, UpdateRow) {
+  TestUpdateRow();
+}
+
+TEST_F(NetworkActionPredictorDatabaseReopenTest, DeleteRow) {
+  TestDeleteRow();
+}
+
+TEST_F(NetworkActionPredictorDatabaseReopenTest, DeleteRows) {
+  TestDeleteRows();
+}
+
+TEST_F(NetworkActionPredictorDatabaseReopenTest, DeleteAllRows) {
+  TestDeleteAllRows();
+}
diff --git a/chrome/browser/autocomplete/network_action_predictor_unittest.cc b/chrome/browser/autocomplete/network_action_predictor_unittest.cc
index 9bbaa05..5f6d8e1 100644
--- a/chrome/browser/autocomplete/network_action_predictor_unittest.cc
+++ b/chrome/browser/autocomplete/network_action_predictor_unittest.cc
@@ -4,12 +4,19 @@
 
 #include "chrome/browser/autocomplete/network_action_predictor.h"
 
+#include "base/command_line.h"
+#include "base/memory/ref_counted.h"
 #include "base/message_loop.h"
+#include "base/string_util.h"
 #include "base/time.h"
 #include "base/utf_string_conversions.h"
 #include "chrome/browser/autocomplete/autocomplete_match.h"
 #include "chrome/browser/history/history.h"
+#include "chrome/browser/history/in_memory_database.h"
 #include "chrome/browser/history/url_database.h"
+#include "chrome/browser/prerender/prerender_field_trial.h"
+#include "chrome/common/chrome_switches.h"
+#include "chrome/common/guid.h"
 #include "chrome/test/base/testing_profile.h"
 #include "content/test/test_browser_thread.h"
 #include "testing/gtest/include/gtest/gtest.h"
@@ -18,49 +25,53 @@ using content::BrowserThread;
 
 namespace {
 
+// TODO(dominich): Set hits/misses to match expected action if the test switches
+// to the Exact Algorithm.
 struct TestUrlInfo {
   GURL url;
   string16 title;
   int typed_count;
   int days_from_now;
   string16 user_text;
+  int number_of_hits;
+  int number_of_misses;
   NetworkActionPredictor::Action expected_action;
 } test_url_db[] = {
   { GURL("http://www.testsite.com/a.html"),
     ASCIIToUTF16("Test - site - just a test"), 1, 1,
-    ASCIIToUTF16("just"),
+    ASCIIToUTF16("just"), 1, 2,
     NetworkActionPredictor::ACTION_PRERENDER },
   { GURL("http://www.testsite.com/b.html"),
     ASCIIToUTF16("Test - site - just a test"), 0, 1,
-    ASCIIToUTF16("just"),
+    ASCIIToUTF16("just"), 0, 0,
     NetworkActionPredictor::ACTION_PRERENDER },
   { GURL("http://www.testsite.com/c.html"),
     ASCIIToUTF16("Test - site - just a test"), 1, 5,
-    ASCIIToUTF16("just"),
+    ASCIIToUTF16("just"), 0, 0,
     NetworkActionPredictor::ACTION_PRECONNECT },
   { GURL("http://www.testsite.com/d.html"),
     ASCIIToUTF16("Test - site - just a test"), 2, 5,
-    ASCIIToUTF16("just"),
+    ASCIIToUTF16("just"), 0, 0,
     NetworkActionPredictor::ACTION_PRERENDER },
   { GURL("http://www.testsite.com/e.html"),
     ASCIIToUTF16("Test - site - just a test"), 1, 8,
-    ASCIIToUTF16("just"),
+    ASCIIToUTF16("just"), 0, 0,
     NetworkActionPredictor::ACTION_PRECONNECT },
   { GURL("http://www.testsite.com/f.html"),
     ASCIIToUTF16("Test - site - just a test"), 4, 8,
-    ASCIIToUTF16("just"),
+    ASCIIToUTF16("just"), 0, 0,
     NetworkActionPredictor::ACTION_PRERENDER },
   { GURL("http://www.testsite.com/g.html"),
     ASCIIToUTF16("Test - site - just a test"), 1, 12,
-    ASCIIToUTF16("just a"),
+    ASCIIToUTF16("just a"), 0, 0,
     NetworkActionPredictor::ACTION_NONE },
   { GURL("http://www.testsite.com/h.html"),
     ASCIIToUTF16("Test - site - just a test"), 2, 21,
-    ASCIIToUTF16("just a test"),
+    ASCIIToUTF16("just a test"), 0, 0,
     NetworkActionPredictor::ACTION_NONE },
   { GURL("http://www.testsite.com/i.html"),
     ASCIIToUTF16("Test - site - just a test"), 3, 28,
-    ASCIIToUTF16("just a test"),
+    ASCIIToUTF16("just a test"), 0, 0,
     NetworkActionPredictor::ACTION_NONE }
 };
 
@@ -71,61 +82,150 @@ class NetworkActionPredictorTest : public testing::Test {
   NetworkActionPredictorTest()
       : loop_(MessageLoop::TYPE_DEFAULT),
         ui_thread_(BrowserThread::UI, &loop_),
+        db_thread_(BrowserThread::DB, &loop_),
         file_thread_(BrowserThread::FILE, &loop_),
-        predictor_(&profile_) {
+        predictor_(new NetworkActionPredictor(&profile_)) {
   }
 
   void SetUp() {
+    CommandLine::ForCurrentProcess()->AppendSwitchASCII(
+        switches::kPrerenderFromOmnibox,
+        switches::kPrerenderFromOmniboxSwitchValueEnabled);
+
+    ASSERT_TRUE(prerender::GetOmniboxHeuristicToUse() ==
+          prerender::OMNIBOX_HEURISTIC_ORIGINAL)
+        << "The heuristic has changed so the expectations need to be updated.";
     profile_.CreateHistoryService(true, false);
     profile_.BlockUntilHistoryProcessesPendingRequests();
 
+    ASSERT_TRUE(predictor_->initialized_);
+    ASSERT_TRUE(db_cache()->empty());
+    ASSERT_TRUE(db_id_cache()->empty());
+  }
+
+  void TearDown() {
+    profile_.DestroyHistoryService();
+  }
+
+ protected:
+  typedef NetworkActionPredictor::DBCacheKey DBCacheKey;
+  typedef NetworkActionPredictor::DBCacheValue DBCacheValue;
+  typedef NetworkActionPredictor::DBCacheMap DBCacheMap;
+  typedef NetworkActionPredictor::DBIdCacheMap DBIdCacheMap;
+
+  void AddAllRowsToHistory() {
+    for (size_t i = 0; i < arraysize(test_url_db); ++i)
+      ASSERT_TRUE(AddRowToHistory(test_url_db[i]));
+  }
+
+  history::URLID AddRowToHistory(const TestUrlInfo& test_row) {
     HistoryService* history =
         profile_.GetHistoryService(Profile::EXPLICIT_ACCESS);
     CHECK(history);
     history::URLDatabase* url_db = history->InMemoryDatabase();
     CHECK(url_db);
 
-    for (size_t i = 0; i < ARRAYSIZE_UNSAFE(test_url_db); ++i) {
-      const base::Time visit_time =
-          base::Time::Now() - base::TimeDelta::FromDays(
-              test_url_db[i].days_from_now);
+    const base::Time visit_time =
+        base::Time::Now() - base::TimeDelta::FromDays(
+            test_row.days_from_now);
+
+    history::URLRow row(test_row.url);
+    row.set_title(test_row.title);
+    row.set_typed_count(test_row.typed_count);
+    row.set_last_visit(visit_time);
 
-      history::URLRow row(test_url_db[i].url);
-      row.set_title(test_url_db[i].title);
-      row.set_typed_count(test_url_db[i].typed_count);
-      row.set_last_visit(visit_time);
+    return url_db->AddURL(row);
+  }
 
-      CHECK(url_db->AddURL(row));
-    }
+  NetworkActionPredictorDatabase::Row CreateRowFromTestUrlInfo(
+      const TestUrlInfo& test_row) const {
+    NetworkActionPredictorDatabase::Row row;
+    row.id = guid::GenerateGUID();
+    row.user_text = test_row.user_text;
+    row.url = test_row.url;
+    row.number_of_hits = test_row.number_of_hits;
+    row.number_of_misses = test_row.number_of_misses;
+    return row;
   }
 
-  const NetworkActionPredictor& predictor() const { return predictor_; }
+  std::string AddRow(const TestUrlInfo& test_row) {
+    NetworkActionPredictor::DBCacheKey key = { test_row.user_text,
+                                               test_row.url };
+    NetworkActionPredictorDatabase::Row row =
+        CreateRowFromTestUrlInfo(test_row);
+    predictor_->AddRow(key, row);
+
+    return row.id;
+  }
+
+  void UpdateRow(NetworkActionPredictor::DBCacheKey key,
+                 const NetworkActionPredictorDatabase::Row& row) {
+    NetworkActionPredictor::DBCacheMap::iterator it =
+        db_cache()->find(key);
+    ASSERT_TRUE(it != db_cache()->end());
+
+    predictor_->UpdateRow(it, row);
+  }
+
+  void DeleteAllRows() {
+    predictor_->DeleteAllRows();
+  }
+
+  void DeleteRowsWithURLs(const std::set<GURL>& urls) {
+    predictor_->DeleteRowsWithURLs(urls);
+  }
+
+  void DeleteOldIdsFromCaches(
+      std::vector<NetworkActionPredictorDatabase::Row::Id>* id_list) {
+    HistoryService* history_service =
+        profile_.GetHistoryService(Profile::EXPLICIT_ACCESS);
+    ASSERT_TRUE(history_service);
+
+    history::URLDatabase* url_db = history_service->InMemoryDatabase();
+    ASSERT_TRUE(url_db);
+
+    predictor_->DeleteOldIdsFromCaches(url_db, id_list);
+  }
+
+  NetworkActionPredictor* predictor() { return predictor_.get(); }
+
+  DBCacheMap* db_cache() { return &predictor_->db_cache_; }
+  DBIdCacheMap* db_id_cache() { return &predictor_->db_id_cache_; }
+
+  static int maximum_days_to_keep_entry() {
+    return NetworkActionPredictor::kMaximumDaysToKeepEntry;
+  }
 
  private:
   MessageLoop loop_;
   content::TestBrowserThread ui_thread_;
+  content::TestBrowserThread db_thread_;
   content::TestBrowserThread file_thread_;
   TestingProfile profile_;
-  NetworkActionPredictor predictor_;
+  scoped_ptr<NetworkActionPredictor> predictor_;
 };
 
 TEST_F(NetworkActionPredictorTest, RecommendActionURL) {
+  ASSERT_NO_FATAL_FAILURE(AddAllRowsToHistory());
+
   AutocompleteMatch match;
   match.type = AutocompleteMatch::HISTORY_URL;
 
   for (size_t i = 0; i < ARRAYSIZE_UNSAFE(test_url_db); ++i) {
     match.destination_url = GURL(test_url_db[i].url);
     EXPECT_EQ(test_url_db[i].expected_action,
-              predictor().RecommendAction(test_url_db[i].user_text, match))
+              predictor()->RecommendAction(test_url_db[i].user_text, match))
         << "Unexpected action for " << match.destination_url;
   }
 }
 
 TEST_F(NetworkActionPredictorTest, RecommendActionSearch) {
+  ASSERT_NO_FATAL_FAILURE(AddAllRowsToHistory());
+
   AutocompleteMatch match;
   match.type = AutocompleteMatch::SEARCH_WHAT_YOU_TYPED;
 
-  for (size_t i = 0; i < ARRAYSIZE_UNSAFE(test_url_db); ++i) {
+  for (size_t i = 0; i < arraysize(test_url_db); ++i) {
     match.destination_url = GURL(test_url_db[i].url);
     const NetworkActionPredictor::Action expected =
         (test_url_db[i].expected_action ==
@@ -134,7 +234,135 @@ TEST_F(NetworkActionPredictorTest, RecommendActionSearch) {
             test_url_db[i].expected_action;
 
     EXPECT_EQ(expected,
-              predictor().RecommendAction(test_url_db[i].user_text, match))
+              predictor()->RecommendAction(test_url_db[i].user_text, match))
         << "Unexpected action for " << match.destination_url;
   }
 }
+
+TEST_F(NetworkActionPredictorTest, AddRow) {
+  // Add a test entry to the predictor.
+  std::string guid = AddRow(test_url_db[0]);
+
+  // Get the data back out of the cache.
+  const DBCacheKey key = { test_url_db[0].user_text, test_url_db[0].url };
+  DBCacheMap::const_iterator it = db_cache()->find(key);
+  EXPECT_TRUE(it != db_cache()->end());
+
+  const DBCacheValue value = { test_url_db[0].number_of_hits,
+                               test_url_db[0].number_of_misses };
+  EXPECT_EQ(value.number_of_hits, it->second.number_of_hits);
+  EXPECT_EQ(value.number_of_misses, it->second.number_of_misses);
+
+  DBIdCacheMap::const_iterator id_it = db_id_cache()->find(key);
+  EXPECT_TRUE(id_it != db_id_cache()->end());
+  EXPECT_EQ(guid, id_it->second);
+}
+
+TEST_F(NetworkActionPredictorTest, UpdateRow) {
+  for (size_t i = 0; i < arraysize(test_url_db); ++i)
+    AddRow(test_url_db[i]);
+
+  EXPECT_EQ(arraysize(test_url_db), db_cache()->size());
+  EXPECT_EQ(arraysize(test_url_db), db_id_cache()->size());
+
+  // Get the data back out of the cache.
+  const DBCacheKey key = { test_url_db[0].user_text, test_url_db[0].url };
+  DBCacheMap::const_iterator it = db_cache()->find(key);
+  EXPECT_TRUE(it != db_cache()->end());
+
+  DBIdCacheMap::const_iterator id_it = db_id_cache()->find(key);
+  EXPECT_TRUE(id_it != db_id_cache()->end());
+
+  NetworkActionPredictorDatabase::Row update_row;
+  update_row.id = id_it->second;
+  update_row.user_text = key.user_text;
+  update_row.url = key.url;
+  update_row.number_of_hits = it->second.number_of_hits + 1;
+  update_row.number_of_misses = it->second.number_of_misses + 2;
+
+  UpdateRow(key, update_row);
+
+  // Get the updated version.
+  DBCacheMap::const_iterator update_it = db_cache()->find(key);
+  EXPECT_TRUE(update_it != db_cache()->end());
+
+  EXPECT_EQ(update_row.number_of_hits, update_it->second.number_of_hits);
+  EXPECT_EQ(update_row.number_of_misses, update_it->second.number_of_misses);
+
+  DBIdCacheMap::const_iterator update_id_it = db_id_cache()->find(key);
+  EXPECT_TRUE(update_id_it != db_id_cache()->end());
+
+  EXPECT_EQ(id_it->second, update_id_it->second);
+}
+
+TEST_F(NetworkActionPredictorTest, DeleteAllRows) {
+  for (size_t i = 0; i < arraysize(test_url_db); ++i)
+    AddRow(test_url_db[i]);
+
+  EXPECT_EQ(arraysize(test_url_db), db_cache()->size());
+  EXPECT_EQ(arraysize(test_url_db), db_id_cache()->size());
+
+  DeleteAllRows();
+
+  EXPECT_TRUE(db_cache()->empty());
+  EXPECT_TRUE(db_id_cache()->empty());
+}
+
+TEST_F(NetworkActionPredictorTest, DeleteRowsWithURLs) {
+  for (size_t i = 0; i < arraysize(test_url_db); ++i)
+    AddRow(test_url_db[i]);
+
+  EXPECT_EQ(arraysize(test_url_db), db_cache()->size());
+  EXPECT_EQ(arraysize(test_url_db), db_id_cache()->size());
+
+  std::set<GURL> urls;
+  for (size_t i = 0; i < 2; ++i)
+    urls.insert(test_url_db[i].url);
+
+  DeleteRowsWithURLs(urls);
+
+  EXPECT_EQ(arraysize(test_url_db) - 2, db_cache()->size());
+  EXPECT_EQ(arraysize(test_url_db) - 2, db_id_cache()->size());
+
+  for (size_t i = 0; i < arraysize(test_url_db); ++i) {
+    DBCacheKey key = { test_url_db[i].user_text, test_url_db[i].url };
+
+    bool deleted = (i < 2);
+    EXPECT_EQ(deleted, db_cache()->find(key) == db_cache()->end());
+    EXPECT_EQ(deleted, db_id_cache()->find(key) == db_id_cache()->end());
+  }
+}
+
+TEST_F(NetworkActionPredictorTest, DeleteOldIdsFromCaches) {
+  std::vector<NetworkActionPredictorDatabase::Row::Id> expected;
+  std::vector<NetworkActionPredictorDatabase::Row::Id> all_ids;
+
+  for (size_t i = 0; i < arraysize(test_url_db); ++i) {
+    std::string row_id = AddRow(test_url_db[i]);
+    all_ids.push_back(row_id);
+
+    bool exclude_url = StartsWithASCII(test_url_db[i].url.path(), "/d", true) ||
+        (test_url_db[i].days_from_now > maximum_days_to_keep_entry());
+
+    if (exclude_url)
+      expected.push_back(row_id);
+    else
+      ASSERT_TRUE(AddRowToHistory(test_url_db[i]));
+  }
+
+  std::vector<NetworkActionPredictorDatabase::Row::Id> id_list;
+  DeleteOldIdsFromCaches(&id_list);
+  EXPECT_EQ(expected.size(), id_list.size());
+  EXPECT_EQ(all_ids.size() - expected.size(), db_cache()->size());
+  EXPECT_EQ(all_ids.size() - expected.size(), db_id_cache()->size());
+
+  for (std::vector<NetworkActionPredictorDatabase::Row::Id>::iterator it =
+       all_ids.begin();
+       it != all_ids.end(); ++it) {
+    bool in_expected =
+        (std::find(expected.begin(), expected.end(), *it) != expected.end());
+    bool in_list =
+        (std::find(id_list.begin(), id_list.end(), *it) != id_list.end());
+    EXPECT_EQ(in_expected, in_list);
+  }
+}
diff --git a/chrome/browser/prerender/prerender_field_trial.cc b/chrome/browser/prerender/prerender_field_trial.cc
index 4956ffa..4c3344e9 100644
--- a/chrome/browser/prerender/prerender_field_trial.cc
+++ b/chrome/browser/prerender/prerender_field_trial.cc
@@ -22,10 +22,12 @@ namespace {
 
 int omnibox_original_group_id = 0;
 int omnibox_conservative_group_id = 0;
+int omnibox_exact_group_id = 0;
 
 const char* kOmniboxHeuristicNames[] = {
   "Original",
   "Conservative",
+  "Exact"
 };
 COMPILE_ASSERT(arraysize(kOmniboxHeuristicNames) == OMNIBOX_HEURISTIC_MAX,
                OmniboxHeuristic_name_count_mismatch);
@@ -170,7 +172,8 @@ void ConfigurePrerenderFromOmnibox() {
   enabled_trial->AppendGroup("OmniboxPrerenderEnabled", kEnabledProbability);
 
   // Field trial to see which heuristic to use.
-  const base::FieldTrial::Probability kConservativeProbability = 50;
+  const base::FieldTrial::Probability kConservativeProbability = 33;
+  const base::FieldTrial::Probability kExactProbability = 33;
   scoped_refptr<base::FieldTrial> heuristic_trial(
       new base::FieldTrial("PrerenderFromOmniboxHeuristic", kDivisor,
                            "OriginalAlgorithm", 2012, 8, 30));
@@ -178,6 +181,8 @@ void ConfigurePrerenderFromOmnibox() {
   omnibox_conservative_group_id =
       heuristic_trial->AppendGroup("ConservativeAlgorithm",
                                    kConservativeProbability);
+  omnibox_exact_group_id =
+      heuristic_trial->AppendGroup("ExactAlgorithm", kExactProbability);
 }
 
 bool IsOmniboxEnabled(Profile* profile) {
@@ -218,6 +223,8 @@ OmniboxHeuristic GetOmniboxHeuristicToUse() {
     return OMNIBOX_HEURISTIC_ORIGINAL;
   if (group == omnibox_conservative_group_id)
     return OMNIBOX_HEURISTIC_CONSERVATIVE;
+  if (group == omnibox_exact_group_id)
+    return OMNIBOX_HEURISTIC_EXACT;
 
   // If we don't have a group just return the original heuristic.
   return OMNIBOX_HEURISTIC_ORIGINAL;
diff --git a/chrome/browser/prerender/prerender_field_trial.h b/chrome/browser/prerender/prerender_field_trial.h
index aafaea1..718a987 100644
--- a/chrome/browser/prerender/prerender_field_trial.h
+++ b/chrome/browser/prerender/prerender_field_trial.h
@@ -15,6 +15,7 @@ namespace prerender {
 enum OmniboxHeuristic {
   OMNIBOX_HEURISTIC_ORIGINAL,
   OMNIBOX_HEURISTIC_CONSERVATIVE,
+  OMNIBOX_HEURISTIC_EXACT,
   OMNIBOX_HEURISTIC_MAX
 };
 
diff --git a/chrome/browser/prerender/prerender_histograms.cc b/chrome/browser/prerender/prerender_histograms.cc
index 8e05739..09d08c3 100644
--- a/chrome/browser/prerender/prerender_histograms.cc
+++ b/chrome/browser/prerender/prerender_histograms.cc
@@ -38,6 +38,10 @@ std::string GetHistogramName(Origin origin, uint8 experiment_id,
       if (experiment_id != kNoExperiment)
         return ComposeHistogramName("wash", name);
       return ComposeHistogramName("omnibox_conservative", name);
+    case ORIGIN_OMNIBOX_EXACT:
+      if (experiment_id != kNoExperiment)
+        return ComposeHistogramName("wash", name);
+      return ComposeHistogramName("omnibox_exact", name);
     case ORIGIN_LINK_REL_PRERENDER:
       if (experiment_id != kNoExperiment)
         return ComposeHistogramName("wash", name);
@@ -97,6 +101,8 @@ std::string GetHistogramName(Origin origin, uint8 experiment_id,
     HISTOGRAM; \
   } else if (origin == ORIGIN_OMNIBOX_CONSERVATIVE) { \
     HISTOGRAM; \
+  } else if (origin == ORIGIN_OMNIBOX_EXACT) { \
+    HISTOGRAM; \
   } else if (experiment != kNoExperiment) { \
     HISTOGRAM; \
   } else { \
diff --git a/chrome/browser/prerender/prerender_manager.cc b/chrome/browser/prerender/prerender_manager.cc
index baa019c..ebce46e 100644
--- a/chrome/browser/prerender/prerender_manager.cc
+++ b/chrome/browser/prerender/prerender_manager.cc
@@ -296,6 +296,10 @@ bool PrerenderManager::AddPrerenderFromOmnibox(
       origin = ORIGIN_OMNIBOX_CONSERVATIVE;
       break;
 
+    case OMNIBOX_HEURISTIC_EXACT:
+      origin = ORIGIN_OMNIBOX_EXACT;
+      break;
+
     default:
       NOTREACHED();
       break;
@@ -332,9 +336,8 @@ bool PrerenderManager::AddPrerender(
 
   GURL url = url_arg;
   GURL alias_url;
-  if (IsControlGroup() && MaybeGetQueryStringBasedAliasURL(url, &alias_url)) {
+  if (IsControlGroup() && MaybeGetQueryStringBasedAliasURL(url, &alias_url))
     url = alias_url;
-  }
 
   if (FindEntry(url))
     return false;
@@ -969,9 +972,20 @@ DictionaryValue* PrerenderManager::GetAsValue() const {
   dict_value->SetBoolean("enabled", enabled_);
   dict_value->SetBoolean("omnibox_enabled", IsOmniboxEnabled(profile_));
   if (IsOmniboxEnabled(profile_)) {
-    dict_value->SetString("omnibox_heuristic",
-        GetOmniboxHeuristicToUse() == OMNIBOX_HEURISTIC_ORIGINAL ?
-            "(original)" : "(conservative)");
+    switch (GetOmniboxHeuristicToUse()) {
+      case OMNIBOX_HEURISTIC_ORIGINAL:
+        dict_value->SetString("omnibox_heuristic", "(original)");
+        break;
+      case OMNIBOX_HEURISTIC_CONSERVATIVE:
+        dict_value->SetString("omnibox_heuristic", "(conservative)");
+        break;
+      case OMNIBOX_HEURISTIC_EXACT:
+        dict_value->SetString("omnibox_heuristic", "(exact)");
+        break;
+      default:
+        NOTREACHED();
+        break;
+    }
   }
   // If prerender is disabled via a flag this method is not even called.
   if (IsControlGroup())
diff --git a/chrome/browser/prerender/prerender_origin.cc b/chrome/browser/prerender/prerender_origin.cc
index c7cb58f..b796fb2 100644
--- a/chrome/browser/prerender/prerender_origin.cc
+++ b/chrome/browser/prerender/prerender_origin.cc
@@ -16,6 +16,7 @@ const char* kOriginNames[] = {
   "Omnibox (original)",
   "GWS Prerender",
   "Omnibox (conservative)",
+  "Omnibox (exact)",
   "Max"
 };
 COMPILE_ASSERT(arraysize(kOriginNames) == ORIGIN_MAX + 1,
diff --git a/chrome/browser/prerender/prerender_origin.h b/chrome/browser/prerender/prerender_origin.h
index 32e6309..0c78ecd 100644
--- a/chrome/browser/prerender/prerender_origin.h
+++ b/chrome/browser/prerender/prerender_origin.h
@@ -14,6 +14,7 @@ enum Origin {
   ORIGIN_OMNIBOX_ORIGINAL = 1,
   ORIGIN_GWS_PRERENDER = 2,
   ORIGIN_OMNIBOX_CONSERVATIVE = 3,
+  ORIGIN_OMNIBOX_EXACT = 4,
   ORIGIN_MAX
 };
 
diff --git a/chrome/browser/profiles/off_the_record_profile_impl.cc b/chrome/browser/profiles/off_the_record_profile_impl.cc
index 8a5be4f..824215f 100644
--- a/chrome/browser/profiles/off_the_record_profile_impl.cc
+++ b/chrome/browser/profiles/off_the_record_profile_impl.cc
@@ -571,6 +571,10 @@ GURL OffTheRecordProfileImpl::GetHomePage() {
   return profile_->GetHomePage();
 }
 
+NetworkActionPredictor* OffTheRecordProfileImpl::GetNetworkActionPredictor() {
+  return NULL;
+}
+
 void OffTheRecordProfileImpl::Observe(int type,
                      const content::NotificationSource& source,
                      const content::NotificationDetails& details) {
diff --git a/chrome/browser/profiles/off_the_record_profile_impl.h b/chrome/browser/profiles/off_the_record_profile_impl.h
index 273238a..a0194c6 100644
--- a/chrome/browser/profiles/off_the_record_profile_impl.h
+++ b/chrome/browser/profiles/off_the_record_profile_impl.h
@@ -129,6 +129,7 @@ class OffTheRecordProfileImpl : public Profile,
   virtual chrome_browser_net::Predictor* GetNetworkPredictor() OVERRIDE;
   virtual void ClearNetworkingHistorySince(base::Time time) OVERRIDE;
   virtual GURL GetHomePage() OVERRIDE;
+  virtual NetworkActionPredictor* GetNetworkActionPredictor() OVERRIDE;
 
   // content::NotificationObserver implementation.
   virtual void Observe(int type,
diff --git a/chrome/browser/profiles/profile.h b/chrome/browser/profiles/profile.h
index 0e3df82..d55f04d 100644
--- a/chrome/browser/profiles/profile.h
+++ b/chrome/browser/profiles/profile.h
@@ -66,6 +66,7 @@ class FindBarState;
 class HistoryService;
 class HostContentSettingsMap;
 class NavigationController;
+class NetworkActionPredictor;
 class PasswordStore;
 class PrefService;
 class ProfileSyncFactory;
@@ -497,6 +498,10 @@ class Profile : public content::BrowserContext {
   // Returns the home page for this profile.
   virtual GURL GetHomePage() = 0;
 
+  // Returns the NetworkActionPredictor used by the Omnibox to decide when to
+  // prerender or prefetch a result.
+  virtual NetworkActionPredictor* GetNetworkActionPredictor() = 0;
+
   std::string GetDebugName();
 
   // Returns whether it is a guest session.
diff --git a/chrome/browser/profiles/profile_impl.cc b/chrome/browser/profiles/profile_impl.cc
index 6343dd2..c6eb3f6 100644
--- a/chrome/browser/profiles/profile_impl.cc
+++ b/chrome/browser/profiles/profile_impl.cc
@@ -16,6 +16,7 @@
 #include "base/string_util.h"
 #include "base/utf_string_conversions.h"
 #include "chrome/browser/autocomplete/autocomplete_classifier.h"
+#include "chrome/browser/autocomplete/network_action_predictor.h"
 #include "chrome/browser/autofill/personal_data_manager.h"
 #include "chrome/browser/background/background_contents_service_factory.h"
 #include "chrome/browser/background/background_mode_manager.h"
@@ -1584,6 +1585,12 @@ GURL ProfileImpl::GetHomePage() {
   return home_page;
 }
 
+NetworkActionPredictor* ProfileImpl::GetNetworkActionPredictor() {
+  if (!network_action_predictor_.get())
+    network_action_predictor_.reset(new NetworkActionPredictor(this));
+  return network_action_predictor_.get();
+}
+
 SpellCheckProfile* ProfileImpl::GetSpellCheckProfile() {
   if (!spellcheck_profile_.get())
     spellcheck_profile_.reset(new SpellCheckProfile(path_));
diff --git a/chrome/browser/profiles/profile_impl.h b/chrome/browser/profiles/profile_impl.h
index d7060fd..482a7a9 100644
--- a/chrome/browser/profiles/profile_impl.h
+++ b/chrome/browser/profiles/profile_impl.h
@@ -130,6 +130,7 @@ class ProfileImpl : public Profile,
   virtual chrome_browser_net::Predictor* GetNetworkPredictor() OVERRIDE;
   virtual void ClearNetworkingHistorySince(base::Time time) OVERRIDE;
   virtual GURL GetHomePage() OVERRIDE;
+  virtual NetworkActionPredictor* GetNetworkActionPredictor() OVERRIDE;
 
 #if defined(OS_CHROMEOS)
   virtual void ChangeAppLocale(const std::string& locale,
@@ -241,6 +242,7 @@ class ProfileImpl : public Profile,
   scoped_refptr<WebKitContext> webkit_context_;
   scoped_refptr<fileapi::FileSystemContext> file_system_context_;
   scoped_refptr<quota::QuotaManager> quota_manager_;
+  scoped_ptr<NetworkActionPredictor> network_action_predictor_;
   bool history_service_created_;
   bool favicon_service_created_;
   bool created_web_data_service_;
diff --git a/chrome/chrome_browser.gypi b/chrome/chrome_browser.gypi
index 923aab6..cb8989e 100644
--- a/chrome/chrome_browser.gypi
+++ b/chrome/chrome_browser.gypi
@@ -118,6 +118,8 @@
         'browser/autocomplete/keyword_provider.h',
         'browser/autocomplete/network_action_predictor.cc',
         'browser/autocomplete/network_action_predictor.h',
+        'browser/autocomplete/network_action_predictor_database.cc',
+        'browser/autocomplete/network_action_predictor_database.h',
         'browser/autocomplete/search_provider.cc',
         'browser/autocomplete/search_provider.h',
         'browser/autocomplete/shortcuts_provider.cc',
diff --git a/chrome/chrome_tests.gypi b/chrome/chrome_tests.gypi
index 6639c68..85bdd44 100644
--- a/chrome/chrome_tests.gypi
+++ b/chrome/chrome_tests.gypi
@@ -1174,6 +1174,7 @@
         'browser/autocomplete/history_url_provider_unittest.cc',
         'browser/autocomplete/keyword_provider_unittest.cc',
         'browser/autocomplete/network_action_predictor_unittest.cc',
+        'browser/autocomplete/network_action_predictor_database_unittest.cc',
         'browser/autocomplete/search_provider_unittest.cc',
         'browser/autocomplete/shortcuts_provider_unittest.cc',
         'browser/autocomplete_history_manager_unittest.cc',
diff --git a/chrome/test/base/testing_profile.cc b/chrome/test/base/testing_profile.cc
index c8eb4bd..7c74334 100644
--- a/chrome/test/base/testing_profile.cc
+++ b/chrome/test/base/testing_profile.cc
@@ -798,6 +798,10 @@ GURL TestingProfile::GetHomePage() {
   return GURL(chrome::kChromeUINewTabURL);
 }
 
+NetworkActionPredictor* TestingProfile::GetNetworkActionPredictor() {
+  return NULL;
+}
+
 PrefService* TestingProfile::GetOffTheRecordPrefs() {
   return NULL;
 }
diff --git a/chrome/test/base/testing_profile.h b/chrome/test/base/testing_profile.h
index bbe73e8..44892a9 100644
--- a/chrome/test/base/testing_profile.h
+++ b/chrome/test/base/testing_profile.h
@@ -284,6 +284,8 @@ class TestingProfile : public Profile {
   virtual chrome_browser_net::Predictor* GetNetworkPredictor();
   virtual void ClearNetworkingHistorySince(base::Time time) OVERRIDE;
   virtual GURL GetHomePage() OVERRIDE;
+  virtual NetworkActionPredictor* GetNetworkActionPredictor() OVERRIDE;
+
   virtual PrefService* GetOffTheRecordPrefs();
 
   // TODO(jam): remove me once webkit_context_unittest.cc doesn't use Profile