basho/riak_search — pull request #112 by rzezeski (2012-05-25 03:22:52+00:00)
Title: smarter AND query

This is still being benchmarked and could still use some general
cleanup but wanted to get the code out.

This work is based on section 4.3, Boolean query processing, of
"Managing Gigabytes" authored by Witten, Moffat and Bell.

The general idea is to not blindly read the postings list for every
term in parallel and do a linear merge-sort. For most conjunction
queries this is a huge waste of time and resources since the query
terms will have varying frequencies. In the worst case the query
contains one term that matches nothing and many other terms that match
a large number of docs. In that case the system is put under heavy
load when it could have ended the query after discovering the one term
matched nothing.

This patch does not accomplish everything outlined in the book. It
still performs linear comparison versus binary search and uses Merge
Index's faux term-frequency. In the future I would like to look at
adding in proper term-frequency and merging.

What _is_ implemented is the idea of ordering the terms by frequency
and performing them sequentially, each result feeding into the next.
From smallest to largest, each term is tried in turn to reach the
final result set. If the set becomes empty at any time the work halts
immediately, doing no more work than necessary. The following is an
overview of the new algorithm.

1. Create a query plan with frequency estimates.

2. Order the sub-queries by frequency in ascending order.

3. Run the first sub-query to determine the _candidate set_.

4. Feed the candidate set into the next sub-query, pushing it all the
way down to Merge Index as a filter to avoid unnecessary streaming of
data back up to the coordinator.

5. Take the resulting set and feed it into the next sub-query, repeat
until all sub-queries have been ran or until the set is empty

A nice aspect of this approach is that the candidate set can only get
_smaller_ as each sub-query processes it. If queries are very
selective then performance only gets better. The more terms involved
and the more frequency variance they have the better this algorithm
does. Also, pushing the filter down to Merge Index is important
because it avoids streaming _everything_ up to the coordinator and
thus taking all those network/heap copy hits in Erlang.