You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Grant Ingersoll (JIRA)" <ji...@apache.org> on 2009/12/07 15:33:18 UTC
[jira] Created: (LUCENE-2127) Improved large result handling
Improved large result handling
------------------------------
Key: LUCENE-2127
URL: https://issues.apache.org/jira/browse/LUCENE-2127
Project: Lucene - Java
Issue Type: New Feature
Reporter: Grant Ingersoll
Priority: Minor
Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Jason Rutherglen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12847146#action_12847146 ]
Jason Rutherglen commented on LUCENE-2127:
------------------------------------------
What's the status of this one? I'm qausi interested in getting it into Solr.
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
> Attachments: LUCENE-2127.patch, LUCENE-2127.patch
>
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Grant Ingersoll (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12797617#action_12797617 ]
Grant Ingersoll commented on LUCENE-2127:
-----------------------------------------
bq. The benchmark code has jira table output. It might help to make the results more readable.
Huh?
bq. It doesn't support sort queries?
Not yet, see discussion earlier.
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
> Attachments: LUCENE-2127.patch
>
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Jason Rutherglen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12797490#action_12797490 ]
Jason Rutherglen commented on LUCENE-2127:
------------------------------------------
The benchmark code has jira table output. It might help to make the results more readable.
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
> Attachments: LUCENE-2127.patch
>
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Jason Rutherglen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12797499#action_12797499 ]
Jason Rutherglen commented on LUCENE-2127:
------------------------------------------
There's a bunch of formatting changes in the patch making it slightly hard to parse. It doesn't support sort queries?
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
> Attachments: LUCENE-2127.patch
>
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Michael McCandless (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12797157#action_12797157 ]
Michael McCandless commented on LUCENE-2127:
--------------------------------------------
bq. It's not fixed.
Ahh OK. We could presumably improve the FieldComparator impls to grow-on-demand as well...
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Michael McCandless (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12797130#action_12797130 ]
Michael McCandless commented on LUCENE-2127:
--------------------------------------------
bq. I was just thinking of an array of ScoreDocs. I'm writing the benchmark code right now. With this approach, though, it seems like the FieldComparator doesn't quite work, b/c you have to pass in numHits, which then goes and allocates another array. Seems like it would need to be modified to take in an already filled array.
A fixed array of ScoreDocs should work fine? But you do need to tell FieldComparator up front the biggest it will be, eg 20K in my example above (when you are intending to only return 10K in the end). You then refer to the slots in your ScoreDoc array when interacting w/ the comparator... FieldComparator needs to allocate a separate array to track whatever its internal values are, to do the comparisons.
Fixing benchmark to allow for custom collector sounds great!
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Grant Ingersoll (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12799261#action_12799261 ]
Grant Ingersoll commented on LUCENE-2127:
-----------------------------------------
So, my patch seems to be faster than ordered collectors and about the same (or a little slower) as unordered collectors. At least that was my observation running collector.alg, but there still might be room for improvement.
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
> Attachments: LUCENE-2127.patch, LUCENE-2127.patch
>
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Jason Rutherglen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12797679#action_12797679 ]
Jason Rutherglen commented on LUCENE-2127:
------------------------------------------
bq. jira table output.
Mike's Python script which compares the results of two benchmark runs and outputs in jira format.
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
> Attachments: LUCENE-2127.patch, LUCENE-2127.patch
>
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Grant Ingersoll (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12796971#action_12796971 ]
Grant Ingersoll commented on LUCENE-2127:
-----------------------------------------
Very cool, Aaron! I've kicked around that idea, but never implemented. That actually solves a slightly different problem that what I'm working on with this one, but is definitely a welcome addition, too. Please feel free to attach or open a new issue.
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Grant Ingersoll (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12796804#action_12796804 ]
Grant Ingersoll commented on LUCENE-2127:
-----------------------------------------
I've started work on this by looking at a collector that does sorting after all the results are collected. Now, I could simply sort on an array of ScoreDocs, but I'd really like to be able to take advantage of the existing Sort/SortField/FieldComparator stuff, but it seems really geared towards using a PriorityQueue and managing an internal values array, whereas in my case I already have the array allocated that I want to manage (well, for the most part.)
The obvious choice is to punt and just provide score and doc id sorting, but wanted to hear other people's thoughts
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Otis Gospodnetic (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12797776#action_12797776 ]
Otis Gospodnetic commented on LUCENE-2127:
------------------------------------------
+1 for Aaron's patch in a separate issue, too.
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
> Attachments: LUCENE-2127.patch, LUCENE-2127.patch
>
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Assigned: (LUCENE-2127) Improved large result handling
Posted by "Grant Ingersoll (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Grant Ingersoll reassigned LUCENE-2127:
---------------------------------------
Assignee: Grant Ingersoll
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Michael McCandless (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12797095#action_12797095 ]
Michael McCandless commented on LUCENE-2127:
--------------------------------------------
I think you should be able to use FieldComparator for the "large queue".
If your "large queue" is a list/array, then it has slots, and you just reference those slots when asking FieldComparator to compare.
The only difference from the FieldComparator's standpoint is you are doing far fewer compare calls as-you-go, then periodically you have a big burst of compares (the "selection algorithm", which should be implementable on FieldComparator) to find a new rough bottom.
But... have you thought about theoretical cost of "true pqueue" vs "approximate pqueue"? I think in the worst case, where results are returned in precisely reverse sort order, so that you always fully turnover the queue, is tricky.
Say your queue size is 10K, but you tolerate say 20 K until pruning. With worst case, every 10K hits you will have to re-select to dump the 10K worst. So cost is O(N * M), where M = queue size and N = total number of hits, though with a smallish 1/10K constant.
With true pqueue, every hit pays log(M) price, so total cost is O(N * log(M)).
But actually that 1/10K constant = 1/M, and so I think the approximate PQ works out to O(N) cost, which is in fact much cheaper. I think?
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Grant Ingersoll (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12848795#action_12848795 ]
Grant Ingersoll commented on LUCENE-2127:
-----------------------------------------
Hey Jason,
My tests are inconclusive on the patch posted above. LUCENE-2215, however, seems promising and good to get into Solr as well.
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
> Attachments: LUCENE-2127.patch, LUCENE-2127.patch
>
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Aaron McCurry (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12796898#action_12796898 ]
Aaron McCurry commented on LUCENE-2127:
---------------------------------------
I have implemented a paging collector for 2.4 and I am porting it to 3.0 that allows for users to page to any depth in their results.
Depending on how you are using lucene it may work a little bit differently but essentially it does an initial search and collects X number of documents. Once that page of results is exhausted, it re-searches feeding the last docid and score into the next page of collected documents. Assuming that the documents are collected in order, if the score of the current docid being collected is less than the previous passes score then it may be collected. If the scores are equal, then compare the docids, and if the current docid being scored is greater than the previous docid, then it may be collected.
Basically it throws out the previous page of results.
This can be a little bit difficult to explain, but using this technique and with our internal collector pages being set to 50,000 scoredocs we have a production system that allows users to page to the last page of their results no matter how large the results, and we have results in the 10s of millions at times.
I can provide my 2.4 collector, and/or my 3.0 (once complete), this solution may solve this issue.
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Adam Heinz (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12800965#action_12800965 ]
Adam Heinz commented on LUCENE-2127:
------------------------------------
Entered a placeholder issue for Aaron's patch: LUCENE-2215
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
> Attachments: LUCENE-2127.patch, LUCENE-2127.patch
>
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Grant Ingersoll (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12797112#action_12797112 ]
Grant Ingersoll commented on LUCENE-2127:
-----------------------------------------
bq. If your "large queue" is a list/array, then it has slots, and you just reference those slots when asking FieldComparator to compare.
I was just thinking of an array of ScoreDocs. I'm writing the benchmark code right now. With this approach, though, it seems like the FieldComparator doesn't quite work, b/c you have to pass in numHits, which then goes and allocates another array. Seems like it would need to be modified to take in an already filled array.
bq. But... have you thought about theoretical cost of "true pqueue" vs "approximate pqueue"? I think in the worst case, where results are returned in precisely reverse sort order, so that you always fully turnover the queue, is tricky.
Yes, but haven't looked at implementing yet.
bq. But actually that 1/10K constant = 1/M, and so I think the approximate PQ works out to O(N) cost, which is in fact much cheaper. I think?
Sounds right to me. Once we have a benchmarker in place that allows for replacement of the Collector, we can try all of this fun stuff out. We also need a collection where we can return large numbers of results with scores (in other words, not just MatchAllDocsQuery, although that still might be valid)
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Jason Rutherglen (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12796823#action_12796823 ]
Jason Rutherglen commented on LUCENE-2127:
------------------------------------------
Grant,
This issue could be useful and I may be able to test out the
resulting patches.
What's the specific problem with the
Sort/SortField/FieldComparator apparatus? We don't want to
generate new objects using DocComparator.value(int slot) and
store these in FieldDoc? We probably don't want to excessively
generate objects. Maybe we can figure out a way to access to the
primitive array and compare values which seems doable?
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Grant Ingersoll (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12797134#action_12797134 ]
Grant Ingersoll commented on LUCENE-2127:
-----------------------------------------
bq. A fixed array of ScoreDocs should work fine? But you do need to tell FieldComparator up front the biggest it will be
It's not fixed. I want to experiment with the idea of collecting all the results and then sorting, based on the discussion in the link above. I'm seeing more and more cases, esp. for heavy machine learning/post processing apps, where the app will retrieve 1M+ docs per query.
Thus, I modified ArrayUtils to have a grow method that takes in a ScoreDoc array, but can also pass in a preallocated array. I'm not convinced this is going to be better, but I think it's interesting to find out. Should have a patch today.
FWIW, I think you approximate PQ makes a lot of sense too.
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Updated: (LUCENE-2127) Improved large result handling
Posted by "Grant Ingersoll (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Grant Ingersoll updated LUCENE-2127:
------------------------------------
Attachment: LUCENE-2127.patch
OK, I think this has some legs, assuming I did everything right (especially the benchmarker stuff).
Here's what I did:
1. Added postCollect() method to Collector as an empty method
2. Hooked it into IndexSearcher, MultiSearcher and ParallelMultiSearcher. I'm not sure I have all of the search paths covered yet, but...
3. Hooked in the ability to specify the collector in benchmarker (see collector.alg)
4. Added a new LongToEnglishContentSource and QueryMaker to create pretty much infinitely scalable number of docs based off the English.java test util.
Prelim results (unvalidated) retrieving up to 1M records (out of 2M):
{quote}
------------> Report sum by Prefix (SearchCollector) and Round (4 about 4 out of 8000034)
Operation round coll runCnt recsPerRun rec/s elapsedSec avgUsedMem avgTotalMem
SearchCollector_10 0org.apache.lucene.search.PostCollectSortCollector 1 10 0.14 73.32 290,371,776 386,625,536
SearchCollector_10 - 1topDocOrdered - - 1 - - - 10 - - - 0.10 - - 98.37 - 449,582,048 - 588,189,696
SearchCollector_10 2org.apache.lucene.search.PostCollectSortCollector 1 10 0.14 71.47 964,864,512 1,016,311,808
SearchCollector_10 - 3topDocOrdered - - 1 - - - 10 - - - 0.10 - - 98.73 - 791,313,664 1,016,311,808
{quote}
Still lots to do, but wanted to put it up for people to look at and tell me what I'm doing wrong. I'd also love to hook in FieldComparator stuff. Even if we could have a wrapper that took in FieldComparator inside of a regular Comparator would be cool.
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
> Attachments: LUCENE-2127.patch
>
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-2127) Improved large result handling
Posted by "Grant Ingersoll (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12797163#action_12797163 ]
Grant Ingersoll commented on LUCENE-2127:
-----------------------------------------
Another issue w/ this "raw" collector is it sure would be nice if it could also be a TopDocsCollector, but that is so priority queue centric as well. I could extract a simple interface w/ just:
{code}
public TopDocs topDocs();
{code}
but that is currently marked final.
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Updated: (LUCENE-2127) Improved large result handling
Posted by "Grant Ingersoll (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-2127?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Grant Ingersoll updated LUCENE-2127:
------------------------------------
Attachment: LUCENE-2127.patch
Added a task to try out the specifics of different array sizes with the PostCollectSortCollector. Still looks pretty promising (collector-small.alg: 100,000 hits retrieved: TopDocs: 20.38 elapsed sec, PostCollect: 13.25 elapsed seconds), but needs more validation.
> Improved large result handling
> ------------------------------
>
> Key: LUCENE-2127
> URL: https://issues.apache.org/jira/browse/LUCENE-2127
> Project: Lucene - Java
> Issue Type: New Feature
> Reporter: Grant Ingersoll
> Assignee: Grant Ingersoll
> Priority: Minor
> Attachments: LUCENE-2127.patch, LUCENE-2127.patch
>
>
> Per http://search.lucidimagination.com/search/document/350c54fc90d257ed/lots_of_results#fbb84bd297d15dd5, it would be nice to offer some other Collectors that are better at handling really large number of results. This could be implemented in a variety of ways via Collectors. For instance, we could have a raw collector that does no sorting and just returns the ScoreDocs, or we could do as Mike suggests and have Collectors that have heuristics about memory tradeoffs and only heapify when appropriate.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org