[Zope-dev] Sorting for zope.index

[Chris McDonough]

Dan Korostelev wrote:
> 2008/12/27 Chris McDonough <chrism at plope.com>:
>> Dan Korostelev wrote:
>>> I also made an implementation for the FieldIndex that may not be too
>>> optimal, but I'm currently most interested in clean and universal
>>> IIndexSort definition that any index could efficiently implement.
>> I've done this work too... but outside zope.index... please see (for example):
>>
>> http://svn.repoze.org/repoze.catalog/trunk/repoze/catalog/indexes/field.py
>>
>> It's reasonably optimized.
> 
> Thanks for the point. That's something I was going to write to add
> optimizations for FieldIndex sorting, now I only need to adapt your
> code and that's great! :-)

There are many tests in there too.  Note that the algorithms came mostly from
the Zope 2 Catalog code.  The only things I'm less than sure about in there is:

- the computation of when to use n-best and lazy (there are constants in there
  stolen from Zope 2).

- The fact that when we need to sort in reverse order we can't be lazy.
  I.e. in the branch that reads:

     # If the result set is not much larger than the number
     # of documents in this index, or if we need to sort in
     # reverse order, use a non-lazy sort.

  BTree values can't be iterated in reverse order, that's why we don't try
  the lazy case here if it's a reverse sort.  There may be a better way to
  do this.


> However, the more important thing for now is the IIndexSort interface
> declaration. Is it okay and fits any possible sortable index? ;-)
> 

It looks like we came up with the same interface independently; I think that's a
good sign.

- C