apache / apache/lucene

PathHierarchyTokenizer "ancestor search" use case broken in lucene >= 10.0

Open
#15,769 3 comments 0 reactions 0 assignees View on GitHub
type:bug
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description

[The javadocs for](https://lucene.apache.org/core/10_3_1/analysis/common/org/apache/lucene/analysis/path/PathHierarchyTokenizerFactory.html) `PathHierarchyTokenizerFactory` describe the two main use cases it was designed to satisfy:

1. "decendent path" search - by configuring it at index time, and using `KeywordTokenizer` at query time
> a query for Books/NonFic will match documents indexed with values like Books/NonFic, Books/NonFic/Law, Books/NonFic/Science/Physics, etc. But it will not match documents indexed with values like Books, or Books/Fic

2. "ancestor path" search - by configuration it at query time, and using `KeywordTokenizer` at index time
> a query for Books/NonFic/Science/Physics would match documents containing Books/NonFic, Books/NonFic/Science, or Books/NonFic/Science/Physics, but not Books/NonFic/Science/Physics/Theory or Books/NonFic/Law.

Since 10.0, it seems that the "ancestor path" type use cases have not worked (using out of the box query parsers), because of the position increment changes made in #12875 / 5d6086e .

IIUC: The changes in #12875 seem to have been made solely based on a conversation in #12750 about trying to make `PathHierarchyTokenizer` play nicely with `BaseTokenStreamTestCase.assertAnalyzesTo()` w/o any specific consideration of how/why/where this `Tokenizer` is designed to be used, or _why_ it was emitting all tokens with the same position. (ie: I don't see any indication that this change motivated by trying to fix any problems encountered "in the wild")

----

The patch below applies cleanly to `9.12`, and adds two new test methods that demonstrate both documented use cases successfully, but the same patch applied to `main` triggers test failures in `testAncestorQuery()` ...

* [PathHierarchyTokenizer.factory-javadoc-use-cases.tests.branch_9_12.patch](https://github.com/user-attachments/files/25558770/PathHierarchyTokenizer.factory-javadoc-use-cases.tests.branch_9_12.patch)

Because the current code uses a positionIncrement of `1` on all tokens emitted, QueryBuilder (or any of it's wrappers like ClassicQueryParser) now view the multiple tokens emited from parsing something like `Books/NonFic/Science/Physics` as if it were a phrase query like `"Books Books/NonFic Books/NonFic/Science Books/NonFic/Science/Physics"`, whereas the entire design of `PathHierarchyTokenizer` was based on the assumption that query parsers should treat the emitted tokens as "synonyms" (hence they were all at the same position) and result in boolean query like `(Books OR Books/NonFic OR Books/NonFic/Science OR Books/NonFic/Science/Physics)`

----

FWIW: Back in #12750, Mike [initially suggested that](https://github.com/apache/lucene/pull/12750#issuecomment-1820713053) adding a `PositionLengthAttribute` to `PathHierarchyTokenizer` would allow it to play nicely with `assertAnalyzesTo()` while still using `0` for all the position increments. I took a crack at reverting `5d6086e` and trying this approach instead. While the patch below does make `assertAnalyzesTo()` happy, it still causes `testAncestorQuery()` to fail due to the `posLen > 1` tokens cause the parser to enter `isGraph` logic and code paths in `QueryBuilder` ...

* [PathHierarchyTokenizer.factory-javadoc-use-cases.alt-poslen-attr.tests-still-fail.main.patch](https://github.com/user-attachments/files/25558771/PathHierarchyTokenizer.factory-javadoc-use-cases.alt-poslen-attr.tests-still-fail.main.patch)

(I'm no expert here, so it's certainly possible that my addition of `PositionLengthAttribute` is flawed and someone smarter then me could point out a fix to make both `testTokenizerViaAnalyzerOutput -> assertAnalyzesTo()` and `testAncestorQuery()` happy)

### Version and environment details

_No response_

Contributor guide

Open the contributing guide

Research direction

Start with PathHierarchyTokenizerFactory and PathHierarchyTokenizer, then inspect testAncestorQuery() and the testTokenizerViaAnalyzerOutput to assertAnalyzesTo() path mentioned in the report. Compare the 9.12 patch with main and trace how QueryBuilder or ClassicQueryParser handles the emitted positions. Done means both documented ancestor and descendant search cases, along with analyzer assertions, pass.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.