QueryParser scales as O(N*N) with AUTO_MULTIWORD_SYNONYM

[Richard Boulton]

I've just fixed various cases where the QueryParser scaled as O(N*N) where N is the number of terms in the query. However, there is one such case left, which involves parsing queries with the multiword synonym option.

Unlike the cases I've just fixed (which involved pair-wise construction of Query objects), the O(N*N) behaviour here appears to stem from searching for any of the synonyms in all the possible multiword substrings of the query. A callgrind run showed 500501 invocations of string::resize() from the query parser for a 1000 word query.

The current algorithm works by, for each starting point:

1. build a string containing all the subsequent words in the query
2. test for a synonym matching this string
3. (if no synonym found) cut off the last word in the string and go back to 2.

I'm not sure that the feature can be reduced to linear, but some possible optimisations might be:

• Don't bother looking for synonyms of more than 250 characters (or thereabouts), since there is a limit on the length of synonym keys of about this amount.

• keep track of the number of words in the longest multiword synonym key stored, and only bother testing for substrings of the query of at most this length. This alone should change the scaling to O(N*M), where M is the number of words in the longest synonym.

• Synonyms are stored in the btree in sorted order, so we can use synonym_keys_begin(prefix) to check if any synonyms exist with a given prefix. Then, we could check for a synonym based on the first word, and only progress to searching for one based on the first and second word if a possible candidate was found.

[Richard Boulton]

Fixed in trunk SVN HEAD (r10648), using the synonym_keys method.

[Olly Betts]

This was actually fixed in trunk r10684 (note: 84 not 48!)

Backported for 1.0.7 in r10746.