Merge lp:~jtv/launchpad/bug-662552-defer-potmsgset-filter into lp:launchpad

Proposed by Jeroen T. Vermeulen on 2010-10-27
Status: Merged
Approved by: Brad Crittenden on 2010-10-27
Approved revision: no longer in the source branch.
Merged at revision: 11807
Proposed branch: lp:~jtv/launchpad/bug-662552-defer-potmsgset-filter
Merge into: lp:launchpad
Diff against target: 24 lines (+3/-4)
1 file modified
lib/lp/translations/model/ (+3/-4)
To merge this branch: bzr merge lp:~jtv/launchpad/bug-662552-defer-potmsgset-filter
Reviewer Review Type Date Requested Status
Brad Crittenden (community) code 2010-10-27 Approve on 2010-10-27
Review via email:

Commit message

Global-suggestions query plan tweak.

Description of the change

= Bug 662552: Query Plan Tweak =

This is another tweak for bug 662552: timeouts on POFile:+translate.

Our big time sink there is searching for global suggestions—available translations and suggestions for other POTMsgSets with the same msgid as the one we're looking at. As you'd expect, the query first looks for POTMsgSets with the same msgid but excepting the POTMsgSet we're looking at (the "inner query"). Then it looks for TranslationMessages for that POTMsgSet in the language we're looking at (the "outer query"). This gets very slow for some msgids.

In this branch I change the query to look first for any POTMsgSet with the same msgid (including the one we're already looking at), and then when searching for TranslationMessages, filter out ones for the same POTMsgSet we're already looking at. So I moved that filter from the inner query to the outer query. You'd think that that would be slower because it leaves the "outer" query with some rows that the inner query could already recognize as unwanted, but it's actually 2×—4× faster.

Here's what seems to happen: the inner query uses a bitmap heap scan on POTMsgSet to look for ones with the right msgid, excluding the one we're already looking at. I moved the latter check condition out of there, combining it with the outer join condition that's already there.

What is a bitmap scan? It's a trick developed by UPC in Barcelona. Instead of scanning through an index or table and gathering up all rows that match, it first does a separate pass to find matching rows. It keeps track of those in a long array of bits; for every matching row, the corresponding bit is set to 1. Then a second pass (shown in the query plan as the parent of the first pass) collects only the rows that have their bit in the array set.

Bitmap scans are an efficient way of dealing with intermediate selectivity: you don't expect to match so many rows that a sequential scan is the best you can do, but neither will there be so few that an index scan is optimal. Every matching row needs to be looked up in the actual table even when all relevant data is also in the index you're using (at least until index-only scans are implemented, but so far this has proven harder than it seems because of tuple visibility issues). There is generally no connection between index order and row storage order, so it's much more efficient to list all matching rows first and then read them all in storage order, than it is to seek randomly around the disk for matching rows as they come in from the index.

The bitmap scan is still in the plan after my tweak, just with one condition (msgid match) instead of two (msgid match and id filter). Why is it so much faster? I'm vague on the details, but as far as I can make out the id filter requires data that is not in the index, and so sabotages any opportunity to elide or defer the reading of actual rows from the table.

Query plan before the tweak:
Query plan after the tweak:

You'll notice that the speedup is hard to explain from the subplan timings. There may have been some cold-cache effects from running test queries on different database instances. The 2×—4× speedup estimate is based on warm-cache figures.


To post a comment you must log in.
Brad Crittenden (bac) wrote :

Thanks for the explanation, Jeroen. Like many database tweaks at this level it is a bit mysterious.

review: Approve (code)

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1=== modified file 'lib/lp/translations/model/'
2--- lib/lp/translations/model/ 2010-10-26 10:31:37 +0000
3+++ lib/lp/translations/model/ 2010-10-27 09:28:46 +0000
4@@ -360,6 +360,7 @@
5 else:
6 query = ["(NOT %s)" % in_use_clause]
7 query.append('TranslationMessage.language = %s' % sqlvalues(language))
8+ query.append('TranslationMessage.potmsgset <> %s' % sqlvalues(self))
10 query.append('''
11 potmsgset IN (
12@@ -370,10 +371,8 @@
13 JOIN SuggestivePOTemplate ON
14 TranslationTemplateItem.potemplate =
15 SuggestivePOTemplate.potemplate
17- <> %s AND
18- msgid_singular = %s
19- )''' % sqlvalues(self, self.msgid_singular))
20+ WHERE msgid_singular = %s
21+ )''' % sqlvalues(self.msgid_singular))
23 # Subquery to find the ids of TranslationMessages that are
24 # matching suggestions.