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.jupiter.api.Assertions.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.KeyValue;
028import org.apache.hadoop.hbase.regionserver.querymatcher.ScanQueryMatcher.MatchCode;
029import org.apache.hadoop.hbase.testclassification.RegionServerTests;
030import org.apache.hadoop.hbase.testclassification.SmallTests;
031import org.apache.hadoop.hbase.util.Bytes;
032import org.junit.jupiter.api.Tag;
033import org.junit.jupiter.api.Test;
034
035@Tag(RegionServerTests.TAG)
036@Tag(SmallTests.TAG)
037public class TestExplicitColumnTracker {
038
039  private final byte[] col1 = Bytes.toBytes("col1");
040  private final byte[] col2 = Bytes.toBytes("col2");
041  private final byte[] col3 = Bytes.toBytes("col3");
042  private final byte[] col4 = Bytes.toBytes("col4");
043  private final byte[] col5 = Bytes.toBytes("col5");
044
045  private void runTest(int maxVersions, TreeSet<byte[]> trackColumns, List<byte[]> scannerColumns,
046    List<MatchCode> expected) throws IOException {
047    ColumnTracker exp = new ExplicitColumnTracker(trackColumns, 0, maxVersions, Long.MIN_VALUE);
048
049    // Initialize result
050    List<ScanQueryMatcher.MatchCode> result = new ArrayList<>(scannerColumns.size());
051
052    long timestamp = 0;
053    // "Match"
054    for (byte[] col : scannerColumns) {
055      result.add(ScanQueryMatcher.checkColumn(exp, col, 0, col.length, ++timestamp,
056        KeyValue.Type.Put.getCode(), false));
057    }
058
059    assertEquals(expected.size(), result.size());
060    for (int i = 0; i < expected.size(); i++) {
061      assertEquals(expected.get(i), result.get(i));
062    }
063  }
064
065  @Test
066  public void testGetSingleVersion() throws IOException {
067    // Create tracker
068    TreeSet<byte[]> columns = new TreeSet<>(Bytes.BYTES_COMPARATOR);
069    // Looking for every other
070    columns.add(col2);
071    columns.add(col4);
072    List<MatchCode> expected = new ArrayList<>(5);
073    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL); // col1
074    expected.add(ScanQueryMatcher.MatchCode.INCLUDE_AND_SEEK_NEXT_COL); // col2
075    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL); // col3
076    expected.add(ScanQueryMatcher.MatchCode.INCLUDE_AND_SEEK_NEXT_ROW); // col4
077    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW); // col5
078    int maxVersions = 1;
079
080    // Create "Scanner"
081    List<byte[]> scanner = new ArrayList<>(5);
082    scanner.add(col1);
083    scanner.add(col2);
084    scanner.add(col3);
085    scanner.add(col4);
086    scanner.add(col5);
087
088    runTest(maxVersions, columns, scanner, expected);
089  }
090
091  @Test
092  public void testGetMultiVersion() throws IOException {
093    // Create tracker
094    TreeSet<byte[]> columns = new TreeSet<>(Bytes.BYTES_COMPARATOR);
095    // Looking for every other
096    columns.add(col2);
097    columns.add(col4);
098
099    List<ScanQueryMatcher.MatchCode> expected = new ArrayList<>(15);
100    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL);
101    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL);
102    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL);
103
104    expected.add(ScanQueryMatcher.MatchCode.INCLUDE); // col2; 1st version
105    expected.add(ScanQueryMatcher.MatchCode.INCLUDE_AND_SEEK_NEXT_COL); // col2; 2nd version
106    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL);
107
108    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL);
109    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL);
110    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_COL);
111
112    expected.add(ScanQueryMatcher.MatchCode.INCLUDE); // col4; 1st version
113    expected.add(ScanQueryMatcher.MatchCode.INCLUDE_AND_SEEK_NEXT_ROW); // col4; 2nd version
114    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW);
115
116    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW);
117    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW);
118    expected.add(ScanQueryMatcher.MatchCode.SEEK_NEXT_ROW);
119    int maxVersions = 2;
120
121    // Create "Scanner"
122    List<byte[]> scanner = new ArrayList<>(15);
123    scanner.add(col1);
124    scanner.add(col1);
125    scanner.add(col1);
126    scanner.add(col2);
127    scanner.add(col2);
128    scanner.add(col2);
129    scanner.add(col3);
130    scanner.add(col3);
131    scanner.add(col3);
132    scanner.add(col4);
133    scanner.add(col4);
134    scanner.add(col4);
135    scanner.add(col5);
136    scanner.add(col5);
137    scanner.add(col5);
138
139    // Initialize result
140    runTest(maxVersions, columns, scanner, expected);
141  }
142
143  /**
144   * hbase-2259
145   */
146  @Test
147  public void testStackOverflow() throws IOException {
148    int maxVersions = 1;
149    TreeSet<byte[]> columns = new TreeSet<>(Bytes.BYTES_COMPARATOR);
150    for (int i = 0; i < 100000; i++) {
151      columns.add(Bytes.toBytes("col" + i));
152    }
153
154    ColumnTracker explicit = new ExplicitColumnTracker(columns, 0, maxVersions, Long.MIN_VALUE);
155    for (int i = 0; i < 100000; i += 2) {
156      byte[] col = Bytes.toBytes("col" + i);
157      ScanQueryMatcher.checkColumn(explicit, col, 0, col.length, 1, KeyValue.Type.Put.getCode(),
158        false);
159    }
160    explicit.reset();
161
162    for (int i = 1; i < 100000; i += 2) {
163      byte[] col = Bytes.toBytes("col" + i);
164      ScanQueryMatcher.checkColumn(explicit, col, 0, col.length, 1, KeyValue.Type.Put.getCode(),
165        false);
166    }
167  }
168
169  /**
170   * Regression test for HBASE-2545
171   */
172  @Test
173  public void testInfiniteLoop() throws IOException {
174    TreeSet<byte[]> columns = new TreeSet<>(Bytes.BYTES_COMPARATOR);
175    columns.addAll(Arrays.asList(new byte[][] { col2, col3, col5 }));
176    List<byte[]> scanner = Arrays.<byte[]> asList(new byte[][] { col1, col4 });
177    List<ScanQueryMatcher.MatchCode> expected =
178      Arrays.<ScanQueryMatcher.MatchCode> asList(new ScanQueryMatcher.MatchCode[] {
179        ScanQueryMatcher.MatchCode.SEEK_NEXT_COL, ScanQueryMatcher.MatchCode.SEEK_NEXT_COL });
180    runTest(1, columns, scanner, expected);
181  }
182
183}