# [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