Simplify nsNavHistoryAutoComplete::AutoCompleteTypedSearch

RESOLVED WONTFIX

Status

()

RESOLVED WONTFIX
12 years ago
9 years ago

People

(Reporter: mak, Assigned: mak)

Tracking

Trunk
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment, 2 obsolete attachments)

(Assignee)

Description

12 years ago
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
(Assignee)

Comment 1

12 years ago
Created attachment 270168 [details] [diff] [review]
Use group by instead of nsDataHashTable
Attachment #270168 - Flags: review?(mano)

Updated

12 years ago
Assignee: nobody → mak77
Status: UNCONFIRMED → NEW
Component: Location Bar and Autocomplete → Places
Ever confirmed: true
QA Contact: location.bar → places
Version: unspecified → Trunk
mano, do you mind if I take this review?

I'd like to see what affects this has on performance.
(Assignee)

Comment 4

11 years ago
Comment on attachment 270168 [details] [diff] [review]
Use group by instead of nsDataHashTable

changing review to sspitzer
Attachment #270168 - Flags: review?(mano) → review?(sspitzer)
(Assignee)

Comment 5

11 years ago
Created attachment 271220 [details] [diff] [review]
Use group by instead of nsDataHashTable

Fixed comment and the SQL query using a label for MAX(visit_date)
Attachment #270168 - Attachment is obsolete: true
Attachment #271220 - Flags: review?(sspitzer)
Attachment #270168 - Flags: review?(sspitzer)
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
Created attachment 272121 [details] [diff] [review]
patch based on marco's patch

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
Attachment #271220 - Attachment is obsolete: true
Attachment #272121 - Flags: review?(mak77)
Attachment #271220 - Flags: review?(sspitzer)
(Assignee)

Comment 8

11 years ago
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?
(Assignee)

Comment 9

11 years ago
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
(Assignee)

Comment 10

11 years ago
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
(Assignee)

Comment 11

11 years ago
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.
Attachment #272121 - Flags: review?(mak77)
(Assignee)

Comment 14

11 years ago
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.
Status: NEW → RESOLVED
Last Resolved: 11 years ago
Resolution: --- → WONTFIX
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
Component: Places → Bookmarks & History
QA Contact: places → bookmarks
You need to log in before you can comment on or make changes to this bug.