You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Steven Tamm (JIRA)" <ji...@apache.org> on 2006/03/21 23:15:34 UTC
[jira] Created: (LUCENE-528) Optimization for
IndexWriter.addIndexes()
Optimization for IndexWriter.addIndexes()
-----------------------------------------
Key: LUCENE-528
URL: http://issues.apache.org/jira/browse/LUCENE-528
Project: Lucene - Java
Type: Improvement
Components: Index
Reporter: Steven Tamm
Priority: Minor
One big performance problem with IndexWriter.addIndexes() is that it has to optimize the index both before and after adding the segments. When you have a very large index, to which you are adding batches of small updates, these calls to optimize make using addIndexes() impossible. It makes parallel updates very frustrating.
Here is an optimized function that helps out by calling mergeSegments only on the newly added documents. It will try to avoid calling mergeSegments until the end, unless you're adding a lot of documents at once.
I also have an extensive unit test that verifies that this function works correctly if people are interested. I gave it a different name because it has very different performance characteristics which can make querying take longer.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Assigned: (LUCENE-528) Optimization for
IndexWriter.addIndexes()
Posted by "Otis Gospodnetic (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/LUCENE-528?page=all ]
Otis Gospodnetic reassigned LUCENE-528:
---------------------------------------
Assignee: Otis Gospodnetic
> Optimization for IndexWriter.addIndexes()
> -----------------------------------------
>
> Key: LUCENE-528
> URL: http://issues.apache.org/jira/browse/LUCENE-528
> Project: Lucene - Java
> Issue Type: Improvement
> Components: Index
> Reporter: Steven Tamm
> Assigned To: Otis Gospodnetic
> Priority: Minor
> Attachments: AddIndexes.patch
>
>
> One big performance problem with IndexWriter.addIndexes() is that it has to optimize the index both before and after adding the segments. When you have a very large index, to which you are adding batches of small updates, these calls to optimize make using addIndexes() impossible. It makes parallel updates very frustrating.
> Here is an optimized function that helps out by calling mergeSegments only on the newly added documents. It will try to avoid calling mergeSegments until the end, unless you're adding a lot of documents at once.
> I also have an extensive unit test that verifies that this function works correctly if people are interested. I gave it a different name because it has very different performance characteristics which can make querying take longer.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-528) Optimization for
IndexWriter.addIndexes()
Posted by "Yonik Seeley (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/LUCENE-528?page=comments#action_12443841 ]
Yonik Seeley commented on LUCENE-528:
-------------------------------------
I think you need to ensure that no segments from the source index "S" remain after the call, right?
> Optimization for IndexWriter.addIndexes()
> -----------------------------------------
>
> Key: LUCENE-528
> URL: http://issues.apache.org/jira/browse/LUCENE-528
> Project: Lucene - Java
> Issue Type: Improvement
> Components: Index
> Reporter: Steven Tamm
> Assigned To: Otis Gospodnetic
> Priority: Minor
> Attachments: AddIndexes.patch
>
>
> One big performance problem with IndexWriter.addIndexes() is that it has to optimize the index both before and after adding the segments. When you have a very large index, to which you are adding batches of small updates, these calls to optimize make using addIndexes() impossible. It makes parallel updates very frustrating.
> Here is an optimized function that helps out by calling mergeSegments only on the newly added documents. It will try to avoid calling mergeSegments until the end, unless you're adding a lot of documents at once.
> I also have an extensive unit test that verifies that this function works correctly if people are interested. I gave it a different name because it has very different performance characteristics which can make querying take longer.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Resolved: (LUCENE-528) Optimization for
IndexWriter.addIndexes()
Posted by "Yonik Seeley (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/LUCENE-528?page=all ]
Yonik Seeley resolved LUCENE-528.
---------------------------------
Resolution: Fixed
Assignee: Yonik Seeley (was: Otis Gospodnetic)
Thanks Ning, I just committed this.
Wish I had had it some time ago :-)
http://www.mail-archive.com/lucene-user@jakarta.apache.org/msg10758.html
> Optimization for IndexWriter.addIndexes()
> -----------------------------------------
>
> Key: LUCENE-528
> URL: http://issues.apache.org/jira/browse/LUCENE-528
> Project: Lucene - Java
> Issue Type: Improvement
> Components: Index
> Reporter: Steven Tamm
> Assigned To: Yonik Seeley
> Priority: Minor
> Attachments: AddIndexes.patch, AddIndexesNoOptimize.patch
>
>
> One big performance problem with IndexWriter.addIndexes() is that it has to optimize the index both before and after adding the segments. When you have a very large index, to which you are adding batches of small updates, these calls to optimize make using addIndexes() impossible. It makes parallel updates very frustrating.
> Here is an optimized function that helps out by calling mergeSegments only on the newly added documents. It will try to avoid calling mergeSegments until the end, unless you're adding a lot of documents at once.
> I also have an extensive unit test that verifies that this function works correctly if people are interested. I gave it a different name because it has very different performance characteristics which can make querying take longer.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Updated: (LUCENE-528) Optimization for
IndexWriter.addIndexes()
Posted by "Steven Tamm (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/LUCENE-528?page=all ]
Steven Tamm updated LUCENE-528:
-------------------------------
Attachment: AddIndexes.patch
> Optimization for IndexWriter.addIndexes()
> -----------------------------------------
>
> Key: LUCENE-528
> URL: http://issues.apache.org/jira/browse/LUCENE-528
> Project: Lucene - Java
> Type: Improvement
> Components: Index
> Reporter: Steven Tamm
> Priority: Minor
> Attachments: AddIndexes.patch
>
> One big performance problem with IndexWriter.addIndexes() is that it has to optimize the index both before and after adding the segments. When you have a very large index, to which you are adding batches of small updates, these calls to optimize make using addIndexes() impossible. It makes parallel updates very frustrating.
> Here is an optimized function that helps out by calling mergeSegments only on the newly added documents. It will try to avoid calling mergeSegments until the end, unless you're adding a lot of documents at once.
> I also have an extensive unit test that verifies that this function works correctly if people are interested. I gave it a different name because it has very different performance characteristics which can make querying take longer.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Updated: (LUCENE-528) Optimization for
IndexWriter.addIndexes()
Posted by "Ning Li (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/LUCENE-528?page=all ]
Ning Li updated LUCENE-528:
---------------------------
Attachment: AddIndexesNoOptimize.patch
This patch implements addIndexesNoOptimize() following the algorithm described earlier.
- The patch is based on the latest version from trunk.
- AddIndexesNoOptimize() is implemented. The algorithm description is included as comment and the code is commented.
- The patch includes a test called TestAddIndexesNoOptimize which covers all the code in addIndexesNoOptimize().
- maybeMergeSegments() was conservative and checked for more merges only when "upperBound * mergeFactor <= maxMergeDocs". Change it to check for more merges when "upperBound < maxMergeDocs".
- Minor changes in TestIndexWriterMergePolicy to better verify merge invariants.
- The patch passes all unit tests.
One more comment on the implementation:
- When we copy un-merged segments from S in step 4, ideally, we want to simply copy
those segments. However, directory does not support copy yet. In addition, source may
use compound file or not and target may use compound file or not. So we use
mergeSegments() to copy each segment, which may cause doc count to change
because deleted docs are garbage collected. That case is handled properly.
> Optimization for IndexWriter.addIndexes()
> -----------------------------------------
>
> Key: LUCENE-528
> URL: http://issues.apache.org/jira/browse/LUCENE-528
> Project: Lucene - Java
> Issue Type: Improvement
> Components: Index
> Reporter: Steven Tamm
> Assigned To: Otis Gospodnetic
> Priority: Minor
> Attachments: AddIndexes.patch, AddIndexesNoOptimize.patch
>
>
> One big performance problem with IndexWriter.addIndexes() is that it has to optimize the index both before and after adding the segments. When you have a very large index, to which you are adding batches of small updates, these calls to optimize make using addIndexes() impossible. It makes parallel updates very frustrating.
> Here is an optimized function that helps out by calling mergeSegments only on the newly added documents. It will try to avoid calling mergeSegments until the end, unless you're adding a lot of documents at once.
> I also have an extensive unit test that verifies that this function works correctly if people are interested. I gave it a different name because it has very different performance characteristics which can make querying take longer.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-528) Optimization for
IndexWriter.addIndexes()
Posted by "Ning Li (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/LUCENE-528?page=comments#action_12443723 ]
Ning Li commented on LUCENE-528:
--------------------------------
We want a robust algorithm for the version of addIndexes() which
does not call optimize().
The robustness can be expressed as the two invariants guaranteed
by the merge policy for adding documents (if mergeFactor M does not
change and segment doc count is not reaching maxMergeDocs):
B for maxBufferedDocs, f(n) defined as ceil(log_M(ceil(n/B)))
1: If i (left*) and i+1 (right*) are two consecutive segments of doc
counts x and y, then f(x) >= f(y).
2: The number of committed segments on the same level (f(n)) <= M.
References are at http://www.gossamer-threads.com/lists/lucene/java-dev/35147,
LUCENE-565 and LUCENE-672.
AddIndexes() can be viewed as adding a sequence of segments S to
a sequence of segments T. Segments in T follow the invariants but
segments in S may not since they could come from multiple indexes.
Here is the merge algorithm for addIndexes():
1. Flush ram segments.
2. Consider a combined sequence with segments from T followed
by segments from S (same as current addIndexes()).
3. Assume the highest level for segments in S is h. Call maybeMergeSegments(),
but instead of starting w/ lowerBound = -1 and upperBound = maxBufferedDocs,
start w/ lowerBound = -1 and upperBound = upperBound of level h.
After this, the invariants are guaranteed except for the last < M segments
whose levels <= h.
4. If the invariants hold for the last < M segments whose levels <= h, done.
Otherwise, simply merge those segments. If the merge results in
a segment of level <= h, done. Otherwise, it's of level h+1 and call
maybeMergeSegments() starting w/ upperBound = upperBound of level h+1.
Suggestions?
> Optimization for IndexWriter.addIndexes()
> -----------------------------------------
>
> Key: LUCENE-528
> URL: http://issues.apache.org/jira/browse/LUCENE-528
> Project: Lucene - Java
> Issue Type: Improvement
> Components: Index
> Reporter: Steven Tamm
> Assigned To: Otis Gospodnetic
> Priority: Minor
> Attachments: AddIndexes.patch
>
>
> One big performance problem with IndexWriter.addIndexes() is that it has to optimize the index both before and after adding the segments. When you have a very large index, to which you are adding batches of small updates, these calls to optimize make using addIndexes() impossible. It makes parallel updates very frustrating.
> Here is an optimized function that helps out by calling mergeSegments only on the newly added documents. It will try to avoid calling mergeSegments until the end, unless you're adding a lot of documents at once.
> I also have an extensive unit test that verifies that this function works correctly if people are interested. I gave it a different name because it has very different performance characteristics which can make querying take longer.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Updated: (LUCENE-528) Optimization for
IndexWriter.addIndexes()
Posted by "Ning Li (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/LUCENE-528?page=all ]
Ning Li updated LUCENE-528:
---------------------------
Lucene Fields: [Patch Available]
> Optimization for IndexWriter.addIndexes()
> -----------------------------------------
>
> Key: LUCENE-528
> URL: http://issues.apache.org/jira/browse/LUCENE-528
> Project: Lucene - Java
> Issue Type: Improvement
> Components: Index
> Reporter: Steven Tamm
> Assigned To: Otis Gospodnetic
> Priority: Minor
> Attachments: AddIndexes.patch, AddIndexesNoOptimize.patch
>
>
> One big performance problem with IndexWriter.addIndexes() is that it has to optimize the index both before and after adding the segments. When you have a very large index, to which you are adding batches of small updates, these calls to optimize make using addIndexes() impossible. It makes parallel updates very frustrating.
> Here is an optimized function that helps out by calling mergeSegments only on the newly added documents. It will try to avoid calling mergeSegments until the end, unless you're adding a lot of documents at once.
> I also have an extensive unit test that verifies that this function works correctly if people are interested. I gave it a different name because it has very different performance characteristics which can make querying take longer.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
[jira] Commented: (LUCENE-528) Optimization for
IndexWriter.addIndexes()
Posted by "Ning Li (JIRA)" <ji...@apache.org>.
[ http://issues.apache.org/jira/browse/LUCENE-528?page=comments#action_12428478 ]
Ning Li commented on LUCENE-528:
--------------------------------
In an email thread titled "LUCENE-528 and 565", I described a weakness of the proposed solution:
"I'm totally for a version of addIndexes() where optimize() is not always called. However, with the one proposed in the patch, we could end up with an index where: segment 0 has 1000 docs, 1 has 2000, 2 has 4000, 3 has 8000, etc. while Lucene desires the reverse. Or we could have a sandwich index where: segment 0 has 4000 docs, 1 has 100, 2 has 100, 3 has 4000. While neither of these will occur if you use addIndexesNoOpt() carefully, there should be a more robust merge policy."
Here is an alternative solution which merges segements so that the docCount of segment i is at least twice as big as the docCount of segment i+1. If we are willing to make it a bit more complicated, we can take merge factor into consideration.
public synchronized void addIndexesNoOpt(Directory[] dirs) throws IOException {
for (int i = 0; i < dirs.length; i++) {
SegmentInfos sis = new SegmentInfos(); // read infos from dir
sis.read(dirs[i]);
for (int j = 0; j < sis.size(); j++) {
segmentInfos.addElement(sis.info(j)); // add each info
}
}
int start = 0;
int docCountFromStart = docCount();
while (start < segmentInfos.size()) {
int end;
int docCountToMerge = 0;
if (docCountFromStart <= minMergeDocs) {
// if the total docCount of the remaining segments
// is lte minMergeDocs, merge all of them
end = segmentInfos.size() - 1;
docCountToMerge = docCountFromStart;
}
else {
// otherwise, merge some segments so that the docCount
// of these segments is at least half of the remaining
for (end = start; end < segmentInfos.size(); end++) {
docCountToMerge += segmentInfos.info(end).docCount;
if (docCountToMerge >= docCountFromStart / 2) {
break;
}
}
}
mergeSegments(start, end + 1);
start++;
docCountFromStart -= docCountToMerge;
}
}
> Optimization for IndexWriter.addIndexes()
> -----------------------------------------
>
> Key: LUCENE-528
> URL: http://issues.apache.org/jira/browse/LUCENE-528
> Project: Lucene - Java
> Issue Type: Improvement
> Components: Index
> Reporter: Steven Tamm
> Assigned To: Otis Gospodnetic
> Priority: Minor
> Attachments: AddIndexes.patch
>
>
> One big performance problem with IndexWriter.addIndexes() is that it has to optimize the index both before and after adding the segments. When you have a very large index, to which you are adding batches of small updates, these calls to optimize make using addIndexes() impossible. It makes parallel updates very frustrating.
> Here is an optimized function that helps out by calling mergeSegments only on the newly added documents. It will try to avoid calling mergeSegments until the end, unless you're adding a lot of documents at once.
> I also have an extensive unit test that verifies that this function works correctly if people are interested. I gave it a different name because it has very different performance characteristics which can make querying take longer.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org