414426 - Optimize SearchTags query

Status: RESOLVED INVALID

(Firefox :: Bookmarks & History, defect)

Description

[Ed Lee :Mardak]

Right now we do the standard place query then filter out if it's a tag in a subselect.

We should select on the tags first then find places that match the tag.

Comment 1

[Ed Lee :Mardak]

Attachment: v1

Initial stab.

Comment 2

[Ed Lee :Mardak]

The patch changes the query to select from "moz_bookmarks t" first and that can quickly find the tags by "t.parent = ?1" and additionally filter out tags that don't have a "t.title IN (list of search tags)". This should be better than the original query which first finds places then decides for each place if it has a bookmark that matches any of the tags.

Comment 3

[Ed Lee :Mardak]

Attachment: v1.1

Unbitrotting from the patches upstream.. saves on some line changes but the query/logic is the same.

Comment 4

[Marco Bonardo [:mak] (Away Apr 25 - May 5)]

Comment on attachment 299857 [details] [diff] [review]
v1.1

these are the results from my tests:

with 18000 places i see a query gain of about 80ms (pure query, no output)

notice that the original query will execute the subquery    

(SELECT t.id FROM moz_bookmarks t WHERE t.parent = 4 AND (
  LOWER(t.title) = 'mozilla' OR LOWER(t.title) = 'minefield' OR LOWER(t.title) = 'random')))

and filtering moz_bookmarks on that, than joining (simple join) with moz_places and left joining with moz_favicons.
So it's basically doing the same thing as yours, that is because of the internal sqlite optimizer.

However the original query is selecting from moz_places JOIN moz_bookmarks and that is the real difference. 
If you change original query to do
    FROM moz_bookmarks b
    JOIN moz_places h ON h.id = b.fk

you will gain the same perf as your query, that is because the sqlite optimizer does not catch-in (so we gain 80ms on that really, not on query time)

Your query is doing before, what the internal sqlite optimizer will do after, so you are putting the tables in the right order, but will not gain any perf other than that (do you have some testcase where this performs far more than 80ms faster than original?)

notice also that you don't need to do LEFT JOINs there, they should be simple JOINs since you don't need to retain a tag without a bookmark or a bookmark without a place

we should take a decision on this:
- take the new query with 2 joins and IN
- invert the join order in the old query (and fix OR with IN that is more readable)

final result will be the same, an 80ms gain

imho we should mantain the original, invert the join and use IN, that should be more readable than a self join on moz_bookmarks

after a chat with Mardak i also tested the two queries with about 1000 search terms, results did not change from above.

Comment 5

[Ed Lee :Mardak]

Attachment: v1.2

LEFT JOIN -> JOIN, moved LOWER processing to sql.

Personally, the query makes more sense this way.. find bookmarks that have tagsfolder as parent, use those tags to find bookmarks that have the tag, from those bookmarks find pages that use the bookmark.

Comment 6

[Marco Bonardo [:mak] (Away Apr 25 - May 5)]

please remove the space after comma when using IN, it's good for readability but with long lists will make the string big without adding any useful info

Comment 7

[Ed Lee :Mardak]

Attachment: v1.3

(In reply to comment #6)
> please remove the space after comma when using IN, it's good for readability
> but with long lists will make the string big without adding any useful info
Sure thing. But I did one better! I got rid of the LOWERs as well so it'll turn into just LOWER(title) IN (?2,?3,?4,?5) etc.

Bug 414285 will provide the already-lowercase tokens.

Comment 8

[Marco Bonardo [:mak] (Away Apr 25 - May 5)]

nice, i'm fixing title since this query does not filter anything more than original, while it's still an optimization since it avoid sqlite internal optimizer overhead (and more)

Comment 9

[Ed Lee :Mardak]

Attachment: v1.4

Was selecting the wrong "b.title". The auto-bookmark from tagging isn't the same as the actual bookmark.

Comment 10

[Ed Lee :Mardak]

This will fix bug 416211.

Comment 11

[Ed Lee :Mardak]

Time it takes AutoCompleteTagsSearch to return with and without the patch for a various number of tag searches:

with: 25 ms 23 ms 22 ms 25 ms 23 ms 24 ms 23 ms 23 ms 24 ms 21 ms
without: 41 ms 39 ms 39 ms 38 ms 40 ms 39 ms 40 ms 39 ms 40 ms 40 ms

That's even with the extra join to select the correct bookmark title. So this will help speed up getting the initial batch of results.

Comment 12

[Ed Lee :Mardak]

The code doesn't exist since bug 401660 is fixed.

Comment 13

[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