Return-Path: X-Original-To: apmail-lucene-commits-archive@www.apache.org Delivered-To: apmail-lucene-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 76065CB10 for ; Tue, 29 May 2012 20:14:24 +0000 (UTC) Received: (qmail 38769 invoked by uid 500); 29 May 2012 20:14:24 -0000 Mailing-List: contact commits-help@lucene.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@lucene.apache.org Delivered-To: mailing list commits@lucene.apache.org Received: (qmail 38762 invoked by uid 99); 29 May 2012 20:14:24 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 29 May 2012 20:14:24 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 29 May 2012 20:14:22 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id 208962388978; Tue, 29 May 2012 20:14:02 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1343955 - in /lucene/dev/branches/branch_4x: ./ lucene/ lucene/core/ lucene/core/src/java/org/apache/lucene/codecs/ lucene/core/src/java/org/apache/lucene/index/ lucene/core/src/test/org/apache/lucene/index/ Date: Tue, 29 May 2012 20:14:01 -0000 To: commits@lucene.apache.org From: mikemccand@apache.org X-Mailer: svnmailer-1.0.8-patched Message-Id: <20120529201402.208962388978@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: mikemccand Date: Tue May 29 20:14:00 2012 New Revision: 1343955 URL: http://svn.apache.org/viewvc?rev=1343955&view=rev Log: LUCENE-2357 (4.x backport): use packed ints to hold docID remapping during merging, to reduce transient RAM usage Modified: lucene/dev/branches/branch_4x/ (props changed) lucene/dev/branches/branch_4x/lucene/ (props changed) lucene/dev/branches/branch_4x/lucene/CHANGES.txt (contents, props changed) lucene/dev/branches/branch_4x/lucene/core/ (props changed) lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/codecs/MappingMultiDocsAndPositionsEnum.java lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/codecs/MappingMultiDocsEnum.java lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/IndexWriter.java lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/MergeState.java lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/MultiDocValues.java lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/SegmentMerger.java lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/SortedBytesMergeUtils.java lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/index/TestSegmentMerger.java Modified: lucene/dev/branches/branch_4x/lucene/CHANGES.txt URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/CHANGES.txt?rev=1343955&r1=1343954&r2=1343955&view=diff ============================================================================== --- lucene/dev/branches/branch_4x/lucene/CHANGES.txt (original) +++ lucene/dev/branches/branch_4x/lucene/CHANGES.txt Tue May 29 20:14:00 2012 @@ -932,6 +932,9 @@ Optimizations performance; add float acceptableOverheadRatio to getWriter and getMutable API to give packed ints freedom to pick faster implementations (Adrien Grand via Mike McCandless) + +* LUCENE-2357: Reduce transient RAM usage when merging segments in + IndexWriter. (Adrien Grand via Mike McCandless) Bug fixes Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/codecs/MappingMultiDocsAndPositionsEnum.java URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/codecs/MappingMultiDocsAndPositionsEnum.java?rev=1343955&r1=1343954&r2=1343955&view=diff ============================================================================== --- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/codecs/MappingMultiDocsAndPositionsEnum.java (original) +++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/codecs/MappingMultiDocsAndPositionsEnum.java Tue May 29 20:14:00 2012 @@ -36,7 +36,7 @@ public final class MappingMultiDocsAndPo private MultiDocsAndPositionsEnum.EnumWithSlice[] subs; int numSubs; int upto; - int[] currentMap; + MergeState.DocMap currentMap; DocsAndPositionsEnum current; int currentBase; int doc = -1; @@ -94,12 +94,10 @@ public final class MappingMultiDocsAndPo int doc = current.nextDoc(); if (doc != NO_MORE_DOCS) { - if (currentMap != null) { - // compact deletions - doc = currentMap[doc]; - if (doc == -1) { - continue; - } + // compact deletions + doc = currentMap.get(doc); + if (doc == -1) { + continue; } return this.doc = currentBase + doc; } else { Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/codecs/MappingMultiDocsEnum.java URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/codecs/MappingMultiDocsEnum.java?rev=1343955&r1=1343954&r2=1343955&view=diff ============================================================================== --- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/codecs/MappingMultiDocsEnum.java (original) +++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/codecs/MappingMultiDocsEnum.java Tue May 29 20:14:00 2012 @@ -35,7 +35,7 @@ public final class MappingMultiDocsEnum private MultiDocsEnum.EnumWithSlice[] subs; int numSubs; int upto; - int[] currentMap; + MergeState.DocMap currentMap; DocsEnum current; int currentBase; int doc = -1; @@ -88,18 +88,16 @@ public final class MappingMultiDocsEnum current = subs[upto].docsEnum; currentBase = mergeState.docBase[reader]; currentMap = mergeState.docMaps[reader]; - assert currentMap == null || currentMap.length == subs[upto].slice.length: "readerIndex=" + reader + " subs.len=" + subs.length + " len1=" + currentMap.length + " vs " + subs[upto].slice.length; + assert currentMap.maxDoc() == subs[upto].slice.length: "readerIndex=" + reader + " subs.len=" + subs.length + " len1=" + currentMap.maxDoc() + " vs " + subs[upto].slice.length; } } int doc = current.nextDoc(); if (doc != NO_MORE_DOCS) { - if (currentMap != null) { - // compact deletions - doc = currentMap[doc]; - if (doc == -1) { - continue; - } + // compact deletions + doc = currentMap.get(doc); + if (doc == -1) { + continue; } return this.doc = currentBase + doc; } else { Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/IndexWriter.java URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/IndexWriter.java?rev=1343955&r1=1343954&r2=1343955&view=diff ============================================================================== --- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/IndexWriter.java (original) +++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/IndexWriter.java Tue May 29 20:14:00 2012 @@ -3483,7 +3483,7 @@ public class IndexWriter implements Clos merge.readers.add(reader); assert delCount <= info.info.getDocCount(): "delCount=" + delCount + " info.docCount=" + info.info.getDocCount() + " rld.pendingDeleteCount=" + rld.getPendingDeleteCount() + " info.getDelCount()=" + info.getDelCount(); if (delCount < info.info.getDocCount()) { - merger.add(reader, liveDocs); + merger.add(reader, liveDocs, delCount); } segUpto++; } Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/MergeState.java URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/MergeState.java?rev=1343955&r1=1343954&r2=1343955&view=diff ============================================================================== --- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/MergeState.java (original) +++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/MergeState.java Tue May 29 20:14:00 2012 @@ -19,11 +19,12 @@ package org.apache.lucene.index; import java.util.List; -import org.apache.lucene.index.PayloadProcessorProvider.ReaderPayloadProcessor; import org.apache.lucene.index.PayloadProcessorProvider.PayloadProcessor; +import org.apache.lucene.index.PayloadProcessorProvider.ReaderPayloadProcessor; import org.apache.lucene.store.Directory; import org.apache.lucene.util.Bits; import org.apache.lucene.util.InfoStream; +import org.apache.lucene.util.packed.PackedInts; /** Holds common state used during segment merging * @@ -33,17 +34,171 @@ public class MergeState { public static class IndexReaderAndLiveDocs { public final AtomicReader reader; public final Bits liveDocs; + public final int numDeletedDocs; - public IndexReaderAndLiveDocs(AtomicReader reader, Bits liveDocs) { + public IndexReaderAndLiveDocs(AtomicReader reader, Bits liveDocs, int numDeletedDocs) { this.reader = reader; this.liveDocs = liveDocs; + this.numDeletedDocs = numDeletedDocs; + } + } + + public static abstract class DocMap { + private final Bits liveDocs; + + protected DocMap(Bits liveDocs) { + this.liveDocs = liveDocs; + } + + public static DocMap build(IndexReaderAndLiveDocs reader) { + final int maxDoc = reader.reader.maxDoc(); + final int numDeletes = reader.numDeletedDocs; + final int numDocs = maxDoc - numDeletes; + assert reader.liveDocs != null || numDeletes == 0; + if (numDeletes == 0) { + return new NoDelDocMap(maxDoc); + } else if (numDeletes < numDocs) { + return buildDelCountDocmap(maxDoc, numDeletes, reader.liveDocs, PackedInts.FAST); + } else { + return buildDirectDocMap(maxDoc, numDocs, reader.liveDocs, PackedInts.FAST); + } + } + + static DocMap buildDelCountDocmap(int maxDoc, int numDeletes, Bits liveDocs, float acceptableOverheadRatio) { + PackedInts.Mutable numDeletesSoFar = PackedInts.getMutable(maxDoc, + PackedInts.bitsRequired(numDeletes), acceptableOverheadRatio); + int del = 0; + for (int i = 0; i < maxDoc; ++i) { + if (!liveDocs.get(i)) { + ++del; + } + numDeletesSoFar.set(i, del); + } + assert del == numDeletes : "del=" + del + ", numdeletes=" + numDeletes; + return new DelCountDocMap(liveDocs, numDeletesSoFar); + } + + static DocMap buildDirectDocMap(int maxDoc, int numDocs, Bits liveDocs, float acceptableOverheadRatio) { + PackedInts.Mutable docIds = PackedInts.getMutable(maxDoc, + PackedInts.bitsRequired(Math.max(0, numDocs - 1)), acceptableOverheadRatio); + int del = 0; + for (int i = 0; i < maxDoc; ++i) { + if (liveDocs.get(i)) { + docIds.set(i, i - del); + } else { + ++del; + } + } + assert numDocs + del == maxDoc : "maxDoc=" + maxDoc + ", del=" + del + ", numDocs=" + numDocs; + return new DirectDocMap(liveDocs, docIds, del); + } + + public int get(int docId) { + if (liveDocs == null || liveDocs.get(docId)) { + return remap(docId); + } else { + return -1; + } + } + + public abstract int remap(int docId); + + public abstract int maxDoc(); + + public final int numDocs() { + return maxDoc() - numDeletedDocs(); + } + + public abstract int numDeletedDocs(); + + public boolean hasDeletions() { + return numDeletedDocs() > 0; + } + + } + + private static class NoDelDocMap extends DocMap { + + private final int maxDoc; + + private NoDelDocMap(int maxDoc) { + super(null); + this.maxDoc = maxDoc; + } + + @Override + public int remap(int docId) { + return docId; + } + + @Override + public int maxDoc() { + return maxDoc; + } + + @Override + public int numDeletedDocs() { + return 0; + } + } + + private static class DirectDocMap extends DocMap { + + private final PackedInts.Mutable docIds; + private final int numDeletedDocs; + + private DirectDocMap(Bits liveDocs, PackedInts.Mutable docIds, int numDeletedDocs) { + super(liveDocs); + this.docIds = docIds; + this.numDeletedDocs = numDeletedDocs; + } + + @Override + public int remap(int docId) { + return (int) docIds.get(docId); + } + + @Override + public int maxDoc() { + return docIds.size(); + } + + @Override + public int numDeletedDocs() { + return numDeletedDocs; + } + } + + private static class DelCountDocMap extends DocMap { + + private final PackedInts.Mutable numDeletesSoFar; + + private DelCountDocMap(Bits liveDocs, PackedInts.Mutable numDeletesSoFar) { + super(liveDocs); + this.numDeletesSoFar = numDeletesSoFar; + } + + @Override + public int remap(int docId) { + return docId - (int) numDeletesSoFar.get(docId); + } + + @Override + public int maxDoc() { + return numDeletesSoFar.size(); + } + + @Override + public int numDeletedDocs() { + final int maxDoc = maxDoc(); + return (int) numDeletesSoFar.get(maxDoc - 1); } } public SegmentInfo segmentInfo; public FieldInfos fieldInfos; public List readers; // Readers & liveDocs being merged - public int[][] docMaps; // Maps docIDs around deletions + public DocMap[] docMaps; // Maps docIDs around deletions public int[] docBase; // New docID base per reader public CheckAbort checkAbort; public InfoStream infoStream; @@ -65,8 +220,8 @@ public class MergeState { public static class CheckAbort { private double workCount; - private MergePolicy.OneMerge merge; - private Directory dir; + private final MergePolicy.OneMerge merge; + private final Directory dir; public CheckAbort(MergePolicy.OneMerge merge, Directory dir) { this.merge = merge; this.dir = dir; Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/MultiDocValues.java URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/MultiDocValues.java?rev=1343955&r1=1343954&r2=1343955&view=diff ============================================================================== --- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/MultiDocValues.java (original) +++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/MultiDocValues.java Tue May 29 20:14:00 2012 @@ -322,7 +322,7 @@ public class MultiDocValues extends DocV final MergeContext ctx = SortedBytesMergeUtils.init(type, values, comp, globalNumDocs); List slices = SortedBytesMergeUtils.buildSlices( - docBases(), new int[values.length][], values, ctx); + docBases(), new MergeState.DocMap[values.length], values, ctx); RecordingBytesRefConsumer consumer = new RecordingBytesRefConsumer( type); final int maxOrd = SortedBytesMergeUtils.mergeRecords(ctx, consumer, Modified: lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/SegmentMerger.java URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/SegmentMerger.java?rev=1343955&r1=1343954&r2=1343955&view=diff ============================================================================== --- lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/SegmentMerger.java (original) +++ lucene/dev/branches/branch_4x/lucene/core/src/java/org/apache/lucene/index/SegmentMerger.java Tue May 29 20:14:00 2012 @@ -80,7 +80,7 @@ final class SegmentMerger { new ReaderUtil.Gather(reader) { @Override protected void add(int base, AtomicReader r) { - mergeState.readers.add(new MergeState.IndexReaderAndLiveDocs(r, r.getLiveDocs())); + mergeState.readers.add(new MergeState.IndexReaderAndLiveDocs(r, r.getLiveDocs(), r.numDeletedDocs())); } }.run(); } catch (IOException ioe) { @@ -89,8 +89,8 @@ final class SegmentMerger { } } - final void add(SegmentReader reader, Bits liveDocs) { - mergeState.readers.add(new MergeState.IndexReaderAndLiveDocs(reader, liveDocs)); + final void add(SegmentReader reader, Bits liveDocs, int delCount) { + mergeState.readers.add(new MergeState.IndexReaderAndLiveDocs(reader, liveDocs, delCount)); } /** @@ -287,7 +287,7 @@ final class SegmentMerger { final int numReaders = mergeState.readers.size(); // Remap docIDs - mergeState.docMaps = new int[numReaders][]; + mergeState.docMaps = new MergeState.DocMap[numReaders]; mergeState.docBase = new int[numReaders]; mergeState.readerPayloadProcessor = new PayloadProcessorProvider.ReaderPayloadProcessor[numReaders]; mergeState.currentPayloadProcessor = new PayloadProcessorProvider.PayloadProcessor[numReaders]; @@ -300,30 +300,9 @@ final class SegmentMerger { final MergeState.IndexReaderAndLiveDocs reader = mergeState.readers.get(i); mergeState.docBase[i] = docBase; - final int maxDoc = reader.reader.maxDoc(); - final int docCount; - final Bits liveDocs = reader.liveDocs; - final int[] docMap; - if (liveDocs != null) { - int delCount = 0; - docMap = new int[maxDoc]; - int newDocID = 0; - for(int j=0;j buildSlices(int[] docBases, int[][] docMaps, + public static List buildSlices( + int[] docBases, MergeState.DocMap[] docMaps, DocValues[] docValues, MergeContext ctx) throws IOException { final List slices = new ArrayList(); for (int i = 0; i < docValues.length; i++) { @@ -111,15 +112,15 @@ public final class SortedBytesMergeUtils * mapping in docIDToRelativeOrd. After the merge SortedSourceSlice#ordMapping * contains the new global ordinals for the relative index. */ - private static void createOrdMapping(int[] docBases, int[][] docMaps, + private static void createOrdMapping(int[] docBases, MergeState.DocMap[] docMaps, SortedSourceSlice currentSlice) { final int readerIdx = currentSlice.readerIdx; - final int[] currentDocMap = docMaps[readerIdx]; + final MergeState.DocMap currentDocMap = docMaps[readerIdx]; final int docBase = currentSlice.docToOrdStart; assert docBase == docBases[readerIdx]; - if (currentDocMap != null) { // we have deletes - for (int i = 0; i < currentDocMap.length; i++) { - final int doc = currentDocMap[i]; + if (currentDocMap != null && currentDocMap.hasDeletions()) { // we have deletes + for (int i = 0; i < currentDocMap.maxDoc(); i++) { + final int doc = currentDocMap.get(i); if (doc != -1) { // not deleted final int ord = currentSlice.source.ord(i); // collect ords strictly // increasing Modified: lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/index/TestSegmentMerger.java URL: http://svn.apache.org/viewvc/lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/index/TestSegmentMerger.java?rev=1343955&r1=1343954&r2=1343955&view=diff ============================================================================== --- lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/index/TestSegmentMerger.java (original) +++ lucene/dev/branches/branch_4x/lucene/core/src/test/org/apache/lucene/index/TestSegmentMerger.java Tue May 29 20:14:00 2012 @@ -25,9 +25,11 @@ import org.apache.lucene.search.DocIdSet import org.apache.lucene.store.Directory; import org.apache.lucene.util.BytesRef; import org.apache.lucene.util.Constants; +import org.apache.lucene.util.FixedBitSet; import org.apache.lucene.util.InfoStream; import org.apache.lucene.util.LuceneTestCase; import org.apache.lucene.util._TestUtil; +import org.apache.lucene.util.packed.PackedInts; public class TestSegmentMerger extends LuceneTestCase { @@ -139,4 +141,41 @@ public class TestSegmentMerger extends L TestSegmentReader.checkNorms(mergedReader); mergedReader.close(); } + + private static boolean equals(MergeState.DocMap map1, MergeState.DocMap map2) { + if (map1.maxDoc() != map2.maxDoc()) { + return false; + } + for (int i = 0; i < map1.maxDoc(); ++i) { + if (map1.get(i) != map2.get(i)) { + return false; + } + } + return true; + } + + public void testBuildDocMap() { + final int maxDoc = 128; + final FixedBitSet liveDocs = new FixedBitSet(maxDoc); + + MergeState.DocMap docMap1 = MergeState.DocMap.buildDelCountDocmap(maxDoc, maxDoc, liveDocs, PackedInts.COMPACT); + MergeState.DocMap docMap2 = MergeState.DocMap.buildDirectDocMap(maxDoc, 0, liveDocs, PackedInts.COMPACT); + assertTrue(equals(docMap1, docMap2)); + + liveDocs.set(1); + for (int i = 7; i < 79; ++i) { + liveDocs.set(i); + } + liveDocs.set(80); + liveDocs.set(88); + int numDocs = liveDocs.cardinality(); + docMap1 = MergeState.DocMap.buildDelCountDocmap(maxDoc, maxDoc - numDocs, liveDocs, PackedInts.COMPACT); + docMap2 = MergeState.DocMap.buildDirectDocMap(maxDoc, numDocs, liveDocs, PackedInts.COMPACT); + assertTrue(equals(docMap1, docMap2)); + + liveDocs.set(0, maxDoc); + docMap1 = MergeState.DocMap.buildDelCountDocmap(maxDoc, 0, liveDocs, PackedInts.COMPACT); + docMap2 = MergeState.DocMap.buildDirectDocMap(maxDoc, maxDoc, liveDocs, PackedInts.COMPACT); + assertTrue(equals(docMap1, docMap2)); + } }