The text below is a cross-post to this list from the a recent chandlerdb blog
post http://blogs.osafoundation.org/chandlerdb/2006/01/using_collectio.html
as per Ted's request.
Andi..
---------------------------------------------------------------------------
January 24, 2006
Using collection indexes to find items
During last week's sprints I was asked to see how easy it was to import mail
into Chandler from a local mailbox. Thanks to Python's mailbox and email
packages, the mailbox parsing was trivial. Similarly, Chandler's domain
model can represent email items and has a number of APIs that make creating
such items from a raw email string very easy.
Unexpectedly, importing mail messages was very slow however, and was getting
worse as more messages were added to the repository. The first cause of
slowness was easily resolved by turning off 'bz2' compression of all the
text LOBs being created.
The second cause of slowness was more surprising though. It had to do with
looking up existing email address items from the email addresses occurring
in the headers of the messages being imported. The EmailAddress item class
defined here has a class method called getEmailAddress() that will linearly
iterate all EmailAddresses instances every time such an item is sought. The
mailbox I was trying to import contains about 6,500 mails with 800 unique
email addresses. Linearly searching them won't scale.
In the early days of the repository we had planned on having a query system
and Ted even implemented a query language not unlike one you'd encounter in
an SQL database. Last year, while working on Chandler 0.6, it occurred to us
that a formal query language in a Python-based system was somewhat redundant
and that we should be using computed collections instead of queries
altogether to accomplish the same goals . Hence abstract sets and their item
wrappers were implemented.
By combining abstract sets, collections and indexes - something I had added
to bi-directional reference collections during the Chandler 0.5 release - we
realized we could get very decent item look-up performance as well as cache
the computed aspect of abstract sets making membership tests and iteration
also considerably faster.
This technique can be illustrated with the example below taken from the
EmailAddress index I added during last week's sprints.
* First, a collection needs to be setup. This can be as simple as a
bi-directional reference collection, an abstract collection of all
items of a given kind or a more complicated computed collection
combining or filtering other collections. In the EmailAddress example,
I just created a KindCollection instance based on the EmailAddress
kind. In the app parcel I added yet another collection called
emailAddressCollection.
emailAddressCollection = \
KindCollection.update(parcel, 'emailAddressCollection',
kind=pim.mail.EmailAddress.getKind(view),
recursive=True)
* Then, a sorted index needs be added to the collection. I wanted to be
able to find existing email addresses such that no two email address
items in the collection have the same lowercase internet email address
string. For this purpose, I added the _compareAddr() method to the
EmailAddress class in the mail parcel:
def _compareAddr(self, other):
return cmp(self.emailAddress.lower(), other.emailAddress.lower())
and the index creation call after the code creating the collection:
emailAddressCollection.rep.addIndex('emailAddress', 'compare',
compare='_compareAddr')
which creates a 'compare' index called 'emailAddress', an index
calling a method called '_compareAddr' on the items it is comparing.
* And finally to use this collection and the index to find items I added
a findEmailAddress() class method to the EmailAddress class:
@classmethod
def findEmailAddress(cls, view, emailAddress):
collection = schema.ns("osaf.app",
view).emailAddressCollection.rep
emailAddress = emailAddress.lower()
def compareAddr(key):
return cmp(emailAddress, view[key].emailAddress.lower())
uuid = collection.findInIndex('emailAddress', 'exact',
compareAddr)
if uuid is None:
return None
return view[uuid]
The findInIndex() call looks for an exact match as per the compareAddr
local function which compares lowercase versions of internet address
strings.
The technique above replaces the linear search with a binary search yielding
a very noticeable performance improvement in the overall importing of email
messages into the repository.
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Open Source Applications Foundation "Dev" mailing list
http://lists.osafoundation.org/mailman/listinfo/dev
