performance - Lucene 内存空间索引性能不佳

Question

在我的应用程序中，有一个用例来查找距其他地理点最近的点。我决定使用内存空间索引并找到了几个候选索引:jeospatial和 Lucene spatial .

我做了一些基准测试，并惊讶地发现 Lucene 索引结果非常慢。这是来自基准测试的代码，它是用 JMH 完成的。完整的源代码可以在我的GitHub repository中找到.

@State(Scope.Thread)
public class MyBenchmark {

    // Lucene
    private static final String COORDINATES_FIELD = "coordinates";
    private static final int GEO_PRECISION_LEVEL = 5;
    private static final double NEARBY_RADIUS_DEGREE = DistanceUtils.dist2Degrees(
            50, DistanceUtils.EARTH_MEAN_RADIUS_KM);

    private final Directory directory = new RAMDirectory();
    private final IndexWriterConfig iwConfig = new IndexWriterConfig();
    private IndexWriter indexWriter = null;
    private IndexSearcher indexSearcher = null;
    private final SpatialContext spatialCxt = SpatialContext.GEO;
    private final ShapeFactory shapeFactory = spatialCxt.getShapeFactory();
    private final SpatialStrategy coordinatesStrategy = new RecursivePrefixTreeStrategy(
            new GeohashPrefixTree(spatialCxt, GEO_PRECISION_LEVEL),
            COORDINATES_FIELD);

    // Jeospatial
    private VPTree<SimpleGeospatialPoint> jeospatialPoints = new VPTree<>();

    public MyBenchmark() {
        try {
            indexWriter = new IndexWriter(directory, iwConfig);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    @Setup
    public void init() throws IOException {
        var r = new Random();
        for (int i = 0; i < 3000; i++) {
            double latitude = ThreadLocalRandom.current().nextDouble(50.4D, 51.4D);
            double longitude = ThreadLocalRandom.current().nextDouble(8.2D, 11.2D);

            Document doc = new Document();
            doc.add(new StoredField("id", r.nextInt()));
            var point = shapeFactory.pointXY(longitude, latitude);
            for (var field : coordinatesStrategy.createIndexableFields(point)) {
                doc.add(field);
            }
            doc.add(new StoredField(coordinatesStrategy.getFieldName(), latitude + ":" + longitude));
            indexWriter.addDocument(doc);

            jeospatialPoints.add(new MyGeospatialPoint(latitude, longitude));
        }
        indexWriter.forceMerge(1);
        indexWriter.close();
        final IndexReader indexReader = DirectoryReader.open(directory);
        indexSearcher = new IndexSearcher(indexReader);
    }

    private SimpleGeospatialPoint createRandomPoint() {
        final double latitude = ThreadLocalRandom.current().nextDouble(50.4D, 51.4D);
        final double longitude = ThreadLocalRandom.current().nextDouble(8.2D, 11.2D);
        return new MyGeospatialPoint(latitude, longitude);
    }

    @Benchmark
    @BenchmarkMode(Mode.Throughput)
    @OutputTimeUnit(TimeUnit.SECONDS)
    @Fork(value = 1)
    @Warmup(iterations = 0)
    @Measurement(iterations = 3)
    public void benchLucene() {
        double latitude = ThreadLocalRandom.current().nextDouble(50.4D, 51.4D);
        double longitude = ThreadLocalRandom.current().nextDouble(8.2D, 11.2D);
        final var spatialArgs = new SpatialArgs(SpatialOperation.IsWithin,
                                                shapeFactory.circle(longitude, latitude, NEARBY_RADIUS_DEGREE));
        final Query q = coordinatesStrategy.makeQuery(spatialArgs);
        try {
            final TopDocs topDocs = indexSearcher.search(q, 1);
            if (topDocs.totalHits == 0) {
                return;
            }
            var doc = indexSearcher.doc(topDocs.scoreDocs[0].doc);
            var coordinates = doc.getField(COORDINATES_FIELD).stringValue();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    @Benchmark
    @BenchmarkMode(Mode.Throughput)
    @OutputTimeUnit(TimeUnit.SECONDS)
    @Fork(value = 1)
    @Warmup(iterations = 0)
    @Measurement(iterations = 3)
    public void benchJeospatial() {
        var neighbor = jeospatialPoints.getNearestNeighbor(createRandomPoint(), 50 * 1000);
        var n = neighbor.getLatitude();
    }
}

在 Lucene 中，我使用 RAMDirectory，但也尝试过 MMapDirectory。几乎没有区别。

基准测试结果:

# JMH version: 1.21
# VM version: JDK 10, Java HotSpot(TM) 64-Bit Server VM, 10+46
# VM invoker: /Library/Java/JavaVirtualMachines/jdk-10.jdk/Contents/Home/bin/java
# VM options: <none>
# Warmup: <none>
# Measurement: 3 iterations, 10 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Throughput, ops/time
# Benchmark: org.sample.MyBenchmark.benchJeospatial

# Run progress: 0,00% complete, ETA 00:01:00
# Fork: 1 of 1
Iteration   1: 77528,657 ops/s
Iteration   2: 81921,096 ops/s
Iteration   3: 83470,405 ops/s


Result "org.sample.MyBenchmark.benchJeospatial":
  80973,386 ±(99.9%) 56230,060 ops/s [Average]
  (min, avg, max) = (77528,657, 80973,386, 83470,405), stdev = 3082,159
  CI (99.9%): [24743,326, 137203,446] (assumes normal distribution)


# JMH version: 1.21
# VM version: JDK 10, Java HotSpot(TM) 64-Bit Server VM, 10+46
# VM invoker: /Library/Java/JavaVirtualMachines/jdk-10.jdk/Contents/Home/bin/java
# VM options: <none>
# Warmup: <none>
# Measurement: 3 iterations, 10 s each
# Timeout: 10 min per iteration
# Threads: 1 thread, will synchronize iterations
# Benchmark mode: Throughput, ops/time
# Benchmark: org.sample.MyBenchmark.benchLucene

# Run progress: 50,00% complete, ETA 00:00:31
# Fork: 1 of 1
Iteration   1: 997,103 ops/s
Iteration   2: 1087,487 ops/s
Iteration   3: 1077,964 ops/s


Result "org.sample.MyBenchmark.benchLucene":
  1054,184 ±(99.9%) 906,037 ops/s [Average]
  (min, avg, max) = (997,103, 1054,184, 1087,487), stdev = 49,663
  CI (99.9%): [148,147, 1960,221] (assumes normal distribution)


# Run complete. Total time: 00:01:03

REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on
why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial
experiments, perform baseline and negative tests that provide experimental control, make sure
the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts.
Do not assume the numbers tell you what you want them to tell.

Benchmark                     Mode  Cnt      Score       Error  Units
MyBenchmark.benchJeospatial  thrpt    3  80973,386 ± 56230,060  ops/s
MyBenchmark.benchLucene      thrpt    3   1054,184 ±   906,037  ops/s

如您所见，Jeospatial 的速度快了约 75 倍。所以我很好奇，如果这确实是真的，或者我只是以某种方式错误地配置了 Lucene。

Answer 1

注意到这是大约一年前发布的。以下内容现在与当时一样相关，但性能要好得多。

不要使用spatial-extras，使用LatLonPoint，它是更高效、更直接的 API。

这就是您所需要的:

// add your points to the document
doc.add(new LatLonPoint(fieldName, lat, lon));

// create your distance query
Query q = LatLonPoint.newDistanceQuery(fieldName, centerLat, centerLon, radiusMeters);

您遇到空间附加(在倒排索引中使用前缀树)性能问题的原因有多种:

1. 对于每个点，您都会递归四叉树，并为树的每个级别的倒排索引添加一个术语。这也意味着您的空间分辨率(和性能)取决于四叉树的深度(例如 GEO_PRECISION_LEVEL)。
带有 shapeFactory.circle 的
2. makeQuery 并不是真正的距离搜索。通过相同的四叉树分解处理圆，以创建近似圆的项(四元胞)集合。然后使用 JTS.relate 对照圆的栅格检查倒排索引中的项，这是一项极其昂贵的操作。

另一方面，

LatLonPoint 创建 block KD 树结构而不是使用倒排索引。它是一种专为大规模空间和多维数字而设计的数据结构。它的空间和时间效率更高，并且在非常大的数据集上表现更好。

希望这有帮助!