# What is the time complexity of query a word in lucene? **URL:** \ **Category:** Elasticsearch\ **Created:** [February 13, 2023, 1:21pm UTC](https://discuss.elastic.co/t/what-is-the-time-complexity-of-query-a-word-in-lucene/325385 "2023-02-13T13:21:06Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![dan\_kim](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/dan_kim/32/95741_2.png) [@dan\_kim](https://discuss.elastic.co/u/dan_kim)\ **Post date:** [February 13, 2023, 1:21pm UTC](https://discuss.elastic.co/t/what-is-the-time-complexity-of-query-a-word-in-lucene/325385/1 "2023-02-13T13:21:06Z")
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 . ---
**Author:** ![dadoonet](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/dadoonet/32/137187_2.png) [@dadoonet](https://discuss.elastic.co/u/dadoonet)\ **Post date:** [February 13, 2023, 2:16pm UTC](https://discuss.elastic.co/t/what-is-the-time-complexity-of-query-a-word-in-lucene/325385/2 "2023-02-13T14:16:57Z")
> [@dan\_kim](#): > > 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? ---
**Author:** ![Christian\_Dahlqvist](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/christian_dahlqvist/32/4617_2.png) [@Christian\_Dahlqvist](https://discuss.elastic.co/u/Christian_Dahlqvist)\ **Post date:** [February 13, 2023, 2:42pm UTC](https://discuss.elastic.co/t/what-is-the-time-complexity-of-query-a-word-in-lucene/325385/3 "2023-02-13T14:42:11Z")
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? ---
**Author:** ![dan\_kim](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/dan_kim/32/95741_2.png) [@dan\_kim](https://discuss.elastic.co/u/dan_kim)\ **Post date:** [February 13, 2023, 2:43pm UTC](https://discuss.elastic.co/t/what-is-the-time-complexity-of-query-a-word-in-lucene/325385/4 "2023-02-13T14:43:34Z")
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. [![](https://us1.discourse-cdn.com/elastic/original/3X/0/8/082a5948568d3920e449806995426b0a65e3a054.jpeg "What is in a Lucene index? Adrien Grand, Software Engineer, Elasticsearch") ](https://www.youtube.com/watch?v=T5RmMNDR5XI) ㄴ\> seminar i just found seminar that tells about finite state transfer which end up with O(logN). but not sure about it though ---
**Author:** ![dan\_kim](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/dan_kim/32/95741_2.png) [@dan\_kim](https://discuss.elastic.co/u/dan_kim)\ **Post date:** [February 13, 2023, 2:47pm UTC](https://discuss.elastic.co/t/what-is-the-time-complexity-of-query-a-word-in-lucene/325385/5 "2023-02-13T14:47:40Z")
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) ---
**Author:** ![Mark\_Harwood1](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/mark_harwood1/32/101255_2.png) [@Mark\_Harwood1](https://discuss.elastic.co/u/Mark_Harwood1)\ **Post date:** [February 13, 2023, 10:31pm UTC](https://discuss.elastic.co/t/what-is-the-time-complexity-of-query-a-word-in-lucene/325385/6 "2023-02-13T22:31:35Z")
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). ---
**Author:** ![dan\_kim](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/dan_kim/32/95741_2.png) [@dan\_kim](https://discuss.elastic.co/u/dan_kim)\ **Post date:** [February 14, 2023, 12:47am UTC](https://discuss.elastic.co/t/what-is-the-time-complexity-of-query-a-word-in-lucene/325385/7 "2023-02-14T00:47:55Z")
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 ---
**Author:** ![Mark\_Harwood1](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/mark_harwood1/32/101255_2.png) [@Mark\_Harwood1](https://discuss.elastic.co/u/Mark_Harwood1)\ **Post date:** [February 14, 2023, 9:10am UTC](https://discuss.elastic.co/t/what-is-the-time-complexity-of-query-a-word-in-lucene/325385/8 "2023-02-14T09:10:22Z")
> [@dan\_kim](#): > > Can you give me some resources about it? I cannot think of a better one than the Adrien Grand video you shared previously. ---
**Author:** ![system](https://us1.discourse-cdn.com/elastic/original/3X/1/a/1ac57faf039f6b580b3f104ef42a2a89e41014de.png) [@system](https://discuss.elastic.co/u/system)\ **Post date:** [March 14, 2023, 9:10am UTC](https://discuss.elastic.co/t/what-is-the-time-complexity-of-query-a-word-in-lucene/325385/9 "2023-03-14T09:10:38Z")
This topic was automatically closed 28 days after the last reply. New replies are no longer allowed.