[FT] FTTimes from m to n

Dear editors,

If I have XML data:
<book>A B A B A C B</book>
and query:
/book ftcontains "A" && "B" occurs from 2 to 3 times

FTWords ("A") will return 3 matches at position (1) (3) (5).
FTWords ("B") will return 3 matches at position (2) (4) (7).
FTAnd will return 9 matches at position (1,2) (1,4) (1,7) (3,2) (3,4) 
(3,7) (5,2) (5,4) (5,7)

According to the semantics, "occurs from 2 to 3 times" is evaluated by 
"occurs at least 2 times && ! occurs at least 4 times".
Now if we evaluate "! occurs at least 4 times":
FTTimes "occurs at least 4 times" has 9 input matches, and will produce 
126 output matches.
After eliminating duplication, we get (numbers in parenthesis are word 
positions) 13 output matches:

AllMatches
--- Match (1,2,3,4,7)
--- Match (1,2,3,4,5,7)
--- Match (1,2,4,5,7)
--- Match (1,2,4,5)
--- Match (1,2,3,4)
--- Match (1,2,3,7)
--- Match (1,2,3,4,5)
--- Match (1,2,3,5,7)
--- Match (1,2,5,7)
--- Match (1,3,4,7)
--- Match (1,3,4,5,7)
--- Match (2,3,4,5,7)
--- Match (2,3,5,7)

If we apply FTUnaryNot on this AllMatches, because the first Match has 5 
StringMatches, the second Match has 6 StringMatches, and so on, we will 
have:
5 x 6 x 5 x 4 x 4 x 4 x 5 x 5 x 4 x 4 x 5 x 5 x 4 = 384 million
possible combinations of StringMatches. Even if we do not materialize 
these combinations at one time, the potential computation is huge. And 
the query evaluation is only half way.

This is simple query and simple data. But evaluating this query may 
incur such a a huge computation. What if "A" and "B" happen 10 times 
each in /book?
My question is: Is my evaluation correct? If it is correct, would it be 
nice if we could simplify the semantics of FTTimes, FTUnaryNot, etc.? Or 
is there a lot of places to optimize?

Thanks,
Andrew

Received on Monday, 30 May 2005 23:48:34 UTC