Lucene 的范围查询详解

本贴最后更新于 3025 天前,其中的信息可能已经沧海桑田

Lucene 的范围查询是怎样实现的呢

粗略来说,是两种方式:

  1. 根据 docId 获取 field 的值,和设定的范围进行比较过滤,得到满足范围条件的 docList。

  2. 根据范围条件从 term 列表过滤出满足条件的 term,把 term 组成 BooleanQuery,查询倒排列表,得到满足范围条件的 docList。

第一种方式,从 docId 获取 value,需要用到 fieldCache,比较占内存,如果候选的 doc 数量非常大(满足其他查询条件的 doc 非常多或没有其他查询条件),则要过滤的计算比较多,性能不会很好。

第二种方式,如果过滤的范围比较大,则过滤出来的 term 非常多,要查的 term 很多,性能会很差。

从源代码看,Lucene 的实现是这两种方式的组合,但第二种方式经过了优化,过滤出来的 term 的数量会非常少,性能非常好。

如果 field 没有索引,且有 docValues,则采取第一种方式(没有索引,是无法用第二种方式的,因为没有对应的 term)

如果 field 有索引,则采取第二种方式,TrieField 的范围过滤

TrieField 实现原理

数值类型 TrieXXXField(XXX 可为 Long、Int、Float、Double、Date 等),如果需要范围查询,一般要设置一个参数 precisionStep。这个参数的用途是,在索引阶段,会把一个数值,根据 precisionStep 进行精度截取,分为多个不同精度的 term 来存储。我们以一个 int 为例,一个 int 共 32 位,如果 precisionStep 为 8,则每根据不同的精度,可以得到 4 个 term

term&11111111111111111111111111111111

term&11111111111111111111111100000000

term&11111111111111110000000000000000

term&11111111000000000000000000000000

这样,每个 term 都会变为 4 个 term,存储会增加很多,低精度的 term 重复率比较高,因此,主要是倒排列表占用的空间会多很多。

查询时,范围的上界和下界也按照这种规则,划分为 4 段,间隔的两个段之间有 256 个 term,

这样范围内的 term,就先取高低精度的,再取高精度的。最多一共有

256+2562+2562+256*2=1280 个 term,这些 term 再用 ConstantScoreQuery 来查询,比较打分计算。

下面举个例子来说明一个范围内的 term 是怎样得到的。

比如,范围[232420561,1399563675],

232420561 的二进制是 00001101110110100111010011010001

1399563675 的二进制是 01010011011010111010010110011011

命中的 term 为

下界高精度

00001101110110100111010011010001

00001101110110100111010011111111

共 48 个 term

下界去掉 8 位精度

00001101110110100111010100000000

00001101110110101111111100000000

共 139 个 term

下界去掉 16 位精度

00001101110110110000000000000000

00001101111111110000000000000000

共 37 个 term

去掉 24 位精度

00001110000000000000000000000000

01010010000000000000000000000000

共 69 个 term

上界去掉 16 位精度

01010011000000000000000000000000

01010011011010100000000000000000

共 107 个 term

上界去掉 8 位精度

01010011011010110000000000000000

01010011011010111010010000000000

共 165 个 term

上界最高精度

01010011011010111010010100000000

01010011011010111010010110011011

共 156 个 term

总共要查询 721 个 term,使用 ConstantScoreQuery 来查询还是很快的。

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • someone

    范围查询部分很赞

推荐标签 标签

  • HHKB

    HHKB 是富士通的 Happy Hacking 系列电容键盘。电容键盘即无接点静电电容式键盘(Capacitive Keyboard)。

    5 引用 • 74 回帖 • 523 关注
  • 又拍云

    又拍云是国内领先的 CDN 服务提供商,国家工信部认证通过的“可信云”,乌云众测平台认证的“安全云”,为移动时代的创业者提供新一代的 CDN 加速服务。

    20 引用 • 37 回帖 • 567 关注
  • Q&A

    提问之前请先看《提问的智慧》,好的问题比好的答案更有价值。

    10323 引用 • 46863 回帖 • 61 关注
  • RabbitMQ

    RabbitMQ 是一个开源的 AMQP 实现,服务器端用 Erlang 语言编写,支持多种语言客户端,如:Python、Ruby、.NET、Java、C、PHP、ActionScript 等。用于在分布式系统中存储转发消息,在易用性、扩展性、高可用性等方面表现不俗。

    49 引用 • 60 回帖 • 348 关注
  • etcd

    etcd 是一个分布式、高可用的 key-value 数据存储,专门用于在分布式系统中保存关键数据。

    6 引用 • 26 回帖 • 545 关注
  • RemNote
    2 引用 • 16 回帖 • 25 关注
  • DNSPod

    DNSPod 建立于 2006 年 3 月份,是一款免费智能 DNS 产品。 DNSPod 可以为同时有电信、网通、教育网服务器的网站提供智能的解析,让电信用户访问电信的服务器,网通的用户访问网通的服务器,教育网的用户访问教育网的服务器,达到互联互通的效果。

    6 引用 • 26 回帖 • 530 关注
  • 外包

    有空闲时间是接外包好呢还是学习好呢?

    26 引用 • 234 回帖 • 1 关注
  • jQuery

    jQuery 是一套跨浏览器的 JavaScript 库,强化 HTML 与 JavaScript 之间的操作。由 John Resig 在 2006 年 1 月的 BarCamp NYC 上释出第一个版本。全球约有 28% 的网站使用 jQuery,是非常受欢迎的 JavaScript 库。

    63 引用 • 134 回帖 • 742 关注
  • 单点登录

    单点登录(Single Sign On)是目前比较流行的企业业务整合的解决方案之一。SSO 的定义是在多个应用系统中,用户只需要登录一次就可以访问所有相互信任的应用系统。

    9 引用 • 25 回帖 • 2 关注
  • SSL

    SSL(Secure Sockets Layer 安全套接层),及其继任者传输层安全(Transport Layer Security,TLS)是为网络通信提供安全及数据完整性的一种安全协议。TLS 与 SSL 在传输层对网络连接进行加密。

    70 引用 • 193 回帖 • 414 关注
  • CSS

    CSS(Cascading Style Sheet)“层叠样式表”是用于控制网页样式并允许将样式信息与网页内容分离的一种标记性语言。

    199 引用 • 543 回帖 • 4 关注
  • Flutter

    Flutter 是谷歌的移动 UI 框架,可以快速在 iOS 和 Android 上构建高质量的原生用户界面。 Flutter 可以与现有的代码一起工作,它正在被越来越多的开发者和组织使用,并且 Flutter 是完全免费、开源的。

    39 引用 • 92 回帖 • 10 关注
  • Log4j

    Log4j 是 Apache 开源的一款使用广泛的 Java 日志组件。

    20 引用 • 18 回帖 • 40 关注
  • Sillot

    Insights(注意当前设置 master 为默认分支)

    汐洛彖夲肜矩阵(Sillot T☳Converbenk Matrix),致力于服务智慧新彖乄,具有彖乄驱动、极致优雅、开发者友好的特点。其中汐洛绞架(Sillot-Gibbet)基于自思源笔记(siyuan-note),前身是思源笔记汐洛版(更早是思源笔记汐洛分支),是智慧新录乄终端(多端融合,移动端优先)。

    主仓库地址:Hi-Windom/Sillot

    文档地址:sillot.db.sc.cn

    注意事项:

    1. ⚠️ 汐洛仍在早期开发阶段,尚不稳定
    2. ⚠️ 汐洛并非面向普通用户设计,使用前请了解风险
    3. ⚠️ 汐洛绞架基于思源笔记,开发者尽最大努力与思源笔记保持兼容,但无法实现 100% 兼容
    29 引用 • 25 回帖 • 140 关注
  • 七牛云

    七牛云是国内领先的企业级公有云服务商,致力于打造以数据为核心的场景化 PaaS 服务。围绕富媒体场景,七牛先后推出了对象存储,融合 CDN 加速,数据通用处理,内容反垃圾服务,以及直播云服务等。

    29 引用 • 230 回帖 • 123 关注
  • webpack

    webpack 是一个用于前端开发的模块加载器和打包工具,它能把各种资源,例如 JS、CSS(less/sass)、图片等都作为模块来使用和处理。

    42 引用 • 130 回帖 • 253 关注
  • Follow
    4 引用 • 12 回帖 • 10 关注
  • App

    App(应用程序,Application 的缩写)一般指手机软件。

    91 引用 • 384 回帖
  • 笔记

    好记性不如烂笔头。

    312 引用 • 794 回帖
  • 倾城之链
    23 引用 • 66 回帖 • 173 关注
  • wolai

    我来 wolai:不仅仅是未来的云端笔记!

    2 引用 • 14 回帖 • 3 关注
  • 星云链

    星云链是一个开源公链,业内简单的将其称为区块链上的谷歌。其实它不仅仅是区块链搜索引擎,一个公链的所有功能,它基本都有,比如你可以用它来开发部署你的去中心化的 APP,你可以在上面编写智能合约,发送交易等等。3 分钟快速接入星云链 (NAS) 测试网

    3 引用 • 16 回帖
  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    284 引用 • 248 回帖 • 4 关注
  • SpaceVim

    SpaceVim 是一个社区驱动的模块化 vim/neovim 配置集合,以模块的方式组织管理插件以
    及相关配置,为不同的语言开发量身定制了相关的开发模块,该模块提供代码自动补全,
    语法检查、格式化、调试、REPL 等特性。用户仅需载入相关语言的模块即可得到一个开箱
    即用的 Vim-IDE。

    3 引用 • 31 回帖 • 112 关注
  • CloudFoundry

    Cloud Foundry 是 VMware 推出的业界第一个开源 PaaS 云平台,它支持多种框架、语言、运行时环境、云平台及应用服务,使开发人员能够在几秒钟内进行应用程序的部署和扩展,无需担心任何基础架构的问题。

    4 引用 • 16 回帖 • 200 关注
  • PHP

    PHP(Hypertext Preprocessor)是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点,主要适用于 Web 开发领域,据说是世界上最好的编程语言。

    167 引用 • 408 回帖 • 485 关注