On Mar 25, 2007, at 12:33 PM, Martijn Faassen wrote:
Jim Fulton wrote:
On Mar 25, 2007, at 3:01 AM, Adam Groszer wrote:
MF> I think one of the main limitations of the current catalog (and
MF> hurry.query) is efficient support for sorting and batching
MF> results. The Zope 3 catalog returns all matching results,
which can then
MF> be sorted and batched. This will stop being scalable for large
MF> collections. A relational database is able to do this
internally, and is
MF> potentially able to use optimizations there.
What evidence to you have to support this assertion?
I have the strong suspicion that modern relational databases are
currently better able to scale at queries using LIMIT and ORDER BY
than the Zope 3 catalog.
I had a similar suspicion. I assigned the Python Labs team the task
of finding out through literature search the approaches used. They
found that there were none other than the sorts of things I've
I cannot back this up as I haven't done measurements. Perhaps you
have done so?
We did a literature search.
* Do you estimate the performance of the Zope 3 catalog to be
equivalent to the performance of a modern relational database
system for queries that need to sort and batch their results?
I estimate that the same issues apply to both.
* If so, do you think it's just as easy for a developer to
accomplish such equivalent performance with the Zope 3 catalog as
it is with a relational database?
It depends on who the developer is. :) Using an alternative primary
key isn't obvious. Keeping extra sets of keys isn't supported in the
current index implementations.
I've made a number of assertions:
a) one of the main limitations of the current catalog and
hurry.query is efficient support for sorting and batching.
b) the Zope 3 catalog returns all matching results, which can then
be sorted and batched. This will stop being scalable for large
I'll amend b) by saying 'This will stop being scalable for large
result sets'. I agree that b) as stated above is incorrect as the
result set might be small, but I intended the amendment.
And I assumed it. I'll assert that even an N-best approach isn't
really scalable either. The only way I know of do scalable result
sorts is to use the primary keys or keep supplemental sort key data
in each of the indexes.
c) A relational database is able to do sorting and batching (limit
queries) internally, and is potentially able to use optimizations
Except that there aren't really any optimizations to use.
Which of these assertions are false?
The implied assertion that relational databases can do sorts scalably
on anything but a primary key.
Don't you think relational database system that has support for
sorting and batching built into its query API can at the very least
more easily use approaches to reduce sorting cost, by rewriting the
query, caching, and potentially employing special indexes?
I think it's conceivable, and with careful database design, even likely.
We did some literature search on this a few years ago and found no
special trick to avoid sorting costs.
I am at least cursorily aware of challenges surrounding efficient
querying and batching. I am not looking for a special trick or
magic bullet. I'd just like more help in avoiding sorting cost in a
typical situation where results are displayed in a batched format.
But the primary issue isn't really batching. An N-best algorithm cab
reduce sort cost a lot, but not enough to be scalable.
If a catalog query returns 1 million results, which I want to show
in batches of 10, sorted by some property of the results, I would
like to reduce the costs. Currently the pattern I (and I imagine
others) employ is to re-execute the query and then sort these
results in memory for each batch, for each request.
No, the current state of the art is to do an N-best operation on the
result. I'm 99% some Zope catalog code does this. My point is that
this isn't good enough.
[you list some approaches to reduce sorting cost]
I would like some system that helps me reduce some of these costs,
using the approaches you list, or at least some caching somewhere.
I would imagine a relational database for instance can employ
caching of result sets, so that if no writes occurred, a second
LIMIT query asking for a different range will return results a lot
Apparently the catalog does support N-best, you state later in this
I'm pretty sure that that is the case. I know we built it into
How does one use this support? Can I add it to hurry.query somehow?
Heck if I know. I haven't worked with catalog code for a long time. :)
Look at zope.index.nbest.
Perhaps all this is not the reponsibility of the catalog itself,
but a system surrounding it. As long as it's obviously there for
people to use.
Certainly, n-best should generally be integrated into searching code.
An n-best algorithm helps, but it doesn't really achieve scalability.
Perhaps however I am seeing problems that aren't there?
I think you are seeing solutions that aren't there, or at least
aren't as straightforward as you (or people misinterpreting your
statements) might expect.
Do you think there is no problem and we have parity with relational
database implementations here?
Obviously, in general, we don't have parity with RDBMSs on query
My main point is that there is no simple way to do sorting scalably.
Sorting is a trap that I've seen many projects fall into. People
expect that because the catalog has some sort of sorting capability
or because SQL has sorting keywords that somehow the "experts" have
figured out how to make it go fast "automatically".
Do you think the current situation cannot be improved much further?
For some definition of "much" yes, I think it can't be improved much
further wrt sorting. Scalable sorting is going to have a major
impact on an application design. It will be disruptive. We can
better educate people about that.
Do you think any further improvements are not worth the costs?
I think further improvements are warrented, but they will not achieve
the goal that many people expect.
Jim Fulton mailto:[EMAIL PROTECTED] Python
CTO (540) 361-1714
Zope Corporation http://www.zope.com http://www.zope.org
For more information about ZODB, see the ZODB Wiki:
ZODB-Dev mailing list - ZODB-Dev@zope.org