1 /*
2 * Copyright (C) 2023 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "src/trace_processor/db/column/dense_null_overlay.h"
18
19 #include <cstdint>
20 #include <limits>
21 #include <memory>
22 #include <utility>
23 #include <vector>
24
25 #include "perfetto/trace_processor/basic_types.h"
26 #include "src/trace_processor/containers/bit_vector.h"
27 #include "src/trace_processor/db/column/data_layer.h"
28 #include "src/trace_processor/db/column/fake_storage.h"
29 #include "src/trace_processor/db/column/numeric_storage.h"
30 #include "src/trace_processor/db/column/types.h"
31 #include "src/trace_processor/db/column/utils.h"
32 #include "test/gtest_and_gmock.h"
33
34 namespace perfetto::trace_processor::column {
35 namespace {
36
37 using testing::ElementsAre;
38 using testing::IsEmpty;
39 using testing::UnorderedElementsAre;
40
41 using Indices = DataLayerChain::Indices;
42 using OrderedIndices = DataLayerChain::OrderedIndices;
43
TEST(DenseNullOverlay,NoFilteringSearch)44 TEST(DenseNullOverlay, NoFilteringSearch) {
45 std::vector<uint32_t> data{0, 1, 0, 1, 0};
46 auto numeric = std::make_unique<NumericStorage<uint32_t>>(
47 &data, ColumnType::kUint32, false);
48
49 BitVector bv{0, 1, 0, 1, 0};
50 DenseNullOverlay storage(&bv);
51 auto chain = storage.MakeChain(numeric->MakeChain());
52
53 auto res = chain->Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
54 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3));
55 }
56
TEST(DenseNullOverlay,RestrictInputSearch)57 TEST(DenseNullOverlay, RestrictInputSearch) {
58 std::vector<uint32_t> data{0, 1, 0, 1, 0};
59 auto numeric = std::make_unique<NumericStorage<uint32_t>>(
60 &data, ColumnType::kUint32, false);
61
62 BitVector bv{0, 1, 0, 1, 0};
63 DenseNullOverlay storage(&bv);
64 auto chain = storage.MakeChain(numeric->MakeChain());
65
66 auto res = chain->Search(FilterOp::kGe, SqlValue::Long(0), Range(1, 3));
67 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
68 }
69
TEST(DenseNullOverlay,RangeFilterSearch)70 TEST(DenseNullOverlay, RangeFilterSearch) {
71 auto fake = FakeStorageChain::SearchSubset(5, Range(1, 3));
72
73 BitVector bv{0, 1, 0, 1, 0};
74 DenseNullOverlay storage(&bv);
75 auto chain = storage.MakeChain(std::move(fake));
76
77 auto res = chain->Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
78 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
79 }
80
TEST(DenseNullOverlay,BitvectorFilterSearch)81 TEST(DenseNullOverlay, BitvectorFilterSearch) {
82 auto fake = FakeStorageChain::SearchSubset(5, BitVector({0, 1, 1, 0, 0}));
83
84 BitVector bv{0, 1, 0, 1, 0};
85 DenseNullOverlay storage(&bv);
86 auto chain = storage.MakeChain(std::move(fake));
87
88 auto res = chain->Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
89 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
90 }
91
TEST(DenseNullOverlay,IsNullSearch)92 TEST(DenseNullOverlay, IsNullSearch) {
93 auto fake = FakeStorageChain::SearchSubset(5, BitVector({1, 1, 0, 0, 1}));
94
95 BitVector bv{1, 0, 0, 1, 1};
96 DenseNullOverlay storage(&bv);
97 auto chain = storage.MakeChain(std::move(fake));
98
99 auto res = chain->Search(FilterOp::kIsNull, SqlValue(), Range(0, 5));
100 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 4));
101 }
102
TEST(DenseNullOverlay,IndexSearch)103 TEST(DenseNullOverlay, IndexSearch) {
104 std::vector<uint32_t> data{1, 0, 0, 1, 1, 1};
105 auto numeric = std::make_unique<NumericStorage<uint32_t>>(
106 &data, ColumnType::kUint32, false);
107
108 BitVector bv{1, 0, 0, 1, 1, 1};
109 DenseNullOverlay storage(&bv);
110 auto chain = storage.MakeChain(numeric->MakeChain());
111
112 Indices indices = Indices::CreateWithIndexPayloadForTesting(
113 {5, 2, 3, 4, 1}, Indices::State::kNonmonotonic);
114 chain->IndexSearch(FilterOp::kGe, SqlValue::Long(0), indices);
115 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2, 3));
116 }
117
TEST(DenseNullOverlay,IsNullIndexSearch)118 TEST(DenseNullOverlay, IsNullIndexSearch) {
119 auto fake = FakeStorageChain::SearchSubset(6, BitVector({0, 0, 0, 1, 1, 1}));
120
121 BitVector bv{0, 1, 0, 1, 1, 1};
122 DenseNullOverlay storage(&bv);
123 auto chain = storage.MakeChain(std::move(fake));
124
125 Indices indices = Indices::CreateWithIndexPayloadForTesting(
126 {5, 2, 3, 4, 1}, Indices::State::kNonmonotonic);
127 chain->IndexSearch(FilterOp::kIsNull, SqlValue(), indices);
128 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
129 ElementsAre(0, 1, 2, 3));
130 }
131
TEST(DenseNullOverlay,OrderedIndexSearch)132 TEST(DenseNullOverlay, OrderedIndexSearch) {
133 std::vector<uint32_t> numeric_data{0, 1, 0, 1, 0, 1};
134 NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
135
136 BitVector bv{0, 1, 0, 1, 0, 1};
137 DenseNullOverlay storage(&bv);
138 auto chain = storage.MakeChain(numeric.MakeChain());
139
140 std::vector<uint32_t> indices_vec({0, 2, 4, 1, 3, 5});
141 OrderedIndices indices{indices_vec.data(), 6, Indices::State::kNonmonotonic};
142
143 Range res = chain->OrderedIndexSearch(FilterOp::kIsNull, SqlValue(), indices);
144 ASSERT_EQ(res.start, 0u);
145 ASSERT_EQ(res.end, 3u);
146
147 res = chain->OrderedIndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
148 ASSERT_EQ(res.start, 3u);
149 ASSERT_EQ(res.end, 6u);
150
151 res = chain->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(1), indices);
152 ASSERT_EQ(res.start, 3u);
153 ASSERT_EQ(res.end, 6u);
154
155 res = chain->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(0), indices);
156 ASSERT_EQ(res.start, 3u);
157 ASSERT_EQ(res.end, 6u);
158
159 res = chain->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(1), indices);
160 ASSERT_EQ(res.start, 3u);
161 ASSERT_EQ(res.end, 6u);
162
163 res = chain->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(1), indices);
164 ASSERT_EQ(res.start, 0u);
165 ASSERT_EQ(res.end, 3u);
166
167 res = chain->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(0), indices);
168 ASSERT_EQ(res.start, 0u);
169 ASSERT_EQ(res.end, 3u);
170 }
171
TEST(DenseNullOverlay,SingleSearch)172 TEST(DenseNullOverlay, SingleSearch) {
173 BitVector bv{0, 1, 0, 1, 1, 1};
174 DenseNullOverlay storage(&bv);
175 auto fake = FakeStorageChain::SearchSubset(5, std::vector<uint32_t>{1, 2});
176 auto chain = storage.MakeChain(std::move(fake));
177
178 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(0u), 1),
179 SingleSearchResult::kMatch);
180 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(0u), 2),
181 SingleSearchResult::kNoMatch);
182 }
183
TEST(DenseNullOverlay,SingleSearchIsNull)184 TEST(DenseNullOverlay, SingleSearchIsNull) {
185 BitVector bv{0, 1, 0, 1, 1, 1};
186 DenseNullOverlay storage(&bv);
187 auto fake = FakeStorageChain::SearchNone(5);
188 auto chain = storage.MakeChain(std::move(fake));
189
190 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNull, SqlValue(), 0),
191 SingleSearchResult::kMatch);
192 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNull, SqlValue(), 1),
193 SingleSearchResult::kNoMatch);
194 }
195
TEST(DenseNullOverlay,SingleSearchIsNotNull)196 TEST(DenseNullOverlay, SingleSearchIsNotNull) {
197 BitVector bv{0, 1, 0, 1, 1, 1};
198 DenseNullOverlay storage(&bv);
199 auto fake = FakeStorageChain::SearchAll(5);
200 auto chain = storage.MakeChain(std::move(fake));
201
202 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNotNull, SqlValue(), 0),
203 SingleSearchResult::kNoMatch);
204 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNotNull, SqlValue(), 1),
205 SingleSearchResult::kMatch);
206 }
207
TEST(DenseNullOverlay,StableSort)208 TEST(DenseNullOverlay, StableSort) {
209 std::vector<uint32_t> numeric_data{0, 3, 0, 1, 0, 2, 4};
210 NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
211
212 BitVector null{0, 1, 0, 1, 1, 1, 1};
213 DenseNullOverlay overlay(&null);
214 auto chain = overlay.MakeChain(numeric.MakeChain());
215
216 auto make_tokens = []() {
217 return std::vector{
218 Token{0, 0}, Token{1, 1}, Token{2, 2}, Token{3, 3},
219 Token{4, 4}, Token{5, 5}, Token{6, 6},
220 };
221 };
222 {
223 auto tokens = make_tokens();
224 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
225 SortDirection::kAscending);
226 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
227 ElementsAre(0, 2, 4, 3, 5, 1, 6));
228 }
229 {
230 auto tokens = make_tokens();
231 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
232 SortDirection::kDescending);
233 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
234 ElementsAre(6, 1, 5, 3, 4, 0, 2));
235 }
236 }
237
TEST(DenseNullOverlay,Distinct)238 TEST(DenseNullOverlay, Distinct) {
239 std::vector<uint32_t> numeric_data{0, 3, 0, 1, 0, 2, 4};
240 NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
241
242 // NULL, 1, NULL, 1, 0, 2, 4
243 BitVector null{0, 1, 0, 1, 1, 1, 1};
244 DenseNullOverlay overlay(&null);
245 auto chain = overlay.MakeChain(numeric.MakeChain());
246
247 // NULL, 0, 1, 1
248 auto indices = Indices::CreateWithIndexPayloadForTesting(
249 {0, 1, 3, 3}, Indices::State::kNonmonotonic);
250 chain->Distinct(indices);
251 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
252 UnorderedElementsAre(0, 1, 2));
253 }
254
255 } // namespace
256 } // namespace perfetto::trace_processor::column
257