[Zope-Coders] Sorting on Textindexes

[Casey Duncan]

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=
=20
> ranking of a ZCTextIndex query
> when other indexes are involved (e.g. you perfrom a search on=20
> SearchableText in combination
> with a range search on a DateTime field). The underlaying problem is th=
at=20
> the Catalog check for
> the keyForDocument() method of an index to obtain a value from an index=
 to=20
> be used for sorting.
> This approach is ok for FieldIndexes but it sucks for text indexes beca=
use=20
> the relevant information
> is part of the result set and can not be retrieved from the index itsel=
f.
>=20
> What about the following solution: indexes return either a sequence of=20
> docids or a mapping
> docid -> ranking.  We could introduce a tiny resultset class that could=
 be=20
> used to wrap
> the the mapping docid-> ranking. Of course this class would have a meth=
od=20
> keyForDocument().

Currently, indexes either return a set of rids or a mapping of rid -> sco=
re.=20
The latter is the case for textindexes.  If the set is scored, then it is=
=20
sorted by score in C code, using the byValue BTree method.

Otherwise, if a sort index is specified, the values are retrieved from th=
e=20
index using keyForDocument or the new (as of 2.7) documentToKeyMap api wh=
ich=20
buys about 15% performance improvement due to less call overhead.

> In the sorting phase, the Catalog would either check for the standard=20
> sequence/mapping of
> docids or for the resultset class and call keyForDocument() either on t=
he=20
> index or on the result
> set. This approach has one drawback: it is necessary to store the=20
> resultsets of the text indexes
> because at the moment they are lost after performing the intersection o=
f=20
> the docids set from the
> different subqueries.

This proposal greatly limits potential opimizations, however. IMO, the ca=
talog=20
should only do sorting if the index cannot provide a better method itself=
=2E I=20
want to move most of the sorting code to the indexes, since they know the=
ir=20
own internal data structures which can buy us orders of magnitude in sort=
=20
speed in certain cases, especially large result sets.

IMO, textindexes should return two results. A set of result rids and a ma=
pping=20
of rid -> score. The latter would support a standard sort interface (to b=
e=20
determined). This interface might look like this:

class ISorter(Interface):

    def sort(catalog, set, reverse=3D0, limit=3DNone, default=3D_marker):
        """Given a catalog and a result set of catalog rids, sort the set=
=20
according to the internal order of the sorter. Return an iterator of cata=
log=20
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 th=
e=20
number of results specified by limit"""

FieldIndex, KeywordIndex and DateIndex (and all other UnIndex derivatives=
)=20
would implement this interface directly. Any index chosen as a sort index=
=20
would be checked for this interface first. If it implements it, sort woul=
d be=20
called, passing the filtered set or None for all documents (the latter is=
 an=20
optimization for sorting the entire contents of the index).=20

If an index does not implement this interface, then the catalog would att=
empt=20
to do sorting using keyForDocument as it does now.

TextIndexes would generate a sorter on the fly, which would sort by the s=
cores=20
generated by the query. The catalog could check for a marker interface or=
=20
somesuch to know that the index will send it a separate sorter. This sort=
er=20
would be kept around to do the sorting after the set operations were=20
complete.

Eventually I would like to see the common case full sort code moved off i=
nto C=20
since it deals with C arrays of integers at the base already. But this wo=
uld=20
be a good first step to get there. I already have some C code that increa=
ses=20
the scored sort for textindexes by a factor of 10. It just needs some pol=
ish=20
to integrate it into the BTree core code.

Perhaps now is a good time for me to develop a real proposal for this? It=
s=20
been brewing since I did the last round of Catalog optimizations released=
 in=20
2.6.1.

-Casey