Lucene 的范围查询详解

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

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

    范围查询部分很赞

推荐标签 标签

  • Swift

    Swift 是苹果于 2014 年 WWDC(苹果开发者大会)发布的开发语言,可与 Objective-C 共同运行于 Mac OS 和 iOS 平台,用于搭建基于苹果平台的应用程序。

    36 引用 • 37 回帖 • 543 关注
  • BND

    BND(Baidu Netdisk Downloader)是一款图形界面的百度网盘不限速下载器,支持 Windows、Linux 和 Mac,详细介绍请看这里

    107 引用 • 1281 回帖 • 35 关注
  • Hadoop

    Hadoop 是由 Apache 基金会所开发的一个分布式系统基础架构。用户可以在不了解分布式底层细节的情况下,开发分布式程序。充分利用集群的威力进行高速运算和存储。

    89 引用 • 122 回帖 • 619 关注
  • BookxNote

    BookxNote 是一款全新的电子书学习工具,助力您的学习与思考,让您的大脑更高效的记忆。

    笔记整理交给我,一心只读圣贤书。

    1 引用 • 1 回帖
  • 前端

    前端技术一般分为前端设计和前端开发,前端设计可以理解为网站的视觉设计,前端开发则是网站的前台代码实现,包括 HTML、CSS 以及 JavaScript 等。

    245 引用 • 1338 回帖
  • Unity

    Unity 是由 Unity Technologies 开发的一个让开发者可以轻松创建诸如 2D、3D 多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

    25 引用 • 7 回帖 • 133 关注
  • Tomcat

    Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。

    162 引用 • 529 回帖 • 3 关注
  • 禅道

    禅道是一款国产的开源项目管理软件,她的核心管理思想基于敏捷方法 scrum,内置了产品管理和项目管理,同时又根据国内研发现状补充了测试管理、计划管理、发布管理、文档管理、事务管理等功能,在一个软件中就可以将软件研发中的需求、任务、bug、用例、计划、发布等要素有序的跟踪管理起来,完整地覆盖了项目管理的核心流程。

    6 引用 • 15 回帖 • 26 关注
  • CSS

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

    199 引用 • 542 回帖 • 1 关注
  • 安装

    你若安好,便是晴天。

    132 引用 • 1184 回帖 • 1 关注
  • 酷鸟浏览器

    安全 · 稳定 · 快速
    为跨境从业人员提供专业的跨境浏览器

    3 引用 • 59 回帖 • 46 关注
  • 工具

    子曰:“工欲善其事,必先利其器。”

    298 引用 • 762 回帖
  • sts
    2 引用 • 2 回帖 • 227 关注
  • PWL

    组织简介

    用爱发电 (Programming With Love) 是一个以开源精神为核心的民间开源爱好者技术组织,“用爱发电”象征开源与贡献精神,加入组织,代表你将遵守组织的“个人开源爱好者”的各项条款。申请加入:用爱发电组织邀请帖
    用爱发电组织官网:https://programmingwithlove.stackoverflow.wiki/

    用爱发电组织的核心驱动力:

    • 遵守开源守则,体现开源&贡献精神:以分享为目的,拒绝非法牟利。
    • 自我保护:使用适当的 License 保护自己的原创作品。
    • 尊重他人:不以各种理由、各种漏洞进行未经允许的抄袭、散播、洩露;以礼相待,尊重所有对社区做出贡献的开发者;通过他人的分享习得知识,要留下足迹,表示感谢。
    • 热爱编程、热爱学习:加入组织,热爱编程是首当其要的。我们欢迎热爱讨论、分享、提问的朋友,也同样欢迎默默成就的朋友。
    • 倾听:正确并恳切对待、处理问题与建议,及时修复开源项目的 Bug ,及时与反馈者沟通。不抬杠、不无视、不辱骂。
    • 平视:不诋毁、轻视、嘲讽其他开发者,主动提出建议、施以帮助,以和谐为本。只要他人肯努力,你也可能会被昔日小看的人所超越,所以请保持谦虚。
    • 乐观且活跃:你的努力决定了你的高度。不要放弃,多年后回头俯瞰,才会发现自己已经成就往日所仰望的水平。积极地将项目开源,帮助他人学习、改进,自己也会获得相应的提升、成就与成就感。
    1 引用 • 487 回帖 • 1 关注
  • FFmpeg

    FFmpeg 是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序。

    23 引用 • 32 回帖
  • Sym

    Sym 是一款用 Java 实现的现代化社区(论坛/BBS/社交网络/博客)系统平台。

    下一代的社区系统,为未来而构建

    524 引用 • 4601 回帖 • 702 关注
  • Quicker

    Quicker 您的指尖工具箱!操作更少,收获更多!

    36 引用 • 155 回帖
  • SVN

    SVN 是 Subversion 的简称,是一个开放源代码的版本控制系统,相较于 RCS、CVS,它采用了分支管理系统,它的设计目标就是取代 CVS。

    29 引用 • 98 回帖 • 689 关注
  • GitBook

    GitBook 使您的团队可以轻松编写和维护高质量的文档。 分享知识,提高团队的工作效率,让用户满意。

    3 引用 • 8 回帖 • 3 关注
  • 链滴

    链滴是一个记录生活的地方。

    记录生活,连接点滴

    171 引用 • 3848 回帖 • 1 关注
  • 安全

    安全永远都不是一个小问题。

    203 引用 • 818 回帖
  • Openfire

    Openfire 是开源的、基于可拓展通讯和表示协议 (XMPP)、采用 Java 编程语言开发的实时协作服务器。Openfire 的效率很高,单台服务器可支持上万并发用户。

    6 引用 • 7 回帖 • 102 关注
  • 学习

    “梦想从学习开始,事业从实践起步” —— 习近平

    172 引用 • 516 回帖
  • 音乐

    你听到信仰的声音了么?

    62 引用 • 512 回帖 • 1 关注
  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    556 引用 • 675 回帖
  • HBase

    HBase 是一个分布式的、面向列的开源数据库,该技术来源于 Fay Chang 所撰写的 Google 论文 “Bigtable:一个结构化数据的分布式存储系统”。就像 Bigtable 利用了 Google 文件系统所提供的分布式数据存储一样,HBase 在 Hadoop 之上提供了类似于 Bigtable 的能力。

    17 引用 • 6 回帖 • 59 关注
  • Flume

    Flume 是一套分布式的、可靠的,可用于有效地收集、聚合和搬运大量日志数据的服务架构。

    9 引用 • 6 回帖 • 653 关注