You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ds...@apache.org on 2013/02/15 07:02:27 UTC
svn commit: r1446452 - in /lucene/dev/trunk/lucene: ./
spatial/src/java/org/apache/lucene/spatial/prefix/
spatial/src/java/org/apache/lucene/spatial/prefix/tree/
spatial/src/test/org/apache/lucene/spatial/prefix/
spatial/src/test/org/apache/lucene/spat...
Author: dsmiley
Date: Fri Feb 15 06:02:27 2013
New Revision: 1446452
URL: http://svn.apache.org/r1446452
Log:
LUCENE-4770: Optional SpatialPrefixTree getNodes simplification
Modified:
lucene/dev/trunk/lucene/CHANGES.txt
lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PrefixTreeStrategy.java
lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/RecursivePrefixTreeStrategy.java
lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/TermQueryPrefixTreeStrategy.java
lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.java
lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/QuadPrefixTree.java
lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.java
lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/JtsPolygonTest.java
lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/SpatialOpRecursivePrefixTreeTest.java
lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeTest.java
Modified: lucene/dev/trunk/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/CHANGES.txt?rev=1446452&r1=1446451&r2=1446452&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/CHANGES.txt (original)
+++ lucene/dev/trunk/lucene/CHANGES.txt Fri Feb 15 06:02:27 2013
@@ -220,6 +220,15 @@ Bug Fixes
MergePolicy.OneMerge.totalBytesSize thread safe (Josh Bronson via
Robert Muir, Mike McCandless)
+* LUCENE-4770: If spatial's TermQueryPrefixTreeStrategy was used to search
+ indexed non-point shapes, then there was an edge case where a query should
+ find a shape but it didn't. The fix is the removal of an optimization that
+ simplifies some leaf cells into a parent. The index data for such a field is
+ now ~20% larger. This optimization is still done for the query shape, and for
+ indexed data for RecursivePrefixTreeStrategy. Furthermore, this optimization
+ is enhanced to roll up beyond the bottom cell level. (David Smiley,
+ Florian Schilling)
+
Documentation
* LUCENE-4718: Fixed documentation of oal.queryparser.classic.
Modified: lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PrefixTreeStrategy.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PrefixTreeStrategy.java?rev=1446452&r1=1446451&r2=1446452&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PrefixTreeStrategy.java (original)
+++ lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/PrefixTreeStrategy.java Fri Feb 15 06:02:27 2013
@@ -78,12 +78,14 @@ import java.util.concurrent.ConcurrentHa
public abstract class PrefixTreeStrategy extends SpatialStrategy {
protected final SpatialPrefixTree grid;
private final Map<String, PointPrefixTreeFieldCacheProvider> provider = new ConcurrentHashMap<String, PointPrefixTreeFieldCacheProvider>();
+ protected final boolean simplifyIndexedCells;
protected int defaultFieldValuesArrayLen = 2;
protected double distErrPct = SpatialArgs.DEFAULT_DISTERRPCT;// [ 0 TO 0.5 ]
- public PrefixTreeStrategy(SpatialPrefixTree grid, String fieldName) {
+ public PrefixTreeStrategy(SpatialPrefixTree grid, String fieldName, boolean simplifyIndexedCells) {
super(grid.getSpatialContext(), fieldName);
this.grid = grid;
+ this.simplifyIndexedCells = simplifyIndexedCells;
}
/**
@@ -123,7 +125,7 @@ public abstract class PrefixTreeStrategy
public Field[] createIndexableFields(Shape shape, double distErr) {
int detailLevel = grid.getLevelForDistance(distErr);
- List<Node> cells = grid.getNodes(shape, detailLevel, true);//true=intermediates cells
+ List<Node> cells = grid.getNodes(shape, detailLevel, true, simplifyIndexedCells);//intermediates cells
//TODO is CellTokenStream supposed to be re-used somehow? see Uwe's comments:
// http://code.google.com/p/lucene-spatial-playground/issues/detail?id=4
Modified: lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/RecursivePrefixTreeStrategy.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/RecursivePrefixTreeStrategy.java?rev=1446452&r1=1446451&r2=1446452&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/RecursivePrefixTreeStrategy.java (original)
+++ lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/RecursivePrefixTreeStrategy.java Fri Feb 15 06:02:27 2013
@@ -38,7 +38,8 @@ public class RecursivePrefixTreeStrategy
private int prefixGridScanLevel;
public RecursivePrefixTreeStrategy(SpatialPrefixTree grid, String fieldName) {
- super(grid, fieldName);
+ super(grid, fieldName,
+ true);//simplify indexed cells
prefixGridScanLevel = grid.getMaxLevels() - 4;//TODO this default constant is dependent on the prefix grid size
}
Modified: lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/TermQueryPrefixTreeStrategy.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/TermQueryPrefixTreeStrategy.java?rev=1446452&r1=1446451&r2=1446452&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/TermQueryPrefixTreeStrategy.java (original)
+++ lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/TermQueryPrefixTreeStrategy.java Fri Feb 15 06:02:27 2013
@@ -32,7 +32,7 @@ import java.util.List;
/**
* A basic implementation of {@link PrefixTreeStrategy} using a large {@link
* TermsFilter} of all the nodes from {@link SpatialPrefixTree#getNodes(com.spatial4j.core.shape.Shape,
- * int, boolean)}. It only supports the search of indexed Point shapes.
+ * int, boolean, boolean)}. It only supports the search of indexed Point shapes.
* <p/>
* The precision of query shapes (distErrPct) is an important factor in using
* this Strategy. If the precision is too precise then it will result in many
@@ -43,7 +43,8 @@ import java.util.List;
public class TermQueryPrefixTreeStrategy extends PrefixTreeStrategy {
public TermQueryPrefixTreeStrategy(SpatialPrefixTree grid, String fieldName) {
- super(grid, fieldName);
+ super(grid, fieldName,
+ false);//do not simplify indexed cells
}
@Override
@@ -54,7 +55,9 @@ public class TermQueryPrefixTreeStrategy
Shape shape = args.getShape();
int detailLevel = grid.getLevelForDistance(args.resolveDistErr(ctx, distErrPct));
- List<Node> cells = grid.getNodes(shape, detailLevel, false);
+ List<Node> cells = grid.getNodes(shape, detailLevel,
+ false,//no parents
+ true);//simplify
BytesRef[] terms = new BytesRef[cells.size()];
int i = 0;
for (Node cell : cells) {
Modified: lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.java?rev=1446452&r1=1446451&r2=1446452&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.java (original)
+++ lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/GeohashPrefixTree.java Fri Feb 15 06:02:27 2013
@@ -93,12 +93,6 @@ public class GeohashPrefixTree extends S
return new GhCell(bytes, offset, len);
}
- @Override
- public List<Node> getNodes(Shape shape, int detailLevel, boolean inclParents) {
- return shape instanceof Point ? super.getNodesAltPoint((Point) shape, detailLevel, inclParents) :
- super.getNodes(shape, detailLevel, inclParents);
- }
-
class GhCell extends Node {
GhCell(String token) {
super(token);
Modified: lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/QuadPrefixTree.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/QuadPrefixTree.java?rev=1446452&r1=1446451&r2=1446452&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/QuadPrefixTree.java (original)
+++ lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/QuadPrefixTree.java Fri Feb 15 06:02:27 2013
@@ -156,14 +156,6 @@ public class QuadPrefixTree extends Spat
return new QuadCell(bytes, offset, len);
}
- @Override //for performance
- public List<Node> getNodes(Shape shape, int detailLevel, boolean inclParents) {
- if (shape instanceof Point)
- return super.getNodesAltPoint((Point) shape, detailLevel, inclParents);
- else
- return super.getNodes(shape, detailLevel, inclParents);
- }
-
private void build(
double x,
double y,
Modified: lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.java?rev=1446452&r1=1446451&r2=1446452&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.java (original)
+++ lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.java Fri Feb 15 06:02:27 2013
@@ -116,88 +116,86 @@ public abstract class SpatialPrefixTree
}
/**
- * Gets the intersecting & including cells for the specified shape, without exceeding detail level.
- * The result is a set of cells (no dups), sorted. Unmodifiable.
+ * Gets the intersecting cells for the specified shape, without exceeding
+ * detail level. If a cell is within the query shape then it's marked as a
+ * leaf and none of its children are added.
* <p/>
- * This implementation checks if shape is a Point and if so uses an implementation that
- * recursively calls {@link Node#getSubCell(com.spatial4j.core.shape.Point)}. Cell subclasses
- * ideally implement that method with a quick implementation, otherwise, subclasses should
- * override this method to invoke {@link #getNodesAltPoint(com.spatial4j.core.shape.Point, int, boolean)}.
- * TODO consider another approach returning an iterator -- won't build up all cells in memory.
+ * This implementation checks if shape is a Point and if so returns {@link
+ * #getNodes(com.spatial4j.core.shape.Point, int, boolean)}.
+ *
+ * @param shape the shape; non-null
+ * @param detailLevel the maximum detail level to get cells for
+ * @param inclParents if true then all parent cells of leaves are returned
+ * too. The top world cell is never returned.
+ * @param simplify for non-point shapes, this will simply/aggregate sets of
+ * complete leaves in a cell to its parent, resulting in
+ * ~20-25% fewer cells.
+ * @return a set of cells (no dups), sorted, immutable, non-null
*/
- public List<Node> getNodes(Shape shape, int detailLevel, boolean inclParents) {
+ public List<Node> getNodes(Shape shape, int detailLevel, boolean inclParents,
+ boolean simplify) {
+ //TODO consider an on-demand iterator -- it won't build up all cells in memory.
if (detailLevel > maxLevels) {
throw new IllegalArgumentException("detailLevel > maxLevels");
}
-
- List<Node> cells;
if (shape instanceof Point) {
- //optimized point algorithm
- final int initialCapacity = inclParents ? 1 + detailLevel : 1;
- cells = new ArrayList<Node>(initialCapacity);
- recursiveGetNodes(getWorldNode(), (Point) shape, detailLevel, true, cells);
- assert cells.size() == initialCapacity;
- } else {
- cells = new ArrayList<Node>(inclParents ? 1024 : 512);
- recursiveGetNodes(getWorldNode(), shape, detailLevel, inclParents, cells);
- }
- if (inclParents) {
- Node c = cells.remove(0);//remove getWorldNode()
- assert c.getLevel() == 0;
+ return getNodes((Point) shape, detailLevel, inclParents);
}
+ List<Node> cells = new ArrayList<Node>(inclParents ? 4096 : 2048);
+ recursiveGetNodes(getWorldNode(), shape, detailLevel, inclParents, simplify, cells);
return cells;
}
- private void recursiveGetNodes(Node node, Shape shape, int detailLevel, boolean inclParents,
- Collection<Node> result) {
- if (node.isLeaf()) {//cell is within shape
- result.add(node);
- return;
- }
- final Collection<Node> subCells = node.getSubCells(shape);
- if (node.getLevel() == detailLevel - 1) {
- if (subCells.size() < node.getSubCellsSize() || node.getLevel() == 0) {
- if (inclParents)
- result.add(node);
- for (Node subCell : subCells) {
- subCell.setLeaf();
- }
- result.addAll(subCells);
- } else {//a bottom level (i.e. detail level) optimization where all boxes intersect, so use parent cell.
- node.setLeaf();//the cell may not be strictly within but its close
- result.add(node);
- }
- } else {
- if (inclParents) {
- result.add(node);
- }
- for (Node subCell : subCells) {
- recursiveGetNodes(subCell, shape, detailLevel, inclParents, result);//tail call
- }
+ /**
+ * Returns true if node was added as a leaf. If it wasn't it recursively
+ * descends.
+ */
+ private boolean recursiveGetNodes(Node node, Shape shape, int detailLevel,
+ boolean inclParents, boolean simplify,
+ List<Node> result) {
+ if (node.getLevel() == detailLevel) {
+ node.setLeaf();//FYI might already be a leaf
}
- }
-
- private void recursiveGetNodes(Node node, Point point, int detailLevel, boolean inclParents,
- Collection<Node> result) {
- if (inclParents) {
+ if (node.isLeaf()) {
result.add(node);
+ return true;
}
- final Node pCell = node.getSubCell(point);
- if (node.getLevel() == detailLevel - 1) {
- pCell.setLeaf();
- result.add(pCell);
- } else {
- recursiveGetNodes(pCell, point, detailLevel, inclParents, result);//tail call
+ if (inclParents && node.getLevel() != 0)
+ result.add(node);
+
+ Collection<Node> subCells = node.getSubCells(shape);
+ int leaves = 0;
+ for (Node subCell : subCells) {
+ if (recursiveGetNodes(subCell, shape, detailLevel, inclParents, simplify, result))
+ leaves++;
+ }
+ //can we simplify?
+ if (simplify && leaves == node.getSubCellsSize() && node.getLevel() != 0) {
+ //Optimization: substitute the parent as a leaf instead of adding all
+ // children as leaves
+
+ //remove the leaves
+ do {
+ result.remove(result.size() - 1);//remove last
+ } while (--leaves > 0);
+ //add node as the leaf
+ node.setLeaf();
+ if (!inclParents) // otherwise it was already added up above
+ result.add(node);
+ return true;
}
+ return false;
}
/**
- * Subclasses might override {@link #getNodes(com.spatial4j.core.shape.Shape, int, boolean)}
- * and check if the argument is a shape and if so, delegate
- * to this implementation, which calls {@link #getNode(com.spatial4j.core.shape.Point, int)} and
- * then calls {@link #getNode(String)} repeatedly if inclParents is true.
+ * A Point-optimized implementation of
+ * {@link #getNodes(com.spatial4j.core.shape.Shape, int, boolean, boolean)}. That
+ * method in facts calls this for points.
+ * <p/>
+ * This implementation depends on {@link #getNode(String)} being fast, as its
+ * called repeatedly when incPlarents is true.
*/
- protected final List<Node> getNodesAltPoint(Point p, int detailLevel, boolean inclParents) {
+ public List<Node> getNodes(Point p, int detailLevel, boolean inclParents) {
Node cell = getNode(p, detailLevel);
if (!inclParents) {
return Collections.singletonList(cell);
Modified: lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/JtsPolygonTest.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/JtsPolygonTest.java?rev=1446452&r1=1446451&r2=1446452&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/JtsPolygonTest.java (original)
+++ lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/JtsPolygonTest.java Fri Feb 15 06:02:27 2013
@@ -18,9 +18,19 @@ package org.apache.lucene.spatial.prefix
*/
import com.spatial4j.core.context.SpatialContextFactory;
+import com.spatial4j.core.shape.Point;
import com.spatial4j.core.shape.Shape;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.Field.Store;
+import org.apache.lucene.document.TextField;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.ScoreDoc;
+import org.apache.lucene.search.TopDocs;
import org.apache.lucene.spatial.StrategyTestCase;
import org.apache.lucene.spatial.prefix.tree.GeohashPrefixTree;
+import org.apache.lucene.spatial.prefix.tree.QuadPrefixTree;
+import org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree;
import org.apache.lucene.spatial.query.SpatialArgs;
import org.apache.lucene.spatial.query.SpatialOperation;
import org.junit.Test;
@@ -70,4 +80,39 @@ public class JtsPolygonTest extends Stra
return args;
}
+ /**
+ * A PrefixTree pruning optimization gone bad.
+ * See <a href="https://issues.apache.org/jira/browse/LUCENE-4770>LUCENE-4770</a>.
+ */
+ @Test
+ public void testBadPrefixTreePrune() throws Exception {
+
+ Shape area = ctx.readShape("POLYGON((-122.83 48.57, -122.77 48.56, -122.79 48.53, -122.83 48.57))");
+
+ SpatialPrefixTree trie = new QuadPrefixTree(ctx, 12);
+ TermQueryPrefixTreeStrategy strategy = new TermQueryPrefixTreeStrategy(trie, "geo");
+ Document doc = new Document();
+ doc.add(new TextField("id", "1", Store.YES));
+
+ Field[] fields = strategy.createIndexableFields(area, 0.025);
+ for (Field field : fields) {
+ doc.add(field);
+ }
+ addDocument(doc);
+
+ Point upperleft = ctx.makePoint(-122.88, 48.54);
+ Point lowerright = ctx.makePoint(-122.82, 48.62);
+
+ Query query = strategy.makeQuery(new SpatialArgs(SpatialOperation.Intersects, ctx.makeRectangle(upperleft, lowerright)));
+ commit();
+
+ TopDocs search = indexSearcher.search(query, 10);
+ ScoreDoc[] scoreDocs = search.scoreDocs;
+ for (ScoreDoc scoreDoc : scoreDocs) {
+ System.out.println(indexSearcher.doc(scoreDoc.doc));
+ }
+
+ assertEquals(1, search.totalHits);
+ }
+
}
Modified: lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/SpatialOpRecursivePrefixTreeTest.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/SpatialOpRecursivePrefixTreeTest.java?rev=1446452&r1=1446451&r2=1446452&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/SpatialOpRecursivePrefixTreeTest.java (original)
+++ lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/SpatialOpRecursivePrefixTreeTest.java Fri Feb 15 06:02:27 2013
@@ -113,7 +113,7 @@ public class SpatialOpRecursivePrefixTre
double distErrPct = ((PrefixTreeStrategy) strategy).getDistErrPct();
double distErr = SpatialArgs.calcDistanceFromErrPct(snapMe, distErrPct, ctx);
int detailLevel = grid.getLevelForDistance(distErr);
- List<Node> cells = grid.getNodes(snapMe, detailLevel, false);
+ List<Node> cells = grid.getNodes(snapMe, detailLevel, false, true);
//calc bounding box of cells.
double minX = Double.POSITIVE_INFINITY, maxX = Double.NEGATIVE_INFINITY;
Modified: lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeTest.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeTest.java?rev=1446452&r1=1446451&r2=1446452&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeTest.java (original)
+++ lucene/dev/trunk/lucene/spatial/src/test/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTreeTest.java Fri Feb 15 06:02:27 2013
@@ -18,14 +18,24 @@
package org.apache.lucene.spatial.prefix.tree;
import com.spatial4j.core.context.SpatialContext;
+import com.spatial4j.core.shape.Point;
import com.spatial4j.core.shape.Rectangle;
import com.spatial4j.core.shape.Shape;
-
-import org.apache.lucene.util.LuceneTestCase;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.Field;
+import org.apache.lucene.document.Field.Store;
+import org.apache.lucene.document.TextField;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.ScoreDoc;
+import org.apache.lucene.search.TopDocs;
+import org.apache.lucene.spatial.SpatialTestCase;
+import org.apache.lucene.spatial.prefix.TermQueryPrefixTreeStrategy;
+import org.apache.lucene.spatial.query.SpatialArgs;
+import org.apache.lucene.spatial.query.SpatialOperation;
import org.junit.Before;
import org.junit.Test;
-public class SpatialPrefixTreeTest extends LuceneTestCase {
+public class SpatialPrefixTreeTest extends SpatialTestCase {
//TODO plug in others and test them
private SpatialContext ctx;
@@ -36,11 +46,12 @@ public class SpatialPrefixTreeTest exten
public void setUp() throws Exception {
super.setUp();
ctx = SpatialContext.GEO;
- trie = new GeohashPrefixTree(ctx,4);
}
@Test
public void testNodeTraverse() {
+ trie = new GeohashPrefixTree(ctx,4);
+
Node prevN = null;
Node n = trie.getWorldNode();
assertEquals(0,n.getLevel());
@@ -57,4 +68,40 @@ public class SpatialPrefixTreeTest exten
assertTrue(prevNShape.getHeight() > sbox.getHeight());
}
}
-}
+ /**
+ * A PrefixTree pruning optimization gone bad.
+ * See <a href="https://issues.apache.org/jira/browse/LUCENE-4770>LUCENE-4770</a>.
+ */
+ @Test
+ public void testBadPrefixTreePrune() throws Exception {
+
+ trie = new QuadPrefixTree(ctx, 12);
+ TermQueryPrefixTreeStrategy strategy = new TermQueryPrefixTreeStrategy(trie, "geo");
+ Document doc = new Document();
+ doc.add(new TextField("id", "1", Store.YES));
+
+ Shape area = ctx.makeRectangle(-122.82, -122.78, 48.54, 48.56);
+
+ Field[] fields = strategy.createIndexableFields(area, 0.025);
+ for (Field field : fields) {
+ doc.add(field);
+ }
+ addDocument(doc);
+
+ Point upperleft = ctx.makePoint(-122.88, 48.54);
+ Point lowerright = ctx.makePoint(-122.82, 48.62);
+
+ Query query = strategy.makeQuery(new SpatialArgs(SpatialOperation.Intersects, ctx.makeRectangle(upperleft, lowerright)));
+
+ commit();
+
+ TopDocs search = indexSearcher.search(query, 10);
+ ScoreDoc[] scoreDocs = search.scoreDocs;
+ for (ScoreDoc scoreDoc : scoreDocs) {
+ System.out.println(indexSearcher.doc(scoreDoc.doc));
+ }
+
+ assertEquals(1, search.totalHits);
+ }
+
+}
\ No newline at end of file