[ 
https://issues.apache.org/jira/browse/SOLR-18664?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
 ]

Rahul Goswami updated SOLR-18664:
---------------------------------
    Description: 
h3. Problem
The graph query parser does a breadth-first traversal: at each hop it reads the 
{{to}} field of every collected document and adds those values to the next 
hop's {{from IN (...)}} frontier query. There is no way to say "collect this 
node, but don't expand it".

A common case is a file-system hierarchy, where every document (file or folder) 
has its own id in {{id}} and its parent's id in {{parentId}}:
{noformat}
q={!graph from=parentId to=id returnRoot=true 
traversalFilter=name:prefix*}<root folder query>
{noformat}
Only folders ({{docType:folder}}) can have children, but every file's 
({{docType:file}}) {{id}} also becomes a term in the next hop's query. Each 
such term costs a docValues read, a hash insert and a terms-dictionary seek per 
segment, and can never match. Files usually far outnumber folders, so most of 
the frontier is wasted work.

* {{traversalFilter=docType:folder}} doesn't help: it restricts which documents 
are collected, so files would be dropped from the results.
* The existing leaf-node optimization ({{resolveLeafNodes()}}) only skips 
documents with *no value* in the {{to}} field. Here every document has an 
{{id}}, so it never applies.

h3. Proposal
Add an optional {{lookupFilter}} local param. Documents reached by the 
traversal (and matching {{traversalFilter}}) are always collected, but only 
those that also match {{lookupFilter}} have their edges followed. It applies at 
every level, including the root. When absent, behaviour is unchanged.
{noformat}
{!graph from=parentId to=id traversalFilter=name:prefix* 
lookupFilter=docType:folder}<root query>
{noformat}
The filter's DocSet is computed once per request via the filterCache, and the 
collector checks it before extracting edges. {{lookupFilter}} is part of 
{{GraphQuery}}'s {{equals}}/{{hashCode}}, so cache keys stay correct. It also 
works for the JSON Facet {{graph}} domain, which goes through 
{{GraphQueryParser}}.

h3. Benchmark
Synthetic 1M-doc file-system index (80k folders, 920k files, ~11.5 files per 
folder, depth up to 15), JDK 21, 4 GB heap, rows=0, queryResultCache disabled. 
Median QTime in ms; same build with and without the param, interleaved in the 
same JVMs:
||Visible subtree size||Without lookupFilter||With 
lookupFilter=docType:folder||Speedup||
|~100|2.6|1.3|1.4x|
|~1k|7.6|2.3|2.4x|
|~10k|53|7.8|6.0x|
|~50k|174|24|7.0x|
|~100k|349|42|8.0x|
|~250k|656|73|8.8x|
|whole tree (829k)|3,038|298|10.1x|
All 5,760 queries returned identical, independently verified numFound. Without 
the param, performance matches the unpatched build within run-to-run noise.

h3. Back-compat
New optional param; no change when it is absent. {{GraphPointsCollector}}'s 
public 3-arg constructor is kept.

Related: SOLR-16202 (a filter on which documents are *returned*; this one 
controls which are *expanded*).

  was:
h3. Problem
The graph query parser does a breadth-first traversal: at each hop it reads the 
{{to}} field of every collected document and adds those values to the next 
hop's {{from IN (...)}} frontier query. There is no way to say "collect this 
node, but don't expand it".

A common case is a file-system hierarchy, where every document (file or folder) 
has its own id in {{contentid}} and its parent's id in {{ParentGUID}}:
{noformat}
q={!graph from=ParentGUID to=contentid returnRoot=true 
traversalFilter=IsVisible:true}<root folder query>
{noformat}
Only folders ({{DocumentType:4}}) can have children, but every file's 
({{DocumentType:1}}) {{contentid}} also becomes a term in the next hop's query. 
Each such term costs a docValues read, a hash insert and a terms-dictionary 
seek per segment, and can never match. Files usually far outnumber folders, so 
most of the frontier is wasted work.

* {{traversalFilter=DocumentType:4}} doesn't help: it restricts which documents 
are collected, so files would be dropped from the results.
* The existing leaf-node optimization ({{resolveLeafNodes()}}) only skips 
documents with *no value* in the {{to}} field. Here every document has a 
{{contentid}}, so it never applies.

h3. Proposal
Add an optional {{lookupFilter}} local param. Documents reached by the 
traversal (and matching {{traversalFilter}}) are always collected, but only 
those that also match {{lookupFilter}} have their edges followed. It applies at 
every level, including the root. When absent, behaviour is unchanged.
{noformat}
{!graph from=ParentGUID to=contentid traversalFilter=IsVisible:true 
lookupFilter=DocumentType:4}<root query>
{noformat}
The filter's DocSet is computed once per request via the filterCache, and the 
collector checks it before extracting edges. {{lookupFilter}} is part of 
{{GraphQuery}}'s {{equals}}/{{hashCode}}, so cache keys stay correct. It also 
works for the JSON Facet {{graph}} domain, which goes through 
{{GraphQueryParser}}.

h3. Benchmark
Synthetic 1M-doc file-system index (80k folders, 920k files, ~11.5 files per 
folder, depth up to 15), JDK 21, 4 GB heap, rows=0, queryResultCache disabled. 
Median QTime in ms; same build with and without the param, interleaved in the 
same JVMs:
||Visible subtree size||Without lookupFilter||With 
lookupFilter=DocumentType:4||Speedup||
|~100|2.6|1.3|1.4x|
|~1k|7.6|2.3|2.4x|
|~10k|53|7.8|6.0x|
|~50k|174|24|7.0x|
|~100k|349|42|8.0x|
|~250k|656|73|8.8x|
|whole tree (829k)|3,038|298|10.1x|
All 5,760 queries returned identical, independently verified numFound. Without 
the param, performance matches the unpatched build within run-to-run noise.

h3. Back-compat
New optional param; no change when it is absent. {{GraphPointsCollector}}'s 
public 3-arg constructor is kept.

Related: SOLR-16202 (a filter on which documents are *returned*; this one 
controls which are *expanded*).


> Add lookupFilter to the graph query parser to skip edge lookups for nodes 
> that can't have children
> --------------------------------------------------------------------------------------------------
>
>                 Key: SOLR-18664
>                 URL: https://issues.apache.org/jira/browse/SOLR-18664
>             Project: Solr
>          Issue Type: Improvement
>          Components: query parsers
>            Reporter: Rahul Goswami
>            Assignee: Rahul Goswami
>            Priority: Major
>              Labels: pull-request-available
>          Time Spent: 10m
>  Remaining Estimate: 0h
>
> h3. Problem
> The graph query parser does a breadth-first traversal: at each hop it reads 
> the {{to}} field of every collected document and adds those values to the 
> next hop's {{from IN (...)}} frontier query. There is no way to say "collect 
> this node, but don't expand it".
> A common case is a file-system hierarchy, where every document (file or 
> folder) has its own id in {{id}} and its parent's id in {{parentId}}:
> {noformat}
> q={!graph from=parentId to=id returnRoot=true 
> traversalFilter=name:prefix*}<root folder query>
> {noformat}
> Only folders ({{docType:folder}}) can have children, but every file's 
> ({{docType:file}}) {{id}} also becomes a term in the next hop's query. Each 
> such term costs a docValues read, a hash insert and a terms-dictionary seek 
> per segment, and can never match. Files usually far outnumber folders, so 
> most of the frontier is wasted work.
> * {{traversalFilter=docType:folder}} doesn't help: it restricts which 
> documents are collected, so files would be dropped from the results.
> * The existing leaf-node optimization ({{resolveLeafNodes()}}) only skips 
> documents with *no value* in the {{to}} field. Here every document has an 
> {{id}}, so it never applies.
> h3. Proposal
> Add an optional {{lookupFilter}} local param. Documents reached by the 
> traversal (and matching {{traversalFilter}}) are always collected, but only 
> those that also match {{lookupFilter}} have their edges followed. It applies 
> at every level, including the root. When absent, behaviour is unchanged.
> {noformat}
> {!graph from=parentId to=id traversalFilter=name:prefix* 
> lookupFilter=docType:folder}<root query>
> {noformat}
> The filter's DocSet is computed once per request via the filterCache, and the 
> collector checks it before extracting edges. {{lookupFilter}} is part of 
> {{GraphQuery}}'s {{equals}}/{{hashCode}}, so cache keys stay correct. It also 
> works for the JSON Facet {{graph}} domain, which goes through 
> {{GraphQueryParser}}.
> h3. Benchmark
> Synthetic 1M-doc file-system index (80k folders, 920k files, ~11.5 files per 
> folder, depth up to 15), JDK 21, 4 GB heap, rows=0, queryResultCache 
> disabled. Median QTime in ms; same build with and without the param, 
> interleaved in the same JVMs:
> ||Visible subtree size||Without lookupFilter||With 
> lookupFilter=docType:folder||Speedup||
> |~100|2.6|1.3|1.4x|
> |~1k|7.6|2.3|2.4x|
> |~10k|53|7.8|6.0x|
> |~50k|174|24|7.0x|
> |~100k|349|42|8.0x|
> |~250k|656|73|8.8x|
> |whole tree (829k)|3,038|298|10.1x|
> All 5,760 queries returned identical, independently verified numFound. 
> Without the param, performance matches the unpatched build within run-to-run 
> noise.
> h3. Back-compat
> New optional param; no change when it is absent. {{GraphPointsCollector}}'s 
> public 3-arg constructor is kept.
> Related: SOLR-16202 (a filter on which documents are *returned*; this one 
> controls which are *expanded*).



--
This message was sent by Atlassian Jira
(v10.3.26#10030026)

---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to