Hi all,

We are two Computer Science Master students at Utrecht University.

As part of our study, we are doing an experimentation project involving MonetDB.

We would like to enrich MonetDB by implementing some smart techniques to handle top-k queries.

So far, we have successfully implemented the Threshold Algorithm [Fagin] in MAL for a given top-k selection SQL query.

It already outperforms MonetDB's strategy (a naive strategy) if the dataset is large enough :)

The problem we are facing now is that almost all top-k techniques require sorted access on the attributes used in the score/ranking function.

And sorting a BAT in the MAL program is the real performance bottleneck in our MAL program right now.

We have had no success using indexes for sorted access because of the way MonetDB deals with these. We already thought of creating an extra table for each attribute used and insert every value in sorted order. This is a way to achieve sorted access on that attribute.

But, obviously, that is not the way to go. It would be feasible for one given SQL query and given data, but not as a general solution.

So the real question boils down to: (if possible) how can we get sorted access to an arbitrary attribute of a SQL table or a BAT without sorting it in MAL / MonetDB?

Thanks,

Maarten van Duren & Nik Schuiling