Replace FTS in the history_service with a brute force text search.

Replace FTS in the history_service with a brute force text search.

The only remaining user of the text_database full-text-search (FTS) is the
chrome://history page.  The FTS database's index files are large, causing
storage and overhead problems.  This change replaces the history pages
search to use a brute force search over URLs and titles in the History DB (which
is small enough that this gives acceptable performance).

A follow up CL will remove all of the unused FTS and text_database code.

BUG=247417
TEST=Tested searches in history page using a number of different character sets.

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=208068

[rmcilroy, 2013-06-11 16:37:18]

There is still a couple of tests I need to fix up before submitting this, but I
thought I'd put it out there for comments first.

I will follow up with a patch to remove the now unused FTS stuff.

[Scott Hess - ex-Googler, 2013-06-12 17:38:34]

IMHO constructing a query full of REGEXP to use SQLite like this is nasty. 
SQLite has no optimization magic for something like this, it's going to have to
do a full table scan and generically string-process everything.  I bet you could
do just as well with a manual WHERE implementation, something like:
  SELECT <fields> FROM urls WHERE hidden = 0
and your loop like:
  while (s.Step()) {
    if (matcher_fun(query_info, s.ColumnString(url_column),
s.ColumnString(title_column)) {
      // load the row.
    }
  }
with matcher_fun() implemented in terms of break iterator (and query_info being
pre-calculated info so you aren't re-parsing the query all the time).

It wouldn't surprise me greatly to find out that a manual WHERE like above is
actually faster than having SQLite execute the VM code from a giant string of
REGEXP, especially if you can get the UTF8/UTF16 conversions minimized.

https://codereview.chromium.org/16776004/diff/2001/chrome/browser/history/url...
File chrome/browser/history/url_database.cc (right):

https://codereview.chromium.org/16776004/diff/2001/chrome/browser/history/url...
chrome/browser/history/url_database.cc:372: sql::Statement
statement(GetDB().GetUniqueStatement(sql.c_str()));
You may want to reference http://crbug.com/248608 here.  Right now you cannot
use a cached statement, here, but I generally dislike constructed statements
like this, so consider it protection against the future.

[rmcilroy, 2013-06-13 15:32:05]

Thanks for the comments Scott, I agree that the regexp was ugly.  Changed to use
query_parser matching.  PTAL.

https://codereview.chromium.org/16776004/diff/2001/chrome/browser/history/url...
File chrome/browser/history/url_database.cc (right):

https://codereview.chromium.org/16776004/diff/2001/chrome/browser/history/url...
chrome/browser/history/url_database.cc:372: sql::Statement
statement(GetDB().GetUniqueStatement(sql.c_str()));
On 2013/06/12 17:38:34, shess wrote:
> You may want to reference http://crbug.com/248608 here.  Right now you cannot
> use a cached statement, here, but I generally dislike constructed statements
> like this, so consider it protection against the future.

Ack (no longer required).

[Scott Hess - ex-Googler, 2013-06-13 19:45:58]

I think this looks a lot cleaner, at least in the areas where I feel remotely
qualified to even comment.

https://codereview.chromium.org/16776004/diff/8001/chrome/browser/history/his...
File chrome/browser/history/history_backend.cc (right):

https://codereview.chromium.org/16776004/diff/8001/chrome/browser/history/his...
chrome/browser/history/history_backend.cc:1498: static_cast<int>(result->size())
>= options.max_count) {
Indentation.

Also, it might read cleaner to capture a size_t-cast version of max_count above
the loop - you could even set it to std::numeric_limits<size_t>::max() if 0.

https://codereview.chromium.org/16776004/diff/8001/chrome/browser/history/his...
chrome/browser/history/history_backend.cc:1509: URLResult::CompareVisitTime);
It seems like this is sorting by visit time AFTER it has trimmed by max_count,
which seems backwards.  It does put the most-relevant stuff first, but there
could be relevant stuff later on which isn't reached in the first place.  Is
that intentional?

[I see that the FTS version did this.  And I don't understand the manual join
being done here.  So I'm asking just to make sure it was considered.]

https://codereview.chromium.org/16776004/diff/8001/chrome/browser/history/url...
File chrome/browser/history/url_database.cc (right):

https://codereview.chromium.org/16776004/diff/8001/chrome/browser/history/url...
chrome/browser/history/url_database.cc:371: string16 url =
base::i18n::ToLower(UTF8ToUTF16(statement.ColumnString(1)));
Replace UTF8ToUTF16(ColumnString()) with ColumnString16().

https://codereview.chromium.org/16776004/diff/8001/chrome/browser/history/url...
chrome/browser/history/url_database.cc:383: return !results->empty();
If this is your success metric, do you want results->clear() before the loop? 
I'm not entirely sure whether this would be more appropriately "Fill |results|
with the matches" versus "Append matches to |results|", though, in which case
this might not be the right metric.

[rmcilroy, 2013-06-14 12:45:41]

Addressed your comments and also fixed the unit_tests.  This also involved a
couple of modifications to the code (i.e., querying the archived_db as well if
necessary, and limiting the visit_db search by time-range.

https://codereview.chromium.org/16776004/diff/8001/chrome/browser/history/his...
File chrome/browser/history/history_backend.cc (right):

https://codereview.chromium.org/16776004/diff/8001/chrome/browser/history/his...
chrome/browser/history/history_backend.cc:1498: static_cast<int>(result->size())
>= options.max_count) {
On 2013/06/13 19:45:58, shess wrote:
> Indentation.
> 
> Also, it might read cleaner to capture a size_t-cast version of max_count
above
> the loop - you could even set it to std::numeric_limits<size_t>::max() if 0.

Done.

https://codereview.chromium.org/16776004/diff/8001/chrome/browser/history/his...
chrome/browser/history/history_backend.cc:1509: URLResult::CompareVisitTime);
On 2013/06/13 19:45:58, shess wrote:
> It seems like this is sorting by visit time AFTER it has trimmed by max_count,
> which seems backwards.  It does put the most-relevant stuff first, but there
> could be relevant stuff later on which isn't reached in the first place.  Is
> that intentional?
> 
> [I see that the FTS version did this.  And I don't understand the manual join
> being done here.  So I'm asking just to make sure it was considered.]

Good point, it makes more sense to trim after sorting by time. Done.

https://codereview.chromium.org/16776004/diff/8001/chrome/browser/history/url...
File chrome/browser/history/url_database.cc (right):

https://codereview.chromium.org/16776004/diff/8001/chrome/browser/history/url...
chrome/browser/history/url_database.cc:371: string16 url =
base::i18n::ToLower(UTF8ToUTF16(statement.ColumnString(1)));
On 2013/06/13 19:45:58, shess wrote:
> Replace UTF8ToUTF16(ColumnString()) with ColumnString16().

Done.

https://codereview.chromium.org/16776004/diff/8001/chrome/browser/history/url...
chrome/browser/history/url_database.cc:383: return !results->empty();
On 2013/06/13 19:45:58, shess wrote:
> If this is your success metric, do you want results->clear() before the loop? 
> I'm not entirely sure whether this would be more appropriately "Fill |results|
> with the matches" versus "Append matches to |results|", though, in which case
> this might not be the right metric.

Done.

[rmcilroy, 2013-06-17 14:13:14]

Ping?  Brett, do you have any suggestions for this CL?

[brettw, 2013-06-18 23:26:28]

https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/hi...
File chrome/browser/history/history_backend.cc (right):

https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/hi...
chrome/browser/history/history_backend.cc:1117: bool
HistoryBackend::GetVisitsForURLWithOptions(URLID id,
I don't get why this is a function since it looks like you just call it in one
place.

https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/vi...
File chrome/browser/history/visit_database.cc (right):

https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/vi...
chrome/browser/history/visit_database.cc:125: std::set<URLID> found_urls;
You just copied this code from GetVisibleVisitsInRange but in your new code you
query by ASC instead of DESC, and the duplicate management behavior will be
different in these two cases.

When you fix the REMOVE_ALL_DUPLICATES below, this function should probably be
defined to always take a DESC query (and it should specify this ordering in the
header) so the results are consistent.

https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/vi...
chrome/browser/history/visit_database.cc:295: return
FillVisitVectorWithOptions(statement, options, visits);
This is a bit weird for the case where we set REMOVE_ALL_DUPLICATES. It makes a
query for all visits and then steps through them, eliminating all but the first
one as duplicates. Do we need a separate branch for REMOVE_ALL_DUPLICATES?

[rmcilroy, 2013-06-19 10:30:14]

Thanks for the comments Brett - hopefully they are all addressed.

https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/hi...
File chrome/browser/history/history_backend.cc (right):

https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/hi...
chrome/browser/history/history_backend.cc:1117: bool
HistoryBackend::GetVisitsForURLWithOptions(URLID id,
On 2013/06/18 23:26:28, brettw wrote:
> I don't get why this is a function since it looks like you just call it in one
> place.

I was following the pattern of the functions above, but I take your point. Done.

https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/vi...
File chrome/browser/history/visit_database.cc (right):

https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/vi...
chrome/browser/history/visit_database.cc:125: std::set<URLID> found_urls;
On 2013/06/18 23:26:28, brettw wrote:
> You just copied this code from GetVisibleVisitsInRange but in your new code
you
> query by ASC instead of DESC, and the duplicate management behavior will be
> different in these two cases.
> 
> When you fix the REMOVE_ALL_DUPLICATES below, this function should probably be
> defined to always take a DESC query (and it should specify this ordering in
the
> header) so the results are consistent.

Good point.  I've updated the comment to state this should be a DESC query. Not
sure if you wanted any kind of check here in the function?

https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/vi...
chrome/browser/history/visit_database.cc:295: return
FillVisitVectorWithOptions(statement, options, visits);
On 2013/06/18 23:26:28, brettw wrote:
> This is a bit weird for the case where we set REMOVE_ALL_DUPLICATES. It makes
a
> query for all visits and then steps through them, eliminating all but the
first
> one as duplicates. Do we need a separate branch for REMOVE_ALL_DUPLICATES?

Done.

[rmcilroy, 2013-06-20 09:54:25]

On 2013/06/19 10:30:14, Ross Mcilroy wrote:
> Thanks for the comments Brett - hopefully they are all addressed.
> 
>
https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/hi...
> File chrome/browser/history/history_backend.cc (right):
> 
>
https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/hi...
> chrome/browser/history/history_backend.cc:1117: bool
> HistoryBackend::GetVisitsForURLWithOptions(URLID id,
> On 2013/06/18 23:26:28, brettw wrote:
> > I don't get why this is a function since it looks like you just call it in
one
> > place.
> 
> I was following the pattern of the functions above, but I take your point.
Done.
> 
>
https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/vi...
> File chrome/browser/history/visit_database.cc (right):
> 
>
https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/vi...
> chrome/browser/history/visit_database.cc:125: std::set<URLID> found_urls;
> On 2013/06/18 23:26:28, brettw wrote:
> > You just copied this code from GetVisibleVisitsInRange but in your new code
> you
> > query by ASC instead of DESC, and the duplicate management behavior will be
> > different in these two cases.
> > 
> > When you fix the REMOVE_ALL_DUPLICATES below, this function should probably
be
> > defined to always take a DESC query (and it should specify this ordering in
> the
> > header) so the results are consistent.
> 
> Good point.  I've updated the comment to state this should be a DESC query.
Not
> sure if you wanted any kind of check here in the function?
> 
>
https://codereview.chromium.org/16776004/diff/13001/chrome/browser/history/vi...
> chrome/browser/history/visit_database.cc:295: return
> FillVisitVectorWithOptions(statement, options, visits);
> On 2013/06/18 23:26:28, brettw wrote:
> > This is a bit weird for the case where we set REMOVE_ALL_DUPLICATES. It
makes
> a
> > query for all visits and then steps through them, eliminating all but the
> first
> > one as duplicates. Do we need a separate branch for REMOVE_ALL_DUPLICATES?
> 
> Done.

Ping?  

It would be great if this could go in before the M29 branch cut, so we can see
if there are any adverse reactions to it during beta and, if necessary, restore
FTS (e.g., waiting till M30 to fully remove the FTS text database).

[Scott Hess - ex-Googler, 2013-06-20 19:50:21]

overall lgtm, but Brett probably can speak better to whether it's wired into
things appropriately.  I don't have a very complete mental model of the history
modules.

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
File chrome/browser/history/history_backend.cc (right):

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
chrome/browser/history/history_backend.cc:1438: QueryResults* result) {
Do you think there would be any value to histogramming timing information for
this function?  Not breaking it down, but just getting the overall cost.

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
File chrome/browser/history/history_querying_unittest.cc (left):

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
chrome/browser/history/history_querying_unittest.cc:361: options.body_only =
true;
Is |body_only| still present as an option?

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
File chrome/browser/history/history_querying_unittest.cc (right):

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
chrome/browser/history/history_querying_unittest.cc:311:
EXPECT_TRUE(results.reached_beginning());
I think the previous EXPECT_FALSE() case was trying to test something additional
to the EXPECT_TRUE() up three lines.  I _think_ it was saying that the oldest
result with "some" wasn't the oldest result possible (such as for std::string()
above).

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
chrome/browser/history/history_querying_unittest.cc:418: QueryHistory("same",
options, &results);
Or "title".

[rmcilroy, 2013-06-20 21:48:08]

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
File chrome/browser/history/history_backend.cc (right):

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
chrome/browser/history/history_backend.cc:1438: QueryResults* result) {
On 2013/06/20 19:50:22, shess wrote:
> Do you think there would be any value to histogramming timing information for
> this function?  Not breaking it down, but just getting the overall cost.

There is already a timing histogram for the caller of this function (line 1374)
which measures timings of both basic and text searches ("History.QueryHistory").
 I think this is sufficient, what do you think?

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
File chrome/browser/history/history_querying_unittest.cc (left):

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
chrome/browser/history/history_querying_unittest.cc:361: options.body_only =
true;
On 2013/06/20 19:50:22, shess wrote:
> Is |body_only| still present as an option?

I will remove it in the followup CL which removes all traces of FTS.

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
File chrome/browser/history/history_querying_unittest.cc (right):

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
chrome/browser/history/history_querying_unittest.cc:311:
EXPECT_TRUE(results.reached_beginning());
On 2013/06/20 19:50:22, shess wrote:
> I think the previous EXPECT_FALSE() case was trying to test something
additional
> to the EXPECT_TRUE() up three lines.  I _think_ it was saying that the oldest
> result with "some" wasn't the oldest result possible (such as for
std::string()
> above).

I _think_ this was not reaching the oldest in this case because previously, the
http://example.com/ visited 180 days ago would be in a separate text_database
index file (since they are split by month).  Since this query reached capacity,
the previous FTS search wouldn't try searching the older index file, and
wouldn't know whether there were any other matches in that index, so would
return false for reached_beginning.  Now the text search will have searched all
timescales, and will know that there are no further results, so
reached_beginning should be true.  Maybe we should just remove this test now?

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
chrome/browser/history/history_querying_unittest.cc:418: QueryHistory("same",
options, &results);
On 2013/06/20 19:50:22, shess wrote:
> Or "title".

"title" also finds the other results which contain the text "Title" which are
added from test_entries in Setup(), so that doesn't work here.

[Scott Hess - ex-Googler, 2013-06-20 22:18:31]

You have defused all of my nits, so still LGTM, but with low confidence.

Brett can feel free to rubber-stamp, though :-).

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
File chrome/browser/history/history_backend.cc (right):

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
chrome/browser/history/history_backend.cc:1438: QueryResults* result) {
On 2013/06/20 21:48:08, Ross Mcilroy wrote:
> On 2013/06/20 19:50:22, shess wrote:
> > Do you think there would be any value to histogramming timing information
for
> > this function?  Not breaking it down, but just getting the overall cost.
> 
> There is already a timing histogram for the caller of this function (line
1374)
> which measures timings of both basic and text searches
("History.QueryHistory").
>  I think this is sufficient, what do you think?

Sounds good.

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
File chrome/browser/history/history_querying_unittest.cc (left):

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
chrome/browser/history/history_querying_unittest.cc:361: options.body_only =
true;
On 2013/06/20 21:48:08, Ross Mcilroy wrote:
> On 2013/06/20 19:50:22, shess wrote:
> > Is |body_only| still present as an option?
> 
> I will remove it in the followup CL which removes all traces of FTS.

OK.  Mostly wanted to make sure there wasn't an alternate meaning.

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
File chrome/browser/history/history_querying_unittest.cc (right):

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
chrome/browser/history/history_querying_unittest.cc:311:
EXPECT_TRUE(results.reached_beginning());
On 2013/06/20 21:48:08, Ross Mcilroy wrote:
> On 2013/06/20 19:50:22, shess wrote:
> > I think the previous EXPECT_FALSE() case was trying to test something
> additional
> > to the EXPECT_TRUE() up three lines.  I _think_ it was saying that the
oldest
> > result with "some" wasn't the oldest result possible (such as for
> std::string()
> > above).
> 
> I _think_ this was not reaching the oldest in this case because previously,
the
> http://example.com/ visited 180 days ago would be in a separate text_database
> index file (since they are split by month).  Since this query reached
capacity,
> the previous FTS search wouldn't try searching the older index file, and
> wouldn't know whether there were any other matches in that index, so would
> return false for reached_beginning.  Now the text search will have searched
all
> timescales, and will know that there are no further results, so
> reached_beginning should be true.  Maybe we should just remove this test now?

<no-idea-dog/>, but it sounds like you're on top of that.  I think these lines
look like they duplicate the intersection of the std::string() test stanza and
the max_count w/"some" test stanza, so they probably aren't necessary.

https://chromiumcodereview.appspot.com/16776004/diff/24001/chrome/browser/his...
chrome/browser/history/history_querying_unittest.cc:418: QueryHistory("same",
options, &results);
On 2013/06/20 21:48:08, Ross Mcilroy wrote:
> On 2013/06/20 19:50:22, shess wrote:
> > Or "title".
> 
> "title" also finds the other results which contain the text "Title" which are
> added from test_entries in Setup(), so that doesn't work here.

In that case, nevermind my point.

[brettw, 2013-06-21 19:41:35]

Owners LGTM, I didn't delve into the detailed matching logic.

[commit-bot: I haz the power, 2013-06-22 01:46:29]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/rmcilroy@chromium.org/16776004/24001

[commit-bot: I haz the power, 2013-06-22 02:30:01]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/rmcilroy@chromium.org/16776004/24001

[commit-bot: I haz the power, 2013-06-22 03:18:58]

Retried try job too often on linux_rel for step(s) base_unittests,
browser_tests, cacheinvalidation_unittests, cc_unittests, check_deps,
chromedriver2_unittests, components_unittests, content_browsertests,
content_unittests, crypto_unittests, gpu_unittests, interactive_ui_tests,
ipc_tests, jingle_unittests, media_unittests, nacl_integration, net_unittests,
ppapi_unittests, printing_unittests, remoting_unittests,
sandbox_linux_unittests, sql_unittests, sync_integration_tests, sync_unit_tests,
unit_tests
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=linux_rel&...

[commit-bot: I haz the power, 2013-06-22 13:47:48]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/rmcilroy@chromium.org/16776004/24001

[commit-bot: I haz the power, 2013-06-22 14:34:08]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/rmcilroy@chromium.org/16776004/24001

[commit-bot: I haz the power, 2013-06-22 15:03:17]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/rmcilroy@chromium.org/16776004/24001

[commit-bot: I haz the power, 2013-06-22 16:59:29]

Change committed as 208068