OmniSciDB  06b3bd477c
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
JoinHashTableQueryRuntime.cpp File Reference
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include "../Shared/geo_compression_runtime.h"
#include "CompareKeysInl.h"
#include "MurmurHash.h"
+ Include dependency graph for JoinHashTableQueryRuntime.cpp:
+ This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  BufferRange
 
struct  Bounds
 

Namespaces

 anonymous_namespace{JoinHashTableQueryRuntime.cpp}
 

Functions

DEVICE bool compare_to_key (const int8_t *entry, const int8_t *key, const size_t key_bytes)
 
template<class T >
DEVICE int64_t get_matching_slot (const int8_t *hash_buff, const uint32_t h, const int8_t *key, const size_t key_bytes)
 
template<class T >
FORCE_INLINE DEVICE int64_t baseline_hash_join_idx_impl (const int8_t *hash_buff, const int8_t *key, const size_t key_bytes, const size_t entry_count)
 
NEVER_INLINE DEVICE int64_t baseline_hash_join_idx_32 (const int8_t *hash_buff, const int8_t *key, const size_t key_bytes, const size_t entry_count)
 
NEVER_INLINE DEVICE int64_t baseline_hash_join_idx_64 (const int8_t *hash_buff, const int8_t *key, const size_t key_bytes, const size_t entry_count)
 
template<typename T >
FORCE_INLINE DEVICE int64_t get_bucket_key_for_value_impl (const T value, const double bucket_size)
 
NEVER_INLINE DEVICE int64_t get_bucket_key_for_range_double (const int8_t *range_bytes, const size_t range_component_index, const double bucket_size)
 
FORCE_INLINE DEVICE int64_t get_bucket_key_for_range_compressed_impl (const int8_t *range, const size_t range_component_index, const double bucket_size)
 
NEVER_INLINE DEVICE int64_t get_bucket_key_for_range_compressed (const int8_t *range, const size_t range_component_index, const double bucket_size)
 
template<typename T >
FORCE_INLINE DEVICE int64_t get_composite_key_index_impl (const T *key, const size_t key_component_count, const T *composite_key_dict, const size_t entry_count)
 
NEVER_INLINE DEVICE int64_t get_composite_key_index_32 (const int32_t *key, const size_t key_component_count, const int32_t *composite_key_dict, const size_t entry_count)
 
NEVER_INLINE DEVICE int64_t get_composite_key_index_64 (const int64_t *key, const size_t key_component_count, const int64_t *composite_key_dict, const size_t entry_count)
 
NEVER_INLINE DEVICE int32_t insert_sorted (int32_t *arr, size_t elem_count, int32_t elem)
 
ALWAYS_INLINE DEVICE int64_t overlaps_hash_join_idx (int64_t hash_buff, const int64_t key, const int64_t min_key, const int64_t max_key)
 
ALWAYS_INLINE DEVICE BufferRange get_row_id_buffer_ptr (int64_t *hash_table_ptr, const int64_t *key, const int64_t key_component_count, const int64_t entry_count, const int64_t offset_buffer_ptr_offset, const int64_t sub_buff_size)
 
NEVER_INLINE DEVICE int64_t get_candidate_rows (int32_t *out_arr, const uint32_t max_arr_size, const int8_t *range_bytes, const int32_t range_component_index, const double bucket_size_x, const double bucket_size_y, const int32_t keys_count, const int64_t key_component_count, int64_t *hash_table_ptr, const int64_t entry_count, const int64_t offset_buffer_ptr_offset, const int64_t sub_buff_size)
 
NEVER_INLINE DEVICE int32_t get_num_buckets_for_bounds (const int8_t *range_bytes, const int32_t range_component_index, const double bucket_size_x, const double bucket_size_y)
 

Variables

const int anonymous_namespace{JoinHashTableQueryRuntime.cpp}::kNoMatch = -1
 
const int anonymous_namespace{JoinHashTableQueryRuntime.cpp}::kNotPresent = -2
 

Function Documentation

NEVER_INLINE DEVICE int64_t baseline_hash_join_idx_32 ( const int8_t *  hash_buff,
const int8_t *  key,
const size_t  key_bytes,
const size_t  entry_count 
)

Definition at line 83 of file JoinHashTableQueryRuntime.cpp.

86  {
87  return baseline_hash_join_idx_impl<int32_t>(hash_buff, key, key_bytes, entry_count);
88 }
NEVER_INLINE DEVICE int64_t baseline_hash_join_idx_64 ( const int8_t *  hash_buff,
const int8_t *  key,
const size_t  key_bytes,
const size_t  entry_count 
)

Definition at line 91 of file JoinHashTableQueryRuntime.cpp.

94  {
95  return baseline_hash_join_idx_impl<int64_t>(hash_buff, key, key_bytes, entry_count);
96 }
template<class T >
FORCE_INLINE DEVICE int64_t baseline_hash_join_idx_impl ( const int8_t *  hash_buff,
const int8_t *  key,
const size_t  key_bytes,
const size_t  entry_count 
)

Definition at line 59 of file JoinHashTableQueryRuntime.cpp.

References anonymous_namespace{JoinHashTableQueryRuntime.cpp}::kNoMatch, and MurmurHash1().

62  {
63  if (!entry_count) {
64  return kNoMatch;
65  }
66  const uint32_t h = MurmurHash1(key, key_bytes, 0) % entry_count;
67  int64_t matching_slot = get_matching_slot<T>(hash_buff, h, key, key_bytes);
68  if (matching_slot != kNoMatch) {
69  return matching_slot;
70  }
71  uint32_t h_probe = (h + 1) % entry_count;
72  while (h_probe != h) {
73  matching_slot = get_matching_slot<T>(hash_buff, h_probe, key, key_bytes);
74  if (matching_slot != kNoMatch) {
75  return matching_slot;
76  }
77  h_probe = (h_probe + 1) % entry_count;
78  }
79  return kNoMatch;
80 }
NEVER_INLINE DEVICE uint32_t MurmurHash1(const void *key, int len, const uint32_t seed)
Definition: MurmurHash.cpp:20

+ Here is the call graph for this function:

DEVICE bool compare_to_key ( const int8_t *  entry,
const int8_t *  key,
const size_t  key_bytes 
)

Definition at line 24 of file JoinHashTableQueryRuntime.cpp.

Referenced by get_matching_slot().

26  {
27  for (size_t i = 0; i < key_bytes; ++i) {
28  if (entry[i] != key[i]) {
29  return false;
30  }
31  }
32  return true;
33 }

+ Here is the caller graph for this function:

NEVER_INLINE DEVICE int64_t get_bucket_key_for_range_compressed ( const int8_t *  range,
const size_t  range_component_index,
const double  bucket_size 
)

Definition at line 131 of file JoinHashTableQueryRuntime.cpp.

References get_bucket_key_for_range_compressed_impl().

133  {
135  range, range_component_index, bucket_size);
136 }
FORCE_INLINE DEVICE int64_t get_bucket_key_for_range_compressed_impl(const int8_t *range, const size_t range_component_index, const double bucket_size)

+ Here is the call graph for this function:

FORCE_INLINE DEVICE int64_t get_bucket_key_for_range_compressed_impl ( const int8_t *  range,
const size_t  range_component_index,
const double  bucket_size 
)

Definition at line 113 of file JoinHashTableQueryRuntime.cpp.

References Geo_namespace::decompress_lattitude_coord_geoint32(), Geo_namespace::decompress_longitude_coord_geoint32(), and get_bucket_key_for_value_impl().

Referenced by get_bucket_key_for_range_compressed().

115  {
116  const auto range_ptr = reinterpret_cast<const int32_t*>(range);
117  if (range_component_index % 2 == 0) {
120  range_ptr[range_component_index]),
121  bucket_size);
122  } else {
125  range_ptr[range_component_index]),
126  bucket_size);
127  }
128 }
FORCE_INLINE DEVICE int64_t get_bucket_key_for_value_impl(const T value, const double bucket_size)
DEVICE double decompress_lattitude_coord_geoint32(const int32_t compressed)
DEVICE double decompress_longitude_coord_geoint32(const int32_t compressed)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

NEVER_INLINE DEVICE int64_t get_bucket_key_for_range_double ( const int8_t *  range_bytes,
const size_t  range_component_index,
const double  bucket_size 
)

Definition at line 105 of file JoinHashTableQueryRuntime.cpp.

References get_bucket_key_for_value_impl().

107  {
108  const auto range = reinterpret_cast<const double*>(range_bytes);
109  return get_bucket_key_for_value_impl(range[range_component_index], bucket_size);
110 }
FORCE_INLINE DEVICE int64_t get_bucket_key_for_value_impl(const T value, const double bucket_size)

+ Here is the call graph for this function:

template<typename T >
FORCE_INLINE DEVICE int64_t get_bucket_key_for_value_impl ( const T  value,
const double  bucket_size 
)

Definition at line 99 of file JoinHashTableQueryRuntime.cpp.

Referenced by get_bucket_key_for_range_compressed_impl(), and get_bucket_key_for_range_double().

100  {
101  return static_cast<int64_t>(floor(static_cast<double>(value) * bucket_size));
102 }

+ Here is the caller graph for this function:

NEVER_INLINE DEVICE int64_t get_candidate_rows ( int32_t *  out_arr,
const uint32_t  max_arr_size,
const int8_t *  range_bytes,
const int32_t  range_component_index,
const double  bucket_size_x,
const double  bucket_size_y,
const int32_t  keys_count,
const int64_t  key_component_count,
int64_t *  hash_table_ptr,
const int64_t  entry_count,
const int64_t  offset_buffer_ptr_offset,
const int64_t  sub_buff_size 
)

Getting overlapping candidates for the overlaps join algorithm works as follows:

  1. Take the bounds of the Polygon and use the bucket sizes to split the bounding box into the hash keys it falls into.
  2. Iterate over the keys and look them up in the hash table.
  3. When looking up the values of each key, we use a series of offsets to get to the array of row ids.
  4. Since it is possible (likely) we encounter the same row id in several buckets, we need to ensure we remove the duplicates we encounter. A simple ordered insertion is used which ignores duplicate values. Since the N elements we insert can be considered relatively small (N < 200) this exhibits a good tradeoff to conserve space since we are constrained by the stack size on the GPU.

RETURNS: Unique Row IDs are placed on the fixed size stack array that is passed in as out_arr. The number of row ids in this array is returned.

Definition at line 288 of file JoinHashTableQueryRuntime.cpp.

References assert(), get_row_id_buffer_ptr(), insert_sorted(), and Bounds::min_X.

299  {
300  const auto range = reinterpret_cast<const double*>(range_bytes);
301 
302  size_t elem_count = 0;
303 
304  const auto bounds =
305  Bounds{.min_X = range[0], .min_Y = range[1], .max_X = range[2], .max_Y = range[3]};
306 
307  for (int64_t x = floor(bounds.min_X * bucket_size_x);
308  x <= floor(bounds.max_X * bucket_size_x);
309  x++) {
310  for (int64_t y = floor(bounds.min_Y * bucket_size_y);
311  y <= floor(bounds.max_Y * bucket_size_y);
312  y++) {
313  int64_t cur_key[2];
314  cur_key[0] = static_cast<int64_t>(x);
315  cur_key[1] = static_cast<int64_t>(y);
316 
317  const auto buffer_range = get_row_id_buffer_ptr(hash_table_ptr,
318  cur_key,
319  key_component_count,
320  entry_count,
321  offset_buffer_ptr_offset,
322  sub_buff_size);
323 
324  for (int64_t j = 0; j < buffer_range.element_count; j++) {
325  const auto rowid = buffer_range.buffer[j];
326  elem_count += insert_sorted(out_arr, elem_count, rowid);
327  assert(max_arr_size >= elem_count);
328  }
329  }
330  }
331 
332  return elem_count;
333 }
ALWAYS_INLINE DEVICE BufferRange get_row_id_buffer_ptr(int64_t *hash_table_ptr, const int64_t *key, const int64_t key_component_count, const int64_t entry_count, const int64_t offset_buffer_ptr_offset, const int64_t sub_buff_size)
NEVER_INLINE DEVICE int32_t insert_sorted(int32_t *arr, size_t elem_count, int32_t elem)
int64_t const int32_t sz assert(dest)

+ Here is the call graph for this function:

NEVER_INLINE DEVICE int64_t get_composite_key_index_32 ( const int32_t *  key,
const size_t  key_component_count,
const int32_t *  composite_key_dict,
const size_t  entry_count 
)

Definition at line 163 of file JoinHashTableQueryRuntime.cpp.

References get_composite_key_index_impl().

166  {
168  key, key_component_count, composite_key_dict, entry_count);
169 }
FORCE_INLINE DEVICE int64_t get_composite_key_index_impl(const T *key, const size_t key_component_count, const T *composite_key_dict, const size_t entry_count)

+ Here is the call graph for this function:

NEVER_INLINE DEVICE int64_t get_composite_key_index_64 ( const int64_t *  key,
const size_t  key_component_count,
const int64_t *  composite_key_dict,
const size_t  entry_count 
)

Definition at line 172 of file JoinHashTableQueryRuntime.cpp.

References get_composite_key_index_impl().

Referenced by get_row_id_buffer_ptr().

175  {
177  key, key_component_count, composite_key_dict, entry_count);
178 }
FORCE_INLINE DEVICE int64_t get_composite_key_index_impl(const T *key, const size_t key_component_count, const T *composite_key_dict, const size_t entry_count)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<typename T >
FORCE_INLINE DEVICE int64_t get_composite_key_index_impl ( const T *  key,
const size_t  key_component_count,
const T *  composite_key_dict,
const size_t  entry_count 
)

Definition at line 139 of file JoinHashTableQueryRuntime.cpp.

References get_invalid_key(), keys_are_equal(), MurmurHash1(), and SUFFIX.

Referenced by get_composite_key_index_32(), and get_composite_key_index_64().

142  {
143  const uint32_t h = MurmurHash1(key, key_component_count * sizeof(T), 0) % entry_count;
144  uint32_t off = h * key_component_count;
145  if (keys_are_equal(&composite_key_dict[off], key, key_component_count)) {
146  return h;
147  }
148  uint32_t h_probe = (h + 1) % entry_count;
149  while (h_probe != h) {
150  off = h_probe * key_component_count;
151  if (keys_are_equal(&composite_key_dict[off], key, key_component_count)) {
152  return h_probe;
153  }
154  if (composite_key_dict[off] == SUFFIX(get_invalid_key) < T > ()) {
155  return -1;
156  }
157  h_probe = (h_probe + 1) % entry_count;
158  }
159  return -1;
160 }
NEVER_INLINE DEVICE uint32_t MurmurHash1(const void *key, int len, const uint32_t seed)
Definition: MurmurHash.cpp:20
bool keys_are_equal(const T *key1, const T *key2, const size_t key_component_count)
#define SUFFIX(name)
DEVICE T SUFFIX() get_invalid_key()

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

template<class T >
DEVICE int64_t get_matching_slot ( const int8_t *  hash_buff,
const uint32_t  h,
const int8_t *  key,
const size_t  key_bytes 
)

Definition at line 43 of file JoinHashTableQueryRuntime.cpp.

References compare_to_key(), get_invalid_key(), anonymous_namespace{JoinHashTableQueryRuntime.cpp}::kNoMatch, anonymous_namespace{JoinHashTableQueryRuntime.cpp}::kNotPresent, and SUFFIX.

46  {
47  const auto lookup_result_ptr = hash_buff + h * (key_bytes + sizeof(T));
48  if (compare_to_key(lookup_result_ptr, key, key_bytes)) {
49  return *reinterpret_cast<const T*>(lookup_result_ptr + key_bytes);
50  }
51  if (*reinterpret_cast<const T*>(lookup_result_ptr) ==
52  SUFFIX(get_invalid_key) < T > ()) {
53  return kNotPresent;
54  }
55  return kNoMatch;
56 }
DEVICE bool compare_to_key(const int8_t *entry, const int8_t *key, const size_t key_bytes)
#define SUFFIX(name)
DEVICE T SUFFIX() get_invalid_key()

+ Here is the call graph for this function:

NEVER_INLINE DEVICE int32_t get_num_buckets_for_bounds ( const int8_t *  range_bytes,
const int32_t  range_component_index,
const double  bucket_size_x,
const double  bucket_size_y 
)

Definition at line 339 of file JoinHashTableQueryRuntime.cpp.

342  {
343  const auto range = reinterpret_cast<const double*>(range_bytes);
344 
345  const auto bounds_min_x = range[0];
346  const auto bounds_min_y = range[1];
347  const auto bounds_max_x = range[2];
348  const auto bounds_max_y = range[3];
349 
350  const auto num_x =
351  floor(bounds_max_x * bucket_size_x) - floor(bounds_min_x * bucket_size_x);
352  const auto num_y =
353  floor(bounds_max_y * bucket_size_y) - floor(bounds_min_y * bucket_size_y);
354  const auto num_buckets = (num_x + 1) * (num_y + 1);
355 
356  return num_buckets;
357 }
ALWAYS_INLINE DEVICE BufferRange get_row_id_buffer_ptr ( int64_t *  hash_table_ptr,
const int64_t *  key,
const int64_t  key_component_count,
const int64_t  entry_count,
const int64_t  offset_buffer_ptr_offset,
const int64_t  sub_buff_size 
)

Definition at line 217 of file JoinHashTableQueryRuntime.cpp.

References BufferRange::buffer, get_composite_key_index_64(), and overlaps_hash_join_idx().

Referenced by get_candidate_rows().

222  {
223  const int64_t min_key = 0;
224  const int64_t max_key = entry_count - 1;
225 
226  auto key_idx =
227  get_composite_key_index_64(key, key_component_count, hash_table_ptr, entry_count);
228 
229  if (key_idx < -1) {
230  return BufferRange{.buffer = nullptr, .element_count = 0};
231  }
232 
233  int8_t* one_to_many_ptr = reinterpret_cast<int8_t*>(hash_table_ptr);
234  one_to_many_ptr += offset_buffer_ptr_offset;
235 
236  // Returns an index used to fetch row count and row ids.
237  const auto slot = overlaps_hash_join_idx(
238  reinterpret_cast<int64_t>(one_to_many_ptr), key_idx, min_key, max_key);
239  if (slot < 0) {
240  return BufferRange{.buffer = nullptr, .element_count = 0};
241  }
242 
243  // Offset into the row count section of buffer
244  int8_t* count_ptr = one_to_many_ptr + sub_buff_size;
245 
246  const int64_t matched_row_count = overlaps_hash_join_idx(
247  reinterpret_cast<int64_t>(count_ptr), key_idx, min_key, max_key);
248 
249  // Offset into payload section, containing an array of row ids
250  int32_t* rowid_buffer = (int32_t*)(one_to_many_ptr + 2 * sub_buff_size);
251  const auto rowidoff_ptr = &rowid_buffer[slot];
252 
253  return BufferRange{.buffer = rowidoff_ptr, .element_count = matched_row_count};
254 }
ALWAYS_INLINE DEVICE int64_t overlaps_hash_join_idx(int64_t hash_buff, const int64_t key, const int64_t min_key, const int64_t max_key)
NEVER_INLINE DEVICE int64_t get_composite_key_index_64(const int64_t *key, const size_t key_component_count, const int64_t *composite_key_dict, const size_t entry_count)

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

NEVER_INLINE DEVICE int32_t insert_sorted ( int32_t *  arr,
size_t  elem_count,
int32_t  elem 
)

Definition at line 180 of file JoinHashTableQueryRuntime.cpp.

Referenced by get_candidate_rows().

182  {
183  for (size_t i = 0; i < elem_count; i++) {
184  if (elem == arr[i])
185  return 0;
186 
187  if (elem > arr[i])
188  continue;
189 
190  for (size_t j = elem_count; i < j; j--) {
191  arr[j] = arr[j - 1];
192  }
193  arr[i] = elem;
194  return 1;
195  }
196 
197  arr[elem_count] = elem;
198  return 1;
199 }

+ Here is the caller graph for this function:

ALWAYS_INLINE DEVICE int64_t overlaps_hash_join_idx ( int64_t  hash_buff,
const int64_t  key,
const int64_t  min_key,
const int64_t  max_key 
)

Definition at line 201 of file JoinHashTableQueryRuntime.cpp.

Referenced by get_row_id_buffer_ptr().

204  {
205  if (key >= min_key && key <= max_key) {
206  return *(reinterpret_cast<int32_t*>(hash_buff) + (key - min_key));
207  }
208  return -1;
209 }

+ Here is the caller graph for this function: