时间戳

首页 > 解决方案 > 为什么 Lucene/Elasticsearch 前缀查询比术语查询慢？

elasticsearch - 为什么 Lucene/Elasticsearch 前缀查询比术语查询慢？

问题描述

我最近一直在阅读有关 Lucene 和 Elasticsearch 的内容，似乎以下内容是正确的（如果我错了，请纠正我）：

  1. 前缀查询比术语查询慢
  2. 后缀查询 (* ing) 比前缀查询 (ing *) 慢

这似乎是一个奇怪的属性组合。也许我需要扩大我正在考虑的数据结构的范围，但是如果一个段的结构类似于哈希表，我可以很容易地看到 1 将是真的（术语查询将是 O(1) 并且前缀查询将需要完整扫描）但是 2 不会为真（前缀和后缀都需要完整扫描）。如果段像排序数组一样布局，我可以很容易地看到 2 将是真的（可以使用二进制搜索 O(log n) 执行前缀查询，并且后缀需要完全扫描）但是 1 将不再为真（术语和前缀查询都需要二进制搜索）。

我唯一的另一个想法是，可能存在哈希和排序的某种组合来解释这种行为（例如，哈希到某个分区并在该分区内排序）。但是我的理解是 Elasticsearch 按文档标识符进行分区，但倒排索引键是一个术语。因此，对术语的查询仍然需要将请求发送到所有分区。

谁能给我一些关于这种行为如何/为什么存在的直觉？

笔记：

标签： elasticsearchsearchsolrluceneinverted-index

解决方案

我对 ES 的具体细节不是很熟悉，所以他们可能会做一些不同于普通 Solr 的事情——但通常情况下并非如此。

前缀匹配将比查找单个术语更昂贵，但并没有那么昂贵。它可以与进行范围搜索（如果您愿意，您可以执行）field:[aa TO ab)进行比较 - 可以与field:aa*（理论上）进行比较；有效地检索位于该范围内的所有标记，然后解析与这些标记匹配的文档集。

有更多匹配的标记的事实意味着您不能简单地获取附加到单个标记（匹配项）的列表并检索这些文档，但您必须检索可能很大的匹配标记集，然后计算为此设置的文档。然而，这不是一个非常昂贵的计算，但它比单个匹配更昂贵。查找可以通过在索引中查找匹配标记的开始和结束索引来完成，然后检索这两者之间的所有术语并找到匹配的文档 ID 集。

foo*针对具有以下术语的索引的查询：

bar, baz, foo, foobar, spam
          ^----------^

将收集附加到fooand的文档列表foobar，将其合并，然后检索文档。

较慢并不意味着它是灾难性的或没有以任何方式优化；只是它比已经确定了一组文档的直接匹配更昂贵。但是，您的查询中可能已经有多个术语，因此同样的过程（尽管在层次结构中稍高一些）也在那里发生。

后缀匹配（您的#2） - 即在令牌开头匹配通配符 - 是昂贵的，因为通常必须考虑索引中的所有令牌。索引具有按字母数字排序的术语，因此当您只想查看字符串的末尾时，您必须考虑每个标记都可以匹配，而不管它在索引中的位置 - 这样您就可以获得完整的索引扫描。但是，如果这是您经常看到的用例，您可以使用反向通配符过滤器。这通过反转字符串并具有以相反顺序匹配术语的标记来工作，因此它foo被索引为oof并且通配符搜索被转换为oof*。

*ar针对具有以下术语的索引的查询：

bar, baz, foo, foobar, spam
?!   ?    ?    ?!      ?

将不得不查看每个术语以确定它是否以ar.

使用 EdgeNGramFilter （您的评论/#3）的原因是您将尽可能多的所需处理移至索引时间（执行您知道的查询时间的工作，即使前缀查询并不是很昂贵，它们仍然有成本），另外：通配符查询不支持大多数分析。如此多的人最终会针对一组已被提取或以其他方式处理的标记进行通配符查询，然后当他们的通配符查询未生成匹配时感到惊讶。只有一小部分过滤器可以应用于通配符查询（例如 LowercaseFilter）。这些过滤器被称为“多术语感知”，因为在文档收集发生之前，该过程最终可以扩展为多个术语。

另一个原因是，使用 EdgeNGramFilter 将为您提供每个前缀的正确频率分数，也为您提供前缀术语的有效评分。

推荐阅读