1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
#pragma once
#include <vector>
#include <Columns/ColumnArray.h>
#include <Columns/ColumnString.h>
namespace DB
{
namespace ErrorCodes
{
extern const int NUMBER_OF_ARGUMENTS_DOESNT_MATCH;
}
template <typename Name, typename Impl>
struct MultiSearchFirstPositionImpl
{
using ResultType = UInt64;
/// Variable for understanding, if we used offsets for the output, most
/// likely to determine whether the function returns ColumnVector of ColumnArray.
static constexpr bool is_column_array = false;
static constexpr auto name = Name::name;
static auto getReturnType() { return std::make_shared<DataTypeNumber<ResultType>>(); }
static void vectorConstant(
const ColumnString::Chars & haystack_data,
const ColumnString::Offsets & haystack_offsets,
const Array & needles_arr,
PaddedPODArray<UInt64> & res,
PaddedPODArray<UInt64> & /*offsets*/,
bool /*allow_hyperscan*/,
size_t /*max_hyperscan_regexp_length*/,
size_t /*max_hyperscan_regexp_total_length*/,
bool /*reject_expensive_hyperscan_regexps*/)
{
// For performance of Volnitsky search, it is crucial to save only one byte for pattern number.
if (needles_arr.size() > std::numeric_limits<UInt8>::max())
throw Exception(ErrorCodes::NUMBER_OF_ARGUMENTS_DOESNT_MATCH,
"Number of arguments for function {} doesn't match: passed {}, should be at most {}",
name, std::to_string(needles_arr.size()), std::to_string(std::numeric_limits<UInt8>::max()));
std::vector<std::string_view> needles;
needles.reserve(needles_arr.size());
for (const auto & needle : needles_arr)
needles.emplace_back(needle.get<String>());
auto res_callback = [](const UInt8 * start, const UInt8 * end) -> UInt64
{
return 1 + Impl::countChars(reinterpret_cast<const char *>(start), reinterpret_cast<const char *>(end));
};
auto searcher = Impl::createMultiSearcherInBigHaystack(needles);
const size_t haystack_size = haystack_offsets.size();
res.resize(haystack_size);
size_t iteration = 0;
while (searcher.hasMoreToSearch())
{
size_t prev_haystack_offset = 0;
for (size_t j = 0; j < haystack_size; ++j)
{
const auto * haystack = &haystack_data[prev_haystack_offset];
const auto * haystack_end = haystack + haystack_offsets[j] - prev_haystack_offset - 1;
if (iteration == 0 || res[j] == 0)
res[j] = searcher.searchOneFirstPosition(haystack, haystack_end, res_callback);
else
{
UInt64 result = searcher.searchOneFirstPosition(haystack, haystack_end, res_callback);
if (result != 0)
res[j] = std::min(result, res[j]);
}
prev_haystack_offset = haystack_offsets[j];
}
++iteration;
}
if (iteration == 0)
std::fill(res.begin(), res.end(), 0);
}
static void vectorVector(
const ColumnString::Chars & haystack_data,
const ColumnString::Offsets & haystack_offsets,
const IColumn & needles_data,
const ColumnArray::Offsets & needles_offsets,
PaddedPODArray<ResultType> & res,
PaddedPODArray<UInt64> & /*offsets*/,
bool /*allow_hyperscan*/,
size_t /*max_hyperscan_regexp_length*/,
size_t /*max_hyperscan_regexp_total_length*/,
bool /*reject_expensive_hyperscan_regexps*/)
{
const size_t haystack_size = haystack_offsets.size();
res.resize(haystack_size);
size_t prev_haystack_offset = 0;
size_t prev_needles_offset = 0;
const ColumnString * needles_data_string = checkAndGetColumn<ColumnString>(&needles_data);
std::vector<std::string_view> needles;
auto res_callback = [](const UInt8 * start, const UInt8 * end) -> UInt64
{
return 1 + Impl::countChars(reinterpret_cast<const char *>(start), reinterpret_cast<const char *>(end));
};
for (size_t i = 0; i < haystack_size; ++i)
{
needles.reserve(needles_offsets[i] - prev_needles_offset);
for (size_t j = prev_needles_offset; j < needles_offsets[i]; ++j)
{
needles.emplace_back(needles_data_string->getDataAt(j).toView());
}
auto searcher = Impl::createMultiSearcherInBigHaystack(needles); // sub-optimal
const auto * const haystack = &haystack_data[prev_haystack_offset];
const auto * haystack_end = haystack + haystack_offsets[i] - prev_haystack_offset - 1;
size_t iteration = 0;
while (searcher.hasMoreToSearch())
{
if (iteration == 0 || res[i] == 0)
{
res[i] = searcher.searchOneFirstPosition(haystack, haystack_end, res_callback);
}
else
{
UInt64 result = searcher.searchOneFirstPosition(haystack, haystack_end, res_callback);
if (result != 0)
{
res[i] = std::min(result, res[i]);
}
}
++iteration;
}
if (iteration == 0)
{
res[i] = 0;
}
prev_haystack_offset = haystack_offsets[i];
prev_needles_offset = needles_offsets[i];
needles.clear();
}
}
};
}
|
