title: Why are Lucene/Elasticsearch prefix queries slower than term queries?
body: <p>I've been recently reading about Lucene and Elasticsearch and it seems the following are true (correct me if i'm wrong):</p>
  <ol>
  <li>prefix queries are slower than term queries</li>
  <li>suffix queries (* ing) are slower than prefix queries (ing *)</li>
  </ol>
  <p>This seems like a strange combination of properties. Perhaps I need to broaden my scope of data structures I'm considering, but if a segment were structured like a hash table, I could easily see that 1 would be true (the term query would be O(1) and a prefix query would require a full scan) however 2 would not be true (both prefix and suffix would require a full scan). If the segment were laid out like a sorted array, I could easily see that 2 would be true (a prefix query could be performed with a binary search O(log n) and the suffix would require a full scan) however 1 would no longer be true (both a term and prefix query would require a binary search).</p>
  <p>My only other thought is that there might be some combination of both hash and sort going on to account for this behavior (ex. hash to some partition and sort within that partition). However my understanding is that Elasticsearch partitions by a document identifier but the inverted index key is a term. So a query for a term still requires the request being sent to all partitions.</p>
  <p>Can anyone provide me with some intuition as to how/why this behavior exists?</p>
  <p>Note:</p>
  <ul>
  <li><p><a href="https://www.youtube.com/watch?v=T5RmMNDR5XI" rel="nofollow noreferrer">https://www.youtube.com/watch?v=T5RmMNDR5XI</a> would suggest that a segment is structured similar to a sorted array rather than a hash table.</p>
  </li>
  <li><p>The reason I believe 1 is true is <a href="https://medium.com/@mourjo_sen/a-detailed-comparison-between-autocompletion-strategies-in-elasticsearch-66cb9e9c62c4" rel="nofollow noreferrer">https://medium.com/@mourjo_sen/a-detailed-comparison-between-autocompletion-strategies-in-elasticsearch-66cb9e9c62c4</a> mentions &quot;The most important reason why prefix-like queries should never be used in production environments is that they are extremely slow. The reason for this is that the tokens in ES are not directly prefix-able&quot;</p>
  </li>
  <li><p>The reason I believe 2 is true is <a href="https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-query-string-query.html" rel="nofollow noreferrer">https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-query-string-query.html</a> mentions &quot;Allowing a wildcard at the beginning of a word (eg &quot;*ing&quot;) is particularly heavy, because all terms in the index need to be examined, just in case they match</p>
  </li>
  </ul>