好久没看书了，最近闲来无事，针对ES的range查询的一些毛刺问题，想办法如何去降低（避免是避免不了了）。无意中在ES的官网看到一篇博客，光看标题肯定就觉的吊炸天了吧。
推荐阅读
Numeric and Date Ranges in Elasticsearch: Just Another Brick in the Wall
话说Elasticsearch 5.2 开始就引入了integer_range,float_range, long_range,double_range和date_range，好吧，老实说，之前从来没有关心过它。直到有一天突然想到一个问题.....
需求
话说，在电商系统里，其实很多的库都会有档期的概念，专场会有始末时间，商品打折也有，总结就是很多的表都会有类似一个xxx_start_time 和xxx_end_time这两个冬冬。
好，那么我们通常要筛选出一批商品列表，专场列表，上架列表等等，我们就需要分别对start 和end做range操作，那自然而然就用到下面这样的搜索：
"bool": {
"filter": [
{
"range": {
"merchand.show_from": {
"lt": "1533026579999"
}
}
},
{
"range": {
"merchan.show_to": {
"gt": "1533026579999"
}
}
}
]
}
大家都知道Lucene6.0 开始对于数字类型用的是一种新的BKD-Tree 数据结构，整棵树首先是不会完全常驻内存，并且通过range计算时对于数据集大时，build 出 bit set 和build scorer都需要不少时间。
上面的例子，输入的仅仅只是一个时间点，但是其实查询的是分别对两个字段做了range，假如第一个range从10亿集合中得出结果集是10w，耗时50ms，第二个range也同样从10亿集合得出10w，耗时50ms，（这里我们暂且忽略doc values 的情形，先讨论两个都走索引，最坏情况！）而最后做完交集可能只有几十个doc id 命中了。那其实是不是很冤枉，因为时间都耗在无谓地对那些结果集做bit set 和build scorer。
后来我在想，有没有一种类似GeoLatLonPoint这样的数据结构，可以把 start_time，end_time 都可以塞入一个字段中，那么其实我查询的话通过对区间来做结果集筛查，往往就能大大压缩return 的集合。
那么结果就是如开篇所示，用ES的long_range,或者date_range 来解决这类问题。那么上面的类型merchand.show_from``merchand.show_to 可能就变成了 merchand.show_period 字段，那么要索引这个字段的时候可能就要用类似 merchand.show_period:{"gte":"2015-10-31","lte":"2015-11-1"}。
好了，这里就不做什么quick start example了，这不是文章的重点，有兴趣的照着上面文章做就好了。下面来一起去探讨一下ES这种类型在Lucene 6的实现。
The Evolution of Numeric Range Filters in Apache Lucene
推荐阅读
The Evolution of Numeric Range Filters in Apache Lucene
我们先暂且飞回去2年前的2016 年，在Lucene 6.0 出来之前，任何东西都是text，包括数字，举个例子，17，2，23，要搜大于10怎么办呢？ 2肯定会被检索出来的，那Lucene的折中就是在前面补0，最后变成了 017，002，023，这样对词条多range就不会错了，但是性能可想而知了。
然后到了后来，随着地图等应用，在Lucene 有了一种称为 geo-spatial search，Lucene 增加了一种称为 block KD (BKD) tree data structure, for fast multi-dimensional point filtering这群人发现，这种数据结构在做这种二维地理位置搜索，临近距离查询等搜索时，性能非常好。
It offers box, distance (Haversine earth surface distance) and polygon filtering, and even includes a unique (versus Lucene's other geo-spatial implementations) very fast nearest neighbor search, something KD-trees are especially good at. It also offers fast distance sorting, using doc values. Lucene's nightly geo-spatial benchmarks compare the performance of our three fastest geo-spatial implementations.
又再后来，这群人又发现，这个结构不仅是做2D，3D Search 性能很好，并且做1D numerics case 性能也是非常好
While the initial goal was fast geo-spatial 2D (latitude, longitude) and 3D (x, y, z) searching, we quickly realized that this data structure also works very well for the 1D numerics case.
那么结果你就猜到了，Lucene 6 开始，BKD Tree 就作为number type 的数据结构实现。
深入Lucene的 BKD Tree
这节我们就看看Lucene 的BKD Tree是怎么实现的，用Lucene团队说就是：
The k-d tree variant we implemented is the block k-d tree which is specifically designed for efficient IO, such that most of the data structure resides in on-disk blocks, with a small in-heap binary tree index structure to locate the blocks at search time
传统的 k-d tree的话，最大弊端就是插入一个节点时需要重新均衡，为了解决这个问题所以Lucene采用了Block 的K-D tree
这里要知道的一个概念是，整个树是不会常驻HEAP的，每个节点作为叶子存在于block，并且HEAP先只保留文件的起始位移，起始每一个节点的下面也是一个完整的K-D tree，这就可以解决局部update的问题。
具体到HEAP中的一个节点的数据结构，用的是一个编码过的byte[], 总共长度是16个字节，,每一个的byte用的是unsigned 256，Lucene当前支持最大是4维度，每个维度支持一个区间，也就是说如果是二维的表达，那么将会是用第1，2个bytes表示 二维的第一个数字，第5，6字节表达二维的第二个数字，维度升高以此类推。这个例子将在下面会再介绍。
Dimensional points are more general than numeric tries because arbitrary
byte[](unsigned, base 256) values up to 16 bytes in length and up to 8 dimensions can be indexed, versus just 4 or 8 byte numeric values with numeric tries. This makes support for IPv6 internet addresses and up to 128 bitBigIntegereasy.
查询的时候，其实也是同样的在一棵树里找区间的一个过程，如果这个值还是小于当前子树的边界，那就再去load sub tree，以此类推，那么在一维数字里，其实就转变成了找数字区间的过程，这个过程很容易展开成 2D， 3D甚至4D的情形，比如2D的搜索，可以在1D的区间里每一个元素相对于第2维都是一个垂直的维度转换。
这里同样提到一点，之所以在范围查询 BKD tree 搜索非常快，是因为在越是密集的区域，子树包好的子叶子会越多，这样略过（或者说横跨过）一整片区域就会越快
K-d trees are fast because they naturally adapt to each data set's particular distribution, using small leaf blocks where the indexed values are dense: notice how central London, where there is a higher density of points, is assigned smaller leaf cells. K-d trees also naturally find the right tradeoff of how deeply to recurse, by splitting up the dimensional space, versus at what point simply scanning the full-precision values in one cell is appropriate. This is in contrast to legacy numeric fields which always index the same precision levels for every value (4 terms for a long value, by default) regardless of how the points are distributed.
更具体的 BKD tree的搜索算法我并没有深入去Lucene的源码去看，我找到另外一个兄弟写了一个类似的算法演绎我觉得已经很好理解了，大家可以看看
https://github.com/zzboy/lucene/blob/master/lucene_6_bkd_tree.md
这里截取其中一个高维查询过程高维场景
有了一维场景，非常容易推广到高维的场景。
构建过程
step 1: 选择一个维度，将数据按照该维度排序，数据量大的话使用外排序。 step 2: 选取中位数作为根节点的split value，除此以外，根节点需要记录下是哪一个维度的split value。 step 3: 前面两步将数据集划分成两部分，分别对两部分重复step 1、step 2，构造根节点的左右子树。 step 4: 持续上述递归构造过程直到节点关联的数据数集数量小于某个阈值。
回过来看ES的 long_range的实现
在上面已经说过了，每一个point的表达是用16字节表示，在ES的一个long_range里，其实分别用了下面的d1,D1来表示一个插入数据的min和max，也就是一个一维的range 在Lucene里其实用了一个2维的point来去保存，这个和GeoPoint其实是一个概念，如下面这个例子，如果我插入了一个range 是5~15 的period，那么它就是保存在下面的的
和D1构成的point
ES的查询模式其实并没有自己实现了什么，从代码来看，都只是对Lucene的封装，用的也是Lucene自带的几种模式：WITHIN，CONTAINS等；根据模式最终会转换成一些原生查询。
性能
既然知道了ES的几种range其实用的是它的2D运算结构，那么就看看 Lucene BKD Tree的2D性能如何。
详细测试从https://www.elastic.co/blog/lucene-points-6.0 看
从图中看，和GeoPoint一样，除了性能提高，其实占用空间和占用HEAP来看都是非常有优势。
1D的性能我就不介绍了。
回到原始需求来
回到我最初的这个需求来，从上面blog中提到说提到的性能提升来，和我所纠结的这个问题似乎没有太大的关系，我的初衷是如何能避免2次无谓的range出大量的临时数据，而从ES的long_range 使用的是BKD Tree 的2D保存实现来看，对于区间范围查询可能并没有剩掉多少运算。或者这么说，Lucene的BKD Tree它在解决特定的场景确实能有非常好的性能，但是并不一定是我这个场景。
当然，我目前还没有对生产的数据重构做一个该场景下的庞大的索引去测一下性能，所以下面的观点是我的一些猜测：
- 从Lucene实现知道，其实这个结构并不是常驻HEAP的，那么分别保存两个Tree 和通过2D结构保存到同一个Tree，不关加载还是运算，我觉得性能都应该是会有提升的，这一点很容易理解。
- 就看Lucene的实现了，通过在同一个树上搜索，其实很多东西可以优化，至少我这么认为，举个例子，就拿
long_range来说，假设我保存的是1-3，2-4，3-5，4-6，5-7，6-8假入我搜索2-5那么如果是老式的不相干的数，第一个字段根据range会先搜出2，3，4，5，6 第2个range查询会搜出3，4，5，最后交集是2-4，3-5但是如果采用2D结构，其实我第一个range可以自动转化成 >2,<5 一下子就得出2，3，4，然后逐个进行2D再从2D树递归查找，这样运算量就少很多了。
当然这是我自己的一些猜测。
有机会我会尝试把我们的一些区间类型用这种range类型替换去测一下并验证性能。大家有兴趣的可以期待。
题外话
在看Lucene BDK Tree的时候搜出了Solr 的一些实现，发现在DateRangeField 这里是有差异的，在Solr 的DateRangeField 其实用的是Lucene 的DateRangeType，本质是text实现来的，而ES的 date_range 看了ES的代码可以发现本质还是用了Lucene 的Long_range，这一点有些差异，有兴趣的可以查看下面几篇Solr的文章,也是挺有意思的
