View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  
19  package org.apache.hadoop.hbase.codec.prefixtree.row;
20  
21  import java.io.ByteArrayOutputStream;
22  import java.io.IOException;
23  import java.nio.ByteBuffer;
24  import java.util.Arrays;
25  import java.util.Collection;
26  import java.util.List;
27  
28  import org.apache.hadoop.hbase.Cell;
29  import org.apache.hadoop.hbase.CellComparator;
30  import org.apache.hadoop.hbase.KeyValue;
31  import org.apache.hadoop.hbase.KeyValueUtil;
32  import org.apache.hadoop.hbase.testclassification.SmallTests;
33  import org.apache.hadoop.hbase.codec.prefixtree.decode.DecoderFactory;
34  import org.apache.hadoop.hbase.codec.prefixtree.encode.PrefixTreeEncoder;
35  import org.apache.hadoop.hbase.codec.prefixtree.row.data.TestRowDataSearchWithPrefix;
36  import org.apache.hadoop.hbase.codec.prefixtree.scanner.CellScannerPosition;
37  import org.apache.hadoop.hbase.codec.prefixtree.scanner.CellSearcher;
38  import org.apache.hadoop.hbase.util.CollectionUtils;
39  import org.junit.Assert;
40  import org.junit.Test;
41  import org.junit.experimental.categories.Category;
42  import org.junit.runner.RunWith;
43  import org.junit.runners.Parameterized;
44  import org.junit.runners.Parameterized.Parameters;
45  
46  @Category(SmallTests.class)
47  @RunWith(Parameterized.class)
48  public class TestPrefixTreeSearcher {
49  
50    protected static int BLOCK_START = 7;
51  
52    @Parameters
53    public static Collection<Object[]> parameters() {
54      return new TestRowData.InMemory().getAllAsObjectArray();
55    }
56  
57    protected TestRowData rows;
58    protected ByteBuffer block;
59  
60    public TestPrefixTreeSearcher(TestRowData testRows) throws IOException {
61      this.rows = testRows;
62      ByteArrayOutputStream os = new ByteArrayOutputStream(1 << 20);
63      PrefixTreeEncoder kvBuilder = new PrefixTreeEncoder(os, true);
64      for (KeyValue kv : rows.getInputs()) {
65        kvBuilder.write(kv);
66      }
67      kvBuilder.flush();
68      byte[] outputBytes = os.toByteArray();
69      this.block = ByteBuffer.wrap(outputBytes);
70    }
71  
72    @Test
73    public void testScanForwards() throws IOException {
74      CellSearcher searcher = null;
75      try {
76        searcher = DecoderFactory.checkOut(block, true);
77  
78        int i = -1;
79        while (searcher.advance()) {
80          ++i;
81          KeyValue inputCell = rows.getInputs().get(i);
82          Cell outputCell = searcher.current();
83  
84          // check all 3 permutations of equals()
85          Assert.assertEquals(inputCell, outputCell);
86          Assert.assertEquals(outputCell, inputCell);
87          Assert.assertTrue(CellComparator.equals(inputCell, outputCell));
88        }
89        Assert.assertEquals(rows.getInputs().size(), i + 1);
90      } finally {
91        DecoderFactory.checkIn(searcher);
92      }
93    }
94  
95  
96    @Test
97    public void testScanBackwards() throws IOException {
98      CellSearcher searcher = null;
99      try {
100       searcher = DecoderFactory.checkOut(block, true);
101       searcher.positionAfterLastCell();
102       int i = -1;
103       while (searcher.previous()) {
104         ++i;
105         int oppositeIndex = rows.getInputs().size() - i - 1;
106         KeyValue inputKv = rows.getInputs().get(oppositeIndex);
107         KeyValue outputKv = KeyValueUtil.copyToNewKeyValue(searcher.current());
108         Assert.assertEquals(inputKv, outputKv);
109       }
110       Assert.assertEquals(rows.getInputs().size(), i + 1);
111     } finally {
112       DecoderFactory.checkIn(searcher);
113     }
114   }
115 
116 
117   @Test
118   public void testRandomSeekHits() throws IOException {
119     CellSearcher searcher = null;
120     try {
121       searcher = DecoderFactory.checkOut(block, true);
122       for (KeyValue kv : rows.getInputs()) {
123         boolean hit = searcher.positionAt(kv);
124         Assert.assertTrue(hit);
125         Cell foundKv = searcher.current();
126         Assert.assertTrue(CellComparator.equals(kv, foundKv));
127       }
128     } finally {
129       DecoderFactory.checkIn(searcher);
130     }
131   }
132 
133   @Test
134   public void testRandomSeekMisses() throws IOException {
135     CellSearcher searcher = null;
136     List<Integer> rowStartIndexes = rows.getRowStartIndexes();
137     try {
138       searcher = DecoderFactory.checkOut(block, true);
139 
140       //test both the positionAtOrBefore and positionAtOrAfter methods
141       for(boolean beforeVsAfterOnMiss : new boolean[]{true, false}){
142         for (int i=0; i < rows.getInputs().size(); ++i) {
143           KeyValue kv = rows.getInputs().get(i);
144 
145           //nextRow
146           KeyValue inputNextRow = KeyValueUtil.createFirstKeyInNextRow(kv);
147 
148           CellScannerPosition position = beforeVsAfterOnMiss
149               ? searcher.positionAtOrBefore(inputNextRow)
150               : searcher.positionAtOrAfter(inputNextRow);
151           boolean isFirstInRow = rowStartIndexes.contains(i);
152           if(isFirstInRow){
153             int rowIndex = rowStartIndexes.indexOf(i);
154             if(rowIndex < rowStartIndexes.size() - 1){
155               if(beforeVsAfterOnMiss){
156                 Assert.assertEquals(CellScannerPosition.BEFORE, position);
157               }else{
158                 Assert.assertEquals(CellScannerPosition.AFTER, position);
159               }
160 
161               int expectedInputIndex = beforeVsAfterOnMiss
162                   ? rowStartIndexes.get(rowIndex + 1) - 1
163                   : rowStartIndexes.get(rowIndex + 1);
164               Assert.assertEquals(rows.getInputs().get(expectedInputIndex), searcher.current());
165             }
166           }
167 
168           //previous KV
169           KeyValue inputPreviousKv = KeyValueUtil.previousKey(kv);
170           boolean hit = searcher.positionAt(inputPreviousKv);
171           Assert.assertFalse(hit);
172           position = searcher.positionAtOrAfter(inputPreviousKv);
173           if(CollectionUtils.isLastIndex(rows.getInputs(), i)){
174             Assert.assertTrue(CellScannerPosition.AFTER_LAST == position);
175           }else{
176             Assert.assertTrue(CellScannerPosition.AFTER == position);
177             /*
178              * TODO: why i+1 instead of i?
179              */
180             Assert.assertEquals(rows.getInputs().get(i+1), searcher.current());
181           }
182         }
183       }
184     } finally {
185       DecoderFactory.checkIn(searcher);
186     }
187   }
188 
189 
190   @Test
191   public void testRandomSeekIndividualAssertions() throws IOException {
192     CellSearcher searcher = null;
193     try {
194       searcher = DecoderFactory.checkOut(block, true);
195       rows.individualSearcherAssertions(searcher);
196     } finally {
197       DecoderFactory.checkIn(searcher);
198     }
199   }
200   
201   @Test
202   public void testSeekWithPrefix() throws IOException {
203     if (!(rows instanceof TestRowDataSearchWithPrefix)) {
204       return;
205     }
206     CellSearcher searcher = null;
207     try {
208       searcher = DecoderFactory.checkOut(block, true);
209       // seek with half bytes of second row key, should return second row
210       KeyValue kv = rows.getInputs().get(1);
211       KeyValue firstKVOnRow = KeyValueUtil.createFirstOnRow(Arrays.copyOfRange(
212           kv.getRowArray(), kv.getRowOffset(),
213           kv.getRowOffset() + kv.getRowLength() / 2));
214       CellScannerPosition position = searcher.positionAtOrAfter(firstKVOnRow);
215       Assert.assertEquals(CellScannerPosition.AFTER, position);
216       Assert.assertEquals(kv, searcher.current());
217     } finally {
218       DecoderFactory.checkIn(searcher);
219     }
220   }
221 }