`
wangzjie
  • 浏览: 74566 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Solr空间索引原理及源码分析

    博客分类:
  • solr
阅读更多

看不到图片的可到我的github博客上看。

 

solr的4.0-4.1版本使用GeohashField.createSpatialQuery(), 未使用IntersectsPrefixTreeFilter(继承于AbstractVisitingPrefixTreeFilter)。4.2版本开始使用IntersectsPrefixTreeFilter。4.2和4.3及以后的区别好像只是小改了一些,比如把Node对象换成Cell对象。

solr空间索引主要有两类GeohashPrefixTree(Geohash)与QuadPrefixTree(四叉树,对应笛卡尔分层策略)。分层其实取的就是前缀。

4.3开始geohash也引入了分层查询策略(这个有些不严谨,4.0-4.2虽然没使用IntersectsPrefixTreeFilter,但具体策略我还没有研究),总体效果应该优于Quad(拿了一个多边形,geohash只要203个term,而quad要488个, 对于点来说geohash只要11个term,而quad要26个term)。应该是4.3开始作者按照quad优化了geohash。

 

GeohashPrefixTree与QuadPrefixTree的主要不同:

1、maxLevels不同:geohash的maxLevels为11,quad的maxLevels为26。

2、通过distance获得相应的detailLevel不同

3、获得子Cell不同:geohash下一层有32个子Cell(编码为0-z), quad下一层有4个子Cell(编码为ABCD。A:左上,B:右上,C:左下,D:右下)

 

由于两种方法的大致思想一致,所以下文重点介绍geohash。

重要属性


schema.xml中的空间索引类型的配置:

 

<fieldTypename="location_jts"  class="solr.SpatialRecursivePrefixTreeFieldType"
           spatialContextFactory="com.spatial4j.core.context.jts.JtsSpatialContextFactory"
           distErrPct="0.025"
           maxDistErr="0.000009"
           units="degrees"/>

 

SpatialRecursivePrefixTreeFieldType

用于深度遍历前缀树的FieldType,主要用于获得基于Lucene中的RecursivePrefixTreeStrategy。

JtsSpatialContextFactory

当有Polygon多边形时会使用jts(需要把jts.jar放到solr服务的lib下)。基本形状使用SpatialContext (spatial4j的类)。

distErrPct

定义非Point图形的精度,范围在0-0.5之间,默认0.025。该值决定了非Point的图形索引或查询时的level(如geohash模式时就是geohash的长度)。当为0时取maxLevels,即精度最大。计算level的方法是 Shape中心到其外包矩形的最远corner的距离 * distErrPct (这块理论依据还没研究...)。实现代码如下SpatialArgs.calcDistanceFromErrPct()返回distErr:

 

public static double calcDistanceFromErrPct(Shape shape, double distErrPct, SpatialContext ctx) {
    if (distErrPct < 0 || distErrPct > 0.5) {
      throw new IllegalArgumentException("distErrPct " + distErrPct + " must be between [0 to 0.5]");
    }
    if (distErrPct == 0 || shape instanceof Point) {
      return 0;
    }
    Rectangle bbox = shape.getBoundingBox();
    //Compute the distance from the center to a corner.  Because the distance
    // to a bottom corner vs a top corner can vary in a geospatial scenario,
    // take the closest one (greater precision).
    Point ctr = bbox.getCenter();
    double y = (ctr.getY() >= 0 ? bbox.getMaxY() : bbox.getMinY());
    double diagonalDist = ctx.getDistCalc().distance(ctr, bbox.getMaxX(), y);
    return diagonalDist * distErrPct;
  }

 

 

然后由GeohashPrefixTree.getLevelForDistantce(distErr)来求得geohash精度。

 

public int getLevelForDistance(double dist) {
    if (dist == 0) //Point时dist=0
      return maxLevels;//short circuit
    final int level = GeohashUtils.lookupHashLenForWidthHeight(dist, dist);
    return Math.max(Math.min(level, maxLevels), 1);
  }


maxDistErr/maxLevels

 

定义索引数据的最高层maxLevels,默认是0.000009即1米(geohash11位),直接决定了Point索引的term数。

maxLevels优先级高于maxDistErr,即有maxLevels的话maxDistErr失效。详见SpatialPrefixTreeFactory.init()方法。

不过一般使用maxDistErr。

worldBounds

世界坐标值:"minX minY maxX maxY"。 geo=true即geohash模式时,该值默认为"-180 -90 180 90"。geo=false即quad时,该值为Java double类型的正负边界,此时需要指定该值,设置成"-180 -90 180 90"。

Solr spatial的类框架图


各类作用说明:

lucene实现的:

SpatialStrategy: 空间索引的核心,用来创建 索引域 以及 查询Query、查询Filter,以及用于score=distance等的打分策略(DistanceValueSource)。

SpatialPrefixTree: 其子类为GeohashPrefixTree和QuadPrefixTree。其主要用于获得索引Level、深度遍历获得与目标Shape相交的Cell,以及将token字符串与Cell间的相互转换。GeohashPrefix.GhCell (下层32个子结点,因为geohash每位代表5bit,2^5=32, 经度3bit,纬度2bit)和QuadPrefixTree.QuadCell(下层4个子结点)均是用于获得与目标Shape相交的下一层子cell。

SpatialPrefixTreeFactory:初始化maxLevels, 通过makeSPT()方法创建SpatialPrefixTree对象(grid)

spatial4j/jts实现的:

SpatialContext: 用于获得距离计算Calculator以及解析形状等。其属于spatial4j包中,该包中还有各种Shape及判断各Shape间的相交情况。JtsSpatialContext(jts包)用于处理多边形等情况。

solr实现的:

AbstractSpatialFieldType:用于获得相应的Strategy,获得相应的索引域、查询Query。

创建空间索引


索引结构

geohash模式的索引结构分成Point和非Point。下图为索引结构示意图(为方便起见只画了6层, 蓝色为Point,黄色为非Point):


Point

如经纬度41.79452,123.41555,对应的geohash为wxrvb2kqexu(maxLevels=11), 则其对应的term有11个(如w、wx、wxr、wxrv...,存储了前缀,牺牲索引加快查询速度)。

非Point

如Polygon。非Point的索引中有leaf叶子结点的概念,比如wtxrvb包含在Polygon中,则该cell为leaf,生成term时会有wtxrvb与wtxrvb+(+是leaf的标志)。

空间索引创建流程

说明:Point的term就是把其geohash:wtxrvb变成w、wt、wtx、wtxr、wtxrv、wtxrvb,Point的索引Level为maxLevels(即11位)。下面主要说明非Point的term创建过程。

1、将空间索引域的shapeStr解析成相应的Shape(复杂Shape如Polygon要使用JTS中的WTKReader来解析),以下拿Polygon为例。

2、计算目标Polygon的索引Level,即根据Polygon的外包矩形以及distErrPct算出distErr,再调用SpatialPrefixTree.getLevelForDistance(distErr)得到索引detaiLlevel。

3、得到与目标Polygon相交(即有交集或在Polygon内)的所有子Cell。主要做法是从root=WorldCell开始进行深度遍历并对各子树进行前枝:每下一层有32个子结点,然后判断各子结点与Polygon的相交情况。判断相交时简单的可以用spatial4j包来计算,复杂的需要用JTS。判断相交主要是先与Polygon的外包矩形判断是否相交(提高效率),如果相交,再与Polygon进行进一步相交判断。

a、不相交的则舍弃该Cell(其子Cell也不会被遍历到)。

b、包含在目标Polygon中,则设置该Cell为叶结点(term末尾加+), 添加到result中,其子Cell不再遍历。

c、intersect以及contain Polygon: 将Cell添加到result中,然后继续深度遍历其子Cell,获得更精确的Cell。

d、当cell的token长度达到detailLevel时,则到达最底层,标记为叶结点,添加到result中,停止该Cell的遍历。如果某个Cell的32个子Cell都是叶结点,则删除这32个子结点,把该Cell设置成叶结点。(这里直接影响了查询时的误差,会多取数据)

4、得到Filed,得到的Cell列表都放在CellTokenStream中。

5、存储索引域与存储域。

下图为判断相交的示意图:

多边形索引一般会得到几百上千个term,大大增加了索引大小与创建时间,哎,一切都是为了查询...

空间索引查询


查询语法

q={!geofiltpt=45.15,-93.85sfield=geod=5 score=distance}

q={!bbox pt=45.15,-93.85sfield=geod=5 score=distance}

q=geo:"Intersects(-74.09341.042-69.34744.558)"

q=geo:"Intersects(POLYGON((-1030,-4040,-10-20,4020,00,-1030)))"

查询方法

我们可以像创建空间索引的方法那样得到与查询Shape相交的所有子Cell,然后再与term进行匹配,但这有两个问题:一是很多没有数据的区域也会被深度遍历,二是得到的子Cell与term进行匹配比较麻烦。

solr的查询策略:利用了索引term的字典有序可以有效地对上面的深度遍历进行剪枝,term的顺序和深度遍历的Cell的顺序是一致的。具体流程如下图:

说明:

1、获得空间索引域的第一个域,深度遍历root=WorldCell开始,找到与查询Shape相交的子Cell。

2、开始深度遍历, 找到遍历的下一个结点,判断当前Cell与当前term的大小关系:

a、当前Cell < term : 则跳过该Cell, 因为term是按字典序顺序取的,在当前term之前的Cell对应不到数据。

b、当前Cell > term : 当前term已经匹配完成(因为以后遍历的Cell肯定都比当前term大),定位到下一个>=Cell的最小term,继续遍历Cell。

c、当前Cell = term : 判断当前Cell是否还要继续深度遍历,即如果Cell包含在查询Shape内,或者Cell已经达到了查询Shape的detailLevel层时,则当前Cell遍历结束,将当前term上的docId都取出来;否则继续深度遍历获得当前Cell的与查询Shape相交的子Cell。同时取下一个term。这里有个特殊情况是当term是以+结尾即leaf结点时且Cell长度和term长度一样长时(长度比较不包括+),说明该数据是非Point索引时的叶结点,再深度遍历已经也对应不上相应的term,所以就把该term对应的非Point docId都取出来,然后取下一个term。

不断重复第2步直到term取完或者所有树结点都被遍历完。

下图是查询策略的示意图:


空间索引查询流程

上图以geofilt查询为例,其中分成有score=distance和无score=distance两种情况。

先介绍不需要score的情况:

1、解析查询,生成Query树:获得相应的QParse, 对geofilt进行语法解析,获得geofilt的各个参数,并且获得相应的查询Query(ConstantScoreQuery)包括相应的Filter(IntersectsPrefixTreeFilter),其中也计算了查询Shape的一些属性,如最大索引长度detailLevel。

2、查询:SolrIndexSearch.search()进行创建Weight树和Score树。利用IntersectsPrefixTreeFilter得到符合条件的docIdSet(调用了前面的VistorTemplate深度遍历策略)。由于不需要score,所以Score返回的是ConstantScorer。

需要score的情况(大坑,要缓存所有term对应的docId及对应的geohash中心点),只说明score=distance,score=recipDistance图中已经说明:

基本流程和上面一致。说明下主要不同的地方:

1、Query对象:其创建的是FilteredQuery,其中有几个属性关系到打分:

a、ShapeFieldCacheDistanceValueSource: 用于生成FuncitonValues对象来给各个doc打分,只用于计算Point类的doc,非Point类的doc都打180分(即非Point都是最近的)。其主要属性PointPrefixTreeFieldCacheProvider缓存了所有Point类doc的docId–>point所在geohash的中心点(大坑之所在)。

b、FunctionQuery:其中包括了FunctionWeight、AllScorer、FunctionValues等主要用于空间索引的打分操作。

2、Scorer.score()调用的是AllScorer.score(): 解析出符合条件的docId,然后通过ShapeFieldCacheDistanceValueSource生成的FunctionValues得到docId对应的中心点,计算与查询Shape中心的距离来作为score。再放到优先队列中进行排序,从而实现按score排序的功能。

 

一些主要类说明:

FunctionValues: 其floatVal(docId)用于计算两点距离(非Point默认最近),调用provider的cache来获得各个docId的中心点坐标。

ShapeFieldCacheDistanceValueSource: 生成的FunctionWeight。

ShapeFieldCache(大坑,文档里说以后会替换这块):缓存了docId-->其term对应的Cell的中心点。cache[docId]=ArrayList。

PointPrefixTreeFieldCacheProvider:管理ShapeFieldCache。(只支持Point)

  • 大小: 194.1 KB
  • 大小: 65.6 KB
  • 大小: 28.9 KB
  • 大小: 46.3 KB
  • 大小: 308.7 KB
  • 大小: 325.5 KB
  • 大小: 742.8 KB
分享到:
评论

相关推荐

    solr查询索引

    在本文中,我们将深入探讨如何使用Solr进行索引查询,并结合相关库文件解析其背后的工作原理。 首先,Solr的查询过程主要分为以下步骤: 1. **建立索引**:Solr通过分析和索引文档内容来创建索引,这个过程包括...

    Solr 学习笔记(五)-Solr扩展之分布式索引实例

    在本篇Solr学习笔记中,我们将探讨Solr的分布式索引功能,这对于处理大量数据和实现高可用性至关重要。Solr的分布式索引能力允许我们跨越多个节点分布和处理索引过程,从而提高索引速度和查询性能。在实际应用中,这...

    solr4.5版本

    8. **源码分析**: - 对于研究Solr的开发者,源码提供了深入理解其工作原理的机会,可以定制和优化Solr以满足特定需求。 综上所述,Solr 4.5版本是一个功能强大且高度可定制的搜索引擎平台,适合各种规模的企业...

    开源企业搜索引擎SOLR的 应用教程

    当新的文档添加到索引中时,Solr会对其进行分析、提取关键词并存储这些信息。索引过程可以通过API调用或批量导入等方式完成。 - **1.3.2 搜索** 用户通过HTTP请求发送查询,Solr根据查询条件在索引中查找匹配的...

    Solr初体验

    Solr初体验 Apache Solr 是一款开源的...通过深入了解 Solr 的工作原理和配置技巧,我们可以构建出高效、可靠的搜索系统,满足各种业务场景的需求。在实际应用中,还需要根据具体需求进行细致的性能调优和扩展开发。

    搜索引擎--原理、技术与系统

    对于开发者来说,通过阅读和分析开源搜索引擎的源码,如Lucene、Elasticsearch和Solr,可以深入理解其内部机制,提升搜索引擎开发能力。同时,也可以自定义和优化搜索算法,满足特定场景的需求。 总结,搜索引擎是...

    lucene实战源码.rar

    源码分析: 1. **索引构建**:Lucene的核心功能之一是创建索引。在源码中,你可以看到如何使用`IndexWriter`类将文档添加到索引中,以及如何处理分词、字段存储和倒排索引等概念。`Analyzer`类负责对输入文本进行...

    confluence源码

    源码分析可以帮助我们理解Confluence的工作机制,这对于开发者进行自定义扩展、性能优化或者问题排查至关重要。 1. **服务端架构**:Confluence基于Java平台,采用Spring框架构建其服务层。Spring的依赖注入(DI)...

    lucene索引

    - **Solr**和**Elasticsearch**:基于Lucene的分布式搜索平台,提供了更高级的功能,如多节点集群、实时索引、复杂查询语法等。 了解并掌握Lucene的索引机制,对于开发高性能的全文检索应用至关重要。无论是从底层...

    elasticsearch实战及使用ppt,私有资源自己 看的

    节点是ES运行的实例,索引是存储数据的逻辑空间,文档是索引中的数据记录,类型则是文档的分类。ES内部使用倒排索引机制,实现快速的全文搜索。 **数据管理** ES支持通过JSON文档进行数据插入、更新和删除。数据...

    fulltext searchable

    2. 源码解析:可能深入解析了某个全文搜索引擎的源码,如Lucene,分析其关键组件如分词器、索引器、查询解析器的工作流程。 3. 工具应用:可能介绍了Elasticsearch或Solr等工具的使用,包括安装配置、索引构建、...

    JAVA上百实例源码以及开源项目源代码

    Java目录监视器源程序 9个目标文件 内容索引:JAVA源码,综合应用,目录监视 用JAVA开发的一个小型的目录监视系统,系统会每5秒自动扫描一次需要监视的目录,可以用来监视目录中文件大小及文件增减数目的变化。...

    ElasticSearch中文学习教程

    通过对索引过程的源码分析,可以深入了解文档如何被索引到ElasticSearch中,以及相关的优化技巧。 #### 六、问题解决 **7.1. 索引修复** 当索引损坏时,需要采取相应的修复措施。常见的修复方法包括重建索引、...

    lucene-3.0.0-src.zip

    在这个版本3.0.0的源码中,我们可以深入理解Lucene的核心机制和设计原理,这对于开发、优化以及定制自己的搜索引擎系统具有极大的价值。 一、Lucene基本架构 1. 文档索引:Lucene的核心工作是将非结构化的文本数据...

    elasticsearch的hanlp中文插件

    **Elasticsearch与HanLP中文插件详解** 在搜索引擎领域,Elasticsearch(简称ES)是一种广泛使用的开源全文检索...同时,源码开放的特点也为自定义开发提供了广阔的空间,让开发者可以根据实际场景进行扩展和优化。

    lucene-3.5.0

    Lucene 提供了详尽的 API 文档和示例代码,开发者可以通过阅读源码和参与社区讨论来深入理解其工作原理和最佳实践。同时,Lucene 与其他开源项目(如 Solr、Elasticsearch)结合使用,可以构建更加强大的搜索解决...

Global site tag (gtag.js) - Google Analytics