| /* |
| * Copyright 2009-2012 by The Regents of the University of California |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * you may obtain a copy of the License from |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package edu.uci.ics.hyracks.storage.am.lsm.invertedindex.search; |
| |
| import java.nio.ByteBuffer; |
| import java.util.ArrayList; |
| import java.util.Collections; |
| |
| import edu.uci.ics.hyracks.api.context.IHyracksCommonContext; |
| import edu.uci.ics.hyracks.api.exceptions.HyracksDataException; |
| import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference; |
| import edu.uci.ics.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer; |
| import edu.uci.ics.hyracks.storage.am.common.api.IndexException; |
| import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator; |
| import edu.uci.ics.hyracks.storage.am.lsm.invertedindex.api.IInvertedIndex; |
| import edu.uci.ics.hyracks.storage.am.lsm.invertedindex.api.IInvertedListCursor; |
| import edu.uci.ics.hyracks.storage.am.lsm.invertedindex.ondisk.FixedSizeFrameTupleAccessor; |
| import edu.uci.ics.hyracks.storage.am.lsm.invertedindex.ondisk.FixedSizeTupleReference; |
| |
| // TODO: The merge procedure is rather confusing regarding cursor positions, hasNext() calls etc. |
| // Needs an overhaul some time. |
| public class InvertedListMerger { |
| |
| protected final MultiComparator invListCmp; |
| protected SearchResult prevSearchResult; |
| protected SearchResult newSearchResult; |
| |
| public InvertedListMerger(IHyracksCommonContext ctx, IInvertedIndex invIndex) { |
| this.invListCmp = MultiComparator.createIgnoreFieldLength(invIndex.getInvListCmpFactories()); |
| this.prevSearchResult = new SearchResult(invIndex.getInvListTypeTraits(), ctx); |
| this.newSearchResult = new SearchResult(prevSearchResult); |
| } |
| |
| public void merge(ArrayList<IInvertedListCursor> invListCursors, int occurrenceThreshold, int numPrefixLists, |
| SearchResult searchResult) throws HyracksDataException, IndexException { |
| Collections.sort(invListCursors); |
| int numInvLists = invListCursors.size(); |
| SearchResult result = null; |
| for (int i = 0; i < numInvLists; i++) { |
| SearchResult swapTemp = prevSearchResult; |
| prevSearchResult = newSearchResult; |
| newSearchResult = swapTemp; |
| newSearchResult.reset(); |
| if (i + 1 != numInvLists) { |
| // Use temporary search results when not merging last list. |
| result = newSearchResult; |
| } else { |
| // When merging the last list, append results to the final search result. |
| result = searchResult; |
| } |
| IInvertedListCursor invListCursor = invListCursors.get(i); |
| invListCursor.pinPages(); |
| if (i < numPrefixLists) { |
| // Merge prefix list. |
| mergePrefixList(invListCursor, prevSearchResult, result); |
| } else { |
| // Merge suffix list. |
| int numInvListElements = invListCursor.size(); |
| int currentNumResults = prevSearchResult.getNumResults(); |
| // Should we binary search the next list or should we sort-merge it? |
| if (currentNumResults * Math.log(numInvListElements) < currentNumResults + numInvListElements) { |
| mergeSuffixListProbe(invListCursor, prevSearchResult, result, i, numInvLists, |
| occurrenceThreshold); |
| } else { |
| mergeSuffixListScan(invListCursor, prevSearchResult, result, i, numInvLists, |
| occurrenceThreshold); |
| } |
| } |
| invListCursor.unpinPages(); |
| } |
| } |
| |
| protected void mergeSuffixListProbe(IInvertedListCursor invListCursor, SearchResult prevSearchResult, |
| SearchResult newSearchResult, int invListIx, int numInvLists, int occurrenceThreshold) |
| throws HyracksDataException, IndexException { |
| |
| int prevBufIdx = 0; |
| int maxPrevBufIdx = prevSearchResult.getCurrentBufferIndex(); |
| ByteBuffer prevCurrentBuffer = prevSearchResult.getBuffers().get(0); |
| |
| FixedSizeFrameTupleAccessor resultFrameTupleAcc = prevSearchResult.getAccessor(); |
| FixedSizeTupleReference resultTuple = prevSearchResult.getTuple(); |
| |
| int resultTidx = 0; |
| |
| resultFrameTupleAcc.reset(prevCurrentBuffer); |
| |
| while (resultTidx < resultFrameTupleAcc.getTupleCount()) { |
| |
| resultTuple.reset(prevCurrentBuffer.array(), resultFrameTupleAcc.getTupleStartOffset(resultTidx)); |
| int count = IntegerSerializerDeserializer.getInt(resultTuple.getFieldData(0), |
| resultTuple.getFieldStart(resultTuple.getFieldCount() - 1)); |
| |
| if (invListCursor.containsKey(resultTuple, invListCmp)) { |
| count++; |
| newSearchResult.append(resultTuple, count); |
| } else { |
| if (count + numInvLists - invListIx > occurrenceThreshold) { |
| newSearchResult.append(resultTuple, count); |
| } |
| } |
| |
| resultTidx++; |
| if (resultTidx >= resultFrameTupleAcc.getTupleCount()) { |
| prevBufIdx++; |
| if (prevBufIdx <= maxPrevBufIdx) { |
| prevCurrentBuffer = prevSearchResult.getBuffers().get(prevBufIdx); |
| resultFrameTupleAcc.reset(prevCurrentBuffer); |
| resultTidx = 0; |
| } |
| } |
| } |
| } |
| |
| protected void mergeSuffixListScan(IInvertedListCursor invListCursor, SearchResult prevSearchResult, |
| SearchResult newSearchResult, int invListIx, int numInvLists, int occurrenceThreshold) |
| throws HyracksDataException, IndexException { |
| |
| int prevBufIdx = 0; |
| int maxPrevBufIdx = prevSearchResult.getCurrentBufferIndex(); |
| ByteBuffer prevCurrentBuffer = prevSearchResult.getBuffers().get(0); |
| |
| FixedSizeFrameTupleAccessor resultFrameTupleAcc = prevSearchResult.getAccessor(); |
| FixedSizeTupleReference resultTuple = prevSearchResult.getTuple(); |
| |
| boolean advanceCursor = true; |
| boolean advancePrevResult = false; |
| int resultTidx = 0; |
| |
| resultFrameTupleAcc.reset(prevCurrentBuffer); |
| |
| int invListTidx = 0; |
| int invListNumTuples = invListCursor.size(); |
| |
| if (invListCursor.hasNext()) |
| invListCursor.next(); |
| |
| while (invListTidx < invListNumTuples && resultTidx < resultFrameTupleAcc.getTupleCount()) { |
| |
| ITupleReference invListTuple = invListCursor.getTuple(); |
| |
| resultTuple.reset(prevCurrentBuffer.array(), resultFrameTupleAcc.getTupleStartOffset(resultTidx)); |
| |
| int cmp = invListCmp.compare(invListTuple, resultTuple); |
| if (cmp == 0) { |
| int count = IntegerSerializerDeserializer.getInt(resultTuple.getFieldData(0), |
| resultTuple.getFieldStart(resultTuple.getFieldCount() - 1)) + 1; |
| newSearchResult.append(resultTuple, count); |
| advanceCursor = true; |
| advancePrevResult = true; |
| } else { |
| if (cmp < 0) { |
| advanceCursor = true; |
| advancePrevResult = false; |
| } else { |
| int count = IntegerSerializerDeserializer.getInt(resultTuple.getFieldData(0), |
| resultTuple.getFieldStart(resultTuple.getFieldCount() - 1)); |
| if (count + numInvLists - invListIx > occurrenceThreshold) { |
| newSearchResult.append(resultTuple, count); |
| } |
| advanceCursor = false; |
| advancePrevResult = true; |
| } |
| } |
| |
| if (advancePrevResult) { |
| resultTidx++; |
| if (resultTidx >= resultFrameTupleAcc.getTupleCount()) { |
| prevBufIdx++; |
| if (prevBufIdx <= maxPrevBufIdx) { |
| prevCurrentBuffer = prevSearchResult.getBuffers().get(prevBufIdx); |
| resultFrameTupleAcc.reset(prevCurrentBuffer); |
| resultTidx = 0; |
| } |
| } |
| } |
| |
| if (advanceCursor) { |
| invListTidx++; |
| if (invListCursor.hasNext()) { |
| invListCursor.next(); |
| } |
| } |
| } |
| |
| // append remaining elements from previous result set |
| while (resultTidx < resultFrameTupleAcc.getTupleCount()) { |
| |
| resultTuple.reset(prevCurrentBuffer.array(), resultFrameTupleAcc.getTupleStartOffset(resultTidx)); |
| |
| int count = IntegerSerializerDeserializer.getInt(resultTuple.getFieldData(0), |
| resultTuple.getFieldStart(resultTuple.getFieldCount() - 1)); |
| if (count + numInvLists - invListIx > occurrenceThreshold) { |
| newSearchResult.append(resultTuple, count); |
| } |
| |
| resultTidx++; |
| if (resultTidx >= resultFrameTupleAcc.getTupleCount()) { |
| prevBufIdx++; |
| if (prevBufIdx <= maxPrevBufIdx) { |
| prevCurrentBuffer = prevSearchResult.getBuffers().get(prevBufIdx); |
| resultFrameTupleAcc.reset(prevCurrentBuffer); |
| resultTidx = 0; |
| } |
| } |
| } |
| } |
| |
| protected void mergePrefixList(IInvertedListCursor invListCursor, SearchResult prevSearchResult, |
| SearchResult newSearchResult) throws HyracksDataException, IndexException { |
| |
| int prevBufIdx = 0; |
| int maxPrevBufIdx = prevSearchResult.getCurrentBufferIndex(); |
| ByteBuffer prevCurrentBuffer = prevSearchResult.getBuffers().get(0); |
| |
| FixedSizeFrameTupleAccessor resultFrameTupleAcc = prevSearchResult.getAccessor(); |
| FixedSizeTupleReference resultTuple = prevSearchResult.getTuple(); |
| |
| boolean advanceCursor = true; |
| boolean advancePrevResult = false; |
| int resultTidx = 0; |
| |
| resultFrameTupleAcc.reset(prevCurrentBuffer); |
| |
| int invListTidx = 0; |
| int invListNumTuples = invListCursor.size(); |
| |
| if (invListCursor.hasNext()) |
| invListCursor.next(); |
| |
| while (invListTidx < invListNumTuples && resultTidx < resultFrameTupleAcc.getTupleCount()) { |
| |
| ITupleReference invListTuple = invListCursor.getTuple(); |
| resultTuple.reset(prevCurrentBuffer.array(), resultFrameTupleAcc.getTupleStartOffset(resultTidx)); |
| |
| int cmp = invListCmp.compare(invListTuple, resultTuple); |
| if (cmp == 0) { |
| int count = IntegerSerializerDeserializer.getInt(resultTuple.getFieldData(0), |
| resultTuple.getFieldStart(resultTuple.getFieldCount() - 1)) + 1; |
| newSearchResult.append(resultTuple, count); |
| advanceCursor = true; |
| advancePrevResult = true; |
| } else { |
| if (cmp < 0) { |
| int count = 1; |
| newSearchResult.append(invListTuple, count); |
| advanceCursor = true; |
| advancePrevResult = false; |
| } else { |
| int count = IntegerSerializerDeserializer.getInt(resultTuple.getFieldData(0), |
| resultTuple.getFieldStart(resultTuple.getFieldCount() - 1)); |
| newSearchResult.append(resultTuple, count); |
| advanceCursor = false; |
| advancePrevResult = true; |
| } |
| } |
| |
| if (advancePrevResult) { |
| resultTidx++; |
| if (resultTidx >= resultFrameTupleAcc.getTupleCount()) { |
| prevBufIdx++; |
| if (prevBufIdx <= maxPrevBufIdx) { |
| prevCurrentBuffer = prevSearchResult.getBuffers().get(prevBufIdx); |
| resultFrameTupleAcc.reset(prevCurrentBuffer); |
| resultTidx = 0; |
| } |
| } |
| } |
| |
| if (advanceCursor) { |
| invListTidx++; |
| if (invListCursor.hasNext()) { |
| invListCursor.next(); |
| } |
| } |
| } |
| |
| // append remaining new elements from inverted list |
| while (invListTidx < invListNumTuples) { |
| ITupleReference invListTuple = invListCursor.getTuple(); |
| newSearchResult.append(invListTuple, 1); |
| invListTidx++; |
| if (invListCursor.hasNext()) { |
| invListCursor.next(); |
| } |
| } |
| |
| // append remaining elements from previous result set |
| while (resultTidx < resultFrameTupleAcc.getTupleCount()) { |
| |
| resultTuple.reset(prevCurrentBuffer.array(), resultFrameTupleAcc.getTupleStartOffset(resultTidx)); |
| |
| int count = IntegerSerializerDeserializer.getInt(resultTuple.getFieldData(0), |
| resultTuple.getFieldStart(resultTuple.getFieldCount() - 1)); |
| newSearchResult.append(resultTuple, count); |
| |
| resultTidx++; |
| if (resultTidx >= resultFrameTupleAcc.getTupleCount()) { |
| prevBufIdx++; |
| if (prevBufIdx <= maxPrevBufIdx) { |
| prevCurrentBuffer = prevSearchResult.getBuffers().get(prevBufIdx); |
| resultFrameTupleAcc.reset(prevCurrentBuffer); |
| resultTidx = 0; |
| } |
| } |
| } |
| } |
| |
| public SearchResult createSearchResult() { |
| return new SearchResult(prevSearchResult); |
| } |
| |
| public void reset() { |
| prevSearchResult.clear(); |
| newSearchResult.clear(); |
| } |
| } |
