Fwd: [bdbxml] Space Time Complexity - Performance issues

---------- Forwarded message ----------
From: Manish Rai Jain <[email protected]>
Date: Sep 13, 2005 11:08 AM
Subject: Re: [bdbxml] Space Time Complexity - Performance issues
To: George Feinberg <[email protected]>

Thanks George! This will surely help :).
Just to clarify more, 

In general, a well-written query with a good index will take
> time/space proportional to the number of results.
> 

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. 

Regards
Manish

On 9/13/05, George Feinberg <[email protected]> wrote:
> 
> 
> Manish,
> 
> These are large, open-ended questions. It's possible
> to provide information, but not precise numbers.
> 
> 
> > Hi all
> > I wanted to know what is the space time complexity (or performance 
> > limits) for
> > 1. Querying across a container with n documents (Indexed)
> 
> With the proper query and index, this may be resolved with
> a single index lookup operation (btree lookup) and fetching
> of the target document(s). 
> In general, a well-written query with a good index will take
> time/space proportional to the number of results.
> 
> Without a proper index and/or query, this could iterate through
> the entire container, examining each document. 
> 
> > 2. Querying across a container with n documents (non-Indexed)
> 
> Best-case, this is proportional to the number of documents. A nasty
> query can be very slow.
> 
> > 3. Cross-querying across 2 containers having m and n documents 
> > (Indexed)
> 
> This is close to the same as (1) with good indexes, except there
> will be 2 index lookups (one per container), not one.
> 
> > I want to know the theoretical limits of these queries. Also, it wd 
> > be great if you can fwd me some experimentation values etc. or any
> > other documents which provide info abt the theoretical limits of
> > querying, indexing, and population.
> 
> The limits, theoretical and not, vary widely with the queries involved. 
> Even with good indexes, it's possible to construct a query that exceeds
> time/space available.
> 
> Some hard limits in the current product:
> o document IDs are 32-bit, so that limits number of documents in 
> a container.
> o there are no hard limits on number of containers
> o size of a container is limited by the file system's maximum
> file size,
> which is platform-specific.
> 
> Regards,
> 
> George 
> 
>