Suffix array performance problems
Jan 1st, 2005 by Phil Dawes
Hit some bad performance hotspots at work yesterday with the new suffix stuff.
The main problem occurs when you do text searches with multiple words, some of which are very popular. The query optimiser frequently makes a bad decision, which boils down to not being able to compute the permutations of the popular word, as it crosses 2 joins (suffixes->suffixlinks->triples) before exploding.
The biggest problem case was the word ‘drkw’ (i.e. the name of the company), which occurs in few suffixes (resulting in a good match on the index), but translates to many thousands of literals when linked through to the triplestore.
E.g. In a search for ‘drkw dam’, the optimiser favours using ‘drkw’ first, since it has fewer suffix index matches, whereas a search for dam would return just a few hundred eventual literals.
Claire’s gone to see a friend for a couple of hours, so have got some time to play with this…
Cool - think I’ve cracked it. The solution was to remove the original suffix and links tables, and replace them with a single suffixes table that just maps char(4) suffixes to literals.
This reduces the accuracy of the suffix match (meaning that substring searches > 4 chars need to join and filter with the nodes table (containing the literals). The width of the suffix field could be increased if this becomes a bottleneck, trading off more space for speed.
Have got the query down to 30ms on my laptop (down from 82.61 seconds on the original scheme). Other queries are looking good as well (mostly in the 10-30ms mark). Should fly on the 10GB 8 proc box at work
The reason this is so much faster is that the mysql query optimiser gets a better view of the number of literals each substring will match, and so correctly identifies the best match order. Also, by indexing the new suffix table both ways (suffix-literal and literal-suffix), the query analyser can chose to impose other constraints in between substring filtering
(e.g. reducing the literal matches to those that are rdfs:labels).
Now I just need to update the veudastore code to use the new scheme…
Have implemented the changes in veudastore - released version 0.3.
To use this with veudas, replace the cgi-bin/veudas-0.6/veudastore directory with this release
Hi !
Looking for a suffix index that would tell me what programs open files with what suffix. Such that it would tell me what program created on what programs would open files say with .jpg suffix.
Probably totally in the wrong place, but could you help?
Ed.
i’m HMT