[lucy-user] Lucy Knowledge Questions

[kasilak <ka...@gmail.com>]

Copying Nick's responses on technical Questions

(1) What is the data structure used to represent Lexicon? (Clownfish
supports hashtable. Does it mean Lucy uses hashtable?)
Lexicon is essentially a sorted on-disk array that is searched with binary
search. Clownfish::Hash, on the other hand, is an in-memory data structure.
Lucy doesn't build in-memory structures for most index data because this
would incur a huge startup penalty. This also makes it possible to work with
indices that don't fit in RAM, although performance deteriorates quickly in
this case.

(2) What is the data structure used to represent postings? (Clownfish
supports hashtable. Does it mean Lucy uses hashtable?)
Posting lists are stored in an on-disk array. The indices are found in
Lexicon.

(3) Which compression method is used? Is it enabled by default?
Lexicon and posting list data is always compressed with delta encoding for
numbers and incremental encoding for strings.

(4) Can I know whether searching through lexicon/posting list is in-memory
process or IO process?
Lucy uses memory-mapped files to access most index data so the distinction
between in-memory and IO-based operation blurs quite a bit.
==============================
Hi Nick:

I have follow up questions based on the above thread.
(1)  You have mentioned above in your response, that Lexicon/Postings are
stored as sorted on-disk array with binary search. Is the sorted array is
represented as a binary tree (underlying data structure)? Is the binary
search is binary tree search? Can I point me to "C" source code where this
is done?

(2) While performing searches on a indexed cf.dat, is there a fixed cost to
decompress the "delta encoded numbers and strings"?

(3) I am taking measurements using my toy benchmark. I have indexed 10,000
documents. In the IxSearcher_Hits, I am changing the num_wanted for the
given query string. My expectation was changing the num_wanted shouldn't
affect the performance (measured using QPS "time taken to search and report
the query in queries per second (QPS)").
On the contrary what I am observing is when the num_wanted is set to 10
hits, then the QPS is higher in comparison with num_wanted is set to 4000
hits. 
If the TF/IDF (term frequency/inverse document frequency) ranking is
constructed always and will report the top 10 hits or top 4000 hits,  then
my expectation is QPS shouldn't change. 
"The only explanation I have is the difference in QPS is because in the case
of 10 hits the search stops as soon as the IxSearcher_Hits found 10 hits
(disregarding the ranking algorithm) and in the case of 4000 hits, it will
continue and stop as soon as 4000 hits or maximum the application can find.
This means IxSearcher_Hits doesn't use any inherent ranking to return the
relevant documents. Is my theory right?"






--
View this message in context: http://lucene.472066.n3.nabble.com/Lucy-Knowledge-Questions-tp4321879.html
Sent from the lucy-user mailing list archive at Nabble.com.

Re: [lucy-user] Lucy Knowledge Questions

[Nick Wellnhofer <we...@aevum.de>]

On 23/02/2017 01:07, kasilak wrote:
> (1)  You have mentioned above in your response, that Lexicon/Postings are
> stored as sorted on-disk array with binary search. Is the sorted array is
> represented as a binary tree (underlying data structure)? Is the binary
> search is binary tree search?

No, it's the classic binary search algorithm that works on a sorted array:

     https://en.wikipedia.org/wiki/Binary_search_algorithm

> Can I point me to "C" source code where this
> is done?

It's implemented in LexIndex_Seek:

 
https://git1-us-west.apache.org/repos/asf?p=lucy.git;a=blob;f=core/Lucy/Index/LexIndex.c;h=0d7a0ea4f4d4f2d720df13be2919691d0977c8ab;hb=HEAD#l141

> (2) While performing searches on a indexed cf.dat, is there a fixed cost to
> decompress the "delta encoded numbers and strings"?

What do you mean by "fixed cost"?

> (3) I am taking measurements using my toy benchmark. I have indexed 10,000
> documents. In the IxSearcher_Hits, I am changing the num_wanted for the
> given query string. My expectation was changing the num_wanted shouldn't
> affect the performance (measured using QPS "time taken to search and report
> the query in queries per second (QPS)").
> On the contrary what I am observing is when the num_wanted is set to 10
> hits, then the QPS is higher in comparison with num_wanted is set to 4000
> hits.
> If the TF/IDF (term frequency/inverse document frequency) ranking is
> constructed always and will report the top 10 hits or top 4000 hits,  then
> my expectation is QPS shouldn't change.
> "The only explanation I have is the difference in QPS is because in the case
> of 10 hits the search stops as soon as the IxSearcher_Hits found 10 hits
> (disregarding the ranking algorithm) and in the case of 4000 hits, it will
> continue and stop as soon as 4000 hits or maximum the application can find.
> This means IxSearcher_Hits doesn't use any inherent ranking to return the
> relevant documents. Is my theory right?"

No, IxSearcher_Hits always returns sorted documents. The search process can be 
divided into three steps:

1. Find all N documents matching a query.
2. Find and sort the top M documents according to the SortSpec. Lucy
    uses a priority queue implemented as a heap (HitQueue), so time
    complexity is O(N * log(M)).
3. Retrieve the stored fields for each of the top M documents.

Steps 2 and 3 are obviously faster for smaller values of M.

Nick