User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.0; it; rv:1.8.1.4) Gecko/20070515 Firefox/2.0.0.4 Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 6.0; it; rv:1.8.1.4) Gecko/20070515 Firefox/2.0.0.4 nsNavHistoryAutoComplete::AutoCompleteTypedSearch uses an nsDataHashtable to filter out duplicates, but that can be done in SQL using a GROUP BY clause. Final result is more readable and removes the AUTOCOMPLETE_MAX_PER_TYPED * 3 "trick" This is my first attempt to make a patch against cvs so please double check. I need someone to review and eventually checkin Reproducible: Always Steps to Reproduce: Nothing

mano, do you mind if I take this review? I'd like to see what affects this has on performance.

Sure thing.

Comment on attachment 270168 [details] [diff] [review] Use group by instead of nsDataHashTable changing review to sspitzer

Fixed comment and the SQL query using a label for MAX(visit_date)

Marco's patch boils down to: SELECT MAX(visit_date) as max_visit_date, url, title FROM moz_historyvisits v JOIN moz_places h ON v.place_id = h.id WHERE h.typed = 1 GROUP BY url ORDER BY max_visit_date DESC LIMIT 100 I'm worried this will be slow for large histories. Following the still on going perf work for the history menu) what about this: SELECT MAX(v.visit_date) as max_visit_date, h.url, h.title FROM moz_places h JOIN moz_historyvisits v ON h.id = v.place_id WHERE (h.id in (select distinct h.id from moz_historyvisits, moz_places h where place_id = h.id and h.typed = 1 order by visit_date desc limit 100)) GROUP BY h.url ORDER BY max_visit_date DESC

note, we no longer need count as we limit the results to AUTOCOMPLETE_MAX_PER_TYPED Marco, what do you think? (Note, this is the same performance trick from bug #381898) In my tests, for ispike's large history, this query is about 2 to 3 times faster than the original patch from Marco. Example times (in microseconds), where "total time 1" is the original patch and "total time 2" is the version I attached. total time 1 = 125000 total time 2 = 31250 total time 1 = 78125 total time 2 = 46875 total time 1 = 109375 total time 2 = 31250 total time 1 = 109375 total time 2 = 46875 total time 1 = 109375 total time 2 = 46875 total time 1 = 62500 total time 2 = 31250 total time 1 = 109375 total time 2 = 46875 total time 1 = 125000 total time 2 = 31250

from previous testing i saw that in sqlite subqueries are better optimized than joins, so your results are not surprising. i don't get a so big advantage but i have a tighter history, on my history timings are almost the same = 18ms Instead i get big advantegs in timing if i create an index over moz_places.typed, with such an index i get my query faster than yours, each are faster with that index, i get less than half the time = 5ms Could you retry what gives your benchmark creating that new index?

i'm doing some additional testing on a random generated content places.sqlite (size of the db is 28MB), i've added also favicons to the queries, i finished with this, that is (very) slightly faster: SELECT p.url, p.title, (SELECT f.url from moz_favicons f WHERE f.id = p.favicon_id) FROM moz_places p WHERE p.id IN( SELECT h.id FROM moz_places h WHERE h.typed = 1 ORDER BY (SELECT MAX(visit_date) FROM moz_historyvisits WHERE place_id = h.id GROUP BY place_id) DESC LIMIT 100 ) ORDER BY (SELECT MAX(visit_date) FROM moz_historyvisits WHERE place_id = p.id GROUP BY place_id) DESC hwv previous patches are all obsolete with the addition of the favicons

i had forgotten to remove the typed index created for testing, without that index instead i get faster with your query, but you can move max(visit_date) to order by, cause you don't need to select that field SELECT h.url, h.title, (SELECT f.url from moz_favicons f WHERE f.id = p.favicon_id) FROM moz_places h JOIN moz_historyvisits v ON h.id = v.place_id WHERE (h.id in (select distinct h.id from moz_historyvisits, moz_places h where place_id = h.id and h.typed = 1 order by visit_date desc limit 100)) GROUP BY h.url ORDER BY MAX(visit_date) DESC yes, imho this could be the final query

comment #10: s/p.favicon_id/h.favicon_id/ i don't see advantages in using a subquery insted of a left join for favicons, i see a slightly improvement mixing the two previous queries: SELECT h.url, h.title, f.url FROM moz_places h LEFT JOIN moz_favicons f ON f.id = h.favicon_id WHERE (h.id in (select distinct h.id from moz_historyvisits JOIN moz_places h ON place_id = h.id WHERE h.typed = 1 order by visit_date desc limit 100) ) ORDER BY (SELECT MAX(visit_date) FROM moz_historyvisits WHERE place_id = h.id group by place_id) DESC This Elapsed time: 21.695495ms comment #10 Elapsed time: 24.337171ms comment #6 Elapsed time: 27.621108ms i can't see any other improvement, sorry for bugspam

Hey Marco, thanks very much for doing the research on this. Seth, is this bug still valid after your recent auto-complete changes?

Comment on attachment 272121 [details] [diff] [review] patch based on marco's patch this code is about to change for bug #394038, so clearing review request.

there has been too much changes, i propose wontfix this, and then look for new improvements after the big changes (frecency)

I agree, marco. In the frecency patch, I have simplified the query, but for another reason. I'll start a new bug on that as it requires ux-approval, and I'll cc you.

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