[jira] Issue Comment Edited: (LUCENE-1606) Automaton Query/Filter (scalable regex)

["Uwe Schindler (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/LUCENE-1606?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12700500#action_12700500 ] 

Uwe Schindler edited comment on LUCENE-1606 at 4/18/09 9:12 AM:
----------------------------------------------------------------

bq. I didn't do any of this because I wasn't sure if this constant score rewrite option is something that should be entirely left to the user, or not.

Yes, it should be normally be left to the user. And the slower filter on large indexes with only sparingly filled bitsets is related to LUCENE-1536.

E.g. I did some comparisions for TrieRangeQuery on a 5 mio doc index, integer field, 8 bit precision step (so about 400 terms per query), the filter is about double as fast. But the ranges were random and hit about 1/3 of all documents in average per query, so the bitset is not so sparse.
TrieRangeQuery is a typical example of a MultiTermQuery, that also works well with Boolean rewrite, because the upper term count is limited by the precision step (for ints and 8 bit the theoretical, but never reached, maximum is about 1700 terms, for lower precisionSteps even less).

      was (Author: thetaphi):
    Yes, it should be normally be left to the user. And the slower filter on large indexes with only sparingly filled bitsets is related to LUCENE-1536.

E.g. I did some comparisions for TrieRangeQuery on a 5 mio doc index, integer field, 8 bit precision step (so about 400 terms per query), the filter is about double as fast. But the ranges were random and hit about 1/3 of all documents in average per query, so the bitset is not so sparse.
TrieRangeQuery is a typical example of a MultiTermQuery, that also works well with Boolean rewrite, because the upper term count is limited by the precision step (for ints and 8 bit the theoretical, but never reached, maximum is about 1700 terms, for lower precisionSteps even less).
  
> Automaton Query/Filter (scalable regex)
> ---------------------------------------
>
>                 Key: LUCENE-1606
>                 URL: https://issues.apache.org/jira/browse/LUCENE-1606
>             Project: Lucene - Java
>          Issue Type: New Feature
>          Components: contrib/*
>            Reporter: Robert Muir
>            Priority: Minor
>             Fix For: 2.9
>
>         Attachments: automaton.patch, automatonMultiQuery.patch, automatonWithWildCard.patch, automatonWithWildCard2.patch
>
>
> Attached is a patch for an AutomatonQuery/Filter (name can change if its not suitable).
> Whereas the out-of-box contrib RegexQuery is nice, I have some very large indexes (100M+ unique tokens) where queries are quite slow, 2 minutes, etc. Additionally all of the existing RegexQuery implementations in Lucene are really slow if there is no constant prefix. This implementation does not depend upon constant prefix, and runs the same query in 640ms.
> Some use cases I envision:
>  1. lexicography/etc on large text corpora
>  2. looking for things such as urls where the prefix is not constant (http:// or ftp://)
> The Filter uses the BRICS package (http://www.brics.dk/automaton/) to convert regular expressions into a DFA. Then, the filter "enumerates" terms in a special way, by using the underlying state machine. Here is my short description from the comments:
>      The algorithm here is pretty basic. Enumerate terms but instead of a binary accept/reject do:
>       
>      1. Look at the portion that is OK (did not enter a reject state in the DFA)
>      2. Generate the next possible String and seek to that.
> the Query simply wraps the filter with ConstantScoreQuery.
> I did not include the automaton.jar inside the patch but it can be downloaded from http://www.brics.dk/automaton/ and is BSD-licensed.

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org