Implement galloping lookup for conjunctive queries
administrator2010-11-24 09:58
Need to modify
getWordSlice(&$next_offset, $last_offset, $len)
to
getWordNext($word_id, $next_doc_offset)
right now next_offset is just an offset into a posting list and it is slow
to do conjunctive queries. Instead, we want to allow lookup in the postings
of a $word_id based on a doc_offset, so that we return the next doc_offset containing that word_id with offset greater to or equal to $next_doc_offset.
Given the posting lists are in order we could binary search or use a galloping search to find this. We want to do this and rewrite intersect_iterator.php to use this to speed up conjunctive queries.
Need to modify getWordSlice(&$next_offset, $last_offset, $len)
to
getWordNext($word_id, $next_doc_offset)
right now next_offset is just an offset into a posting list and it is slow to do conjunctive queries. Instead, we want to allow lookup in the postings of a $word_id based on a doc_offset, so that we return the next doc_offset containing that word_id with offset greater to or equal to $next_doc_offset. Given the posting lists are in order we could binary search or use a galloping search to find this. We want to do this and rewrite intersect_iterator.php to use this to speed up conjunctive queries.
Fixed with check in ccdd8e8