Merge lp:~lifeless/launchpad/malone into lp:launchpad

[Robert Collins]

Further improve the performance of bug duplicate detection by switching from | (any term matches) to & (all terms must match), with an expansion to handle one missing term.

This reduces over 90% of the overhead in tests so far, taking a 8second operation(on staging) down to 800msec.

I'm putting this up for review now to get feedback on the changes; I'm going to spin it up on staging and see if it delivers what it looks like it promises.

[Michael Hudson-Doyle (mwhudson)]

Is there a bug or spec you can reference in the XXX comments about introducing a better search? Otherwise it's fine.

review: Approve

[Robert Collins (lifeless)]

I will file a bug and reference before landing.

[Tim Penhey (thumper)]

u'(firefox&flickr&slow)|(flickr&slow)|(firefox&slow)|(firefox&flickr)'

Why have the (firefox&flickr&slow) term?

It will be covered by the other three.

[Robert Collins (lifeless)]

On Mon, Jul 26, 2010 at 2:53 AM, Tim Penhey <email address hidden> wrote:
> u'(firefox&flickr&slow)|(flickr&slow)|(firefox&slow)|(firefox&flickr)'
>
> Why have the (firefox&flickr&slow) term?
>
> It will be covered by the other three.

Ideally we'd iterate over the f&f&s, then the other terms, and expand
further. As for why, here - the same phrase is overloaded and used for
ranking, which means we do want the semantic statement as much/more
than the baseline work.

-Rob

[Tim Penhey (thumper)]

Changes look fine, although I'd love to see the doctest rewritten so it doesn't use sample data.

review: Approve

=== modified file 'lib/canonical/database/nl_search.py'
--- lib/canonical/database/nl_search.py	2010-07-21 19:55:38 +0000
+++ lib/canonical/database/nl_search.py	2010-08-02 02:36:50 +0000
@@ -73,17 +73,28 @@
 def _nl_phrase_search(terms, table, constraints, extra_constraints_tables):
     """Perform a very simple pruning of the phrase, letting fti do ranking.
 
+    This function groups the terms with & clause, and creates an additional
+    & grouping for each subset of terms created by discarding one term.
+
     See nl_phrase_search for the contract of this function.
     """
-    bad_words = set(['firefox', 'ubuntu', 'launchpad'])
     terms = set(terms)
-    filtered_terms = []
-    for term in terms:
-        if term.lower() in bad_words:
-            continue
-        filtered_terms.append(term)
-    # sorted for testing convenience.
-    return '|'.join(sorted(filtered_terms))
+    # Special cased because in the two-term case there is no benefit by having
+    # a more complex rank & search function.
+    # sorted for doctesting convenience - should have no impact on tsearch2.
+    if len(terms) < 3:
+        return '|'.join(sorted(terms))
+    # Expand
+    and_groups = [None] * (len(terms) + 1)
+    for pos in range(len(terms) + 1):
+        and_groups[pos] = set(terms)
+    # sorted for doctesting convenience - should have no impact on tsearch2.
+    for pos, term in enumerate(sorted(terms)):
+        and_groups[pos + 1].discard(term)
+    # sorted for doctesting convenience - should have no impact on tsearch2.
+    and_clauses = ['(' + '&'.join(sorted(group)) + ')'
+        for group in and_groups]
+    return '|'.join(and_clauses)
 
 
 def _slow_nl_phrase_search(terms, table, constraints,

=== modified file 'lib/canonical/launchpad/doc/textsearching.txt'
--- lib/canonical/launchpad/doc/textsearching.txt	2010-07-21 19:55:38 +0000
+++ lib/canonical/launchpad/doc/textsearching.txt	2010-08-02 02:36:50 +0000
@@ -549,10 +549,12 @@
 tsearch2 to_tsquery() already removes stop-words (it also stems the
 words). Relevance can be computed using the rank() or rank_cd()
 functions. These are not TD-IDF scoring functions, but they take into
-accounts where the words appeared (in the case of rank()) or proximity
+account where the words appeared (in the case of rank()) or proximity
 of the words (in the case of rank_cd()). Both scoring functions can
 normalize based on document length. So the only part left to implement
-is the >50% filtering part.
+is the >50% filtering part. Howevert the > 50% filtering is very expensive,
+and so is processing every single returned item (> 200000 for common queries
+on Ubuntu) - so we are disabling this and reworking from the ground up.
 
 
 === nl_term_candidates() ===
@@ -622,11 +624,17 @@
     >>> nl_phrase_search('how do I do this?', Question)
     ''
 
-The fast code path only removes firefox, ubuntu and launchpad today:
+The fast code path does not remove any terms. Rather it uses an & query over
+all the terms combined with an & query for each ordinal-1 subset of the terms:
 
     >>> nl_phrase_search('system is slow when running firefox on ubuntu',
     ...     Question)
-    u'run|slow|system'
+    u'(firefox&run&slow&system&ubuntu)|(run&slow&system&ubuntu)|(firefox&slow&system&ubuntu)|(firefox&run&system&ubuntu)|(firefox&run&slow&ubuntu)|(firefox&run&slow&system)'
+
+Short queries are expanded more simply:
+
+    >>> nl_phrase_search('system is slow', Question)
+    u'slow|system'
 
 
 ==== Using other constraints ====
@@ -655,10 +663,10 @@
     ...     ['Product'], fast_enabled=False)
     u'slow|flickr'
 
-When the query only has stop words or common words in it, the returned
-query will be the empty string:
+When the query only has stop words in it, the returned query will be the empty
+string:
 
-    >>> nl_phrase_search('ubuntu will not do it', Question)
+    >>> nl_phrase_search('will not do it', Question)
     ''
 
 When there are no candidate rows, only stemming and stop words removal
@@ -668,7 +676,7 @@
     0
     >>> nl_phrase_search('firefox is very slow on flickr', Question,
     ...                  'product = -1')
-    u'flickr|slow'
+    u'(firefox&flickr&slow)|(flickr&slow)|(firefox&slow)|(firefox&flickr)'
 
 
 ==== No keywords filtering with few rows ====
@@ -705,4 +713,4 @@
     ...     'firefox is slow', Question,
     ...     'distribution = %s AND sourcepackagename = %s' % sqlvalues(
     ...     ubuntu, firefox_package.sourcepackagename))
-    u'slow'
+    u'firefox|slow'

=== modified file 'lib/lp/answers/doc/emailinterface.txt.disabled'
--- lib/lp/answers/doc/emailinterface.txt.disabled	2010-07-28 17:25:30 +0000
+++ lib/lp/answers/doc/emailinterface.txt.disabled	2010-08-02 02:36:50 +0000
@@ -1,6 +1,6 @@
 = Answer Tracker Email Interface =
 
-The Answer TRacker has an email interface, although it's quite limited
+The Answer Tracker has an email interface, although it's quite limited
 at the moment. The only thing you can do is post new messages on the
 question. This is an important feature, though, since it ensures that if
 a user decides to reply to a question notification, his email won't be

=== modified file 'lib/lp/answers/doc/faq-vocabulary.txt'
--- lib/lp/answers/doc/faq-vocabulary.txt	2010-01-12 19:02:09 +0000
+++ lib/lp/answers/doc/faq-vocabulary.txt	2010-08-02 02:36:50 +0000
@@ -75,7 +75,7 @@
 
     >>> from zope.security import proxy
     >>> from canonical.launchpad.webapp.vocabulary import CountableIterator
-    >>> terms = vocabulary.searchForTerms('Problem showing SVG')
+    >>> terms = vocabulary.searchForTerms('extensions')
     >>> proxy.isinstance(terms, CountableIterator)
     True
     >>> terms.count()
@@ -83,6 +83,6 @@
     >>> for term in terms:
     ...     print term.title
     How do I troubleshoot problems with extensions/themes?
-    How do I install Java?
+    How do I install Extensions?
 
 

=== modified file 'lib/lp/answers/doc/faqtarget.txt'
--- lib/lp/answers/doc/faqtarget.txt	2010-07-28 16:56:05 +0000
+++ lib/lp/answers/doc/faqtarget.txt	2010-08-02 02:36:50 +0000
@@ -175,7 +175,6 @@
     >>> for faq in target.findSimilarFAQs('How do I use the Answer Tracker'):
     ...     print faq.title
     How to answer a question
-    How to use bug mail
     How to become a Launchpad king
 
 The results are ordered by relevancy. The first document is considered

=== modified file 'lib/lp/answers/doc/questiontarget.txt'
--- lib/lp/answers/doc/questiontarget.txt	2010-07-28 16:56:05 +0000
+++ lib/lp/answers/doc/questiontarget.txt	2010-08-02 02:36:50 +0000
@@ -359,10 +359,6 @@
     ...     print t.title
     New question
     Another question
-    Question title3
-    Question title2
-    Question title1
-    Question title0
 
 
 

=== modified file 'lib/lp/answers/stories/project-add-question.txt'
--- lib/lp/answers/stories/project-add-question.txt	2010-04-16 15:06:55 +0000
+++ lib/lp/answers/stories/project-add-question.txt	2010-08-02 02:36:50 +0000
@@ -62,7 +62,7 @@
 Firefox in English regarding SVG.
 
     >>> user_browser.getControl('Summary').value = (
-    ...     'Problem displaying complex SVG')
+    ...     'Problem with SVG')
     >>> user_browser.getControl('Continue').click()
 
 He's shown a list of similar questions related to the product Firefox

=== modified file 'lib/lp/answers/stories/question-add-in-other-languages.txt'
--- lib/lp/answers/stories/question-add-in-other-languages.txt	2010-07-22 05:48:07 +0000
+++ lib/lp/answers/stories/question-add-in-other-languages.txt	2010-08-02 02:36:50 +0000
@@ -41,10 +41,18 @@
 understood by any member of the support community.
 
     >>> similar_questions = find_tag_by_id(browser.contents, 'similar-questions')
-    >>> for row in similar_questions.findAll('tr', 'noted'):
-    ...     row.first('a').renderContents()
-    'Installation of Java Runtime Environment for Mozilla'
-    'Problema al recompilar kernel con soporte smp (doble-n\xc3\xbacleo)'
+    
+    XXX: Making search fast has a significant impact on this tests' use case,
+    because there are 9 terms - the query has to ignore 7 of the terms to
+    permit a hit under the new & based logic (which is needed for scaling).
+    When we push better relevance and cheap ordering into the core we will be
+    able to test this case again. Note that in production this exact use case
+    already finds nothing.
+
+    #>>> for row in similar_questions.findAll('tr', 'noted'):
+    #...     row.first('a').renderContents()
+    #'Installation of Java Runtime Environment for Mozilla'
+    #'Problema al recompilar kernel con soporte smp (doble-n\xc3\xbacleo)'
 
     >>> for tag in find_tags_by_class(browser.contents, 'warning message'):
     ...     print tag.renderContents()

=== modified file 'lib/lp/answers/stories/question-add.txt'
--- lib/lp/answers/stories/question-add.txt	2010-07-22 05:48:07 +0000
+++ lib/lp/answers/stories/question-add.txt	2010-08-02 02:36:50 +0000
@@ -66,8 +66,17 @@
 The user enters his problem summary and a list of similar FAQs and
 questions are displayed.
 
+XXX: Original search, disabled due to performance issues RBC 20100725. This
+will be reinstated when cheap relevance filtering is available / when search
+is overhauled.
+
     >>> user_browser.getControl('Summary').value = (
     ...     'Visiting a web page requiring java crashes firefox')
+
+For now, use a closer search:
+
+    >>> user_browser.getControl('Summary').value = (
+    ...     'java web pages')
     >>> user_browser.getControl('Continue').click()
     >>> contents = find_main_content(user_browser.contents)
     >>> similar_faqs = contents.find(id='similar-faqs')
@@ -122,7 +131,7 @@
 summary he provided.
 
     >>> user_browser.getControl('Summary').value
-    'Visiting a web page requiring java crashes firefox'
+    'java web pages'
 
 If the user doesn't provide details, he'll get an error message:
 

=== modified file 'lib/lp/answers/stories/this-is-a-faq.txt'
--- lib/lp/answers/stories/this-is-a-faq.txt	2009-12-05 17:10:59 +0000
+++ lib/lp/answers/stories/this-is-a-faq.txt	2010-08-02 02:36:50 +0000
@@ -6,6 +6,22 @@
 (a.k.a. Frequently Asked Question - FAQ) which can be used to answer
 a particular question.
 
+== Fix up sample data ==
+
+The sample data has question titles which perform poorly with the sample data's
+answers in fulltext searching, using efficient tsearch2 queries; we are going
+to overhaul the fulltext search implementation but in the interim less prose
+permits better matching. See bug 612384.
+
+    >>> from zope.component import getUtility
+    >>> from lp.registry.interfaces.product import IProductSet
+    >>> from lp.testing import login, logout
+    >>> login('[e-mail]')
+    >>> firefox = getUtility(IProductSet)['firefox']
+    >>> svg_question = firefox.getQuestion(2)
+    >>> svg_question.title = 'SVG extension'
+    >>> logout()
+
 
 == Linking to a FAQ ==
 
@@ -51,7 +67,7 @@
     >>> printFAQOptions(user_browser.contents)
     (*) No existing FAQs are relevant
     ( ) 9: How do I troubleshoot problems with extensions/themes?
-    ( ) 7: How do I install Java?
+    ( ) 8: How do I install Extensions?
 
     >>> print user_browser.getLink('How do I troubleshoot problems').url
     http://answers.launchpad.dev/firefox/+faq/9
@@ -61,13 +77,13 @@
 
     >>> search_field = user_browser.getControl(name='field.faq-query')
     >>> print search_field.value
-    Problem showing the SVG demo on W3C site
+    SVG extension
 
 From the titles, it doesn't seem like one of these FAQs would be
 appropriate. The user can modify the search query and hit the 'Search'
 button to update the list of available choices:
 
-    >>> search_field.value = 'Where can I find a SVG plugin'
+    >>> search_field.value = 'SVG plugin'
     >>> user_browser.getControl('Search', index=0).click()
 
 The page is updated with a new list of FAQs:
@@ -78,7 +94,6 @@
     (*) No existing FAQs are relevant
     ( ) 10: How do I install plugins (Shockwave, QuickTime, etc.)?
     ( ) 7: How do I install Java?
-    ( ) 8: How do I install Extensions?
 
 The most relevant result seems like the good answer, so the user selects
 it.
@@ -143,7 +158,7 @@
     ( ) No existing FAQs are relevant
     (*) 10: How do I install plugins (Shockwave, QuickTime, etc.)?
     ( ) 9: How do I troubleshoot problems with extensions/themes?
-    ( ) 7: How do I install Java?
+    ( ) 8: How do I install Extensions?
 
 He changes the message and click 'Link to FAQ'.
 
@@ -226,7 +241,7 @@
 edits them to be more appropriate:
 
     >>> print owner_browser.getControl('Title').value
-    Problem showing the SVG demo on W3C site
+    SVG extension
     >>> owner_browser.getControl('Title').value = 'Displaying SVG in Firefox'
 
     >>> print owner_browser.getControl('Content').value
@@ -308,10 +323,10 @@
     >>> print extract_text(find_portlet(
     ...     owner_browser.contents, 'Related questions'))
     Related questions
-    #2 Problem showing the SVG demo on W3C site
+    #2 SVG extension
 
     >>> print owner_browser.getLink(
-    ...     'Problem showing the SVG demo on W3C site').url
+    ...     'SVG extension').url
     http://answers.launchpad.dev/firefox/+question/2
 
 

=== modified file 'lib/lp/bugs/doc/bugtask-find-similar.txt'
--- lib/lp/bugs/doc/bugtask-find-similar.txt	2009-06-12 16:36:02 +0000
+++ lib/lp/bugs/doc/bugtask-find-similar.txt	2010-08-02 02:36:50 +0000
@@ -55,12 +55,12 @@
     >>> from canonical.launchpad.interfaces import IDistributionSet
     >>> ubuntu = getUtility(IDistributionSet).getByName('ubuntu')
     >>> similar_bugs = getUtility(IBugTaskSet).findSimilar(
-    ...     sample_person, "Thunderbird crashes when displaying SVG",
+    ...     sample_person, "Thunderbird SVG",
     ...     distribution=ubuntu)
     >>> for bugtask in similar_bugs:
     ...     print bugtask.bug.title
+    Firefox does not support SVG
     Thunderbird crashes
-    Firefox does not support SVG
 
 As well as limiting it to a specific source package:
 
@@ -94,7 +94,7 @@
     False
     >>> no_priv = getUtility(ILaunchBag).user
     >>> similar_bugs = getUtility(IBugTaskSet).findSimilar(
-    ...     no_priv, "Thunderbird chrashes when displaying SVG",
+    ...     no_priv, "Thunderbird SVG",
     ...     distribution=ubuntu)
     >>> for bugtask in similar_bugs:
     ...     print bugtask.bug.title
@@ -118,13 +118,16 @@
 results of the fulltext search on the Bug table, so bugs that have a
 summary or description that match the phrase will be displayed first.
 
+Due to the sample data assuming a way-to-wide search facility, this test
+has been narrowed - see bug 612384.
+
     >>> similar_bugs = getUtility(IBugTaskSet).findSimilar(
     ...     sample_person, "Another test bug for Thunderbird",
     ...     distribution=ubuntu)
     >>> for bugtask in similar_bugs:
     ...     print bugtask.bug.title
     another test bug
-    Thunderbird crashes
+    >>> #Thunderbird crashes
 
     >>> similar_bugs = getUtility(IBugTaskSet).findSimilar(
     ...     sample_person, "Another Thunderbird crash",
@@ -132,4 +135,4 @@
     >>> for bugtask in similar_bugs:
     ...     print bugtask.bug.title
     Thunderbird crashes
-    another test bug
+    >>> #another test bug

=== modified file 'lib/lp/bugs/doc/bugtask.txt'
--- lib/lp/bugs/doc/bugtask.txt	2010-07-21 19:55:38 +0000
+++ lib/lp/bugs/doc/bugtask.txt	2010-08-02 02:36:50 +0000
@@ -1365,7 +1365,6 @@
     >>> for similar_bug in sorted(similar_bugs, key=attrgetter('id')):
     ...     print "%s: %s" % (similar_bug.id, similar_bug.title)
     1: Firefox does not support SVG
-    4: Reflow problems with complex page layouts
     5: Firefox install instructions should be complete
 
 This also works for distributions...
@@ -1375,12 +1374,6 @@
     >>> for similar_bug in sorted(similar_bugs, key=attrgetter('id')):
     ...     print "%s: %s" % (similar_bug.id, similar_bug.title)
     1: Firefox does not support SVG
-    2: Blackhole Trash folder
-    9: Thunderbird crashes
-    10: another test bug
-    16: a test bug
-    17: a test bug
-    18: New Bug
 
 
 ... and for SourcePackages.
@@ -1394,7 +1387,6 @@
     >>> for similar_bug in sorted(similar_bugs, key=attrgetter('id')):
     ...     print "%s: %s" % (similar_bug.id, similar_bug.title)
     1: Firefox does not support SVG
-    18: New Bug
 
 Private bugs won't show up in the list of similar bugs unless the user
 is a direct subscriber. We'll demonstrate this by creating a new bug
@@ -1406,7 +1398,6 @@
     >>> for similar_bug in sorted(similar_bugs, key=attrgetter('id')):
     ...     print "%s: %s" % (similar_bug.id, similar_bug.title)
     1: Firefox does not support SVG
-    4: Reflow problems with complex page layouts
     5: Firefox install instructions should be complete
     ...Yet another Firefox bug
 
@@ -1420,7 +1411,6 @@
     >>> for similar_bug in sorted(similar_bugs, key=attrgetter('id')):
     ...     print "%s: %s" % (similar_bug.id, similar_bug.title)
     1: Firefox does not support SVG
-    4: Reflow problems with complex page layouts
     5: Firefox install instructions should be complete
 
 

=== modified file 'lib/lp/bugs/stories/guided-filebug/xx-distro-guided-filebug.txt'
--- lib/lp/bugs/stories/guided-filebug/xx-distro-guided-filebug.txt	2009-08-18 11:04:38 +0000
+++ lib/lp/bugs/stories/guided-filebug/xx-distro-guided-filebug.txt	2010-08-02 02:36:50 +0000
@@ -7,8 +7,12 @@
 
 Submitting a bug title...
 
+The example here are a little short - in reality we have a comprehensive
+database to find candidates from, our sample data has no real near-fits,
+see bug 612384 for the overall effort to provide a sensible search facility.
+
     >>> user_browser.getControl("Summary").value = (
-    ...     "Thunderbird crashes when opening large e-mails")
+    ...     "Thunderbird crashes opening")
     >>> user_browser.getControl("Continue").click()
 
 ...yields one similar bug.

=== modified file 'lib/lp/bugs/stories/guided-filebug/xx-product-guided-filebug.txt'
--- lib/lp/bugs/stories/guided-filebug/xx-product-guided-filebug.txt	2009-08-18 11:04:38 +0000
+++ lib/lp/bugs/stories/guided-filebug/xx-product-guided-filebug.txt	2010-08-02 02:36:50 +0000
@@ -24,7 +24,7 @@
 bugs.
 
     >>> user_browser.getControl("Summary").value = (
-    ...     "SVG images aren't displayed")
+    ...     "SVG images are broken")
     >>> user_browser.getControl("Continue").click()
 
 The form is self-posting, so the user is still at +filebug. This makes
@@ -92,7 +92,7 @@
 
     >>> user_browser.open("http://bugs.launchpad.dev/firefox/+filebug")
     >>> user_browser.getControl("Summary").value = (
-    ...     "SVG images aren't displayed")
+    ...     "SVG images are broken")
     >>> user_browser.getControl("Continue").click()
 
 As before, we get a list of similar bugs to choose from.
@@ -120,7 +120,7 @@
 
     >>> user_browser.open("http://bugs.launchpad.dev/firefox/+filebug")
     >>> user_browser.getControl("Summary").value = (
-    ...     "SVG images aren't displayed")
+    ...     "SVG images are broken")
     >>> user_browser.getControl("Continue").click()
 
 There's a hidden field on the "yes, this is my bug" form, which we can

=== modified file 'lib/lp/bugs/stories/guided-filebug/xx-sorting-by-relevance.txt'
--- lib/lp/bugs/stories/guided-filebug/xx-sorting-by-relevance.txt	2010-07-22 05:48:07 +0000
+++ lib/lp/bugs/stories/guided-filebug/xx-sorting-by-relevance.txt	2010-08-02 02:36:50 +0000
@@ -5,6 +5,11 @@
 reason, the search result is sorted by how well the given summary
 matches the bug's summary and description.
 
+These bugs used to return more hits, but the more restrictive search introduced
+to bandaid search scaling issues inhibits that in the sample data; when we get
+a relevance-integrated index we'll be able to do relevance ordered, limited
+searches efficiently and these tests can be expanded at that point.
+
     >>> user_browser.open("http://launchpad.dev/products/firefox/+filebug")
 
     >>> user_browser.getControl("Summary").value = (
@@ -16,10 +21,6 @@
     >>> print_bugs_list(user_browser.contents, "similar-bugs")
     #1 Firefox does not support SVG
     New (1 comment) last updated 2006-05-19...
-    Firefox needs to support embedded SVG...
-    #4 Reflow problems with complex page layouts
-    New (0 comments) last updated 2006-07-14...
-    Malone pages that use more complex layouts...
 
 If we instead enter a summary that matches bug #4 better, the result will
 be reversed.
@@ -27,16 +28,10 @@
     >>> user_browser.open("http://launchpad.dev/products/firefox/+filebug")
 
     >>> user_browser.getControl("Summary").value = (
-    ...     "Reflow problems when there are SVG images on the page")
+    ...     "Reflow problems with SVG")
     >>> user_browser.getControl("Continue").click()
 
     >>> print_bugs_list(user_browser.contents, "similar-bugs")
     #4 Reflow problems with complex page layouts
     New (0 comments) last updated 2006-07-14...
     Malone pages that use more complex layouts...
-    #1 Firefox does not support SVG
-    New (1 comment) last updated 2006-05-19...
-    Firefox needs to support embedded SVG...
-    #5 Firefox install instructions should be complete
-    New (0 comments) last updated 2006-07-14...
-    All ways of downloading firefox should provide complete...