// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
package com.yahoo.search.predicate.index;
import com.yahoo.search.predicate.Hit;
import com.yahoo.search.predicate.SubqueryBitmap;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import static java.util.stream.Collectors.toList;
import static org.junit.Assert.assertEquals;
/**
* @author Magnar Nedland
* @author bjorncs
*/
public class PredicateSearchTest {
@Test
public void requireThatNoStreamsReturnNoResults() {
PredicateSearch search = new PredicateSearch(new ArrayList<>(), new byte[0], new byte[0], new short[0], 1);
assertEquals(0, search.stream().count());
}
@Test
public void requireThatSingleStreamFiltersOnConstructedCompleteIntervals() {
PredicateSearch search = createPredicateSearch(
new byte[]{1, 1, 1},
postingList(
SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x000100ff),
entry(1, 0x00010001, 0x000200ff),
entry(2, 0x00010042)));
assertEquals(Arrays.asList(new Hit(0), new Hit(1)).toString(), search.stream().collect(toList()).toString());
}
@Test
public void requireThatMinFeatureIsUsedToPruneResults() {
PredicateSearch search = createPredicateSearch(
new byte[]{3, 1},
postingList(
SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x000100ff),
entry(1, 0x000100ff)));
assertEquals(Arrays.asList(new Hit(1)).toString(), search.stream().collect(toList()).toString());
}
@Test
public void requireThatAHighKCanYieldResults() {
PredicateSearch search = createPredicateSearch(
new byte[]{2},
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00010001)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x000200ff)));
assertEquals(Arrays.asList(new Hit(0)).toString(), search.stream().collect(toList()).toString());
}
@Test
public void requireThatPostingListsAreSortedAfterAdvancing() {
PredicateSearch search = createPredicateSearch(
new byte[] {2, 1, 1, 1},
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x000100ff),
entry(3, 0x000100ff)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(1, 0x000100ff),
entry(2, 0x000100ff)));
assertEquals(Arrays.asList(new Hit(1), new Hit(2), new Hit(3)).toString(), search.stream().collect(toList()).toString());
}
@Test
public void requireThatEmptyPostingListsWork() {
PredicateSearch search = createPredicateSearch(
new byte[0],
postingList(SubqueryBitmap.ALL_SUBQUERIES));
assertEquals(Arrays.asList().toString(), search.stream().collect(toList()).toString());
}
@Test
public void requireThatShorterPostingListEndingIsOk() {
PredicateSearch search = createPredicateSearch(
new byte[]{1, 1, 1},
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x000100ff),
entry(1, 0x000100ff)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(2, 0x000100ff)));
assertEquals(Arrays.asList(new Hit(0), new Hit(1), new Hit(2)).toString(), search.stream().collect(toList()).toString());
}
@Test
public void requireThatSortingWorksForManyPostingLists() {
PredicateSearch search = createPredicateSearch(
new byte[]{1, 5, 2, 2},
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x000100ff),
entry(1, 0x000100ff)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(1, 0x000100ff),
entry(2, 0x000100ff)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(1, 0x000100ff),
entry(3, 0x000100ff)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(1, 0x000100ff),
entry(2, 0x000100ff)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(1, 0x000100ff),
entry(3, 0x000100ff)));
assertEquals(
Arrays.asList(new Hit(0), new Hit(1), new Hit(2), new Hit(3)).toString(),
search.stream().collect(toList()).toString());
}
@Test
public void requireThatInsufficientIntervalCoveragePreventsMatch() {
PredicateSearch search = createPredicateSearch(
new byte[]{1, 1},
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00010001),
entry(1, 0x000200ff)));
assertEquals(Arrays.asList().toString(), search.stream().collect(toList()).toString());
}
@Test
public void requireThatIntervalsAreSorted() {
PredicateSearch search = createPredicateSearch(
new byte[]{1},
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00010001)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x000300ff)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00020002)));
assertEquals(Arrays.asList(new Hit(0)).toString(), search.stream().collect(toList()).toString());
}
@Test
public void requireThatThereCanBeManyIntervals() {
PredicateSearch search = createPredicateSearch(
new byte[]{1},
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00010001, 0x00020002, 0x00030003, 0x000100ff, 0x00040004, 0x00050005, 0x00060006)));
assertEquals(Arrays.asList(new Hit(0)).toString(), search.stream().collect(toList()).toString());
}
@Test
public void requireThatNotIsSupported_NoMatch() {
PredicateSearch search = createPredicateSearch(
new byte[]{1},
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00010001)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00010000, 0x00ff0001)));
assertEquals(Arrays.asList().toString(), search.stream().collect(toList()).toString());
}
@Test
public void requireThatNotIsSupported_Match() {
PredicateSearch search = createPredicateSearch(
new byte[]{1},
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00010000, 0x00ff0001)));
assertEquals(Arrays.asList(new Hit(0)).toString(), search.stream().collect(toList()).toString());
}
@Test
public void requireThatNotIsSupported_NoMatchBecauseOfPreviousTerm() {
PredicateSearch search = createPredicateSearch(
new byte[]{1},
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00020001, 0x00ff0001)));
assertEquals(Arrays.asList().toString(), search.stream().collect(toList()).toString());
}
@Test
public void requireThatIntervalSortingWorksAsUnsigned() {
PredicateSearch search = createPredicateSearch(
new byte[]{1},
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00010001)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00fe0001, 0x00ff00fe)));
assertEquals(Arrays.asList(new Hit(0)).toString(), search.stream().collect(toList()).toString());
}
@Test
public void requireThatMatchCanRequireMultiplePostingLists() {
PredicateSearch search = createPredicateSearch(
new byte[]{6},
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00010001)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x0002000b, 0x00030003)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00040003)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00050004)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00010008, 0x00060006)),
postingList(SubqueryBitmap.ALL_SUBQUERIES,
entry(0, 0x00020002, 0x000700ff)));
assertEquals(Arrays.asList(new Hit(0)).toString(), search.stream().collect(toList()).toString());
}
private static PredicateSearch createPredicateSearch(byte[] minFeatures, PostingList... postingLists) {
byte[] nPostingListsForDocument = new byte[minFeatures.length];
short[] intervalEnds = new short[minFeatures.length];
Arrays.fill(intervalEnds, (short) 0xFF);
List list = Arrays.asList(postingLists);
for (PostingList postingList : postingLists) {
for (int id : postingList.getDocIds()) {
nPostingListsForDocument[id]++;
}
}
return new PredicateSearch(list, nPostingListsForDocument, minFeatures, intervalEnds, 0xFF);
}
private static class SimplePostingList implements PostingList {
private final long subquery;
private final Entry[] entries;
private int[] currentIntervals;
private int currentIntervalIndex;
private int currentDocId;
private int currentIndex;
public SimplePostingList(long subquery, Entry... entries) {
this.subquery = subquery;
this.entries = entries;
this.currentIndex = 0;
this.currentDocId = -1;
}
@Override
public boolean nextDocument(int docId) {
while (currentIndex < entries.length && entries[currentIndex].docId <= docId) {
++currentIndex;
}
if (currentIndex == entries.length) {
return false;
}
Entry entry = entries[currentIndex];
currentDocId = entry.docId;
currentIntervals = entry.intervals;
currentIntervalIndex = 0;
return true;
}
@Override
public boolean prepareIntervals() {
return true;
}
@Override
public boolean nextInterval() {
return ++currentIntervalIndex < currentIntervals.length;
}
@Override
public int getDocId() {
return currentDocId;
}
@Override
public int size() {
return entries.length;
}
@Override
public int getInterval() {
return currentIntervals[currentIntervalIndex];
}
@Override
public long getSubquery() {
return subquery;
}
@Override
public int[] getDocIds() {
return Arrays.stream(entries).mapToInt(e -> e.docId).toArray();
}
public static class Entry {
public final int docId;
public final int[] intervals;
public Entry(int docId, int... intervals) {
this.docId = docId;
this.intervals = intervals;
}
}
}
private static SimplePostingList postingList(long subquery, SimplePostingList.Entry... entries) {
return new SimplePostingList(subquery, entries);
}
private static SimplePostingList.Entry entry(int docId, int... intervals) {
return new SimplePostingList.Entry(docId, intervals);
}
}