Last Comment Bug 479739 - Make location bar autocomplete even faster
: Make location bar autocomplete even faster
Status: RESOLVED FIXED
: perf, verified1.9.1
Product: Firefox
Classification: Client Software
Component: Location Bar (show other bugs)
: Trunk
: All All
: -- normal with 4 votes (vote)
: Firefox 3.6a1
Assigned To: Ed Lee :Mardak
:
Mentors:
https://build.mozilla.org/tryserver-b...
Depends on: 478097
Blocks:
  Show dependency treegraph
 
Reported: 2009-02-22 21:32 PST by Ed Lee :Mardak
Modified: 2009-09-14 13:11 PDT (History)
21 users (show)
edilee: in‑testsuite-
edilee: in‑litmus-
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
v1 (1.67 KB, patch)
2009-02-22 21:35 PST, Ed Lee :Mardak
sdwilsh: review+
mbeltzner: approval1.9.1+
Details | Diff | Splinter Review
explain output (new query) (6.25 KB, text/plain)
2009-02-25 10:17 PST, Ed Lee :Mardak
no flags Details
schema info (4.55 KB, text/plain)
2009-02-25 10:17 PST, Ed Lee :Mardak
no flags Details
explain output (old query) (9.96 KB, text/plain)
2009-02-25 10:46 PST, Ed Lee :Mardak
no flags Details

Description Ed Lee :Mardak 2009-02-22 21:32:33 PST
From bug 478097 comment #19:
> With that said, we could probably remove "WHERE h.id NOT IN (SELECT id FROM
> moz_places_temp)" from the second query since we already check for duplicates
> anyway.  I imagine that will let sqlite get us results faster, but it'd need
> testing (and should go into a new bug).

I took a look at getting rid of that check, but it didn't improve much when querying without anything in the temp table. But I adjusted the query and got rid of a bunch of duplicate parts and it runs much faster.

It makes going through all your history twice as fast. Or it takes half the time to see the throbber stop spinning.
Comment 1 Ed Lee :Mardak 2009-02-22 21:35:25 PST
Created attachment 363646 [details] [diff] [review]
v1

Use an inner query to figure out which places to grab out of temp table and moz_places. Then do the usual business except now without duplicating SELECT, BOOK_TAG_SQL, OUTER JOIN for favicon, frececy <> 0, etc.

combine.select:
Query: mozilla First: 16,16,16 Finish: 16,16,16
Query: mozilla bugzilla First: 7,8,12 Finish: 107,118,135
Query: mozilla bugzilla fast First: 131,141,150 Finish: 15026,15086,15175

trunk:
Query: mozilla First: 8,8,8 Finish: 8,8,8
Query: mozilla bugzilla First: 7,8,8 Finish: 101,111,117
Query: mozilla bugzilla fast First: 125,136,141 Finish: 32502,33390,33719

I'm still looking into why the initial query is some ms slower, but in the long running case of going through all of history, it goes much faster.
Comment 2 Shawn Wilsher :sdwilsh 2009-02-22 21:48:47 PST
Hmm, not sure we want to optimize the case of going through all of history.  Finding out why it's slower initially would be good to know.

What does the first result look like in terms of bookmarks/tags/keyword/adaptive rank?
Comment 3 Ed Lee :Mardak 2009-02-22 23:46:48 PST
(In reply to comment #2)
> Hmm, not sure we want to optimize the case of going through all of history. 
Well, this also speeds up finding pages you want in your history. The faster we go through boundary matches, the faster we switch to anywhere matches as well.

> What does the first result look like in terms of bookmarks...
Same functionality as before. This only changes the full history query.

I've been using this build for a little bit and things seem to be fine.
https://build.mozilla.org/tryserver-builds/2009-02-22_18:47-edward.lee@engineering.uiuc.edu-combine.select/

A bit snappier due to it being able to find pages with lower frecencies faster too. 8ms vs 16ms doesn't make a big difference to me.
Comment 4 Ed Lee :Mardak 2009-02-23 00:29:17 PST
This is interesting. This build goes even faster than Firefox 3...?

Firefox 3
Query: mozilla First: 18,18,19 Finish: 18,18,19
Query: mozilla bugzilla First: 11,11,12 Finish: 101,114,126
Query: mozilla bugzilla fast First: 129,141,151 Finish: 19147,19589,20340

combine.select:
Query: mozilla First: 16,16,16 Finish: 16,16,16
Query: mozilla bugzilla First: 7,8,8 Finish: 108,113,121
Query: mozilla bugzilla fast First: 134,137,142 Finish: 15630,15729,15851
Comment 5 Marco Bonardo [::mak] 2009-02-23 02:02:32 PST
mh that is somehow going back to before when we were already limiting moz_places, but will remove the optimization we have in the query where the union helps us allowing for multiple threads, so we go back having to complete a first query before going on with the next one. At least from what drh said us.
Comment 6 Shawn Wilsher :sdwilsh 2009-02-23 07:27:52 PST
(In reply to comment #3)
> > What does the first result look like in terms of bookmarks...
> Same functionality as before. This only changes the full history query.
> 
> I've been using this build for a little bit and things seem to be fine.
> https://build.mozilla.org/tryserver-builds/2009-02-22_18:47-edward.lee@engineering.uiuc.edu-combine.select/
I meant what was the result, not how it differs from before.  I'm trying to establish why we are seeing the speed gains, which means I need to know details about the first entry such as "is it a bookmark/keyword/has tags, etc.  I don't have your places.sqlite, so I can't find out myself.
Comment 7 Ed Lee :Mardak 2009-02-24 19:08:17 PST
Using dietrich's places.sqlite, I paste in "mozilla bugzilla fail" and do a wall clock timing:
feb 14: ~122sec
trunk: ~68sec
combine: ~24sec

When I use a test script that runs 5 times (min,avg,max) milliseconds:
feb 14:  Finish: 108990, 109859, 110970
trunk:   Finish:  63764,  64144,  64640
combine: Finish:  22426,  22724,  23543
Comment 8 Shawn Wilsher :sdwilsh 2009-02-24 19:16:44 PST
What about searches where it finds a result?
Comment 9 Marco Bonardo [::mak] 2009-02-25 08:42:44 PST
{ADDITIONAL_CONDITIONS} is applied later, but moz_places are limited before... so practically we look through more smaller chunks instead of less already filtered chunks.

so we split moz_places in many LIMIT chunks, then on every chunk we apply {ADDITIONAL_CONDITIONS}, continuing till we get all the results we need.
The worst case then should be something with a really low frecency that is the only result true with {ADDITIONAL_CONDITIONS}, that will cause us to skip a lot of chunks before reaching it.
Comment 10 Shawn Wilsher :sdwilsh 2009-02-25 10:09:13 PST
(In reply to comment #9)
> {ADDITIONAL_CONDITIONS} is applied later, but moz_places are limited before...
> so practically we look through more smaller chunks instead of less already
> filtered chunks.
How have you come to that conclusion?

> so we split moz_places in many LIMIT chunks, then on every chunk we apply
> {ADDITIONAL_CONDITIONS}, continuing till we get all the results we need.
> The worst case then should be something with a really low frecency that is the
> only result true with {ADDITIONAL_CONDITIONS}, that will cause us to skip a lot
> of chunks before reaching it.
But his benchmarks indicate that this has no noticeable performance hit (in fact it's a win).  It's quite possible that the optimizer is passing these conditions to the subquery tables, but I need to see the explain output still (Edward, can you attach that please?)
Comment 11 Ed Lee :Mardak 2009-02-25 10:17:09 PST
Created attachment 364126 [details]
explain output (new query)

Here's the explain text I'm trying to feed into asuth's (Andrew Sutherland) python script to visualize the query. He's put the script online in version control here.

http://hg.mozilla.org/users/bugmail_asutherland.org/grokexplain/

Output of the script for another query here:
http://www.visophyte.org/blog/2009/02/04/visualization-of-control-flowdata-flow-analysis-of-sqlite-explain-ations/
Comment 12 Ed Lee :Mardak 2009-02-25 10:17:52 PST
Created attachment 364128 [details]
schema info
Comment 13 Ed Lee :Mardak 2009-02-25 10:46:18 PST
Created attachment 364133 [details]
explain output (old query)
Comment 14 Shawn Wilsher :sdwilsh 2009-02-25 18:37:14 PST
Comment on attachment 363646 [details] [diff] [review]
v1

r=sdwilsh
Comment 15 Shawn Wilsher :sdwilsh 2009-02-25 18:39:29 PST
That's r=sdwilsh with a comment stating that raw sqlite says this isn't the fastest way to do this, but in the browser it ends up being the case.
Comment 17 Ed Lee :Mardak 2009-02-25 21:49:28 PST
Comment on attachment 363646 [details] [diff] [review]
v1

Requesting approval of simple performance win for Firefox 3.1.
Comment 18 Dean Tessman 2009-03-03 07:35:31 PST
(In reply to comment #15)
> That's r=sdwilsh with a comment stating that raw sqlite says this isn't the
> fastest way to do this, but in the browser it ends up being the case.

I don't think this comment made it into the check-in.
Comment 19 Mike Beltzner [:beltzner, not reading bugmail] 2009-03-31 10:40:50 PDT
Comment on attachment 363646 [details] [diff] [review]
v1

a191=beltzner
Comment 20 Marco Bonardo [::mak] 2009-04-01 06:31:27 PDT
http://hg.mozilla.org/releases/mozilla-1.9.1/rev/324737486a0e

Note You need to log in before you can comment on or make changes to this bug.