What is the time complexity of query a word in lucene?

Elastic Stack Elasticsearch
1

Hello!

please let me know what is the time complexity of query in lucene index .

for example, jus simple query to a index like

"localhost:9200/index1/_search?q={searchWord}"

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 .

2

What is the value of took in the response?

Was that at the first run? And was the index refreshed before you tested it?

3

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?

4

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.

ㄴ> seminar

i just found seminar that tells about finite state transfer which end up with O(logN). but not sure about it though

5

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)

6

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).
7

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

8

I cannot think of a better one than the Adrien Grand video you shared previously.