February 13, 2023, 1:21pm
please let me know what is the time complexity of query in lucene index .
for example, jus simple query to a index like
I know it is inverted index , but i think O(1) doesn't make sense because when i run performance test on es cluster, it was slow though .
February 13, 2023, 2:16pm
it was slow though
What is the value of
took in the response?
Was that at the first run? And was the index refreshed before you tested it?
What is the size and hardware specification of the cluster?
How large is the index you are querying? What is the size and complexity of your documents?
February 13, 2023, 2:43pm
Thank you for replying ! Each test was run 100 time repeatedely
But what i want to know was
" i experienced if there are more docs on one index, tps goes down even though there are not much disk id difference. so I think time complexity of term query should not be O(1) , because size affect performance"
I learned that main concern of tuning elasticsearch is make low disk io which is main performance issue,
but i want to know pure time complexity of term query of lucene or elasticsearch besides disk io.
i just found seminar that tells about finite state transfer which end up with O(logN). but not sure about it though
February 13, 2023, 2:47pm
i was trying to write post about elasticsearch. so I dont need to tuning es cluster now.
I was wondering time complexity of term query. because there are less resources bout it, and some blog post said that time complexity of term query is O(1) , but i think not .
Because i saw several times size of index affect performance even though there's not much disk io difference ( it might be my mistake)
Roughly speaking, costs are:
Linear with the number of Lucene segments (all segments are searched)
Sub-linear with number of unique terms in a segment (index structure can lookup terms efficiently)
Linear with the number of docs that contain a term (each doc’s TF is considered for relevance scoring).
February 14, 2023, 12:47am
Thank you. yes, document and term size does matter in performance.
Can you give me some resources about it? just for curiosity, I want to sure more
I cannot think of a better one than the Adrien Grand video you shared previously.
March 14, 2023, 9:10am
This topic was automatically closed 28 days after the last reply. New replies are no longer allowed.