Implementing sorting by one field and filtering by another


#1

I am looking into using FoundationDB and maybe writing a layer to work as a database system backend for my SaaS.

What I can’t figure out is, if I use key-value pairs to create indexes, how could I filter by one field with one index and then sort by another with another index.

The only way I can think is to create a composite index of the two fields. But what if there are too many fields and the user can sort/filter by any?


(Ryan Worl) #2

You can use two indexes at the same time. For example, you could retrieve all the records matching the filter condition, then do individual look-ups for the matching records and perform the sorting yourself in memory. You could also use one index to retrieve a set of sorted records, and then do individual key look-ups to evaluate the filter. You could also create the composite index, but that is not as flexible, as you’ve already discovered.

Knowing which one of these is the best solution 1) for your application specifically, and 2) which to choose at runtime in a database are two different issues. The latter is a field of database research called query optimization, and the typical first implementation is a basic heuristics-based query optimizer to choose what index to use for a given query, followed by replacing it with a cost-based optimizer which uses statistics to choose a more efficient (usually) ordering of indexes, and if to use an index at all.

Some queries, when expressed as scanning one index and doing key look-ups in another, are more efficiently done as full table scans. A simple example is if your index situation required a key look-up for each row in the table. It would obviously be more efficient to just scan the records in order as you get the benefits of sequential IO instead of random IO.

This question is complicated and unfortunately doesn’t have any easy answer that isn’t application-specific.


#3

Thank you for explaining! It is similar to what I thought … it doesn’t have a simple solution that can be applied to every case.