Re: Fwd: [bdbxml] Space Time Complexity - Performance issues

Manish Rai Jain wrote:
> In a scenario where the query is something like this:
> 
> where (some $someacc in $acc satisfies contains($someacc, "keyword"))
> or (some $sometax in $tax satisfies contains($sometax, "keyword"))
> or (some $someauthors in $authors satisfies contains($someauthors, 
> "keyword"))
> or (some $somescop in $scop satisfies contains($somescop, "keyword"))
> or (some $somenam in $nam satisfies contains($somenam, "keyword"))
> 
> If all the fields are properly indexed, in such a case, how will the 
> performance fare? That is, will it be proportional to the result set; or 
> it will depend upon some other factors etc.

Query complexity should be linear with regard to query size and document 
size. The only thing that complicates that is if the query planner 
determines that your query will need to be sorted due to an "order by" 
clause, or to implicit document-order sorting that cannot be eliminated. 
Sorting is obviously O(n log n).

John

-- 
John Snelson, Berkeley DB XML Engineer
Sleepycat Software, Inc
http://www.sleepycat.com

Contracted to Sleepycat through Parthenon Computing Ltd
http://blog.parthcomp.com/dbxml


------------------------------------------
To remove yourself from this list, send an
email to [email protected]