You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by we...@apache.org on 2022/07/13 19:52:58 UTC
[arrow] branch master updated: ARROW-14182: [C++][Compute] Hash Join performance improvement v2 (#13493)
This is an automated email from the ASF dual-hosted git repository.
westonpace pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/arrow.git
The following commit(s) were added to refs/heads/master by this push:
new 96a3af437b ARROW-14182: [C++][Compute] Hash Join performance improvement v2 (#13493)
96a3af437b is described below
commit 96a3af437bfc498b75b832b161df378ad96cae1c
Author: michalursa <76...@users.noreply.github.com>
AuthorDate: Wed Jul 13 12:52:51 2022 -0700
ARROW-14182: [C++][Compute] Hash Join performance improvement v2 (#13493)
Faster implementation of hash join.
Authored-by: michalursa <mi...@ursacomputing.com>
Signed-off-by: Weston Pace <we...@gmail.com>
---
cpp/src/arrow/CMakeLists.txt | 2 +
cpp/src/arrow/compute/exec/hash_join.cc | 116 +-
cpp/src/arrow/compute/exec/hash_join.h | 75 +-
cpp/src/arrow/compute/exec/hash_join_benchmark.cc | 17 +-
cpp/src/arrow/compute/exec/hash_join_node.cc | 70 +-
.../compute/exec/{hash_join.h => hash_join_node.h} | 38 +-
cpp/src/arrow/compute/exec/key_hash.cc | 4 +-
cpp/src/arrow/compute/exec/key_hash.h | 2 +
cpp/src/arrow/compute/exec/key_map.cc | 206 +-
cpp/src/arrow/compute/exec/key_map.h | 105 +-
cpp/src/arrow/compute/exec/key_map_avx2.cc | 54 +-
cpp/src/arrow/compute/exec/partition_util.h | 48 +
cpp/src/arrow/compute/exec/schema_util.h | 71 +-
cpp/src/arrow/compute/exec/swiss_join.cc | 2526 ++++++++++++++++++++
cpp/src/arrow/compute/exec/swiss_join.h | 761 ++++++
cpp/src/arrow/compute/exec/swiss_join_avx2.cc | 197 ++
cpp/src/arrow/compute/exec/util.h | 49 +-
cpp/src/arrow/compute/exec/util_test.cc | 2 +-
cpp/src/arrow/compute/row/compare_internal.cc | 122 +-
cpp/src/arrow/compute/row/compare_internal.h | 25 +-
cpp/src/arrow/compute/row/compare_internal_avx2.cc | 95 +-
cpp/src/arrow/compute/row/encode_internal.cc | 40 +-
cpp/src/arrow/compute/row/encode_internal.h | 13 +-
cpp/src/arrow/compute/row/grouper.cc | 40 +-
cpp/src/arrow/compute/row/row_internal.cc | 4 +
cpp/src/arrow/compute/row/row_internal.h | 3 +
docs/source/python/compute.rst | 8 +-
python/pyarrow/table.pxi | 188 +-
python/pyarrow/tests/test_exec_plan.py | 30 +-
29 files changed, 4317 insertions(+), 594 deletions(-)
diff --git a/cpp/src/arrow/CMakeLists.txt b/cpp/src/arrow/CMakeLists.txt
index ac07ccf4b7..93dd1297bd 100644
--- a/cpp/src/arrow/CMakeLists.txt
+++ b/cpp/src/arrow/CMakeLists.txt
@@ -404,6 +404,7 @@ if(ARROW_COMPUTE)
compute/exec/project_node.cc
compute/exec/sink_node.cc
compute/exec/source_node.cc
+ compute/exec/swiss_join.cc
compute/exec/task_util.cc
compute/exec/tpch_node.cc
compute/exec/union_node.cc
@@ -459,6 +460,7 @@ if(ARROW_COMPUTE)
append_avx2_src(compute/exec/bloom_filter_avx2.cc)
append_avx2_src(compute/exec/key_hash_avx2.cc)
append_avx2_src(compute/exec/key_map_avx2.cc)
+ append_avx2_src(compute/exec/swiss_join_avx2.cc)
append_avx2_src(compute/exec/util_avx2.cc)
append_avx2_src(compute/row/compare_internal_avx2.cc)
append_avx2_src(compute/row/encode_internal_avx2.cc)
diff --git a/cpp/src/arrow/compute/exec/hash_join.cc b/cpp/src/arrow/compute/exec/hash_join.cc
index a376fb5f57..e821979ae1 100644
--- a/cpp/src/arrow/compute/exec/hash_join.cc
+++ b/cpp/src/arrow/compute/exec/hash_join.cc
@@ -41,18 +41,21 @@ class HashJoinBasicImpl : public HashJoinImpl {
public:
Status Init(ExecContext* ctx, JoinType join_type, size_t num_threads,
- HashJoinSchema* schema_mgr, std::vector<JoinKeyCmp> key_cmp,
- Expression filter, OutputBatchCallback output_batch_callback,
+ const HashJoinProjectionMaps* proj_map_left,
+ const HashJoinProjectionMaps* proj_map_right,
+ std::vector<JoinKeyCmp> key_cmp, Expression filter,
+ OutputBatchCallback output_batch_callback,
FinishedCallback finished_callback, TaskScheduler* scheduler) override {
START_COMPUTE_SPAN(span_, "HashJoinBasicImpl",
{{"detail", filter.ToString()},
- {"join.kind", ToString(join_type)},
+ {"join.kind", arrow::compute::ToString(join_type)},
{"join.threads", static_cast<uint32_t>(num_threads)}});
num_threads_ = num_threads;
ctx_ = ctx;
join_type_ = join_type;
- schema_mgr_ = schema_mgr;
+ schema_[0] = proj_map_left;
+ schema_[1] = proj_map_right;
key_cmp_ = std::move(key_cmp);
filter_ = std::move(filter);
output_batch_callback_ = std::move(output_batch_callback);
@@ -82,13 +85,15 @@ class HashJoinBasicImpl : public HashJoinImpl {
scheduler_->Abort(std::move(pos_abort_callback));
}
+ std::string ToString() const override { return "HashJoinBasicImpl"; }
+
private:
void InitEncoder(int side, HashJoinProjection projection_handle, RowEncoder* encoder) {
std::vector<TypeHolder> data_types;
- int num_cols = schema_mgr_->proj_maps[side].num_cols(projection_handle);
+ int num_cols = schema_[side]->num_cols(projection_handle);
data_types.resize(num_cols);
for (int icol = 0; icol < num_cols; ++icol) {
- data_types[icol] = schema_mgr_->proj_maps[side].data_type(projection_handle, icol);
+ data_types[icol] = schema_[side]->data_type(projection_handle, icol);
}
encoder->Init(data_types, ctx_);
encoder->Clear();
@@ -99,8 +104,7 @@ class HashJoinBasicImpl : public HashJoinImpl {
ThreadLocalState& local_state = local_states_[thread_index];
if (!local_state.is_initialized) {
InitEncoder(0, HashJoinProjection::KEY, &local_state.exec_batch_keys);
- bool has_payload =
- (schema_mgr_->proj_maps[0].num_cols(HashJoinProjection::PAYLOAD) > 0);
+ bool has_payload = (schema_[0]->num_cols(HashJoinProjection::PAYLOAD) > 0);
if (has_payload) {
InitEncoder(0, HashJoinProjection::PAYLOAD, &local_state.exec_batch_payloads);
}
@@ -112,11 +116,10 @@ class HashJoinBasicImpl : public HashJoinImpl {
Status EncodeBatch(int side, HashJoinProjection projection_handle, RowEncoder* encoder,
const ExecBatch& batch, ExecBatch* opt_projected_batch = nullptr) {
ExecBatch projected({}, batch.length);
- int num_cols = schema_mgr_->proj_maps[side].num_cols(projection_handle);
+ int num_cols = schema_[side]->num_cols(projection_handle);
projected.values.resize(num_cols);
- auto to_input =
- schema_mgr_->proj_maps[side].map(projection_handle, HashJoinProjection::INPUT);
+ auto to_input = schema_[side]->map(projection_handle, HashJoinProjection::INPUT);
for (int icol = 0; icol < num_cols; ++icol) {
projected.values[icol] = batch.values[to_input.get(icol)];
}
@@ -179,19 +182,17 @@ class HashJoinBasicImpl : public HashJoinImpl {
ExecBatch* opt_left_payload, ExecBatch* opt_right_key,
ExecBatch* opt_right_payload) {
ExecBatch result({}, batch_size_next);
- int num_out_cols_left =
- schema_mgr_->proj_maps[0].num_cols(HashJoinProjection::OUTPUT);
- int num_out_cols_right =
- schema_mgr_->proj_maps[1].num_cols(HashJoinProjection::OUTPUT);
+ int num_out_cols_left = schema_[0]->num_cols(HashJoinProjection::OUTPUT);
+ int num_out_cols_right = schema_[1]->num_cols(HashJoinProjection::OUTPUT);
result.values.resize(num_out_cols_left + num_out_cols_right);
- auto from_key = schema_mgr_->proj_maps[0].map(HashJoinProjection::OUTPUT,
- HashJoinProjection::KEY);
- auto from_payload = schema_mgr_->proj_maps[0].map(HashJoinProjection::OUTPUT,
- HashJoinProjection::PAYLOAD);
+ auto from_key = schema_[0]->map(HashJoinProjection::OUTPUT, HashJoinProjection::KEY);
+ auto from_payload =
+ schema_[0]->map(HashJoinProjection::OUTPUT, HashJoinProjection::PAYLOAD);
for (int icol = 0; icol < num_out_cols_left; ++icol) {
- bool is_from_key = (from_key.get(icol) != HashJoinSchema::kMissingField());
- bool is_from_payload = (from_payload.get(icol) != HashJoinSchema::kMissingField());
+ bool is_from_key = (from_key.get(icol) != HashJoinProjectionMaps::kMissingField);
+ bool is_from_payload =
+ (from_payload.get(icol) != HashJoinProjectionMaps::kMissingField);
ARROW_DCHECK(is_from_key != is_from_payload);
ARROW_DCHECK(!is_from_key ||
(opt_left_key &&
@@ -206,13 +207,13 @@ class HashJoinBasicImpl : public HashJoinImpl {
? opt_left_key->values[from_key.get(icol)]
: opt_left_payload->values[from_payload.get(icol)];
}
- from_key = schema_mgr_->proj_maps[1].map(HashJoinProjection::OUTPUT,
- HashJoinProjection::KEY);
- from_payload = schema_mgr_->proj_maps[1].map(HashJoinProjection::OUTPUT,
- HashJoinProjection::PAYLOAD);
+ from_key = schema_[1]->map(HashJoinProjection::OUTPUT, HashJoinProjection::KEY);
+ from_payload =
+ schema_[1]->map(HashJoinProjection::OUTPUT, HashJoinProjection::PAYLOAD);
for (int icol = 0; icol < num_out_cols_right; ++icol) {
- bool is_from_key = (from_key.get(icol) != HashJoinSchema::kMissingField());
- bool is_from_payload = (from_payload.get(icol) != HashJoinSchema::kMissingField());
+ bool is_from_key = (from_key.get(icol) != HashJoinProjectionMaps::kMissingField);
+ bool is_from_payload =
+ (from_payload.get(icol) != HashJoinProjectionMaps::kMissingField);
ARROW_DCHECK(is_from_key != is_from_payload);
ARROW_DCHECK(!is_from_key ||
(opt_right_key &&
@@ -228,7 +229,7 @@ class HashJoinBasicImpl : public HashJoinImpl {
: opt_right_payload->values[from_payload.get(icol)];
}
- output_batch_callback_(std::move(result));
+ output_batch_callback_(0, std::move(result));
// Update the counter of produced batches
//
@@ -254,13 +255,13 @@ class HashJoinBasicImpl : public HashJoinImpl {
hash_table_keys_.Decode(match_right.size(), match_right.data()));
ExecBatch left_payload;
- if (!schema_mgr_->LeftPayloadIsEmpty()) {
+ if (!schema_[0]->is_empty(HashJoinProjection::PAYLOAD)) {
ARROW_ASSIGN_OR_RAISE(left_payload, local_state.exec_batch_payloads.Decode(
match_left.size(), match_left.data()));
}
ExecBatch right_payload;
- if (!schema_mgr_->RightPayloadIsEmpty()) {
+ if (!schema_[1]->is_empty(HashJoinProjection::PAYLOAD)) {
ARROW_ASSIGN_OR_RAISE(right_payload, hash_table_payloads_.Decode(
match_right.size(), match_right.data()));
}
@@ -280,14 +281,14 @@ class HashJoinBasicImpl : public HashJoinImpl {
}
};
- SchemaProjectionMap left_to_key = schema_mgr_->proj_maps[0].map(
- HashJoinProjection::FILTER, HashJoinProjection::KEY);
- SchemaProjectionMap left_to_pay = schema_mgr_->proj_maps[0].map(
- HashJoinProjection::FILTER, HashJoinProjection::PAYLOAD);
- SchemaProjectionMap right_to_key = schema_mgr_->proj_maps[1].map(
- HashJoinProjection::FILTER, HashJoinProjection::KEY);
- SchemaProjectionMap right_to_pay = schema_mgr_->proj_maps[1].map(
- HashJoinProjection::FILTER, HashJoinProjection::PAYLOAD);
+ SchemaProjectionMap left_to_key =
+ schema_[0]->map(HashJoinProjection::FILTER, HashJoinProjection::KEY);
+ SchemaProjectionMap left_to_pay =
+ schema_[0]->map(HashJoinProjection::FILTER, HashJoinProjection::PAYLOAD);
+ SchemaProjectionMap right_to_key =
+ schema_[1]->map(HashJoinProjection::FILTER, HashJoinProjection::KEY);
+ SchemaProjectionMap right_to_pay =
+ schema_[1]->map(HashJoinProjection::FILTER, HashJoinProjection::PAYLOAD);
AppendFields(left_to_key, left_to_pay, left_key, left_payload);
AppendFields(right_to_key, right_to_pay, right_key, right_payload);
@@ -363,15 +364,14 @@ class HashJoinBasicImpl : public HashJoinImpl {
bool has_left =
(join_type_ != JoinType::RIGHT_SEMI && join_type_ != JoinType::RIGHT_ANTI &&
- schema_mgr_->proj_maps[0].num_cols(HashJoinProjection::OUTPUT) > 0);
+ schema_[0]->num_cols(HashJoinProjection::OUTPUT) > 0);
bool has_right =
(join_type_ != JoinType::LEFT_SEMI && join_type_ != JoinType::LEFT_ANTI &&
- schema_mgr_->proj_maps[1].num_cols(HashJoinProjection::OUTPUT) > 0);
+ schema_[1]->num_cols(HashJoinProjection::OUTPUT) > 0);
bool has_left_payload =
- has_left && (schema_mgr_->proj_maps[0].num_cols(HashJoinProjection::PAYLOAD) > 0);
+ has_left && (schema_[0]->num_cols(HashJoinProjection::PAYLOAD) > 0);
bool has_right_payload =
- has_right &&
- (schema_mgr_->proj_maps[1].num_cols(HashJoinProjection::PAYLOAD) > 0);
+ has_right && (schema_[1]->num_cols(HashJoinProjection::PAYLOAD) > 0);
ThreadLocalState& local_state = local_states_[thread_index];
RETURN_NOT_OK(InitLocalStateIfNeeded(thread_index));
@@ -394,7 +394,7 @@ class HashJoinBasicImpl : public HashJoinImpl {
ARROW_ASSIGN_OR_RAISE(right_key,
hash_table_keys_.Decode(batch_size_next, opt_right_ids));
// Post process build side keys that use dictionary
- RETURN_NOT_OK(dict_build_.PostDecode(schema_mgr_->proj_maps[1], &right_key, ctx_));
+ RETURN_NOT_OK(dict_build_.PostDecode(*schema_[1], &right_key, ctx_));
}
if (has_right_payload) {
ARROW_ASSIGN_OR_RAISE(right_payload,
@@ -494,8 +494,7 @@ class HashJoinBasicImpl : public HashJoinImpl {
RETURN_NOT_OK(EncodeBatch(0, HashJoinProjection::KEY, &local_state.exec_batch_keys,
batch, &batch_key_for_lookups));
- bool has_left_payload =
- (schema_mgr_->proj_maps[0].num_cols(HashJoinProjection::PAYLOAD) > 0);
+ bool has_left_payload = (schema_[0]->num_cols(HashJoinProjection::PAYLOAD) > 0);
if (has_left_payload) {
local_state.exec_batch_payloads.Clear();
RETURN_NOT_OK(EncodeBatch(0, HashJoinProjection::PAYLOAD,
@@ -507,13 +506,13 @@ class HashJoinBasicImpl : public HashJoinImpl {
local_state.match_left.clear();
local_state.match_right.clear();
- bool use_key_batch_for_dicts = dict_probe_.BatchRemapNeeded(
- thread_index, schema_mgr_->proj_maps[0], schema_mgr_->proj_maps[1], ctx_);
+ bool use_key_batch_for_dicts =
+ dict_probe_.BatchRemapNeeded(thread_index, *schema_[0], *schema_[1], ctx_);
RowEncoder* row_encoder_for_lookups = &local_state.exec_batch_keys;
if (use_key_batch_for_dicts) {
- RETURN_NOT_OK(dict_probe_.EncodeBatch(
- thread_index, schema_mgr_->proj_maps[0], schema_mgr_->proj_maps[1], dict_build_,
- batch, &row_encoder_for_lookups, &batch_key_for_lookups, ctx_));
+ RETURN_NOT_OK(dict_probe_.EncodeBatch(thread_index, *schema_[0], *schema_[1],
+ dict_build_, batch, &row_encoder_for_lookups,
+ &batch_key_for_lookups, ctx_));
}
// Collect information about all nulls in key columns.
@@ -561,9 +560,8 @@ class HashJoinBasicImpl : public HashJoinImpl {
if (batches.empty()) {
hash_table_empty_ = true;
} else {
- dict_build_.InitEncoder(schema_mgr_->proj_maps[1], &hash_table_keys_, ctx_);
- bool has_payload =
- (schema_mgr_->proj_maps[1].num_cols(HashJoinProjection::PAYLOAD) > 0);
+ dict_build_.InitEncoder(*schema_[1], &hash_table_keys_, ctx_);
+ bool has_payload = (schema_[1]->num_cols(HashJoinProjection::PAYLOAD) > 0);
if (has_payload) {
InitEncoder(1, HashJoinProjection::PAYLOAD, &hash_table_payloads_);
}
@@ -578,11 +576,11 @@ class HashJoinBasicImpl : public HashJoinImpl {
} else if (hash_table_empty_) {
hash_table_empty_ = false;
- RETURN_NOT_OK(dict_build_.Init(schema_mgr_->proj_maps[1], &batch, ctx_));
+ RETURN_NOT_OK(dict_build_.Init(*schema_[1], &batch, ctx_));
}
int32_t num_rows_before = hash_table_keys_.num_rows();
- RETURN_NOT_OK(dict_build_.EncodeBatch(thread_index, schema_mgr_->proj_maps[1],
- batch, &hash_table_keys_, ctx_));
+ RETURN_NOT_OK(dict_build_.EncodeBatch(thread_index, *schema_[1], batch,
+ &hash_table_keys_, ctx_));
if (has_payload) {
RETURN_NOT_OK(
EncodeBatch(1, HashJoinProjection::PAYLOAD, &hash_table_payloads_, batch));
@@ -595,7 +593,7 @@ class HashJoinBasicImpl : public HashJoinImpl {
}
if (hash_table_empty_) {
- RETURN_NOT_OK(dict_build_.Init(schema_mgr_->proj_maps[1], nullptr, ctx_));
+ RETURN_NOT_OK(dict_build_.Init(*schema_[1], nullptr, ctx_));
}
return Status::OK();
@@ -740,7 +738,7 @@ class HashJoinBasicImpl : public HashJoinImpl {
ExecContext* ctx_;
JoinType join_type_;
size_t num_threads_;
- HashJoinSchema* schema_mgr_;
+ const HashJoinProjectionMaps* schema_[2];
std::vector<JoinKeyCmp> key_cmp_;
Expression filter_;
TaskScheduler* scheduler_;
diff --git a/cpp/src/arrow/compute/exec/hash_join.h b/cpp/src/arrow/compute/exec/hash_join.h
index 97bdf166a0..19add7d440 100644
--- a/cpp/src/arrow/compute/exec/hash_join.h
+++ b/cpp/src/arrow/compute/exec/hash_join.h
@@ -36,81 +36,18 @@ namespace compute {
using arrow::util::AccumulationQueue;
-class ARROW_EXPORT HashJoinSchema {
- public:
- Status Init(JoinType join_type, const Schema& left_schema,
- const std::vector<FieldRef>& left_keys, const Schema& right_schema,
- const std::vector<FieldRef>& right_keys, const Expression& filter,
- const std::string& left_field_name_prefix,
- const std::string& right_field_name_prefix);
-
- Status Init(JoinType join_type, const Schema& left_schema,
- const std::vector<FieldRef>& left_keys,
- const std::vector<FieldRef>& left_output, const Schema& right_schema,
- const std::vector<FieldRef>& right_keys,
- const std::vector<FieldRef>& right_output, const Expression& filter,
- const std::string& left_field_name_prefix,
- const std::string& right_field_name_prefix);
-
- static Status ValidateSchemas(JoinType join_type, const Schema& left_schema,
- const std::vector<FieldRef>& left_keys,
- const std::vector<FieldRef>& left_output,
- const Schema& right_schema,
- const std::vector<FieldRef>& right_keys,
- const std::vector<FieldRef>& right_output,
- const std::string& left_field_name_prefix,
- const std::string& right_field_name_prefix);
-
- Result<Expression> BindFilter(Expression filter, const Schema& left_schema,
- const Schema& right_schema, ExecContext* exec_context);
- std::shared_ptr<Schema> MakeOutputSchema(const std::string& left_field_name_suffix,
- const std::string& right_field_name_suffix);
-
- bool LeftPayloadIsEmpty() { return PayloadIsEmpty(0); }
-
- bool RightPayloadIsEmpty() { return PayloadIsEmpty(1); }
-
- static int kMissingField() {
- return SchemaProjectionMaps<HashJoinProjection>::kMissingField;
- }
-
- SchemaProjectionMaps<HashJoinProjection> proj_maps[2];
-
- private:
- static bool IsTypeSupported(const DataType& type);
-
- Status CollectFilterColumns(std::vector<FieldRef>& left_filter,
- std::vector<FieldRef>& right_filter,
- const Expression& filter, const Schema& left_schema,
- const Schema& right_schema);
-
- Expression RewriteFilterToUseFilterSchema(int right_filter_offset,
- const SchemaProjectionMap& left_to_filter,
- const SchemaProjectionMap& right_to_filter,
- const Expression& filter);
-
- bool PayloadIsEmpty(int side) {
- ARROW_DCHECK(side == 0 || side == 1);
- return proj_maps[side].num_cols(HashJoinProjection::PAYLOAD) == 0;
- }
-
- static Result<std::vector<FieldRef>> ComputePayload(const Schema& schema,
- const std::vector<FieldRef>& output,
- const std::vector<FieldRef>& filter,
- const std::vector<FieldRef>& key);
-};
-
class HashJoinImpl {
public:
- using OutputBatchCallback = std::function<void(ExecBatch)>;
+ using OutputBatchCallback = std::function<void(int64_t, ExecBatch)>;
using BuildFinishedCallback = std::function<Status(size_t)>;
- using ProbeFinishedCallback = std::function<Status(size_t)>;
using FinishedCallback = std::function<void(int64_t)>;
virtual ~HashJoinImpl() = default;
virtual Status Init(ExecContext* ctx, JoinType join_type, size_t num_threads,
- HashJoinSchema* schema_mgr, std::vector<JoinKeyCmp> key_cmp,
- Expression filter, OutputBatchCallback output_batch_callback,
+ const HashJoinProjectionMaps* proj_map_left,
+ const HashJoinProjectionMaps* proj_map_right,
+ std::vector<JoinKeyCmp> key_cmp, Expression filter,
+ OutputBatchCallback output_batch_callback,
FinishedCallback finished_callback, TaskScheduler* scheduler) = 0;
virtual Status BuildHashTable(size_t thread_index, AccumulationQueue batches,
@@ -118,8 +55,10 @@ class HashJoinImpl {
virtual Status ProbeSingleBatch(size_t thread_index, ExecBatch batch) = 0;
virtual Status ProbingFinished(size_t thread_index) = 0;
virtual void Abort(TaskScheduler::AbortContinuationImpl pos_abort_callback) = 0;
+ virtual std::string ToString() const = 0;
static Result<std::unique_ptr<HashJoinImpl>> MakeBasic();
+ static Result<std::unique_ptr<HashJoinImpl>> MakeSwiss();
protected:
util::tracing::Span span_;
diff --git a/cpp/src/arrow/compute/exec/hash_join_benchmark.cc b/cpp/src/arrow/compute/exec/hash_join_benchmark.cc
index 0786071f99..97badb8423 100644
--- a/cpp/src/arrow/compute/exec/hash_join_benchmark.cc
+++ b/cpp/src/arrow/compute/exec/hash_join_benchmark.cc
@@ -38,6 +38,9 @@ namespace compute {
struct BenchmarkSettings {
int num_threads = 1;
JoinType join_type = JoinType::INNER;
+ // Change to 'true' to benchmark alternative, non-default and less optimized version of
+ // a hash join node implementation.
+ bool use_basic_implementation = false;
int batch_size = 1024;
int num_build_batches = 32;
int num_probe_batches = 32 * 16;
@@ -78,6 +81,8 @@ class JoinBenchmark {
build_metadata["null_probability"] = std::to_string(settings.null_percentage);
build_metadata["min"] = std::to_string(min_build_value);
build_metadata["max"] = std::to_string(max_build_value);
+ build_metadata["min_length"] = "2";
+ build_metadata["max_length"] = "20";
std::unordered_map<std::string, std::string> probe_metadata;
probe_metadata["null_probability"] = std::to_string(settings.null_percentage);
@@ -132,7 +137,11 @@ class JoinBenchmark {
left_keys, *r_batches_with_schema.schema, right_keys,
filter, "l_", "r_"));
- join_ = *HashJoinImpl::MakeBasic();
+ if (settings.use_basic_implementation) {
+ join_ = *HashJoinImpl::MakeBasic();
+ } else {
+ join_ = *HashJoinImpl::MakeSwiss();
+ }
omp_set_num_threads(settings.num_threads);
auto schedule_callback = [](std::function<Status(size_t)> func) -> Status {
@@ -143,9 +152,9 @@ class JoinBenchmark {
scheduler_ = TaskScheduler::Make();
DCHECK_OK(join_->Init(
- ctx_.get(), settings.join_type, settings.num_threads, schema_mgr_.get(),
- std::move(key_cmp), std::move(filter), [](ExecBatch) {}, [](int64_t x) {},
- scheduler_.get()));
+ ctx_.get(), settings.join_type, settings.num_threads,
+ &(schema_mgr_->proj_maps[0]), &(schema_mgr_->proj_maps[1]), std::move(key_cmp),
+ std::move(filter), [](ExecBatch) {}, [](int64_t x) {}, scheduler_.get()));
task_group_probe_ = scheduler_->RegisterTaskGroup(
[this](size_t thread_index, int64_t task_id) -> Status {
diff --git a/cpp/src/arrow/compute/exec/hash_join_node.cc b/cpp/src/arrow/compute/exec/hash_join_node.cc
index baa8267125..73df78b46e 100644
--- a/cpp/src/arrow/compute/exec/hash_join_node.cc
+++ b/cpp/src/arrow/compute/exec/hash_join_node.cc
@@ -22,6 +22,7 @@
#include "arrow/compute/exec/exec_plan.h"
#include "arrow/compute/exec/hash_join.h"
#include "arrow/compute/exec/hash_join_dict.h"
+#include "arrow/compute/exec/hash_join_node.h"
#include "arrow/compute/exec/key_hash.h"
#include "arrow/compute/exec/options.h"
#include "arrow/compute/exec/schema_util.h"
@@ -560,7 +561,8 @@ struct BloomFilterPushdownContext {
}
}
ARROW_ASSIGN_OR_RAISE(ExecBatch key_batch, ExecBatch::Make(std::move(keys)));
- RETURN_NOT_OK(Hashing32::HashBatch(key_batch, hashes.data(),
+ std::vector<KeyColumnArray> temp_column_arrays;
+ RETURN_NOT_OK(Hashing32::HashBatch(key_batch, hashes.data(), temp_column_arrays,
ctx_->cpu_info()->hardware_flags(), stack, 0,
key_batch.length));
@@ -654,6 +656,33 @@ struct BloomFilterPushdownContext {
FilterFinishedCallback on_finished_;
} eval_;
};
+bool HashJoinSchema::HasDictionaries() const {
+ for (int side = 0; side <= 1; ++side) {
+ for (int icol = 0; icol < proj_maps[side].num_cols(HashJoinProjection::INPUT);
+ ++icol) {
+ const std::shared_ptr<DataType>& column_type =
+ proj_maps[side].data_type(HashJoinProjection::INPUT, icol);
+ if (column_type->id() == Type::DICTIONARY) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+bool HashJoinSchema::HasLargeBinary() const {
+ for (int side = 0; side <= 1; ++side) {
+ for (int icol = 0; icol < proj_maps[side].num_cols(HashJoinProjection::INPUT);
+ ++icol) {
+ const std::shared_ptr<DataType>& column_type =
+ proj_maps[side].data_type(HashJoinProjection::INPUT, icol);
+ if (is_large_binary_like(column_type->id())) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
class HashJoinNode : public ExecNode {
public:
@@ -708,8 +737,26 @@ class HashJoinNode : public ExecNode {
// Generate output schema
std::shared_ptr<Schema> output_schema = schema_mgr->MakeOutputSchema(
join_options.output_suffix_for_left, join_options.output_suffix_for_right);
+
// Create hash join implementation object
- ARROW_ASSIGN_OR_RAISE(std::unique_ptr<HashJoinImpl> impl, HashJoinImpl::MakeBasic());
+ // SwissJoin does not support:
+ // a) 64-bit string offsets
+ // b) residual predicates
+ // c) dictionaries
+ //
+ bool use_swiss_join;
+#if ARROW_LITTLE_ENDIAN
+ use_swiss_join = (filter == literal(true)) && !schema_mgr->HasDictionaries() &&
+ !schema_mgr->HasLargeBinary();
+#else
+ use_swiss_join = false;
+#endif
+ std::unique_ptr<HashJoinImpl> impl;
+ if (use_swiss_join) {
+ ARROW_ASSIGN_OR_RAISE(impl, HashJoinImpl::MakeSwiss());
+ } else {
+ ARROW_ASSIGN_OR_RAISE(impl, HashJoinImpl::MakeBasic());
+ }
return plan->EmplaceNode<HashJoinNode>(
plan, inputs, join_options, std::move(output_schema), std::move(schema_mgr),
@@ -907,8 +954,11 @@ class HashJoinNode : public ExecNode {
disable_bloom_filter_, use_sync_execution);
RETURN_NOT_OK(impl_->Init(
- plan_->exec_context(), join_type_, num_threads, schema_mgr_.get(), key_cmp_,
- filter_, [this](ExecBatch batch) { this->OutputBatchCallback(batch); },
+ plan_->exec_context(), join_type_, num_threads, &(schema_mgr_->proj_maps[0]),
+ &(schema_mgr_->proj_maps[1]), key_cmp_, filter_,
+ [this](int64_t /*ignored*/, ExecBatch batch) {
+ this->OutputBatchCallback(batch);
+ },
[this](int64_t total_num_batches) { this->FinishedCallback(total_num_batches); },
scheduler_.get()));
@@ -968,6 +1018,11 @@ class HashJoinNode : public ExecNode {
Future<> finished() override { return task_group_.OnFinished(); }
+ protected:
+ std::string ToStringExtra(int indent = 0) const override {
+ return "implementation=" + impl_->ToString();
+ }
+
private:
void OutputBatchCallback(ExecBatch batch) {
outputs_[0]->InputReceived(this, std::move(batch));
@@ -1124,8 +1179,11 @@ Status BloomFilterPushdownContext::BuildBloomFilter_exec_task(size_t thread_inde
for (int64_t i = 0; i < key_batch.length; i += util::MiniBatch::kMiniBatchLength) {
int64_t length = std::min(static_cast<int64_t>(key_batch.length - i),
static_cast<int64_t>(util::MiniBatch::kMiniBatchLength));
- RETURN_NOT_OK(Hashing32::HashBatch(
- key_batch, hashes, ctx_->cpu_info()->hardware_flags(), stack, i, length));
+
+ std::vector<KeyColumnArray> temp_column_arrays;
+ RETURN_NOT_OK(Hashing32::HashBatch(key_batch, hashes, temp_column_arrays,
+ ctx_->cpu_info()->hardware_flags(), stack, i,
+ length));
RETURN_NOT_OK(build_.builder_->PushNextBatch(thread_index, length, hashes));
}
return Status::OK();
diff --git a/cpp/src/arrow/compute/exec/hash_join.h b/cpp/src/arrow/compute/exec/hash_join_node.h
similarity index 75%
copy from cpp/src/arrow/compute/exec/hash_join.h
copy to cpp/src/arrow/compute/exec/hash_join_node.h
index 97bdf166a0..8dc7ea0b8b 100644
--- a/cpp/src/arrow/compute/exec/hash_join.h
+++ b/cpp/src/arrow/compute/exec/hash_join_node.h
@@ -17,25 +17,16 @@
#pragma once
-#include <functional>
-#include <memory>
#include <vector>
-#include "arrow/compute/exec/accumulation_queue.h"
-#include "arrow/compute/exec/bloom_filter.h"
#include "arrow/compute/exec/options.h"
#include "arrow/compute/exec/schema_util.h"
-#include "arrow/compute/exec/task_util.h"
#include "arrow/result.h"
#include "arrow/status.h"
-#include "arrow/type.h"
-#include "arrow/util/tracing.h"
namespace arrow {
namespace compute {
-using arrow::util::AccumulationQueue;
-
class ARROW_EXPORT HashJoinSchema {
public:
Status Init(JoinType join_type, const Schema& left_schema,
@@ -61,6 +52,10 @@ class ARROW_EXPORT HashJoinSchema {
const std::string& left_field_name_prefix,
const std::string& right_field_name_prefix);
+ bool HasDictionaries() const;
+
+ bool HasLargeBinary() const;
+
Result<Expression> BindFilter(Expression filter, const Schema& left_schema,
const Schema& right_schema, ExecContext* exec_context);
std::shared_ptr<Schema> MakeOutputSchema(const std::string& left_field_name_suffix,
@@ -100,30 +95,5 @@ class ARROW_EXPORT HashJoinSchema {
const std::vector<FieldRef>& key);
};
-class HashJoinImpl {
- public:
- using OutputBatchCallback = std::function<void(ExecBatch)>;
- using BuildFinishedCallback = std::function<Status(size_t)>;
- using ProbeFinishedCallback = std::function<Status(size_t)>;
- using FinishedCallback = std::function<void(int64_t)>;
-
- virtual ~HashJoinImpl() = default;
- virtual Status Init(ExecContext* ctx, JoinType join_type, size_t num_threads,
- HashJoinSchema* schema_mgr, std::vector<JoinKeyCmp> key_cmp,
- Expression filter, OutputBatchCallback output_batch_callback,
- FinishedCallback finished_callback, TaskScheduler* scheduler) = 0;
-
- virtual Status BuildHashTable(size_t thread_index, AccumulationQueue batches,
- BuildFinishedCallback on_finished) = 0;
- virtual Status ProbeSingleBatch(size_t thread_index, ExecBatch batch) = 0;
- virtual Status ProbingFinished(size_t thread_index) = 0;
- virtual void Abort(TaskScheduler::AbortContinuationImpl pos_abort_callback) = 0;
-
- static Result<std::unique_ptr<HashJoinImpl>> MakeBasic();
-
- protected:
- util::tracing::Span span_;
-};
-
} // namespace compute
} // namespace arrow
diff --git a/cpp/src/arrow/compute/exec/key_hash.cc b/cpp/src/arrow/compute/exec/key_hash.cc
index 5a5d524c40..3f495bc9e6 100644
--- a/cpp/src/arrow/compute/exec/key_hash.cc
+++ b/cpp/src/arrow/compute/exec/key_hash.cc
@@ -458,9 +458,9 @@ void Hashing32::HashMultiColumn(const std::vector<KeyColumnArray>& cols,
}
Status Hashing32::HashBatch(const ExecBatch& key_batch, uint32_t* hashes,
+ std::vector<KeyColumnArray>& column_arrays,
int64_t hardware_flags, util::TempVectorStack* temp_stack,
int64_t offset, int64_t length) {
- std::vector<KeyColumnArray> column_arrays;
RETURN_NOT_OK(ColumnArraysFromExecBatch(key_batch, offset, length, &column_arrays));
LightContext ctx;
@@ -890,9 +890,9 @@ void Hashing64::HashMultiColumn(const std::vector<KeyColumnArray>& cols,
}
Status Hashing64::HashBatch(const ExecBatch& key_batch, uint64_t* hashes,
+ std::vector<KeyColumnArray>& column_arrays,
int64_t hardware_flags, util::TempVectorStack* temp_stack,
int64_t offset, int64_t length) {
- std::vector<KeyColumnArray> column_arrays;
RETURN_NOT_OK(ColumnArraysFromExecBatch(key_batch, offset, length, &column_arrays));
LightContext ctx;
diff --git a/cpp/src/arrow/compute/exec/key_hash.h b/cpp/src/arrow/compute/exec/key_hash.h
index f8af798838..68197973e0 100644
--- a/cpp/src/arrow/compute/exec/key_hash.h
+++ b/cpp/src/arrow/compute/exec/key_hash.h
@@ -49,6 +49,7 @@ class ARROW_EXPORT Hashing32 {
uint32_t* out_hash);
static Status HashBatch(const ExecBatch& key_batch, uint32_t* hashes,
+ std::vector<KeyColumnArray>& column_arrays,
int64_t hardware_flags, util::TempVectorStack* temp_stack,
int64_t offset, int64_t length);
@@ -161,6 +162,7 @@ class ARROW_EXPORT Hashing64 {
uint64_t* hashes);
static Status HashBatch(const ExecBatch& key_batch, uint64_t* hashes,
+ std::vector<KeyColumnArray>& column_arrays,
int64_t hardware_flags, util::TempVectorStack* temp_stack,
int64_t offset, int64_t length);
diff --git a/cpp/src/arrow/compute/exec/key_map.cc b/cpp/src/arrow/compute/exec/key_map.cc
index fe5ed98bb3..a61184e4ca 100644
--- a/cpp/src/arrow/compute/exec/key_map.cc
+++ b/cpp/src/arrow/compute/exec/key_map.cc
@@ -42,8 +42,8 @@ constexpr uint64_t kHighBitOfEachByte = 0x8080808080808080ULL;
// b) first empty slot is encountered,
// c) we reach the end of the block.
//
-// Optionally an index of the first slot to start the search from can be specified.
-// In this case slots before it will be ignored.
+// Optionally an index of the first slot to start the search from can be specified. In
+// this case slots before it will be ignored.
//
template <bool use_start_slot>
inline void SwissTable::search_block(uint64_t block, int stamp, int start_slot,
@@ -88,29 +88,12 @@ inline void SwissTable::search_block(uint64_t block, int stamp, int start_slot,
// We get 0 if there are no matches
*out_match_found = (matches == 0 ? 0 : 1);
- // Now if we or with the highest bits of the block and scan zero bits in reverse,
- // we get 8x slot index that we were looking for.
- // This formula works in all three cases a), b) and c).
+ // Now if we or with the highest bits of the block and scan zero bits in reverse, we get
+ // 8x slot index that we were looking for. This formula works in all three cases a), b)
+ // and c).
*out_slot = static_cast<int>(CountLeadingZeros(matches | block_high_bits) >> 3);
}
-inline uint64_t SwissTable::extract_group_id(const uint8_t* block_ptr, int slot,
- uint64_t group_id_mask) const {
- // Group id values for all 8 slots in the block are bit-packed and follow the status
- // bytes. We assume here that the number of bits is rounded up to 8, 16, 32 or 64. In
- // that case we can extract group id using aligned 64-bit word access.
- int num_group_id_bits = static_cast<int>(ARROW_POPCOUNT64(group_id_mask));
- ARROW_DCHECK(num_group_id_bits == 8 || num_group_id_bits == 16 ||
- num_group_id_bits == 32 || num_group_id_bits == 64);
-
- int bit_offset = slot * num_group_id_bits;
- const uint64_t* group_id_bytes =
- reinterpret_cast<const uint64_t*>(block_ptr) + 1 + (bit_offset >> 6);
- uint64_t group_id = (*group_id_bytes >> (bit_offset & 63)) & group_id_mask;
-
- return group_id;
-}
-
template <typename T, bool use_selection>
void SwissTable::extract_group_ids_imp(const int num_keys, const uint16_t* selection,
const uint32_t* hashes, const uint8_t* local_slots,
@@ -147,14 +130,16 @@ void SwissTable::extract_group_ids(const int num_keys, const uint16_t* optional_
ARROW_DCHECK(num_group_id_bits == 8 || num_group_id_bits == 16 ||
num_group_id_bits == 32);
+ int num_processed = 0;
+
// Optimistically use simplified lookup involving only a start block to find
// a single group id candidate for every input.
#if defined(ARROW_HAVE_AVX2)
int num_group_id_bytes = num_group_id_bits / 8;
if ((hardware_flags_ & arrow::internal::CpuInfo::AVX2) && !optional_selection) {
- extract_group_ids_avx2(num_keys, hashes, local_slots, out_group_ids, sizeof(uint64_t),
- 8 + 8 * num_group_id_bytes, num_group_id_bytes);
- return;
+ num_processed = extract_group_ids_avx2(num_keys, hashes, local_slots, out_group_ids,
+ sizeof(uint64_t), 8 + 8 * num_group_id_bytes,
+ num_group_id_bytes);
}
#endif
switch (num_group_id_bits) {
@@ -163,8 +148,9 @@ void SwissTable::extract_group_ids(const int num_keys, const uint16_t* optional_
extract_group_ids_imp<uint8_t, true>(num_keys, optional_selection, hashes,
local_slots, out_group_ids, 8, 16);
} else {
- extract_group_ids_imp<uint8_t, false>(num_keys, nullptr, hashes, local_slots,
- out_group_ids, 8, 16);
+ extract_group_ids_imp<uint8_t, false>(
+ num_keys - num_processed, nullptr, hashes + num_processed,
+ local_slots + num_processed, out_group_ids + num_processed, 8, 16);
}
break;
case 16:
@@ -172,8 +158,9 @@ void SwissTable::extract_group_ids(const int num_keys, const uint16_t* optional_
extract_group_ids_imp<uint16_t, true>(num_keys, optional_selection, hashes,
local_slots, out_group_ids, 4, 12);
} else {
- extract_group_ids_imp<uint16_t, false>(num_keys, nullptr, hashes, local_slots,
- out_group_ids, 4, 12);
+ extract_group_ids_imp<uint16_t, false>(
+ num_keys - num_processed, nullptr, hashes + num_processed,
+ local_slots + num_processed, out_group_ids + num_processed, 4, 12);
}
break;
case 32:
@@ -181,8 +168,9 @@ void SwissTable::extract_group_ids(const int num_keys, const uint16_t* optional_
extract_group_ids_imp<uint32_t, true>(num_keys, optional_selection, hashes,
local_slots, out_group_ids, 2, 10);
} else {
- extract_group_ids_imp<uint32_t, false>(num_keys, nullptr, hashes, local_slots,
- out_group_ids, 2, 10);
+ extract_group_ids_imp<uint32_t, false>(
+ num_keys - num_processed, nullptr, hashes + num_processed,
+ local_slots + num_processed, out_group_ids + num_processed, 2, 10);
}
break;
default:
@@ -312,24 +300,21 @@ void SwissTable::early_filter(const int num_keys, const uint32_t* hashes,
uint8_t* out_local_slots) const {
// Optimistically use simplified lookup involving only a start block to find
// a single group id candidate for every input.
+ int num_processed = 0;
#if defined(ARROW_HAVE_AVX2)
if (hardware_flags_ & arrow::internal::CpuInfo::AVX2) {
if (log_blocks_ <= 4) {
- int tail = num_keys % 32;
- int delta = num_keys - tail;
- early_filter_imp_avx2_x32(num_keys - tail, hashes, out_match_bitvector,
- out_local_slots);
- early_filter_imp_avx2_x8(tail, hashes + delta, out_match_bitvector + delta / 8,
- out_local_slots + delta);
- } else {
- early_filter_imp_avx2_x8(num_keys, hashes, out_match_bitvector, out_local_slots);
+ num_processed = early_filter_imp_avx2_x32(num_keys, hashes, out_match_bitvector,
+ out_local_slots);
}
- } else {
-#endif
- early_filter_imp(num_keys, hashes, out_match_bitvector, out_local_slots);
-#if defined(ARROW_HAVE_AVX2)
+ num_processed += early_filter_imp_avx2_x8(
+ num_keys - num_processed, hashes + num_processed,
+ out_match_bitvector + num_processed / 8, out_local_slots + num_processed);
}
#endif
+ early_filter_imp(num_keys - num_processed, hashes + num_processed,
+ out_match_bitvector + num_processed / 8,
+ out_local_slots + num_processed);
}
// Input selection may be:
@@ -348,10 +333,16 @@ void SwissTable::run_comparisons(const int num_keys,
const uint16_t* optional_selection_ids,
const uint8_t* optional_selection_bitvector,
const uint32_t* groupids, int* out_num_not_equal,
- uint16_t* out_not_equal_selection) const {
+ uint16_t* out_not_equal_selection,
+ const EqualImpl& equal_impl, void* callback_ctx) const {
ARROW_DCHECK(optional_selection_ids || optional_selection_bitvector);
ARROW_DCHECK(!optional_selection_ids || !optional_selection_bitvector);
+ if (num_keys == 0) {
+ *out_num_not_equal = 0;
+ return;
+ }
+
if (!optional_selection_ids && optional_selection_bitvector) {
// Count rows with matches (based on stamp comparison)
// and decide based on their percentage whether to call dense or sparse comparison
@@ -368,21 +359,22 @@ void SwissTable::run_comparisons(const int num_keys,
if (num_inserted_ > 0 && num_matches > 0 && num_matches > 3 * num_keys / 4) {
uint32_t out_num;
- equal_impl_(num_keys, nullptr, groupids, &out_num, out_not_equal_selection);
+ equal_impl(num_keys, nullptr, groupids, &out_num, out_not_equal_selection,
+ callback_ctx);
*out_num_not_equal = static_cast<int>(out_num);
} else {
util::bit_util::bits_to_indexes(1, hardware_flags_, num_keys,
optional_selection_bitvector, out_num_not_equal,
out_not_equal_selection);
uint32_t out_num;
- equal_impl_(*out_num_not_equal, out_not_equal_selection, groupids, &out_num,
- out_not_equal_selection);
+ equal_impl(*out_num_not_equal, out_not_equal_selection, groupids, &out_num,
+ out_not_equal_selection, callback_ctx);
*out_num_not_equal = static_cast<int>(out_num);
}
} else {
uint32_t out_num;
- equal_impl_(num_keys, optional_selection_ids, groupids, &out_num,
- out_not_equal_selection);
+ equal_impl(num_keys, optional_selection_ids, groupids, &out_num,
+ out_not_equal_selection, callback_ctx);
*out_num_not_equal = static_cast<int>(out_num);
}
}
@@ -432,35 +424,6 @@ bool SwissTable::find_next_stamp_match(const uint32_t hash, const uint32_t in_sl
return match_found;
}
-void SwissTable::insert_into_empty_slot(uint32_t slot_id, uint32_t hash,
- uint32_t group_id) {
- const uint64_t num_groupid_bits = num_groupid_bits_from_log_blocks(log_blocks_);
-
- // We assume here that the number of bits is rounded up to 8, 16, 32 or 64.
- // In that case we can insert group id value using aligned 64-bit word access.
- ARROW_DCHECK(num_groupid_bits == 8 || num_groupid_bits == 16 ||
- num_groupid_bits == 32 || num_groupid_bits == 64);
-
- const uint64_t num_block_bytes = (8 + num_groupid_bits);
- constexpr uint64_t stamp_mask = 0x7f;
-
- int start_slot = (slot_id & 7);
- int stamp =
- static_cast<int>((hash >> (bits_hash_ - log_blocks_ - bits_stamp_)) & stamp_mask);
- uint64_t block_id = slot_id >> 3;
- uint8_t* blockbase = blocks_ + num_block_bytes * block_id;
-
- blockbase[7 - start_slot] = static_cast<uint8_t>(stamp);
- int groupid_bit_offset = static_cast<int>(start_slot * num_groupid_bits);
-
- // Block status bytes should start at an address aligned to 8 bytes
- ARROW_DCHECK((reinterpret_cast<uint64_t>(blockbase) & 7) == 0);
- uint64_t* ptr = reinterpret_cast<uint64_t*>(blockbase) + 1 + (groupid_bit_offset >> 6);
- *ptr |= (static_cast<uint64_t>(group_id) << (groupid_bit_offset & 63));
-
- hashes_[slot_id] = hash;
-}
-
// Find method is the continuation of processing from early_filter.
// Its input consists of hash values and the output of early_filter.
// It updates match bit-vector, clearing it from any false positives
@@ -471,7 +434,8 @@ void SwissTable::insert_into_empty_slot(uint32_t slot_id, uint32_t hash,
//
void SwissTable::find(const int num_keys, const uint32_t* hashes,
uint8_t* inout_match_bitvector, const uint8_t* local_slots,
- uint32_t* out_group_ids) const {
+ uint32_t* out_group_ids, util::TempVectorStack* temp_stack,
+ const EqualImpl& equal_impl, void* callback_ctx) const {
// Temporary selection vector.
// It will hold ids of keys for which we do not know yet
// if they have a match in hash table or not.
@@ -481,12 +445,12 @@ void SwissTable::find(const int num_keys, const uint32_t* hashes,
// to array of ids.
//
ARROW_DCHECK(num_keys <= (1 << log_minibatch_));
- auto ids_buf = util::TempVectorHolder<uint16_t>(temp_stack_, num_keys);
+ auto ids_buf = util::TempVectorHolder<uint16_t>(temp_stack, num_keys);
uint16_t* ids = ids_buf.mutable_data();
int num_ids;
- int64_t num_matches =
- arrow::internal::CountSetBits(inout_match_bitvector, /*offset=*/0, num_keys);
+ int64_t num_matches = arrow::internal::CountSetBits(inout_match_bitvector,
+ /*offset=*/0, num_keys);
// If there is a high density of selected input rows
// (majority of them are present in the selection),
@@ -498,19 +462,20 @@ void SwissTable::find(const int num_keys, const uint32_t* hashes,
if (visit_all) {
extract_group_ids(num_keys, nullptr, hashes, local_slots, out_group_ids);
run_comparisons(num_keys, nullptr, inout_match_bitvector, out_group_ids, &num_ids,
- ids);
+ ids, equal_impl, callback_ctx);
} else {
util::bit_util::bits_to_indexes(1, hardware_flags_, num_keys, inout_match_bitvector,
&num_ids, ids);
extract_group_ids(num_ids, ids, hashes, local_slots, out_group_ids);
- run_comparisons(num_ids, ids, nullptr, out_group_ids, &num_ids, ids);
+ run_comparisons(num_ids, ids, nullptr, out_group_ids, &num_ids, ids, equal_impl,
+ callback_ctx);
}
if (num_ids == 0) {
return;
}
- auto slot_ids_buf = util::TempVectorHolder<uint32_t>(temp_stack_, num_keys);
+ auto slot_ids_buf = util::TempVectorHolder<uint32_t>(temp_stack, num_keys);
uint32_t* slot_ids = slot_ids_buf.mutable_data();
init_slot_ids(num_ids, ids, hashes, local_slots, inout_match_bitvector, slot_ids);
@@ -531,9 +496,10 @@ void SwissTable::find(const int num_keys, const uint32_t* hashes,
}
}
- run_comparisons(num_ids, ids, nullptr, out_group_ids, &num_ids, ids);
+ run_comparisons(num_ids, ids, nullptr, out_group_ids, &num_ids, ids, equal_impl,
+ callback_ctx);
}
-} // namespace compute
+}
// Slow processing of input keys in the most generic case.
// Handles inserting new keys.
@@ -545,11 +511,11 @@ void SwissTable::find(const int num_keys, const uint32_t* hashes,
// Update selection vector to reflect which items have been processed.
// Ids in selection vector do not have to be sorted.
//
-Status SwissTable::map_new_keys_helper(const uint32_t* hashes,
- uint32_t* inout_num_selected,
- uint16_t* inout_selection, bool* out_need_resize,
- uint32_t* out_group_ids,
- uint32_t* inout_next_slot_ids) {
+Status SwissTable::map_new_keys_helper(
+ const uint32_t* hashes, uint32_t* inout_num_selected, uint16_t* inout_selection,
+ bool* out_need_resize, uint32_t* out_group_ids, uint32_t* inout_next_slot_ids,
+ util::TempVectorStack* temp_stack, const EqualImpl& equal_impl,
+ const AppendImpl& append_impl, void* callback_ctx) {
auto num_groups_limit = num_groups_for_resize();
ARROW_DCHECK(num_inserted_ < num_groups_limit);
@@ -560,7 +526,7 @@ Status SwissTable::map_new_keys_helper(const uint32_t* hashes,
size_t num_bytes_for_bits = (*inout_num_selected + 7) / 8 + sizeof(uint64_t);
auto match_bitvector_buf = util::TempVectorHolder<uint8_t>(
- temp_stack_, static_cast<uint32_t>(num_bytes_for_bits));
+ temp_stack, static_cast<uint32_t>(num_bytes_for_bits));
uint8_t* match_bitvector = match_bitvector_buf.mutable_data();
memset(match_bitvector, 0xff, num_bytes_for_bits);
@@ -580,11 +546,12 @@ Status SwissTable::map_new_keys_helper(const uint32_t* hashes,
//
out_group_ids[id] = num_inserted_ + num_inserted_new;
insert_into_empty_slot(inout_next_slot_ids[id], hashes[id], out_group_ids[id]);
+ hashes_[inout_next_slot_ids[id]] = hashes[id];
::arrow::bit_util::ClearBit(match_bitvector, num_processed);
++num_inserted_new;
- // We need to break processing and have the caller of this function
- // resize hash table if we reach the limit of the number of groups present.
+ // We need to break processing and have the caller of this function resize hash
+ // table if we reach the limit of the number of groups present.
//
if (num_inserted_ + num_inserted_new == num_groups_limit) {
++num_processed;
@@ -594,7 +561,7 @@ Status SwissTable::map_new_keys_helper(const uint32_t* hashes,
}
auto temp_ids_buffer =
- util::TempVectorHolder<uint16_t>(temp_stack_, *inout_num_selected);
+ util::TempVectorHolder<uint16_t>(temp_stack, *inout_num_selected);
uint16_t* temp_ids = temp_ids_buffer.mutable_data();
int num_temp_ids = 0;
@@ -603,16 +570,18 @@ Status SwissTable::map_new_keys_helper(const uint32_t* hashes,
util::bit_util::bits_filter_indexes(0, hardware_flags_, num_processed, match_bitvector,
inout_selection, &num_temp_ids, temp_ids);
ARROW_DCHECK(static_cast<int>(num_inserted_new) == num_temp_ids);
- RETURN_NOT_OK(append_impl_(num_inserted_new, temp_ids));
+ RETURN_NOT_OK(append_impl(num_inserted_new, temp_ids, callback_ctx));
num_inserted_ += num_inserted_new;
// Evaluate comparisons and append ids of rows that failed it to the non-match set.
util::bit_util::bits_filter_indexes(1, hardware_flags_, num_processed, match_bitvector,
inout_selection, &num_temp_ids, temp_ids);
- run_comparisons(num_temp_ids, temp_ids, nullptr, out_group_ids, &num_temp_ids,
- temp_ids);
+ run_comparisons(num_temp_ids, temp_ids, nullptr, out_group_ids, &num_temp_ids, temp_ids,
+ equal_impl, callback_ctx);
- memcpy(inout_selection, temp_ids, sizeof(uint16_t) * num_temp_ids);
+ if (num_temp_ids > 0) {
+ memcpy(inout_selection, temp_ids, sizeof(uint16_t) * num_temp_ids);
+ }
// Append ids of any unprocessed entries if we aborted processing due to the need
// to resize.
if (num_processed < *inout_num_selected) {
@@ -629,7 +598,9 @@ Status SwissTable::map_new_keys_helper(const uint32_t* hashes,
// this set).
//
Status SwissTable::map_new_keys(uint32_t num_ids, uint16_t* ids, const uint32_t* hashes,
- uint32_t* group_ids) {
+ uint32_t* group_ids, util::TempVectorStack* temp_stack,
+ const EqualImpl& equal_impl,
+ const AppendImpl& append_impl, void* callback_ctx) {
if (num_ids == 0) {
return Status::OK();
}
@@ -645,7 +616,7 @@ Status SwissTable::map_new_keys(uint32_t num_ids, uint16_t* ids, const uint32_t*
ARROW_DCHECK(static_cast<int>(max_id + 1) <= (1 << log_minibatch_));
// Allocate temporary buffers for slot ids and intialize them
- auto slot_ids_buf = util::TempVectorHolder<uint32_t>(temp_stack_, max_id + 1);
+ auto slot_ids_buf = util::TempVectorHolder<uint32_t>(temp_stack, max_id + 1);
uint32_t* slot_ids = slot_ids_buf.mutable_data();
init_slot_ids_for_new_keys(num_ids, ids, hashes, slot_ids);
@@ -658,7 +629,8 @@ Status SwissTable::map_new_keys(uint32_t num_ids, uint16_t* ids, const uint32_t*
// bigger hash table.
bool out_of_capacity;
RETURN_NOT_OK(map_new_keys_helper(hashes, &num_ids, ids, &out_of_capacity, group_ids,
- slot_ids));
+ slot_ids, temp_stack, equal_impl, append_impl,
+ callback_ctx));
if (out_of_capacity) {
RETURN_NOT_OK(grow_double());
// Reset start slot ids for still unprocessed input keys.
@@ -803,17 +775,13 @@ Status SwissTable::grow_double() {
return Status::OK();
}
-Status SwissTable::init(int64_t hardware_flags, MemoryPool* pool,
- util::TempVectorStack* temp_stack, int log_minibatch,
- EqualImpl equal_impl, AppendImpl append_impl) {
+Status SwissTable::init(int64_t hardware_flags, MemoryPool* pool, int log_blocks,
+ bool no_hash_array) {
hardware_flags_ = hardware_flags;
pool_ = pool;
- temp_stack_ = temp_stack;
- log_minibatch_ = log_minibatch;
- equal_impl_ = equal_impl;
- append_impl_ = append_impl;
+ log_minibatch_ = util::MiniBatch::kLogMiniBatchLength;
- log_blocks_ = 0;
+ log_blocks_ = log_blocks;
int num_groupid_bits = num_groupid_bits_from_log_blocks(log_blocks_);
num_inserted_ = 0;
@@ -829,12 +797,16 @@ Status SwissTable::init(int64_t hardware_flags, MemoryPool* pool,
util::SafeStore(blocks_ + i * block_bytes, kHighBitOfEachByte);
}
- uint64_t num_slots = 1ULL << (log_blocks_ + 3);
- const uint64_t hash_size = sizeof(uint32_t);
- const uint64_t hash_bytes = hash_size * num_slots + padding_;
- uint8_t* hashes8;
- RETURN_NOT_OK(pool_->Allocate(hash_bytes, &hashes8));
- hashes_ = reinterpret_cast<uint32_t*>(hashes8);
+ if (no_hash_array) {
+ hashes_ = nullptr;
+ } else {
+ uint64_t num_slots = 1ULL << (log_blocks_ + 3);
+ const uint64_t hash_size = sizeof(uint32_t);
+ const uint64_t hash_bytes = hash_size * num_slots + padding_;
+ uint8_t* hashes8;
+ RETURN_NOT_OK(pool_->Allocate(hash_bytes, &hashes8));
+ hashes_ = reinterpret_cast<uint32_t*>(hashes8);
+ }
return Status::OK();
}
diff --git a/cpp/src/arrow/compute/exec/key_map.h b/cpp/src/arrow/compute/exec/key_map.h
index 12c1e393c4..cc630e0b1c 100644
--- a/cpp/src/arrow/compute/exec/key_map.h
+++ b/cpp/src/arrow/compute/exec/key_map.h
@@ -27,7 +27,17 @@
namespace arrow {
namespace compute {
+// SwissTable is a variant of a hash table implementation.
+// This implementation is vectorized, that is: main interface methods take arrays of input
+// values and output arrays of result values.
+//
+// A detailed explanation of this data structure (including concepts such as blocks,
+// slots, stamps) and operations provided by this class is given in the document:
+// arrow/compute/exec/doc/key_map.md.
+//
class SwissTable {
+ friend class SwissTableMerge;
+
public:
SwissTable() = default;
~SwissTable() { cleanup(); }
@@ -35,11 +45,12 @@ class SwissTable {
using EqualImpl =
std::function<void(int num_keys, const uint16_t* selection /* may be null */,
const uint32_t* group_ids, uint32_t* out_num_keys_mismatch,
- uint16_t* out_selection_mismatch)>;
- using AppendImpl = std::function<Status(int num_keys, const uint16_t* selection)>;
+ uint16_t* out_selection_mismatch, void* callback_ctx)>;
+ using AppendImpl =
+ std::function<Status(int num_keys, const uint16_t* selection, void* callback_ctx)>;
- Status init(int64_t hardware_flags, MemoryPool* pool, util::TempVectorStack* temp_stack,
- int log_minibatch, EqualImpl equal_impl, AppendImpl append_impl);
+ Status init(int64_t hardware_flags, MemoryPool* pool, int log_blocks = 0,
+ bool no_hash_array = false);
void cleanup();
@@ -47,10 +58,22 @@ class SwissTable {
uint8_t* out_match_bitvector, uint8_t* out_local_slots) const;
void find(const int num_keys, const uint32_t* hashes, uint8_t* inout_match_bitvector,
- const uint8_t* local_slots, uint32_t* out_group_ids) const;
+ const uint8_t* local_slots, uint32_t* out_group_ids,
+ util::TempVectorStack* temp_stack, const EqualImpl& equal_impl,
+ void* callback_ctx) const;
Status map_new_keys(uint32_t num_ids, uint16_t* ids, const uint32_t* hashes,
- uint32_t* group_ids);
+ uint32_t* group_ids, util::TempVectorStack* temp_stack,
+ const EqualImpl& equal_impl, const AppendImpl& append_impl,
+ void* callback_ctx);
+
+ int minibatch_size() const { return 1 << log_minibatch_; }
+
+ int64_t num_inserted() const { return num_inserted_; }
+
+ int64_t hardware_flags() const { return hardware_flags_; }
+
+ MemoryPool* pool() const { return pool_; }
private:
// Lookup helpers
@@ -116,21 +139,22 @@ class SwissTable {
void early_filter_imp(const int num_keys, const uint32_t* hashes,
uint8_t* out_match_bitvector, uint8_t* out_local_slots) const;
#if defined(ARROW_HAVE_AVX2)
- void early_filter_imp_avx2_x8(const int num_hashes, const uint32_t* hashes,
+ int early_filter_imp_avx2_x8(const int num_hashes, const uint32_t* hashes,
+ uint8_t* out_match_bitvector,
+ uint8_t* out_local_slots) const;
+ int early_filter_imp_avx2_x32(const int num_hashes, const uint32_t* hashes,
uint8_t* out_match_bitvector,
uint8_t* out_local_slots) const;
- void early_filter_imp_avx2_x32(const int num_hashes, const uint32_t* hashes,
- uint8_t* out_match_bitvector,
- uint8_t* out_local_slots) const;
- void extract_group_ids_avx2(const int num_keys, const uint32_t* hashes,
- const uint8_t* local_slots, uint32_t* out_group_ids,
- int byte_offset, int byte_multiplier, int byte_size) const;
+ int extract_group_ids_avx2(const int num_keys, const uint32_t* hashes,
+ const uint8_t* local_slots, uint32_t* out_group_ids,
+ int byte_offset, int byte_multiplier, int byte_size) const;
#endif
void run_comparisons(const int num_keys, const uint16_t* optional_selection_ids,
const uint8_t* optional_selection_bitvector,
const uint32_t* groupids, int* out_num_not_equal,
- uint16_t* out_not_equal_selection) const;
+ uint16_t* out_not_equal_selection, const EqualImpl& equal_impl,
+ void* callback_ctx) const;
inline bool find_next_stamp_match(const uint32_t hash, const uint32_t in_slot_id,
uint32_t* out_slot_id, uint32_t* out_group_id) const;
@@ -145,7 +169,10 @@ class SwissTable {
//
Status map_new_keys_helper(const uint32_t* hashes, uint32_t* inout_num_selected,
uint16_t* inout_selection, bool* out_need_resize,
- uint32_t* out_group_ids, uint32_t* out_next_slot_ids);
+ uint32_t* out_group_ids, uint32_t* out_next_slot_ids,
+ util::TempVectorStack* temp_stack,
+ const EqualImpl& equal_impl, const AppendImpl& append_impl,
+ void* callback_ctx);
// Resize small hash tables when 50% full (up to 8KB).
// Resize large hash tables when 75% full.
@@ -198,11 +225,51 @@ class SwissTable {
int64_t hardware_flags_;
MemoryPool* pool_;
- util::TempVectorStack* temp_stack_;
-
- EqualImpl equal_impl_;
- AppendImpl append_impl_;
};
+uint64_t SwissTable::extract_group_id(const uint8_t* block_ptr, int slot,
+ uint64_t group_id_mask) const {
+ // Group id values for all 8 slots in the block are bit-packed and follow the status
+ // bytes. We assume here that the number of bits is rounded up to 8, 16, 32 or 64. In
+ // that case we can extract group id using aligned 64-bit word access.
+ int num_group_id_bits = static_cast<int>(ARROW_POPCOUNT64(group_id_mask));
+ ARROW_DCHECK(num_group_id_bits == 8 || num_group_id_bits == 16 ||
+ num_group_id_bits == 32 || num_group_id_bits == 64);
+
+ int bit_offset = slot * num_group_id_bits;
+ const uint64_t* group_id_bytes =
+ reinterpret_cast<const uint64_t*>(block_ptr) + 1 + (bit_offset >> 6);
+ uint64_t group_id = (*group_id_bytes >> (bit_offset & 63)) & group_id_mask;
+
+ return group_id;
+}
+
+void SwissTable::insert_into_empty_slot(uint32_t slot_id, uint32_t hash,
+ uint32_t group_id) {
+ const uint64_t num_groupid_bits = num_groupid_bits_from_log_blocks(log_blocks_);
+
+ // We assume here that the number of bits is rounded up to 8, 16, 32 or 64.
+ // In that case we can insert group id value using aligned 64-bit word access.
+ ARROW_DCHECK(num_groupid_bits == 8 || num_groupid_bits == 16 ||
+ num_groupid_bits == 32 || num_groupid_bits == 64);
+
+ const uint64_t num_block_bytes = (8 + num_groupid_bits);
+ constexpr uint64_t stamp_mask = 0x7f;
+
+ int start_slot = (slot_id & 7);
+ int stamp =
+ static_cast<int>((hash >> (bits_hash_ - log_blocks_ - bits_stamp_)) & stamp_mask);
+ uint64_t block_id = slot_id >> 3;
+ uint8_t* blockbase = blocks_ + num_block_bytes * block_id;
+
+ blockbase[7 - start_slot] = static_cast<uint8_t>(stamp);
+ int groupid_bit_offset = static_cast<int>(start_slot * num_groupid_bits);
+
+ // Block status bytes should start at an address aligned to 8 bytes
+ ARROW_DCHECK((reinterpret_cast<uint64_t>(blockbase) & 7) == 0);
+ uint64_t* ptr = reinterpret_cast<uint64_t*>(blockbase) + 1 + (groupid_bit_offset >> 6);
+ *ptr |= (static_cast<uint64_t>(group_id) << (groupid_bit_offset & 63));
+}
+
} // namespace compute
} // namespace arrow
diff --git a/cpp/src/arrow/compute/exec/key_map_avx2.cc b/cpp/src/arrow/compute/exec/key_map_avx2.cc
index 2fca6bf6c1..4c77f3af23 100644
--- a/cpp/src/arrow/compute/exec/key_map_avx2.cc
+++ b/cpp/src/arrow/compute/exec/key_map_avx2.cc
@@ -24,21 +24,15 @@ namespace compute {
#if defined(ARROW_HAVE_AVX2)
-// Why it is OK to round up number of rows internally:
-// All of the buffers: hashes, out_match_bitvector, out_group_ids, out_next_slot_ids
-// are temporary buffers of group id mapping.
-// Temporary buffers are buffers that live only within the boundaries of a single
-// minibatch. Temporary buffers add 64B at the end, so that SIMD code does not have to
-// worry about reading and writing outside of the end of the buffer up to 64B. If the
-// hashes array contains garbage after the last element, it cannot cause computation to
-// fail, since any random data is a valid hash for the purpose of lookup.
+// This is more or less translation of equivalent scalar code, adjusted for a
+// different instruction set (e.g. missing leading zero count instruction).
//
-// This is more or less translation of equivalent scalar code, adjusted for a different
-// instruction set (e.g. missing leading zero count instruction).
+// Returns the number of hashes actually processed, which may be less than
+// requested due to alignment required by SIMD.
//
-void SwissTable::early_filter_imp_avx2_x8(const int num_hashes, const uint32_t* hashes,
- uint8_t* out_match_bitvector,
- uint8_t* out_local_slots) const {
+int SwissTable::early_filter_imp_avx2_x8(const int num_hashes, const uint32_t* hashes,
+ uint8_t* out_match_bitvector,
+ uint8_t* out_local_slots) const {
// Number of inputs processed together in a loop
constexpr int unroll = 8;
@@ -46,8 +40,7 @@ void SwissTable::early_filter_imp_avx2_x8(const int num_hashes, const uint32_t*
const __m256i* vhash_ptr = reinterpret_cast<const __m256i*>(hashes);
const __m256i vstamp_mask = _mm256_set1_epi32((1 << bits_stamp_) - 1);
- // TODO: explain why it is ok to process hashes outside of buffer boundaries
- for (int i = 0; i < ((num_hashes + unroll - 1) / unroll); ++i) {
+ for (int i = 0; i < num_hashes / unroll; ++i) {
constexpr uint64_t kEachByteIs8 = 0x0808080808080808ULL;
constexpr uint64_t kByteSequenceOfPowersOf2 = 0x8040201008040201ULL;
@@ -139,6 +132,8 @@ void SwissTable::early_filter_imp_avx2_x8(const int num_hashes, const uint32_t*
out_match_bitvector[i] = _pext_u32(_mm256_movemask_epi8(vmatch_found),
0x11111111); // 0b00010001 repeated 4x
}
+
+ return num_hashes - (num_hashes % unroll);
}
// Take a set of 16 64-bit elements,
@@ -173,8 +168,8 @@ inline void split_bytes_avx2(__m256i word0, __m256i word1, __m256i word2, __m256
// k4, o4, l4, p4, ... k7, o7, l7, p7}
__m256i byte01 = _mm256_unpacklo_epi32(
- a, b); // {a0, e0, b0, f0, i0, m0, j0, n0, a1, e1, b1, f1, i1, m1, j1, n1, c0, g0,
- // d0, h0, k0, o0, l0, p0, ...}
+ a, b); // {a0, e0, b0, f0, i0, m0, j0, n0, a1, e1, b1, f1, i1, m1, j1, n1,
+ // c0, g0, d0, h0, k0, o0, l0, p0, ...}
__m256i shuffle_const =
_mm256_setr_epi8(0, 2, 8, 10, 1, 3, 9, 11, 4, 6, 12, 14, 5, 7, 13, 15, 0, 2, 8, 10,
1, 3, 9, 11, 4, 6, 12, 14, 5, 7, 13, 15);
@@ -206,9 +201,13 @@ inline void split_bytes_avx2(__m256i word0, __m256i word1, __m256i word2, __m256
// using a different method.
// TODO: Explain the idea behind storing arrays in SIMD registers.
// Explain why it is faster with SIMD than using memory loads.
-void SwissTable::early_filter_imp_avx2_x32(const int num_hashes, const uint32_t* hashes,
- uint8_t* out_match_bitvector,
- uint8_t* out_local_slots) const {
+//
+// Returns the number of hashes actually processed, which may be less than
+// requested due to alignment required by SIMD.
+//
+int SwissTable::early_filter_imp_avx2_x32(const int num_hashes, const uint32_t* hashes,
+ uint8_t* out_match_bitvector,
+ uint8_t* out_local_slots) const {
constexpr int unroll = 32;
// There is a limit on the number of input blocks,
@@ -366,12 +365,14 @@ void SwissTable::early_filter_imp_avx2_x32(const int num_hashes, const uint32_t*
reinterpret_cast<uint32_t*>(out_match_bitvector)[i] =
_mm256_movemask_epi8(vmatch_found);
}
+
+ return num_hashes - (num_hashes % unroll);
}
-void SwissTable::extract_group_ids_avx2(const int num_keys, const uint32_t* hashes,
- const uint8_t* local_slots,
- uint32_t* out_group_ids, int byte_offset,
- int byte_multiplier, int byte_size) const {
+int SwissTable::extract_group_ids_avx2(const int num_keys, const uint32_t* hashes,
+ const uint8_t* local_slots,
+ uint32_t* out_group_ids, int byte_offset,
+ int byte_multiplier, int byte_size) const {
ARROW_DCHECK(byte_size == 1 || byte_size == 2 || byte_size == 4);
uint32_t mask = byte_size == 1 ? 0xFF : byte_size == 2 ? 0xFFFF : 0xFFFFFFFF;
auto elements = reinterpret_cast<const int*>(blocks_ + byte_offset);
@@ -380,7 +381,7 @@ void SwissTable::extract_group_ids_avx2(const int num_keys, const uint32_t* hash
ARROW_DCHECK(byte_size == 1 && byte_offset == 8 && byte_multiplier == 16);
__m256i block_group_ids =
_mm256_set1_epi64x(reinterpret_cast<const uint64_t*>(blocks_)[1]);
- for (int i = 0; i < (num_keys + unroll - 1) / unroll; ++i) {
+ for (int i = 0; i < num_keys / unroll; ++i) {
__m256i local_slot =
_mm256_set1_epi64x(reinterpret_cast<const uint64_t*>(local_slots)[i]);
__m256i group_id = _mm256_shuffle_epi8(block_group_ids, local_slot);
@@ -390,7 +391,7 @@ void SwissTable::extract_group_ids_avx2(const int num_keys, const uint32_t* hash
_mm256_storeu_si256(reinterpret_cast<__m256i*>(out_group_ids) + i, group_id);
}
} else {
- for (int i = 0; i < (num_keys + unroll - 1) / unroll; ++i) {
+ for (int i = 0; i < num_keys / unroll; ++i) {
__m256i hash = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(hashes) + i);
__m256i local_slot =
_mm256_set1_epi64x(reinterpret_cast<const uint64_t*>(local_slots)[i]);
@@ -406,6 +407,7 @@ void SwissTable::extract_group_ids_avx2(const int num_keys, const uint32_t* hash
_mm256_storeu_si256(reinterpret_cast<__m256i*>(out_group_ids) + i, group_id);
}
}
+ return num_keys - (num_keys % unroll);
}
#endif
diff --git a/cpp/src/arrow/compute/exec/partition_util.h b/cpp/src/arrow/compute/exec/partition_util.h
index 07fb91f2f1..b3f302511a 100644
--- a/cpp/src/arrow/compute/exec/partition_util.h
+++ b/cpp/src/arrow/compute/exec/partition_util.h
@@ -118,6 +118,54 @@ class PartitionLocks {
/// \brief Release a partition so that other threads can work on it
void ReleasePartitionLock(int prtn_id);
+ // Executes (synchronously and using current thread) the same operation on a set of
+ // multiple partitions. Tries to minimize partition locking overhead by randomizing and
+ // adjusting order in which partitions are processed.
+ //
+ // PROCESS_PRTN_FN is a callback which will be executed for each partition after
+ // acquiring the lock for that partition. It gets partition id as an argument.
+ // IS_PRTN_EMPTY_FN is a callback which filters out (when returning true) partitions
+ // with specific ids from processing.
+ //
+ template <typename IS_PRTN_EMPTY_FN, typename PROCESS_PRTN_FN>
+ Status ForEachPartition(size_t thread_id,
+ /*scratch space buffer with space for one element per partition;
+ dirty in and dirty out*/
+ int* temp_unprocessed_prtns, IS_PRTN_EMPTY_FN is_prtn_empty_fn,
+ PROCESS_PRTN_FN process_prtn_fn) {
+ int num_unprocessed_partitions = 0;
+ for (int i = 0; i < num_prtns_; ++i) {
+ bool is_prtn_empty = is_prtn_empty_fn(i);
+ if (!is_prtn_empty) {
+ temp_unprocessed_prtns[num_unprocessed_partitions++] = i;
+ }
+ }
+ while (num_unprocessed_partitions > 0) {
+ int locked_prtn_id;
+ int locked_prtn_id_pos;
+ AcquirePartitionLock(thread_id, num_unprocessed_partitions, temp_unprocessed_prtns,
+ /*limit_retries=*/false, /*max_retries=*/-1, &locked_prtn_id,
+ &locked_prtn_id_pos);
+ {
+ class AutoReleaseLock {
+ public:
+ AutoReleaseLock(PartitionLocks* locks, int prtn_id)
+ : locks(locks), prtn_id(prtn_id) {}
+ ~AutoReleaseLock() { locks->ReleasePartitionLock(prtn_id); }
+ PartitionLocks* locks;
+ int prtn_id;
+ } auto_release_lock(this, locked_prtn_id);
+ ARROW_RETURN_NOT_OK(process_prtn_fn(locked_prtn_id));
+ }
+ if (locked_prtn_id_pos < num_unprocessed_partitions - 1) {
+ temp_unprocessed_prtns[locked_prtn_id_pos] =
+ temp_unprocessed_prtns[num_unprocessed_partitions - 1];
+ }
+ --num_unprocessed_partitions;
+ }
+ return Status::OK();
+ }
+
private:
std::atomic<bool>* lock_ptr(int prtn_id);
int random_int(size_t thread_id, int num_values);
diff --git a/cpp/src/arrow/compute/exec/schema_util.h b/cpp/src/arrow/compute/exec/schema_util.h
index 91b7e6cfc6..f2b14aa545 100644
--- a/cpp/src/arrow/compute/exec/schema_util.h
+++ b/cpp/src/arrow/compute/exec/schema_util.h
@@ -24,7 +24,6 @@
#include "arrow/compute/light_array.h" // for KeyColumnMetadata
#include "arrow/type.h" // for DataType, FieldRef, Field and Schema
-#include "arrow/util/mutex.h"
namespace arrow {
@@ -79,16 +78,28 @@ class SchemaProjectionMaps {
int num_cols(ProjectionIdEnum schema_handle) const {
int id = schema_id(schema_handle);
- return static_cast<int>(schemas_[id].second.size());
+ return static_cast<int>(schemas_[id].second.data_types.size());
+ }
+
+ bool is_empty(ProjectionIdEnum schema_handle) const {
+ return num_cols(schema_handle) == 0;
}
const std::string& field_name(ProjectionIdEnum schema_handle, int field_id) const {
- return field(schema_handle, field_id).field_name;
+ int id = schema_id(schema_handle);
+ return schemas_[id].second.field_names[field_id];
}
const std::shared_ptr<DataType>& data_type(ProjectionIdEnum schema_handle,
int field_id) const {
- return field(schema_handle, field_id).data_type;
+ int id = schema_id(schema_handle);
+ return schemas_[id].second.data_types[field_id];
+ }
+
+ const std::vector<std::shared_ptr<DataType>>& data_types(
+ ProjectionIdEnum schema_handle) const {
+ int id = schema_id(schema_handle);
+ return schemas_[id].second.data_types;
}
SchemaProjectionMap map(ProjectionIdEnum from, ProjectionIdEnum to) const {
@@ -102,22 +113,24 @@ class SchemaProjectionMaps {
}
protected:
- struct FieldInfo {
- int field_path;
- std::string field_name;
- std::shared_ptr<DataType> data_type;
+ struct FieldInfos {
+ std::vector<int> field_paths;
+ std::vector<std::string> field_names;
+ std::vector<std::shared_ptr<DataType>> data_types;
};
Status RegisterSchema(ProjectionIdEnum handle, const Schema& schema) {
- std::vector<FieldInfo> out_fields;
+ FieldInfos out_fields;
const FieldVector& in_fields = schema.fields();
- out_fields.resize(in_fields.size());
+ out_fields.field_paths.resize(in_fields.size());
+ out_fields.field_names.resize(in_fields.size());
+ out_fields.data_types.resize(in_fields.size());
for (size_t i = 0; i < in_fields.size(); ++i) {
const std::string& name = in_fields[i]->name();
const std::shared_ptr<DataType>& type = in_fields[i]->type();
- out_fields[i].field_path = static_cast<int>(i);
- out_fields[i].field_name = name;
- out_fields[i].data_type = type;
+ out_fields.field_paths[i] = static_cast<int>(i);
+ out_fields.field_names[i] = name;
+ out_fields.data_types[i] = type;
}
schemas_.push_back(std::make_pair(handle, out_fields));
return Status::OK();
@@ -126,17 +139,19 @@ class SchemaProjectionMaps {
Status RegisterProjectedSchema(ProjectionIdEnum handle,
const std::vector<FieldRef>& selected_fields,
const Schema& full_schema) {
- std::vector<FieldInfo> out_fields;
+ FieldInfos out_fields;
const FieldVector& in_fields = full_schema.fields();
- out_fields.resize(selected_fields.size());
+ out_fields.field_paths.resize(selected_fields.size());
+ out_fields.field_names.resize(selected_fields.size());
+ out_fields.data_types.resize(selected_fields.size());
for (size_t i = 0; i < selected_fields.size(); ++i) {
// All fields must be found in schema without ambiguity
ARROW_ASSIGN_OR_RAISE(auto match, selected_fields[i].FindOne(full_schema));
const std::string& name = in_fields[match[0]]->name();
const std::shared_ptr<DataType>& type = in_fields[match[0]]->type();
- out_fields[i].field_path = match[0];
- out_fields[i].field_name = name;
- out_fields[i].data_type = type;
+ out_fields.field_paths[i] = match[0];
+ out_fields.field_names[i] = name;
+ out_fields.data_types[i] = type;
}
schemas_.push_back(std::make_pair(handle, out_fields));
return Status::OK();
@@ -163,15 +178,9 @@ class SchemaProjectionMaps {
return -1;
}
- const FieldInfo& field(ProjectionIdEnum schema_handle, int field_id) const {
- int id = schema_id(schema_handle);
- const std::vector<FieldInfo>& field_infos = schemas_[id].second;
- return field_infos[field_id];
- }
-
void GenerateMapForProjection(int id_proj, int id_base) {
- int num_cols_proj = static_cast<int>(schemas_[id_proj].second.size());
- int num_cols_base = static_cast<int>(schemas_[id_base].second.size());
+ int num_cols_proj = static_cast<int>(schemas_[id_proj].second.data_types.size());
+ int num_cols_base = static_cast<int>(schemas_[id_base].second.data_types.size());
std::vector<int>& mapping = mappings_[id_proj];
std::vector<int>& inverse_mapping = inverse_mappings_[id_proj];
@@ -183,15 +192,15 @@ class SchemaProjectionMaps {
mapping[i] = inverse_mapping[i] = i;
}
} else {
- const std::vector<FieldInfo>& fields_proj = schemas_[id_proj].second;
- const std::vector<FieldInfo>& fields_base = schemas_[id_base].second;
+ const FieldInfos& fields_proj = schemas_[id_proj].second;
+ const FieldInfos& fields_base = schemas_[id_base].second;
for (int i = 0; i < num_cols_base; ++i) {
inverse_mapping[i] = SchemaProjectionMap::kMissingField;
}
for (int i = 0; i < num_cols_proj; ++i) {
int field_id = SchemaProjectionMap::kMissingField;
for (int j = 0; j < num_cols_base; ++j) {
- if (fields_proj[i].field_path == fields_base[j].field_path) {
+ if (fields_proj.field_paths[i] == fields_base.field_paths[j]) {
field_id = j;
// If there are multiple matches for the same input field,
// it will be mapped to the first match.
@@ -206,10 +215,12 @@ class SchemaProjectionMaps {
}
// vector used as a mapping from ProjectionIdEnum to fields
- std::vector<std::pair<ProjectionIdEnum, std::vector<FieldInfo>>> schemas_;
+ std::vector<std::pair<ProjectionIdEnum, FieldInfos>> schemas_;
std::vector<std::vector<int>> mappings_;
std::vector<std::vector<int>> inverse_mappings_;
};
+using HashJoinProjectionMaps = SchemaProjectionMaps<HashJoinProjection>;
+
} // namespace compute
} // namespace arrow
diff --git a/cpp/src/arrow/compute/exec/swiss_join.cc b/cpp/src/arrow/compute/exec/swiss_join.cc
new file mode 100644
index 0000000000..5d70e01b1e
--- /dev/null
+++ b/cpp/src/arrow/compute/exec/swiss_join.cc
@@ -0,0 +1,2526 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "arrow/compute/exec/swiss_join.h"
+#include <sys/stat.h>
+#include <algorithm> // std::upper_bound
+#include <cstdio>
+#include <cstdlib>
+#include <mutex>
+#include "arrow/array/util.h" // MakeArrayFromScalar
+#include "arrow/compute/exec/hash_join.h"
+#include "arrow/compute/exec/key_hash.h"
+#include "arrow/compute/exec/util.h"
+#include "arrow/compute/kernels/row_encoder.h"
+#include "arrow/compute/row/compare_internal.h"
+#include "arrow/compute/row/encode_internal.h"
+#include "arrow/util/bit_util.h"
+#include "arrow/util/bitmap_ops.h"
+#include "arrow/util/tracing_internal.h"
+
+namespace arrow {
+namespace compute {
+
+int RowArrayAccessor::VarbinaryColumnId(const RowTableMetadata& row_metadata,
+ int column_id) {
+ ARROW_DCHECK(row_metadata.num_cols() > static_cast<uint32_t>(column_id));
+ ARROW_DCHECK(!row_metadata.is_fixed_length);
+ ARROW_DCHECK(!row_metadata.column_metadatas[column_id].is_fixed_length);
+
+ int varbinary_column_id = 0;
+ for (int i = 0; i < column_id; ++i) {
+ if (!row_metadata.column_metadatas[i].is_fixed_length) {
+ ++varbinary_column_id;
+ }
+ }
+ return varbinary_column_id;
+}
+
+int RowArrayAccessor::NumRowsToSkip(const RowTableImpl& rows, int column_id, int num_rows,
+ const uint32_t* row_ids, int num_tail_bytes_to_skip) {
+ uint32_t num_bytes_skipped = 0;
+ int num_rows_left = num_rows;
+
+ bool is_fixed_length_column =
+ rows.metadata().column_metadatas[column_id].is_fixed_length;
+
+ if (!is_fixed_length_column) {
+ // Varying length column
+ //
+ int varbinary_column_id = VarbinaryColumnId(rows.metadata(), column_id);
+
+ while (num_rows_left > 0 &&
+ num_bytes_skipped < static_cast<uint32_t>(num_tail_bytes_to_skip)) {
+ // Find the pointer to the last requested row
+ //
+ uint32_t last_row_id = row_ids[num_rows_left - 1];
+ const uint8_t* row_ptr = rows.data(2) + rows.offsets()[last_row_id];
+
+ // Find the length of the requested varying length field in that row
+ //
+ uint32_t field_offset_within_row, field_length;
+ if (varbinary_column_id == 0) {
+ rows.metadata().first_varbinary_offset_and_length(
+ row_ptr, &field_offset_within_row, &field_length);
+ } else {
+ rows.metadata().nth_varbinary_offset_and_length(
+ row_ptr, varbinary_column_id, &field_offset_within_row, &field_length);
+ }
+
+ num_bytes_skipped += field_length;
+ --num_rows_left;
+ }
+ } else {
+ // Fixed length column
+ //
+ uint32_t field_length = rows.metadata().column_metadatas[column_id].fixed_length;
+ uint32_t num_bytes_skipped = 0;
+ while (num_rows_left > 0 &&
+ num_bytes_skipped < static_cast<uint32_t>(num_tail_bytes_to_skip)) {
+ num_bytes_skipped += field_length;
+ --num_rows_left;
+ }
+ }
+
+ return num_rows - num_rows_left;
+}
+
+template <class PROCESS_VALUE_FN>
+void RowArrayAccessor::Visit(const RowTableImpl& rows, int column_id, int num_rows,
+ const uint32_t* row_ids, PROCESS_VALUE_FN process_value_fn) {
+ bool is_fixed_length_column =
+ rows.metadata().column_metadatas[column_id].is_fixed_length;
+
+ // There are 4 cases, each requiring different steps:
+ // 1. Varying length column that is the first varying length column in a row
+ // 2. Varying length column that is not the first varying length column in a
+ // row
+ // 3. Fixed length column in a fixed length row
+ // 4. Fixed length column in a varying length row
+
+ if (!is_fixed_length_column) {
+ int varbinary_column_id = VarbinaryColumnId(rows.metadata(), column_id);
+ const uint8_t* row_ptr_base = rows.data(2);
+ const uint32_t* row_offsets = rows.offsets();
+ uint32_t field_offset_within_row, field_length;
+
+ if (varbinary_column_id == 0) {
+ // Case 1: This is the first varbinary column
+ //
+ for (int i = 0; i < num_rows; ++i) {
+ uint32_t row_id = row_ids[i];
+ const uint8_t* row_ptr = row_ptr_base + row_offsets[row_id];
+ rows.metadata().first_varbinary_offset_and_length(
+ row_ptr, &field_offset_within_row, &field_length);
+ process_value_fn(i, row_ptr + field_offset_within_row, field_length);
+ }
+ } else {
+ // Case 2: This is second or later varbinary column
+ //
+ for (int i = 0; i < num_rows; ++i) {
+ uint32_t row_id = row_ids[i];
+ const uint8_t* row_ptr = row_ptr_base + row_offsets[row_id];
+ rows.metadata().nth_varbinary_offset_and_length(
+ row_ptr, varbinary_column_id, &field_offset_within_row, &field_length);
+ process_value_fn(i, row_ptr + field_offset_within_row, field_length);
+ }
+ }
+ }
+
+ if (is_fixed_length_column) {
+ uint32_t field_offset_within_row = rows.metadata().encoded_field_offset(
+ rows.metadata().pos_after_encoding(column_id));
+ uint32_t field_length = rows.metadata().column_metadatas[column_id].fixed_length;
+ // Bit column is encoded as a single byte
+ //
+ if (field_length == 0) {
+ field_length = 1;
+ }
+ uint32_t row_length = rows.metadata().fixed_length;
+
+ bool is_fixed_length_row = rows.metadata().is_fixed_length;
+ if (is_fixed_length_row) {
+ // Case 3: This is a fixed length column in a fixed length row
+ //
+ const uint8_t* row_ptr_base = rows.data(1) + field_offset_within_row;
+ for (int i = 0; i < num_rows; ++i) {
+ uint32_t row_id = row_ids[i];
+ const uint8_t* row_ptr = row_ptr_base + row_length * row_id;
+ process_value_fn(i, row_ptr, field_length);
+ }
+ } else {
+ // Case 4: This is a fixed length column in a varying length row
+ //
+ const uint8_t* row_ptr_base = rows.data(2) + field_offset_within_row;
+ const uint32_t* row_offsets = rows.offsets();
+ for (int i = 0; i < num_rows; ++i) {
+ uint32_t row_id = row_ids[i];
+ const uint8_t* row_ptr = row_ptr_base + row_offsets[row_id];
+ process_value_fn(i, row_ptr, field_length);
+ }
+ }
+ }
+}
+
+template <class PROCESS_VALUE_FN>
+void RowArrayAccessor::VisitNulls(const RowTableImpl& rows, int column_id, int num_rows,
+ const uint32_t* row_ids,
+ PROCESS_VALUE_FN process_value_fn) {
+ const uint8_t* null_masks = rows.null_masks();
+ uint32_t null_mask_num_bytes = rows.metadata().null_masks_bytes_per_row;
+ uint32_t pos_after_encoding = rows.metadata().pos_after_encoding(column_id);
+ for (int i = 0; i < num_rows; ++i) {
+ uint32_t row_id = row_ids[i];
+ int64_t bit_id = row_id * null_mask_num_bytes * 8 + pos_after_encoding;
+ process_value_fn(i, bit_util::GetBit(null_masks, bit_id) ? 0xff : 0);
+ }
+}
+
+Status RowArray::InitIfNeeded(MemoryPool* pool, const RowTableMetadata& row_metadata) {
+ if (is_initialized_) {
+ return Status::OK();
+ }
+ encoder_.Init(row_metadata.column_metadatas, sizeof(uint64_t), sizeof(uint64_t));
+ RETURN_NOT_OK(rows_temp_.Init(pool, row_metadata));
+ RETURN_NOT_OK(rows_.Init(pool, row_metadata));
+ is_initialized_ = true;
+ return Status::OK();
+}
+
+Status RowArray::InitIfNeeded(MemoryPool* pool, const ExecBatch& batch) {
+ if (is_initialized_) {
+ return Status::OK();
+ }
+ std::vector<KeyColumnMetadata> column_metadatas;
+ RETURN_NOT_OK(ColumnMetadatasFromExecBatch(batch, &column_metadatas));
+ RowTableMetadata row_metadata;
+ row_metadata.FromColumnMetadataVector(column_metadatas, sizeof(uint64_t),
+ sizeof(uint64_t));
+
+ return InitIfNeeded(pool, row_metadata);
+}
+
+Status RowArray::AppendBatchSelection(MemoryPool* pool, const ExecBatch& batch,
+ int begin_row_id, int end_row_id, int num_row_ids,
+ const uint16_t* row_ids,
+ std::vector<KeyColumnArray>& temp_column_arrays) {
+ RETURN_NOT_OK(InitIfNeeded(pool, batch));
+ RETURN_NOT_OK(ColumnArraysFromExecBatch(batch, begin_row_id, end_row_id - begin_row_id,
+ &temp_column_arrays));
+ encoder_.PrepareEncodeSelected(
+ /*start_row=*/0, end_row_id - begin_row_id, temp_column_arrays);
+ RETURN_NOT_OK(encoder_.EncodeSelected(&rows_temp_, num_row_ids, row_ids));
+ RETURN_NOT_OK(rows_.AppendSelectionFrom(rows_temp_, num_row_ids, nullptr));
+ return Status::OK();
+}
+
+void RowArray::Compare(const ExecBatch& batch, int begin_row_id, int end_row_id,
+ int num_selected, const uint16_t* batch_selection_maybe_null,
+ const uint32_t* array_row_ids, uint32_t* out_num_not_equal,
+ uint16_t* out_not_equal_selection, int64_t hardware_flags,
+ util::TempVectorStack* temp_stack,
+ std::vector<KeyColumnArray>& temp_column_arrays,
+ uint8_t* out_match_bitvector_maybe_null) {
+ Status status = ColumnArraysFromExecBatch(
+ batch, begin_row_id, end_row_id - begin_row_id, &temp_column_arrays);
+ ARROW_DCHECK(status.ok());
+
+ LightContext ctx;
+ ctx.hardware_flags = hardware_flags;
+ ctx.stack = temp_stack;
+ KeyCompare::CompareColumnsToRows(
+ num_selected, batch_selection_maybe_null, array_row_ids, &ctx, out_num_not_equal,
+ out_not_equal_selection, temp_column_arrays, rows_,
+ /*are_cols_in_encoding_order=*/false, out_match_bitvector_maybe_null);
+}
+
+Status RowArray::DecodeSelected(ResizableArrayData* output, int column_id,
+ int num_rows_to_append, const uint32_t* row_ids,
+ MemoryPool* pool) const {
+ int num_rows_before = output->num_rows();
+ RETURN_NOT_OK(output->ResizeFixedLengthBuffers(num_rows_before + num_rows_to_append));
+
+ // Both input (KeyRowArray) and output (ResizableArrayData) have buffers with
+ // extra bytes added at the end to avoid buffer overruns when using wide load
+ // instructions.
+ //
+
+ ARROW_ASSIGN_OR_RAISE(KeyColumnMetadata column_metadata, output->column_metadata());
+
+ if (column_metadata.is_fixed_length) {
+ uint32_t fixed_length = column_metadata.fixed_length;
+ switch (fixed_length) {
+ case 0:
+ RowArrayAccessor::Visit(rows_, column_id, num_rows_to_append, row_ids,
+ [&](int i, const uint8_t* ptr, uint32_t num_bytes) {
+ bit_util::SetBitTo(output->mutable_data(1),
+ num_rows_before + i, *ptr != 0);
+ });
+ break;
+ case 1:
+ RowArrayAccessor::Visit(rows_, column_id, num_rows_to_append, row_ids,
+ [&](int i, const uint8_t* ptr, uint32_t num_bytes) {
+ output->mutable_data(1)[num_rows_before + i] = *ptr;
+ });
+ break;
+ case 2:
+ RowArrayAccessor::Visit(
+ rows_, column_id, num_rows_to_append, row_ids,
+ [&](int i, const uint8_t* ptr, uint32_t num_bytes) {
+ reinterpret_cast<uint16_t*>(output->mutable_data(1))[num_rows_before + i] =
+ *reinterpret_cast<const uint16_t*>(ptr);
+ });
+ break;
+ case 4:
+ RowArrayAccessor::Visit(
+ rows_, column_id, num_rows_to_append, row_ids,
+ [&](int i, const uint8_t* ptr, uint32_t num_bytes) {
+ reinterpret_cast<uint32_t*>(output->mutable_data(1))[num_rows_before + i] =
+ *reinterpret_cast<const uint32_t*>(ptr);
+ });
+ break;
+ case 8:
+ RowArrayAccessor::Visit(
+ rows_, column_id, num_rows_to_append, row_ids,
+ [&](int i, const uint8_t* ptr, uint32_t num_bytes) {
+ reinterpret_cast<uint64_t*>(output->mutable_data(1))[num_rows_before + i] =
+ *reinterpret_cast<const uint64_t*>(ptr);
+ });
+ break;
+ default:
+ RowArrayAccessor::Visit(
+ rows_, column_id, num_rows_to_append, row_ids,
+ [&](int i, const uint8_t* ptr, uint32_t num_bytes) {
+ uint64_t* dst = reinterpret_cast<uint64_t*>(
+ output->mutable_data(1) + num_bytes * (num_rows_before + i));
+ const uint64_t* src = reinterpret_cast<const uint64_t*>(ptr);
+ for (uint32_t word_id = 0;
+ word_id < bit_util::CeilDiv(num_bytes, sizeof(uint64_t)); ++word_id) {
+ util::SafeStore<uint64_t>(dst + word_id, util::SafeLoad(src + word_id));
+ }
+ });
+ break;
+ }
+ } else {
+ uint32_t* offsets =
+ reinterpret_cast<uint32_t*>(output->mutable_data(1)) + num_rows_before;
+ uint32_t sum = num_rows_before == 0 ? 0 : offsets[0];
+ RowArrayAccessor::Visit(
+ rows_, column_id, num_rows_to_append, row_ids,
+ [&](int i, const uint8_t* ptr, uint32_t num_bytes) { offsets[i] = num_bytes; });
+ for (int i = 0; i < num_rows_to_append; ++i) {
+ uint32_t length = offsets[i];
+ offsets[i] = sum;
+ sum += length;
+ }
+ offsets[num_rows_to_append] = sum;
+ RETURN_NOT_OK(output->ResizeVaryingLengthBuffer());
+ RowArrayAccessor::Visit(
+ rows_, column_id, num_rows_to_append, row_ids,
+ [&](int i, const uint8_t* ptr, uint32_t num_bytes) {
+ uint64_t* dst = reinterpret_cast<uint64_t*>(
+ output->mutable_data(2) +
+ reinterpret_cast<const uint32_t*>(
+ output->mutable_data(1))[num_rows_before + i]);
+ const uint64_t* src = reinterpret_cast<const uint64_t*>(ptr);
+ for (uint32_t word_id = 0;
+ word_id < bit_util::CeilDiv(num_bytes, sizeof(uint64_t)); ++word_id) {
+ util::SafeStore<uint64_t>(dst + word_id, util::SafeLoad(src + word_id));
+ }
+ });
+ }
+
+ // Process nulls
+ //
+ RowArrayAccessor::VisitNulls(
+ rows_, column_id, num_rows_to_append, row_ids, [&](int i, uint8_t value) {
+ bit_util::SetBitTo(output->mutable_data(0), num_rows_before + i, value == 0);
+ });
+
+ return Status::OK();
+}
+
+void RowArray::DebugPrintToFile(const char* filename, bool print_sorted) const {
+ FILE* fout;
+#if defined(_MSC_VER) && _MSC_VER >= 1400
+ fopen_s(&fout, filename, "wt");
+#else
+ fout = fopen(filename, "wt");
+#endif
+ if (!fout) {
+ return;
+ }
+
+ for (int64_t row_id = 0; row_id < rows_.length(); ++row_id) {
+ for (uint32_t column_id = 0; column_id < rows_.metadata().num_cols(); ++column_id) {
+ bool is_null;
+ uint32_t row_id_cast = static_cast<uint32_t>(row_id);
+ RowArrayAccessor::VisitNulls(rows_, column_id, 1, &row_id_cast,
+ [&](int i, uint8_t value) { is_null = (value != 0); });
+ if (is_null) {
+ fprintf(fout, "null");
+ } else {
+ RowArrayAccessor::Visit(rows_, column_id, 1, &row_id_cast,
+ [&](int i, const uint8_t* ptr, uint32_t num_bytes) {
+ fprintf(fout, "\"");
+ for (uint32_t ibyte = 0; ibyte < num_bytes; ++ibyte) {
+ fprintf(fout, "%02x", ptr[ibyte]);
+ }
+ fprintf(fout, "\"");
+ });
+ }
+ fprintf(fout, "\t");
+ }
+ fprintf(fout, "\n");
+ }
+ fclose(fout);
+
+ if (print_sorted) {
+ struct stat sb;
+ if (stat(filename, &sb) == -1) {
+ ARROW_DCHECK(false);
+ return;
+ }
+ std::vector<char> buffer;
+ buffer.resize(sb.st_size);
+ std::vector<std::string> lines;
+ FILE* fin;
+#if defined(_MSC_VER) && _MSC_VER >= 1400
+ fopen_s(&fin, filename, "rt");
+#else
+ fin = fopen(filename, "rt");
+#endif
+ if (!fin) {
+ return;
+ }
+ while (fgets(buffer.data(), static_cast<int>(buffer.size()), fin)) {
+ lines.push_back(std::string(buffer.data()));
+ }
+ fclose(fin);
+ std::sort(lines.begin(), lines.end());
+ FILE* fout2;
+#if defined(_MSC_VER) && _MSC_VER >= 1400
+ fopen_s(&fout2, filename, "wt");
+#else
+ fout2 = fopen(filename, "wt");
+#endif
+ if (!fout2) {
+ return;
+ }
+ for (size_t i = 0; i < lines.size(); ++i) {
+ fprintf(fout2, "%s\n", lines[i].c_str());
+ }
+ fclose(fout2);
+ }
+}
+
+Status RowArrayMerge::PrepareForMerge(RowArray* target,
+ const std::vector<RowArray*>& sources,
+ std::vector<int64_t>* first_target_row_id,
+ MemoryPool* pool) {
+ ARROW_DCHECK(!sources.empty());
+
+ ARROW_DCHECK(sources[0]->is_initialized_);
+ const RowTableMetadata& metadata = sources[0]->rows_.metadata();
+ ARROW_DCHECK(!target->is_initialized_);
+ RETURN_NOT_OK(target->InitIfNeeded(pool, metadata));
+
+ // Sum the number of rows from all input sources and calculate their total
+ // size.
+ //
+ int64_t num_rows = 0;
+ int64_t num_bytes = 0;
+ if (first_target_row_id) {
+ first_target_row_id->resize(sources.size() + 1);
+ }
+ for (size_t i = 0; i < sources.size(); ++i) {
+ // All input sources must be initialized and have the same row format.
+ //
+ ARROW_DCHECK(sources[i]->is_initialized_);
+ ARROW_DCHECK(metadata.is_compatible(sources[i]->rows_.metadata()));
+ if (first_target_row_id) {
+ (*first_target_row_id)[i] = num_rows;
+ }
+ num_rows += sources[i]->rows_.length();
+ if (!metadata.is_fixed_length) {
+ num_bytes += sources[i]->rows_.offsets()[sources[i]->rows_.length()];
+ }
+ }
+ if (first_target_row_id) {
+ (*first_target_row_id)[sources.size()] = num_rows;
+ }
+
+ // Allocate target memory
+ //
+ target->rows_.Clean();
+ RETURN_NOT_OK(target->rows_.AppendEmpty(static_cast<uint32_t>(num_rows),
+ static_cast<uint32_t>(num_bytes)));
+
+ // In case of varying length rows,
+ // initialize the first row offset for each range of rows corresponding to a
+ // single source.
+ //
+ if (!metadata.is_fixed_length) {
+ num_rows = 0;
+ num_bytes = 0;
+ for (size_t i = 0; i < sources.size(); ++i) {
+ target->rows_.mutable_offsets()[num_rows] = static_cast<uint32_t>(num_bytes);
+ num_rows += sources[i]->rows_.length();
+ num_bytes += sources[i]->rows_.offsets()[sources[i]->rows_.length()];
+ }
+ target->rows_.mutable_offsets()[num_rows] = static_cast<uint32_t>(num_bytes);
+ }
+
+ return Status::OK();
+}
+
+void RowArrayMerge::MergeSingle(RowArray* target, const RowArray& source,
+ int64_t first_target_row_id,
+ const int64_t* source_rows_permutation) {
+ // Source and target must:
+ // - be initialized
+ // - use the same row format
+ // - use 64-bit alignment
+ //
+ ARROW_DCHECK(source.is_initialized_ && target->is_initialized_);
+ ARROW_DCHECK(target->rows_.metadata().is_compatible(source.rows_.metadata()));
+ ARROW_DCHECK(target->rows_.metadata().row_alignment == sizeof(uint64_t));
+
+ if (target->rows_.metadata().is_fixed_length) {
+ CopyFixedLength(&target->rows_, source.rows_, first_target_row_id,
+ source_rows_permutation);
+ } else {
+ CopyVaryingLength(&target->rows_, source.rows_, first_target_row_id,
+ target->rows_.offsets()[first_target_row_id],
+ source_rows_permutation);
+ }
+ CopyNulls(&target->rows_, source.rows_, first_target_row_id, source_rows_permutation);
+}
+
+void RowArrayMerge::CopyFixedLength(RowTableImpl* target, const RowTableImpl& source,
+ int64_t first_target_row_id,
+ const int64_t* source_rows_permutation) {
+ int64_t num_source_rows = source.length();
+
+ int64_t fixed_length = target->metadata().fixed_length;
+
+ // Permutation of source rows is optional. Without permutation all that is
+ // needed is memcpy.
+ //
+ if (!source_rows_permutation) {
+ memcpy(target->mutable_data(1) + fixed_length * first_target_row_id, source.data(1),
+ fixed_length * num_source_rows);
+ } else {
+ // Row length must be a multiple of 64-bits due to enforced alignment.
+ // Loop for each output row copying a fixed number of 64-bit words.
+ //
+ ARROW_DCHECK(fixed_length % sizeof(uint64_t) == 0);
+
+ int64_t num_words_per_row = fixed_length / sizeof(uint64_t);
+ for (int64_t i = 0; i < num_source_rows; ++i) {
+ int64_t source_row_id = source_rows_permutation[i];
+ const uint64_t* source_row_ptr = reinterpret_cast<const uint64_t*>(
+ source.data(1) + fixed_length * source_row_id);
+ uint64_t* target_row_ptr = reinterpret_cast<uint64_t*>(
+ target->mutable_data(1) + fixed_length * (first_target_row_id + i));
+
+ for (int64_t word = 0; word < num_words_per_row; ++word) {
+ target_row_ptr[word] = source_row_ptr[word];
+ }
+ }
+ }
+}
+
+void RowArrayMerge::CopyVaryingLength(RowTableImpl* target, const RowTableImpl& source,
+ int64_t first_target_row_id,
+ int64_t first_target_row_offset,
+ const int64_t* source_rows_permutation) {
+ int64_t num_source_rows = source.length();
+ uint32_t* target_offsets = target->mutable_offsets();
+ const uint32_t* source_offsets = source.offsets();
+
+ // Permutation of source rows is optional.
+ //
+ if (!source_rows_permutation) {
+ int64_t target_row_offset = first_target_row_offset;
+ for (int64_t i = 0; i < num_source_rows; ++i) {
+ target_offsets[first_target_row_id + i] = static_cast<uint32_t>(target_row_offset);
+ target_row_offset += source_offsets[i + 1] - source_offsets[i];
+ }
+ // We purposefully skip outputting of N+1 offset, to allow concurrent
+ // copies of rows done to adjacent ranges in target array.
+ // It should have already been initialized during preparation for merge.
+ //
+
+ // We can simply memcpy bytes of rows if their order has not changed.
+ //
+ memcpy(target->mutable_data(2) + target_offsets[first_target_row_id], source.data(2),
+ source_offsets[num_source_rows] - source_offsets[0]);
+ } else {
+ int64_t target_row_offset = first_target_row_offset;
+ uint64_t* target_row_ptr =
+ reinterpret_cast<uint64_t*>(target->mutable_data(2) + target_row_offset);
+ for (int64_t i = 0; i < num_source_rows; ++i) {
+ int64_t source_row_id = source_rows_permutation[i];
+ const uint64_t* source_row_ptr = reinterpret_cast<const uint64_t*>(
+ source.data(2) + source_offsets[source_row_id]);
+ uint32_t length = source_offsets[source_row_id + 1] - source_offsets[source_row_id];
+
+ // Rows should be 64-bit aligned.
+ // In that case we can copy them using a sequence of 64-bit read/writes.
+ //
+ ARROW_DCHECK(length % sizeof(uint64_t) == 0);
+
+ for (uint32_t word = 0; word < length / sizeof(uint64_t); ++word) {
+ *target_row_ptr++ = *source_row_ptr++;
+ }
+
+ target_offsets[first_target_row_id + i] = static_cast<uint32_t>(target_row_offset);
+ target_row_offset += length;
+ }
+ }
+}
+
+void RowArrayMerge::CopyNulls(RowTableImpl* target, const RowTableImpl& source,
+ int64_t first_target_row_id,
+ const int64_t* source_rows_permutation) {
+ int64_t num_source_rows = source.length();
+ int num_bytes_per_row = target->metadata().null_masks_bytes_per_row;
+ uint8_t* target_nulls = target->null_masks() + num_bytes_per_row * first_target_row_id;
+ if (!source_rows_permutation) {
+ memcpy(target_nulls, source.null_masks(), num_bytes_per_row * num_source_rows);
+ } else {
+ for (int64_t i = 0; i < num_source_rows; ++i) {
+ int64_t source_row_id = source_rows_permutation[i];
+ const uint8_t* source_nulls =
+ source.null_masks() + num_bytes_per_row * source_row_id;
+ for (int64_t byte = 0; byte < num_bytes_per_row; ++byte) {
+ *target_nulls++ = *source_nulls++;
+ }
+ }
+ }
+}
+
+Status SwissTableMerge::PrepareForMerge(SwissTable* target,
+ const std::vector<SwissTable*>& sources,
+ std::vector<uint32_t>* first_target_group_id,
+ MemoryPool* pool) {
+ ARROW_DCHECK(!sources.empty());
+
+ // Each source should correspond to a range of hashes.
+ // A row belongs to a source with index determined by K highest bits of hash.
+ // That means that the number of sources must be a power of 2.
+ //
+ int log_num_sources = bit_util::Log2(sources.size());
+ ARROW_DCHECK((1 << log_num_sources) == static_cast<int>(sources.size()));
+
+ // Determine the number of blocks in the target table.
+ // We will use max of numbers of blocks in any of the sources multiplied by
+ // the number of sources.
+ //
+ int log_blocks_max = 1;
+ for (size_t i = 0; i < sources.size(); ++i) {
+ log_blocks_max = std::max(log_blocks_max, sources[i]->log_blocks_);
+ }
+ int log_blocks = log_num_sources + log_blocks_max;
+
+ // Allocate target blocks and mark all slots as empty
+ //
+ // We will skip allocating the array of hash values in target table.
+ // Target will be used in read-only mode and that array is only needed when
+ // resizing table which may occur only after new inserts.
+ //
+ RETURN_NOT_OK(target->init(sources[0]->hardware_flags_, pool, log_blocks,
+ /*no_hash_array=*/true));
+
+ // Calculate and output the first group id index for each source.
+ //
+ if (first_target_group_id) {
+ uint32_t num_groups = 0;
+ first_target_group_id->resize(sources.size());
+ for (size_t i = 0; i < sources.size(); ++i) {
+ (*first_target_group_id)[i] = num_groups;
+ num_groups += sources[i]->num_inserted_;
+ }
+ target->num_inserted_ = num_groups;
+ }
+
+ return Status::OK();
+}
+
+void SwissTableMerge::MergePartition(SwissTable* target, const SwissTable* source,
+ uint32_t partition_id, int num_partition_bits,
+ uint32_t base_group_id,
+ std::vector<uint32_t>* overflow_group_ids,
+ std::vector<uint32_t>* overflow_hashes) {
+ // Prepare parameters needed for scanning full slots in source.
+ //
+ int source_group_id_bits =
+ SwissTable::num_groupid_bits_from_log_blocks(source->log_blocks_);
+ uint64_t source_group_id_mask = ~0ULL >> (64 - source_group_id_bits);
+ int64_t source_block_bytes = source_group_id_bits + 8;
+ ARROW_DCHECK(source_block_bytes % sizeof(uint64_t) == 0);
+
+ // Compute index of the last block in target that corresponds to the given
+ // partition.
+ //
+ ARROW_DCHECK(num_partition_bits <= target->log_blocks_);
+ int64_t target_max_block_id =
+ ((partition_id + 1) << (target->log_blocks_ - num_partition_bits)) - 1;
+
+ overflow_group_ids->clear();
+ overflow_hashes->clear();
+
+ // For each source block...
+ int64_t source_blocks = 1LL << source->log_blocks_;
+ for (int64_t block_id = 0; block_id < source_blocks; ++block_id) {
+ uint8_t* block_bytes = source->blocks_ + block_id * source_block_bytes;
+ uint64_t block = *reinterpret_cast<const uint64_t*>(block_bytes);
+
+ // For each non-empty source slot...
+ constexpr uint64_t kHighBitOfEachByte = 0x8080808080808080ULL;
+ constexpr int kSlotsPerBlock = 8;
+ int num_full_slots =
+ kSlotsPerBlock - static_cast<int>(ARROW_POPCOUNT64(block & kHighBitOfEachByte));
+ for (int local_slot_id = 0; local_slot_id < num_full_slots; ++local_slot_id) {
+ // Read group id and hash for this slot.
+ //
+ uint64_t group_id =
+ source->extract_group_id(block_bytes, local_slot_id, source_group_id_mask);
+ int64_t global_slot_id = block_id * kSlotsPerBlock + local_slot_id;
+ uint32_t hash = source->hashes_[global_slot_id];
+ // Insert partition id into the highest bits of hash, shifting the
+ // remaining hash bits right.
+ //
+ hash >>= num_partition_bits;
+ hash |= (partition_id << (SwissTable::bits_hash_ - 1 - num_partition_bits) << 1);
+ // Add base group id
+ //
+ group_id += base_group_id;
+
+ // Insert new entry into target. Store in overflow vectors if not
+ // successful.
+ //
+ bool was_inserted = InsertNewGroup(target, group_id, hash, target_max_block_id);
+ if (!was_inserted) {
+ overflow_group_ids->push_back(static_cast<uint32_t>(group_id));
+ overflow_hashes->push_back(hash);
+ }
+ }
+ }
+}
+
+inline bool SwissTableMerge::InsertNewGroup(SwissTable* target, uint64_t group_id,
+ uint32_t hash, int64_t max_block_id) {
+ // Load the first block to visit for this hash
+ //
+ int64_t block_id = hash >> (SwissTable::bits_hash_ - target->log_blocks_);
+ int64_t block_id_mask = ((1LL << target->log_blocks_) - 1);
+ int num_group_id_bits =
+ SwissTable::num_groupid_bits_from_log_blocks(target->log_blocks_);
+ int64_t num_block_bytes = num_group_id_bits + sizeof(uint64_t);
+ ARROW_DCHECK(num_block_bytes % sizeof(uint64_t) == 0);
+ uint8_t* block_bytes = target->blocks_ + block_id * num_block_bytes;
+ uint64_t block = *reinterpret_cast<const uint64_t*>(block_bytes);
+
+ // Search for the first block with empty slots.
+ // Stop after reaching max block id.
+ //
+ constexpr uint64_t kHighBitOfEachByte = 0x8080808080808080ULL;
+ while ((block & kHighBitOfEachByte) == 0 && block_id < max_block_id) {
+ block_id = (block_id + 1) & block_id_mask;
+ block_bytes = target->blocks_ + block_id * num_block_bytes;
+ block = *reinterpret_cast<const uint64_t*>(block_bytes);
+ }
+ if ((block & kHighBitOfEachByte) == 0) {
+ return false;
+ }
+ constexpr int kSlotsPerBlock = 8;
+ int local_slot_id =
+ kSlotsPerBlock - static_cast<int>(ARROW_POPCOUNT64(block & kHighBitOfEachByte));
+ int64_t global_slot_id = block_id * kSlotsPerBlock + local_slot_id;
+ target->insert_into_empty_slot(static_cast<uint32_t>(global_slot_id), hash,
+ static_cast<uint32_t>(group_id));
+ return true;
+}
+
+void SwissTableMerge::InsertNewGroups(SwissTable* target,
+ const std::vector<uint32_t>& group_ids,
+ const std::vector<uint32_t>& hashes) {
+ int64_t num_blocks = 1LL << target->log_blocks_;
+ for (size_t i = 0; i < group_ids.size(); ++i) {
+ std::ignore = InsertNewGroup(target, group_ids[i], hashes[i], num_blocks);
+ }
+}
+
+SwissTableWithKeys::Input::Input(const ExecBatch* in_batch, int in_batch_start_row,
+ int in_batch_end_row,
+ util::TempVectorStack* in_temp_stack,
+ std::vector<KeyColumnArray>* in_temp_column_arrays)
+ : batch(in_batch),
+ batch_start_row(in_batch_start_row),
+ batch_end_row(in_batch_end_row),
+ num_selected(0),
+ selection_maybe_null(nullptr),
+ temp_stack(in_temp_stack),
+ temp_column_arrays(in_temp_column_arrays),
+ temp_group_ids(nullptr) {}
+
+SwissTableWithKeys::Input::Input(const ExecBatch* in_batch,
+ util::TempVectorStack* in_temp_stack,
+ std::vector<KeyColumnArray>* in_temp_column_arrays)
+ : batch(in_batch),
+ batch_start_row(0),
+ batch_end_row(static_cast<int>(in_batch->length)),
+ num_selected(0),
+ selection_maybe_null(nullptr),
+ temp_stack(in_temp_stack),
+ temp_column_arrays(in_temp_column_arrays),
+ temp_group_ids(nullptr) {}
+
+SwissTableWithKeys::Input::Input(const ExecBatch* in_batch, int in_num_selected,
+ const uint16_t* in_selection,
+ util::TempVectorStack* in_temp_stack,
+ std::vector<KeyColumnArray>* in_temp_column_arrays,
+ std::vector<uint32_t>* in_temp_group_ids)
+ : batch(in_batch),
+ batch_start_row(0),
+ batch_end_row(static_cast<int>(in_batch->length)),
+ num_selected(in_num_selected),
+ selection_maybe_null(in_selection),
+ temp_stack(in_temp_stack),
+ temp_column_arrays(in_temp_column_arrays),
+ temp_group_ids(in_temp_group_ids) {}
+
+SwissTableWithKeys::Input::Input(const Input& base, int num_rows_to_skip,
+ int num_rows_to_include)
+ : batch(base.batch),
+ temp_stack(base.temp_stack),
+ temp_column_arrays(base.temp_column_arrays),
+ temp_group_ids(base.temp_group_ids) {
+ if (base.selection_maybe_null) {
+ batch_start_row = 0;
+ batch_end_row = static_cast<int>(batch->length);
+ ARROW_DCHECK(num_rows_to_skip + num_rows_to_include <= base.num_selected);
+ num_selected = num_rows_to_include;
+ selection_maybe_null = base.selection_maybe_null + num_rows_to_skip;
+ } else {
+ ARROW_DCHECK(base.batch_start_row + num_rows_to_skip + num_rows_to_include <=
+ base.batch_end_row);
+ batch_start_row = base.batch_start_row + num_rows_to_skip;
+ batch_end_row = base.batch_start_row + num_rows_to_skip + num_rows_to_include;
+ num_selected = 0;
+ selection_maybe_null = nullptr;
+ }
+}
+
+Status SwissTableWithKeys::Init(int64_t hardware_flags, MemoryPool* pool) {
+ InitCallbacks();
+ return swiss_table_.init(hardware_flags, pool);
+}
+
+void SwissTableWithKeys::EqualCallback(int num_keys, const uint16_t* selection_maybe_null,
+ const uint32_t* group_ids,
+ uint32_t* out_num_keys_mismatch,
+ uint16_t* out_selection_mismatch,
+ void* callback_ctx) {
+ if (num_keys == 0) {
+ *out_num_keys_mismatch = 0;
+ return;
+ }
+
+ ARROW_DCHECK(num_keys <= swiss_table_.minibatch_size());
+
+ Input* in = reinterpret_cast<Input*>(callback_ctx);
+
+ int64_t hardware_flags = swiss_table_.hardware_flags();
+
+ int batch_start_to_use;
+ int batch_end_to_use;
+ const uint16_t* selection_to_use;
+ const uint32_t* group_ids_to_use;
+
+ if (in->selection_maybe_null) {
+ auto selection_to_use_buf =
+ util::TempVectorHolder<uint16_t>(in->temp_stack, num_keys);
+ ARROW_DCHECK(in->temp_group_ids);
+ in->temp_group_ids->resize(in->batch->length);
+
+ if (selection_maybe_null) {
+ for (int i = 0; i < num_keys; ++i) {
+ uint16_t local_row_id = selection_maybe_null[i];
+ uint16_t global_row_id = in->selection_maybe_null[local_row_id];
+ selection_to_use_buf.mutable_data()[i] = global_row_id;
+ (*in->temp_group_ids)[global_row_id] = group_ids[local_row_id];
+ }
+ selection_to_use = selection_to_use_buf.mutable_data();
+ } else {
+ for (int i = 0; i < num_keys; ++i) {
+ uint16_t global_row_id = in->selection_maybe_null[i];
+ (*in->temp_group_ids)[global_row_id] = group_ids[i];
+ }
+ selection_to_use = in->selection_maybe_null;
+ }
+ batch_start_to_use = 0;
+ batch_end_to_use = static_cast<int>(in->batch->length);
+ group_ids_to_use = in->temp_group_ids->data();
+
+ auto match_bitvector_buf = util::TempVectorHolder<uint8_t>(in->temp_stack, num_keys);
+ uint8_t* match_bitvector = match_bitvector_buf.mutable_data();
+
+ keys_.Compare(*in->batch, batch_start_to_use, batch_end_to_use, num_keys,
+ selection_to_use, group_ids_to_use, nullptr, nullptr, hardware_flags,
+ in->temp_stack, *in->temp_column_arrays, match_bitvector);
+
+ if (selection_maybe_null) {
+ int num_keys_mismatch = 0;
+ util::bit_util::bits_filter_indexes(0, hardware_flags, num_keys, match_bitvector,
+ selection_maybe_null, &num_keys_mismatch,
+ out_selection_mismatch);
+ *out_num_keys_mismatch = num_keys_mismatch;
+ } else {
+ int num_keys_mismatch = 0;
+ util::bit_util::bits_to_indexes(0, hardware_flags, num_keys, match_bitvector,
+ &num_keys_mismatch, out_selection_mismatch);
+ *out_num_keys_mismatch = num_keys_mismatch;
+ }
+
+ } else {
+ batch_start_to_use = in->batch_start_row;
+ batch_end_to_use = in->batch_end_row;
+ selection_to_use = selection_maybe_null;
+ group_ids_to_use = group_ids;
+ keys_.Compare(*in->batch, batch_start_to_use, batch_end_to_use, num_keys,
+ selection_to_use, group_ids_to_use, out_num_keys_mismatch,
+ out_selection_mismatch, hardware_flags, in->temp_stack,
+ *in->temp_column_arrays);
+ }
+}
+
+Status SwissTableWithKeys::AppendCallback(int num_keys, const uint16_t* selection,
+ void* callback_ctx) {
+ ARROW_DCHECK(num_keys <= swiss_table_.minibatch_size());
+ ARROW_DCHECK(selection);
+
+ Input* in = reinterpret_cast<Input*>(callback_ctx);
+
+ int batch_start_to_use;
+ int batch_end_to_use;
+ const uint16_t* selection_to_use;
+
+ if (in->selection_maybe_null) {
+ auto selection_to_use_buf =
+ util::TempVectorHolder<uint16_t>(in->temp_stack, num_keys);
+ for (int i = 0; i < num_keys; ++i) {
+ selection_to_use_buf.mutable_data()[i] = in->selection_maybe_null[selection[i]];
+ }
+ batch_start_to_use = 0;
+ batch_end_to_use = static_cast<int>(in->batch->length);
+ selection_to_use = selection_to_use_buf.mutable_data();
+
+ return keys_.AppendBatchSelection(swiss_table_.pool(), *in->batch, batch_start_to_use,
+ batch_end_to_use, num_keys, selection_to_use,
+ *in->temp_column_arrays);
+ } else {
+ batch_start_to_use = in->batch_start_row;
+ batch_end_to_use = in->batch_end_row;
+ selection_to_use = selection;
+
+ return keys_.AppendBatchSelection(swiss_table_.pool(), *in->batch, batch_start_to_use,
+ batch_end_to_use, num_keys, selection_to_use,
+ *in->temp_column_arrays);
+ }
+}
+
+void SwissTableWithKeys::InitCallbacks() {
+ equal_impl_ = [&](int num_keys, const uint16_t* selection_maybe_null,
+ const uint32_t* group_ids, uint32_t* out_num_keys_mismatch,
+ uint16_t* out_selection_mismatch, void* callback_ctx) {
+ EqualCallback(num_keys, selection_maybe_null, group_ids, out_num_keys_mismatch,
+ out_selection_mismatch, callback_ctx);
+ };
+ append_impl_ = [&](int num_keys, const uint16_t* selection, void* callback_ctx) {
+ return AppendCallback(num_keys, selection, callback_ctx);
+ };
+}
+
+void SwissTableWithKeys::Hash(Input* input, uint32_t* hashes, int64_t hardware_flags) {
+ // Hashing does not support selection of rows
+ //
+ ARROW_DCHECK(input->selection_maybe_null == nullptr);
+
+ Status status =
+ Hashing32::HashBatch(*input->batch, hashes, *input->temp_column_arrays,
+ hardware_flags, input->temp_stack, input->batch_start_row,
+ input->batch_end_row - input->batch_start_row);
+ ARROW_DCHECK(status.ok());
+}
+
+void SwissTableWithKeys::MapReadOnly(Input* input, const uint32_t* hashes,
+ uint8_t* match_bitvector, uint32_t* key_ids) {
+ std::ignore = Map(input, /*insert_missing=*/false, hashes, match_bitvector, key_ids);
+}
+
+Status SwissTableWithKeys::MapWithInserts(Input* input, const uint32_t* hashes,
+ uint32_t* key_ids) {
+ return Map(input, /*insert_missing=*/true, hashes, nullptr, key_ids);
+}
+
+Status SwissTableWithKeys::Map(Input* input, bool insert_missing, const uint32_t* hashes,
+ uint8_t* match_bitvector_maybe_null, uint32_t* key_ids) {
+ util::TempVectorStack* temp_stack = input->temp_stack;
+
+ // Split into smaller mini-batches
+ //
+ int minibatch_size = swiss_table_.minibatch_size();
+ int num_rows_to_process = input->selection_maybe_null
+ ? input->num_selected
+ : input->batch_end_row - input->batch_start_row;
+ auto hashes_buf = util::TempVectorHolder<uint32_t>(temp_stack, minibatch_size);
+ auto match_bitvector_buf = util::TempVectorHolder<uint8_t>(
+ temp_stack,
+ static_cast<uint32_t>(bit_util::BytesForBits(minibatch_size)) + sizeof(uint64_t));
+ for (int minibatch_start = 0; minibatch_start < num_rows_to_process;) {
+ int minibatch_size_next =
+ std::min(minibatch_size, num_rows_to_process - minibatch_start);
+
+ // Prepare updated input buffers that represent the current minibatch.
+ //
+ Input minibatch_input(*input, minibatch_start, minibatch_size_next);
+ uint8_t* minibatch_match_bitvector =
+ insert_missing ? match_bitvector_buf.mutable_data()
+ : match_bitvector_maybe_null + minibatch_start / 8;
+ const uint32_t* minibatch_hashes;
+ if (input->selection_maybe_null) {
+ minibatch_hashes = hashes_buf.mutable_data();
+ for (int i = 0; i < minibatch_size_next; ++i) {
+ hashes_buf.mutable_data()[i] = hashes[minibatch_input.selection_maybe_null[i]];
+ }
+ } else {
+ minibatch_hashes = hashes + minibatch_start;
+ }
+ uint32_t* minibatch_key_ids = key_ids + minibatch_start;
+
+ // Lookup existing keys.
+ {
+ auto slots = util::TempVectorHolder<uint8_t>(temp_stack, minibatch_size_next);
+ swiss_table_.early_filter(minibatch_size_next, minibatch_hashes,
+ minibatch_match_bitvector, slots.mutable_data());
+ swiss_table_.find(minibatch_size_next, minibatch_hashes, minibatch_match_bitvector,
+ slots.mutable_data(), minibatch_key_ids, temp_stack, equal_impl_,
+ &minibatch_input);
+ }
+
+ // Perform inserts of missing keys if required.
+ //
+ if (insert_missing) {
+ auto ids_buf = util::TempVectorHolder<uint16_t>(temp_stack, minibatch_size_next);
+ int num_ids;
+ util::bit_util::bits_to_indexes(0, swiss_table_.hardware_flags(),
+ minibatch_size_next, minibatch_match_bitvector,
+ &num_ids, ids_buf.mutable_data());
+
+ RETURN_NOT_OK(swiss_table_.map_new_keys(
+ num_ids, ids_buf.mutable_data(), minibatch_hashes, minibatch_key_ids,
+ temp_stack, equal_impl_, append_impl_, &minibatch_input));
+ }
+
+ minibatch_start += minibatch_size_next;
+ }
+
+ return Status::OK();
+}
+
+uint8_t* SwissTableForJoin::local_has_match(int64_t thread_id) {
+ int64_t num_rows_hash_table = num_rows();
+ if (num_rows_hash_table == 0) {
+ return nullptr;
+ }
+
+ ThreadLocalState& local_state = local_states_[thread_id];
+ if (local_state.has_match.empty() && num_rows_hash_table > 0) {
+ local_state.has_match.resize(bit_util::BytesForBits(num_rows_hash_table) +
+ sizeof(uint64_t));
+ memset(local_state.has_match.data(), 0, bit_util::BytesForBits(num_rows_hash_table));
+ }
+
+ return local_states_[thread_id].has_match.data();
+}
+
+void SwissTableForJoin::UpdateHasMatchForKeys(int64_t thread_id, int num_ids,
+ const uint32_t* key_ids) {
+ uint8_t* bit_vector = local_has_match(thread_id);
+ if (num_ids == 0 || !bit_vector) {
+ return;
+ }
+ for (int i = 0; i < num_ids; ++i) {
+ // Mark row in hash table as having a match
+ //
+ bit_util::SetBit(bit_vector, key_ids[i]);
+ }
+}
+
+void SwissTableForJoin::MergeHasMatch() {
+ int64_t num_rows_hash_table = num_rows();
+ if (num_rows_hash_table == 0) {
+ return;
+ }
+
+ has_match_.resize(bit_util::BytesForBits(num_rows_hash_table) + sizeof(uint64_t));
+ memset(has_match_.data(), 0, bit_util::BytesForBits(num_rows_hash_table));
+
+ for (size_t tid = 0; tid < local_states_.size(); ++tid) {
+ if (!local_states_[tid].has_match.empty()) {
+ arrow::internal::BitmapOr(has_match_.data(), 0, local_states_[tid].has_match.data(),
+ 0, num_rows_hash_table, 0, has_match_.data());
+ }
+ }
+}
+
+uint32_t SwissTableForJoin::payload_id_to_key_id(uint32_t payload_id) const {
+ if (no_duplicate_keys_) {
+ return payload_id;
+ }
+ int64_t num_entries = num_keys();
+ const uint32_t* entries = key_to_payload();
+ ARROW_DCHECK(entries);
+ ARROW_DCHECK(entries[num_entries] > payload_id);
+ const uint32_t* first_greater =
+ std::upper_bound(entries, entries + num_entries + 1, payload_id);
+ ARROW_DCHECK(first_greater > entries);
+ return static_cast<uint32_t>(first_greater - entries) - 1;
+}
+
+void SwissTableForJoin::payload_ids_to_key_ids(int num_rows, const uint32_t* payload_ids,
+ uint32_t* key_ids) const {
+ if (num_rows == 0) {
+ return;
+ }
+ if (no_duplicate_keys_) {
+ memcpy(key_ids, payload_ids, num_rows * sizeof(uint32_t));
+ return;
+ }
+
+ const uint32_t* entries = key_to_payload();
+ uint32_t key_id = payload_id_to_key_id(payload_ids[0]);
+ key_ids[0] = key_id;
+ for (int i = 1; i < num_rows; ++i) {
+ ARROW_DCHECK(payload_ids[i] > payload_ids[i - 1]);
+ while (entries[key_id + 1] <= payload_ids[i]) {
+ ++key_id;
+ ARROW_DCHECK(key_id < num_keys());
+ }
+ key_ids[i] = key_id;
+ }
+}
+
+Status SwissTableForJoinBuild::Init(SwissTableForJoin* target, int dop, int64_t num_rows,
+ bool reject_duplicate_keys, bool no_payload,
+ const std::vector<KeyColumnMetadata>& key_types,
+ const std::vector<KeyColumnMetadata>& payload_types,
+ MemoryPool* pool, int64_t hardware_flags) {
+ target_ = target;
+ dop_ = dop;
+ num_rows_ = num_rows;
+
+ // Make sure that we do not use many partitions if there are not enough rows.
+ //
+ constexpr int64_t min_num_rows_per_prtn = 1 << 18;
+ log_num_prtns_ =
+ std::min(bit_util::Log2(dop_),
+ bit_util::Log2(bit_util::CeilDiv(num_rows, min_num_rows_per_prtn)));
+ num_prtns_ = 1 << log_num_prtns_;
+
+ reject_duplicate_keys_ = reject_duplicate_keys;
+ no_payload_ = no_payload;
+ pool_ = pool;
+ hardware_flags_ = hardware_flags;
+
+ prtn_states_.resize(num_prtns_);
+ thread_states_.resize(dop_);
+ prtn_locks_.Init(dop_, num_prtns_);
+
+ RowTableMetadata key_row_metadata;
+ key_row_metadata.FromColumnMetadataVector(key_types,
+ /*row_alignment=*/sizeof(uint64_t),
+ /*string_alignment=*/sizeof(uint64_t));
+ RowTableMetadata payload_row_metadata;
+ payload_row_metadata.FromColumnMetadataVector(payload_types,
+ /*row_alignment=*/sizeof(uint64_t),
+ /*string_alignment=*/sizeof(uint64_t));
+
+ for (int i = 0; i < num_prtns_; ++i) {
+ PartitionState& prtn_state = prtn_states_[i];
+ RETURN_NOT_OK(prtn_state.keys.Init(hardware_flags_, pool_));
+ RETURN_NOT_OK(prtn_state.keys.keys()->InitIfNeeded(pool, key_row_metadata));
+ RETURN_NOT_OK(prtn_state.payloads.InitIfNeeded(pool, payload_row_metadata));
+ }
+
+ target_->dop_ = dop_;
+ target_->local_states_.resize(dop_);
+ target_->no_payload_columns_ = no_payload;
+ target_->no_duplicate_keys_ = reject_duplicate_keys;
+ target_->map_.InitCallbacks();
+
+ return Status::OK();
+}
+
+Status SwissTableForJoinBuild::PushNextBatch(int64_t thread_id,
+ const ExecBatch& key_batch,
+ const ExecBatch* payload_batch_maybe_null,
+ util::TempVectorStack* temp_stack) {
+ ARROW_DCHECK(thread_id < dop_);
+ ThreadState& locals = thread_states_[thread_id];
+
+ // Compute hash
+ //
+ locals.batch_hashes.resize(key_batch.length);
+ RETURN_NOT_OK(Hashing32::HashBatch(
+ key_batch, locals.batch_hashes.data(), locals.temp_column_arrays, hardware_flags_,
+ temp_stack, /*start_row=*/0, static_cast<int>(key_batch.length)));
+
+ // Partition on hash
+ //
+ locals.batch_prtn_row_ids.resize(locals.batch_hashes.size());
+ locals.batch_prtn_ranges.resize(num_prtns_ + 1);
+ int num_rows = static_cast<int>(locals.batch_hashes.size());
+ if (num_prtns_ == 1) {
+ // We treat single partition case separately to avoid extra checks in row
+ // partitioning implementation for general case.
+ //
+ locals.batch_prtn_ranges[0] = 0;
+ locals.batch_prtn_ranges[1] = num_rows;
+ for (int i = 0; i < num_rows; ++i) {
+ locals.batch_prtn_row_ids[i] = i;
+ }
+ } else {
+ PartitionSort::Eval(
+ static_cast<int>(locals.batch_hashes.size()), num_prtns_,
+ locals.batch_prtn_ranges.data(),
+ [this, &locals](int64_t i) {
+ // SwissTable uses the highest bits of the hash for block index.
+ // We want each partition to correspond to a range of block indices,
+ // so we also partition on the highest bits of the hash.
+ //
+ return locals.batch_hashes[i] >> (31 - log_num_prtns_) >> 1;
+ },
+ [&locals](int64_t i, int pos) {
+ locals.batch_prtn_row_ids[pos] = static_cast<uint16_t>(i);
+ });
+ }
+
+ // Update hashes, shifting left to get rid of the bits that were already used
+ // for partitioning.
+ //
+ for (size_t i = 0; i < locals.batch_hashes.size(); ++i) {
+ locals.batch_hashes[i] <<= log_num_prtns_;
+ }
+
+ // For each partition:
+ // - map keys to unique integers using (this partition's) hash table
+ // - append payloads (if present) to (this partition's) row array
+ //
+ locals.temp_prtn_ids.resize(num_prtns_);
+
+ RETURN_NOT_OK(prtn_locks_.ForEachPartition(
+ thread_id, locals.temp_prtn_ids.data(),
+ /*is_prtn_empty_fn=*/
+ [&](int prtn_id) {
+ return locals.batch_prtn_ranges[prtn_id + 1] == locals.batch_prtn_ranges[prtn_id];
+ },
+ /*process_prtn_fn=*/
+ [&](int prtn_id) {
+ return ProcessPartition(thread_id, key_batch, payload_batch_maybe_null,
+ temp_stack, prtn_id);
+ }));
+
+ return Status::OK();
+}
+
+Status SwissTableForJoinBuild::ProcessPartition(int64_t thread_id,
+ const ExecBatch& key_batch,
+ const ExecBatch* payload_batch_maybe_null,
+ util::TempVectorStack* temp_stack,
+ int prtn_id) {
+ ARROW_DCHECK(thread_id < dop_);
+ ThreadState& locals = thread_states_[thread_id];
+
+ int num_rows_new =
+ locals.batch_prtn_ranges[prtn_id + 1] - locals.batch_prtn_ranges[prtn_id];
+ const uint16_t* row_ids =
+ locals.batch_prtn_row_ids.data() + locals.batch_prtn_ranges[prtn_id];
+ PartitionState& prtn_state = prtn_states_[prtn_id];
+ size_t num_rows_before = prtn_state.key_ids.size();
+ // Insert new keys into hash table associated with the current partition
+ // and map existing keys to integer ids.
+ //
+ prtn_state.key_ids.resize(num_rows_before + num_rows_new);
+ SwissTableWithKeys::Input input(&key_batch, num_rows_new, row_ids, temp_stack,
+ &locals.temp_column_arrays, &locals.temp_group_ids);
+ RETURN_NOT_OK(prtn_state.keys.MapWithInserts(
+ &input, locals.batch_hashes.data(), prtn_state.key_ids.data() + num_rows_before));
+ // Append input batch rows from current partition to an array of payload
+ // rows for this partition.
+ //
+ // The order of payloads is the same as the order of key ids accumulated
+ // in a vector (we will use the vector of key ids later on to sort
+ // payload on key ids before merging into the final row array).
+ //
+ if (!no_payload_) {
+ ARROW_DCHECK(payload_batch_maybe_null);
+ RETURN_NOT_OK(prtn_state.payloads.AppendBatchSelection(
+ pool_, *payload_batch_maybe_null, 0,
+ static_cast<int>(payload_batch_maybe_null->length), num_rows_new, row_ids,
+ locals.temp_column_arrays));
+ }
+ // We do not need to keep track of key ids if we reject rows with
+ // duplicate keys.
+ //
+ if (reject_duplicate_keys_) {
+ prtn_state.key_ids.clear();
+ }
+ return Status::OK();
+}
+
+Status SwissTableForJoinBuild::PreparePrtnMerge() {
+ // There are 4 data structures that require partition merging:
+ // 1. array of key rows
+ // 2. SwissTable
+ // 3. array of payload rows (only when no_payload_ is false)
+ // 4. mapping from key id to first payload id (only when
+ // reject_duplicate_keys_ is false and there are duplicate keys)
+ //
+
+ // 1. Array of key rows:
+ //
+ std::vector<RowArray*> partition_keys;
+ partition_keys.resize(num_prtns_);
+ for (int i = 0; i < num_prtns_; ++i) {
+ partition_keys[i] = prtn_states_[i].keys.keys();
+ }
+ RETURN_NOT_OK(RowArrayMerge::PrepareForMerge(target_->map_.keys(), partition_keys,
+ &partition_keys_first_row_id_, pool_));
+
+ // 2. SwissTable:
+ //
+ std::vector<SwissTable*> partition_tables;
+ partition_tables.resize(num_prtns_);
+ for (int i = 0; i < num_prtns_; ++i) {
+ partition_tables[i] = prtn_states_[i].keys.swiss_table();
+ }
+ std::vector<uint32_t> partition_first_group_id;
+ RETURN_NOT_OK(SwissTableMerge::PrepareForMerge(
+ target_->map_.swiss_table(), partition_tables, &partition_first_group_id, pool_));
+
+ // 3. Array of payload rows:
+ //
+ if (!no_payload_) {
+ std::vector<RowArray*> partition_payloads;
+ partition_payloads.resize(num_prtns_);
+ for (int i = 0; i < num_prtns_; ++i) {
+ partition_payloads[i] = &prtn_states_[i].payloads;
+ }
+ RETURN_NOT_OK(RowArrayMerge::PrepareForMerge(&target_->payloads_, partition_payloads,
+ &partition_payloads_first_row_id_,
+ pool_));
+ }
+
+ // Check if we have duplicate keys
+ //
+ int64_t num_keys = partition_keys_first_row_id_[num_prtns_];
+ int64_t num_rows = 0;
+ for (int i = 0; i < num_prtns_; ++i) {
+ num_rows += static_cast<int64_t>(prtn_states_[i].key_ids.size());
+ }
+ bool no_duplicate_keys = reject_duplicate_keys_ || num_keys == num_rows;
+
+ // 4. Mapping from key id to first payload id:
+ //
+ target_->no_duplicate_keys_ = no_duplicate_keys;
+ if (!no_duplicate_keys) {
+ target_->row_offset_for_key_.resize(num_keys + 1);
+ int64_t num_rows = 0;
+ for (int i = 0; i < num_prtns_; ++i) {
+ int64_t first_key = partition_keys_first_row_id_[i];
+ target_->row_offset_for_key_[first_key] = static_cast<uint32_t>(num_rows);
+ num_rows += static_cast<int64_t>(prtn_states_[i].key_ids.size());
+ }
+ target_->row_offset_for_key_[num_keys] = static_cast<uint32_t>(num_rows);
+ }
+
+ return Status::OK();
+}
+
+void SwissTableForJoinBuild::PrtnMerge(int prtn_id) {
+ PartitionState& prtn_state = prtn_states_[prtn_id];
+
+ // There are 4 data structures that require partition merging:
+ // 1. array of key rows
+ // 2. SwissTable
+ // 3. mapping from key id to first payload id (only when
+ // reject_duplicate_keys_ is false and there are duplicate keys)
+ // 4. array of payload rows (only when no_payload_ is false)
+ //
+
+ // 1. Array of key rows:
+ //
+ RowArrayMerge::MergeSingle(target_->map_.keys(), *prtn_state.keys.keys(),
+ partition_keys_first_row_id_[prtn_id],
+ /*source_rows_permutation=*/nullptr);
+
+ // 2. SwissTable:
+ //
+ SwissTableMerge::MergePartition(
+ target_->map_.swiss_table(), prtn_state.keys.swiss_table(), prtn_id, log_num_prtns_,
+ static_cast<uint32_t>(partition_keys_first_row_id_[prtn_id]),
+ &prtn_state.overflow_key_ids, &prtn_state.overflow_hashes);
+
+ std::vector<int64_t> source_payload_ids;
+
+ // 3. mapping from key id to first payload id
+ //
+ if (!target_->no_duplicate_keys_) {
+ // Count for each local (within partition) key id how many times it appears
+ // in input rows.
+ //
+ // For convenience, we use an array in merged hash table mapping key ids to
+ // first payload ids to collect the counters.
+ //
+ int64_t first_key = partition_keys_first_row_id_[prtn_id];
+ int64_t num_keys = partition_keys_first_row_id_[prtn_id + 1] - first_key;
+ uint32_t* counters = target_->row_offset_for_key_.data() + first_key;
+ uint32_t first_payload = counters[0];
+ for (int64_t i = 0; i < num_keys; ++i) {
+ counters[i] = 0;
+ }
+ for (size_t i = 0; i < prtn_state.key_ids.size(); ++i) {
+ uint32_t key_id = prtn_state.key_ids[i];
+ ++counters[key_id];
+ }
+
+ if (!no_payload_) {
+ // Count sort payloads on key id
+ //
+ // Start by computing inclusive cummulative sum of counters.
+ //
+ uint32_t sum = 0;
+ for (int64_t i = 0; i < num_keys; ++i) {
+ sum += counters[i];
+ counters[i] = sum;
+ }
+ // Now use cummulative sum of counters to obtain the target position in
+ // the sorted order for each row. At the end of this process the counters
+ // will contain exclusive cummulative sum (instead of inclusive that is
+ // there at the beginning).
+ //
+ source_payload_ids.resize(prtn_state.key_ids.size());
+ for (size_t i = 0; i < prtn_state.key_ids.size(); ++i) {
+ uint32_t key_id = prtn_state.key_ids[i];
+ int64_t position = --counters[key_id];
+ source_payload_ids[position] = static_cast<int64_t>(i);
+ }
+ // Add base payload id to all of the counters.
+ //
+ for (int64_t i = 0; i < num_keys; ++i) {
+ counters[i] += first_payload;
+ }
+ } else {
+ // When there is no payload to process, we just need to compute exclusive
+ // cummulative sum of counters and add the base payload id to all of them.
+ //
+ uint32_t sum = 0;
+ for (int64_t i = 0; i < num_keys; ++i) {
+ uint32_t sum_next = sum + counters[i];
+ counters[i] = sum + first_payload;
+ sum = sum_next;
+ }
+ }
+ }
+
+ // 4. Array of payload rows:
+ //
+ if (!no_payload_) {
+ // If there are duplicate keys, then we have already initialized permutation
+ // of payloads for this partition.
+ //
+ if (target_->no_duplicate_keys_) {
+ source_payload_ids.resize(prtn_state.key_ids.size());
+ for (size_t i = 0; i < prtn_state.key_ids.size(); ++i) {
+ uint32_t key_id = prtn_state.key_ids[i];
+ source_payload_ids[key_id] = static_cast<int64_t>(i);
+ }
+ }
+ // Merge partition payloads into target array using the permutation.
+ //
+ RowArrayMerge::MergeSingle(&target_->payloads_, prtn_state.payloads,
+ partition_payloads_first_row_id_[prtn_id],
+ source_payload_ids.data());
+ }
+}
+
+void SwissTableForJoinBuild::FinishPrtnMerge(util::TempVectorStack* temp_stack) {
+ // Process overflow key ids
+ //
+ for (int prtn_id = 0; prtn_id < num_prtns_; ++prtn_id) {
+ SwissTableMerge::InsertNewGroups(target_->map_.swiss_table(),
+ prtn_states_[prtn_id].overflow_key_ids,
+ prtn_states_[prtn_id].overflow_hashes);
+ }
+
+ // Calculate whether we have nulls in hash table keys
+ // (it is lazily evaluated but since we will be accessing it from multiple
+ // threads we need to make sure that the value gets calculated here).
+ //
+ LightContext ctx;
+ ctx.hardware_flags = hardware_flags_;
+ ctx.stack = temp_stack;
+ std::ignore = target_->map_.keys()->rows_.has_any_nulls(&ctx);
+}
+
+void JoinResultMaterialize::Init(MemoryPool* pool,
+ const HashJoinProjectionMaps* probe_schemas,
+ const HashJoinProjectionMaps* build_schemas) {
+ pool_ = pool;
+ probe_schemas_ = probe_schemas;
+ build_schemas_ = build_schemas;
+ num_rows_ = 0;
+ null_ranges_.clear();
+ num_produced_batches_ = 0;
+
+ // Initialize mapping of columns from output batch column index to key and
+ // payload batch column index.
+ //
+ probe_output_to_key_and_payload_.resize(
+ probe_schemas_->num_cols(HashJoinProjection::OUTPUT));
+ int num_key_cols = probe_schemas_->num_cols(HashJoinProjection::KEY);
+ auto to_key = probe_schemas_->map(HashJoinProjection::OUTPUT, HashJoinProjection::KEY);
+ auto to_payload =
+ probe_schemas_->map(HashJoinProjection::OUTPUT, HashJoinProjection::PAYLOAD);
+ for (int i = 0; static_cast<size_t>(i) < probe_output_to_key_and_payload_.size(); ++i) {
+ probe_output_to_key_and_payload_[i] =
+ to_key.get(i) == SchemaProjectionMap::kMissingField
+ ? to_payload.get(i) + num_key_cols
+ : to_key.get(i);
+ }
+}
+
+void JoinResultMaterialize::SetBuildSide(const RowArray* build_keys,
+ const RowArray* build_payloads,
+ bool payload_id_same_as_key_id) {
+ build_keys_ = build_keys;
+ build_payloads_ = build_payloads;
+ payload_id_same_as_key_id_ = payload_id_same_as_key_id;
+}
+
+bool JoinResultMaterialize::HasProbeOutput() const {
+ return probe_schemas_->num_cols(HashJoinProjection::OUTPUT) > 0;
+}
+
+bool JoinResultMaterialize::HasBuildKeyOutput() const {
+ auto to_key = build_schemas_->map(HashJoinProjection::OUTPUT, HashJoinProjection::KEY);
+ for (int i = 0; i < build_schemas_->num_cols(HashJoinProjection::OUTPUT); ++i) {
+ if (to_key.get(i) != SchemaProjectionMap::kMissingField) {
+ return true;
+ }
+ }
+ return false;
+}
+
+bool JoinResultMaterialize::HasBuildPayloadOutput() const {
+ auto to_payload =
+ build_schemas_->map(HashJoinProjection::OUTPUT, HashJoinProjection::PAYLOAD);
+ for (int i = 0; i < build_schemas_->num_cols(HashJoinProjection::OUTPUT); ++i) {
+ if (to_payload.get(i) != SchemaProjectionMap::kMissingField) {
+ return true;
+ }
+ }
+ return false;
+}
+
+bool JoinResultMaterialize::NeedsKeyId() const {
+ return HasBuildKeyOutput() || (HasBuildPayloadOutput() && payload_id_same_as_key_id_);
+}
+
+bool JoinResultMaterialize::NeedsPayloadId() const {
+ return HasBuildPayloadOutput() && !payload_id_same_as_key_id_;
+}
+
+Status JoinResultMaterialize::AppendProbeOnly(const ExecBatch& key_and_payload,
+ int num_rows_to_append,
+ const uint16_t* row_ids,
+ int* num_rows_appended) {
+ num_rows_to_append =
+ std::min(ExecBatchBuilder::num_rows_max() - num_rows_, num_rows_to_append);
+ if (HasProbeOutput()) {
+ RETURN_NOT_OK(batch_builder_.AppendSelected(
+ pool_, key_and_payload, num_rows_to_append, row_ids,
+ static_cast<int>(probe_output_to_key_and_payload_.size()),
+ probe_output_to_key_and_payload_.data()));
+ }
+ if (!null_ranges_.empty() &&
+ null_ranges_.back().first + null_ranges_.back().second == num_rows_) {
+ // We can extend the last range of null rows on build side.
+ //
+ null_ranges_.back().second += num_rows_to_append;
+ } else {
+ null_ranges_.push_back(
+ std::make_pair(static_cast<int>(num_rows_), num_rows_to_append));
+ }
+ num_rows_ += num_rows_to_append;
+ *num_rows_appended = num_rows_to_append;
+ return Status::OK();
+}
+
+Status JoinResultMaterialize::AppendBuildOnly(int num_rows_to_append,
+ const uint32_t* key_ids,
+ const uint32_t* payload_ids,
+ int* num_rows_appended) {
+ num_rows_to_append =
+ std::min(ExecBatchBuilder::num_rows_max() - num_rows_, num_rows_to_append);
+ if (HasProbeOutput()) {
+ RETURN_NOT_OK(batch_builder_.AppendNulls(
+ pool_, probe_schemas_->data_types(HashJoinProjection::OUTPUT),
+ num_rows_to_append));
+ }
+ if (NeedsKeyId()) {
+ ARROW_DCHECK(key_ids != nullptr);
+ key_ids_.resize(num_rows_ + num_rows_to_append);
+ memcpy(key_ids_.data() + num_rows_, key_ids, num_rows_to_append * sizeof(uint32_t));
+ }
+ if (NeedsPayloadId()) {
+ ARROW_DCHECK(payload_ids != nullptr);
+ payload_ids_.resize(num_rows_ + num_rows_to_append);
+ memcpy(payload_ids_.data() + num_rows_, payload_ids,
+ num_rows_to_append * sizeof(uint32_t));
+ }
+ num_rows_ += num_rows_to_append;
+ *num_rows_appended = num_rows_to_append;
+ return Status::OK();
+}
+
+Status JoinResultMaterialize::Append(const ExecBatch& key_and_payload,
+ int num_rows_to_append, const uint16_t* row_ids,
+ const uint32_t* key_ids, const uint32_t* payload_ids,
+ int* num_rows_appended) {
+ num_rows_to_append =
+ std::min(ExecBatchBuilder::num_rows_max() - num_rows_, num_rows_to_append);
+ if (HasProbeOutput()) {
+ RETURN_NOT_OK(batch_builder_.AppendSelected(
+ pool_, key_and_payload, num_rows_to_append, row_ids,
+ static_cast<int>(probe_output_to_key_and_payload_.size()),
+ probe_output_to_key_and_payload_.data()));
+ }
+ if (NeedsKeyId()) {
+ ARROW_DCHECK(key_ids != nullptr);
+ key_ids_.resize(num_rows_ + num_rows_to_append);
+ memcpy(key_ids_.data() + num_rows_, key_ids, num_rows_to_append * sizeof(uint32_t));
+ }
+ if (NeedsPayloadId()) {
+ ARROW_DCHECK(payload_ids != nullptr);
+ payload_ids_.resize(num_rows_ + num_rows_to_append);
+ memcpy(payload_ids_.data() + num_rows_, payload_ids,
+ num_rows_to_append * sizeof(uint32_t));
+ }
+ num_rows_ += num_rows_to_append;
+ *num_rows_appended = num_rows_to_append;
+ return Status::OK();
+}
+
+Result<std::shared_ptr<ArrayData>> JoinResultMaterialize::FlushBuildColumn(
+ const std::shared_ptr<DataType>& data_type, const RowArray* row_array, int column_id,
+ uint32_t* row_ids) {
+ ResizableArrayData output;
+ output.Init(data_type, pool_, bit_util::Log2(num_rows_));
+
+ for (size_t i = 0; i <= null_ranges_.size(); ++i) {
+ int row_id_begin =
+ i == 0 ? 0 : null_ranges_[i - 1].first + null_ranges_[i - 1].second;
+ int row_id_end = i == null_ranges_.size() ? num_rows_ : null_ranges_[i].first;
+ if (row_id_end > row_id_begin) {
+ RETURN_NOT_OK(row_array->DecodeSelected(
+ &output, column_id, row_id_end - row_id_begin, row_ids + row_id_begin, pool_));
+ }
+ int num_nulls = i == null_ranges_.size() ? 0 : null_ranges_[i].second;
+ if (num_nulls > 0) {
+ RETURN_NOT_OK(ExecBatchBuilder::AppendNulls(data_type, output, num_nulls, pool_));
+ }
+ }
+
+ return output.array_data();
+}
+
+Status JoinResultMaterialize::Flush(ExecBatch* out) {
+ if (num_rows_ == 0) {
+ return Status::OK();
+ }
+
+ out->length = num_rows_;
+ out->values.clear();
+
+ int num_probe_cols = probe_schemas_->num_cols(HashJoinProjection::OUTPUT);
+ int num_build_cols = build_schemas_->num_cols(HashJoinProjection::OUTPUT);
+ out->values.resize(num_probe_cols + num_build_cols);
+
+ if (HasProbeOutput()) {
+ ExecBatch probe_batch = batch_builder_.Flush();
+ ARROW_DCHECK(static_cast<int>(probe_batch.values.size()) == num_probe_cols);
+ for (size_t i = 0; i < probe_batch.values.size(); ++i) {
+ out->values[i] = std::move(probe_batch.values[i]);
+ }
+ }
+ auto to_key = build_schemas_->map(HashJoinProjection::OUTPUT, HashJoinProjection::KEY);
+ auto to_payload =
+ build_schemas_->map(HashJoinProjection::OUTPUT, HashJoinProjection::PAYLOAD);
+ for (int i = 0; i < num_build_cols; ++i) {
+ if (to_key.get(i) != SchemaProjectionMap::kMissingField) {
+ std::shared_ptr<ArrayData> column;
+ ARROW_ASSIGN_OR_RAISE(
+ column,
+ FlushBuildColumn(build_schemas_->data_type(HashJoinProjection::OUTPUT, i),
+ build_keys_, to_key.get(i), key_ids_.data()));
+ out->values[num_probe_cols + i] = std::move(column);
+ } else if (to_payload.get(i) != SchemaProjectionMap::kMissingField) {
+ std::shared_ptr<ArrayData> column;
+ ARROW_ASSIGN_OR_RAISE(
+ column,
+ FlushBuildColumn(
+ build_schemas_->data_type(HashJoinProjection::OUTPUT, i), build_payloads_,
+ to_payload.get(i),
+ payload_id_same_as_key_id_ ? key_ids_.data() : payload_ids_.data()));
+ out->values[num_probe_cols + i] = std::move(column);
+ } else {
+ ARROW_DCHECK(false);
+ }
+ }
+
+ num_rows_ = 0;
+ key_ids_.clear();
+ payload_ids_.clear();
+ null_ranges_.clear();
+
+ ++num_produced_batches_;
+
+ return Status::OK();
+}
+
+void JoinNullFilter::Filter(const ExecBatch& key_batch, int batch_start_row,
+ int num_batch_rows, const std::vector<JoinKeyCmp>& cmp,
+ bool* all_valid, bool and_with_input,
+ uint8_t* inout_bit_vector) {
+ // AND together validity vectors for columns that use equality comparison.
+ //
+ bool is_output_initialized = and_with_input;
+ for (size_t i = 0; i < cmp.size(); ++i) {
+ // No null filtering if null == null is true
+ //
+ if (cmp[i] != JoinKeyCmp::EQ) {
+ continue;
+ }
+
+ // No null filtering when there are no nulls
+ //
+ const Datum& data = key_batch.values[i];
+ ARROW_DCHECK(data.is_array());
+ const std::shared_ptr<ArrayData>& array_data = data.array();
+ if (!array_data->buffers[0]) {
+ continue;
+ }
+
+ const uint8_t* non_null_buffer = array_data->buffers[0]->data();
+ int64_t offset = array_data->offset + batch_start_row;
+
+ // Filter out nulls for this column
+ //
+ if (!is_output_initialized) {
+ memset(inout_bit_vector, 0xff, bit_util::BytesForBits(num_batch_rows));
+ is_output_initialized = true;
+ }
+ arrow::internal::BitmapAnd(inout_bit_vector, 0, non_null_buffer, offset,
+ num_batch_rows, 0, inout_bit_vector);
+ }
+ *all_valid = !is_output_initialized;
+}
+
+void JoinMatchIterator::SetLookupResult(int num_batch_rows, int start_batch_row,
+ const uint8_t* batch_has_match,
+ const uint32_t* key_ids, bool no_duplicate_keys,
+ const uint32_t* key_to_payload) {
+ num_batch_rows_ = num_batch_rows;
+ start_batch_row_ = start_batch_row;
+ batch_has_match_ = batch_has_match;
+ key_ids_ = key_ids;
+
+ no_duplicate_keys_ = no_duplicate_keys;
+ key_to_payload_ = key_to_payload;
+
+ current_row_ = 0;
+ current_match_for_row_ = 0;
+}
+
+bool JoinMatchIterator::GetNextBatch(int num_rows_max, int* out_num_rows,
+ uint16_t* batch_row_ids, uint32_t* key_ids,
+ uint32_t* payload_ids) {
+ *out_num_rows = 0;
+
+ if (no_duplicate_keys_) {
+ // When every input key can have at most one match,
+ // then we only need to filter according to has match bit vector.
+ //
+ // We stop when either we produce a full batch or when we reach the end of
+ // matches to output.
+ //
+ while (current_row_ < num_batch_rows_ && *out_num_rows < num_rows_max) {
+ batch_row_ids[*out_num_rows] = start_batch_row_ + current_row_;
+ key_ids[*out_num_rows] = payload_ids[*out_num_rows] = key_ids_[current_row_];
+ (*out_num_rows) += bit_util::GetBit(batch_has_match_, current_row_) ? 1 : 0;
+ ++current_row_;
+ }
+ } else {
+ // When every input key can have zero, one or many matches,
+ // then we need to filter out ones with no match and
+ // iterate over all matches for the remaining ones.
+ //
+ // We stop when either we produce a full batch or when we reach the end of
+ // matches to output.
+ //
+ while (current_row_ < num_batch_rows_ && *out_num_rows < num_rows_max) {
+ if (!bit_util::GetBit(batch_has_match_, current_row_)) {
+ ++current_row_;
+ current_match_for_row_ = 0;
+ continue;
+ }
+ uint32_t base_payload_id = key_to_payload_[key_ids_[current_row_]];
+
+ // Total number of matches for the currently selected input row
+ //
+ int num_matches_total =
+ key_to_payload_[key_ids_[current_row_] + 1] - base_payload_id;
+
+ // Number of remaining matches for the currently selected input row
+ //
+ int num_matches_left = num_matches_total - current_match_for_row_;
+
+ // Number of matches for the currently selected input row that will fit
+ // into the next batch
+ //
+ int num_matches_next = std::min(num_matches_left, num_rows_max - *out_num_rows);
+
+ for (int imatch = 0; imatch < num_matches_next; ++imatch) {
+ batch_row_ids[*out_num_rows] = start_batch_row_ + current_row_;
+ key_ids[*out_num_rows] = key_ids_[current_row_];
+ payload_ids[*out_num_rows] = base_payload_id + current_match_for_row_ + imatch;
+ ++(*out_num_rows);
+ }
+ current_match_for_row_ += num_matches_next;
+
+ if (current_match_for_row_ == num_matches_total) {
+ ++current_row_;
+ current_match_for_row_ = 0;
+ }
+ }
+ }
+
+ return (*out_num_rows) > 0;
+}
+
+void JoinProbeProcessor::Init(int num_key_columns, JoinType join_type,
+ SwissTableForJoin* hash_table,
+ std::vector<JoinResultMaterialize*> materialize,
+ const std::vector<JoinKeyCmp>* cmp,
+ OutputBatchFn output_batch_fn) {
+ num_key_columns_ = num_key_columns;
+ join_type_ = join_type;
+ hash_table_ = hash_table;
+ materialize_.resize(materialize.size());
+ for (size_t i = 0; i < materialize.size(); ++i) {
+ materialize_[i] = materialize[i];
+ }
+ cmp_ = cmp;
+ output_batch_fn_ = output_batch_fn;
+}
+
+Status JoinProbeProcessor::OnNextBatch(int64_t thread_id,
+ const ExecBatch& keypayload_batch,
+ util::TempVectorStack* temp_stack,
+ std::vector<KeyColumnArray>* temp_column_arrays) {
+ const SwissTable* swiss_table = hash_table_->keys()->swiss_table();
+ int64_t hardware_flags = swiss_table->hardware_flags();
+ int minibatch_size = swiss_table->minibatch_size();
+ int num_rows = static_cast<int>(keypayload_batch.length);
+
+ ExecBatch key_batch({}, keypayload_batch.length);
+ key_batch.values.resize(num_key_columns_);
+ for (int i = 0; i < num_key_columns_; ++i) {
+ key_batch.values[i] = keypayload_batch.values[i];
+ }
+
+ // Break into mini-batches
+ //
+ // Start by allocating mini-batch buffers
+ //
+ auto hashes_buf = util::TempVectorHolder<uint32_t>(temp_stack, minibatch_size);
+ auto match_bitvector_buf = util::TempVectorHolder<uint8_t>(
+ temp_stack, static_cast<uint32_t>(bit_util::BytesForBits(minibatch_size)));
+ auto key_ids_buf = util::TempVectorHolder<uint32_t>(temp_stack, minibatch_size);
+ auto materialize_batch_ids_buf =
+ util::TempVectorHolder<uint16_t>(temp_stack, minibatch_size);
+ auto materialize_key_ids_buf =
+ util::TempVectorHolder<uint32_t>(temp_stack, minibatch_size);
+ auto materialize_payload_ids_buf =
+ util::TempVectorHolder<uint32_t>(temp_stack, minibatch_size);
+
+ for (int minibatch_start = 0; minibatch_start < num_rows;) {
+ uint32_t minibatch_size_next = std::min(minibatch_size, num_rows - minibatch_start);
+
+ SwissTableWithKeys::Input input(&key_batch, minibatch_start,
+ minibatch_start + minibatch_size_next, temp_stack,
+ temp_column_arrays);
+ hash_table_->keys()->Hash(&input, hashes_buf.mutable_data(), hardware_flags);
+ hash_table_->keys()->MapReadOnly(&input, hashes_buf.mutable_data(),
+ match_bitvector_buf.mutable_data(),
+ key_ids_buf.mutable_data());
+
+ // AND bit vector with null key filter for join
+ //
+ bool ignored;
+ JoinNullFilter::Filter(key_batch, minibatch_start, minibatch_size_next, *cmp_,
+ &ignored,
+ /*and_with_input=*/true, match_bitvector_buf.mutable_data());
+ // Semi-joins
+ //
+ if (join_type_ == JoinType::LEFT_SEMI || join_type_ == JoinType::LEFT_ANTI ||
+ join_type_ == JoinType::RIGHT_SEMI || join_type_ == JoinType::RIGHT_ANTI) {
+ int num_passing_ids = 0;
+ util::bit_util::bits_to_indexes(
+ (join_type_ == JoinType::LEFT_ANTI) ? 0 : 1, hardware_flags,
+ minibatch_size_next, match_bitvector_buf.mutable_data(), &num_passing_ids,
+ materialize_batch_ids_buf.mutable_data());
+
+ // For right-semi, right-anti joins: update has-match flags for the rows
+ // in hash table.
+ //
+ if (join_type_ == JoinType::RIGHT_SEMI || join_type_ == JoinType::RIGHT_ANTI) {
+ for (int i = 0; i < num_passing_ids; ++i) {
+ uint16_t id = materialize_batch_ids_buf.mutable_data()[i];
+ key_ids_buf.mutable_data()[i] = key_ids_buf.mutable_data()[id];
+ }
+ hash_table_->UpdateHasMatchForKeys(thread_id, num_passing_ids,
+ key_ids_buf.mutable_data());
+ } else {
+ // For left-semi, left-anti joins: call materialize using match
+ // bit-vector.
+ //
+
+ // Add base batch row index.
+ //
+ for (int i = 0; i < num_passing_ids; ++i) {
+ materialize_batch_ids_buf.mutable_data()[i] +=
+ static_cast<uint16_t>(minibatch_start);
+ }
+
+ RETURN_NOT_OK(materialize_[thread_id]->AppendProbeOnly(
+ keypayload_batch, num_passing_ids, materialize_batch_ids_buf.mutable_data(),
+ [&](ExecBatch batch) { output_batch_fn_(thread_id, std::move(batch)); }));
+ }
+ } else {
+ // We need to output matching pairs of rows from both sides of the join.
+ // Since every hash table lookup for an input row might have multiple
+ // matches we use a helper class that implements enumerating all of them.
+ //
+ bool no_duplicate_keys = (hash_table_->key_to_payload() == nullptr);
+ bool no_payload_columns = (hash_table_->payloads() == nullptr);
+ JoinMatchIterator match_iterator;
+ match_iterator.SetLookupResult(
+ minibatch_size_next, minibatch_start, match_bitvector_buf.mutable_data(),
+ key_ids_buf.mutable_data(), no_duplicate_keys, hash_table_->key_to_payload());
+ int num_matches_next;
+ while (match_iterator.GetNextBatch(minibatch_size, &num_matches_next,
+ materialize_batch_ids_buf.mutable_data(),
+ materialize_key_ids_buf.mutable_data(),
+ materialize_payload_ids_buf.mutable_data())) {
+ const uint16_t* materialize_batch_ids = materialize_batch_ids_buf.mutable_data();
+ const uint32_t* materialize_key_ids = materialize_key_ids_buf.mutable_data();
+ const uint32_t* materialize_payload_ids =
+ no_duplicate_keys || no_payload_columns
+ ? materialize_key_ids_buf.mutable_data()
+ : materialize_payload_ids_buf.mutable_data();
+
+ // For right-outer, full-outer joins we need to update has-match flags
+ // for the rows in hash table.
+ //
+ if (join_type_ == JoinType::RIGHT_OUTER || join_type_ == JoinType::FULL_OUTER) {
+ hash_table_->UpdateHasMatchForKeys(thread_id, num_matches_next,
+ materialize_key_ids);
+ }
+
+ // Call materialize for resulting id tuples pointing to matching pairs
+ // of rows.
+ //
+ RETURN_NOT_OK(materialize_[thread_id]->Append(
+ keypayload_batch, num_matches_next, materialize_batch_ids,
+ materialize_key_ids, materialize_payload_ids,
+ [&](ExecBatch batch) { output_batch_fn_(thread_id, std::move(batch)); }));
+ }
+
+ // For left-outer and full-outer joins output non-matches.
+ //
+ // Call materialize. Nulls will be output in all columns that come from
+ // the other side of the join.
+ //
+ if (join_type_ == JoinType::LEFT_OUTER || join_type_ == JoinType::FULL_OUTER) {
+ int num_passing_ids = 0;
+ util::bit_util::bits_to_indexes(
+ /*bit_to_search=*/0, hardware_flags, minibatch_size_next,
+ match_bitvector_buf.mutable_data(), &num_passing_ids,
+ materialize_batch_ids_buf.mutable_data());
+
+ // Add base batch row index.
+ //
+ for (int i = 0; i < num_passing_ids; ++i) {
+ materialize_batch_ids_buf.mutable_data()[i] +=
+ static_cast<uint16_t>(minibatch_start);
+ }
+
+ RETURN_NOT_OK(materialize_[thread_id]->AppendProbeOnly(
+ keypayload_batch, num_passing_ids, materialize_batch_ids_buf.mutable_data(),
+ [&](ExecBatch batch) { output_batch_fn_(thread_id, std::move(batch)); }));
+ }
+ }
+
+ minibatch_start += minibatch_size_next;
+ }
+
+ return Status::OK();
+}
+
+Status JoinProbeProcessor::OnFinished() {
+ // Flush all instances of materialize that have non-zero accumulated output
+ // rows.
+ //
+ for (size_t i = 0; i < materialize_.size(); ++i) {
+ JoinResultMaterialize& materialize = *materialize_[i];
+ RETURN_NOT_OK(materialize.Flush(
+ [&](ExecBatch batch) { output_batch_fn_(i, std::move(batch)); }));
+ }
+
+ return Status::OK();
+}
+
+class SwissJoin : public HashJoinImpl {
+ public:
+ Status Init(ExecContext* ctx, JoinType join_type, size_t num_threads,
+ const HashJoinProjectionMaps* proj_map_left,
+ const HashJoinProjectionMaps* proj_map_right,
+ std::vector<JoinKeyCmp> key_cmp, Expression filter,
+ OutputBatchCallback output_batch_callback,
+ FinishedCallback finished_callback, TaskScheduler* scheduler) override {
+ START_COMPUTE_SPAN(span_, "SwissJoinImpl",
+ {{"detail", filter.ToString()},
+ {"join.kind", arrow::compute::ToString(join_type)},
+ {"join.threads", static_cast<uint32_t>(num_threads)}});
+
+ num_threads_ = static_cast<int>(num_threads);
+ ctx_ = ctx;
+ hardware_flags_ = ctx->cpu_info()->hardware_flags();
+ pool_ = ctx->memory_pool();
+
+ join_type_ = join_type;
+ key_cmp_.resize(key_cmp.size());
+ for (size_t i = 0; i < key_cmp.size(); ++i) {
+ key_cmp_[i] = key_cmp[i];
+ }
+ schema_[0] = proj_map_left;
+ schema_[1] = proj_map_right;
+ output_batch_callback_ = output_batch_callback;
+ finished_callback_ = finished_callback;
+ scheduler_ = scheduler;
+ hash_table_ready_.store(false);
+ cancelled_.store(false);
+ {
+ std::lock_guard<std::mutex> lock(state_mutex_);
+ left_side_finished_ = false;
+ right_side_finished_ = false;
+ error_status_ = Status::OK();
+ }
+
+ local_states_.resize(num_threads_);
+ for (int i = 0; i < num_threads_; ++i) {
+ local_states_[i].hash_table_ready = false;
+ local_states_[i].num_output_batches = 0;
+ RETURN_NOT_OK(CancelIfNotOK(local_states_[i].temp_stack.Init(
+ pool_, 1024 + 64 * util::MiniBatch::kMiniBatchLength)));
+ local_states_[i].materialize.Init(pool_, proj_map_left, proj_map_right);
+ }
+
+ std::vector<JoinResultMaterialize*> materialize;
+ materialize.resize(num_threads_);
+ for (int i = 0; i < num_threads_; ++i) {
+ materialize[i] = &local_states_[i].materialize;
+ }
+
+ probe_processor_.Init(proj_map_left->num_cols(HashJoinProjection::KEY), join_type_,
+ &hash_table_, materialize, &key_cmp_, output_batch_callback_);
+
+ InitTaskGroups();
+
+ return Status::OK();
+ }
+
+ void InitTaskGroups() {
+ task_group_build_ = scheduler_->RegisterTaskGroup(
+ [this](size_t thread_index, int64_t task_id) -> Status {
+ return BuildTask(thread_index, task_id);
+ },
+ [this](size_t thread_index) -> Status { return BuildFinished(thread_index); });
+ task_group_merge_ = scheduler_->RegisterTaskGroup(
+ [this](size_t thread_index, int64_t task_id) -> Status {
+ return MergeTask(thread_index, task_id);
+ },
+ [this](size_t thread_index) -> Status { return MergeFinished(thread_index); });
+ task_group_scan_ = scheduler_->RegisterTaskGroup(
+ [this](size_t thread_index, int64_t task_id) -> Status {
+ return ScanTask(thread_index, task_id);
+ },
+ [this](size_t thread_index) -> Status { return ScanFinished(thread_index); });
+ }
+
+ Status ProbeSingleBatch(size_t thread_index, ExecBatch batch) override {
+ if (IsCancelled()) {
+ return status();
+ }
+
+ if (!local_states_[thread_index].hash_table_ready) {
+ local_states_[thread_index].hash_table_ready = hash_table_ready_.load();
+ }
+ ARROW_DCHECK(local_states_[thread_index].hash_table_ready);
+
+ ExecBatch keypayload_batch;
+ ARROW_ASSIGN_OR_RAISE(keypayload_batch, KeyPayloadFromInput(/*side=*/0, &batch));
+
+ return CancelIfNotOK(probe_processor_.OnNextBatch(
+ thread_index, keypayload_batch, &local_states_[thread_index].temp_stack,
+ &local_states_[thread_index].temp_column_arrays));
+ }
+
+ Status ProbingFinished(size_t thread_index) override {
+ if (IsCancelled()) {
+ return status();
+ }
+
+ return CancelIfNotOK(StartScanHashTable(static_cast<int64_t>(thread_index)));
+ }
+
+ Status BuildHashTable(size_t thread_id, AccumulationQueue batches,
+ BuildFinishedCallback on_finished) override {
+ if (IsCancelled()) {
+ return status();
+ }
+
+ build_side_batches_ = std::move(batches);
+ build_finished_callback_ = on_finished;
+
+ return CancelIfNotOK(StartBuildHashTable(static_cast<int64_t>(thread_id)));
+ }
+
+ void Abort(TaskScheduler::AbortContinuationImpl pos_abort_callback) override {
+ EVENT(span_, "Abort");
+ END_SPAN(span_);
+ std::ignore = CancelIfNotOK(Status::Cancelled("Hash Join Cancelled"));
+ scheduler_->Abort(std::move(pos_abort_callback));
+ }
+
+ std::string ToString() const override { return "SwissJoin"; }
+
+ private:
+ Status StartBuildHashTable(int64_t thread_id) {
+ // Initialize build class instance
+ //
+ const HashJoinProjectionMaps* schema = schema_[1];
+ bool reject_duplicate_keys =
+ join_type_ == JoinType::LEFT_SEMI || join_type_ == JoinType::LEFT_ANTI;
+ bool no_payload =
+ reject_duplicate_keys || schema->num_cols(HashJoinProjection::PAYLOAD) == 0;
+
+ std::vector<KeyColumnMetadata> key_types;
+ for (int i = 0; i < schema->num_cols(HashJoinProjection::KEY); ++i) {
+ ARROW_ASSIGN_OR_RAISE(
+ KeyColumnMetadata metadata,
+ ColumnMetadataFromDataType(schema->data_type(HashJoinProjection::KEY, i)));
+ key_types.push_back(metadata);
+ }
+ std::vector<KeyColumnMetadata> payload_types;
+ for (int i = 0; i < schema->num_cols(HashJoinProjection::PAYLOAD); ++i) {
+ ARROW_ASSIGN_OR_RAISE(
+ KeyColumnMetadata metadata,
+ ColumnMetadataFromDataType(schema->data_type(HashJoinProjection::PAYLOAD, i)));
+ payload_types.push_back(metadata);
+ }
+ RETURN_NOT_OK(CancelIfNotOK(hash_table_build_.Init(
+ &hash_table_, num_threads_, build_side_batches_.row_count(),
+ reject_duplicate_keys, no_payload, key_types, payload_types, pool_,
+ hardware_flags_)));
+
+ // Process all input batches
+ //
+ return CancelIfNotOK(scheduler_->StartTaskGroup(static_cast<size_t>(thread_id),
+ task_group_build_,
+ build_side_batches_.batch_count()));
+ }
+
+ Status BuildTask(size_t thread_id, int64_t batch_id) {
+ if (IsCancelled()) {
+ return Status::OK();
+ }
+
+ const HashJoinProjectionMaps* schema = schema_[1];
+ bool no_payload = hash_table_build_.no_payload();
+
+ ExecBatch input_batch;
+ ARROW_ASSIGN_OR_RAISE(
+ input_batch, KeyPayloadFromInput(/*side=*/1, &build_side_batches_[batch_id]));
+
+ if (input_batch.length == 0) {
+ return Status::OK();
+ }
+
+ // Split batch into key batch and optional payload batch
+ //
+ // Input batch is key-payload batch (key columns followed by payload
+ // columns). We split it into two separate batches.
+ //
+ // TODO: Change SwissTableForJoinBuild interface to use key-payload
+ // batch instead to avoid this operation, which involves increasing
+ // shared pointer ref counts.
+ //
+ ExecBatch key_batch({}, input_batch.length);
+ key_batch.values.resize(schema->num_cols(HashJoinProjection::KEY));
+ for (size_t icol = 0; icol < key_batch.values.size(); ++icol) {
+ key_batch.values[icol] = input_batch.values[icol];
+ }
+ ExecBatch payload_batch({}, input_batch.length);
+
+ if (!no_payload) {
+ payload_batch.values.resize(schema->num_cols(HashJoinProjection::PAYLOAD));
+ for (size_t icol = 0; icol < payload_batch.values.size(); ++icol) {
+ payload_batch.values[icol] =
+ input_batch.values[schema->num_cols(HashJoinProjection::KEY) + icol];
+ }
+ }
+ RETURN_NOT_OK(CancelIfNotOK(hash_table_build_.PushNextBatch(
+ static_cast<int64_t>(thread_id), key_batch, no_payload ? nullptr : &payload_batch,
+ &local_states_[thread_id].temp_stack)));
+
+ // Release input batch
+ //
+ input_batch.values.clear();
+
+ return Status::OK();
+ }
+
+ Status BuildFinished(size_t thread_id) {
+ RETURN_NOT_OK(status());
+
+ build_side_batches_.Clear();
+
+ // On a single thread prepare for merging partitions of the resulting hash
+ // table.
+ //
+ RETURN_NOT_OK(CancelIfNotOK(hash_table_build_.PreparePrtnMerge()));
+ return CancelIfNotOK(scheduler_->StartTaskGroup(thread_id, task_group_merge_,
+ hash_table_build_.num_prtns()));
+ }
+
+ Status MergeTask(size_t /*thread_id*/, int64_t prtn_id) {
+ if (IsCancelled()) {
+ return Status::OK();
+ }
+ hash_table_build_.PrtnMerge(static_cast<int>(prtn_id));
+ return Status::OK();
+ }
+
+ Status MergeFinished(size_t thread_id) {
+ RETURN_NOT_OK(status());
+ hash_table_build_.FinishPrtnMerge(&local_states_[thread_id].temp_stack);
+ return CancelIfNotOK(OnBuildHashTableFinished(static_cast<int64_t>(thread_id)));
+ }
+
+ Status OnBuildHashTableFinished(int64_t thread_id) {
+ if (IsCancelled()) {
+ return status();
+ }
+
+ for (int i = 0; i < num_threads_; ++i) {
+ local_states_[i].materialize.SetBuildSide(hash_table_.keys()->keys(),
+ hash_table_.payloads(),
+ hash_table_.key_to_payload() == nullptr);
+ }
+ hash_table_ready_.store(true);
+
+ return build_finished_callback_(thread_id);
+ }
+
+ Status StartScanHashTable(int64_t thread_id) {
+ if (IsCancelled()) {
+ return status();
+ }
+
+ bool need_to_scan =
+ (join_type_ == JoinType::RIGHT_SEMI || join_type_ == JoinType::RIGHT_ANTI ||
+ join_type_ == JoinType::RIGHT_OUTER || join_type_ == JoinType::FULL_OUTER);
+
+ if (need_to_scan) {
+ hash_table_.MergeHasMatch();
+ int64_t num_tasks = bit_util::CeilDiv(hash_table_.num_rows(), kNumRowsPerScanTask);
+
+ return CancelIfNotOK(scheduler_->StartTaskGroup(static_cast<size_t>(thread_id),
+ task_group_scan_, num_tasks));
+ } else {
+ return CancelIfNotOK(OnScanHashTableFinished());
+ }
+ }
+
+ Status ScanTask(size_t thread_id, int64_t task_id) {
+ if (IsCancelled()) {
+ return Status::OK();
+ }
+
+ // Should we output matches or non-matches?
+ //
+ bool bit_to_output = (join_type_ == JoinType::RIGHT_SEMI);
+
+ int64_t start_row = task_id * kNumRowsPerScanTask;
+ int64_t end_row =
+ std::min((task_id + 1) * kNumRowsPerScanTask, hash_table_.num_rows());
+ // Get thread index and related temp vector stack
+ //
+ util::TempVectorStack* temp_stack = &local_states_[thread_id].temp_stack;
+
+ // Split into mini-batches
+ //
+ auto payload_ids_buf =
+ util::TempVectorHolder<uint32_t>(temp_stack, util::MiniBatch::kMiniBatchLength);
+ auto key_ids_buf =
+ util::TempVectorHolder<uint32_t>(temp_stack, util::MiniBatch::kMiniBatchLength);
+ auto selection_buf =
+ util::TempVectorHolder<uint16_t>(temp_stack, util::MiniBatch::kMiniBatchLength);
+ for (int64_t mini_batch_start = start_row; mini_batch_start < end_row;) {
+ // Compute the size of the next mini-batch
+ //
+ int64_t mini_batch_size_next =
+ std::min(end_row - mini_batch_start,
+ static_cast<int64_t>(util::MiniBatch::kMiniBatchLength));
+
+ // Get the list of key and payload ids from this mini-batch to output.
+ //
+ uint32_t first_key_id =
+ hash_table_.payload_id_to_key_id(static_cast<uint32_t>(mini_batch_start));
+ uint32_t last_key_id = hash_table_.payload_id_to_key_id(
+ static_cast<uint32_t>(mini_batch_start + mini_batch_size_next - 1));
+ int num_output_rows = 0;
+ for (uint32_t key_id = first_key_id; key_id <= last_key_id; ++key_id) {
+ if (bit_util::GetBit(hash_table_.has_match(), key_id) == bit_to_output) {
+ uint32_t first_payload_for_key =
+ std::max(static_cast<uint32_t>(mini_batch_start),
+ hash_table_.key_to_payload() ? hash_table_.key_to_payload()[key_id]
+ : key_id);
+ uint32_t last_payload_for_key = std::min(
+ static_cast<uint32_t>(mini_batch_start + mini_batch_size_next - 1),
+ hash_table_.key_to_payload() ? hash_table_.key_to_payload()[key_id + 1] - 1
+ : key_id);
+ uint32_t num_payloads_for_key =
+ last_payload_for_key - first_payload_for_key + 1;
+ for (uint32_t i = 0; i < num_payloads_for_key; ++i) {
+ key_ids_buf.mutable_data()[num_output_rows + i] = key_id;
+ payload_ids_buf.mutable_data()[num_output_rows + i] =
+ first_payload_for_key + i;
+ }
+ num_output_rows += num_payloads_for_key;
+ }
+ }
+
+ if (num_output_rows > 0) {
+ // Materialize (and output whenever buffers get full) hash table
+ // values according to the generated list of ids.
+ //
+ Status status = local_states_[thread_id].materialize.AppendBuildOnly(
+ num_output_rows, key_ids_buf.mutable_data(), payload_ids_buf.mutable_data(),
+ [&](ExecBatch batch) {
+ output_batch_callback_(static_cast<int64_t>(thread_id), std::move(batch));
+ });
+ RETURN_NOT_OK(CancelIfNotOK(status));
+ if (!status.ok()) {
+ break;
+ }
+ }
+ mini_batch_start += mini_batch_size_next;
+ }
+
+ return Status::OK();
+ }
+
+ Status ScanFinished(size_t thread_id) {
+ if (IsCancelled()) {
+ return status();
+ }
+
+ return CancelIfNotOK(OnScanHashTableFinished());
+ }
+
+ Status OnScanHashTableFinished() {
+ if (IsCancelled()) {
+ return status();
+ }
+ END_SPAN(span_);
+
+ // Flush all instances of materialize that have non-zero accumulated output
+ // rows.
+ //
+ RETURN_NOT_OK(CancelIfNotOK(probe_processor_.OnFinished()));
+
+ int64_t num_produced_batches = 0;
+ for (size_t i = 0; i < local_states_.size(); ++i) {
+ JoinResultMaterialize& materialize = local_states_[i].materialize;
+ num_produced_batches += materialize.num_produced_batches();
+ }
+
+ finished_callback_(num_produced_batches);
+
+ return Status::OK();
+ }
+
+ Result<ExecBatch> KeyPayloadFromInput(int side, ExecBatch* input) {
+ ExecBatch projected({}, input->length);
+ int num_key_cols = schema_[side]->num_cols(HashJoinProjection::KEY);
+ int num_payload_cols = schema_[side]->num_cols(HashJoinProjection::PAYLOAD);
+ projected.values.resize(num_key_cols + num_payload_cols);
+
+ auto key_to_input =
+ schema_[side]->map(HashJoinProjection::KEY, HashJoinProjection::INPUT);
+ for (int icol = 0; icol < num_key_cols; ++icol) {
+ const Datum& value_in = input->values[key_to_input.get(icol)];
+ if (value_in.is_scalar()) {
+ ARROW_ASSIGN_OR_RAISE(
+ projected.values[icol],
+ MakeArrayFromScalar(*value_in.scalar(), projected.length, pool_));
+ } else {
+ projected.values[icol] = value_in;
+ }
+ }
+ auto payload_to_input =
+ schema_[side]->map(HashJoinProjection::PAYLOAD, HashJoinProjection::INPUT);
+ for (int icol = 0; icol < num_payload_cols; ++icol) {
+ const Datum& value_in = input->values[payload_to_input.get(icol)];
+ if (value_in.is_scalar()) {
+ ARROW_ASSIGN_OR_RAISE(
+ projected.values[num_key_cols + icol],
+ MakeArrayFromScalar(*value_in.scalar(), projected.length, pool_));
+ } else {
+ projected.values[num_key_cols + icol] = value_in;
+ }
+ }
+
+ return projected;
+ }
+
+ bool IsCancelled() { return cancelled_.load(); }
+
+ Status status() {
+ if (IsCancelled()) {
+ std::lock_guard<std::mutex> lock(state_mutex_);
+ return error_status_;
+ }
+ return Status::OK();
+ }
+
+ Status CancelIfNotOK(Status status) {
+ if (!status.ok()) {
+ {
+ std::lock_guard<std::mutex> lock(state_mutex_);
+ // Only update the status for the first error encountered.
+ //
+ if (error_status_.ok()) {
+ error_status_ = status;
+ }
+ }
+ cancelled_.store(true);
+ }
+ return status;
+ }
+
+ static constexpr int kNumRowsPerScanTask = 512 * 1024;
+
+ ExecContext* ctx_;
+ int64_t hardware_flags_;
+ MemoryPool* pool_;
+ int num_threads_;
+ JoinType join_type_;
+ std::vector<JoinKeyCmp> key_cmp_;
+ const HashJoinProjectionMaps* schema_[2];
+
+ // Task scheduling
+ TaskScheduler* scheduler_;
+ int task_group_build_;
+ int task_group_merge_;
+ int task_group_scan_;
+
+ // Callbacks
+ OutputBatchCallback output_batch_callback_;
+ BuildFinishedCallback build_finished_callback_;
+ FinishedCallback finished_callback_;
+
+ struct ThreadLocalState {
+ JoinResultMaterialize materialize;
+ util::TempVectorStack temp_stack;
+ std::vector<KeyColumnArray> temp_column_arrays;
+ int64_t num_output_batches;
+ bool hash_table_ready;
+ };
+ std::vector<ThreadLocalState> local_states_;
+
+ SwissTableForJoin hash_table_;
+ JoinProbeProcessor probe_processor_;
+ SwissTableForJoinBuild hash_table_build_;
+ AccumulationQueue build_side_batches_;
+
+ // Atomic state flags.
+ // These flags are kept outside of mutex, since they can be queried for every
+ // batch.
+ //
+ // The other flags that follow them, protected by mutex, will be queried or
+ // updated only a fixed number of times during entire join processing.
+ //
+ std::atomic<bool> hash_table_ready_;
+ std::atomic<bool> cancelled_;
+
+ // Mutex protecting state flags.
+ //
+ std::mutex state_mutex_;
+
+ // Mutex protected state flags.
+ //
+ bool left_side_finished_;
+ bool right_side_finished_;
+ Status error_status_;
+};
+
+Result<std::unique_ptr<HashJoinImpl>> HashJoinImpl::MakeSwiss() {
+ std::unique_ptr<HashJoinImpl> impl{new SwissJoin()};
+ return std::move(impl);
+}
+
+} // namespace compute
+} // namespace arrow
diff --git a/cpp/src/arrow/compute/exec/swiss_join.h b/cpp/src/arrow/compute/exec/swiss_join.h
new file mode 100644
index 0000000000..bf3273c4e0
--- /dev/null
+++ b/cpp/src/arrow/compute/exec/swiss_join.h
@@ -0,0 +1,761 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#pragma once
+
+#include <cstdint>
+#include "arrow/compute/exec/key_map.h"
+#include "arrow/compute/exec/options.h"
+#include "arrow/compute/exec/partition_util.h"
+#include "arrow/compute/exec/schema_util.h"
+#include "arrow/compute/exec/task_util.h"
+#include "arrow/compute/kernels/row_encoder.h"
+#include "arrow/compute/light_array.h"
+#include "arrow/compute/row/encode_internal.h"
+
+namespace arrow {
+namespace compute {
+
+class RowArrayAccessor {
+ public:
+ // Find the index of this varbinary column within the sequence of all
+ // varbinary columns encoded in rows.
+ //
+ static int VarbinaryColumnId(const RowTableMetadata& row_metadata, int column_id);
+
+ // Calculate how many rows to skip from the tail of the
+ // sequence of selected rows, such that the total size of skipped rows is at
+ // least equal to the size specified by the caller. Skipping of the tail rows
+ // is used to allow for faster processing by the caller of remaining rows
+ // without checking buffer bounds (useful with SIMD or fixed size memory loads
+ // and stores).
+ //
+ static int NumRowsToSkip(const RowTableImpl& rows, int column_id, int num_rows,
+ const uint32_t* row_ids, int num_tail_bytes_to_skip);
+
+ // The supplied lambda will be called for each row in the given list of rows.
+ // The arguments given to it will be:
+ // - index of a row (within the set of selected rows),
+ // - pointer to the value,
+ // - byte length of the value.
+ //
+ // The information about nulls (validity bitmap) is not used in this call and
+ // has to be processed separately.
+ //
+ template <class PROCESS_VALUE_FN>
+ static void Visit(const RowTableImpl& rows, int column_id, int num_rows,
+ const uint32_t* row_ids, PROCESS_VALUE_FN process_value_fn);
+
+ // The supplied lambda will be called for each row in the given list of rows.
+ // The arguments given to it will be:
+ // - index of a row (within the set of selected rows),
+ // - byte 0xFF if the null is set for the row or 0x00 otherwise.
+ //
+ template <class PROCESS_VALUE_FN>
+ static void VisitNulls(const RowTableImpl& rows, int column_id, int num_rows,
+ const uint32_t* row_ids, PROCESS_VALUE_FN process_value_fn);
+
+ private:
+#if defined(ARROW_HAVE_AVX2)
+ // This is equivalent to Visit method, but processing 8 rows at a time in a
+ // loop.
+ // Returns the number of processed rows, which may be less than requested (up
+ // to 7 rows at the end may be skipped).
+ //
+ template <class PROCESS_8_VALUES_FN>
+ static int Visit_avx2(const RowTableImpl& rows, int column_id, int num_rows,
+ const uint32_t* row_ids, PROCESS_8_VALUES_FN process_8_values_fn);
+
+ // This is equivalent to VisitNulls method, but processing 8 rows at a time in
+ // a loop. Returns the number of processed rows, which may be less than
+ // requested (up to 7 rows at the end may be skipped).
+ //
+ template <class PROCESS_8_VALUES_FN>
+ static int VisitNulls_avx2(const RowTableImpl& rows, int column_id, int num_rows,
+ const uint32_t* row_ids,
+ PROCESS_8_VALUES_FN process_8_values_fn);
+#endif
+};
+
+// Write operations (appending batch rows) must not be called by more than one
+// thread at the same time.
+//
+// Read operations (row comparison, column decoding)
+// can be called by multiple threads concurrently.
+//
+struct RowArray {
+ RowArray() : is_initialized_(false) {}
+
+ Status InitIfNeeded(MemoryPool* pool, const ExecBatch& batch);
+ Status InitIfNeeded(MemoryPool* pool, const RowTableMetadata& row_metadata);
+
+ Status AppendBatchSelection(MemoryPool* pool, const ExecBatch& batch, int begin_row_id,
+ int end_row_id, int num_row_ids, const uint16_t* row_ids,
+ std::vector<KeyColumnArray>& temp_column_arrays);
+
+ // This can only be called for a minibatch.
+ //
+ void Compare(const ExecBatch& batch, int begin_row_id, int end_row_id, int num_selected,
+ const uint16_t* batch_selection_maybe_null, const uint32_t* array_row_ids,
+ uint32_t* out_num_not_equal, uint16_t* out_not_equal_selection,
+ int64_t hardware_flags, util::TempVectorStack* temp_stack,
+ std::vector<KeyColumnArray>& temp_column_arrays,
+ uint8_t* out_match_bitvector_maybe_null = NULLPTR);
+
+ // TODO: add AVX2 version
+ //
+ Status DecodeSelected(ResizableArrayData* target, int column_id, int num_rows_to_append,
+ const uint32_t* row_ids, MemoryPool* pool) const;
+
+ void DebugPrintToFile(const char* filename, bool print_sorted) const;
+
+ int64_t num_rows() const { return is_initialized_ ? rows_.length() : 0; }
+
+ bool is_initialized_;
+ RowTableEncoder encoder_;
+ RowTableImpl rows_;
+ RowTableImpl rows_temp_;
+};
+
+// Implements concatenating multiple row arrays into a single one, using
+// potentially multiple threads, each processing a single input row array.
+//
+class RowArrayMerge {
+ public:
+ // Calculate total number of rows and size in bytes for merged sequence of
+ // rows and allocate memory for it.
+ //
+ // If the rows are of varying length, initialize in the offset array the first
+ // entry for the write area for each input row array. Leave all other
+ // offsets and buffers uninitialized.
+ //
+ // All input sources must be initialized, but they can contain zero rows.
+ //
+ // Output in vector the first target row id for each source (exclusive
+ // cummulative sum of number of rows in sources). This output is optional,
+ // caller can pass in nullptr to indicate that it is not needed.
+ //
+ static Status PrepareForMerge(RowArray* target, const std::vector<RowArray*>& sources,
+ std::vector<int64_t>* first_target_row_id,
+ MemoryPool* pool);
+
+ // Copy rows from source array to target array.
+ // Both arrays must have the same row metadata.
+ // Target array must already have the memory reserved in all internal buffers
+ // for the copy of the rows.
+ //
+ // Copy of the rows will occupy the same amount of space in the target array
+ // buffers as in the source array, but in the target array we pick at what row
+ // position and offset we start writing.
+ //
+ // Optionally, the rows may be reordered during copy according to the
+ // provided permutation, which represents some sorting order of source rows.
+ // Nth element of the permutation array is the source row index for the Nth
+ // row written into target array. If permutation is missing (null), then the
+ // order of source rows will remain unchanged.
+ //
+ // In case of varying length rows, we purposefully skip outputting of N+1 (one
+ // after last) offset, to allow concurrent copies of rows done to adjacent
+ // ranges in the target array. This offset should already contain the right
+ // value after calling the method preparing target array for merge (which
+ // initializes boundary offsets for target row ranges for each source).
+ //
+ static void MergeSingle(RowArray* target, const RowArray& source,
+ int64_t first_target_row_id,
+ const int64_t* source_rows_permutation);
+
+ private:
+ // Copy rows from source array to a region of the target array.
+ // This implementation is for fixed length rows.
+ // Null information needs to be handled separately.
+ //
+ static void CopyFixedLength(RowTableImpl* target, const RowTableImpl& source,
+ int64_t first_target_row_id,
+ const int64_t* source_rows_permutation);
+
+ // Copy rows from source array to a region of the target array.
+ // This implementation is for varying length rows.
+ // Null information needs to be handled separately.
+ //
+ static void CopyVaryingLength(RowTableImpl* target, const RowTableImpl& source,
+ int64_t first_target_row_id,
+ int64_t first_target_row_offset,
+ const int64_t* source_rows_permutation);
+
+ // Copy null information from rows from source array to a region of the target
+ // array.
+ //
+ static void CopyNulls(RowTableImpl* target, const RowTableImpl& source,
+ int64_t first_target_row_id,
+ const int64_t* source_rows_permutation);
+};
+
+// Implements merging of multiple SwissTables into a single one, using
+// potentially multiple threads, each processing a single input source.
+//
+// Each source should correspond to a range of original hashes.
+// A row belongs to a source with index determined by K highest bits of
+// original hash. That means that the number of sources must be a power of 2.
+//
+// We assume that the hash values used and stored inside source tables
+// have K highest bits removed from the original hash in order to avoid huge
+// number of hash collisions that would occur otherwise.
+// These bits will be reinserted back (original hashes will be used) when
+// merging into target.
+//
+class SwissTableMerge {
+ public:
+ // Calculate total number of blocks for merged table.
+ // Allocate buffers sized accordingly and initialize empty target table.
+ //
+ // All input sources must be initialized, but they can be empty.
+ //
+ // Output in a vector the first target group id for each source (exclusive
+ // cummulative sum of number of groups in sources). This output is optional,
+ // caller can pass in nullptr to indicate that it is not needed.
+ //
+ static Status PrepareForMerge(SwissTable* target,
+ const std::vector<SwissTable*>& sources,
+ std::vector<uint32_t>* first_target_group_id,
+ MemoryPool* pool);
+
+ // Copy all entries from source to a range of blocks (partition) of target.
+ //
+ // During copy, adjust group ids from source by adding provided base id.
+ //
+ // Skip entries from source that would cross partition boundaries (range of
+ // blocks) when inserted into target. Save their data in output vector for
+ // processing later. We postpone inserting these overflow entries in order to
+ // allow concurrent processing of all partitions. Overflow entries will be
+ // handled by a single-thread afterwards.
+ //
+ static void MergePartition(SwissTable* target, const SwissTable* source,
+ uint32_t partition_id, int num_partition_bits,
+ uint32_t base_group_id,
+ std::vector<uint32_t>* overflow_group_ids,
+ std::vector<uint32_t>* overflow_hashes);
+
+ // Single-threaded processing of remaining groups, that could not be
+ // inserted in partition merge phase
+ // (due to entries from one partition spilling over due to full blocks into
+ // the next partition).
+ //
+ static void InsertNewGroups(SwissTable* target, const std::vector<uint32_t>& group_ids,
+ const std::vector<uint32_t>& hashes);
+
+ private:
+ // Insert a new group id.
+ //
+ // Assumes that there are enough slots in the target
+ // and there is no need to resize it.
+ //
+ // Max block id can be provided, in which case the search for an empty slot to
+ // insert new entry to will stop after visiting that block.
+ //
+ // Max block id value greater or equal to the number of blocks guarantees that
+ // the search will not be stopped.
+ //
+ static inline bool InsertNewGroup(SwissTable* target, uint64_t group_id, uint32_t hash,
+ int64_t max_block_id);
+};
+
+struct SwissTableWithKeys {
+ struct Input {
+ Input(const ExecBatch* in_batch, int in_batch_start_row, int in_batch_end_row,
+ util::TempVectorStack* in_temp_stack,
+ std::vector<KeyColumnArray>* in_temp_column_arrays);
+
+ Input(const ExecBatch* in_batch, util::TempVectorStack* in_temp_stack,
+ std::vector<KeyColumnArray>* in_temp_column_arrays);
+
+ Input(const ExecBatch* in_batch, int in_num_selected, const uint16_t* in_selection,
+ util::TempVectorStack* in_temp_stack,
+ std::vector<KeyColumnArray>* in_temp_column_arrays,
+ std::vector<uint32_t>* in_temp_group_ids);
+
+ Input(const Input& base, int num_rows_to_skip, int num_rows_to_include);
+
+ const ExecBatch* batch;
+ // Window of the batch to operate on.
+ // The window information is only used if row selection is null.
+ //
+ int batch_start_row;
+ int batch_end_row;
+ // Optional selection.
+ // Used instead of window of the batch if not null.
+ //
+ int num_selected;
+ const uint16_t* selection_maybe_null;
+ // Thread specific scratch buffers for storing temporary data.
+ //
+ util::TempVectorStack* temp_stack;
+ std::vector<KeyColumnArray>* temp_column_arrays;
+ std::vector<uint32_t>* temp_group_ids;
+ };
+
+ Status Init(int64_t hardware_flags, MemoryPool* pool);
+
+ void InitCallbacks();
+
+ static void Hash(Input* input, uint32_t* hashes, int64_t hardware_flags);
+
+ // If input uses selection, then hashes array must have one element for every
+ // row in the whole (unfiltered and not spliced) input exec batch. Otherwise,
+ // there must be one element in hashes array for every value in the window of
+ // the exec batch specified by input.
+ //
+ // Output arrays will contain one element for every selected batch row in
+ // input (selected either by selection vector if provided or input window
+ // otherwise).
+ //
+ void MapReadOnly(Input* input, const uint32_t* hashes, uint8_t* match_bitvector,
+ uint32_t* key_ids);
+ Status MapWithInserts(Input* input, const uint32_t* hashes, uint32_t* key_ids);
+
+ SwissTable* swiss_table() { return &swiss_table_; }
+ const SwissTable* swiss_table() const { return &swiss_table_; }
+ RowArray* keys() { return &keys_; }
+ const RowArray* keys() const { return &keys_; }
+
+ private:
+ void EqualCallback(int num_keys, const uint16_t* selection_maybe_null,
+ const uint32_t* group_ids, uint32_t* out_num_keys_mismatch,
+ uint16_t* out_selection_mismatch, void* callback_ctx);
+ Status AppendCallback(int num_keys, const uint16_t* selection, void* callback_ctx);
+ Status Map(Input* input, bool insert_missing, const uint32_t* hashes,
+ uint8_t* match_bitvector_maybe_null, uint32_t* key_ids);
+
+ SwissTable::EqualImpl equal_impl_;
+ SwissTable::AppendImpl append_impl_;
+
+ SwissTable swiss_table_;
+ RowArray keys_;
+};
+
+// Enhances SwissTableWithKeys with the following structures used by hash join:
+// - storage of payloads (that unlike keys do not have to be unique)
+// - mapping from a key to all inserted payloads corresponding to it (we can
+// store multiple rows corresponding to a single key)
+// - bit-vectors for keeping track of whether each payload had a match during
+// evaluation of join.
+//
+class SwissTableForJoin {
+ friend class SwissTableForJoinBuild;
+
+ public:
+ void UpdateHasMatchForKeys(int64_t thread_id, int num_rows, const uint32_t* key_ids);
+ void MergeHasMatch();
+
+ const SwissTableWithKeys* keys() const { return &map_; }
+ SwissTableWithKeys* keys() { return &map_; }
+ const RowArray* payloads() const { return no_payload_columns_ ? NULLPTR : &payloads_; }
+ const uint32_t* key_to_payload() const {
+ return no_duplicate_keys_ ? NULLPTR : row_offset_for_key_.data();
+ }
+ const uint8_t* has_match() const {
+ return has_match_.empty() ? NULLPTR : has_match_.data();
+ }
+ int64_t num_keys() const { return map_.keys()->num_rows(); }
+ int64_t num_rows() const {
+ return no_duplicate_keys_ ? num_keys() : row_offset_for_key_[num_keys()];
+ }
+
+ uint32_t payload_id_to_key_id(uint32_t payload_id) const;
+ // Input payload ids must form an increasing sequence.
+ //
+ void payload_ids_to_key_ids(int num_rows, const uint32_t* payload_ids,
+ uint32_t* key_ids) const;
+
+ private:
+ uint8_t* local_has_match(int64_t thread_id);
+
+ // Degree of parallelism (number of threads)
+ int dop_;
+
+ struct ThreadLocalState {
+ std::vector<uint8_t> has_match;
+ };
+ std::vector<ThreadLocalState> local_states_;
+ std::vector<uint8_t> has_match_;
+
+ SwissTableWithKeys map_;
+
+ bool no_duplicate_keys_;
+ // Not used if no_duplicate_keys_ is true.
+ std::vector<uint32_t> row_offset_for_key_;
+
+ bool no_payload_columns_;
+ // Not used if no_payload_columns_ is true.
+ RowArray payloads_;
+};
+
+// Implements parallel build process for hash table for join from a sequence of
+// exec batches with input rows.
+//
+class SwissTableForJoinBuild {
+ public:
+ Status Init(SwissTableForJoin* target, int dop, int64_t num_rows,
+ bool reject_duplicate_keys, bool no_payload,
+ const std::vector<KeyColumnMetadata>& key_types,
+ const std::vector<KeyColumnMetadata>& payload_types, MemoryPool* pool,
+ int64_t hardware_flags);
+
+ // In the first phase of parallel hash table build, threads pick unprocessed
+ // exec batches, partition the rows based on hash, and update all of the
+ // partitions with information related to that batch of rows.
+ //
+ Status PushNextBatch(int64_t thread_id, const ExecBatch& key_batch,
+ const ExecBatch* payload_batch_maybe_null,
+ util::TempVectorStack* temp_stack);
+
+ // Allocate memory and initialize counters required for parallel merging of
+ // hash table partitions.
+ // Single-threaded.
+ //
+ Status PreparePrtnMerge();
+
+ // Second phase of parallel hash table build.
+ // Each partition can be processed by a different thread.
+ // Parallel step.
+ //
+ void PrtnMerge(int prtn_id);
+
+ // Single-threaded processing of the rows that have been skipped during
+ // parallel merging phase, due to hash table search resulting in crossing
+ // partition boundaries.
+ //
+ void FinishPrtnMerge(util::TempVectorStack* temp_stack);
+
+ // The number of partitions is the number of parallel tasks to execute during
+ // the final phase of hash table build process.
+ //
+ int num_prtns() const { return num_prtns_; }
+
+ bool no_payload() const { return no_payload_; }
+
+ private:
+ void InitRowArray();
+ Status ProcessPartition(int64_t thread_id, const ExecBatch& key_batch,
+ const ExecBatch* payload_batch_maybe_null,
+ util::TempVectorStack* temp_stack, int prtn_id);
+
+ SwissTableForJoin* target_;
+ // DOP stands for Degree Of Parallelism - the maximum number of participating
+ // threads.
+ //
+ int dop_;
+ // Partition is a unit of parallel work.
+ //
+ // There must be power of 2 partitions (bits of hash will be used to
+ // identify them).
+ //
+ // Pick number of partitions at least equal to the number of threads (degree
+ // of parallelism).
+ //
+ int log_num_prtns_;
+ int num_prtns_;
+ int64_t num_rows_;
+ // Left-semi and left-anti-semi joins do not need more than one copy of the
+ // same key in the hash table.
+ // This flag, if set, will result in filtering rows with duplicate keys before
+ // inserting them into hash table.
+ //
+ // Since left-semi and left-anti-semi joins also do not need payload, when
+ // this flag is set there also will not be any processing of payload.
+ //
+ bool reject_duplicate_keys_;
+ // This flag, when set, will result in skipping any processing of the payload.
+ //
+ // The flag for rejecting duplicate keys (which should be set for left-semi
+ // and left-anti joins), when set, will force this flag to also be set, but
+ // other join flavors may set it to true as well if no payload columns are
+ // needed for join output.
+ //
+ bool no_payload_;
+ MemoryPool* pool_;
+ int64_t hardware_flags_;
+
+ // One per partition.
+ //
+ struct PartitionState {
+ SwissTableWithKeys keys;
+ RowArray payloads;
+ std::vector<uint32_t> key_ids;
+ std::vector<uint32_t> overflow_key_ids;
+ std::vector<uint32_t> overflow_hashes;
+ };
+
+ // One per thread.
+ //
+ // Buffers for storing temporary intermediate results when processing input
+ // batches.
+ //
+ struct ThreadState {
+ std::vector<uint32_t> batch_hashes;
+ std::vector<uint16_t> batch_prtn_ranges;
+ std::vector<uint16_t> batch_prtn_row_ids;
+ std::vector<int> temp_prtn_ids;
+ std::vector<uint32_t> temp_group_ids;
+ std::vector<KeyColumnArray> temp_column_arrays;
+ };
+
+ std::vector<PartitionState> prtn_states_;
+ std::vector<ThreadState> thread_states_;
+ PartitionLocks prtn_locks_;
+
+ std::vector<int64_t> partition_keys_first_row_id_;
+ std::vector<int64_t> partition_payloads_first_row_id_;
+};
+
+class JoinResultMaterialize {
+ public:
+ void Init(MemoryPool* pool, const HashJoinProjectionMaps* probe_schemas,
+ const HashJoinProjectionMaps* build_schemas);
+
+ void SetBuildSide(const RowArray* build_keys, const RowArray* build_payloads,
+ bool payload_id_same_as_key_id);
+
+ // Input probe side batches should contain all key columns followed by all
+ // payload columns.
+ //
+ Status AppendProbeOnly(const ExecBatch& key_and_payload, int num_rows_to_append,
+ const uint16_t* row_ids, int* num_rows_appended);
+
+ Status AppendBuildOnly(int num_rows_to_append, const uint32_t* key_ids,
+ const uint32_t* payload_ids, int* num_rows_appended);
+
+ Status Append(const ExecBatch& key_and_payload, int num_rows_to_append,
+ const uint16_t* row_ids, const uint32_t* key_ids,
+ const uint32_t* payload_ids, int* num_rows_appended);
+
+ // Should only be called if num_rows() returns non-zero.
+ //
+ Status Flush(ExecBatch* out);
+
+ int num_rows() const { return num_rows_; }
+
+ template <class APPEND_ROWS_FN, class OUTPUT_BATCH_FN>
+ Status AppendAndOutput(int num_rows_to_append, const APPEND_ROWS_FN& append_rows_fn,
+ const OUTPUT_BATCH_FN& output_batch_fn) {
+ int offset = 0;
+ for (;;) {
+ int num_rows_appended = 0;
+ ARROW_RETURN_NOT_OK(append_rows_fn(num_rows_to_append, offset, &num_rows_appended));
+ if (num_rows_appended < num_rows_to_append) {
+ ExecBatch batch;
+ ARROW_RETURN_NOT_OK(Flush(&batch));
+ output_batch_fn(batch);
+ num_rows_to_append -= num_rows_appended;
+ offset += num_rows_appended;
+ } else {
+ break;
+ }
+ }
+ return Status::OK();
+ }
+
+ template <class OUTPUT_BATCH_FN>
+ Status AppendProbeOnly(const ExecBatch& key_and_payload, int num_rows_to_append,
+ const uint16_t* row_ids, OUTPUT_BATCH_FN output_batch_fn) {
+ return AppendAndOutput(
+ num_rows_to_append,
+ [&](int num_rows_to_append_left, int offset, int* num_rows_appended) {
+ return AppendProbeOnly(key_and_payload, num_rows_to_append_left,
+ row_ids + offset, num_rows_appended);
+ },
+ output_batch_fn);
+ }
+
+ template <class OUTPUT_BATCH_FN>
+ Status AppendBuildOnly(int num_rows_to_append, const uint32_t* key_ids,
+ const uint32_t* payload_ids, OUTPUT_BATCH_FN output_batch_fn) {
+ return AppendAndOutput(
+ num_rows_to_append,
+ [&](int num_rows_to_append_left, int offset, int* num_rows_appended) {
+ return AppendBuildOnly(
+ num_rows_to_append_left, key_ids ? key_ids + offset : NULLPTR,
+ payload_ids ? payload_ids + offset : NULLPTR, num_rows_appended);
+ },
+ output_batch_fn);
+ }
+
+ template <class OUTPUT_BATCH_FN>
+ Status Append(const ExecBatch& key_and_payload, int num_rows_to_append,
+ const uint16_t* row_ids, const uint32_t* key_ids,
+ const uint32_t* payload_ids, OUTPUT_BATCH_FN output_batch_fn) {
+ return AppendAndOutput(
+ num_rows_to_append,
+ [&](int num_rows_to_append_left, int offset, int* num_rows_appended) {
+ return Append(key_and_payload, num_rows_to_append_left,
+ row_ids ? row_ids + offset : NULLPTR,
+ key_ids ? key_ids + offset : NULLPTR,
+ payload_ids ? payload_ids + offset : NULLPTR, num_rows_appended);
+ },
+ output_batch_fn);
+ }
+
+ template <class OUTPUT_BATCH_FN>
+ Status Flush(OUTPUT_BATCH_FN output_batch_fn) {
+ if (num_rows_ > 0) {
+ ExecBatch batch({}, num_rows_);
+ ARROW_RETURN_NOT_OK(Flush(&batch));
+ output_batch_fn(std::move(batch));
+ }
+ return Status::OK();
+ }
+
+ int64_t num_produced_batches() const { return num_produced_batches_; }
+
+ private:
+ bool HasProbeOutput() const;
+ bool HasBuildKeyOutput() const;
+ bool HasBuildPayloadOutput() const;
+ bool NeedsKeyId() const;
+ bool NeedsPayloadId() const;
+ Result<std::shared_ptr<ArrayData>> FlushBuildColumn(
+ const std::shared_ptr<DataType>& data_type, const RowArray* row_array,
+ int column_id, uint32_t* row_ids);
+
+ MemoryPool* pool_;
+ const HashJoinProjectionMaps* probe_schemas_;
+ const HashJoinProjectionMaps* build_schemas_;
+ const RowArray* build_keys_;
+ // Payload array pointer may be left as null, if no payload columns are
+ // in the output column set.
+ //
+ const RowArray* build_payloads_;
+ // If true, then ignore updating payload ids and use key ids instead when
+ // reading.
+ //
+ bool payload_id_same_as_key_id_;
+ std::vector<int> probe_output_to_key_and_payload_;
+
+ // Number of accumulated rows (since last flush)
+ //
+ int num_rows_;
+ // Accumulated output columns from probe side batches.
+ //
+ ExecBatchBuilder batch_builder_;
+ // Accumulated build side row references.
+ //
+ std::vector<uint32_t> key_ids_;
+ std::vector<uint32_t> payload_ids_;
+ // Information about ranges of rows from build side,
+ // that in the accumulated materialized results have all fields set to null.
+ //
+ // Each pair contains index of the first output row in the range and the
+ // length of the range. Only rows outside of these ranges have data present in
+ // the key_ids_ and payload_ids_ arrays.
+ //
+ std::vector<std::pair<int, int>> null_ranges_;
+
+ int64_t num_produced_batches_;
+};
+
+// When comparing two join key values to check if they are equal, hash join allows to
+// chose (even separately for each field within the join key) whether two null values are
+// considered to be equal (IS comparison) or not (EQ comparison). For EQ comparison we
+// need to filter rows with nulls in keys outside of hash table lookups, since hash table
+// implementation always treats two nulls as equal (like IS comparison).
+//
+// Implements evaluating filter bit vector eliminating rows that do not have
+// join matches due to nulls in key columns.
+//
+class JoinNullFilter {
+ public:
+ // The batch for which the filter bit vector will be computed
+ // needs to start with all key columns but it may contain more columns
+ // (payload) following them.
+ //
+ static void Filter(const ExecBatch& key_batch, int batch_start_row, int num_batch_rows,
+ const std::vector<JoinKeyCmp>& cmp, bool* all_valid,
+ bool and_with_input, uint8_t* out_bit_vector);
+};
+
+// A helper class that takes hash table lookup results for a range of rows in
+// input batch, that is:
+// - bit vector marking whether there was a key match in the hash table
+// - key id if there was a match
+// - mapping from key id to a range of payload ids associated with that key
+// (representing multiple matching rows in a hash table for a single row in an
+// input batch), and iterates output batches of limited size containing tuples
+// describing all matching pairs of rows:
+// - input batch row id (only rows that have matches in the hash table are
+// included)
+// - key id for a match
+// - payload id (different one for each matching row in the hash table)
+//
+class JoinMatchIterator {
+ public:
+ void SetLookupResult(int num_batch_rows, int start_batch_row,
+ const uint8_t* batch_has_match, const uint32_t* key_ids,
+ bool no_duplicate_keys, const uint32_t* key_to_payload);
+ bool GetNextBatch(int num_rows_max, int* out_num_rows, uint16_t* batch_row_ids,
+ uint32_t* key_ids, uint32_t* payload_ids);
+
+ private:
+ int num_batch_rows_;
+ int start_batch_row_;
+ const uint8_t* batch_has_match_;
+ const uint32_t* key_ids_;
+
+ bool no_duplicate_keys_;
+ const uint32_t* key_to_payload_;
+
+ // Index of the first not fully processed input row, or number of rows if all
+ // have been processed. May be pointing to a row with no matches.
+ //
+ int current_row_;
+ // Index of the first unprocessed match for the input row. May be zero if the
+ // row has no matches.
+ //
+ int current_match_for_row_;
+};
+
+// Implements entire processing of a probe side exec batch,
+// provided the join hash table is already built and available.
+//
+class JoinProbeProcessor {
+ public:
+ using OutputBatchFn = std::function<void(int64_t, ExecBatch)>;
+
+ void Init(int num_key_columns, JoinType join_type, SwissTableForJoin* hash_table,
+ std::vector<JoinResultMaterialize*> materialize,
+ const std::vector<JoinKeyCmp>* cmp, OutputBatchFn output_batch_fn);
+ Status OnNextBatch(int64_t thread_id, const ExecBatch& keypayload_batch,
+ util::TempVectorStack* temp_stack,
+ std::vector<KeyColumnArray>* temp_column_arrays);
+
+ // Must be called by a single-thread having exclusive access to the instance
+ // of this class. The caller is responsible for ensuring that.
+ //
+ Status OnFinished();
+
+ private:
+ int num_key_columns_;
+ JoinType join_type_;
+
+ SwissTableForJoin* hash_table_;
+ // One element per thread
+ //
+ std::vector<JoinResultMaterialize*> materialize_;
+ const std::vector<JoinKeyCmp>* cmp_;
+ OutputBatchFn output_batch_fn_;
+};
+
+} // namespace compute
+} // namespace arrow
diff --git a/cpp/src/arrow/compute/exec/swiss_join_avx2.cc b/cpp/src/arrow/compute/exec/swiss_join_avx2.cc
new file mode 100644
index 0000000000..261b458132
--- /dev/null
+++ b/cpp/src/arrow/compute/exec/swiss_join_avx2.cc
@@ -0,0 +1,197 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include <immintrin.h>
+
+#include "arrow/compute/exec/swiss_join.h"
+#include "arrow/util/bit_util.h"
+
+namespace arrow {
+namespace compute {
+
+#if defined(ARROW_HAVE_AVX2)
+
+template <class PROCESS_8_VALUES_FN>
+int RowArrayAccessor::Visit_avx2(const RowTableImpl& rows, int column_id, int num_rows,
+ const uint32_t* row_ids,
+ PROCESS_8_VALUES_FN process_8_values_fn) {
+ // Number of rows processed together in a single iteration of the loop (single
+ // call to the provided processing lambda).
+ //
+ constexpr int unroll = 8;
+
+ bool is_fixed_length_column =
+ rows.metadata().column_metadatas[column_id].is_fixed_length;
+
+ // There are 4 cases, each requiring different steps:
+ // 1. Varying length column that is the first varying length column in a row
+ // 2. Varying length column that is not the first varying length column in a
+ // row
+ // 3. Fixed length column in a fixed length row
+ // 4. Fixed length column in a varying length row
+
+ if (!is_fixed_length_column) {
+ int varbinary_column_id = VarbinaryColumnId(rows.metadata(), column_id);
+ const uint8_t* row_ptr_base = rows.data(2);
+ const uint32_t* row_offsets = rows.offsets();
+
+ if (varbinary_column_id == 0) {
+ // Case 1: This is the first varbinary column
+ //
+ __m256i field_offset_within_row = _mm256_set1_epi32(rows.metadata().fixed_length);
+ __m256i varbinary_end_array_offset =
+ _mm256_set1_epi32(rows.metadata().varbinary_end_array_offset);
+ for (int i = 0; i < num_rows / unroll; ++i) {
+ __m256i row_id =
+ _mm256_loadu_si256(reinterpret_cast<const __m256i*>(row_ids) + i);
+ __m256i row_offset = _mm256_i32gather_epi32(
+ reinterpret_cast<const int*>(row_offsets), row_id, sizeof(uint32_t));
+ __m256i field_length = _mm256_sub_epi32(
+ _mm256_i32gather_epi32(
+ reinterpret_cast<const int*>(row_ptr_base),
+ _mm256_add_epi32(row_offset, varbinary_end_array_offset), 1),
+ field_offset_within_row);
+ process_8_values_fn(i * unroll, row_ptr_base,
+ _mm256_add_epi32(row_offset, field_offset_within_row),
+ field_length);
+ }
+ } else {
+ // Case 2: This is second or later varbinary column
+ //
+ __m256i varbinary_end_array_offset =
+ _mm256_set1_epi32(rows.metadata().varbinary_end_array_offset +
+ sizeof(uint32_t) * (varbinary_column_id - 1));
+ auto row_ptr_base_i64 =
+ reinterpret_cast<const arrow::util::int64_for_gather_t*>(row_ptr_base);
+ for (int i = 0; i < num_rows / unroll; ++i) {
+ __m256i row_id =
+ _mm256_loadu_si256(reinterpret_cast<const __m256i*>(row_ids) + i);
+ __m256i row_offset = _mm256_i32gather_epi32(
+ reinterpret_cast<const int*>(row_offsets), row_id, sizeof(uint32_t));
+ __m256i end_array_offset =
+ _mm256_add_epi32(row_offset, varbinary_end_array_offset);
+
+ __m256i field_offset_within_row_A = _mm256_i32gather_epi64(
+ row_ptr_base_i64, _mm256_castsi256_si128(end_array_offset), 1);
+ __m256i field_offset_within_row_B = _mm256_i32gather_epi64(
+ row_ptr_base_i64, _mm256_extracti128_si256(end_array_offset, 1), 1);
+ field_offset_within_row_A = _mm256_permutevar8x32_epi32(
+ field_offset_within_row_A, _mm256_setr_epi32(0, 2, 4, 6, 1, 3, 5, 7));
+ field_offset_within_row_B = _mm256_permutevar8x32_epi32(
+ field_offset_within_row_B, _mm256_setr_epi32(1, 3, 5, 7, 0, 2, 4, 6));
+
+ __m256i field_offset_within_row = _mm256_blend_epi32(
+ field_offset_within_row_A, field_offset_within_row_B, 0xf0);
+
+ __m256i alignment_padding =
+ _mm256_andnot_si256(field_offset_within_row, _mm256_set1_epi8(0xff));
+ alignment_padding = _mm256_add_epi32(alignment_padding, _mm256_set1_epi32(1));
+ alignment_padding = _mm256_and_si256(
+ alignment_padding, _mm256_set1_epi32(rows.metadata().string_alignment - 1));
+
+ field_offset_within_row =
+ _mm256_add_epi32(field_offset_within_row, alignment_padding);
+
+ __m256i field_length = _mm256_blend_epi32(field_offset_within_row_A,
+ field_offset_within_row_B, 0x0f);
+ field_length = _mm256_permute4x64_epi64(field_length,
+ 0x4e); // Swapping low and high 128-bits
+ field_length = _mm256_sub_epi32(field_length, field_offset_within_row);
+
+ process_8_values_fn(i * unroll, row_ptr_base,
+ _mm256_add_epi32(row_offset, field_offset_within_row),
+ field_length);
+ }
+ }
+ }
+
+ if (is_fixed_length_column) {
+ __m256i field_offset_within_row =
+ _mm256_set1_epi32(rows.metadata().encoded_field_offset(
+ rows.metadata().pos_after_encoding(column_id)));
+ __m256i field_length =
+ _mm256_set1_epi32(rows.metadata().column_metadatas[column_id].fixed_length);
+
+ bool is_fixed_length_row = rows.metadata().is_fixed_length;
+ if (is_fixed_length_row) {
+ // Case 3: This is a fixed length column in fixed length row
+ //
+ const uint8_t* row_ptr_base = rows.data(1);
+ for (int i = 0; i < num_rows / unroll; ++i) {
+ __m256i row_id =
+ _mm256_loadu_si256(reinterpret_cast<const __m256i*>(row_ids) + i);
+ __m256i row_offset = _mm256_mullo_epi32(row_id, field_length);
+ __m256i field_offset = _mm256_add_epi32(row_offset, field_offset_within_row);
+ process_8_values_fn(i * unroll, row_ptr_base, field_offset, field_length);
+ }
+ } else {
+ // Case 4: This is a fixed length column in varying length row
+ //
+ const uint8_t* row_ptr_base = rows.data(2);
+ const uint32_t* row_offsets = rows.offsets();
+ for (int i = 0; i < num_rows / unroll; ++i) {
+ __m256i row_id =
+ _mm256_loadu_si256(reinterpret_cast<const __m256i*>(row_ids) + i);
+ __m256i row_offset = _mm256_i32gather_epi32(
+ reinterpret_cast<const int*>(row_offsets), row_id, sizeof(uint32_t));
+ __m256i field_offset = _mm256_add_epi32(row_offset, field_offset_within_row);
+ process_8_values_fn(i * unroll, row_ptr_base, field_offset, field_length);
+ }
+ }
+ }
+
+ return num_rows - (num_rows % unroll);
+}
+
+template <class PROCESS_8_VALUES_FN>
+int RowArrayAccessor::VisitNulls_avx2(const RowTableImpl& rows, int column_id,
+ int num_rows, const uint32_t* row_ids,
+ PROCESS_8_VALUES_FN process_8_values_fn) {
+ // Number of rows processed together in a single iteration of the loop (single
+ // call to the provided processing lambda).
+ //
+ constexpr int unroll = 8;
+
+ const uint8_t* null_masks = rows.null_masks();
+ __m256i null_bits_per_row =
+ _mm256_set1_epi32(8 * rows.metadata().null_masks_bytes_per_row);
+ for (int i = 0; i < num_rows / unroll; ++i) {
+ __m256i row_id = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(row_ids) + i);
+ __m256i bit_id = _mm256_mullo_epi32(row_id, null_bits_per_row);
+ bit_id = _mm256_add_epi32(bit_id, _mm256_set1_epi32(column_id));
+ __m256i bytes = _mm256_i32gather_epi32(reinterpret_cast<const int*>(null_masks),
+ _mm256_srli_epi32(bit_id, 3), 1);
+ __m256i bit_in_word = _mm256_sllv_epi32(
+ _mm256_set1_epi32(1), _mm256_and_si256(bit_id, _mm256_set1_epi32(7)));
+ __m256i result =
+ _mm256_cmpeq_epi32(_mm256_and_si256(bytes, bit_in_word), bit_in_word);
+ uint64_t null_bytes = static_cast<uint64_t>(
+ _mm256_movemask_epi8(_mm256_cvtepi32_epi64(_mm256_castsi256_si128(result))));
+ null_bytes |= static_cast<uint64_t>(_mm256_movemask_epi8(
+ _mm256_cvtepi32_epi64(_mm256_extracti128_si256(result, 1))))
+ << 32;
+
+ process_8_values_fn(i * unroll, null_bytes);
+ }
+
+ return num_rows - (num_rows % unroll);
+}
+
+#endif
+
+} // namespace compute
+} // namespace arrow
diff --git a/cpp/src/arrow/compute/exec/util.h b/cpp/src/arrow/compute/exec/util.h
index 839a8a7d29..1a635857f9 100644
--- a/cpp/src/arrow/compute/exec/util.h
+++ b/cpp/src/arrow/compute/exec/util.h
@@ -77,7 +77,8 @@ using int64_for_gather_t = const long long int; // NOLINT runtime-int
//
class MiniBatch {
public:
- static constexpr int kMiniBatchLength = 1024;
+ static constexpr int kLogMiniBatchLength = 10;
+ static constexpr int kMiniBatchLength = 1 << kLogMiniBatchLength;
};
/// Storage used to allocate temporary vectors of a batch size.
@@ -295,5 +296,51 @@ class ARROW_EXPORT ThreadIndexer {
std::unordered_map<std::thread::id, size_t> id_to_index_;
};
+// Helper class to calculate the modified number of rows to process using SIMD.
+//
+// Some array elements at the end will be skipped in order to avoid buffer
+// overrun, when doing memory loads and stores using larger word size than a
+// single array element.
+//
+class TailSkipForSIMD {
+ public:
+ static int64_t FixBitAccess(int num_bytes_accessed_together, int64_t num_rows,
+ int bit_offset) {
+ int64_t num_bytes = bit_util::BytesForBits(num_rows + bit_offset);
+ int64_t num_bytes_safe =
+ std::max(static_cast<int64_t>(0LL), num_bytes - num_bytes_accessed_together + 1);
+ int64_t num_rows_safe =
+ std::max(static_cast<int64_t>(0LL), 8 * num_bytes_safe - bit_offset);
+ return std::min(num_rows_safe, num_rows);
+ }
+ static int64_t FixBinaryAccess(int num_bytes_accessed_together, int64_t num_rows,
+ int64_t length) {
+ int64_t num_rows_to_skip = bit_util::CeilDiv(length, num_bytes_accessed_together);
+ int64_t num_rows_safe =
+ std::max(static_cast<int64_t>(0LL), num_rows - num_rows_to_skip);
+ return num_rows_safe;
+ }
+ static int64_t FixVarBinaryAccess(int num_bytes_accessed_together, int64_t num_rows,
+ const uint32_t* offsets) {
+ // Do not process rows that could read past the end of the buffer using N
+ // byte loads/stores.
+ //
+ int64_t num_rows_safe = num_rows;
+ while (num_rows_safe > 0 &&
+ offsets[num_rows_safe] + num_bytes_accessed_together > offsets[num_rows]) {
+ --num_rows_safe;
+ }
+ return num_rows_safe;
+ }
+ static int FixSelection(int64_t num_rows_safe, int num_selected,
+ const uint16_t* selection) {
+ int num_selected_safe = num_selected;
+ while (num_selected_safe > 0 && selection[num_selected_safe] >= num_rows_safe) {
+ --num_selected_safe;
+ }
+ return num_selected_safe;
+ }
+};
+
} // namespace compute
} // namespace arrow
diff --git a/cpp/src/arrow/compute/exec/util_test.cc b/cpp/src/arrow/compute/exec/util_test.cc
index 6d85991735..3861446bb3 100644
--- a/cpp/src/arrow/compute/exec/util_test.cc
+++ b/cpp/src/arrow/compute/exec/util_test.cc
@@ -15,7 +15,7 @@
// specific language governing permissions and limitations
// under the License.
-#include "arrow/compute/exec/hash_join.h"
+#include "arrow/compute/exec/hash_join_node.h"
#include "arrow/compute/exec/schema_util.h"
#include "arrow/testing/gtest_util.h"
#include "arrow/testing/matchers.h"
diff --git a/cpp/src/arrow/compute/row/compare_internal.cc b/cpp/src/arrow/compute/row/compare_internal.cc
index e863c9cd05..750012e60e 100644
--- a/cpp/src/arrow/compute/row/compare_internal.cc
+++ b/cpp/src/arrow/compute/row/compare_internal.cc
@@ -35,7 +35,8 @@ void KeyCompare::NullUpdateColumnToRow(uint32_t id_col, uint32_t num_rows_to_com
const uint32_t* left_to_right_map,
LightContext* ctx, const KeyColumnArray& col,
const RowTableImpl& rows,
- uint8_t* match_bytevector) {
+ uint8_t* match_bytevector,
+ bool are_cols_in_encoding_order) {
if (!rows.has_any_nulls(ctx) && !col.data(0)) {
return;
}
@@ -48,6 +49,9 @@ void KeyCompare::NullUpdateColumnToRow(uint32_t id_col, uint32_t num_rows_to_com
}
#endif
+ uint32_t null_bit_id =
+ are_cols_in_encoding_order ? id_col : rows.metadata().pos_after_encoding(id_col);
+
if (!col.data(0)) {
// Remove rows from the result for which the column value is a null
const uint8_t* null_masks = rows.null_masks();
@@ -55,11 +59,12 @@ void KeyCompare::NullUpdateColumnToRow(uint32_t id_col, uint32_t num_rows_to_com
for (uint32_t i = num_processed; i < num_rows_to_compare; ++i) {
uint32_t irow_left = use_selection ? sel_left_maybe_null[i] : i;
uint32_t irow_right = left_to_right_map[irow_left];
- int64_t bitid = irow_right * null_mask_num_bytes * 8 + id_col;
+ int64_t bitid = irow_right * null_mask_num_bytes * 8 + null_bit_id;
match_bytevector[i] &= (bit_util::GetBit(null_masks, bitid) ? 0 : 0xff);
}
} else if (!rows.has_any_nulls(ctx)) {
- // Remove rows from the result for which the column value on left side is null
+ // Remove rows from the result for which the column value on left side is
+ // null
const uint8_t* non_nulls = col.data(0);
ARROW_DCHECK(non_nulls);
for (uint32_t i = num_processed; i < num_rows_to_compare; ++i) {
@@ -75,7 +80,7 @@ void KeyCompare::NullUpdateColumnToRow(uint32_t id_col, uint32_t num_rows_to_com
for (uint32_t i = num_processed; i < num_rows_to_compare; ++i) {
uint32_t irow_left = use_selection ? sel_left_maybe_null[i] : i;
uint32_t irow_right = left_to_right_map[irow_left];
- int64_t bitid_right = irow_right * null_mask_num_bytes * 8 + id_col;
+ int64_t bitid_right = irow_right * null_mask_num_bytes * 8 + null_bit_id;
int right_null = bit_util::GetBit(null_masks, bitid_right) ? 0xff : 0;
int left_null =
bit_util::GetBit(non_nulls, irow_left + col.bit_offset(0)) ? 0 : 0xff;
@@ -228,27 +233,16 @@ void KeyCompare::CompareBinaryColumnToRow(uint32_t offset_within_row,
// Overwrites the match_bytevector instead of updating it
template <bool use_selection, bool is_first_varbinary_col>
-void KeyCompare::CompareVarBinaryColumnToRow(uint32_t id_varbinary_col,
- uint32_t num_rows_to_compare,
- const uint16_t* sel_left_maybe_null,
- const uint32_t* left_to_right_map,
- LightContext* ctx, const KeyColumnArray& col,
- const RowTableImpl& rows,
- uint8_t* match_bytevector) {
-#if defined(ARROW_HAVE_AVX2)
- if (ctx->has_avx2()) {
- CompareVarBinaryColumnToRow_avx2(
- use_selection, is_first_varbinary_col, id_varbinary_col, num_rows_to_compare,
- sel_left_maybe_null, left_to_right_map, ctx, col, rows, match_bytevector);
- return;
- }
-#endif
-
+void KeyCompare::CompareVarBinaryColumnToRowHelper(
+ uint32_t id_varbinary_col, uint32_t first_row_to_compare,
+ uint32_t num_rows_to_compare, const uint16_t* sel_left_maybe_null,
+ const uint32_t* left_to_right_map, LightContext* ctx, const KeyColumnArray& col,
+ const RowTableImpl& rows, uint8_t* match_bytevector) {
const uint32_t* offsets_left = col.offsets();
const uint32_t* offsets_right = rows.offsets();
const uint8_t* rows_left = col.data(2);
const uint8_t* rows_right = rows.data(2);
- for (uint32_t i = 0; i < num_rows_to_compare; ++i) {
+ for (uint32_t i = first_row_to_compare; i < num_rows_to_compare; ++i) {
uint32_t irow_left = use_selection ? sel_left_maybe_null[i] : i;
uint32_t irow_right = left_to_right_map[irow_left];
uint32_t begin_left = offsets_left[irow_left];
@@ -292,6 +286,29 @@ void KeyCompare::CompareVarBinaryColumnToRow(uint32_t id_varbinary_col,
}
}
+// Overwrites the match_bytevector instead of updating it
+template <bool use_selection, bool is_first_varbinary_col>
+void KeyCompare::CompareVarBinaryColumnToRow(uint32_t id_varbinary_col,
+ uint32_t num_rows_to_compare,
+ const uint16_t* sel_left_maybe_null,
+ const uint32_t* left_to_right_map,
+ LightContext* ctx, const KeyColumnArray& col,
+ const RowTableImpl& rows,
+ uint8_t* match_bytevector) {
+ uint32_t num_processed = 0;
+#if defined(ARROW_HAVE_AVX2)
+ if (ctx->has_avx2()) {
+ num_processed = CompareVarBinaryColumnToRow_avx2(
+ use_selection, is_first_varbinary_col, id_varbinary_col, num_rows_to_compare,
+ sel_left_maybe_null, left_to_right_map, ctx, col, rows, match_bytevector);
+ }
+#endif
+
+ CompareVarBinaryColumnToRowHelper<use_selection, is_first_varbinary_col>(
+ id_varbinary_col, num_processed, num_rows_to_compare, sel_left_maybe_null,
+ left_to_right_map, ctx, col, rows, match_bytevector);
+}
+
void KeyCompare::AndByteVectors(LightContext* ctx, uint32_t num_elements,
uint8_t* bytevector_A, const uint8_t* bytevector_B) {
uint32_t num_processed = 0;
@@ -308,13 +325,12 @@ void KeyCompare::AndByteVectors(LightContext* ctx, uint32_t num_elements,
}
}
-void KeyCompare::CompareColumnsToRows(uint32_t num_rows_to_compare,
- const uint16_t* sel_left_maybe_null,
- const uint32_t* left_to_right_map,
- LightContext* ctx, uint32_t* out_num_rows,
- uint16_t* out_sel_left_maybe_same,
- const std::vector<KeyColumnArray>& cols,
- const RowTableImpl& rows) {
+void KeyCompare::CompareColumnsToRows(
+ uint32_t num_rows_to_compare, const uint16_t* sel_left_maybe_null,
+ const uint32_t* left_to_right_map, LightContext* ctx, uint32_t* out_num_rows,
+ uint16_t* out_sel_left_maybe_same, const std::vector<KeyColumnArray>& cols,
+ const RowTableImpl& rows, bool are_cols_in_encoding_order,
+ uint8_t* out_match_bitvector_maybe_null) {
if (num_rows_to_compare == 0) {
*out_num_rows = 0;
return;
@@ -335,6 +351,7 @@ void KeyCompare::CompareColumnsToRows(uint32_t num_rows_to_compare,
bool is_first_column = true;
for (size_t icol = 0; icol < cols.size(); ++icol) {
const KeyColumnArray& col = cols[icol];
+
if (col.metadata().is_null_type) {
// If this null type col is the first column, the match_bytevector_A needs to be
// initialized with 0xFF. Otherwise, the calculation can be skipped
@@ -343,8 +360,11 @@ void KeyCompare::CompareColumnsToRows(uint32_t num_rows_to_compare,
}
continue;
}
- uint32_t offset_within_row =
- rows.metadata().encoded_field_offset(static_cast<uint32_t>(icol));
+
+ uint32_t offset_within_row = rows.metadata().encoded_field_offset(
+ are_cols_in_encoding_order
+ ? static_cast<uint32_t>(icol)
+ : rows.metadata().pos_after_encoding(static_cast<uint32_t>(icol)));
if (col.metadata().is_fixed_length) {
if (sel_left_maybe_null) {
CompareBinaryColumnToRow<true>(
@@ -354,7 +374,8 @@ void KeyCompare::CompareColumnsToRows(uint32_t num_rows_to_compare,
NullUpdateColumnToRow<true>(
static_cast<uint32_t>(icol), num_rows_to_compare, sel_left_maybe_null,
left_to_right_map, ctx, col, rows,
- is_first_column ? match_bytevector_A : match_bytevector_B);
+ is_first_column ? match_bytevector_A : match_bytevector_B,
+ are_cols_in_encoding_order);
} else {
// Version without using selection vector
CompareBinaryColumnToRow<false>(
@@ -364,7 +385,8 @@ void KeyCompare::CompareColumnsToRows(uint32_t num_rows_to_compare,
NullUpdateColumnToRow<false>(
static_cast<uint32_t>(icol), num_rows_to_compare, sel_left_maybe_null,
left_to_right_map, ctx, col, rows,
- is_first_column ? match_bytevector_A : match_bytevector_B);
+ is_first_column ? match_bytevector_A : match_bytevector_B,
+ are_cols_in_encoding_order);
}
if (!is_first_column) {
AndByteVectors(ctx, num_rows_to_compare, match_bytevector_A, match_bytevector_B);
@@ -391,7 +413,8 @@ void KeyCompare::CompareColumnsToRows(uint32_t num_rows_to_compare,
NullUpdateColumnToRow<true>(
static_cast<uint32_t>(icol), num_rows_to_compare, sel_left_maybe_null,
left_to_right_map, ctx, col, rows,
- is_first_column ? match_bytevector_A : match_bytevector_B);
+ is_first_column ? match_bytevector_A : match_bytevector_B,
+ are_cols_in_encoding_order);
} else {
if (ivarbinary == 0) {
CompareVarBinaryColumnToRow<false, true>(
@@ -405,7 +428,8 @@ void KeyCompare::CompareColumnsToRows(uint32_t num_rows_to_compare,
NullUpdateColumnToRow<false>(
static_cast<uint32_t>(icol), num_rows_to_compare, sel_left_maybe_null,
left_to_right_map, ctx, col, rows,
- is_first_column ? match_bytevector_A : match_bytevector_B);
+ is_first_column ? match_bytevector_A : match_bytevector_B,
+ are_cols_in_encoding_order);
}
if (!is_first_column) {
AndByteVectors(ctx, num_rows_to_compare, match_bytevector_A, match_bytevector_B);
@@ -417,18 +441,26 @@ void KeyCompare::CompareColumnsToRows(uint32_t num_rows_to_compare,
util::bit_util::bytes_to_bits(ctx->hardware_flags, num_rows_to_compare,
match_bytevector_A, match_bitvector);
- if (sel_left_maybe_null) {
- int out_num_rows_int;
- util::bit_util::bits_filter_indexes(0, ctx->hardware_flags, num_rows_to_compare,
- match_bitvector, sel_left_maybe_null,
- &out_num_rows_int, out_sel_left_maybe_same);
- *out_num_rows = out_num_rows_int;
+
+ if (out_match_bitvector_maybe_null) {
+ ARROW_DCHECK(out_num_rows == nullptr);
+ ARROW_DCHECK(out_sel_left_maybe_same == nullptr);
+ memcpy(out_match_bitvector_maybe_null, match_bitvector,
+ bit_util::BytesForBits(num_rows_to_compare));
} else {
- int out_num_rows_int;
- util::bit_util::bits_to_indexes(0, ctx->hardware_flags, num_rows_to_compare,
- match_bitvector, &out_num_rows_int,
- out_sel_left_maybe_same);
- *out_num_rows = out_num_rows_int;
+ if (sel_left_maybe_null) {
+ int out_num_rows_int;
+ util::bit_util::bits_filter_indexes(0, ctx->hardware_flags, num_rows_to_compare,
+ match_bitvector, sel_left_maybe_null,
+ &out_num_rows_int, out_sel_left_maybe_same);
+ *out_num_rows = out_num_rows_int;
+ } else {
+ int out_num_rows_int;
+ util::bit_util::bits_to_indexes(0, ctx->hardware_flags, num_rows_to_compare,
+ match_bitvector, &out_num_rows_int,
+ out_sel_left_maybe_same);
+ *out_num_rows = out_num_rows_int;
+ }
}
}
diff --git a/cpp/src/arrow/compute/row/compare_internal.h b/cpp/src/arrow/compute/row/compare_internal.h
index e3b9057115..f9ec1e7f53 100644
--- a/cpp/src/arrow/compute/row/compare_internal.h
+++ b/cpp/src/arrow/compute/row/compare_internal.h
@@ -35,13 +35,12 @@ class KeyCompare {
// Returns a single 16-bit selection vector of rows that failed comparison.
// If there is input selection on the left, the resulting selection is a filtered image
// of input selection.
- static void CompareColumnsToRows(uint32_t num_rows_to_compare,
- const uint16_t* sel_left_maybe_null,
- const uint32_t* left_to_right_map, LightContext* ctx,
- uint32_t* out_num_rows,
- uint16_t* out_sel_left_maybe_same,
- const std::vector<KeyColumnArray>& cols,
- const RowTableImpl& rows);
+ static void CompareColumnsToRows(
+ uint32_t num_rows_to_compare, const uint16_t* sel_left_maybe_null,
+ const uint32_t* left_to_right_map, LightContext* ctx, uint32_t* out_num_rows,
+ uint16_t* out_sel_left_maybe_same, const std::vector<KeyColumnArray>& cols,
+ const RowTableImpl& rows, bool are_cols_in_encoding_order,
+ uint8_t* out_match_bitvector_maybe_null = NULLPTR);
private:
template <bool use_selection>
@@ -49,7 +48,8 @@ class KeyCompare {
const uint16_t* sel_left_maybe_null,
const uint32_t* left_to_right_map, LightContext* ctx,
const KeyColumnArray& col, const RowTableImpl& rows,
- uint8_t* match_bytevector);
+ uint8_t* match_bytevector,
+ bool are_cols_in_encoding_order);
template <bool use_selection, class COMPARE_FN>
static void CompareBinaryColumnToRowHelper(
@@ -67,6 +67,13 @@ class KeyCompare {
const RowTableImpl& rows,
uint8_t* match_bytevector);
+ template <bool use_selection, bool is_first_varbinary_col>
+ static void CompareVarBinaryColumnToRowHelper(
+ uint32_t id_varlen_col, uint32_t first_row_to_compare, uint32_t num_rows_to_compare,
+ const uint16_t* sel_left_maybe_null, const uint32_t* left_to_right_map,
+ LightContext* ctx, const KeyColumnArray& col, const RowTableImpl& rows,
+ uint8_t* match_bytevector);
+
template <bool use_selection, bool is_first_varbinary_col>
static void CompareVarBinaryColumnToRow(uint32_t id_varlen_col,
uint32_t num_rows_to_compare,
@@ -125,7 +132,7 @@ class KeyCompare {
LightContext* ctx, const KeyColumnArray& col, const RowTableImpl& rows,
uint8_t* match_bytevector);
- static void CompareVarBinaryColumnToRow_avx2(
+ static uint32_t CompareVarBinaryColumnToRow_avx2(
bool use_selection, bool is_first_varbinary_col, uint32_t id_varlen_col,
uint32_t num_rows_to_compare, const uint16_t* sel_left_maybe_null,
const uint32_t* left_to_right_map, LightContext* ctx, const KeyColumnArray& col,
diff --git a/cpp/src/arrow/compute/row/compare_internal_avx2.cc b/cpp/src/arrow/compute/row/compare_internal_avx2.cc
index 818f4c4fe7..96dacab679 100644
--- a/cpp/src/arrow/compute/row/compare_internal_avx2.cc
+++ b/cpp/src/arrow/compute/row/compare_internal_avx2.cc
@@ -44,6 +44,9 @@ uint32_t KeyCompare::NullUpdateColumnToRowImp_avx2(
if (!rows.has_any_nulls(ctx) && !col.data(0)) {
return num_rows_to_compare;
}
+
+ uint32_t null_bit_id = rows.metadata().pos_after_encoding(id_col);
+
if (!col.data(0)) {
// Remove rows from the result for which the column value is a null
const uint8_t* null_masks = rows.null_masks();
@@ -63,7 +66,7 @@ uint32_t KeyCompare::NullUpdateColumnToRowImp_avx2(
}
__m256i bitid =
_mm256_mullo_epi32(irow_right, _mm256_set1_epi32(null_mask_num_bytes * 8));
- bitid = _mm256_add_epi32(bitid, _mm256_set1_epi32(id_col));
+ bitid = _mm256_add_epi32(bitid, _mm256_set1_epi32(null_bit_id));
__m256i right =
_mm256_i32gather_epi32((const int*)null_masks, _mm256_srli_epi32(bitid, 3), 1);
right = _mm256_and_si256(
@@ -80,7 +83,8 @@ uint32_t KeyCompare::NullUpdateColumnToRowImp_avx2(
num_processed = num_rows_to_compare / unroll * unroll;
return num_processed;
} else if (!rows.has_any_nulls(ctx)) {
- // Remove rows from the result for which the column value on left side is null
+ // Remove rows from the result for which the column value on left side is
+ // null
const uint8_t* non_nulls = col.data(0);
ARROW_DCHECK(non_nulls);
uint32_t num_processed = 0;
@@ -145,7 +149,7 @@ uint32_t KeyCompare::NullUpdateColumnToRowImp_avx2(
}
__m256i bitid =
_mm256_mullo_epi32(irow_right, _mm256_set1_epi32(null_mask_num_bytes * 8));
- bitid = _mm256_add_epi32(bitid, _mm256_set1_epi32(id_col));
+ bitid = _mm256_add_epi32(bitid, _mm256_set1_epi32(null_bit_id));
__m256i right =
_mm256_i32gather_epi32((const int*)null_masks, _mm256_srli_epi32(bitid, 3), 1);
right = _mm256_and_si256(
@@ -252,22 +256,22 @@ inline uint64_t CompareSelected8_avx2(const uint8_t* left_base, const uint8_t* r
int bit_offset = 0) {
__m256i left;
switch (column_width) {
- case 0:
+ case 0: {
irow_left = _mm256_add_epi32(irow_left, _mm256_set1_epi32(bit_offset));
left = _mm256_i32gather_epi32((const int*)left_base,
- _mm256_srli_epi32(irow_left, 3), 1);
- left = _mm256_and_si256(
- _mm256_set1_epi32(1),
- _mm256_srlv_epi32(left, _mm256_and_si256(irow_left, _mm256_set1_epi32(7))));
- left = _mm256_mullo_epi32(left, _mm256_set1_epi32(0xff));
- break;
+ _mm256_srli_epi32(irow_left, 5), 4);
+ __m256i bit_selection = _mm256_sllv_epi32(
+ _mm256_set1_epi32(1), _mm256_and_si256(irow_left, _mm256_set1_epi32(31)));
+ left = _mm256_cmpeq_epi32(bit_selection, _mm256_and_si256(left, bit_selection));
+ left = _mm256_and_si256(left, _mm256_set1_epi32(0xff));
+ } break;
case 1:
left = _mm256_i32gather_epi32((const int*)left_base, irow_left, 1);
left = _mm256_and_si256(left, _mm256_set1_epi32(0xff));
break;
case 2:
left = _mm256_i32gather_epi32((const int*)left_base, irow_left, 2);
- left = _mm256_and_si256(left, _mm256_set1_epi32(0xff));
+ left = _mm256_and_si256(left, _mm256_set1_epi32(0xffff));
break;
case 4:
left = _mm256_i32gather_epi32((const int*)left_base, irow_left, 4);
@@ -311,15 +315,15 @@ inline uint64_t Compare8_avx2(const uint8_t* left_base, const uint8_t* right_bas
} break;
case 1:
left = _mm256_cvtepu8_epi32(_mm_set1_epi64x(
- reinterpret_cast<const uint64_t*>(left_base)[irow_left_first / 8]));
+ *reinterpret_cast<const uint64_t*>(left_base + irow_left_first)));
break;
case 2:
left = _mm256_cvtepu16_epi32(_mm_loadu_si128(
- reinterpret_cast<const __m128i*>(left_base) + irow_left_first / 8));
+ reinterpret_cast<const __m128i*>(left_base + 2 * irow_left_first)));
break;
case 4:
- left = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(left_base) +
- irow_left_first / 8);
+ left = _mm256_loadu_si256(
+ reinterpret_cast<const __m256i*>(left_base + 4 * irow_left_first));
break;
default:
ARROW_DCHECK(false);
@@ -347,19 +351,17 @@ inline uint64_t Compare8_64bit_avx2(const uint8_t* left_base, const uint8_t* rig
__m256i offset_right) {
auto left_base_i64 =
reinterpret_cast<const arrow::util::int64_for_gather_t*>(left_base);
- __m256i left_lo =
- _mm256_i32gather_epi64(left_base_i64, _mm256_castsi256_si128(irow_left), 8);
- __m256i left_hi =
- _mm256_i32gather_epi64(left_base_i64, _mm256_extracti128_si256(irow_left, 1), 8);
+ __m256i left_lo, left_hi;
if (use_selection) {
left_lo = _mm256_i32gather_epi64(left_base_i64, _mm256_castsi256_si128(irow_left), 8);
left_hi =
_mm256_i32gather_epi64(left_base_i64, _mm256_extracti128_si256(irow_left, 1), 8);
} else {
- left_lo = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(left_base) +
- irow_left_first / 4);
- left_hi = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(left_base) +
- irow_left_first / 4 + 1);
+ left_lo = _mm256_loadu_si256(
+ reinterpret_cast<const __m256i*>(left_base + irow_left_first * sizeof(uint64_t)));
+ left_hi = _mm256_loadu_si256(
+ reinterpret_cast<const __m256i*>(left_base + irow_left_first * sizeof(uint64_t)) +
+ 1);
}
auto right_base_i64 =
reinterpret_cast<const arrow::util::int64_for_gather_t*>(right_base);
@@ -532,7 +534,7 @@ void KeyCompare::CompareVarBinaryColumnToRowImp_avx2(
const __m256i* key_right_ptr =
reinterpret_cast<const __m256i*>(rows_right + begin_right);
int32_t j;
- // length can be zero
+ // length is greater than zero
for (j = 0; j < (static_cast<int32_t>(length) + 31) / 32 - 1; ++j) {
__m256i key_left = _mm256_loadu_si256(key_left_ptr + j);
__m256i key_right = _mm256_loadu_si256(key_right_ptr + j);
@@ -569,6 +571,15 @@ uint32_t KeyCompare::NullUpdateColumnToRow_avx2(
const uint16_t* sel_left_maybe_null, const uint32_t* left_to_right_map,
LightContext* ctx, const KeyColumnArray& col, const RowTableImpl& rows,
uint8_t* match_bytevector) {
+ int64_t num_rows_safe =
+ TailSkipForSIMD::FixBitAccess(sizeof(uint32_t), col.length(), col.bit_offset(0));
+ if (sel_left_maybe_null) {
+ num_rows_to_compare = static_cast<uint32_t>(TailSkipForSIMD::FixSelection(
+ num_rows_safe, static_cast<int>(num_rows_to_compare), sel_left_maybe_null));
+ } else {
+ num_rows_to_compare = static_cast<uint32_t>(num_rows_safe);
+ }
+
if (use_selection) {
return NullUpdateColumnToRowImp_avx2<true>(id_col, num_rows_to_compare,
sel_left_maybe_null, left_to_right_map,
@@ -585,6 +596,29 @@ uint32_t KeyCompare::CompareBinaryColumnToRow_avx2(
const uint16_t* sel_left_maybe_null, const uint32_t* left_to_right_map,
LightContext* ctx, const KeyColumnArray& col, const RowTableImpl& rows,
uint8_t* match_bytevector) {
+ uint32_t col_width = col.metadata().fixed_length;
+ int64_t num_rows_safe = col.length();
+ if (col_width == 0) {
+ // In this case we will access left column memory 4B at a time
+ num_rows_safe =
+ TailSkipForSIMD::FixBitAccess(sizeof(uint32_t), col.length(), col.bit_offset(1));
+ } else if (col_width == 1 || col_width == 2) {
+ // In this case we will access left column memory 4B at a time
+ num_rows_safe =
+ TailSkipForSIMD::FixBinaryAccess(sizeof(uint32_t), col.length(), col_width);
+ } else if (col_width != 4 && col_width != 8) {
+ // In this case we will access left column memory 32B at a time
+ num_rows_safe =
+ TailSkipForSIMD::FixBinaryAccess(sizeof(__m256i), col.length(), col_width);
+ }
+ if (sel_left_maybe_null) {
+ num_rows_to_compare = static_cast<uint32_t>(TailSkipForSIMD::FixSelection(
+ num_rows_safe, static_cast<int>(num_rows_to_compare), sel_left_maybe_null));
+ } else {
+ num_rows_to_compare = static_cast<uint32_t>(
+ std::min(num_rows_safe, static_cast<int64_t>(num_rows_to_compare)));
+ }
+
if (use_selection) {
return CompareBinaryColumnToRowImp_avx2<true>(offset_within_row, num_rows_to_compare,
sel_left_maybe_null, left_to_right_map,
@@ -596,11 +630,20 @@ uint32_t KeyCompare::CompareBinaryColumnToRow_avx2(
}
}
-void KeyCompare::CompareVarBinaryColumnToRow_avx2(
+uint32_t KeyCompare::CompareVarBinaryColumnToRow_avx2(
bool use_selection, bool is_first_varbinary_col, uint32_t id_varlen_col,
uint32_t num_rows_to_compare, const uint16_t* sel_left_maybe_null,
const uint32_t* left_to_right_map, LightContext* ctx, const KeyColumnArray& col,
const RowTableImpl& rows, uint8_t* match_bytevector) {
+ int64_t num_rows_safe =
+ TailSkipForSIMD::FixVarBinaryAccess(sizeof(__m256i), col.length(), col.offsets());
+ if (use_selection) {
+ num_rows_to_compare = static_cast<uint32_t>(TailSkipForSIMD::FixSelection(
+ num_rows_safe, static_cast<int>(num_rows_to_compare), sel_left_maybe_null));
+ } else {
+ num_rows_to_compare = static_cast<uint32_t>(num_rows_safe);
+ }
+
if (use_selection) {
if (is_first_varbinary_col) {
CompareVarBinaryColumnToRowImp_avx2<true, true>(
@@ -622,6 +665,8 @@ void KeyCompare::CompareVarBinaryColumnToRow_avx2(
col, rows, match_bytevector);
}
}
+
+ return num_rows_to_compare;
}
#endif
diff --git a/cpp/src/arrow/compute/row/encode_internal.cc b/cpp/src/arrow/compute/row/encode_internal.cc
index cbfd169b44..9d138258d6 100644
--- a/cpp/src/arrow/compute/row/encode_internal.cc
+++ b/cpp/src/arrow/compute/row/encode_internal.cc
@@ -16,13 +16,14 @@
// under the License.
#include "arrow/compute/row/encode_internal.h"
+#include "arrow/compute/exec.h"
+#include "arrow/util/checked_cast.h"
namespace arrow {
namespace compute {
-void RowTableEncoder::Init(const std::vector<KeyColumnMetadata>& cols, LightContext* ctx,
- int row_alignment, int string_alignment) {
- ctx_ = ctx;
+void RowTableEncoder::Init(const std::vector<KeyColumnMetadata>& cols, int row_alignment,
+ int string_alignment) {
row_metadata_.FromColumnMetadataVector(cols, row_alignment, string_alignment);
uint32_t num_cols = row_metadata_.num_cols();
uint32_t num_varbinary_cols = row_metadata_.num_varbinary_cols();
@@ -59,18 +60,24 @@ void RowTableEncoder::PrepareKeyColumnArrays(int64_t start_row, int64_t num_rows
void RowTableEncoder::DecodeFixedLengthBuffers(int64_t start_row_input,
int64_t start_row_output, int64_t num_rows,
const RowTableImpl& rows,
- std::vector<KeyColumnArray>* cols) {
+ std::vector<KeyColumnArray>* cols,
+ int64_t hardware_flags,
+ util::TempVectorStack* temp_stack) {
// Prepare column array vectors
PrepareKeyColumnArrays(start_row_output, num_rows, *cols);
+ LightContext ctx;
+ ctx.hardware_flags = hardware_flags;
+ ctx.stack = temp_stack;
+
// Create two temp vectors with 16-bit elements
auto temp_buffer_holder_A =
- util::TempVectorHolder<uint16_t>(ctx_->stack, static_cast<uint32_t>(num_rows));
+ util::TempVectorHolder<uint16_t>(ctx.stack, static_cast<uint32_t>(num_rows));
auto temp_buffer_A = KeyColumnArray(
KeyColumnMetadata(true, sizeof(uint16_t)), num_rows, nullptr,
reinterpret_cast<uint8_t*>(temp_buffer_holder_A.mutable_data()), nullptr);
auto temp_buffer_holder_B =
- util::TempVectorHolder<uint16_t>(ctx_->stack, static_cast<uint32_t>(num_rows));
+ util::TempVectorHolder<uint16_t>(ctx.stack, static_cast<uint32_t>(num_rows));
auto temp_buffer_B = KeyColumnArray(
KeyColumnMetadata(true, sizeof(uint16_t)), num_rows, nullptr,
reinterpret_cast<uint8_t*>(temp_buffer_holder_B.mutable_data()), nullptr);
@@ -79,7 +86,7 @@ void RowTableEncoder::DecodeFixedLengthBuffers(int64_t start_row_input,
if (!is_row_fixed_length) {
EncoderOffsets::Decode(static_cast<uint32_t>(start_row_input),
static_cast<uint32_t>(num_rows), rows, &batch_varbinary_cols_,
- batch_varbinary_cols_base_offsets_, ctx_);
+ batch_varbinary_cols_base_offsets_, &ctx);
}
// Process fixed length columns
@@ -98,13 +105,13 @@ void RowTableEncoder::DecodeFixedLengthBuffers(int64_t start_row_input,
EncoderBinary::Decode(static_cast<uint32_t>(start_row_input),
static_cast<uint32_t>(num_rows),
row_metadata_.column_offsets[i], rows, &batch_all_cols_[i],
- ctx_, &temp_buffer_A);
+ &ctx, &temp_buffer_A);
i += 1;
} else {
EncoderBinaryPair::Decode(
static_cast<uint32_t>(start_row_input), static_cast<uint32_t>(num_rows),
row_metadata_.column_offsets[i], rows, &batch_all_cols_[i],
- &batch_all_cols_[i + 1], ctx_, &temp_buffer_A, &temp_buffer_B);
+ &batch_all_cols_[i + 1], &ctx, &temp_buffer_A, &temp_buffer_B);
i += 2;
}
}
@@ -114,14 +121,17 @@ void RowTableEncoder::DecodeFixedLengthBuffers(int64_t start_row_input,
static_cast<uint32_t>(num_rows), rows, &batch_all_cols_);
}
-void RowTableEncoder::DecodeVaryingLengthBuffers(int64_t start_row_input,
- int64_t start_row_output,
- int64_t num_rows,
- const RowTableImpl& rows,
- std::vector<KeyColumnArray>* cols) {
+void RowTableEncoder::DecodeVaryingLengthBuffers(
+ int64_t start_row_input, int64_t start_row_output, int64_t num_rows,
+ const RowTableImpl& rows, std::vector<KeyColumnArray>* cols, int64_t hardware_flags,
+ util::TempVectorStack* temp_stack) {
// Prepare column array vectors
PrepareKeyColumnArrays(start_row_output, num_rows, *cols);
+ LightContext ctx;
+ ctx.hardware_flags = hardware_flags;
+ ctx.stack = temp_stack;
+
bool is_row_fixed_length = row_metadata_.is_fixed_length;
if (!is_row_fixed_length) {
for (size_t i = 0; i < batch_varbinary_cols_.size(); ++i) {
@@ -129,7 +139,7 @@ void RowTableEncoder::DecodeVaryingLengthBuffers(int64_t start_row_input,
// positions in the output row buffer.
EncoderVarBinary::Decode(static_cast<uint32_t>(start_row_input),
static_cast<uint32_t>(num_rows), static_cast<uint32_t>(i),
- rows, &batch_varbinary_cols_[i], ctx_);
+ rows, &batch_varbinary_cols_[i], &ctx);
}
}
}
diff --git a/cpp/src/arrow/compute/row/encode_internal.h b/cpp/src/arrow/compute/row/encode_internal.h
index ce88731346..970537a306 100644
--- a/cpp/src/arrow/compute/row/encode_internal.h
+++ b/cpp/src/arrow/compute/row/encode_internal.h
@@ -46,8 +46,8 @@ namespace compute {
/// Does not support nested types
class RowTableEncoder {
public:
- void Init(const std::vector<KeyColumnMetadata>& cols, LightContext* ctx,
- int row_alignment, int string_alignment);
+ void Init(const std::vector<KeyColumnMetadata>& cols, int row_alignment,
+ int string_alignment);
const RowTableMetadata& row_metadata() { return row_metadata_; }
// GrouperFastImpl right now needs somewhat intrusive visibility into RowTableEncoder
@@ -84,7 +84,8 @@ class RowTableEncoder {
/// for the call to DecodeVaryingLengthBuffers
void DecodeFixedLengthBuffers(int64_t start_row_input, int64_t start_row_output,
int64_t num_rows, const RowTableImpl& rows,
- std::vector<KeyColumnArray>* cols);
+ std::vector<KeyColumnArray>* cols, int64_t hardware_flags,
+ util::TempVectorStack* temp_stack);
/// \brief Decode the varlength columns of a row table into column storage
/// \param start_row_input The starting row to decode
@@ -94,7 +95,9 @@ class RowTableEncoder {
/// \param cols The column arrays to decode into
void DecodeVaryingLengthBuffers(int64_t start_row_input, int64_t start_row_output,
int64_t num_rows, const RowTableImpl& rows,
- std::vector<KeyColumnArray>* cols);
+ std::vector<KeyColumnArray>* cols,
+ int64_t hardware_flags,
+ util::TempVectorStack* temp_stack);
private:
/// Prepare column array vectors.
@@ -107,8 +110,6 @@ class RowTableEncoder {
void PrepareKeyColumnArrays(int64_t start_row, int64_t num_rows,
const std::vector<KeyColumnArray>& cols_in);
- LightContext* ctx_;
-
// Data initialized once, based on data types of key columns
RowTableMetadata row_metadata_;
diff --git a/cpp/src/arrow/compute/row/grouper.cc b/cpp/src/arrow/compute/row/grouper.cc
index ba76bad0d1..28ebc9f196 100644
--- a/cpp/src/arrow/compute/row/grouper.cc
+++ b/cpp/src/arrow/compute/row/grouper.cc
@@ -247,7 +247,7 @@ struct GrouperFastImpl : Grouper {
impl->key_types_[icol] = key;
}
- impl->encoder_.Init(impl->col_metadata_, &impl->encode_ctx_,
+ impl->encoder_.Init(impl->col_metadata_,
/* row_alignment = */ sizeof(uint64_t),
/* string_alignment = */ sizeof(uint64_t));
RETURN_NOT_OK(impl->rows_.Init(ctx->memory_pool(), impl->encoder_.row_metadata()));
@@ -255,24 +255,23 @@ struct GrouperFastImpl : Grouper {
impl->rows_minibatch_.Init(ctx->memory_pool(), impl->encoder_.row_metadata()));
impl->minibatch_size_ = impl->minibatch_size_min_;
GrouperFastImpl* impl_ptr = impl.get();
- auto equal_func = [impl_ptr](
- int num_keys_to_compare, const uint16_t* selection_may_be_null,
- const uint32_t* group_ids, uint32_t* out_num_keys_mismatch,
- uint16_t* out_selection_mismatch) {
- KeyCompare::CompareColumnsToRows(
- num_keys_to_compare, selection_may_be_null, group_ids, &impl_ptr->encode_ctx_,
- out_num_keys_mismatch, out_selection_mismatch,
- impl_ptr->encoder_.batch_all_cols(), impl_ptr->rows_);
- };
- auto append_func = [impl_ptr](int num_keys, const uint16_t* selection) {
+ impl->map_equal_impl_ =
+ [impl_ptr](int num_keys_to_compare, const uint16_t* selection_may_be_null,
+ const uint32_t* group_ids, uint32_t* out_num_keys_mismatch,
+ uint16_t* out_selection_mismatch, void*) {
+ KeyCompare::CompareColumnsToRows(
+ num_keys_to_compare, selection_may_be_null, group_ids,
+ &impl_ptr->encode_ctx_, out_num_keys_mismatch, out_selection_mismatch,
+ impl_ptr->encoder_.batch_all_cols(), impl_ptr->rows_,
+ /* are_cols_in_encoding_order=*/true);
+ };
+ impl->map_append_impl_ = [impl_ptr](int num_keys, const uint16_t* selection, void*) {
RETURN_NOT_OK(impl_ptr->encoder_.EncodeSelected(&impl_ptr->rows_minibatch_,
num_keys, selection));
return impl_ptr->rows_.AppendSelectionFrom(impl_ptr->rows_minibatch_, num_keys,
nullptr);
};
- RETURN_NOT_OK(impl->map_.init(impl->encode_ctx_.hardware_flags, ctx->memory_pool(),
- impl->encode_ctx_.stack, impl->log_minibatch_max_,
- equal_func, append_func));
+ RETURN_NOT_OK(impl->map_.init(impl->encode_ctx_.hardware_flags, ctx->memory_pool()));
impl->cols_.resize(num_columns);
impl->minibatch_hashes_.resize(impl->minibatch_size_max_ +
kPaddingForSIMD / sizeof(uint32_t));
@@ -372,7 +371,8 @@ struct GrouperFastImpl : Grouper {
match_bitvector.mutable_data(), local_slots.mutable_data());
map_.find(batch_size_next, minibatch_hashes_.data(),
match_bitvector.mutable_data(), local_slots.mutable_data(),
- reinterpret_cast<uint32_t*>(group_ids->mutable_data()) + start_row);
+ reinterpret_cast<uint32_t*>(group_ids->mutable_data()) + start_row,
+ &temp_stack_, map_equal_impl_, nullptr);
}
auto ids = util::TempVectorHolder<uint16_t>(&temp_stack_, batch_size_next);
int num_ids;
@@ -382,7 +382,8 @@ struct GrouperFastImpl : Grouper {
RETURN_NOT_OK(map_.map_new_keys(
num_ids, ids.mutable_data(), minibatch_hashes_.data(),
- reinterpret_cast<uint32_t*>(group_ids->mutable_data()) + start_row));
+ reinterpret_cast<uint32_t*>(group_ids->mutable_data()) + start_row,
+ &temp_stack_, map_equal_impl_, map_append_impl_, nullptr));
start_row += batch_size_next;
@@ -450,7 +451,7 @@ struct GrouperFastImpl : Grouper {
int64_t batch_size_next =
std::min(num_groups - start_row, static_cast<int64_t>(minibatch_size_max_));
encoder_.DecodeFixedLengthBuffers(start_row, start_row, batch_size_next, rows_,
- &cols_);
+ &cols_, encode_ctx_.hardware_flags, &temp_stack_);
start_row += batch_size_next;
}
@@ -470,7 +471,8 @@ struct GrouperFastImpl : Grouper {
int64_t batch_size_next =
std::min(num_groups - start_row, static_cast<int64_t>(minibatch_size_max_));
encoder_.DecodeVaryingLengthBuffers(start_row, start_row, batch_size_next, rows_,
- &cols_);
+ &cols_, encode_ctx_.hardware_flags,
+ &temp_stack_);
start_row += batch_size_next;
}
}
@@ -535,6 +537,8 @@ struct GrouperFastImpl : Grouper {
RowTableImpl rows_minibatch_;
RowTableEncoder encoder_;
SwissTable map_;
+ SwissTable::EqualImpl map_equal_impl_;
+ SwissTable::AppendImpl map_append_impl_;
};
} // namespace
diff --git a/cpp/src/arrow/compute/row/row_internal.cc b/cpp/src/arrow/compute/row/row_internal.cc
index e99ff75d64..11a8a0bc43 100644
--- a/cpp/src/arrow/compute/row/row_internal.cc
+++ b/cpp/src/arrow/compute/row/row_internal.cc
@@ -110,6 +110,10 @@ void RowTableMetadata::FromColumnMetadataVector(
}
return left < right;
});
+ inverse_column_order.resize(num_cols);
+ for (uint32_t i = 0; i < num_cols; ++i) {
+ inverse_column_order[column_order[i]] = i;
+ }
row_alignment = in_row_alignment;
string_alignment = in_string_alignment;
diff --git a/cpp/src/arrow/compute/row/row_internal.h b/cpp/src/arrow/compute/row/row_internal.h
index d46ac0e9a9..c9194267aa 100644
--- a/cpp/src/arrow/compute/row/row_internal.h
+++ b/cpp/src/arrow/compute/row/row_internal.h
@@ -73,6 +73,7 @@ struct ARROW_EXPORT RowTableMetadata {
/// Order in which fields are encoded.
std::vector<uint32_t> column_order;
+ std::vector<uint32_t> inverse_column_order;
/// Offsets within a row to fields in their encoding order.
std::vector<uint32_t> column_offsets;
@@ -133,6 +134,8 @@ struct ARROW_EXPORT RowTableMetadata {
uint32_t encoded_field_order(uint32_t icol) const { return column_order[icol]; }
+ uint32_t pos_after_encoding(uint32_t icol) const { return inverse_column_order[icol]; }
+
uint32_t encoded_field_offset(uint32_t icol) const { return column_offsets[icol]; }
uint32_t num_cols() const { return static_cast<uint32_t>(column_metadatas.size()); }
diff --git a/docs/source/python/compute.rst b/docs/source/python/compute.rst
index b0867123d5..bcbca9dff3 100644
--- a/docs/source/python/compute.rst
+++ b/docs/source/python/compute.rst
@@ -237,10 +237,10 @@ In that case the result would be::
n_legs: int64
animal: string
----
- id: [[3,1,2],[4]]
- year: [[2019,2020,2022],[null]]
- n_legs: [[5,null,null],[100]]
- animal: [["Brittle stars",null,null],["Centipede"]]
+ id: [[3,1,2,4]]
+ year: [[2019,2020,2022,null]]
+ n_legs: [[5,null,null,100]]
+ animal: [["Brittle stars",null,null,"Centipede"]]
It's also possible to provide additional join keys, so that the
join happens on two keys instead of one. For example we can add
diff --git a/python/pyarrow/table.pxi b/python/pyarrow/table.pxi
index 17ea6d3558..17f88aca4e 100644
--- a/python/pyarrow/table.pxi
+++ b/python/pyarrow/table.pxi
@@ -4631,6 +4631,89 @@ cdef class Table(_PandasConvertible):
return table
+ def group_by(self, keys):
+ """Declare a grouping over the columns of the table.
+
+ Resulting grouping can then be used to perform aggregations
+ with a subsequent ``aggregate()`` method.
+
+ Parameters
+ ----------
+ keys : str or list[str]
+ Name of the columns that should be used as the grouping key.
+
+ Returns
+ -------
+ TableGroupBy
+
+ See Also
+ --------
+ TableGroupBy.aggregate
+
+ Examples
+ --------
+ >>> import pandas as pd
+ >>> import pyarrow as pa
+ >>> df = pd.DataFrame({'year': [2020, 2022, 2021, 2022, 2019, 2021],
+ ... 'n_legs': [2, 2, 4, 4, 5, 100],
+ ... 'animal': ["Flamingo", "Parrot", "Dog", "Horse",
+ ... "Brittle stars", "Centipede"]})
+ >>> table = pa.Table.from_pandas(df)
+ >>> table.group_by('year').aggregate([('n_legs', 'sum')])
+ pyarrow.Table
+ n_legs_sum: int64
+ year: int64
+ ----
+ n_legs_sum: [[2,6,104,5]]
+ year: [[2020,2022,2021,2019]]
+ """
+ return TableGroupBy(self, keys)
+
+ def sort_by(self, sorting):
+ """
+ Sort the table by one or multiple columns.
+
+ Parameters
+ ----------
+ sorting : str or list[tuple(name, order)]
+ Name of the column to use to sort (ascending), or
+ a list of multiple sorting conditions where
+ each entry is a tuple with column name
+ and sorting order ("ascending" or "descending")
+
+ Returns
+ -------
+ Table
+ A new table sorted according to the sort keys.
+
+ Examples
+ --------
+ >>> import pandas as pd
+ >>> import pyarrow as pa
+ >>> df = pd.DataFrame({'year': [2020, 2022, 2021, 2022, 2019, 2021],
+ ... 'n_legs': [2, 2, 4, 4, 5, 100],
+ ... 'animal': ["Flamingo", "Parrot", "Dog", "Horse",
+ ... "Brittle stars", "Centipede"]})
+ >>> table = pa.Table.from_pandas(df)
+ >>> table.sort_by('animal')
+ pyarrow.Table
+ year: int64
+ n_legs: int64
+ animal: string
+ ----
+ year: [[2019,2021,2021,2020,2022,2022]]
+ n_legs: [[5,100,4,2,4,2]]
+ animal: [["Brittle stars","Centipede","Dog","Flamingo","Horse","Parrot"]]
+ """
+ if isinstance(sorting, str):
+ sorting = [(sorting, "ascending")]
+
+ indices = _pc().sort_indices(
+ self,
+ sort_keys=sorting
+ )
+ return self.take(indices)
+
def join(self, right_table, keys, right_keys=None, join_type="left outer",
left_suffix=None, right_suffix=None, coalesce_keys=True,
use_threads=True):
@@ -4686,7 +4769,7 @@ cdef class Table(_PandasConvertible):
Left outer join:
- >>> t1.join(t2, 'id')
+ >>> t1.join(t2, 'id').combine_chunks().sort_by('year')
pyarrow.Table
id: int64
year: int64
@@ -4700,31 +4783,31 @@ cdef class Table(_PandasConvertible):
Full outer join:
- >>> t1.join(t2, 'id', join_type="full outer")
+ >>> t1.join(t2, 'id', join_type="full outer").combine_chunks().sort_by('year')
pyarrow.Table
id: int64
year: int64
n_legs: int64
animal: string
----
- id: [[3,1,2],[4]]
- year: [[2019,2020,2022],[null]]
- n_legs: [[5,null,null],[100]]
- animal: [["Brittle stars",null,null],["Centipede"]]
+ id: [[3,1,2,4]]
+ year: [[2019,2020,2022,null]]
+ n_legs: [[5,null,null,100]]
+ animal: [["Brittle stars",null,null,"Centipede"]]
Right outer join:
- >>> t1.join(t2, 'id', join_type="right outer")
+ >>> t1.join(t2, 'id', join_type="right outer").combine_chunks().sort_by('year')
pyarrow.Table
year: int64
id: int64
n_legs: int64
animal: string
----
- year: [[2019],[null]]
- id: [[3],[4]]
- n_legs: [[5],[100]]
- animal: [["Brittle stars"],["Centipede"]]
+ year: [[2019,null]]
+ id: [[3,4]]
+ n_legs: [[5,100]]
+ animal: [["Brittle stars","Centipede"]]
Right anti join
@@ -4745,89 +4828,6 @@ cdef class Table(_PandasConvertible):
use_threads=use_threads, coalesce_keys=coalesce_keys,
output_type=Table)
- def group_by(self, keys):
- """Declare a grouping over the columns of the table.
-
- Resulting grouping can then be used to perform aggregations
- with a subsequent ``aggregate()`` method.
-
- Parameters
- ----------
- keys : str or list[str]
- Name of the columns that should be used as the grouping key.
-
- Returns
- -------
- TableGroupBy
-
- See Also
- --------
- TableGroupBy.aggregate
-
- Examples
- --------
- >>> import pandas as pd
- >>> import pyarrow as pa
- >>> df = pd.DataFrame({'year': [2020, 2022, 2021, 2022, 2019, 2021],
- ... 'n_legs': [2, 2, 4, 4, 5, 100],
- ... 'animal': ["Flamingo", "Parrot", "Dog", "Horse",
- ... "Brittle stars", "Centipede"]})
- >>> table = pa.Table.from_pandas(df)
- >>> table.group_by('year').aggregate([('n_legs', 'sum')])
- pyarrow.Table
- n_legs_sum: int64
- year: int64
- ----
- n_legs_sum: [[2,6,104,5]]
- year: [[2020,2022,2021,2019]]
- """
- return TableGroupBy(self, keys)
-
- def sort_by(self, sorting):
- """
- Sort the table by one or multiple columns.
-
- Parameters
- ----------
- sorting : str or list[tuple(name, order)]
- Name of the column to use to sort (ascending), or
- a list of multiple sorting conditions where
- each entry is a tuple with column name
- and sorting order ("ascending" or "descending")
-
- Returns
- -------
- Table
- A new table sorted according to the sort keys.
-
- Examples
- --------
- >>> import pandas as pd
- >>> import pyarrow as pa
- >>> df = pd.DataFrame({'year': [2020, 2022, 2021, 2022, 2019, 2021],
- ... 'n_legs': [2, 2, 4, 4, 5, 100],
- ... 'animal': ["Flamingo", "Parrot", "Dog", "Horse",
- ... "Brittle stars", "Centipede"]})
- >>> table = pa.Table.from_pandas(df)
- >>> table.sort_by('animal')
- pyarrow.Table
- year: int64
- n_legs: int64
- animal: string
- ----
- year: [[2019,2021,2021,2020,2022,2022]]
- n_legs: [[5,100,4,2,4,2]]
- animal: [["Brittle stars","Centipede","Dog","Flamingo","Horse","Parrot"]]
- """
- if isinstance(sorting, str):
- sorting = [(sorting, "ascending")]
-
- indices = _pc().sort_indices(
- self,
- sort_keys=sorting
- )
- return self.take(indices)
-
def _reconstruct_table(arrays, schema):
"""
diff --git a/python/pyarrow/tests/test_exec_plan.py b/python/pyarrow/tests/test_exec_plan.py
index f93aac3f86..209eed9d25 100644
--- a/python/pyarrow/tests/test_exec_plan.py
+++ b/python/pyarrow/tests/test_exec_plan.py
@@ -134,20 +134,24 @@ def test_table_join_collisions():
result = ep._perform_join(
"full outer", t1, ["colA", "colB"], t2, ["colA", "colB"])
- assert result.combine_chunks() == pa.table([
- [1, 2, 6, None],
- [10, 20, 60, None],
- ["a", "b", "f", None],
- [10, 20, None, 99],
- ["A", "B", None, "Z"],
- [300, 200, None, 100],
- [1, 2, None, 99],
+ result = result.combine_chunks()
+ result = result.sort_by("colUniq")
+ assert result == pa.table([
+ [None, 2, 1, 6],
+ [None, 20, 10, 60],
+ [None, "b", "a", "f"],
+ [99, 20, 10, None],
+ ["Z", "B", "A", None],
+ [100, 200, 300, None],
+ [99, 2, 1, None],
], names=["colA", "colB", "colVals", "colB", "colVals", "colUniq", "colA"])
result = ep._perform_join("full outer", t1, "colA",
t2, "colA", right_suffix="_r",
coalesce_keys=False)
- assert result.combine_chunks() == pa.table({
+ result = result.combine_chunks()
+ result = result.sort_by("colA")
+ assert result == pa.table({
"colA": [1, 2, 6, None],
"colB": [10, 20, 60, None],
"colVals": ["a", "b", "f", None],
@@ -160,7 +164,9 @@ def test_table_join_collisions():
result = ep._perform_join("full outer", t1, "colA",
t2, "colA", right_suffix="_r",
coalesce_keys=True)
- assert result.combine_chunks() == pa.table({
+ result = result.combine_chunks()
+ result = result.sort_by("colA")
+ assert result == pa.table({
"colA": [1, 2, 6, 99],
"colB": [10, 20, 60, None],
"colVals": ["a", "b", "f", None],
@@ -185,7 +191,9 @@ def test_table_join_keys_order():
result = ep._perform_join("full outer", t1, "colA", t2, "colX",
left_suffix="_l", right_suffix="_r",
coalesce_keys=True)
- assert result.combine_chunks() == pa.table({
+ result = result.combine_chunks()
+ result = result.sort_by("colA")
+ assert result == pa.table({
"colB": [10, 20, 60, None],
"colA": [1, 2, 6, 99],
"colVals_l": ["a", "b", "f", None],