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 2014/03/18 14:31:03 UTC
svn commit: r1578868 - in /lucene/dev/trunk/lucene: ./
spatial/src/java/org/apache/lucene/spatial/prefix/
spatial/src/java/org/apache/lucene/spatial/prefix/tree/
Author: dsmiley
Date: Tue Mar 18 13:31:02 2014
New Revision: 1578868
URL: http://svn.apache.org/r1578868
Log:
LUCENE-5529: Spatial RPT optimization to skip intersection test on redundant cells. Other small changes too.
Modified:
lucene/dev/trunk/lucene/CHANGES.txt
lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/AbstractVisitingPrefixTreeFilter.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/SpatialPrefixTree.java
Modified: lucene/dev/trunk/lucene/CHANGES.txt
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/CHANGES.txt?rev=1578868&r1=1578867&r2=1578868&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/CHANGES.txt (original)
+++ lucene/dev/trunk/lucene/CHANGES.txt Tue Mar 18 13:31:02 2014
@@ -157,6 +157,9 @@ Optimizations
* LUCENE-5515: Improved TopDocs#merge to create a merged ScoreDoc
array with length of at most equal to the specified size instead of length
equal to at most from + size as was before. (Martijn van Groningen)
+
+* LUCENE-5529: Spatial search of non-point indexed shapes should be a little
+ faster due to skipping intersection tests on redundant cells. (David Smiley)
Bug fixes
Modified: lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/AbstractVisitingPrefixTreeFilter.java
URL: http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/AbstractVisitingPrefixTreeFilter.java?rev=1578868&r1=1578867&r2=1578868&view=diff
==============================================================================
--- lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/AbstractVisitingPrefixTreeFilter.java (original)
+++ lucene/dev/trunk/lucene/spatial/src/java/org/apache/lucene/spatial/prefix/AbstractVisitingPrefixTreeFilter.java Tue Mar 18 13:31:02 2014
@@ -17,9 +17,7 @@ package org.apache.lucene.spatial.prefix
* limitations under the License.
*/
-import java.io.IOException;
-import java.util.Iterator;
-
+import com.spatial4j.core.shape.Shape;
import org.apache.lucene.index.AtomicReaderContext;
import org.apache.lucene.index.TermsEnum;
import org.apache.lucene.search.DocIdSet;
@@ -28,7 +26,9 @@ import org.apache.lucene.spatial.prefix.
import org.apache.lucene.util.Bits;
import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.StringHelper;
-import com.spatial4j.core.shape.Shape;
+
+import java.io.IOException;
+import java.util.Iterator;
/**
* Traverses a {@link SpatialPrefixTree} indexed field, using the template &
@@ -60,9 +60,7 @@ public abstract class AbstractVisitingPr
public boolean equals(Object o) {
if (!super.equals(o)) return false;//checks getClass == o.getClass & instanceof
- AbstractVisitingPrefixTreeFilter that = (AbstractVisitingPrefixTreeFilter) o;
-
- if (prefixGridScanLevel != that.prefixGridScanLevel) return false;
+ //Ignore prefixGridScanLevel as it is merely a tuning parameter.
return true;
}
@@ -70,7 +68,6 @@ public abstract class AbstractVisitingPr
@Override
public int hashCode() {
int result = super.hashCode();
- result = 31 * result + prefixGridScanLevel;
return result;
}
@@ -90,7 +87,7 @@ public abstract class AbstractVisitingPr
* method then it's short-circuited until it finds one, at which point
* {@link #visit(org.apache.lucene.spatial.prefix.tree.Cell)} is called. At
* some depths, of the tree, the algorithm switches to a scanning mode that
- * finds calls {@link #visitScanned(org.apache.lucene.spatial.prefix.tree.Cell)}
+ * calls {@link #visitScanned(org.apache.lucene.spatial.prefix.tree.Cell)}
* for each leaf cell found.
*
* @lucene.internal
@@ -218,7 +215,7 @@ public abstract class AbstractVisitingPr
if (hasIndexedLeaves && cell.getLevel() != 0) {
//If the next indexed term just adds a leaf marker ('+') to cell,
// then add all of those docs
- assert StringHelper.startsWith(thisTerm, curVNodeTerm);
+ assert StringHelper.startsWith(thisTerm, curVNodeTerm);//TODO refactor to use method on curVNode.cell
scanCell = grid.getCell(thisTerm.bytes, thisTerm.offset, thisTerm.length, scanCell);
if (scanCell.getLevel() == cell.getLevel() && scanCell.isLeaf()) {
visitLeaf(scanCell);
@@ -268,15 +265,17 @@ public abstract class AbstractVisitingPr
*/
protected void scan(int scanDetailLevel) throws IOException {
for (;
- thisTerm != null && StringHelper.startsWith(thisTerm, curVNodeTerm);
+ thisTerm != null && StringHelper.startsWith(thisTerm, curVNodeTerm);//TODO refactor to use method on curVNode.cell
thisTerm = termsEnum.next()) {
scanCell = grid.getCell(thisTerm.bytes, thisTerm.offset, thisTerm.length, scanCell);
int termLevel = scanCell.getLevel();
- if (termLevel > scanDetailLevel)
- continue;
- if (termLevel == scanDetailLevel || scanCell.isLeaf()) {
- visitScanned(scanCell);
+ if (termLevel < scanDetailLevel) {
+ if (scanCell.isLeaf())
+ visitScanned(scanCell);
+ } else if (termLevel == scanDetailLevel) {
+ if (!scanCell.isLeaf())//LUCENE-5529
+ visitScanned(scanCell);
}
}//term loop
}
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=1578868&r1=1578867&r2=1578868&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 Tue Mar 18 13:31:02 2014
@@ -61,7 +61,7 @@ public class TermQueryPrefixTreeStrategy
BytesRef[] terms = new BytesRef[cells.size()];
int i = 0;
for (Cell cell : cells) {
- terms[i++] = new BytesRef(cell.getTokenString());
+ terms[i++] = new BytesRef(cell.getTokenString());//TODO use cell.getTokenBytes()
}
return new TermsFilter(getFieldName(), terms);
}
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=1578868&r1=1578867&r2=1578868&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 Tue Mar 18 13:31:02 2014
@@ -228,7 +228,7 @@ public abstract class SpatialPrefixTree
assert endToken.length() == detailLevel;
List<Cell> cells = new ArrayList<>(detailLevel);
for (int i = 1; i < detailLevel; i++) {
- cells.add(getCell(endToken.substring(0, i)));
+ cells.add(getCell(endToken.substring(0, i)));//TODO refactor: add a cell.getParent()
}
cells.add(cell);
return cells;
@@ -236,6 +236,7 @@ public abstract class SpatialPrefixTree
/**
* Will add the trailing leaf byte for leaves. This isn't particularly efficient.
+ * @deprecated TODO remove; not used and not interesting, don't need collection in & out
*/
public static List<String> cellsToTokenStrings(Collection<Cell> cells) {
List<String> tokens = new ArrayList<>((cells.size()));