Re: 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. You'd be better only allowing keyword searches.

But, if you decide to try the big file route, a couple of things that will help are:

When concatenating your files, remove all the newlines so that each file becomes a single line prefixed by the path information.
This makes searching for phrases that span lines much simpler and much, much faster.
If you need to obtain position information, re-search the actual files once you've located them from the master file.
If you have multiple cores available, split the master into as many parts as you have cores and search them in parallel.
If you can distribute these parts across different spindles, you'll gain the maximum advantage of the parallelism. Otherwise, you may not see much benefit due to head thrash.
None the less, by making each file a single long line in the master, the ratio of cpu to IO will be greatly improved.
If your OS/filesystem allows you to override the default IO buffer size, increasing it to encompass the average (or maximum) line length may yield benefits.
Make your master file(s) contiguous if your filesystem allows that.

If you can limit a first pass to keywords only, then building an inverted index would be the fastest way of trimming the dataset. You could then allow a full regex search to be run on the subset of documents.

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.

RIP PCW It is as I've been saying!(Audio until 20090817)

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

Replies are listed 'Best First'.
Re^2: What DB style to use with search engine by halfcountplus (Hermit) on Nov 10, 2009 at 23:02 UTC
When concatenating your files, remove all the newlines so that each file becomes a single line prefixed by the path information. This makes searching for phrases that span lines much simpler and much, much faster. Excellent point, thanks for that. Vis optimizing on the server, I do not have root access and that may be a hassle, but I will keep this in mind once everything is finalized. I am sure the regexp is feasible on this scale -- as it is now, most of the work is using regexps to parse the tags out, which must be done, and it still performs usably fast. No matter how I database the data, it should be way, way, way quicker with the tags preprocessed out.	[reply]
Re^2: What DB style to use with search engine by creamygoodness (Curate) on Nov 11, 2009 at 16:43 UTC
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... Scan the over the whole term dictionary looking for terms that match the regex. 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.	[reply]
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. RIP PCW It is as I've been saying!(Audio until 20090817)	[reply] [d/l] [select]