| 1174 | } |
| 1175 | |
| 1176 | std::pair<HashJoinNode*, std::vector<int>> BloomFilterPushdownContext::GetPushdownTarget( |
| 1177 | HashJoinNode* start) { |
| 1178 | #if !ARROW_LITTLE_ENDIAN |
| 1179 | // TODO (ARROW-16591): Debug bloom_filter.cc to enable on Big endian. It probably just |
| 1180 | // needs a few byte swaps in the proper spots. |
| 1181 | disable_bloom_filter_ = true; |
| 1182 | return {nullptr, {}}; |
| 1183 | #else |
| 1184 | if (disable_bloom_filter_) return {nullptr, {}}; |
| 1185 | JoinType join_type = start->join_type_; |
| 1186 | |
| 1187 | // A build-side Bloom filter tells us if a row is definitely not in the build side. |
| 1188 | // This allows us to early-eliminate rows or early-accept rows depending on the type |
| 1189 | // of join. Left Outer Join and Full Outer Join output all rows, so a build-side Bloom |
| 1190 | // filter would only allow us to early-output. Left Antijoin outputs only if there is |
| 1191 | // no match, so again early output. We don't implement early output for now, so we |
| 1192 | // must disallow these types of joins. |
| 1193 | bool bloom_filter_does_not_apply_to_join = join_type == JoinType::LEFT_ANTI || |
| 1194 | join_type == JoinType::LEFT_OUTER || |
| 1195 | join_type == JoinType::FULL_OUTER; |
| 1196 | disable_bloom_filter_ = disable_bloom_filter_ || bloom_filter_does_not_apply_to_join; |
| 1197 | |
| 1198 | // Bloom filter currently doesn't support dictionaries. |
| 1199 | for (int side = 0; side <= 1 && !disable_bloom_filter_; side++) { |
| 1200 | SchemaProjectionMap keys_to_input = start->schema_mgr_->proj_maps[side].map( |
| 1201 | HashJoinProjection::KEY, HashJoinProjection::INPUT); |
| 1202 | // Bloom filter currently doesn't support dictionaries. |
| 1203 | for (int i = 0; i < keys_to_input.num_cols; i++) { |
| 1204 | int idx = keys_to_input.get(i); |
| 1205 | bool is_dict = start->inputs_[side]->output_schema()->field(idx)->type()->id() == |
| 1206 | Type::DICTIONARY; |
| 1207 | if (is_dict) { |
| 1208 | disable_bloom_filter_ = true; |
| 1209 | break; |
| 1210 | } |
| 1211 | } |
| 1212 | } |
| 1213 | |
| 1214 | bool all_comparisons_is = true; |
| 1215 | for (JoinKeyCmp cmp : start->key_cmp_) all_comparisons_is &= (cmp == JoinKeyCmp::IS); |
| 1216 | |
| 1217 | if ((join_type == JoinType::RIGHT_OUTER || join_type == JoinType::FULL_OUTER) && |
| 1218 | all_comparisons_is) |
| 1219 | disable_bloom_filter_ = true; |
| 1220 | |
| 1221 | if (disable_bloom_filter_) return {nullptr, {}}; |
| 1222 | |
| 1223 | // We currently only push Bloom filters on the probe side, and only if that input is |
| 1224 | // also a join. |
| 1225 | SchemaProjectionMap probe_key_to_input = start->schema_mgr_->proj_maps[0].map( |
| 1226 | HashJoinProjection::KEY, HashJoinProjection::INPUT); |
| 1227 | int num_keys = probe_key_to_input.num_cols; |
| 1228 | |
| 1229 | // A mapping such that bloom_to_target[i] is the index of key i in the pushdown |
| 1230 | // target's input |
| 1231 | std::vector<int> bloom_to_target(num_keys); |
| 1232 | HashJoinNode* pushdown_target = start; |
| 1233 | for (int i = 0; i < num_keys; i++) bloom_to_target[i] = probe_key_to_input.get(i); |