[Zope-Coders] Sorting on Textindexes

[Andreas Jung]

sounds very good.

andreas

--On Montag, 12. Mai 2003 14:35 Uhr -0400 Casey Duncan <casey@zope.com> 
wrote:

> On Monday 12 May 2003 12:21 pm, Andreas Jung wrote:
>> Chris Withers came up with a case where it is impossible to sort by the
>> ranking of a ZCTextIndex query
>> when other indexes are involved (e.g. you perfrom a search on
>> SearchableText in combination
>> with a range search on a DateTime field). The underlaying problem is
>> that  the Catalog check for
>> the keyForDocument() method of an index to obtain a value from an index
>> to  be used for sorting.
>> This approach is ok for FieldIndexes but it sucks for text indexes
>> because  the relevant information
>> is part of the result set and can not be retrieved from the index itself.
>>
>> What about the following solution: indexes return either a sequence of
>> docids or a mapping
>> docid -> ranking.  We could introduce a tiny resultset class that could
>> be  used to wrap
>> the the mapping docid-> ranking. Of course this class would have a
>> method  keyForDocument().
>
> Currently, indexes either return a set of rids or a mapping of rid ->
> score.  The latter is the case for textindexes.  If the set is scored,
> then it is  sorted by score in C code, using the byValue BTree method.
>
> Otherwise, if a sort index is specified, the values are retrieved from
> the  index using keyForDocument or the new (as of 2.7) documentToKeyMap
> api which  buys about 15% performance improvement due to less call
> overhead.
>
>> In the sorting phase, the Catalog would either check for the standard
>> sequence/mapping of
>> docids or for the resultset class and call keyForDocument() either on
>> the  index or on the result
>> set. This approach has one drawback: it is necessary to store the
>> resultsets of the text indexes
>> because at the moment they are lost after performing the intersection of
>> the docids set from the
>> different subqueries.
>
> This proposal greatly limits potential opimizations, however. IMO, the
> catalog  should only do sorting if the index cannot provide a better
> method itself. I  want to move most of the sorting code to the indexes,
> since they know their  own internal data structures which can buy us
> orders of magnitude in sort  speed in certain cases, especially large
> result sets.
>
> IMO, textindexes should return two results. A set of result rids and a
> mapping  of rid -> score. The latter would support a standard sort
> interface (to be  determined). This interface might look like this:
>
> class ISorter(Interface):
>
>     def sort(catalog, set, reverse=0, limit=None, default=_marker):
>         """Given a catalog and a result set of catalog rids, sort the set
> according to the internal order of the sorter. Return an iterator of
> catalog  rids in order. For rids in the set that are not known to the
> sorter, use the default value, if specified as the sort key. Otherwise
> omit those rids from the output set. If set is None, then return an
> iterator of all rids known to the sorter in order. If limit is specified,
> return only the  number of results specified by limit"""
>
> FieldIndex, KeywordIndex and DateIndex (and all other UnIndex
> derivatives)  would implement this interface directly. Any index chosen
> as a sort index  would be checked for this interface first. If it
> implements it, sort would be  called, passing the filtered set or None
> for all documents (the latter is an  optimization for sorting the entire
> contents of the index).
>
> If an index does not implement this interface, then the catalog would
> attempt  to do sorting using keyForDocument as it does now.
>
> TextIndexes would generate a sorter on the fly, which would sort by the
> scores  generated by the query. The catalog could check for a marker
> interface or  somesuch to know that the index will send it a separate
> sorter. This sorter  would be kept around to do the sorting after the set
> operations were  complete.
>
> Eventually I would like to see the common case full sort code moved off
> into C  since it deals with C arrays of integers at the base already. But
> this would  be a good first step to get there. I already have some C code
> that increases  the scored sort for textindexes by a factor of 10. It
> just needs some polish  to integrate it into the BTree core code.
>
> Perhaps now is a good time for me to develop a real proposal for this?
> Its  been brewing since I did the last round of Catalog optimizations
> released in  2.6.1.
>
> -Casey
>
> _______________________________________________
> Zope-Coders mailing list
> Zope-Coders@zope.org
> http://mail.zope.org/mailman/listinfo/zope-coders