365992 - [meta] Places based history searches are slow and hang the main-thread (Library/Sidebar UI)

Status: RESOLVED INACTIVE

(Firefox :: Bookmarks & History, defect)

Description

[(not reading, please use [e-mail] instead)]

places based history sidebar sluggish to respond to searches?

spun off of https://bugzilla.mozilla.org/show_bug.cgi?id=364325#c9

ria writes:  "This is fixed indeed but now it shows a temporary hang of more than a minute when I search for the word "window" in a places.sqlite file of 2.8 MB."

"Tested again but now I still see a large places.sqlite.file but no history in
the sidebar anymore. But when I search for the word "window", I see a hang
although the search results are in the right order now.
I have browser.history_expire_days set to 900 days."

"The test works fine when I run the same profile in a branch build.
Yesterday I saw the imported history in my sidebar but now only the today's
history again. If you want I can send you the profile for testing purposes (it's not very privacy sensitive but not in a way I can attach it here for there are hidden mail data)."

Comment 1

[(not reading, please use [e-mail] instead)]

I think I've seen this, too.

Comment 2

[(not reading, please use [e-mail] instead)]

for bug #364325 (see comment #6), I removed a performance optimization (which was causing a bug). removing that probably made things worse here, but we still have performance problems even after mano's fix for #366589.

Comment 3

[(not reading, please use [e-mail] instead)]

ria, once asaf lands his fix for bug #366589, can you test again?

Comment 4

[Ria Klaassen (not reading all bugmail)]

Bad news here: bug 366589 did not fix this bug; the behaviour is unchanged.
But there is also good news: it did fix bug 365768.

Comment 5

[Marco Bonardo [:mak]]

Attachment: patch v1.0

This patch reduced the query time in a debug build to a usable time.

Approach:
- Limit histoy sidebar results to a fixed amount (500 results, hardly a user can manage thousands of results)
- sort search results by frecency
- avoid the visits table join
- use autocomplete matching function

The patch is on top of Bug 556068 but it's independent from it, so it can be unbitrotted apart.

I can provide a trybuild if anybody is interested, but unless I get any sign of possibility to get it approved, I won't spend any more time on the topic.

Comment 6

[Dietrich Ayala (:dietrich)]

Does the change pass try? I'd feel much better if you confirmed that the code impact doesn't spread beyond this.

Comment 7

[Marco Bonardo [:mak]]

I've only run tests locally. will do a try pass.

Comment 8

[Marco Bonardo [:mak]]

got green, trybuilds here:
http://ftp.mozilla.org/pub/mozilla.org/firefox/tryserver-builds/[e-mail]-138ce8c6bf20/

Comment 9

[Dietrich Ayala (:dietrich)]

Comment on attachment 507871 [details] [diff] [review]
patch v1.0


>diff --git a/toolkit/components/places/public/nsINavHistoryService.idl b/toolkit/components/places/public/nsINavHistoryService.idl
>--- a/toolkit/components/places/public/nsINavHistoryService.idl
>+++ b/toolkit/components/places/public/nsINavHistoryService.idl
>@@ -1131,7 +1131,8 @@ interface nsINavHistoryQueryOptions : ns
>   const unsigned short SORT_BY_TAGS_DESCENDING = 18;
>   const unsigned short SORT_BY_ANNOTATION_ASCENDING = 19;
>   const unsigned short SORT_BY_ANNOTATION_DESCENDING = 20;
>-
>+  const unsigned short SORT_BY_FRECENCY_ASCENDING = 21;
>+  const unsigned short SORT_BY_FRECENCY_DESCENDING = 22;
> 

rev UUID... and isn't too late in the process for that?

another question: are sync tests run on tryserver? how does sync get history results? we need to figure out what assumptions in that code and their tests that we might be breaking.

Comment 10

[Brendan Eich [:brendan]]

Lealve the old constants in and add the new, or at least leave a gap? No IID change needed for const-only additions, right? Oh, I am a big cheater...

/be

Comment 11

[Marco Bonardo [:mak]]

Adding constants never required a UUID rev, we can do that.

Comment 12

[Marco Bonardo [:mak]]

(In reply to comment #9)
> another question: are sync tests run on tryserver? how does sync get history
> results? we need to figure out what assumptions in that code and their tests
> that we might be breaking.

I'm not limiting all queries, I'm explicitely setting sidebar and Library queries (well not in this patch but I should do it) to have a maxResults on the query object. It's a ui change, the only backend change is that we support sorting by frecency with this.
So, I'm just using our API, not changing anything developers can do with it. If a add-on wants to get all history it can, it will be slow as before.
I still have to do a couple experiments, I think 500 results is still a hog for the UI, I could have to limit to 200, that ideally is already enough for a user looking for results to handle.

Comment 14

[Dietrich Ayala (:dietrich)]

Comment on attachment 507871 [details] [diff] [review]
patch v1.0

>@@ -3547,7 +3540,7 @@ PlacesSQLQueryBuilder::SelectAsSite()
>     "WHERE EXISTS ( "
>       "SELECT h.id FROM moz_places h "
>       "%s "
>-      "WHERE h.hidden <> 1 "
>+      "WHERE h.hidden = 0 "
>         "AND h.visit_count > 0 "
>         "AND h.url BETWEEN 'file://' AND 'file:/~' "
>       "%s "

why?

>@@ -5835,19 +5854,11 @@ nsNavHistory::QueryToSelectClause(nsNavH
> 
>   // transitions
>   const nsTArray<PRUint32>& transitions = aQuery->Transitions();
>-  // Optimize single transition query, since this is the most common use case.
>-  if (transitions.Length() == 1) {
>-    clause.Condition("v.visit_type =").Param(":transition0_");
>-  }
>-  else if (transitions.Length() > 1) {
>-    for (PRUint32 i = 0; i < transitions.Length(); ++i) {
>-      nsPrintfCString param(":transition%d_", i);
>-      clause.Str("EXISTS (SELECT 1 FROM moz_historyvisits "
>-                         "WHERE place_id = h.id AND visit_type = "
>-                ).Param(param.get()).Str(" LIMIT 1)");
>-      if (i < transitions.Length() - 1)
>-        clause.Str("AND");
>-    }
>+  for (PRUint32 i = 0; i < transitions.Length(); ++i) {
>+    nsPrintfCString param(":transition%d_", i);
>+    clause.Condition("EXISTS (SELECT 1 FROM moz_historyvisits "
>+                             "WHERE place_id = h.id AND visit_type = "
>+              ).Param(param.get()).Str(" LIMIT 1)");
>   }

why removing that optimization?

>-  static int SortComparison_TagsGreater(
>-      nsNavHistoryResultNode* a, nsNavHistoryResultNode* b, void* closure);
>+  static PRInt32 SortComparison_Bookmark(nsNavHistoryResultNode* a,
>+                                         nsNavHistoryResultNode* b,

why?

*every* change has risk, so we need to minimize impact of patches as much as possible, hence my questioning about changes that don't appear to be absolutely necessary to fix the problem at hand.

Comment 15

[Marco Bonardo [:mak]]

(In reply to comment #14)
> Comment on attachment 507871 [details] [diff] [review]
> >@@ -3547,7 +3540,7 @@ PlacesSQLQueryBuilder::SelectAsSite()
> >     "WHERE EXISTS ( "
> >       "SELECT h.id FROM moz_places h "
> >       "%s "
> >-      "WHERE h.hidden <> 1 "
> >+      "WHERE h.hidden = 0 "
> >         "AND h.visit_count > 0 "
> >         "AND h.url BETWEEN 'file://' AND 'file:/~' "
> >       "%s "
> 
> why?

SQLite optimizer is happier about it (it can better evaluate the size of the resultset), and since it can only have 2 values (1,0) it makes no sense to check for <>. The change has no other impact, I can avoid it if you want a smaller patch.

> >@@ -5835,19 +5854,11 @@ nsNavHistory::QueryToSelectClause(nsNavH
> > 
> >   // transitions
> >   const nsTArray<PRUint32>& transitions = aQuery->Transitions();
> >-  // Optimize single transition query, since this is the most common use case.
> 
> why removing that optimization?

to avoid the slow "group by" I'm not joining on visits, so we can't do direct visits table checks

> 
> >-  static int SortComparison_TagsGreater(
> >-      nsNavHistoryResultNode* a, nsNavHistoryResultNode* b, void* closure);
> >+  static PRInt32 SortComparison_Bookmark(nsNavHistoryResultNode* a,
> >+                                         nsNavHistoryResultNode* b,
> 
> why?

we don't use pure "int", we use nspr, I noticed that when I added the new comparator for frecency. it's a mere s/int/PRInt32/ replace

> *every* change has risk, so we need to minimize impact of patches as much as
> possible, hence my questioning about changes that don't appear to be absolutely
> necessary to fix the problem at hand.

absolutely, I also think there is no sense in taking the patch unless the usecase has a _huge_ win. So I want something that solves the real usage problem or wait next version.

Comment 16

[Dietrich Ayala (:dietrich)]

Comment #5 says this patch gets search to a "usable" state. What's that in numbers, in your local tests?

Comment 17

[Marco Bonardo [:mak]]

(In reply to comment #16)
> Comment #5 says this patch gets search to a "usable" state. What's that in
> numbers, in your local tests?

Unfortunately there is no fixed number, the performance is variable based on "how hard is to find X results for the search term".
The only way we have to do a search is a table scan, we start from the result with higher frecency, and go down the table looking for a row that matches. If the matching rows are high we can stop earlier, if there is no match or less than the limit, then we have to walk the full table.
This is because we miss a fulltext index.
This is also why the locationbar sometimes is incredibly fast and sometimes incredibly slow. But the locationbar has 2 big advantages: it's limited to 12 results, and it's async.

Searching for "google" in my db moved the first result to be returned from 12s to 600ms, but this is a website I clearly visit often.
Searching for a strange word that does not exist in history, or has fewer than X matches, still has to walk the full table. What we save is only the sqlite>resultnode conversion and some other marginal code in this case.
The more we restrict the number of results, the less likely we scan all the table, the difficult part is to find the right number of results without making the query lacking.

Summing up advantages with the patch:
- last visited and most visited are instant (locally limited to 200 results that look enough for most purposes)
- searches returning lots of results are faster (a good limit has to be found though)
- searches are more useful (frecency is a better sorting algo than title)
- moves us a bit more toward async containers
Disadvantages:
- late changes are risky
What does not improve enough:
- searches returning few results (< our limit) or no results still hang, and the hang is repeated due to live-update (it's funny that updating a empty result is much slower than a full one)

Comment 19

[Marco Bonardo [:mak]]

Comment on attachment 507871 [details] [diff] [review]
patch v1.0

Since the full issue can't be fixed without fulltext index and async containers, I'm going to make this a meta bug.

Comment 20

[Marco Bonardo [:mak]]

Notice the above patch to make things better has been moved to bug 630225.

Comment 21

[BMO Automation]

Per policy at https://wiki.mozilla.org/Bug_Triage/Projects/Bug_Handling/Bug_Husbandry#Inactive_Bugs. If this bug is not an enhancement request or a bug not present in a supported release of Firefox, then it may be reopened.