为什么 Lucene/Elasticsearch 前缀查询比术语查询慢？
Why are Lucene/Elasticsearch prefix queries slower than term queries?
我最近一直在阅读有关 Lucene 和 Elasticsearch 的文章，似乎以下内容是正确的（如果我错了请纠正我）：
- 前缀查询比术语查询慢
- 后缀查询 (*ing) 比前缀查询 (ing *) 慢
这似乎是一种奇怪的属性组合。也许我需要扩大我正在考虑的数据结构的范围，但是如果一个段的结构类似于散列 table，我可以很容易地看出 1 为真（术语查询为 O(1) 并且前缀查询需要完全扫描）但是 2 不成立（前缀和后缀都需要完全扫描）。如果该段的布局类似于排序数组，我可以很容易地看出 2 为真（可以使用二进制搜索 O(log n) 执行前缀查询，后缀需要完全扫描）但是 1 将不再为真（术语和前缀查询都需要二进制搜索）。
我唯一的其他想法是，可能存在哈希和排序的某种组合来解释这种行为（例如哈希到某个分区并在该分区内排序）。但是我的理解是，Elasticsearch 按文档标识符进行分区，但倒排索引键是一个术语。所以查询一个词仍然需要将请求发送到所有分区。
谁能给我提供一些关于 how/why 这种行为存在的直觉？
注：
https://www.youtube.com/watch?v=T5RmMNDR5XI 表明段的结构类似于排序数组而不是散列 table.
我相信 1 是真的原因是 https://medium.com/@mourjo_sen/a-detailed-comparison-between-autocompletion-strategies-in-elasticsearch-66cb9e9c62c4 提到“在生产环境中永远不应使用类似前缀的查询的最重要原因是它们非常慢。原因这是因为 ES 中的标记不能直接添加前缀
我相信 2 正确的原因是 https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-query-string-query.html 提到“在单词的开头允许使用通配符（例如“*ing”）特别繁重，因为需要检查索引，以防它们匹配
我不太熟悉 ES 的具体细节，所以他们可能在做一些不同于普通 Solr 的事情——但#1 通常情况并非如此。
前缀匹配比查找单个术语的成本更高，但成本并不高。它可以比作范围搜索（如果你愿意，你可以执行 - field:[aa TO ab) 可以比作 field:aa*（理论上）；有效地检索位于该范围内的所有标记，然后解析与这些标记匹配的文档集。
事实上，有更多的标记匹配意味着您不能简单地获取附加到单个标记（匹配项）的列表并检索这些文档，但您必须检索可能很大的匹配集标记，然后计算它的文档集。然而，这不是一个 非常昂贵的 计算，但它比单个匹配更昂贵。查找可以通过在索引中找到匹配标记的开始和结束索引，然后检索这两者之间的所有术语并找到匹配文档 ID 集来完成。
foo* 对具有以下项的索引的查询：
bar, baz, foo, foobar, spam
^----------^
将收集附加到 foo 和 foobar 的文档列表，合并它然后检索文档。
较慢并不意味着它是灾难性的或没有以任何方式进行优化；只是它比已经确定文档集的直接匹配更昂贵。但是，您的查询中可能已经有多个术语，因此同样的过程（尽管在层次结构中略高）也会在那里发生。
后缀匹配（您的#2）——即匹配令牌开头的通配符——代价高昂，因为通常必须考虑索引中的所有令牌。索引按字母数字顺序对术语进行排序，因此当您只想查看字符串的末尾时，您必须考虑每个标记都可以匹配，而不管它位于索引中的什么位置——这样您就可以进行完整的索引扫描。但是，如果这是您经常看到的用例，则可以使用 the reverse wildcard filter。这通过反转字符串并使标记以相反的顺序匹配术语来工作，因此 foo 被索引为 oof 并且通配符搜索变成 oof* 相反。
*ar 对具有以下项的索引的查询：
bar, baz, foo, foobar, spam
?! ? ? ?! ?
将不得不查看每个术语以决定它是否以 ar 结尾。
使用 EdgeNGramFilter（您的评论/#3）的原因是您将尽可能多的所需处理移动到索引时间（做您知道查询时间的工作，即使前缀查询不是'不是很贵，它们仍然有成本），另外：通配符查询不支持大多数分析。许多人最终对一组已被阻止或以其他方式处理的令牌进行通配符查询，然后当他们的通配符查询未生成匹配项时感到惊讶。只有一小部分过滤器可以应用于通配符查询（例如 LowercaseFilter）。这些过滤器被称为 being "Multi term aware"，因为在文档收集发生之前，该过程最终可以扩展为多个术语。
另一个原因是使用 EdgeNGramFilter 将为您提供每个前缀的正确频率分数，同时为您提供前缀术语的有效评分。
我最近一直在阅读有关 Lucene 和 Elasticsearch 的文章，似乎以下内容是正确的（如果我错了请纠正我）：
- 前缀查询比术语查询慢
- 后缀查询 (*ing) 比前缀查询 (ing *) 慢
这似乎是一种奇怪的属性组合。也许我需要扩大我正在考虑的数据结构的范围，但是如果一个段的结构类似于散列 table，我可以很容易地看出 1 为真（术语查询为 O(1) 并且前缀查询需要完全扫描）但是 2 不成立（前缀和后缀都需要完全扫描）。如果该段的布局类似于排序数组，我可以很容易地看出 2 为真（可以使用二进制搜索 O(log n) 执行前缀查询，后缀需要完全扫描）但是 1 将不再为真（术语和前缀查询都需要二进制搜索）。
我唯一的其他想法是，可能存在哈希和排序的某种组合来解释这种行为（例如哈希到某个分区并在该分区内排序）。但是我的理解是，Elasticsearch 按文档标识符进行分区，但倒排索引键是一个术语。所以查询一个词仍然需要将请求发送到所有分区。
谁能给我提供一些关于 how/why 这种行为存在的直觉？
注：
https://www.youtube.com/watch?v=T5RmMNDR5XI 表明段的结构类似于排序数组而不是散列 table.
我相信 1 是真的原因是 https://medium.com/@mourjo_sen/a-detailed-comparison-between-autocompletion-strategies-in-elasticsearch-66cb9e9c62c4 提到“在生产环境中永远不应使用类似前缀的查询的最重要原因是它们非常慢。原因这是因为 ES 中的标记不能直接添加前缀
我相信 2 正确的原因是 https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-query-string-query.html 提到“在单词的开头允许使用通配符（例如“*ing”）特别繁重，因为需要检查索引，以防它们匹配
我不太熟悉 ES 的具体细节，所以他们可能在做一些不同于普通 Solr 的事情——但#1 通常情况并非如此。
前缀匹配比查找单个术语的成本更高，但成本并不高。它可以比作范围搜索（如果你愿意，你可以执行 - field:[aa TO ab) 可以比作 field:aa*（理论上）；有效地检索位于该范围内的所有标记，然后解析与这些标记匹配的文档集。
事实上，有更多的标记匹配意味着您不能简单地获取附加到单个标记（匹配项）的列表并检索这些文档，但您必须检索可能很大的匹配集标记，然后计算它的文档集。然而，这不是一个 非常昂贵的 计算，但它比单个匹配更昂贵。查找可以通过在索引中找到匹配标记的开始和结束索引，然后检索这两者之间的所有术语并找到匹配文档 ID 集来完成。
foo* 对具有以下项的索引的查询：
bar, baz, foo, foobar, spam
^----------^
将收集附加到 foo 和 foobar 的文档列表，合并它然后检索文档。
较慢并不意味着它是灾难性的或没有以任何方式进行优化；只是它比已经确定文档集的直接匹配更昂贵。但是，您的查询中可能已经有多个术语，因此同样的过程（尽管在层次结构中略高）也会在那里发生。
后缀匹配（您的#2）——即匹配令牌开头的通配符——代价高昂，因为通常必须考虑索引中的所有令牌。索引按字母数字顺序对术语进行排序，因此当您只想查看字符串的末尾时，您必须考虑每个标记都可以匹配，而不管它位于索引中的什么位置——这样您就可以进行完整的索引扫描。但是，如果这是您经常看到的用例，则可以使用 the reverse wildcard filter。这通过反转字符串并使标记以相反的顺序匹配术语来工作，因此 foo 被索引为 oof 并且通配符搜索变成 oof* 相反。
*ar 对具有以下项的索引的查询：
bar, baz, foo, foobar, spam
?! ? ? ?! ?
将不得不查看每个术语以决定它是否以 ar 结尾。
使用 EdgeNGramFilter（您的评论/#3）的原因是您将尽可能多的所需处理移动到索引时间（做您知道查询时间的工作，即使前缀查询不是'不是很贵，它们仍然有成本），另外：通配符查询不支持大多数分析。许多人最终对一组已被阻止或以其他方式处理的令牌进行通配符查询，然后当他们的通配符查询未生成匹配项时感到惊讶。只有一小部分过滤器可以应用于通配符查询（例如 LowercaseFilter）。这些过滤器被称为 being "Multi term aware"，因为在文档收集发生之前，该过程最终可以扩展为多个术语。
另一个原因是使用 EdgeNGramFilter 将为您提供每个前缀的正确频率分数，同时为您提供前缀术语的有效评分。