Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris

Re^2: What DB style to use with search engine

by creamygoodness (Curate)
on Nov 11, 2009 at 16:43 UTC ( #806545=note: print w/replies, xml ) Need Help??

in reply to Re: What DB style to use with search engine
in thread What DB style to use with search engine

There is a good reaason why search engines don't allow full regex searches--they are simply too slow.

Yep. The way we typically implement a regex query against an inverted index is...

  1. Scan the over the whole term dictionary looking for terms that match the regex.
  2. Iterate over the posting lists (enumeration of doc ids that match) for all matching terms.

If too many terms match, that could end up being slower than a full table scan. Depending on implementation and index size, you could also end up running out of memory (e.g. if the posting lists are all iterated concurrently). Futhermore, that algo limits the scope of regex matches to individual terms.

Getting good performance out of indexed data is all about planning what queries you need in advance. Regexes are so flexible that they're hard to plan for.

  • Comment on Re^2: What DB style to use with search engine

Replies are listed 'Best First'.
Re^3: What DB style to use with search engine
by BrowserUk (Patriarch) on Nov 11, 2009 at 17:14 UTC
    that algo limits the scope of regex matches to individual terms.

    Allowing for post-wildcarded keywords stem* is relatively easy, especially if you limit the prefix to a minimum of (say) 3-chars or more.

    Where I had to provide for a pre & post wildcards, I built a trigram index (and insisted upon a minimum of 3 contiguous chars). That worked well, but required a substantial sized index.

    The one search engine I am familiar with that does allow full regex including term spanning is Google's codesearch. I'd love to see insights into how they do that. It's quite interesting to see the difference in the time it takes to do

    • for.*map lang:perl 0.6 seconds.
    • fo.*ap lang:perl 4.6 seconds.
    • lang:perl \$[abcd].+[pqrs] also 4.6 seconds.

    Really quite remarkable even given the massive parallelism. They must do some pretty clever parsing of the regexes in order to avoid searching the entire dictionary. I guess the code corpus is considerably smaller than the main set which will help a lot.

    That said: It makes you wonder why the OP doesn't just use Googles search engine?

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://806545]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (3)
As of 2023-03-24 04:01 GMT
Find Nodes?
    Voting Booth?
    Which type of climate do you prefer to live in?

    Results (60 votes). Check out past polls.