385397 - history menu is slow to open with a large history

Status: RESOLVED FIXED

(Firefox :: Bookmarks & History, defect)

Description

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

history menu is slow to open with a large history

my change for bug #384677 made this worse, as we used to limit that with a date query (30 days <= visit date <= 2 hours in the future).

we do benefit from bug #337855 if you re-open the menu before visiting a page.

given that we only have 10 elements, I bet the slow down is with our query, and not with the code that builds up the menu.

Our query is:  place:type=0&sort=4&maxResults=10

or:  "the last ten unique uris sorted by date descending."

limiting the range should help, as that means less for us to sort.  with the query query, sqlite has to sort all the history items.

hack idea, forgive me:

For a query like:  place:type=0&sort=4&maxResults=10

1)  figure out the visit date of the last page we visited
2)  query for the last ten unique uris and newer than 24 hours before the last page we visited (or something reasonable)

If we get ten results, we are good.  otherwise, we may have to do a full query

Comment 1

[Dave Townsend [:mossop]]

I would agree with this. At least for the history menu I'm likely looking for the things I've visited very recently. I'm not going to remember if its a day or so old.

Comment 2

[Ria Klaassen (not reading all bugmail)]

I'm using some code ( http://forums.mozillazine.org/viewtopic.php?p=2757303&sid=4b31ce7dbe2143b364407ae8380c271e#2757303  ) 
to enlarge the menu to 200 items. When I start the browser and click on the History menu, it takes 3 seconds before the menu shows up. But when I first do some other things (reading mail at Gmail e.g.) and then click on History, there's a big chance that it hangs. I have no idea what is causing this because I can't reproduce it intentionally. It happens very often particularly in the last few days/weeks, maybe it has nothing to do with history, as I'm also experiencing hangs and delays while scrolling. Could not yet pinpoint it down to a certain extension or script, that's the big problem. 

Comment 3

[Ria Klaassen (not reading all bugmail)]

The delays while scrolling and while typing in the location bar only happen after opening the History menu. Then it gets worse and worse and the only solution is to restart the browser and to avoid the use of the History menu.
When I disable the half of the extensions also the problem halves. Both the extensions UserChrome.js and Custom Buttons seem to provoke the problem, which deteriorated when Bug 337855 was checked in.

Comment 4

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

This are really slow for me with ispiked's profile.  

I agree about bug #337855 being related. 

I can see that after opening the menu, we re-query [1] after visiting a link.

And our query is expensive and can take over 5 seconds to execute:

SELECT h.id, h.url, h.title, h.rev_host, h.visit_count, (SELECT MAX(visit_date) FROM moz_historyvisits WHERE place_id = h.id), f.url, null, null FROM moz_places h LEFT OUTER JOIN moz_historyvisits v ON h.id = v.place_id LEFT OUTER JOIN moz_favicons f ON h.favicon_id = f.id WHERE (h.hidden <> 1 )
GROUP BY h.id ORDER BY 6 DESC LIMIT 10

I am sure we can find a better way to get the last 10 visited pages for the history menu.

Comment 5

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

this also explains a problem I was seeing:

1)  open history menu with large history
2)  visit page with a text field
3)  start typing in text field
4)  we do the lazy add of the visit (see bug #329816) 
5)  we requery, so the browser freezes for 5 seconds while I attempt to type.

Separate from that problem, having things freeze / pause on every link after open the history menu has gotten worse in A6, and I'd like to fix that before we ship A6.

Comment 6

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

an update:

the reason we currently have to rebuild the menu after visiting a page is that because we limiting our query to the 10 results. So in  nsNavHistory::GetUpdateRequirements(), we determine the query to be QUERYUPDATE_COMPLEX, so on visit, we will call Refresh() on the result node, re run the query (which can be expensive), which will call invalidateContainer() in menu.xml, and so we'll rebuild the menu.

for the bookmarks menu, menu.xml has helped "second time" performance.

but for the history menu, this is very expensive, once you've opened it, we'll rebuild and re-query on every page visit, even if you don't open the menu.  so that's one thing to fix.  (note, if you have the history sidebar open while browsing, that will also be a perf hit for the same reason.  we have open bugs on that.)

the second thing to fix is the actual query to be faster.

right now we do:

SELECT h.id, h.url, h.title, h.rev_host, h.visit_count, (SELECT MAX(visit_date) FROM moz_historyvisits WHERE place_id = h.id), f.url, null, null FROM moz_places h LEFT OUTER JOIN moz_historyvisits v ON h.id = v.place_id LEFT OUTER JOIN moz_favicons f ON h.favicon_id = f.id WHERE (h.hidden <> 1) GROUP BY h.id ORDER BY 6 DESC LIMIT 10

This is actually giving us the wrong results, with ispiked's places.sqlite.  (See bug #381898, thanks ispiked!)

for one, we are not excluding TRANSITION_EMBED (v.visit_type <> 4).  but additionally, we are not excluding those (or hidden visits) when determing the most recent visits!

So a correct query would be:

SELECT h.id, h.url, h.title, h.rev_host, h.visit_count, (SELECT MAX(visit_date) FROM moz_historyvisits WHERE place_id = h.id and v.visit_type <> 4 and hidden <> 1), f.url, null, null FROM moz_places h LEFT OUTER JOIN moz_historyvisits v ON h.id = v.place_id LEFT OUTER JOIN moz_favicons f ON h.favicon_id = f.id GROUP BY h.id ORDER BY 6 DESC LIMIT 10

A faster version, from my tests, would be:

select h.id, h.url, h.title, h.rev_host, h.visit_count, MAX(visit_date), f.url, null, null from moz_historyvisits, moz_places h LEFT OUTER JOIN moz_favicons f ON h.favicon_id = f.id where place_id = h.id and h.hidden <> 1 and visit_type <> 4 group by place_id order by 6 desc limit 10

I wonder if we could get even faster by getting only the (at most) 10 favicons we need after we determine our 10 items?

Comment 7

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

ok, given that we have an index on visit_date, the following is a very fast way to return the place ids for the 10 items to show in the menu item:

select distinct h.id from moz_historyvisits, moz_places h where place_id = h.id and hidden <> 1 and visit_type <> 4 order by visit_date desc limit 10

now to just use it as a sub select and I think we should be good for the history menu.

Comment 8

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

the following query (which is a little ugly, still working on it), returns the last ten items for history menu in 15 milliseconds:

SELECT h.id, h.url, h.title, h.rev_host, h.visit_count, v.visit_date, f.url, null, null FROM moz_places h LEFT OUTER JOIN moz_historyvisits v ON h.id = v.place_id LEFT OUTER JOIN moz_favicons f ON h.favicon_id = f.id WHERE (h.id in (select distinct h.id from moz_historyvisits, moz_places h where place_id = h.id and hidden <> 1 and visit_type <> 4 order by visit_date desc limit 10)) order by v.visit_date desc limit 10

Compared to ~5000 milliseconds (5 seconds, ouch) for the previous query:
SELECT h.id, h.url, h.title, h.rev_host, h.visit_count, (SELECT MAX(visit_date) FROM moz_historyvisits WHERE place_id = h.id), f.url, null, null FROM moz_places h LEFT OUTER JOIN moz_historyvisits v ON h.id = v.place_id LEFT OUTER JOIN moz_favicons f ON h.favicon_id = f.id WHERE (h.hidden <> 1 ) GROUP BY h.id ORDER BY 6 DESC LIMIT 10

Comment 9

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

here's a better query, I think:

SELECT h.id, h.url, h.title, h.rev_host, h.visit_count, v.visit_date, f.url, null, null FROM moz_places h LEFT OUTER JOIN moz_historyvisits v ON h.id = v.place_id LEFT OUTER JOIN moz_favicons f ON h.favicon_id = f.id WHERE (h.id in (select distinct h.id from moz_historyvisits, moz_places h where place_id = h.id and hidden <> 1 and visit_type <> 4 order by visit_date desc limit 10)) GROUP BY h.id order by v.visit_date desc

Comment 10

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

Attachment: draft patch, include fix for bug #381898

Comment 11

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

Attachment: draft patch, v2, include fix for bug #381898

Comment 12

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

Attachment: draft patch, v3, include fix for bug #381898

Comment 13

[Asaf Romano (gone)]

For a6 I think we better do bug 386159. We can optimize result-type-uri queries in general before beta.

Comment 14

[Ria Klaassen (not reading all bugmail)]

Would this mean that the menu can't be changed anymore by the user? 10 items is pretty useless and that would mean that you mostly click in vain on History, only to discover that it was longer that 10 items ago that you visited the site that you're looking for. When you want to go to the sidebar (would not prefer this for the entire window moves unpleasantly to the right) it has a very long delay, nearly a hang, would not prefer this either.

Comment 15

[Ria Klaassen (not reading all bugmail)]

Wouldn't it be a good idea for an about:config option to be able to change the amount of history that is shown in the menu? 

Comment 16

[Ria Klaassen (not reading all bugmail)]

(In reply to comment #14)
> When you want to go to the sidebar (would not prefer
> this for the entire window moves unpleasantly to the right) it has a very long
> delay, nearly a hang
Sorry, this was nearly fixed, by Bug 341137.

Comment 17

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

> For a6 I think we better do bug 386159. 

Your fix for bug #386159 makes it so for non-folders we don't keep the container open.  That would help if we didn't optimize the query, as we would not re-query on every visit.

But with a large history, opening the menu is unreasonably slow, and I think we want this fix for that reason alone.

> We can optimize result-type-uri queries in general before beta.

Optimizing queries (both result-type-uri and result-type-visit) in general will be needed.  But I think we will also end up having some highly optimized special queries like the one in this patch.

Comment 18

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

> Would this mean that the menu can't be changed anymore by the user?

Ria, how could you do that before?

But to answer your question, the optimized query will work for place:type=0&sort=4&maxResults=<n> as long as n > 1.  Note, for large histories and large values of n, it will not perform well.

> Wouldn't it be a good idea for an about:config option to be able to change the
> amount of history that is shown in the menu? 

Let's spin that enhancement idea to a different bug.

> the sidebar ... has a very long delay, nearly a hang

Yes, there are lots of performance issues with the history sidebar with a large history and with searching (see bug #385245).  Let's take that discussion to that bug.

Comment 19

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

Attachment: patch for a specialized query for a fast history menu

separating out just the part for fixing the history menu query

Comment 20

[bomfog]

(In reply to comment #18)
> > Would this mean that the menu can't be changed anymore by the user?
> 
> Ria, how could you do that before?

userChrome.js (see comment #2)

Comment 21

[Dietrich Ayala (:dietrich)]

Comment on attachment 273188 [details] [diff] [review]
patch for a specialized query for a fast history menu

the test for when to use the special-case query needs to be exclusionary as well as inclusionary. currently, it'll match any query that has those parameters *plus* any other parameters set. it needs to exclude all queries except those with *only* those parameters set.

Comment 22

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

Attachment: updated patch, per dietrich's comment. (more exclusions coming...)

Comment 23

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

Attachment: updated patch, complete exclusion (and passes test_history.js)

Comment 24

[Mike Schroepfer]

Any chance we can get this into a7?

Comment 25

[Mike Connor [:mconnor]]

Missing the freeze, moving out.

Comment 26

[Dietrich Ayala (:dietrich)]

Comment on attachment 273931 [details] [diff] [review]
updated patch, complete exclusion (and passes test_history.js)

looks good, thanks for adding the exclusions, r=me

Comment 27

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

seeking approval for m7

Comment 28

[Mike Schroepfer]

approved over IRC.  Make sure to steer clear of the secure wrapper landing

Comment 29

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

fixed.

Checking in toolkit/components/places/src/nsNavHistory.cpp;
/cvsroot/mozilla/toolkit/components/places/src/nsNavHistory.cpp,v  <--  nsNavHis
tory.cpp
new revision: 1.146; previous revision: 1.145
done
Checking in toolkit/components/places/src/nsNavHistory.h;
/cvsroot/mozilla/toolkit/components/places/src/nsNavHistory.h,v  <--  nsNavHisto
ry.h
new revision: 1.88; previous revision: 1.87
done

Comment 30

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

Attachment: test case

Comment 31

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

thanks for the review, dietrich.

landed with a=mconnor for M7.

Checking in test_385397.js;
/cvsroot/mozilla/toolkit/components/places/tests/unit/test_385397.js,v  <--  tes
t_385397.js
initial revision: 1.1
done

Comment 33

[Tracy Walker [:tracy]]

verified with: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9a8pre) Gecko/2007080309 Minefield/3.0a8pre

Comment 34

[Danny]

Just installed latest nightly build and still got same problem

Comment 35

[Colin Barrett [:cbarrett]]

This is still really slow for me, on both my Macs. One running Leopard, one Tiger.

Comment 36

[Colin Barrett [:cbarrett]]

STR:

1. Start Minefield.
2. Click History menu.

I have a wait of ~10 seconds before the menu actually appears.

Comment 37

[Shawn Wilsher :sdwilsh]

~1-2 seconds for me
places.sqlite is 9.6MB

Comment 38

[Mike Schroepfer]

For the folks that are slow can you post the size of your db, moz_historyvisits and moz_places tables?

Comment 39

[Dietrich Ayala (:dietrich)]

looks like it's not using the special-case query seth added in this fix.

Comment 40

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

> looks like it's not using the special-case query seth added in this fix.

thanks for investigating.  

we should see why IsHistoryMenuQuery() [1] is not returning true for place:type=0&sort=4&maxResults=10 [2]

[1] http://lxr.mozilla.org/seamonkey/source/toolkit/components/places/src/nsNavHistory.cpp#2107

[2] http://lxr.mozilla.org/seamonkey/source/browser/base/content/browser-menubar.inc#334

Comment 41

[Mike Schroepfer]

if we are just swapping queries shouldw e get this in for b1/m9?

Comment 42

[Ria Klaassen (not reading all bugmail)]

Seems to be Mac only. On a rather slow system and a old places.sqlite of about 14 MB the history menu opens its 10 items within one second here. 

Comment 43

[Ria Klaassen (not reading all bugmail)]

Sorry for changing the target milestone inadvertently. 

Comment 44

[Ryan VanderMeulen [:RyanVM]]

If we're talking about the History sidebar, I can confirm that it's very slow on XPSP2 for me with a 53MB places.sqlite file.

Comment 45

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

> If we're talking about the History sidebar

In this case, we're talking about the History menu.  

As far as the history sidebar, that's covered by other bugs, such as bug #385245

Comment 46

[Dietrich Ayala (:dietrich)]

Attachment: fix regression from bug 317847

bug 317847 changed the default value for expandQueries, which caused IsHistoryMenuQuery() to return false.

Comment 47

[Asaf Romano (gone)]

Comment on attachment 287569 [details] [diff] [review]
fix regression from bug 317847

Er, there's no point in checking any of the exclude* options (and showsessions too fwiw) as they don't affect the db query.

Comment 48

[Dietrich Ayala (:dietrich)]

Attachment: fix regression from bug 317847 (v2)

(In reply to comment #47)
> (From update of attachment 287569 [details] [diff] [review])
> Er, there's no point in checking any of the exclude* options (and showsessions
> too fwiw) as they don't affect the db query.

Yes, that makes sense - most of the post-sql options could probably be removed. I'm going to fix this one option here, and file a bug about reviewing the rest.

Comment 49

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 287572 [details] [diff] [review]
fix regression from bug 317847 (v2)

a=beltzner for M9

Comment 50

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 287572 [details] [diff] [review]
fix regression from bug 317847 (v2)

No, seriously. It's approved.

Comment 51

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

Comment on attachment 287572 [details] [diff] [review]
fix regression from bug 317847 (v2)

r=sspitzer as well.

additionally, I double checked and tested against the dreaded ispiked places.sqlite and verified that before the fix we were slow (because IsHistoryMenuQuery() returned false) but after the fix IsHistoryMenuQuery() returned true for the history menu, and we were fast once again.

thanks dietrich (and thanks to colin for reopening)

Comment 52

[Dietrich Ayala (:dietrich)]

Checking in toolkit/components/places/src/nsNavHistory.cpp;
/cvsroot/mozilla/toolkit/components/places/src/nsNavHistory.cpp,v  <--  nsNavHistory.cpp
new revision: 1.187; previous revision: 1.186
done

Comment 53

[Gervase Markham [:gerv]]

Bug 451915 - move Firefox/Places bugs to Firefox/Bookmarks and History. Remove all bugspam from this move by filtering for the string "places-to-b-and-h".

In Thunderbird 3.0b, you do that as follows:
Tools | Message Filters
Make sure the correct account is selected. Click "New"
Conditions: Body   contains   places-to-b-and-h
Change the action to "Delete Message".
Select "Manually Run" from the dropdown at the top.
Click OK.

Select the filter in the list, make sure "Inbox" is selected at the bottom, and click "Run Now". This should delete all the bugspam. You can then delete the filter.

Gerv