001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.regionserver.querymatcher;
019
020import static org.junit.Assert.assertEquals;
021
022import java.io.IOException;
023import java.util.ArrayList;
024import java.util.Arrays;
025import java.util.List;
026import java.util.TreeSet;
027import org.apache.hadoop.hbase.HBaseClassTestRule;
028import org.apache.hadoop.hbase.KeyValue;
029import org.apache.hadoop.hbase.regionserver.querymatcher.ScanQueryMatcher.MatchCode;
030import org.apache.hadoop.hbase.testclassification.RegionServerTests;
031import org.apache.hadoop.hbase.testclassification.SmallTests;
032import org.apache.hadoop.hbase.util.Bytes;
033import org.junit.ClassRule;
034import org.junit.Test;
035import org.junit.experimental.categories.Category;
036
037@Category({ RegionServerTests.class, SmallTests.class })
038public class TestExplicitColumnTracker {
039
040  @ClassRule
041  public static final HBaseClassTestRule CLASS_RULE =
042    HBaseClassTestRule.forClass(TestExplicitColumnTracker.class);
043
044  private final byte[] col1 = Bytes.toBytes("col1");
045  private final byte[] col2 = Bytes.toBytes("col2");
046  private final byte[] col3 = Bytes.toBytes("col3");
047  private final byte[] col4 = Bytes.toBytes("col4");
048  private final byte[] col5 = Bytes.toBytes("col5");
049
050  private void runTest(int maxVersions, TreeSet<byte[]> trackColumns, List<byte[]> scannerColumns,
051    List<MatchCode> expected) throws IOException {
052    ColumnTracker exp = new ExplicitColumnTracker(trackColumns, 0, maxVersions, Long.MIN_VALUE);
053
054    // Initialize result
055    List<ScanQueryMatcher.MatchCode> result = new ArrayList<>(scannerColumns.size());
056
057    long timestamp = 0;
058    // "Match"
059    for (byte[] col : scannerColumns) {
060      result.add(ScanQueryMatcher.checkColumn(exp, col, 0, col.length, ++timestamp,
061        KeyValue.Type.Put.getCode(), false));
062    }
063
064    assertEquals(expected.size(), result.size());
065    for (int i = 0; i < expected.size(); i++) {
066      assertEquals(expected.get(i), result.get(i));
067    }
068  }
069
070  @Test
071  public void testGetSingleVersion() throws IOException {
072    // Create tracker
073    TreeSet<byte[]> columns = new TreeSet<>(Bytes.BYTES_COMPARATOR);
074    // Looking for every other
075    columns.add(col2);
076    columns.add(col4);
077    List<MatchCode> expected = new ArrayList<>(5);
078    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL); // col1
079    expected.add(ScanQueryMatcher.MatchCode.INCLUDE_AND_SEEK_NEXT_COL); // col2
080    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL); // col3
081    expected.add(ScanQueryMatcher.MatchCode.INCLUDE_AND_SEEK_NEXT_ROW); // col4
082    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW); // col5
083    int maxVersions = 1;
084
085    // Create "Scanner"
086    List<byte[]> scanner = new ArrayList<>(5);
087    scanner.add(col1);
088    scanner.add(col2);
089    scanner.add(col3);
090    scanner.add(col4);
091    scanner.add(col5);
092
093    runTest(maxVersions, columns, scanner, expected);
094  }
095
096  @Test
097  public void testGetMultiVersion() throws IOException {
098    // Create tracker
099    TreeSet<byte[]> columns = new TreeSet<>(Bytes.BYTES_COMPARATOR);
100    // Looking for every other
101    columns.add(col2);
102    columns.add(col4);
103
104    List<ScanQueryMatcher.MatchCode> expected = new ArrayList<>(15);
105    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL);
106    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL);
107    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL);
108
109    expected.add(ScanQueryMatcher.MatchCode.INCLUDE); // col2; 1st version
110    expected.add(ScanQueryMatcher.MatchCode.INCLUDE_AND_SEEK_NEXT_COL); // col2; 2nd version
111    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL);
112
113    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL);
114    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL);
115    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL);
116
117    expected.add(ScanQueryMatcher.MatchCode.INCLUDE); // col4; 1st version
118    expected.add(ScanQueryMatcher.MatchCode.INCLUDE_AND_SEEK_NEXT_ROW); // col4; 2nd version
119    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW);
120
121    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW);
122    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW);
123    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW);
124    int maxVersions = 2;
125
126    // Create "Scanner"
127    List<byte[]> scanner = new ArrayList<>(15);
128    scanner.add(col1);
129    scanner.add(col1);
130    scanner.add(col1);
131    scanner.add(col2);
132    scanner.add(col2);
133    scanner.add(col2);
134    scanner.add(col3);
135    scanner.add(col3);
136    scanner.add(col3);
137    scanner.add(col4);
138    scanner.add(col4);
139    scanner.add(col4);
140    scanner.add(col5);
141    scanner.add(col5);
142    scanner.add(col5);
143
144    // Initialize result
145    runTest(maxVersions, columns, scanner, expected);
146  }
147
148  /**
149   * hbase-2259
150   */
151  @Test
152  public void testStackOverflow() throws IOException {
153    int maxVersions = 1;
154    TreeSet<byte[]> columns = new TreeSet<>(Bytes.BYTES_COMPARATOR);
155    for (int i = 0; i < 100000; i++) {
156      columns.add(Bytes.toBytes("col" + i));
157    }
158
159    ColumnTracker explicit = new ExplicitColumnTracker(columns, 0, maxVersions, Long.MIN_VALUE);
160    for (int i = 0; i < 100000; i += 2) {
161      byte[] col = Bytes.toBytes("col" + i);
162      ScanQueryMatcher.checkColumn(explicit, col, 0, col.length, 1, KeyValue.Type.Put.getCode(),
163        false);
164    }
165    explicit.reset();
166
167    for (int i = 1; i < 100000; i += 2) {
168      byte[] col = Bytes.toBytes("col" + i);
169      ScanQueryMatcher.checkColumn(explicit, col, 0, col.length, 1, KeyValue.Type.Put.getCode(),
170        false);
171    }
172  }
173
174  /**
175   * Regression test for HBASE-2545
176   */
177  @Test
178  public void testInfiniteLoop() throws IOException {
179    TreeSet<byte[]> columns = new TreeSet<>(Bytes.BYTES_COMPARATOR);
180    columns.addAll(Arrays.asList(new byte[][] { col2, col3, col5 }));
181    List<byte[]> scanner = Arrays.<byte[]> asList(new byte[][] { col1, col4 });
182    List<ScanQueryMatcher.MatchCode> expected =
183      Arrays.<ScanQueryMatcher.MatchCode> asList(new ScanQueryMatcher.MatchCode[] {
184        ScanQueryMatcher.MatchCode.SEEK_NEXT_COL, ScanQueryMatcher.MatchCode.SEEK_NEXT_COL });
185    runTest(1, columns, scanner, expected);
186  }
187
188}