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/12/03 06:58:08 UTC
[GitHub] [lucene] mdmarshmallow opened a new pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
mdmarshmallow opened a new pull request #509:
URL: https://github.com/apache/lucene/pull/509
<!--
_(If you are a project committer then you may remove some/all of the following template.)_
Before creating a pull request, please file an issue in the ASF Jira system for Lucene:
* https://issues.apache.org/jira/projects/LUCENE
You will need to create an account in Jira in order to create an issue.
The title of the PR should reference the Jira issue number in the form:
* LUCENE-####: <short description of problem or changes>
LUCENE must be fully capitalized. A short description helps people scanning pull requests for items they can work on.
Properly referencing the issue in the title ensures that Jira is correctly updated with code review comments and commits. -->
# Description
Currently, SSDV faceting doesn't support hierarchical labels with a hierarchy of greater than 2. This change enables hierarchical labels of arbitrary length with SSDV faceting.
# Solution
In `SortedSetDocValuesReaderState`, I created a tree data structure called `HierarchicalOrdRange` that maintains all the labels added, storing the ordinal ranges of each label as well as references to child labels. This replaces the current `Map<String, OrdRange>` data structure that maps each dimension to its ordinal range. The `HierarchicalOrdRange` data structure is populated in `DefaultSortedSetDocValuesReaderState` and is then read in `SortedSetDocValuesFacetCounts` and `ConcurrentSortedSetDocValuesCounts` in order to get ranges of arbitrary length labels efficiently.
# Tests
* Created `TestHierarchicalOrdRange` to test `HierarchicalOrdRange` data structure
* Added length > 2 labels to tests in `TestSortedSetDocValuesFacets` test class
# Checklist
Please review the following and check all that apply:
- [X] I have reviewed the guidelines for [How to Contribute](https://wiki.apache.org/lucene/HowToContribute) and my code conforms to the standards described there to the best of my ability.
- [X] I have created a Jira issue and added the issue ID to my pull request title.
- [X] I have given Lucene maintainers [access](https://help.github.com/en/articles/allowing-changes-to-a-pull-request-branch-created-from-a-fork) to contribute to my PR branch. (optional but recommended)
- [X] I have developed this patch against the `main` branch.
- [X] I have run `./gradlew check`.
- [X] I have added tests for my changes.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] gsmiller commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
gsmiller commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r780563276
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,36 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
-
- // For facet counts:
- doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
-
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ DimConfig dimConfig = getDimConfig(facetField.dim);
+ if (dimConfig.hierarchical) {
+ for (int i = 0; i < facetLabel.length; i++) {
+ String fullPath = pathToString(facetLabel.components, i + 1);
+ // For facet counts:
+ doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
+ }
+ // For drill-down:
Review comment:
Looks like a straggler comment line leftover.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -317,10 +345,19 @@ public Number getSpecificValue(String dim, String... path) throws IOException {
public List<FacetResult> getAllDims(int topN) throws IOException {
List<FacetResult> results = new ArrayList<>();
- for (Map.Entry<String, OrdRange> ent : state.getPrefixToOrdRange().entrySet()) {
- FacetResult fr = getDim(ent.getKey(), ent.getValue(), topN);
- if (fr != null) {
- results.add(fr);
+ for (String dim : state.getDims()) {
+ if (stateConfig.getDimConfig(dim).hierarchical) {
+ DimTree dimTree = state.getDimTree(dim);
+ FacetResult fr = getDim(dim, emptyPath, dimTree.dimStartOrd, dimTree.iterator(), topN);
Review comment:
I can't respond to our previous comment thread because it seems to think the comment is outdated or something. But to pick up that thread, you'd said:
>If we pass -1 in the code would just use dimCount for the value, which could be inaccurate in the multi-valued case. Given that, I think it would be better to pass in dimStartOrd so we can guarantee that hierarchical SSDV facets have accurate multi-valued counts, given that we are already doing ancestral indexing. What do you think?
... and that makes total sense. I got my wired crossed a little on this. Separately (but related to my confusion), is `dimStartOrd` really just the `dimOrd`? Do you think it would be more readable to rename this? Or maybe I'm still confused about this?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetField.java
##########
@@ -40,20 +41,33 @@
/** Dimension. */
public final String dim;
- /** Label. */
- public final String label;
+ /** Path. */
+ public final String[] path;
+
+ /** String form of path. */
Review comment:
Could you add a `@deprecated` message to the javadoc as well please? Maybe something like:
```
/**
* String form of path.
*
* @deprecated This field will be removed in a future version. {@link
* FacetsConfig#pathToString(String[])} can be applied to {@code path} as a replacement if
* string path is desired.
*/
```
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,38 +105,139 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
-
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
- for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
+ int ord = 0;
+ while (ord != valueCount) {
+ BytesRef term = dv.lookupOrd(ord);
String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ String dim = components[0];
+ if (config != null && config.getDimConfig(dim).hierarchical) {
+ ord = createOneHierarchicalFacetDimState(dv, ord) + 1;
+ } else {
+ ord = createOneFlatFacetDimState(dv, ord) + 1;
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+ }
+ }
+
+ // returns last ord of dimension
+ private int createOneHierarchicalFacetDimState(SortedSetDocValues dv, int dimStartOrd)
+ throws IOException {
+ List<Boolean> hasChildren = new ArrayList<>();
+ List<Integer> siblings = new ArrayList<>();
+
+ // stack of paths with unfulfilled siblings
+ Stack<OrdAndComponent> siblingStack = new Stack<>();
+
+ int dimEndOrd = dimStartOrd;
+
+ BytesRef nextTerm = dv.lookupOrd(dimEndOrd);
+ String[] nextComponents = FacetsConfig.stringToPath(nextTerm.utf8ToString());
+ String dim = nextComponents[0];
+
+ while (true) {
+ String[] components = nextComponents;
+
+ int ord = dimEndOrd - dimStartOrd;
+
+ while (siblingStack.empty() == false
+ && siblingStack.peek().component.length >= components.length) {
+ OrdAndComponent possibleSibling = siblingStack.pop();
+ if (possibleSibling.component.length == components.length) {
+ // lengths are equal, all non-siblings of equal length will have already been popped off
+ // so this must be sibling
+ siblings.set(possibleSibling.ord, ord);
}
- startOrd = ord;
- lastDim = components[0];
}
+
+ if (dimEndOrd + 1 == valueCount) {
+ // current ord needs to be added, can't have children or siblings
+ siblings.add(-1);
+ hasChildren.add(false);
+ break;
+ }
+
+ nextTerm = dv.lookupOrd(dimEndOrd + 1);
+ nextComponents = FacetsConfig.stringToPath(nextTerm.utf8ToString());
+
+ if (nextComponents[0].equals(components[0]) == false) {
+ // current ord needs to be added, can't have children or siblings
+ siblings.add(-1);
+ hasChildren.add(false);
+ break;
+ }
+
+ if (components.length < nextComponents.length) {
+ // next ord must be a direct child of current ord, this is because we are indexing all
+ // ancestral paths
+ hasChildren.add(ord, true);
+ // we don't know if this ord has a sibling or where it's sibling could be yet
+ siblingStack.push(new OrdAndComponent(ord, components));
+ // we still add INVALID_ORDINAL, which will be replaced if a valid sibling is found
+ siblings.add(ord, INVALID_ORDINAL);
+ } else if (components.length == nextComponents.length) {
+ // next ord must be a sibling of current and there are no direct children or current, this
Review comment:
typo: "no direct children _of_ current" instead of "no direct children or current"
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -62,15 +166,28 @@ protected SortedSetDocValuesReaderState() {}
/** Indexed field we are reading. */
public abstract String getField();
+ /** Returns top-level index reader. */
+ public abstract IndexReader getReader();
+
+ /** Number of unique labels. */
+ public abstract int getSize();
+
+ /** Returns the associated facet config. */
+ public abstract FacetsConfig getFacetConfig();
Review comment:
minor: For naming consistency, maybe make "facet" plural (so `getFacetsConfig`). Sorry to be so nit-picky on this but since it's a public API, I'm being a little pedantic.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -51,20 +55,42 @@
private final Map<String, OrdinalMap> cachedOrdMaps = new HashMap<>();
+ private final FacetsConfig config;
+
+ /** Used for hierarchical dims. */
+ private final Map<String, DimTree> prefixToDimTree = new HashMap<>();
+
+ /** Used for flat dims. */
private final Map<String, OrdRange> prefixToOrdRange = new HashMap<>();
/**
- * Creates this, pulling doc values from the default {@link
+ * Creates this with a config, pulling doc values from the default {@link
+ * FacetsConfig#DEFAULT_INDEX_FIELD_NAME}.
+ */
+ public DefaultSortedSetDocValuesReaderState(IndexReader reader, FacetsConfig config)
+ throws IOException {
+ this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME, config);
+ }
+
+ /**
+ * Creates this without a config, pulling doc values from the default {@link
* FacetsConfig#DEFAULT_INDEX_FIELD_NAME}.
*/
public DefaultSortedSetDocValuesReaderState(IndexReader reader) throws IOException {
- this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME);
+ this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME, null);
}
- /** Creates this, pulling doc values from the specified field. */
+ /** Creates this without a config, pulling doc values from the specified field. */
public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) throws IOException {
+ this(reader, field, null);
+ }
+
+ /** Creates this, pulling doc values from the specified field. */
+ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field, FacetsConfig config)
+ throws IOException {
this.field = field;
this.reader = reader;
+ this.config = Objects.requireNonNullElse(config, new FacetsConfig());
Review comment:
Hmm, I don't think we want to default this here. It would be good to know that the user didn't provide a `FacetsConfig` instance later on instead of just assuming some default. Can we let this be `null` and be defensive against that case elsewhere?
Separately, we might want to deprecate the ability to instantiate this class without providing the config. Let's tackle that as a separate issue though.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] gsmiller commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
gsmiller commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r774242416
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,24 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+ Set<String> addedPaths = new HashSet<>();
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
-
- // For facet counts:
- doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
-
- // For drill-down:
- indexDrillDownTerms(doc, indexFieldName, getDimConfig(facetField.dim), facetLabel);
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ for (int i = 0; i < facetLabel.length; i++) {
Review comment:
Ooops, I actually meant to go back and remove this comment before publishing my review. So let me elaborate.
Seems like the only hard requirement for this indexing is to handle multi-valued counting properly, but I can also see that it makes building up the child/sibling state much simpler to know that every unique path will have a corresponding ordinal in the SSDV field. So I'm supportive of always doing this for now (could maybe optimize later).
It does seem that this will "regress" the non-hierarchical and single-valued cases though in that it will start indexing all the dims even though it's not strictly necessary. It would be nice to not do this indexing where it's not needed. At the same time, we don't actually know if current users expect multi- vs. single-valued since dim config isn't made available, so I could be convinced that we should just do this and assume everything could be multi-valued. But maybe there's a clean way to make this configurable like taxo facets? Let's think about it a bit more.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] mdmarshmallow commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
mdmarshmallow commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r779974107
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,35 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ if (getDimConfig(facetField.dim).hierarchical) {
+ for (int i = 0; i < facetLabel.length; i++) {
+ String fullPath = pathToString(facetLabel.components, i + 1);
+ // For facet counts:
+ doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
+
+ // For drill-down:
+ indexDrillDownTerms(doc, indexFieldName, getDimConfig(facetField.dim), facetLabel);
+ }
+ } else {
+ if (facetLabel.length != 2) {
+ throw new IllegalArgumentException(
Review comment:
Changed error message to match taxo-facets.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,35 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ if (getDimConfig(facetField.dim).hierarchical) {
+ for (int i = 0; i < facetLabel.length; i++) {
+ String fullPath = pathToString(facetLabel.components, i + 1);
+ // For facet counts:
+ doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
+
+ // For drill-down:
+ indexDrillDownTerms(doc, indexFieldName, getDimConfig(facetField.dim), facetLabel);
Review comment:
Yeah that is correct, that should not be in the loop.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -51,20 +54,42 @@
private final Map<String, OrdinalMap> cachedOrdMaps = new HashMap<>();
+ private final FacetsConfig config;
+
+ /*** Used for hierarchical dims ***/
Review comment:
Oh I think I was copying and pasting that from a comment that was trying to signify a section or something, but yeah I'll make those normal haha.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,38 +104,160 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
-
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
- for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
+ int ord = 0;
+ while (ord != valueCount) {
+ BytesRef term = dv.lookupOrd(ord);
String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ String dim = components[0];
+ if (config != null && config.getDimConfig(dim).hierarchical) {
+ ord = createOneHierarchicalFacetDimState(dv, ord) + 1;
+ } else {
+ ord = createOneFlatFacetDimState(dv, ord) + 1;
+ }
+ }
+ }
+
+ // returns last ord of dimension
+ private int createOneHierarchicalFacetDimState(SortedSetDocValues dv, int dimStartOrd)
+ throws IOException {
+ List<Boolean> hasChildren = new ArrayList<>();
+ List<Integer> siblings = new ArrayList<>();
+
+ String dim = null;
+
+ // stack of paths with unfulfilled siblings
+ Stack<OrdAndComponent> siblingStack = new Stack<>();
+
+ String[] nextComponents = null;
+ int dimEndOrd = dimStartOrd;
+ while (true) {
+ String[] components;
+
+ int ord = dimEndOrd - dimStartOrd;
+
+ if (nextComponents == null) {
Review comment:
Initialized this before loop.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -95,17 +96,34 @@ public FacetResult getTopChildren(int topN, String dim, String... path) throws I
if (topN <= 0) {
throw new IllegalArgumentException("topN must be > 0 (got: " + topN + ")");
}
- if (path.length > 0) {
- throw new IllegalArgumentException("path should be 0 length");
- }
- OrdRange ordRange = state.getOrdRange(dim);
- if (ordRange == null) {
- return null; // means dimension was never indexed
+
+ if (state.isHierarchicalDim(dim)) {
+ int pathOrd = (int) dv.lookupTerm(new BytesRef(FacetsConfig.pathToString(dim, path)));
+ if (pathOrd == -1) {
+ // path was never indexed
+ return null;
+ }
+ DimTree dimTree = state.getDimTree(dim);
+ if (dimTree == null) {
Review comment:
That is true, removed null check.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -62,15 +159,27 @@ protected SortedSetDocValuesReaderState() {}
/** Indexed field we are reading. */
public abstract String getField();
+ /** Returns top-level index reader. */
+ public abstract IndexReader getReader();
+
+ /** Number of unique labels. */
+ public abstract int getSize();
+
+ /** Returns if dim is configured as hierarchical ** */
+ public abstract boolean isHierarchicalDim(String dim);
+
+ /*** Only used for flat facets (dim/value) ***/
+
/** Returns the {@link OrdRange} for this dimension. */
public abstract OrdRange getOrdRange(String dim);
/** Returns mapping from prefix to {@link OrdRange}. */
public abstract Map<String, OrdRange> getPrefixToOrdRange();
- /** Returns top-level index reader. */
- public abstract IndexReader getReader();
+ /*** Only used for hierarchical facets ***/
- /** Number of unique labels. */
- public abstract int getSize();
+ public abstract DimTree getDimTree(String dim);
+
+ /** Returns a list of all dimensions and their respective ordinals */
Review comment:
Yes correct I left that there on accident from a previous revision.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -317,10 +343,19 @@ public Number getSpecificValue(String dim, String... path) throws IOException {
public List<FacetResult> getAllDims(int topN) throws IOException {
List<FacetResult> results = new ArrayList<>();
- for (Map.Entry<String, OrdRange> ent : state.getPrefixToOrdRange().entrySet()) {
- FacetResult fr = getDim(ent.getKey(), ent.getValue(), topN);
- if (fr != null) {
- results.add(fr);
+ for (String dim : state.getDims()) {
+ if (state.isHierarchicalDim(dim)) {
+ DimTree dimTree = state.getDimTree(dim);
+ FacetResult fr = getDim(dim, new String[0], dimTree.dimStartOrd, dimTree.iterator(), topN);
Review comment:
If we pass `-1` in the code would just use `dimCount` for the value, which could be inaccurate in the multi-valued case. Given that, I think it would be better to pass in `dimStartOrd` so we can guarantee that hierarchical SSDV facets have accurate multi-valued counts, given that we are already doing ancestral indexing. What do you think?
```
if (pathOrd == -1) {
// not hierarchical facet
return new FacetResult(dim, emptyPath, dimCount, labelValues, childCount);
} else {
// hierarchical facet
return new FacetResult(dim, path, counts[pathOrd], labelValues, childCount);
}
```
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -62,15 +159,27 @@ protected SortedSetDocValuesReaderState() {}
/** Indexed field we are reading. */
public abstract String getField();
+ /** Returns top-level index reader. */
+ public abstract IndexReader getReader();
+
+ /** Number of unique labels. */
+ public abstract int getSize();
+
+ /** Returns if dim is configured as hierarchical ** */
+ public abstract boolean isHierarchicalDim(String dim);
Review comment:
Yeah that makes sense.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -95,17 +96,34 @@ public FacetResult getTopChildren(int topN, String dim, String... path) throws I
if (topN <= 0) {
throw new IllegalArgumentException("topN must be > 0 (got: " + topN + ")");
}
- if (path.length > 0) {
- throw new IllegalArgumentException("path should be 0 length");
- }
- OrdRange ordRange = state.getOrdRange(dim);
- if (ordRange == null) {
- return null; // means dimension was never indexed
+
+ if (state.isHierarchicalDim(dim)) {
+ int pathOrd = (int) dv.lookupTerm(new BytesRef(FacetsConfig.pathToString(dim, path)));
+ if (pathOrd == -1) {
Review comment:
I added a unit test and it actually still did return `null` in `getDims` due to the dim tree iterator not iterating over anything. With that being said, I did change this check to just be a negative check (and added a unit test).
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,38 +104,160 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
-
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
- for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
+ int ord = 0;
+ while (ord != valueCount) {
+ BytesRef term = dv.lookupOrd(ord);
String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ String dim = components[0];
+ if (config != null && config.getDimConfig(dim).hierarchical) {
+ ord = createOneHierarchicalFacetDimState(dv, ord) + 1;
+ } else {
+ ord = createOneFlatFacetDimState(dv, ord) + 1;
+ }
+ }
+ }
+
+ // returns last ord of dimension
+ private int createOneHierarchicalFacetDimState(SortedSetDocValues dv, int dimStartOrd)
+ throws IOException {
+ List<Boolean> hasChildren = new ArrayList<>();
+ List<Integer> siblings = new ArrayList<>();
+
+ String dim = null;
+
+ // stack of paths with unfulfilled siblings
+ Stack<OrdAndComponent> siblingStack = new Stack<>();
+
+ String[] nextComponents = null;
+ int dimEndOrd = dimStartOrd;
+ while (true) {
+ String[] components;
+
+ int ord = dimEndOrd - dimStartOrd;
+
+ if (nextComponents == null) {
+ BytesRef term = dv.lookupOrd(dimEndOrd);
+ components = FacetsConfig.stringToPath(term.utf8ToString());
+ dim = components[0];
+ } else {
+ components = nextComponents;
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+
+ while (siblingStack.empty() == false
+ && siblingStack.peek().component.length >= components.length) {
+ OrdAndComponent possibleSibling = siblingStack.pop();
+ if (possibleSibling.component.length == components.length) {
+ // lengths are equal
+ boolean isSibling = true;
+ for (int i = 0; i < possibleSibling.component.length - 1; i++) {
+ if (possibleSibling.component[i].equals(components[i]) == false) {
+ isSibling = false;
+ break;
+ }
+ }
+ if (isSibling) {
+ siblings.set(possibleSibling.ord, ord);
+ }
}
- startOrd = ord;
- lastDim = components[0];
}
+
+ if (dimEndOrd + 1 == valueCount) {
+ // current ord needs to be added, can't have children or siblings
+ siblings.add(-1);
+ hasChildren.add(false);
+ break;
+ }
+
+ BytesRef nextTerm = dv.lookupOrd(dimEndOrd + 1);
+ nextComponents = FacetsConfig.stringToPath(nextTerm.utf8ToString());
+
+ if (nextComponents[0].equals(components[0]) == false) {
+ // current ord needs to be added, can't have children or siblings
+ siblings.add(-1);
+ hasChildren.add(false);
+ break;
+ }
+
+ if (components.length < nextComponents.length) {
+ // next ord must be a direct child of current ord, this is because we are indexing all
+ // ancestral paths
+ hasChildren.add(ord, true);
+ // we don't know if this ord has a sibling or where it's sibling could be yet
+ siblingStack.push(new OrdAndComponent(ord, components));
+ // we still add INVALID_ORDINAL, which will be replaced if a valid sibling is found
+ siblings.add(ord, INVALID_ORDINAL);
+ } else if (components.length == nextComponents.length) {
+ // next ord must be a sibling of current and there are no direct children or current, this
+ // is because we
+ // are indexing all ancestral paths
+ siblings.add(ord, ord + 1);
+ hasChildren.add(ord, false);
+ } else {
+ // components.length > nextComponents.length
+ // next ord is neither sibling nor child
+ siblings.add(ord, INVALID_ORDINAL);
+ hasChildren.add(ord, false);
+ }
+
+ dimEndOrd++;
}
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, valueCount - 1));
+ prefixToDimTree.put(dim, new DimTree(dimStartOrd, siblings, hasChildren));
+
+ return dimEndOrd;
+ }
+
+ // returns last ord of dimension
+ private int createOneFlatFacetDimState(SortedSetDocValues dv, int dimStartOrd)
+ throws IOException {
+
+ String dim = null;
+
+ String[] nextComponents = null;
+ int dimEndOrd = dimStartOrd;
+
+ while (true) {
+ String[] components;
+
+ if (nextComponents == null) {
Review comment:
Yeah, I moved the initialization of this out of the loop (as with the other case of this you mentioned).
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,38 +104,160 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
-
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
- for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
+ int ord = 0;
+ while (ord != valueCount) {
+ BytesRef term = dv.lookupOrd(ord);
String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ String dim = components[0];
+ if (config != null && config.getDimConfig(dim).hierarchical) {
+ ord = createOneHierarchicalFacetDimState(dv, ord) + 1;
+ } else {
+ ord = createOneFlatFacetDimState(dv, ord) + 1;
+ }
+ }
+ }
+
+ // returns last ord of dimension
+ private int createOneHierarchicalFacetDimState(SortedSetDocValues dv, int dimStartOrd)
+ throws IOException {
+ List<Boolean> hasChildren = new ArrayList<>();
+ List<Integer> siblings = new ArrayList<>();
+
+ String dim = null;
+
+ // stack of paths with unfulfilled siblings
+ Stack<OrdAndComponent> siblingStack = new Stack<>();
+
+ String[] nextComponents = null;
+ int dimEndOrd = dimStartOrd;
+ while (true) {
+ String[] components;
+
+ int ord = dimEndOrd - dimStartOrd;
+
+ if (nextComponents == null) {
+ BytesRef term = dv.lookupOrd(dimEndOrd);
+ components = FacetsConfig.stringToPath(term.utf8ToString());
+ dim = components[0];
+ } else {
+ components = nextComponents;
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+
+ while (siblingStack.empty() == false
+ && siblingStack.peek().component.length >= components.length) {
+ OrdAndComponent possibleSibling = siblingStack.pop();
+ if (possibleSibling.component.length == components.length) {
+ // lengths are equal
+ boolean isSibling = true;
+ for (int i = 0; i < possibleSibling.component.length - 1; i++) {
+ if (possibleSibling.component[i].equals(components[i]) == false) {
Review comment:
Yeah I thought about it for a bit and you're correct. Thanks! That should make the state construction at least a bit faster.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] gsmiller commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
gsmiller commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r780546237
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -51,20 +54,42 @@
private final Map<String, OrdinalMap> cachedOrdMaps = new HashMap<>();
+ private final FacetsConfig config;
+
+ /*** Used for hierarchical dims ***/
Review comment:
Oh I see. That's fine then. I assumed it was an IDE/spotless issue since I saw some other places that looked a little more funky.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] gsmiller commented on pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
gsmiller commented on pull request #509:
URL: https://github.com/apache/lucene/pull/509#issuecomment-1009000807
This looks good to me in its current state. I kicked off the precommit checks again. Assuming they pass successfully, I'll work on merging this today. Thanks!
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] mdmarshmallow commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
mdmarshmallow commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r776104278
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,24 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+ Set<String> addedPaths = new HashSet<>();
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
-
- // For facet counts:
- doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
-
- // For drill-down:
- indexDrillDownTerms(doc, indexFieldName, getDimConfig(facetField.dim), facetLabel);
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ for (int i = 0; i < facetLabel.length; i++) {
Review comment:
Yeah I turned everything configurable. If there is at least one dim that is configured as hierarchical, then everything will be stored and counted in the "new" way, if not then SSDV facets will be stored and counted the same way they are currently.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,37 +86,78 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
+ // keeps track of last path with length i where the path has an unfilled sibling
+ Map<Integer, OrdAndComponent> pathsWithUnfilledSiblings = new HashMap<>();
+
+ BytesRef nextTerm = null;
+ String[] nextComponents = null;
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
- String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ if (children == null) {
+ children = new FixedBitSet(valueCount);
+ siblings = new int[valueCount];
+ }
+
+ String[] components;
+
+ if (nextTerm == null) {
+ BytesRef term = dv.lookupOrd(ord);
+ components = FacetsConfig.stringToPath(term.utf8ToString());
+ } else {
+ components = nextComponents;
+ }
+
+ if (components.length == 1) {
+ // current ord is a dim
+ if (dims == null) {
+ dims = new ArrayList<>();
+ }
+ dims.add(new DimAndOrd(components[0], ord));
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+
+ if (pathsWithUnfilledSiblings.containsKey(components.length - 1)) {
Review comment:
I agree that stacks are probably better suited to this problem. I changed it to use stacks instead. I think the resulting code is actually a bit cleaner.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,37 +86,78 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
+ // keeps track of last path with length i where the path has an unfilled sibling
+ Map<Integer, OrdAndComponent> pathsWithUnfilledSiblings = new HashMap<>();
+
+ BytesRef nextTerm = null;
+ String[] nextComponents = null;
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
- String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ if (children == null) {
+ children = new FixedBitSet(valueCount);
+ siblings = new int[valueCount];
+ }
+
+ String[] components;
+
+ if (nextTerm == null) {
+ BytesRef term = dv.lookupOrd(ord);
+ components = FacetsConfig.stringToPath(term.utf8ToString());
+ } else {
+ components = nextComponents;
+ }
+
+ if (components.length == 1) {
+ // current ord is a dim
+ if (dims == null) {
+ dims = new ArrayList<>();
+ }
+ dims.add(new DimAndOrd(components[0], ord));
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+
+ if (pathsWithUnfilledSiblings.containsKey(components.length - 1)) {
+ OrdAndComponent possibleSibling = pathsWithUnfilledSiblings.get(components.length - 1);
+ boolean isSibling = true;
+ for (int i = 0; i < possibleSibling.component.length - 1; i++) {
+ if (!possibleSibling.component[i].equals(components[i])) {
+ isSibling = false;
+ break;
+ }
+ }
+ if (isSibling) {
+ siblings[possibleSibling.ord] = ord;
+ } else {
+ siblings[possibleSibling.ord] = INVALID_ORDINAL;
}
- startOrd = ord;
- lastDim = components[0];
+ pathsWithUnfilledSiblings.remove(components.length - 1);
+ }
+
+ if (ord + 1 == valueCount) {
+ // last value, cannot have children or links to more siblings
+ siblings[ord] = INVALID_ORDINAL;
+ break;
+ }
+
+ nextTerm = dv.lookupOrd(ord + 1);
+ nextComponents = FacetsConfig.stringToPath(nextTerm.utf8ToString());
+
+ if (components.length < nextComponents.length) {
+ // next ord must be a direct child of current ord
Review comment:
Mentioned it in this comment as well as the comment in the next `else if` statement, since that is also only true due to indexing all ancestral paths.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -46,13 +48,18 @@
private final String field;
private final int valueCount;
+ // denotes whether next ord is child or not
+ private FixedBitSet children;
Review comment:
Yes your interpretation is correct. I'll change the name to `hasChildren` and add a more descriptive comment.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -222,4 +258,59 @@ public IndexReader getReader() {
public int getSize() {
return valueCount;
}
+
+ @Override
+ public Iterable<Integer> childOrds(int pathOrd) {
+ return () ->
+ new Iterator<>() {
+
+ boolean atStart = true;
+ int currentOrd = pathOrd;
+
+ @Override
+ public boolean hasNext() {
+ if (atStart) {
+ if (currentOrd < 0 || currentOrd >= children.length()) {
+ return false;
+ }
+ return children.get(currentOrd);
+ } else {
+ return siblings[currentOrd] != INVALID_ORDINAL;
+ }
+ }
+
+ @Override
+ public Integer next() {
+ if (atStart) {
+ if (currentOrd < 0 || currentOrd >= children.length()) {
+ return INVALID_ORDINAL;
+ }
+ atStart = false;
+ if (children.get(currentOrd)) {
+ return ++currentOrd;
Review comment:
Changed it.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,37 +86,78 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
+ // keeps track of last path with length i where the path has an unfilled sibling
+ Map<Integer, OrdAndComponent> pathsWithUnfilledSiblings = new HashMap<>();
+
+ BytesRef nextTerm = null;
+ String[] nextComponents = null;
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
- String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ if (children == null) {
+ children = new FixedBitSet(valueCount);
+ siblings = new int[valueCount];
+ }
+
+ String[] components;
+
+ if (nextTerm == null) {
+ BytesRef term = dv.lookupOrd(ord);
+ components = FacetsConfig.stringToPath(term.utf8ToString());
+ } else {
+ components = nextComponents;
+ }
+
+ if (components.length == 1) {
+ // current ord is a dim
+ if (dims == null) {
+ dims = new ArrayList<>();
+ }
+ dims.add(new DimAndOrd(components[0], ord));
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+
+ if (pathsWithUnfilledSiblings.containsKey(components.length - 1)) {
+ OrdAndComponent possibleSibling = pathsWithUnfilledSiblings.get(components.length - 1);
+ boolean isSibling = true;
+ for (int i = 0; i < possibleSibling.component.length - 1; i++) {
+ if (!possibleSibling.component[i].equals(components[i])) {
Review comment:
Replaced all `!` with `== false`.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -222,4 +258,59 @@ public IndexReader getReader() {
public int getSize() {
return valueCount;
}
+
+ @Override
+ public Iterable<Integer> childOrds(int pathOrd) {
Review comment:
Changed this to a primitive iterator instead. Didn't know that was a thing :)
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,37 +86,78 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
+ // keeps track of last path with length i where the path has an unfilled sibling
+ Map<Integer, OrdAndComponent> pathsWithUnfilledSiblings = new HashMap<>();
+
+ BytesRef nextTerm = null;
+ String[] nextComponents = null;
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
- String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ if (children == null) {
+ children = new FixedBitSet(valueCount);
+ siblings = new int[valueCount];
+ }
+
+ String[] components;
+
+ if (nextTerm == null) {
+ BytesRef term = dv.lookupOrd(ord);
+ components = FacetsConfig.stringToPath(term.utf8ToString());
+ } else {
+ components = nextComponents;
+ }
+
+ if (components.length == 1) {
+ // current ord is a dim
+ if (dims == null) {
+ dims = new ArrayList<>();
+ }
+ dims.add(new DimAndOrd(components[0], ord));
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+
+ if (pathsWithUnfilledSiblings.containsKey(components.length - 1)) {
+ OrdAndComponent possibleSibling = pathsWithUnfilledSiblings.get(components.length - 1);
+ boolean isSibling = true;
+ for (int i = 0; i < possibleSibling.component.length - 1; i++) {
+ if (!possibleSibling.component[i].equals(components[i])) {
+ isSibling = false;
+ break;
+ }
+ }
+ if (isSibling) {
+ siblings[possibleSibling.ord] = ord;
+ } else {
+ siblings[possibleSibling.ord] = INVALID_ORDINAL;
}
- startOrd = ord;
- lastDim = components[0];
+ pathsWithUnfilledSiblings.remove(components.length - 1);
+ }
+
+ if (ord + 1 == valueCount) {
+ // last value, cannot have children or links to more siblings
+ siblings[ord] = INVALID_ORDINAL;
+ break;
+ }
+
+ nextTerm = dv.lookupOrd(ord + 1);
+ nextComponents = FacetsConfig.stringToPath(nextTerm.utf8ToString());
+
+ if (components.length < nextComponents.length) {
+ // next ord must be a direct child of current ord
+ children.set(ord);
Review comment:
Thanks :)
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -46,13 +48,18 @@
private final String field;
private final int valueCount;
+ // denotes whether next ord is child or not
+ private FixedBitSet children;
Review comment:
Removed lazy inits and changed to `final`
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -36,23 +35,21 @@
*/
public abstract class SortedSetDocValuesReaderState implements Accountable {
- /**
- * Holds start/end range of ords, which maps to one dimension (someday we may generalize it to map
- * to hierarchies within one dimension).
- */
- public static final class OrdRange {
- /** Start of range, inclusive: */
- public final int start;
- /** End of range, inclusive: */
- public final int end;
+ /** Holder class for a dimension along with it's corresponding ordinal */
+ public static class DimAndOrd {
+ String dim;
+ int ord;
- /** Start and end are inclusive. */
- public OrdRange(int start, int end) {
- this.start = start;
- this.end = end;
+ /** sole constructor */
+ public DimAndOrd(String dim, int ord) {
+ this.dim = dim;
+ this.ord = ord;
}
}
+ /** Invalid ordinal const */
+ public static int INVALID_ORDINAL = -1;
Review comment:
`SortedSetDocValues#NO_MORE_ORDS` is a `long` so I think it's easier to just define a new constant.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -317,26 +317,23 @@ public Number getSpecificValue(String dim, String... path) throws IOException {
public List<FacetResult> getAllDims(int topN) throws IOException {
List<FacetResult> results = new ArrayList<>();
- for (Map.Entry<String, OrdRange> ent : state.getPrefixToOrdRange().entrySet()) {
- FacetResult fr = getDim(ent.getKey(), ent.getValue(), topN);
+ for (DimAndOrd dim : state.getDims()) {
+ Iterable<Integer> childOrds = state.childOrds(dim.ord);
+ FacetResult fr = getDim(dim.dim, new String[0], dim.ord, childOrds, topN);
if (fr != null) {
results.add(fr);
}
}
// Sort by highest count:
- Collections.sort(
- results,
- new Comparator<FacetResult>() {
- @Override
- public int compare(FacetResult a, FacetResult b) {
- if (a.value.intValue() > b.value.intValue()) {
- return -1;
- } else if (b.value.intValue() > a.value.intValue()) {
- return 1;
- } else {
- return a.dim.compareTo(b.dim);
- }
+ results.sort(
+ (a, b) -> {
Review comment:
Hmm ok, I changed the lambdas back to anonymous classes for now.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,24 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+ Set<String> addedPaths = new HashSet<>();
Review comment:
Wasn't sure if this was already done, will remove this.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -46,13 +48,18 @@
private final String field;
private final int valueCount;
+ // denotes whether next ord is child or not
+ private FixedBitSet children;
+ // maps an ord to its first sibling
+ private int[] siblings;
Review comment:
I added a TODO, but changed it so this array will only be initialized if the field is configured to be hierarchical.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] mdmarshmallow commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
mdmarshmallow commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r774240119
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,24 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+ Set<String> addedPaths = new HashSet<>();
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
-
- // For facet counts:
- doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
-
- // For drill-down:
- indexDrillDownTerms(doc, indexFieldName, getDimConfig(facetField.dim), facetLabel);
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ for (int i = 0; i < facetLabel.length; i++) {
Review comment:
Yes, though I do also use the ancestor path indexes for establishing parent/child and sibling relationships in `DefaultSortedSetDocValuesReaderState` (and made some optimizations around the fact that ancestor paths were indexed), but I want to say that it can still be done without the ancestor path indexing, I would just need to change how it is done.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] mdmarshmallow commented on pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
mdmarshmallow commented on pull request #509:
URL: https://github.com/apache/lucene/pull/509#issuecomment-992806271
Yeah we would double count ancestors if they are in the same document. I'll need to look more into what exactly "rolling up" is and more on how taxonomy-based faceting works.
Also as a side note, I tested this change with high cardinality facets (~50M) and the tree structure took too much heap-space, so I'm wondering if it might be better to then just do what taxonomy does and store every ancestor ordinal and then roll up, though I'll need to test high cardinality faceting with taxonomy just to make sure this issue only occurs in these SSDV facets.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] gsmiller commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
gsmiller commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r780546237
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -51,20 +54,42 @@
private final Map<String, OrdinalMap> cachedOrdMaps = new HashMap<>();
+ private final FacetsConfig config;
+
+ /*** Used for hierarchical dims ***/
Review comment:
Oh I see. That's fine then. I assumed it was an IDE/spotless issue since I saw some other places that looked a little more funky.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,36 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
-
- // For facet counts:
- doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
-
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ DimConfig dimConfig = getDimConfig(facetField.dim);
+ if (dimConfig.hierarchical) {
+ for (int i = 0; i < facetLabel.length; i++) {
+ String fullPath = pathToString(facetLabel.components, i + 1);
+ // For facet counts:
+ doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
+ }
+ // For drill-down:
Review comment:
Looks like a straggler comment line leftover.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -317,10 +345,19 @@ public Number getSpecificValue(String dim, String... path) throws IOException {
public List<FacetResult> getAllDims(int topN) throws IOException {
List<FacetResult> results = new ArrayList<>();
- for (Map.Entry<String, OrdRange> ent : state.getPrefixToOrdRange().entrySet()) {
- FacetResult fr = getDim(ent.getKey(), ent.getValue(), topN);
- if (fr != null) {
- results.add(fr);
+ for (String dim : state.getDims()) {
+ if (stateConfig.getDimConfig(dim).hierarchical) {
+ DimTree dimTree = state.getDimTree(dim);
+ FacetResult fr = getDim(dim, emptyPath, dimTree.dimStartOrd, dimTree.iterator(), topN);
Review comment:
I can't respond to our previous comment thread because it seems to think the comment is outdated or something. But to pick up that thread, you'd said:
>If we pass -1 in the code would just use dimCount for the value, which could be inaccurate in the multi-valued case. Given that, I think it would be better to pass in dimStartOrd so we can guarantee that hierarchical SSDV facets have accurate multi-valued counts, given that we are already doing ancestral indexing. What do you think?
... and that makes total sense. I got my wired crossed a little on this. Separately (but related to my confusion), is `dimStartOrd` really just the `dimOrd`? Do you think it would be more readable to rename this? Or maybe I'm still confused about this?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetField.java
##########
@@ -40,20 +41,33 @@
/** Dimension. */
public final String dim;
- /** Label. */
- public final String label;
+ /** Path. */
+ public final String[] path;
+
+ /** String form of path. */
Review comment:
Could you add a `@deprecated` message to the javadoc as well please? Maybe something like:
```
/**
* String form of path.
*
* @deprecated This field will be removed in a future version. {@link
* FacetsConfig#pathToString(String[])} can be applied to {@code path} as a replacement if
* string path is desired.
*/
```
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,38 +105,139 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
-
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
- for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
+ int ord = 0;
+ while (ord != valueCount) {
+ BytesRef term = dv.lookupOrd(ord);
String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ String dim = components[0];
+ if (config != null && config.getDimConfig(dim).hierarchical) {
+ ord = createOneHierarchicalFacetDimState(dv, ord) + 1;
+ } else {
+ ord = createOneFlatFacetDimState(dv, ord) + 1;
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+ }
+ }
+
+ // returns last ord of dimension
+ private int createOneHierarchicalFacetDimState(SortedSetDocValues dv, int dimStartOrd)
+ throws IOException {
+ List<Boolean> hasChildren = new ArrayList<>();
+ List<Integer> siblings = new ArrayList<>();
+
+ // stack of paths with unfulfilled siblings
+ Stack<OrdAndComponent> siblingStack = new Stack<>();
+
+ int dimEndOrd = dimStartOrd;
+
+ BytesRef nextTerm = dv.lookupOrd(dimEndOrd);
+ String[] nextComponents = FacetsConfig.stringToPath(nextTerm.utf8ToString());
+ String dim = nextComponents[0];
+
+ while (true) {
+ String[] components = nextComponents;
+
+ int ord = dimEndOrd - dimStartOrd;
+
+ while (siblingStack.empty() == false
+ && siblingStack.peek().component.length >= components.length) {
+ OrdAndComponent possibleSibling = siblingStack.pop();
+ if (possibleSibling.component.length == components.length) {
+ // lengths are equal, all non-siblings of equal length will have already been popped off
+ // so this must be sibling
+ siblings.set(possibleSibling.ord, ord);
}
- startOrd = ord;
- lastDim = components[0];
}
+
+ if (dimEndOrd + 1 == valueCount) {
+ // current ord needs to be added, can't have children or siblings
+ siblings.add(-1);
+ hasChildren.add(false);
+ break;
+ }
+
+ nextTerm = dv.lookupOrd(dimEndOrd + 1);
+ nextComponents = FacetsConfig.stringToPath(nextTerm.utf8ToString());
+
+ if (nextComponents[0].equals(components[0]) == false) {
+ // current ord needs to be added, can't have children or siblings
+ siblings.add(-1);
+ hasChildren.add(false);
+ break;
+ }
+
+ if (components.length < nextComponents.length) {
+ // next ord must be a direct child of current ord, this is because we are indexing all
+ // ancestral paths
+ hasChildren.add(ord, true);
+ // we don't know if this ord has a sibling or where it's sibling could be yet
+ siblingStack.push(new OrdAndComponent(ord, components));
+ // we still add INVALID_ORDINAL, which will be replaced if a valid sibling is found
+ siblings.add(ord, INVALID_ORDINAL);
+ } else if (components.length == nextComponents.length) {
+ // next ord must be a sibling of current and there are no direct children or current, this
Review comment:
typo: "no direct children _of_ current" instead of "no direct children or current"
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -62,15 +166,28 @@ protected SortedSetDocValuesReaderState() {}
/** Indexed field we are reading. */
public abstract String getField();
+ /** Returns top-level index reader. */
+ public abstract IndexReader getReader();
+
+ /** Number of unique labels. */
+ public abstract int getSize();
+
+ /** Returns the associated facet config. */
+ public abstract FacetsConfig getFacetConfig();
Review comment:
minor: For naming consistency, maybe make "facet" plural (so `getFacetsConfig`). Sorry to be so nit-picky on this but since it's a public API, I'm being a little pedantic.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -51,20 +55,42 @@
private final Map<String, OrdinalMap> cachedOrdMaps = new HashMap<>();
+ private final FacetsConfig config;
+
+ /** Used for hierarchical dims. */
+ private final Map<String, DimTree> prefixToDimTree = new HashMap<>();
+
+ /** Used for flat dims. */
private final Map<String, OrdRange> prefixToOrdRange = new HashMap<>();
/**
- * Creates this, pulling doc values from the default {@link
+ * Creates this with a config, pulling doc values from the default {@link
+ * FacetsConfig#DEFAULT_INDEX_FIELD_NAME}.
+ */
+ public DefaultSortedSetDocValuesReaderState(IndexReader reader, FacetsConfig config)
+ throws IOException {
+ this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME, config);
+ }
+
+ /**
+ * Creates this without a config, pulling doc values from the default {@link
* FacetsConfig#DEFAULT_INDEX_FIELD_NAME}.
*/
public DefaultSortedSetDocValuesReaderState(IndexReader reader) throws IOException {
- this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME);
+ this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME, null);
}
- /** Creates this, pulling doc values from the specified field. */
+ /** Creates this without a config, pulling doc values from the specified field. */
public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) throws IOException {
+ this(reader, field, null);
+ }
+
+ /** Creates this, pulling doc values from the specified field. */
+ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field, FacetsConfig config)
+ throws IOException {
this.field = field;
this.reader = reader;
+ this.config = Objects.requireNonNullElse(config, new FacetsConfig());
Review comment:
Hmm, I don't think we want to default this here. It would be good to know that the user didn't provide a `FacetsConfig` instance later on instead of just assuming some default. Can we let this be `null` and be defensive against that case elsewhere?
Separately, we might want to deprecate the ability to instantiate this class without providing the config. Let's tackle that as a separate issue though.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] mdmarshmallow commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
mdmarshmallow commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r779974107
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,35 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ if (getDimConfig(facetField.dim).hierarchical) {
+ for (int i = 0; i < facetLabel.length; i++) {
+ String fullPath = pathToString(facetLabel.components, i + 1);
+ // For facet counts:
+ doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
+
+ // For drill-down:
+ indexDrillDownTerms(doc, indexFieldName, getDimConfig(facetField.dim), facetLabel);
+ }
+ } else {
+ if (facetLabel.length != 2) {
+ throw new IllegalArgumentException(
Review comment:
Changed error message to match taxo-facets.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,35 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ if (getDimConfig(facetField.dim).hierarchical) {
+ for (int i = 0; i < facetLabel.length; i++) {
+ String fullPath = pathToString(facetLabel.components, i + 1);
+ // For facet counts:
+ doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
+
+ // For drill-down:
+ indexDrillDownTerms(doc, indexFieldName, getDimConfig(facetField.dim), facetLabel);
Review comment:
Yeah that is correct, that should not be in the loop.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -51,20 +54,42 @@
private final Map<String, OrdinalMap> cachedOrdMaps = new HashMap<>();
+ private final FacetsConfig config;
+
+ /*** Used for hierarchical dims ***/
Review comment:
Oh I think I was copying and pasting that from a comment that was trying to signify a section or something, but yeah I'll make those normal haha.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,38 +104,160 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
-
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
- for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
+ int ord = 0;
+ while (ord != valueCount) {
+ BytesRef term = dv.lookupOrd(ord);
String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ String dim = components[0];
+ if (config != null && config.getDimConfig(dim).hierarchical) {
+ ord = createOneHierarchicalFacetDimState(dv, ord) + 1;
+ } else {
+ ord = createOneFlatFacetDimState(dv, ord) + 1;
+ }
+ }
+ }
+
+ // returns last ord of dimension
+ private int createOneHierarchicalFacetDimState(SortedSetDocValues dv, int dimStartOrd)
+ throws IOException {
+ List<Boolean> hasChildren = new ArrayList<>();
+ List<Integer> siblings = new ArrayList<>();
+
+ String dim = null;
+
+ // stack of paths with unfulfilled siblings
+ Stack<OrdAndComponent> siblingStack = new Stack<>();
+
+ String[] nextComponents = null;
+ int dimEndOrd = dimStartOrd;
+ while (true) {
+ String[] components;
+
+ int ord = dimEndOrd - dimStartOrd;
+
+ if (nextComponents == null) {
Review comment:
Initialized this before loop.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -95,17 +96,34 @@ public FacetResult getTopChildren(int topN, String dim, String... path) throws I
if (topN <= 0) {
throw new IllegalArgumentException("topN must be > 0 (got: " + topN + ")");
}
- if (path.length > 0) {
- throw new IllegalArgumentException("path should be 0 length");
- }
- OrdRange ordRange = state.getOrdRange(dim);
- if (ordRange == null) {
- return null; // means dimension was never indexed
+
+ if (state.isHierarchicalDim(dim)) {
+ int pathOrd = (int) dv.lookupTerm(new BytesRef(FacetsConfig.pathToString(dim, path)));
+ if (pathOrd == -1) {
+ // path was never indexed
+ return null;
+ }
+ DimTree dimTree = state.getDimTree(dim);
+ if (dimTree == null) {
Review comment:
That is true, removed null check.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -62,15 +159,27 @@ protected SortedSetDocValuesReaderState() {}
/** Indexed field we are reading. */
public abstract String getField();
+ /** Returns top-level index reader. */
+ public abstract IndexReader getReader();
+
+ /** Number of unique labels. */
+ public abstract int getSize();
+
+ /** Returns if dim is configured as hierarchical ** */
+ public abstract boolean isHierarchicalDim(String dim);
+
+ /*** Only used for flat facets (dim/value) ***/
+
/** Returns the {@link OrdRange} for this dimension. */
public abstract OrdRange getOrdRange(String dim);
/** Returns mapping from prefix to {@link OrdRange}. */
public abstract Map<String, OrdRange> getPrefixToOrdRange();
- /** Returns top-level index reader. */
- public abstract IndexReader getReader();
+ /*** Only used for hierarchical facets ***/
- /** Number of unique labels. */
- public abstract int getSize();
+ public abstract DimTree getDimTree(String dim);
+
+ /** Returns a list of all dimensions and their respective ordinals */
Review comment:
Yes correct I left that there on accident from a previous revision.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -317,10 +343,19 @@ public Number getSpecificValue(String dim, String... path) throws IOException {
public List<FacetResult> getAllDims(int topN) throws IOException {
List<FacetResult> results = new ArrayList<>();
- for (Map.Entry<String, OrdRange> ent : state.getPrefixToOrdRange().entrySet()) {
- FacetResult fr = getDim(ent.getKey(), ent.getValue(), topN);
- if (fr != null) {
- results.add(fr);
+ for (String dim : state.getDims()) {
+ if (state.isHierarchicalDim(dim)) {
+ DimTree dimTree = state.getDimTree(dim);
+ FacetResult fr = getDim(dim, new String[0], dimTree.dimStartOrd, dimTree.iterator(), topN);
Review comment:
If we pass `-1` in the code would just use `dimCount` for the value, which could be inaccurate in the multi-valued case. Given that, I think it would be better to pass in `dimStartOrd` so we can guarantee that hierarchical SSDV facets have accurate multi-valued counts, given that we are already doing ancestral indexing. What do you think?
```
if (pathOrd == -1) {
// not hierarchical facet
return new FacetResult(dim, emptyPath, dimCount, labelValues, childCount);
} else {
// hierarchical facet
return new FacetResult(dim, path, counts[pathOrd], labelValues, childCount);
}
```
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -62,15 +159,27 @@ protected SortedSetDocValuesReaderState() {}
/** Indexed field we are reading. */
public abstract String getField();
+ /** Returns top-level index reader. */
+ public abstract IndexReader getReader();
+
+ /** Number of unique labels. */
+ public abstract int getSize();
+
+ /** Returns if dim is configured as hierarchical ** */
+ public abstract boolean isHierarchicalDim(String dim);
Review comment:
Yeah that makes sense.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -95,17 +96,34 @@ public FacetResult getTopChildren(int topN, String dim, String... path) throws I
if (topN <= 0) {
throw new IllegalArgumentException("topN must be > 0 (got: " + topN + ")");
}
- if (path.length > 0) {
- throw new IllegalArgumentException("path should be 0 length");
- }
- OrdRange ordRange = state.getOrdRange(dim);
- if (ordRange == null) {
- return null; // means dimension was never indexed
+
+ if (state.isHierarchicalDim(dim)) {
+ int pathOrd = (int) dv.lookupTerm(new BytesRef(FacetsConfig.pathToString(dim, path)));
+ if (pathOrd == -1) {
Review comment:
I added a unit test and it actually still did return `null` in `getDims` due to the dim tree iterator not iterating over anything. With that being said, I did change this check to just be a negative check (and added a unit test).
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,38 +104,160 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
-
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
- for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
+ int ord = 0;
+ while (ord != valueCount) {
+ BytesRef term = dv.lookupOrd(ord);
String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ String dim = components[0];
+ if (config != null && config.getDimConfig(dim).hierarchical) {
+ ord = createOneHierarchicalFacetDimState(dv, ord) + 1;
+ } else {
+ ord = createOneFlatFacetDimState(dv, ord) + 1;
+ }
+ }
+ }
+
+ // returns last ord of dimension
+ private int createOneHierarchicalFacetDimState(SortedSetDocValues dv, int dimStartOrd)
+ throws IOException {
+ List<Boolean> hasChildren = new ArrayList<>();
+ List<Integer> siblings = new ArrayList<>();
+
+ String dim = null;
+
+ // stack of paths with unfulfilled siblings
+ Stack<OrdAndComponent> siblingStack = new Stack<>();
+
+ String[] nextComponents = null;
+ int dimEndOrd = dimStartOrd;
+ while (true) {
+ String[] components;
+
+ int ord = dimEndOrd - dimStartOrd;
+
+ if (nextComponents == null) {
+ BytesRef term = dv.lookupOrd(dimEndOrd);
+ components = FacetsConfig.stringToPath(term.utf8ToString());
+ dim = components[0];
+ } else {
+ components = nextComponents;
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+
+ while (siblingStack.empty() == false
+ && siblingStack.peek().component.length >= components.length) {
+ OrdAndComponent possibleSibling = siblingStack.pop();
+ if (possibleSibling.component.length == components.length) {
+ // lengths are equal
+ boolean isSibling = true;
+ for (int i = 0; i < possibleSibling.component.length - 1; i++) {
+ if (possibleSibling.component[i].equals(components[i]) == false) {
+ isSibling = false;
+ break;
+ }
+ }
+ if (isSibling) {
+ siblings.set(possibleSibling.ord, ord);
+ }
}
- startOrd = ord;
- lastDim = components[0];
}
+
+ if (dimEndOrd + 1 == valueCount) {
+ // current ord needs to be added, can't have children or siblings
+ siblings.add(-1);
+ hasChildren.add(false);
+ break;
+ }
+
+ BytesRef nextTerm = dv.lookupOrd(dimEndOrd + 1);
+ nextComponents = FacetsConfig.stringToPath(nextTerm.utf8ToString());
+
+ if (nextComponents[0].equals(components[0]) == false) {
+ // current ord needs to be added, can't have children or siblings
+ siblings.add(-1);
+ hasChildren.add(false);
+ break;
+ }
+
+ if (components.length < nextComponents.length) {
+ // next ord must be a direct child of current ord, this is because we are indexing all
+ // ancestral paths
+ hasChildren.add(ord, true);
+ // we don't know if this ord has a sibling or where it's sibling could be yet
+ siblingStack.push(new OrdAndComponent(ord, components));
+ // we still add INVALID_ORDINAL, which will be replaced if a valid sibling is found
+ siblings.add(ord, INVALID_ORDINAL);
+ } else if (components.length == nextComponents.length) {
+ // next ord must be a sibling of current and there are no direct children or current, this
+ // is because we
+ // are indexing all ancestral paths
+ siblings.add(ord, ord + 1);
+ hasChildren.add(ord, false);
+ } else {
+ // components.length > nextComponents.length
+ // next ord is neither sibling nor child
+ siblings.add(ord, INVALID_ORDINAL);
+ hasChildren.add(ord, false);
+ }
+
+ dimEndOrd++;
}
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, valueCount - 1));
+ prefixToDimTree.put(dim, new DimTree(dimStartOrd, siblings, hasChildren));
+
+ return dimEndOrd;
+ }
+
+ // returns last ord of dimension
+ private int createOneFlatFacetDimState(SortedSetDocValues dv, int dimStartOrd)
+ throws IOException {
+
+ String dim = null;
+
+ String[] nextComponents = null;
+ int dimEndOrd = dimStartOrd;
+
+ while (true) {
+ String[] components;
+
+ if (nextComponents == null) {
Review comment:
Yeah, I moved the initialization of this out of the loop (as with the other case of this you mentioned).
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,38 +104,160 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
-
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
- for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
+ int ord = 0;
+ while (ord != valueCount) {
+ BytesRef term = dv.lookupOrd(ord);
String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ String dim = components[0];
+ if (config != null && config.getDimConfig(dim).hierarchical) {
+ ord = createOneHierarchicalFacetDimState(dv, ord) + 1;
+ } else {
+ ord = createOneFlatFacetDimState(dv, ord) + 1;
+ }
+ }
+ }
+
+ // returns last ord of dimension
+ private int createOneHierarchicalFacetDimState(SortedSetDocValues dv, int dimStartOrd)
+ throws IOException {
+ List<Boolean> hasChildren = new ArrayList<>();
+ List<Integer> siblings = new ArrayList<>();
+
+ String dim = null;
+
+ // stack of paths with unfulfilled siblings
+ Stack<OrdAndComponent> siblingStack = new Stack<>();
+
+ String[] nextComponents = null;
+ int dimEndOrd = dimStartOrd;
+ while (true) {
+ String[] components;
+
+ int ord = dimEndOrd - dimStartOrd;
+
+ if (nextComponents == null) {
+ BytesRef term = dv.lookupOrd(dimEndOrd);
+ components = FacetsConfig.stringToPath(term.utf8ToString());
+ dim = components[0];
+ } else {
+ components = nextComponents;
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+
+ while (siblingStack.empty() == false
+ && siblingStack.peek().component.length >= components.length) {
+ OrdAndComponent possibleSibling = siblingStack.pop();
+ if (possibleSibling.component.length == components.length) {
+ // lengths are equal
+ boolean isSibling = true;
+ for (int i = 0; i < possibleSibling.component.length - 1; i++) {
+ if (possibleSibling.component[i].equals(components[i]) == false) {
Review comment:
Yeah I thought about it for a bit and you're correct. Thanks! That should make the state construction at least a bit faster.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetField.java
##########
@@ -40,20 +41,33 @@
/** Dimension. */
public final String dim;
- /** Label. */
- public final String label;
+ /** Path. */
+ public final String[] path;
+
+ /** String form of path. */
Review comment:
I'll just use this comment.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,36 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
-
- // For facet counts:
- doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
-
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ DimConfig dimConfig = getDimConfig(facetField.dim);
+ if (dimConfig.hierarchical) {
+ for (int i = 0; i < facetLabel.length; i++) {
+ String fullPath = pathToString(facetLabel.components, i + 1);
+ // For facet counts:
+ doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
+ }
+ // For drill-down:
Review comment:
Removed
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -317,10 +345,19 @@ public Number getSpecificValue(String dim, String... path) throws IOException {
public List<FacetResult> getAllDims(int topN) throws IOException {
List<FacetResult> results = new ArrayList<>();
- for (Map.Entry<String, OrdRange> ent : state.getPrefixToOrdRange().entrySet()) {
- FacetResult fr = getDim(ent.getKey(), ent.getValue(), topN);
- if (fr != null) {
- results.add(fr);
+ for (String dim : state.getDims()) {
+ if (stateConfig.getDimConfig(dim).hierarchical) {
+ DimTree dimTree = state.getDimTree(dim);
+ FacetResult fr = getDim(dim, emptyPath, dimTree.dimStartOrd, dimTree.iterator(), topN);
Review comment:
Hmm my reasoning with `dimStartOrd` was that it is the first ("start") ord in the dimension represented by the `DimTree`. Though I can also see your reasoning for calling it `dimOrd` in that it is ord of the dimension. Maybe just `firstOrd` or `startOrd` might be more appropriate?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -62,15 +166,28 @@ protected SortedSetDocValuesReaderState() {}
/** Indexed field we are reading. */
public abstract String getField();
+ /** Returns top-level index reader. */
+ public abstract IndexReader getReader();
+
+ /** Number of unique labels. */
+ public abstract int getSize();
+
+ /** Returns the associated facet config. */
+ public abstract FacetsConfig getFacetConfig();
Review comment:
No worries. In fact, thanks for reviewing this so thoroughly :)
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -51,20 +55,42 @@
private final Map<String, OrdinalMap> cachedOrdMaps = new HashMap<>();
+ private final FacetsConfig config;
+
+ /** Used for hierarchical dims. */
+ private final Map<String, DimTree> prefixToDimTree = new HashMap<>();
+
+ /** Used for flat dims. */
private final Map<String, OrdRange> prefixToOrdRange = new HashMap<>();
/**
- * Creates this, pulling doc values from the default {@link
+ * Creates this with a config, pulling doc values from the default {@link
+ * FacetsConfig#DEFAULT_INDEX_FIELD_NAME}.
+ */
+ public DefaultSortedSetDocValuesReaderState(IndexReader reader, FacetsConfig config)
+ throws IOException {
+ this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME, config);
+ }
+
+ /**
+ * Creates this without a config, pulling doc values from the default {@link
* FacetsConfig#DEFAULT_INDEX_FIELD_NAME}.
*/
public DefaultSortedSetDocValuesReaderState(IndexReader reader) throws IOException {
- this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME);
+ this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME, null);
}
- /** Creates this, pulling doc values from the specified field. */
+ /** Creates this without a config, pulling doc values from the specified field. */
public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) throws IOException {
+ this(reader, field, null);
+ }
+
+ /** Creates this, pulling doc values from the specified field. */
+ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field, FacetsConfig config)
+ throws IOException {
this.field = field;
this.reader = reader;
+ this.config = Objects.requireNonNullElse(config, new FacetsConfig());
Review comment:
Yeah sure, in `SSDVFacetCounts` and `ConcurrentSSDVFacetCounts`, I have this line which just stores the facet config of the state:
```
this.stateConfig = state.getFacetConfig();
```
I think replacing a null with the default here would be better, because then we can still check if the `state` has a null config (which would mean we can still check if a config was provided if needed). I'll move this to the FacetCount constructors then.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] gsmiller commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
gsmiller commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r781298962
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -317,10 +345,19 @@ public Number getSpecificValue(String dim, String... path) throws IOException {
public List<FacetResult> getAllDims(int topN) throws IOException {
List<FacetResult> results = new ArrayList<>();
- for (Map.Entry<String, OrdRange> ent : state.getPrefixToOrdRange().entrySet()) {
- FacetResult fr = getDim(ent.getKey(), ent.getValue(), topN);
- if (fr != null) {
- results.add(fr);
+ for (String dim : state.getDims()) {
+ if (stateConfig.getDimConfig(dim).hierarchical) {
+ DimTree dimTree = state.getDimTree(dim);
+ FacetResult fr = getDim(dim, emptyPath, dimTree.dimStartOrd, dimTree.iterator(), topN);
Review comment:
I think it's fine how it is. I don't want to get too nit-picky about the naming of this internal variable.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] gsmiller commented on pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
gsmiller commented on pull request #509:
URL: https://github.com/apache/lucene/pull/509#issuecomment-992752034
Ah I think I understand the need for retaining the tree structure now. With taxonomy faceting, we generally "roll up" ancestry counts at construction-time but with this approach we can't actually do that because ordinals may not actually exist for some of the ancestors right? So we need this structure in order to essentially "roll up" counts when doing the top-n or specific value retrieval.
Have you considered the multi-value scenario? What happens if a document has multiple values for a faceting field that share common ancestry? We'll double-count ancestors right? Taxonomy-based faceting handles this at indexing time based on the `DimConfig` specified for the field. So if a field is configured as multi-valued, we explicitly index all of the ancestry values and don't do the "roll up" to avoid the double-counting problem. I wonder if we need to do something similar for this as well?
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] mdmarshmallow commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
mdmarshmallow commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r766907398
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -37,19 +38,102 @@
public abstract class SortedSetDocValuesReaderState implements Accountable {
/**
- * Holds start/end range of ords, which maps to one dimension (someday we may generalize it to map
- * to hierarchies within one dimension).
+ * Class to store ranges of facet label as well as references to children of that label, key'd by
+ * label string
*/
- public static final class OrdRange {
+ public static final class HierarchicalOrdRange {
/** Start of range, inclusive: */
- public final int start;
- /** End of range, inclusive: */
- public final int end;
-
- /** Start and end are inclusive. */
- public OrdRange(int start, int end) {
- this.start = start;
- this.end = end;
+ private int start = -1;
+ /** End of range, exclusive: */
Review comment:
This should say inclusive
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] mdmarshmallow commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
mdmarshmallow commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r766907398
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -37,19 +38,102 @@
public abstract class SortedSetDocValuesReaderState implements Accountable {
/**
- * Holds start/end range of ords, which maps to one dimension (someday we may generalize it to map
- * to hierarchies within one dimension).
+ * Class to store ranges of facet label as well as references to children of that label, key'd by
+ * label string
*/
- public static final class OrdRange {
+ public static final class HierarchicalOrdRange {
/** Start of range, inclusive: */
- public final int start;
- /** End of range, inclusive: */
- public final int end;
-
- /** Start and end are inclusive. */
- public OrdRange(int start, int end) {
- this.start = start;
- this.end = end;
+ private int start = -1;
+ /** End of range, exclusive: */
Review comment:
This should say inclusive
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] gsmiller commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
gsmiller commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r774170371
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,24 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+ Set<String> addedPaths = new HashSet<>();
Review comment:
So you shouldn't need to actually de-dupe. `SortedSetDocValues` will do this for you (i.e., it will only add each unique value one to each document when it goes to actually index it, even if you've added it multiple times). I'd suggest delegating to SSDV to do this de-duping and just keep this code simple.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,37 +86,78 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
+ // keeps track of last path with length i where the path has an unfilled sibling
+ Map<Integer, OrdAndComponent> pathsWithUnfilledSiblings = new HashMap<>();
+
+ BytesRef nextTerm = null;
+ String[] nextComponents = null;
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
- String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ if (children == null) {
+ children = new FixedBitSet(valueCount);
+ siblings = new int[valueCount];
+ }
+
+ String[] components;
+
+ if (nextTerm == null) {
+ BytesRef term = dv.lookupOrd(ord);
+ components = FacetsConfig.stringToPath(term.utf8ToString());
+ } else {
+ components = nextComponents;
+ }
+
+ if (components.length == 1) {
+ // current ord is a dim
+ if (dims == null) {
+ dims = new ArrayList<>();
+ }
+ dims.add(new DimAndOrd(components[0], ord));
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+
+ if (pathsWithUnfilledSiblings.containsKey(components.length - 1)) {
Review comment:
I think you could solve this with a stack instead of a set. Each time the path length increases, you could put an entry on the stack containing the last path at that length. Then whenever the path length decreases from one ordinal to the next, you could pop the stack and examine the entries to see if you need to "connect" the siblings. Would that make sense? I might sketch out a suggested algorithm if I have some. Maybe this approach is easier to read but a stack is immediately what my brain jumped to when I thought about this problem. Thoughts?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,37 +86,78 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
+ // keeps track of last path with length i where the path has an unfilled sibling
+ Map<Integer, OrdAndComponent> pathsWithUnfilledSiblings = new HashMap<>();
+
+ BytesRef nextTerm = null;
+ String[] nextComponents = null;
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
- String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ if (children == null) {
+ children = new FixedBitSet(valueCount);
+ siblings = new int[valueCount];
+ }
+
+ String[] components;
+
+ if (nextTerm == null) {
+ BytesRef term = dv.lookupOrd(ord);
+ components = FacetsConfig.stringToPath(term.utf8ToString());
+ } else {
+ components = nextComponents;
+ }
+
+ if (components.length == 1) {
+ // current ord is a dim
+ if (dims == null) {
+ dims = new ArrayList<>();
+ }
+ dims.add(new DimAndOrd(components[0], ord));
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+
+ if (pathsWithUnfilledSiblings.containsKey(components.length - 1)) {
+ OrdAndComponent possibleSibling = pathsWithUnfilledSiblings.get(components.length - 1);
+ boolean isSibling = true;
+ for (int i = 0; i < possibleSibling.component.length - 1; i++) {
+ if (!possibleSibling.component[i].equals(components[i])) {
+ isSibling = false;
+ break;
+ }
+ }
+ if (isSibling) {
+ siblings[possibleSibling.ord] = ord;
+ } else {
+ siblings[possibleSibling.ord] = INVALID_ORDINAL;
}
- startOrd = ord;
- lastDim = components[0];
+ pathsWithUnfilledSiblings.remove(components.length - 1);
+ }
+
+ if (ord + 1 == valueCount) {
+ // last value, cannot have children or links to more siblings
+ siblings[ord] = INVALID_ORDINAL;
+ break;
+ }
+
+ nextTerm = dv.lookupOrd(ord + 1);
+ nextComponents = FacetsConfig.stringToPath(nextTerm.utf8ToString());
+
+ if (components.length < nextComponents.length) {
+ // next ord must be a direct child of current ord
+ children.set(ord);
Review comment:
Oh, I like this! I was originally thinking you'd need an `int[]` to track the first child for each ordinal (much like taxonomy faceting does) but it's a smart observation that the first child will always have to be one value greater than the parent ordinal for the SSDV case. Nice way to save some memory! Very cool :)
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,24 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+ Set<String> addedPaths = new HashSet<>();
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
-
- // For facet counts:
- doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
-
- // For drill-down:
- indexDrillDownTerms(doc, indexFieldName, getDimConfig(facetField.dim), facetLabel);
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ for (int i = 0; i < facetLabel.length; i++) {
Review comment:
Is the only reason for indexing all the ancestor paths to make sure counts for multi-valued docs work correctly?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,37 +86,78 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
+ // keeps track of last path with length i where the path has an unfilled sibling
+ Map<Integer, OrdAndComponent> pathsWithUnfilledSiblings = new HashMap<>();
+
+ BytesRef nextTerm = null;
+ String[] nextComponents = null;
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
- String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ if (children == null) {
+ children = new FixedBitSet(valueCount);
+ siblings = new int[valueCount];
+ }
+
+ String[] components;
+
+ if (nextTerm == null) {
+ BytesRef term = dv.lookupOrd(ord);
+ components = FacetsConfig.stringToPath(term.utf8ToString());
+ } else {
+ components = nextComponents;
+ }
+
+ if (components.length == 1) {
+ // current ord is a dim
+ if (dims == null) {
+ dims = new ArrayList<>();
+ }
+ dims.add(new DimAndOrd(components[0], ord));
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+
+ if (pathsWithUnfilledSiblings.containsKey(components.length - 1)) {
+ OrdAndComponent possibleSibling = pathsWithUnfilledSiblings.get(components.length - 1);
+ boolean isSibling = true;
+ for (int i = 0; i < possibleSibling.component.length - 1; i++) {
+ if (!possibleSibling.component[i].equals(components[i])) {
+ isSibling = false;
+ break;
+ }
+ }
+ if (isSibling) {
+ siblings[possibleSibling.ord] = ord;
+ } else {
+ siblings[possibleSibling.ord] = INVALID_ORDINAL;
}
- startOrd = ord;
- lastDim = components[0];
+ pathsWithUnfilledSiblings.remove(components.length - 1);
+ }
+
+ if (ord + 1 == valueCount) {
+ // last value, cannot have children or links to more siblings
+ siblings[ord] = INVALID_ORDINAL;
+ break;
+ }
+
+ nextTerm = dv.lookupOrd(ord + 1);
+ nextComponents = FacetsConfig.stringToPath(nextTerm.utf8ToString());
+
+ if (components.length < nextComponents.length) {
+ // next ord must be a direct child of current ord
Review comment:
This is only true because all ancestry paths are explicitly indexed right? Otherwise it could be possible that the next value is actually a "grandchild" (or even further descended)? Might be worth mentioning this in the comments.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -46,13 +48,18 @@
private final String field;
private final int valueCount;
+ // denotes whether next ord is child or not
+ private FixedBitSet children;
Review comment:
This comment and variable name were a bit confusing to me. From looking through the code, it seems like this bitset is really storing whether-or-not a given ordinal has at least one child right? So a set bit means "yes, there is at least one child" and then it's implied that the first child is the next ordinal? To get the rest of the children, you have to start traversing the siblings?
Maybe a different name like `hasChildren` might be helpful along with a comment that's a little more descriptive?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,37 +86,78 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
+ // keeps track of last path with length i where the path has an unfilled sibling
+ Map<Integer, OrdAndComponent> pathsWithUnfilledSiblings = new HashMap<>();
+
+ BytesRef nextTerm = null;
+ String[] nextComponents = null;
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
- String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ if (children == null) {
+ children = new FixedBitSet(valueCount);
+ siblings = new int[valueCount];
+ }
+
+ String[] components;
+
+ if (nextTerm == null) {
+ BytesRef term = dv.lookupOrd(ord);
+ components = FacetsConfig.stringToPath(term.utf8ToString());
+ } else {
+ components = nextComponents;
+ }
+
+ if (components.length == 1) {
+ // current ord is a dim
+ if (dims == null) {
+ dims = new ArrayList<>();
+ }
+ dims.add(new DimAndOrd(components[0], ord));
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+
+ if (pathsWithUnfilledSiblings.containsKey(components.length - 1)) {
+ OrdAndComponent possibleSibling = pathsWithUnfilledSiblings.get(components.length - 1);
+ boolean isSibling = true;
+ for (int i = 0; i < possibleSibling.component.length - 1; i++) {
+ if (!possibleSibling.component[i].equals(components[i])) {
Review comment:
We generally use `== false` instead of `!` in this codebase to improve readability. So in this case, it would be good to change to `possibleSibling.component[i].equals(components[i]) == false`
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -37,19 +38,102 @@
public abstract class SortedSetDocValuesReaderState implements Accountable {
/**
- * Holds start/end range of ords, which maps to one dimension (someday we may generalize it to map
- * to hierarchies within one dimension).
+ * Class to store ranges of facet label as well as references to children of that label, key'd by
+ * label string
*/
- public static final class OrdRange {
+ public static final class HierarchicalOrdRange {
Review comment:
As I mentioned elsewhere, I'm not convinced we need to maintain this tree structure, allocating all these separate maps, requiring them to be ordered, etc. Can we not maintain a single map of "path" -> ordinal range? As far as I can tell, when we need to look up the ordinal range for a value we already have a full path and should just be able to do a simple key/value lookup in a flat map to obtain the range for that path right? I think a single map without all this tree structure might be simpler and less costly w.r.t. allocating a bunch of maps, etc. What do you think? Am I maybe overlooking some fundamental reason we need to maintain this tree?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -222,4 +258,59 @@ public IndexReader getReader() {
public int getSize() {
return valueCount;
}
+
+ @Override
+ public Iterable<Integer> childOrds(int pathOrd) {
Review comment:
What about `PrimitiveIterator.OfInt` here instead? It would be nice to avoid boxing all those ints.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -95,29 +92,31 @@ public FacetResult getTopChildren(int topN, String dim, String... path) throws I
if (topN <= 0) {
throw new IllegalArgumentException("topN must be > 0 (got: " + topN + ")");
}
- if (path.length > 0) {
- throw new IllegalArgumentException("path should be 0 length");
- }
- OrdRange ordRange = state.getOrdRange(dim);
- if (ordRange == null) {
- return null; // means dimension was never indexed
+
+ int pathOrd = (int) dv.lookupTerm(new BytesRef(FacetsConfig.pathToString(dim, path)));
+ if (pathOrd == -1) {
+ // path was never indexed
+ return null;
}
- return getDim(dim, ordRange, topN);
+
+ Iterable<Integer> childOrds = state.childOrds(pathOrd);
+
+ return getDim(dim, path, pathOrd, childOrds, topN);
}
- private FacetResult getDim(String dim, OrdRange ordRange, int topN) throws IOException {
+ private FacetResult getDim(
+ String dim, String[] path, int pathOrd, Iterable<Integer> childOrds, int topN)
+ throws IOException {
TopOrdAndIntQueue q = null;
int bottomCount = 0;
- int dimCount = 0;
Review comment:
I like that this also fixes the bug tracked in LUCENE-9952. If you end up needing to plumb the facet configuration in here for back-compat (I think you might), then it would be good to only do this in cases where it's necessary. Taxo faceting is a good example of this. The code is a little burdensome due to having slightly different aggregation implementations depending on how the dim is configured, but it lets the index stay as small as possible.
So in this particular case, if a user has single-valued dims that aren't hierarchical, we hopefully won't need to index the dims explicitly and can continue to aggregate them with this logic as before.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -222,4 +258,59 @@ public IndexReader getReader() {
public int getSize() {
return valueCount;
}
+
+ @Override
+ public Iterable<Integer> childOrds(int pathOrd) {
+ return () ->
+ new Iterator<>() {
+
+ boolean atStart = true;
+ int currentOrd = pathOrd;
+
+ @Override
+ public boolean hasNext() {
+ if (atStart) {
+ if (currentOrd < 0 || currentOrd >= children.length()) {
+ return false;
+ }
+ return children.get(currentOrd);
+ } else {
+ return siblings[currentOrd] != INVALID_ORDINAL;
+ }
+ }
+
+ @Override
+ public Integer next() {
+ if (atStart) {
+ if (currentOrd < 0 || currentOrd >= children.length()) {
+ return INVALID_ORDINAL;
+ }
+ atStart = false;
+ if (children.get(currentOrd)) {
+ return ++currentOrd;
Review comment:
A lot of people find this notation a bit difficult to read. We usually do something like:
```
currentOrd++;
return currentOrd;
```
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -317,26 +317,23 @@ public Number getSpecificValue(String dim, String... path) throws IOException {
public List<FacetResult> getAllDims(int topN) throws IOException {
List<FacetResult> results = new ArrayList<>();
- for (Map.Entry<String, OrdRange> ent : state.getPrefixToOrdRange().entrySet()) {
- FacetResult fr = getDim(ent.getKey(), ent.getValue(), topN);
+ for (DimAndOrd dim : state.getDims()) {
+ Iterable<Integer> childOrds = state.childOrds(dim.ord);
+ FacetResult fr = getDim(dim.dim, new String[0], dim.ord, childOrds, topN);
if (fr != null) {
results.add(fr);
}
}
// Sort by highest count:
- Collections.sort(
- results,
- new Comparator<FacetResult>() {
- @Override
- public int compare(FacetResult a, FacetResult b) {
- if (a.value.intValue() > b.value.intValue()) {
- return -1;
- } else if (b.value.intValue() > a.value.intValue()) {
- return 1;
- } else {
- return a.dim.compareTo(b.dim);
- }
+ results.sort(
+ (a, b) -> {
Review comment:
I've seen past feedback to generally avoid lambdas in favor of anonymous classes. I think @rmuir has brought this up in the past. I'm no expert on lambdas but I think there's a class generation cost that ends up getting paid at runtime? Maybe Robert can chime in with thoughts on lambdas, but I tend to avoid them in this codebase.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -36,23 +35,21 @@
*/
public abstract class SortedSetDocValuesReaderState implements Accountable {
- /**
- * Holds start/end range of ords, which maps to one dimension (someday we may generalize it to map
- * to hierarchies within one dimension).
- */
- public static final class OrdRange {
- /** Start of range, inclusive: */
- public final int start;
- /** End of range, inclusive: */
- public final int end;
+ /** Holder class for a dimension along with it's corresponding ordinal */
+ public static class DimAndOrd {
Review comment:
I'd make this `final`
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -46,13 +48,18 @@
private final String field;
private final int valueCount;
+ // denotes whether next ord is child or not
+ private FixedBitSet children;
+ // maps an ord to its first sibling
+ private int[] siblings;
Review comment:
This could get fairly expensive with high-cardinality dimensions. I'd at least add a note/TODO here to see if there's a more efficient way to go about doing this to avoid the memory consumption.
Also, I know you're still thinking about backwards-compatibility, but it would be really nice to not incur this memory overhead for non-hierarchical cases to avoid existing users all the sudden seeing this nasty increase in memory usage with SSDV faceting.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -46,13 +48,18 @@
private final String field;
private final int valueCount;
+ // denotes whether next ord is child or not
+ private FixedBitSet children;
Review comment:
I'd be in favor of initializing `children`, `siblings` and `dims` up front and making them `final` instead of lazily initializing them below. The only case where you're saving initialization is if there are no actual values in the SSDV field. I suspect that can't even happen, but if it can, seems incredibly rare (and useless?).
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -36,23 +35,21 @@
*/
public abstract class SortedSetDocValuesReaderState implements Accountable {
- /**
- * Holds start/end range of ords, which maps to one dimension (someday we may generalize it to map
- * to hierarchies within one dimension).
- */
- public static final class OrdRange {
- /** Start of range, inclusive: */
- public final int start;
- /** End of range, inclusive: */
- public final int end;
+ /** Holder class for a dimension along with it's corresponding ordinal */
+ public static class DimAndOrd {
+ String dim;
+ int ord;
- /** Start and end are inclusive. */
- public OrdRange(int start, int end) {
- this.start = start;
- this.end = end;
+ /** sole constructor */
+ public DimAndOrd(String dim, int ord) {
+ this.dim = dim;
+ this.ord = ord;
}
}
+ /** Invalid ordinal const */
+ public static int INVALID_ORDINAL = -1;
Review comment:
What about reusing `SortedSetDocValues#NO_MORE_ORDS` for this purpose instead of defining a new constant?
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] gsmiller commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
gsmiller commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r774242640
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -37,19 +38,102 @@
public abstract class SortedSetDocValuesReaderState implements Accountable {
/**
- * Holds start/end range of ords, which maps to one dimension (someday we may generalize it to map
- * to hierarchies within one dimension).
+ * Class to store ranges of facet label as well as references to children of that label, key'd by
+ * label string
*/
- public static final class OrdRange {
+ public static final class HierarchicalOrdRange {
Review comment:
Ooops! This was a stale comment from last time I was reviewing that snuck in. Please disregard!
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] mdmarshmallow commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
mdmarshmallow commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r780593368
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetField.java
##########
@@ -40,20 +41,33 @@
/** Dimension. */
public final String dim;
- /** Label. */
- public final String label;
+ /** Path. */
+ public final String[] path;
+
+ /** String form of path. */
Review comment:
I'll just use this comment.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,36 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
-
- // For facet counts:
- doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
-
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ DimConfig dimConfig = getDimConfig(facetField.dim);
+ if (dimConfig.hierarchical) {
+ for (int i = 0; i < facetLabel.length; i++) {
+ String fullPath = pathToString(facetLabel.components, i + 1);
+ // For facet counts:
+ doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
+ }
+ // For drill-down:
Review comment:
Removed
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -317,10 +345,19 @@ public Number getSpecificValue(String dim, String... path) throws IOException {
public List<FacetResult> getAllDims(int topN) throws IOException {
List<FacetResult> results = new ArrayList<>();
- for (Map.Entry<String, OrdRange> ent : state.getPrefixToOrdRange().entrySet()) {
- FacetResult fr = getDim(ent.getKey(), ent.getValue(), topN);
- if (fr != null) {
- results.add(fr);
+ for (String dim : state.getDims()) {
+ if (stateConfig.getDimConfig(dim).hierarchical) {
+ DimTree dimTree = state.getDimTree(dim);
+ FacetResult fr = getDim(dim, emptyPath, dimTree.dimStartOrd, dimTree.iterator(), topN);
Review comment:
Hmm my reasoning with `dimStartOrd` was that it is the first ("start") ord in the dimension represented by the `DimTree`. Though I can also see your reasoning for calling it `dimOrd` in that it is ord of the dimension. Maybe just `firstOrd` or `startOrd` might be more appropriate?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -62,15 +166,28 @@ protected SortedSetDocValuesReaderState() {}
/** Indexed field we are reading. */
public abstract String getField();
+ /** Returns top-level index reader. */
+ public abstract IndexReader getReader();
+
+ /** Number of unique labels. */
+ public abstract int getSize();
+
+ /** Returns the associated facet config. */
+ public abstract FacetsConfig getFacetConfig();
Review comment:
No worries. In fact, thanks for reviewing this so thoroughly :)
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -51,20 +55,42 @@
private final Map<String, OrdinalMap> cachedOrdMaps = new HashMap<>();
+ private final FacetsConfig config;
+
+ /** Used for hierarchical dims. */
+ private final Map<String, DimTree> prefixToDimTree = new HashMap<>();
+
+ /** Used for flat dims. */
private final Map<String, OrdRange> prefixToOrdRange = new HashMap<>();
/**
- * Creates this, pulling doc values from the default {@link
+ * Creates this with a config, pulling doc values from the default {@link
+ * FacetsConfig#DEFAULT_INDEX_FIELD_NAME}.
+ */
+ public DefaultSortedSetDocValuesReaderState(IndexReader reader, FacetsConfig config)
+ throws IOException {
+ this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME, config);
+ }
+
+ /**
+ * Creates this without a config, pulling doc values from the default {@link
* FacetsConfig#DEFAULT_INDEX_FIELD_NAME}.
*/
public DefaultSortedSetDocValuesReaderState(IndexReader reader) throws IOException {
- this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME);
+ this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME, null);
}
- /** Creates this, pulling doc values from the specified field. */
+ /** Creates this without a config, pulling doc values from the specified field. */
public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) throws IOException {
+ this(reader, field, null);
+ }
+
+ /** Creates this, pulling doc values from the specified field. */
+ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field, FacetsConfig config)
+ throws IOException {
this.field = field;
this.reader = reader;
+ this.config = Objects.requireNonNullElse(config, new FacetsConfig());
Review comment:
Yeah sure, in `SSDVFacetCounts` and `ConcurrentSSDVFacetCounts`, I have this line which just stores the facet config of the state:
```
this.stateConfig = state.getFacetConfig();
```
I think replacing a null with the default here would be better, because then we can still check if the `state` has a null config (which would mean we can still check if a config was provided if needed). I'll move this to the FacetCount constructors then.
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] gsmiller merged pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
gsmiller merged pull request #509:
URL: https://github.com/apache/lucene/pull/509
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] gsmiller commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
gsmiller commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r779892023
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetField.java
##########
@@ -41,19 +42,28 @@
public final String dim;
/** Label. */
- public final String label;
+ public final String[] path;
Review comment:
It's frustrating that these fields are public, but because they are, this isn't actually backwards compatible. It seems like these are public to make them visible to other code in the facets module that's in a different java package (specifically, `FacetsConfig`), but users could still be reading this field directly for some reason and have their code no longer compile because of this change. If we really want to keep this fully back-compat, I think we need to add a new field for `path` and maintain the `label` string (marked as deprecated). The label could be created in the ctor with `FacetsConfig#pathToString`.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -95,17 +96,34 @@ public FacetResult getTopChildren(int topN, String dim, String... path) throws I
if (topN <= 0) {
throw new IllegalArgumentException("topN must be > 0 (got: " + topN + ")");
}
- if (path.length > 0) {
- throw new IllegalArgumentException("path should be 0 length");
- }
- OrdRange ordRange = state.getOrdRange(dim);
- if (ordRange == null) {
- return null; // means dimension was never indexed
+
+ if (state.isHierarchicalDim(dim)) {
+ int pathOrd = (int) dv.lookupTerm(new BytesRef(FacetsConfig.pathToString(dim, path)));
+ if (pathOrd == -1) {
Review comment:
If you take a look at the javadoc (or implementation) for `SortedSetDocValues#lookupTerm`, I think you'll want to change this condition to check for a return value < 0 (instead of `-1` explicitly). Any negative return value indicates "not found".
It would also be good to ensure there's a unit test covering this case. I suspect there may not be if you didn't find this as a bug in testing?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,38 +104,160 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
-
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
- for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
+ int ord = 0;
+ while (ord != valueCount) {
+ BytesRef term = dv.lookupOrd(ord);
String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ String dim = components[0];
+ if (config != null && config.getDimConfig(dim).hierarchical) {
+ ord = createOneHierarchicalFacetDimState(dv, ord) + 1;
+ } else {
+ ord = createOneFlatFacetDimState(dv, ord) + 1;
+ }
+ }
+ }
+
+ // returns last ord of dimension
+ private int createOneHierarchicalFacetDimState(SortedSetDocValues dv, int dimStartOrd)
+ throws IOException {
+ List<Boolean> hasChildren = new ArrayList<>();
+ List<Integer> siblings = new ArrayList<>();
+
+ String dim = null;
+
+ // stack of paths with unfulfilled siblings
+ Stack<OrdAndComponent> siblingStack = new Stack<>();
+
+ String[] nextComponents = null;
+ int dimEndOrd = dimStartOrd;
+ while (true) {
+ String[] components;
+
+ int ord = dimEndOrd - dimStartOrd;
+
+ if (nextComponents == null) {
+ BytesRef term = dv.lookupOrd(dimEndOrd);
+ components = FacetsConfig.stringToPath(term.utf8ToString());
+ dim = components[0];
+ } else {
+ components = nextComponents;
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+
+ while (siblingStack.empty() == false
+ && siblingStack.peek().component.length >= components.length) {
+ OrdAndComponent possibleSibling = siblingStack.pop();
+ if (possibleSibling.component.length == components.length) {
+ // lengths are equal
+ boolean isSibling = true;
+ for (int i = 0; i < possibleSibling.component.length - 1; i++) {
+ if (possibleSibling.component[i].equals(components[i]) == false) {
Review comment:
My reasoning might be incomplete, but I don't think you need this loop check. Isn't it enough that the lengths are equal? I think for some ancestry component to be different, we would have already popped this off right?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,35 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ if (getDimConfig(facetField.dim).hierarchical) {
Review comment:
minor: Maybe pull out the DimConfig into a local variable since you reference it a couple times.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -62,15 +159,27 @@ protected SortedSetDocValuesReaderState() {}
/** Indexed field we are reading. */
public abstract String getField();
+ /** Returns top-level index reader. */
+ public abstract IndexReader getReader();
+
+ /** Number of unique labels. */
+ public abstract int getSize();
+
+ /** Returns if dim is configured as hierarchical ** */
+ public abstract boolean isHierarchicalDim(String dim);
+
+ /*** Only used for flat facets (dim/value) ***/
+
/** Returns the {@link OrdRange} for this dimension. */
public abstract OrdRange getOrdRange(String dim);
/** Returns mapping from prefix to {@link OrdRange}. */
public abstract Map<String, OrdRange> getPrefixToOrdRange();
- /** Returns top-level index reader. */
- public abstract IndexReader getReader();
+ /*** Only used for hierarchical facets ***/
- /** Number of unique labels. */
- public abstract int getSize();
+ public abstract DimTree getDimTree(String dim);
+
+ /** Returns a list of all dimensions and their respective ordinals */
Review comment:
This doesn't return the ordinals right? Just the dimension strings?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -145,12 +164,19 @@ private FacetResult getDim(String dim, OrdRange ordRange, int topN) throws IOExc
LabelAndValue[] labelValues = new LabelAndValue[q.size()];
for (int i = labelValues.length - 1; i >= 0; i--) {
TopOrdAndIntQueue.OrdAndValue ordAndValue = q.pop();
+ assert ordAndValue != null;
final BytesRef term = dv.lookupOrd(ordAndValue.ord);
String[] parts = FacetsConfig.stringToPath(term.utf8ToString());
- labelValues[i] = new LabelAndValue(parts[1], ordAndValue.value);
+ labelValues[i] = new LabelAndValue(parts[parts.length - 1], ordAndValue.value);
}
- return new FacetResult(dim, new String[0], dimCount, labelValues, childCount);
+ if (pathOrd == -1) {
+ // not hierarchical facet
+ return new FacetResult(dim, new String[0], dimCount, labelValues, childCount);
Review comment:
Maybe define a local constant as `new String[0]` that you reference in these spots instead?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -51,8 +51,105 @@ public OrdRange(int start, int end) {
this.start = start;
this.end = end;
}
+
+ /** Iterates from start to end ord (inclusive) * */
Review comment:
minor: I see some one-line javadoc that has a funky extra '*' near the end. Could you do a pass and try to clean these up? I'm sure it's some combo of and IDE + spotless?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -62,15 +159,27 @@ protected SortedSetDocValuesReaderState() {}
/** Indexed field we are reading. */
public abstract String getField();
+ /** Returns top-level index reader. */
+ public abstract IndexReader getReader();
+
+ /** Number of unique labels. */
+ public abstract int getSize();
+
+ /** Returns if dim is configured as hierarchical ** */
+ public abstract boolean isHierarchicalDim(String dim);
Review comment:
What about actually exposing the `FacetsConfig` instead of just this one-off attribute of the config? That would also help with a separate issue where dim counts can be over-counted since SSDV faceting doesn't know whether-or-not it's multi-valued (LUCENE-9952).
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,35 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ if (getDimConfig(facetField.dim).hierarchical) {
+ for (int i = 0; i < facetLabel.length; i++) {
+ String fullPath = pathToString(facetLabel.components, i + 1);
+ // For facet counts:
+ doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
+
+ // For drill-down:
+ indexDrillDownTerms(doc, indexFieldName, getDimConfig(facetField.dim), facetLabel);
+ }
+ } else {
+ if (facetLabel.length != 2) {
+ throw new IllegalArgumentException(
Review comment:
minor: Maybe try to base the exception message on the error checking already done for taxo-facets to make the wording a little more consistent?
```
if (facetField.path.length > 1 && dimConfig.hierarchical == false) {
throw new IllegalArgumentException(
"dimension \""
+ facetField.dim
+ "\" is not hierarchical yet has "
+ facetField.path.length
+ " components");
}
```
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -95,17 +96,34 @@ public FacetResult getTopChildren(int topN, String dim, String... path) throws I
if (topN <= 0) {
throw new IllegalArgumentException("topN must be > 0 (got: " + topN + ")");
}
- if (path.length > 0) {
- throw new IllegalArgumentException("path should be 0 length");
- }
- OrdRange ordRange = state.getOrdRange(dim);
- if (ordRange == null) {
- return null; // means dimension was never indexed
+
+ if (state.isHierarchicalDim(dim)) {
+ int pathOrd = (int) dv.lookupTerm(new BytesRef(FacetsConfig.pathToString(dim, path)));
+ if (pathOrd == -1) {
+ // path was never indexed
+ return null;
+ }
+ DimTree dimTree = state.getDimTree(dim);
+ if (dimTree == null) {
+ return null;
+ }
+ return getDim(dim, path, pathOrd, dimTree.iterator(pathOrd), topN);
+ } else {
+ if (path.length > 0) {
+ throw new IllegalArgumentException(
+ "Field is not configured as hierarchical, path should be 0 length");
+ }
+ OrdRange ordRange = state.getOrdRange(dim);
+ if (ordRange == null) {
+ return null;
Review comment:
minor: Could you please retain the comment on this line? `// means dimension was never indexed`
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesReaderState.java
##########
@@ -51,8 +51,105 @@ public OrdRange(int start, int end) {
this.start = start;
this.end = end;
}
+
+ /** Iterates from start to end ord (inclusive) * */
+ public PrimitiveIterator.OfInt iterator() {
+ return new PrimitiveIterator.OfInt() {
+ int current = start;
+
+ @Override
+ public int nextInt() {
+ if (current > end) {
+ return INVALID_ORDINAL;
+ }
+ return current++;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return current <= end;
+ }
+ };
+ }
+ }
+
+ /**
+ * Holds children and sibling information for a single dimension. Only used with hierarchical
+ * dimensions.
+ */
+ public static final class DimTree {
+ private final FixedBitSet hasChildren;
+ // TODO: This array can take up a lot of space. Change type based on input size maybe?
+ private final int[] siblings;
+
+ /** The first ord of the dimension * */
+ public final int dimStartOrd;
+
+ /** Sibling and children must be of same length * */
+ public DimTree(int dimStartOrd, List<Integer> sibling, List<Boolean> hasChildren) {
+ assert sibling.size() == hasChildren.size();
Review comment:
Throwing an IllegalArumentException might be a better fit here since these are user-provided parameters.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -95,17 +96,34 @@ public FacetResult getTopChildren(int topN, String dim, String... path) throws I
if (topN <= 0) {
throw new IllegalArgumentException("topN must be > 0 (got: " + topN + ")");
}
- if (path.length > 0) {
- throw new IllegalArgumentException("path should be 0 length");
- }
- OrdRange ordRange = state.getOrdRange(dim);
- if (ordRange == null) {
- return null; // means dimension was never indexed
+
+ if (state.isHierarchicalDim(dim)) {
+ int pathOrd = (int) dv.lookupTerm(new BytesRef(FacetsConfig.pathToString(dim, path)));
+ if (pathOrd == -1) {
+ // path was never indexed
+ return null;
+ }
+ DimTree dimTree = state.getDimTree(dim);
+ if (dimTree == null) {
Review comment:
Seems like this should never happen right? If we reach this point, it means the path was indexed. Shouldn't there always be a dim tree then?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,38 +104,160 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
-
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
- for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
+ int ord = 0;
+ while (ord != valueCount) {
+ BytesRef term = dv.lookupOrd(ord);
String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ String dim = components[0];
+ if (config != null && config.getDimConfig(dim).hierarchical) {
+ ord = createOneHierarchicalFacetDimState(dv, ord) + 1;
+ } else {
+ ord = createOneFlatFacetDimState(dv, ord) + 1;
+ }
+ }
+ }
+
+ // returns last ord of dimension
+ private int createOneHierarchicalFacetDimState(SortedSetDocValues dv, int dimStartOrd)
+ throws IOException {
+ List<Boolean> hasChildren = new ArrayList<>();
+ List<Integer> siblings = new ArrayList<>();
+
+ String dim = null;
+
+ // stack of paths with unfulfilled siblings
+ Stack<OrdAndComponent> siblingStack = new Stack<>();
+
+ String[] nextComponents = null;
+ int dimEndOrd = dimStartOrd;
+ while (true) {
+ String[] components;
+
+ int ord = dimEndOrd - dimStartOrd;
+
+ if (nextComponents == null) {
+ BytesRef term = dv.lookupOrd(dimEndOrd);
+ components = FacetsConfig.stringToPath(term.utf8ToString());
+ dim = components[0];
+ } else {
+ components = nextComponents;
}
- if (!components[0].equals(lastDim)) {
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, ord - 1));
+
+ while (siblingStack.empty() == false
+ && siblingStack.peek().component.length >= components.length) {
+ OrdAndComponent possibleSibling = siblingStack.pop();
+ if (possibleSibling.component.length == components.length) {
+ // lengths are equal
+ boolean isSibling = true;
+ for (int i = 0; i < possibleSibling.component.length - 1; i++) {
+ if (possibleSibling.component[i].equals(components[i]) == false) {
+ isSibling = false;
+ break;
+ }
+ }
+ if (isSibling) {
+ siblings.set(possibleSibling.ord, ord);
+ }
}
- startOrd = ord;
- lastDim = components[0];
}
+
+ if (dimEndOrd + 1 == valueCount) {
+ // current ord needs to be added, can't have children or siblings
+ siblings.add(-1);
+ hasChildren.add(false);
+ break;
+ }
+
+ BytesRef nextTerm = dv.lookupOrd(dimEndOrd + 1);
+ nextComponents = FacetsConfig.stringToPath(nextTerm.utf8ToString());
+
+ if (nextComponents[0].equals(components[0]) == false) {
+ // current ord needs to be added, can't have children or siblings
+ siblings.add(-1);
+ hasChildren.add(false);
+ break;
+ }
+
+ if (components.length < nextComponents.length) {
+ // next ord must be a direct child of current ord, this is because we are indexing all
+ // ancestral paths
+ hasChildren.add(ord, true);
+ // we don't know if this ord has a sibling or where it's sibling could be yet
+ siblingStack.push(new OrdAndComponent(ord, components));
+ // we still add INVALID_ORDINAL, which will be replaced if a valid sibling is found
+ siblings.add(ord, INVALID_ORDINAL);
+ } else if (components.length == nextComponents.length) {
+ // next ord must be a sibling of current and there are no direct children or current, this
+ // is because we
+ // are indexing all ancestral paths
+ siblings.add(ord, ord + 1);
+ hasChildren.add(ord, false);
+ } else {
+ // components.length > nextComponents.length
+ // next ord is neither sibling nor child
+ siblings.add(ord, INVALID_ORDINAL);
+ hasChildren.add(ord, false);
+ }
+
+ dimEndOrd++;
}
- if (lastDim != null) {
- prefixToOrdRange.put(lastDim, new OrdRange(startOrd, valueCount - 1));
+ prefixToDimTree.put(dim, new DimTree(dimStartOrd, siblings, hasChildren));
+
+ return dimEndOrd;
+ }
+
+ // returns last ord of dimension
+ private int createOneFlatFacetDimState(SortedSetDocValues dv, int dimStartOrd)
+ throws IOException {
+
+ String dim = null;
+
+ String[] nextComponents = null;
+ int dimEndOrd = dimStartOrd;
+
+ while (true) {
+ String[] components;
+
+ if (nextComponents == null) {
Review comment:
This should only be true on the first iteration of the loop right? Maybe it would be a little more readable to pull this outside the loop? So you'd initialize nextComponents to be the first entry for the dim and then enter the loop?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/SortedSetDocValuesFacetCounts.java
##########
@@ -317,10 +343,19 @@ public Number getSpecificValue(String dim, String... path) throws IOException {
public List<FacetResult> getAllDims(int topN) throws IOException {
List<FacetResult> results = new ArrayList<>();
- for (Map.Entry<String, OrdRange> ent : state.getPrefixToOrdRange().entrySet()) {
- FacetResult fr = getDim(ent.getKey(), ent.getValue(), topN);
- if (fr != null) {
- results.add(fr);
+ for (String dim : state.getDims()) {
+ if (state.isHierarchicalDim(dim)) {
+ DimTree dimTree = state.getDimTree(dim);
+ FacetResult fr = getDim(dim, new String[0], dimTree.dimStartOrd, dimTree.iterator(), topN);
Review comment:
Can you just pass `-1` instead of `dimTree.dimStartOrd` here? If I'm understanding the logic in `getDim`, I think you can right? Then you can make `dimStartOrd` `private`, which would be nice.
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -51,20 +54,42 @@
private final Map<String, OrdinalMap> cachedOrdMaps = new HashMap<>();
+ private final FacetsConfig config;
+
+ /*** Used for hierarchical dims ***/
Review comment:
I commented elsewhere but there's something going on with extra '*' in some of these javadoc comments :)
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -79,38 +104,160 @@ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) th
}
valueCount = (int) dv.getValueCount();
- // TODO: we can make this more efficient if eg we can be
- // "involved" when OrdinalMap is being created? Ie see
- // each term/ord it's assigning as it goes...
- String lastDim = null;
- int startOrd = -1;
-
- // TODO: this approach can work for full hierarchy?;
- // TaxoReader can't do this since ords are not in
- // "sorted order" ... but we should generalize this to
- // support arbitrary hierarchy:
- for (int ord = 0; ord < valueCount; ord++) {
- final BytesRef term = dv.lookupOrd(ord);
+ int ord = 0;
+ while (ord != valueCount) {
+ BytesRef term = dv.lookupOrd(ord);
String[] components = FacetsConfig.stringToPath(term.utf8ToString());
- if (components.length != 2) {
- throw new IllegalArgumentException(
- "this class can only handle 2 level hierarchy (dim/value); got: "
- + Arrays.toString(components)
- + " "
- + term.utf8ToString());
+ String dim = components[0];
+ if (config != null && config.getDimConfig(dim).hierarchical) {
+ ord = createOneHierarchicalFacetDimState(dv, ord) + 1;
+ } else {
+ ord = createOneFlatFacetDimState(dv, ord) + 1;
+ }
+ }
+ }
+
+ // returns last ord of dimension
+ private int createOneHierarchicalFacetDimState(SortedSetDocValues dv, int dimStartOrd)
+ throws IOException {
+ List<Boolean> hasChildren = new ArrayList<>();
+ List<Integer> siblings = new ArrayList<>();
+
+ String dim = null;
+
+ // stack of paths with unfulfilled siblings
+ Stack<OrdAndComponent> siblingStack = new Stack<>();
+
+ String[] nextComponents = null;
+ int dimEndOrd = dimStartOrd;
+ while (true) {
+ String[] components;
+
+ int ord = dimEndOrd - dimStartOrd;
+
+ if (nextComponents == null) {
Review comment:
I made a similar comment elsewhere, but it seems like nextComponents could be initialized outside of the loop right?
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/FacetsConfig.java
##########
@@ -471,19 +471,35 @@ private void indexDrillDownTerms(
private void processSSDVFacetFields(
Map<String, List<SortedSetDocValuesFacetField>> byField, Document doc) {
+
for (Map.Entry<String, List<SortedSetDocValuesFacetField>> ent : byField.entrySet()) {
String indexFieldName = ent.getKey();
for (SortedSetDocValuesFacetField facetField : ent.getValue()) {
- FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.label);
- String fullPath = pathToString(facetLabel.components, facetLabel.length);
+ FacetLabel facetLabel = new FacetLabel(facetField.dim, facetField.path);
+ if (getDimConfig(facetField.dim).hierarchical) {
+ for (int i = 0; i < facetLabel.length; i++) {
+ String fullPath = pathToString(facetLabel.components, i + 1);
+ // For facet counts:
+ doc.add(new SortedSetDocValuesField(indexFieldName, new BytesRef(fullPath)));
+
+ // For drill-down:
+ indexDrillDownTerms(doc, indexFieldName, getDimConfig(facetField.dim), facetLabel);
Review comment:
I don't think you intended to put this in the loop right? In fact, I think it should be outside of the conditional altogether since the logic should be the same regardless of whether-or-not it's hierarchical right?
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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
[GitHub] [lucene] gsmiller commented on a change in pull request #509: LUCENE-10250: Add support for arbitrary length hierarchical SSDV facets
Posted by GitBox <gi...@apache.org>.
gsmiller commented on a change in pull request #509:
URL: https://github.com/apache/lucene/pull/509#discussion_r781298004
##########
File path: lucene/facet/src/java/org/apache/lucene/facet/sortedset/DefaultSortedSetDocValuesReaderState.java
##########
@@ -51,20 +55,42 @@
private final Map<String, OrdinalMap> cachedOrdMaps = new HashMap<>();
+ private final FacetsConfig config;
+
+ /** Used for hierarchical dims. */
+ private final Map<String, DimTree> prefixToDimTree = new HashMap<>();
+
+ /** Used for flat dims. */
private final Map<String, OrdRange> prefixToOrdRange = new HashMap<>();
/**
- * Creates this, pulling doc values from the default {@link
+ * Creates this with a config, pulling doc values from the default {@link
+ * FacetsConfig#DEFAULT_INDEX_FIELD_NAME}.
+ */
+ public DefaultSortedSetDocValuesReaderState(IndexReader reader, FacetsConfig config)
+ throws IOException {
+ this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME, config);
+ }
+
+ /**
+ * Creates this without a config, pulling doc values from the default {@link
* FacetsConfig#DEFAULT_INDEX_FIELD_NAME}.
*/
public DefaultSortedSetDocValuesReaderState(IndexReader reader) throws IOException {
- this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME);
+ this(reader, FacetsConfig.DEFAULT_INDEX_FIELD_NAME, null);
}
- /** Creates this, pulling doc values from the specified field. */
+ /** Creates this without a config, pulling doc values from the specified field. */
public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field) throws IOException {
+ this(reader, field, null);
+ }
+
+ /** Creates this, pulling doc values from the specified field. */
+ public DefaultSortedSetDocValuesReaderState(IndexReader reader, String field, FacetsConfig config)
+ throws IOException {
this.field = field;
this.reader = reader;
+ this.config = Objects.requireNonNullElse(config, new FacetsConfig());
Review comment:
OK, thanks. My preference would be to avoid defaulting this entirely so we retain the difference between "we don't know what the config is for this dim" vs. "this dim uses default config". But I don't think it's a significant difference at this point and is easy to change if we need to now that it's being defaulted internally to these faceting implementations, so I'm good with what you've done here. Thanks!
--
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.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
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