You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by GitBox <gi...@apache.org> on 2021/01/29 21:08:38 UTC
[GitHub] [lucene-solr] mikemccand commented on a change in pull request #2247: LUCENE-9476 Add getBulkPath API for the Taxonomy index
mikemccand commented on a change in pull request #2247:
URL: https://github.com/apache/lucene-solr/pull/2247#discussion_r567085518
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/taxonomy/directory/DirectoryTaxonomyReader.java
##########
@@ -353,12 +349,104 @@ public FacetLabel getPath(int ordinal) throws IOException {
}
synchronized (categoryCache) {
- categoryCache.put(catIDInteger, ret);
+ categoryCache.put(ordinal, ret);
}
return ret;
}
+ private FacetLabel getPathFromCache(int ordinal) {
+ // TODO: can we use an int-based hash impl, such as IntToObjectMap,
Review comment:
Oooh that is a great idea, and low-hanging fruit, and would greatly reduce the RAM usage for this cache.
I think `DirectoryTaxonomyWriter` also has such a cache that we could change to a native map.
Could you open a spinoff issue?
##########
File path: lucene/CHANGES.txt
##########
@@ -11,6 +11,8 @@ New Features
* LUCENE-9004: Approximate nearest vector search via NSW graphs
+* LUCENE-9476: DirectoryTaxonomyReader now provides a getBulkPath API (Gautam Worah)
Review comment:
Can you expand a bit more? E.g.:
```
LUCENE-9476: add new getBulkPath API to DirectoryTaxonomyReader to more efficiently retrieve FacetLabels for multiple facet ordinals at once
```
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/taxonomy/directory/DirectoryTaxonomyReader.java
##########
@@ -353,12 +349,104 @@ public FacetLabel getPath(int ordinal) throws IOException {
}
synchronized (categoryCache) {
- categoryCache.put(catIDInteger, ret);
+ categoryCache.put(ordinal, ret);
}
return ret;
}
+ private FacetLabel getPathFromCache(int ordinal) {
+ // TODO: can we use an int-based hash impl, such as IntToObjectMap,
+ // wrapped as LRU?
+ synchronized (categoryCache) {
+ return categoryCache.get(ordinal);
+ }
+ }
+
+ private void isOrdinalInIndexReaderRange(int ordinal, int indexReaderMaxDoc)
+ throws IllegalArgumentException {
+ if (ordinal < 0 || ordinal >= indexReaderMaxDoc) {
+ throw new IllegalArgumentException(
+ "ordinal "
+ + ordinal
+ + " is out of the range of the indexReader "
+ + indexReader.toString());
+ }
+ }
+
+ /**
+ * Returns an array of FacetLabels for a given array of ordinals.
+ *
+ * <p>This API is generally faster than iteratively calling {@link
+ * org.apache.lucene.facet.taxonomy.directory.DirectoryTaxonomyReader#getPath} over an array of
+ * ordinals.
+ *
+ * <p>This API is only available for Lucene indexes created with 8.7+ codec because it uses
+ * BinaryDocValues instead of StoredFields. Use the {@link
+ * org.apache.lucene.facet.taxonomy.directory.DirectoryTaxonomyReader#getPath} method for indices
+ * created with codec version older than 8.7.
+ *
+ * @param ordinals Array of ordinals that are assigned to categories inserted into the taxonomy
+ * index
+ * @throws IOException if the taxonomy index is created using the older StoredFields based codec.
+ */
+ public FacetLabel[] getBulkPath(int... ordinals) throws IOException {
+ ensureOpen();
+
+ FacetLabel[] bulkPath = new FacetLabel[ordinals.length];
+ // remember the original positions of ordinals before they are sorted
+ IntIntScatterMap originalPosition = new IntIntScatterMap();
+ int indexReaderMaxDoc = indexReader.maxDoc();
+ for (int i = 0; i < ordinals.length; i++) {
+ // check whether the ordinal is valid before accessing the cache
+ isOrdinalInIndexReaderRange(ordinals[i], indexReaderMaxDoc);
+ // check the cache before trying to find it in the index
+ FacetLabel ordinalPath = getPathFromCache(ordinals[i]);
+ if (ordinalPath != null) {
+ bulkPath[i] = ordinalPath;
+ }
+ originalPosition.put(ordinals[i], i);
+ }
+
+ Arrays.sort(ordinals);
+ int readerIndex;
+ int leafReaderMaxDoc = 0;
+ int leafReaderDocBase = 0;
+ LeafReader leafReader;
+ LeafReaderContext leafReaderContext = null;
+ BinaryDocValues values = null;
+
+ for (int ord : ordinals) {
+ if (bulkPath[originalPosition.get(ord)] == null) {
+ if (values == null || ord > leafReaderMaxDoc) {
+
+ readerIndex = ReaderUtil.subIndex(ord, indexReader.leaves());
+ leafReaderContext = indexReader.leaves().get(readerIndex);
+ leafReader = leafReaderContext.reader();
+ leafReaderMaxDoc = leafReader.maxDoc();
+ leafReaderDocBase = leafReaderContext.docBase;
+ values = leafReader.getBinaryDocValues(Consts.FULL);
+
+ // this check is only needed once to confirm that the index uses BinaryDocValues
+ boolean success = values.advanceExact(ord - leafReaderDocBase);
+ if (success == false) {
+ throw new IOException(
+ "the taxonomy index is created using the older StoredFields format which uses a Lucene "
+ + "codec older than 8.7. Use the getPath(int ordinal) API iteratively instead.");
+ }
+ }
+ values.advanceExact(ord - leafReaderDocBase);
Review comment:
Hmm can we `assert` that this indeed returned `true`?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/taxonomy/directory/DirectoryTaxonomyReader.java
##########
@@ -353,12 +349,104 @@ public FacetLabel getPath(int ordinal) throws IOException {
}
synchronized (categoryCache) {
- categoryCache.put(catIDInteger, ret);
+ categoryCache.put(ordinal, ret);
}
return ret;
}
+ private FacetLabel getPathFromCache(int ordinal) {
+ // TODO: can we use an int-based hash impl, such as IntToObjectMap,
+ // wrapped as LRU?
+ synchronized (categoryCache) {
+ return categoryCache.get(ordinal);
+ }
+ }
+
+ private void isOrdinalInIndexReaderRange(int ordinal, int indexReaderMaxDoc)
Review comment:
Maybe rename to `checkOrdinalBounds`? The `is` name prefix makes me think it returns a `boolean`.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/taxonomy/directory/DirectoryTaxonomyReader.java
##########
@@ -353,12 +349,104 @@ public FacetLabel getPath(int ordinal) throws IOException {
}
synchronized (categoryCache) {
- categoryCache.put(catIDInteger, ret);
+ categoryCache.put(ordinal, ret);
}
return ret;
}
+ private FacetLabel getPathFromCache(int ordinal) {
+ // TODO: can we use an int-based hash impl, such as IntToObjectMap,
+ // wrapped as LRU?
+ synchronized (categoryCache) {
+ return categoryCache.get(ordinal);
+ }
+ }
+
+ private void isOrdinalInIndexReaderRange(int ordinal, int indexReaderMaxDoc)
+ throws IllegalArgumentException {
+ if (ordinal < 0 || ordinal >= indexReaderMaxDoc) {
+ throw new IllegalArgumentException(
+ "ordinal "
+ + ordinal
+ + " is out of the range of the indexReader "
+ + indexReader.toString());
+ }
+ }
+
+ /**
+ * Returns an array of FacetLabels for a given array of ordinals.
+ *
+ * <p>This API is generally faster than iteratively calling {@link
+ * org.apache.lucene.facet.taxonomy.directory.DirectoryTaxonomyReader#getPath} over an array of
+ * ordinals.
+ *
+ * <p>This API is only available for Lucene indexes created with 8.7+ codec because it uses
+ * BinaryDocValues instead of StoredFields. Use the {@link
+ * org.apache.lucene.facet.taxonomy.directory.DirectoryTaxonomyReader#getPath} method for indices
+ * created with codec version older than 8.7.
+ *
+ * @param ordinals Array of ordinals that are assigned to categories inserted into the taxonomy
+ * index
+ * @throws IOException if the taxonomy index is created using the older StoredFields based codec.
+ */
+ public FacetLabel[] getBulkPath(int... ordinals) throws IOException {
+ ensureOpen();
+
+ FacetLabel[] bulkPath = new FacetLabel[ordinals.length];
+ // remember the original positions of ordinals before they are sorted
+ IntIntScatterMap originalPosition = new IntIntScatterMap();
+ int indexReaderMaxDoc = indexReader.maxDoc();
+ for (int i = 0; i < ordinals.length; i++) {
+ // check whether the ordinal is valid before accessing the cache
+ isOrdinalInIndexReaderRange(ordinals[i], indexReaderMaxDoc);
+ // check the cache before trying to find it in the index
+ FacetLabel ordinalPath = getPathFromCache(ordinals[i]);
+ if (ordinalPath != null) {
+ bulkPath[i] = ordinalPath;
+ }
+ originalPosition.put(ordinals[i], i);
+ }
+
+ Arrays.sort(ordinals);
+ int readerIndex;
+ int leafReaderMaxDoc = 0;
+ int leafReaderDocBase = 0;
+ LeafReader leafReader;
+ LeafReaderContext leafReaderContext = null;
+ BinaryDocValues values = null;
+
+ for (int ord : ordinals) {
+ if (bulkPath[originalPosition.get(ord)] == null) {
+ if (values == null || ord > leafReaderMaxDoc) {
+
+ readerIndex = ReaderUtil.subIndex(ord, indexReader.leaves());
+ leafReaderContext = indexReader.leaves().get(readerIndex);
+ leafReader = leafReaderContext.reader();
+ leafReaderMaxDoc = leafReader.maxDoc();
+ leafReaderDocBase = leafReaderContext.docBase;
+ values = leafReader.getBinaryDocValues(Consts.FULL);
+
+ // this check is only needed once to confirm that the index uses BinaryDocValues
+ boolean success = values.advanceExact(ord - leafReaderDocBase);
+ if (success == false) {
+ throw new IOException(
Review comment:
Hmm, instead, could we just forward to the slow `getPath` API for this case? And then update the javadocs to state that if you call this on a pre-8.7 written taxonomy index, it will "emulate" bulk by calling the single lookup API multiple times, i.e. no performance gains, but on newer indices, yes performance gains?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/taxonomy/directory/DirectoryTaxonomyReader.java
##########
@@ -353,12 +349,104 @@ public FacetLabel getPath(int ordinal) throws IOException {
}
synchronized (categoryCache) {
- categoryCache.put(catIDInteger, ret);
+ categoryCache.put(ordinal, ret);
}
return ret;
}
+ private FacetLabel getPathFromCache(int ordinal) {
+ // TODO: can we use an int-based hash impl, such as IntToObjectMap,
+ // wrapped as LRU?
+ synchronized (categoryCache) {
+ return categoryCache.get(ordinal);
+ }
+ }
+
+ private void isOrdinalInIndexReaderRange(int ordinal, int indexReaderMaxDoc)
+ throws IllegalArgumentException {
+ if (ordinal < 0 || ordinal >= indexReaderMaxDoc) {
+ throw new IllegalArgumentException(
+ "ordinal "
+ + ordinal
+ + " is out of the range of the indexReader "
+ + indexReader.toString());
+ }
+ }
+
+ /**
+ * Returns an array of FacetLabels for a given array of ordinals.
+ *
+ * <p>This API is generally faster than iteratively calling {@link
+ * org.apache.lucene.facet.taxonomy.directory.DirectoryTaxonomyReader#getPath} over an array of
Review comment:
Hmm does `{@link #getPath}` not work? Does that somehow fail `gradle precommit` or something?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/taxonomy/directory/DirectoryTaxonomyReader.java
##########
@@ -320,18 +322,12 @@ public FacetLabel getPath(int ordinal) throws IOException {
// doOpenIfChanged, we need to ensure that the ordinal is one that this DTR
// instance recognizes. Therefore we do this check up front, before we hit
// the cache.
- if (ordinal < 0 || ordinal >= indexReader.maxDoc()) {
- return null;
- }
+ int indexReaderMaxDoc = indexReader.maxDoc();
+ isOrdinalInIndexReaderRange(ordinal, indexReaderMaxDoc);
Review comment:
Ahh, I see, this is a (small) API break for `getPath`, throwing exception instead of leniently returning `null`, but I think it is the right change since it serves to expose bugs in the Lucene user's usage of facets APIs.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/taxonomy/directory/DirectoryTaxonomyReader.java
##########
@@ -353,12 +349,65 @@ public FacetLabel getPath(int ordinal) throws IOException {
}
synchronized (categoryCache) {
- categoryCache.put(catIDInteger, ret);
+ categoryCache.put(ordinal, ret);
}
return ret;
}
+ private FacetLabel getPathFromCache(int ordinal) {
+ ensureOpen();
+
+ // TODO: can we use an int-based hash impl, such as IntToObjectMap,
+ // wrapped as LRU?
+ synchronized (categoryCache) {
+ FacetLabel res = categoryCache.get(ordinal);
+ if (res != null) {
+ return res;
+ }
+ }
+ return null;
+ }
+
+ /* This API is only supported for indexes created with Lucene 8.7+ codec **/
+ public FacetLabel[] getBulkPath(int[] ordinal) throws IOException {
+ FacetLabel[] bulkPath = new FacetLabel[ordinal.length];
+ Map<Integer, Integer> originalPosition = new HashMap<>();
+ for (int i = 0; i < ordinal.length; i++) {
+ if (ordinal[i] < 0 || ordinal[i] >= indexReader.maxDoc()) {
+ return null;
+ }
+ FacetLabel ordinalPath = getPathFromCache(ordinal[i]);
+ if (ordinalPath != null) {
+ bulkPath[i] = ordinalPath;
+ }
+ originalPosition.put(ordinal[i], i);
+ }
+
+ Arrays.sort(ordinal);
+ int readerIndex = 0;
+ BinaryDocValues values = null;
+
+ for (int ord : ordinal) {
+ if (bulkPath[originalPosition.get(ord)] == null) {
Review comment:
Ahhh, I see!
But then, shouldn't we just not enroll that ordinal/index into the map, up front?
##########
File path: lucene/facet/src/test/org/apache/lucene/facet/taxonomy/directory/TestDirectoryTaxonomyReader.java
##########
@@ -569,4 +569,32 @@ public void testAccountable() throws Exception {
taxoReader.close();
dir.close();
}
+
+ public void testCallingBulkPathReturnsCorrectResult() throws Exception {
+ Directory src = newDirectory();
+ DirectoryTaxonomyWriter w = new DirectoryTaxonomyWriter(src);
+ String randomArray[] = new String[random().nextInt(1000)];
+ Arrays.setAll(randomArray, i -> Integer.toString(random().nextInt()));
+
+ FacetLabel allPaths[] = new FacetLabel[randomArray.length];
+ int allOrdinals[] = new int[randomArray.length];
+
+ for (int i = 0; i < randomArray.length; i++) {
+ allPaths[i] = new FacetLabel(randomArray[i]);
+ w.addCategory(allPaths[i]);
Review comment:
Could we randomly `w.commit()` in here with low but non-zero chance? This way we will sometimes exercise a multi-segment taxo index.
And, could you temporarily put the `assert` back from the first revision and confirm this test case eventually would catch that bug?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/taxonomy/directory/DirectoryTaxonomyReader.java
##########
@@ -353,12 +349,104 @@ public FacetLabel getPath(int ordinal) throws IOException {
}
synchronized (categoryCache) {
- categoryCache.put(catIDInteger, ret);
+ categoryCache.put(ordinal, ret);
}
return ret;
}
+ private FacetLabel getPathFromCache(int ordinal) {
+ // TODO: can we use an int-based hash impl, such as IntToObjectMap,
+ // wrapped as LRU?
+ synchronized (categoryCache) {
+ return categoryCache.get(ordinal);
+ }
+ }
+
+ private void isOrdinalInIndexReaderRange(int ordinal, int indexReaderMaxDoc)
+ throws IllegalArgumentException {
+ if (ordinal < 0 || ordinal >= indexReaderMaxDoc) {
+ throw new IllegalArgumentException(
+ "ordinal "
+ + ordinal
+ + " is out of the range of the indexReader "
+ + indexReader.toString());
+ }
+ }
+
+ /**
+ * Returns an array of FacetLabels for a given array of ordinals.
+ *
+ * <p>This API is generally faster than iteratively calling {@link
+ * org.apache.lucene.facet.taxonomy.directory.DirectoryTaxonomyReader#getPath} over an array of
+ * ordinals.
+ *
+ * <p>This API is only available for Lucene indexes created with 8.7+ codec because it uses
+ * BinaryDocValues instead of StoredFields. Use the {@link
+ * org.apache.lucene.facet.taxonomy.directory.DirectoryTaxonomyReader#getPath} method for indices
+ * created with codec version older than 8.7.
+ *
+ * @param ordinals Array of ordinals that are assigned to categories inserted into the taxonomy
+ * index
+ * @throws IOException if the taxonomy index is created using the older StoredFields based codec.
+ */
+ public FacetLabel[] getBulkPath(int... ordinals) throws IOException {
+ ensureOpen();
+
+ FacetLabel[] bulkPath = new FacetLabel[ordinals.length];
+ // remember the original positions of ordinals before they are sorted
+ IntIntScatterMap originalPosition = new IntIntScatterMap();
+ int indexReaderMaxDoc = indexReader.maxDoc();
+ for (int i = 0; i < ordinals.length; i++) {
+ // check whether the ordinal is valid before accessing the cache
+ isOrdinalInIndexReaderRange(ordinals[i], indexReaderMaxDoc);
+ // check the cache before trying to find it in the index
+ FacetLabel ordinalPath = getPathFromCache(ordinals[i]);
+ if (ordinalPath != null) {
+ bulkPath[i] = ordinalPath;
+ }
+ originalPosition.put(ordinals[i], i);
+ }
+
+ Arrays.sort(ordinals);
+ int readerIndex;
+ int leafReaderMaxDoc = 0;
+ int leafReaderDocBase = 0;
+ LeafReader leafReader;
+ LeafReaderContext leafReaderContext = null;
+ BinaryDocValues values = null;
+
+ for (int ord : ordinals) {
+ if (bulkPath[originalPosition.get(ord)] == null) {
+ if (values == null || ord > leafReaderMaxDoc) {
+
+ readerIndex = ReaderUtil.subIndex(ord, indexReader.leaves());
+ leafReaderContext = indexReader.leaves().get(readerIndex);
+ leafReader = leafReaderContext.reader();
+ leafReaderMaxDoc = leafReader.maxDoc();
+ leafReaderDocBase = leafReaderContext.docBase;
+ values = leafReader.getBinaryDocValues(Consts.FULL);
+
+ // this check is only needed once to confirm that the index uses BinaryDocValues
+ boolean success = values.advanceExact(ord - leafReaderDocBase);
+ if (success == false) {
+ throw new IOException(
+ "the taxonomy index is created using the older StoredFields format which uses a Lucene "
+ + "codec older than 8.7. Use the getPath(int ordinal) API iteratively instead.");
+ }
+ }
+ values.advanceExact(ord - leafReaderDocBase);
+ bulkPath[originalPosition.get(ord)] =
+ new FacetLabel(FacetsConfig.stringToPath(values.binaryValue().utf8ToString()));
+ synchronized (categoryCache) {
Review comment:
We could move this `synchrtonized` out to a separate pass in the end, so we don't sync per ordinal but rather sync once, and then add all ordinals we looked up?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/taxonomy/directory/DirectoryTaxonomyReader.java
##########
@@ -353,12 +349,104 @@ public FacetLabel getPath(int ordinal) throws IOException {
}
synchronized (categoryCache) {
- categoryCache.put(catIDInteger, ret);
+ categoryCache.put(ordinal, ret);
}
return ret;
}
+ private FacetLabel getPathFromCache(int ordinal) {
+ // TODO: can we use an int-based hash impl, such as IntToObjectMap,
+ // wrapped as LRU?
+ synchronized (categoryCache) {
+ return categoryCache.get(ordinal);
+ }
+ }
+
+ private void isOrdinalInIndexReaderRange(int ordinal, int indexReaderMaxDoc)
+ throws IllegalArgumentException {
+ if (ordinal < 0 || ordinal >= indexReaderMaxDoc) {
+ throw new IllegalArgumentException(
+ "ordinal "
+ + ordinal
+ + " is out of the range of the indexReader "
+ + indexReader.toString());
+ }
+ }
+
+ /**
+ * Returns an array of FacetLabels for a given array of ordinals.
+ *
+ * <p>This API is generally faster than iteratively calling {@link
+ * org.apache.lucene.facet.taxonomy.directory.DirectoryTaxonomyReader#getPath} over an array of
+ * ordinals.
+ *
+ * <p>This API is only available for Lucene indexes created with 8.7+ codec because it uses
+ * BinaryDocValues instead of StoredFields. Use the {@link
+ * org.apache.lucene.facet.taxonomy.directory.DirectoryTaxonomyReader#getPath} method for indices
+ * created with codec version older than 8.7.
+ *
+ * @param ordinals Array of ordinals that are assigned to categories inserted into the taxonomy
+ * index
+ * @throws IOException if the taxonomy index is created using the older StoredFields based codec.
+ */
+ public FacetLabel[] getBulkPath(int... ordinals) throws IOException {
+ ensureOpen();
+
+ FacetLabel[] bulkPath = new FacetLabel[ordinals.length];
+ // remember the original positions of ordinals before they are sorted
+ IntIntScatterMap originalPosition = new IntIntScatterMap();
+ int indexReaderMaxDoc = indexReader.maxDoc();
+ for (int i = 0; i < ordinals.length; i++) {
+ // check whether the ordinal is valid before accessing the cache
+ isOrdinalInIndexReaderRange(ordinals[i], indexReaderMaxDoc);
+ // check the cache before trying to find it in the index
+ FacetLabel ordinalPath = getPathFromCache(ordinals[i]);
+ if (ordinalPath != null) {
+ bulkPath[i] = ordinalPath;
+ }
+ originalPosition.put(ordinals[i], i);
Review comment:
Hmm, one reason for doing the parallel sort instead of the hash map is: what if the incoming ordinals have duplicates? It is silly to do, but user might do it out of laziness or something, and as the code now stands, that would not work right, I think? I.e. one of the returned `FacetLabel`s would be `null`?
Could you add a test case for that (admittedly, strange) usage?
And then I think switch to the parallel sort? [Here is an example](https://github.com/apache/lucene-solr/blob/master/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java#L423-L476) of how to do this using Lucene's `Sorter` utility APIs.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org