Full_Name: Howard Chu
Version: 2.3
S:
URL:
Submission from: (NULL) (24.126.120.178)
Submitted by: hyc
The pcache code stores its list of queries in a singly linked list. As the
number of cached queries grows, it becomes extremely slow (quadratic) to
determine if an incoming query can be answered by any cached queries. This query
containment code needs to be re-designed.
As a simple optimization, for any query with either base scope, or sizelimit=1,
we can just pass it to the cacheDB immediately. If an entry is found, we're
done; otherwise we can pass it to the remote DB and cache it as appropriate.
It seems we need a pretty complex tree structure in order to store the queries
efficiently. The first step is to match the search base and scope; this can be
done in a DN-structured tree. Ideally we could just store this part in the
cacheDB itself, along with the cached entries, but the next step seems to make
this impractical. From the base/scope node we need to search for matching
filters, and the filters ought to be stored in their own tree structure as well.
Storing the filters in a multivalued attribute would just worsen their current
linear search characteristic