OmniSciDB  c07336695a
JoinHashTableQueryRuntime.cpp File Reference
+ 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.

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)
 

Variables

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

Function Documentation

◆ baseline_hash_join_idx_32()

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 80 of file JoinHashTableQueryRuntime.cpp.

References DEVICE, and NEVER_INLINE.

83  {
84  return baseline_hash_join_idx_impl<int32_t>(hash_buff, key, key_bytes, entry_count);
85 }

◆ baseline_hash_join_idx_64()

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 88 of file JoinHashTableQueryRuntime.cpp.

91  {
92  return baseline_hash_join_idx_impl<int64_t>(hash_buff, key, key_bytes, entry_count);
93 }

◆ baseline_hash_join_idx_impl()

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 56 of file JoinHashTableQueryRuntime.cpp.

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

59  {
60  if (!entry_count) {
61  return kNoMatch;
62  }
63  const uint32_t h = MurmurHash1(key, key_bytes, 0) % entry_count;
64  int64_t matching_slot = get_matching_slot<T>(hash_buff, h, key, key_bytes);
65  if (matching_slot != kNoMatch) {
66  return matching_slot;
67  }
68  uint32_t h_probe = (h + 1) % entry_count;
69  while (h_probe != h) {
70  matching_slot = get_matching_slot<T>(hash_buff, h_probe, key, key_bytes);
71  if (matching_slot != kNoMatch) {
72  return matching_slot;
73  }
74  h_probe = (h_probe + 1) % entry_count;
75  }
76  return kNoMatch;
77 }
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:

◆ compare_to_key()

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

Definition at line 21 of file JoinHashTableQueryRuntime.cpp.

Referenced by get_matching_slot().

23  {
24  for (size_t i = 0; i < key_bytes; ++i) {
25  if (entry[i] != key[i]) {
26  return false;
27  }
28  }
29  return true;
30 }
+ Here is the caller graph for this function:

◆ get_bucket_key_for_range_compressed()

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 128 of file JoinHashTableQueryRuntime.cpp.

References get_bucket_key_for_range_compressed_impl().

130  {
132  range, range_component_index, bucket_size);
133 }
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:

◆ get_bucket_key_for_range_compressed_impl()

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 110 of file JoinHashTableQueryRuntime.cpp.

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

Referenced by get_bucket_key_for_range_compressed().

112  {
113  const auto range_ptr = reinterpret_cast<const int32_t*>(range);
114  if (range_component_index % 2 == 0) {
117  range_ptr[range_component_index]),
118  bucket_size);
119  } else {
122  range_ptr[range_component_index]),
123  bucket_size);
124  }
125 }
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:

◆ get_bucket_key_for_range_double()

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 102 of file JoinHashTableQueryRuntime.cpp.

References DEVICE, FORCE_INLINE, and get_bucket_key_for_value_impl().

104  {
105  const auto range = reinterpret_cast<const double*>(range_bytes);
106  return get_bucket_key_for_value_impl(range[range_component_index], bucket_size);
107 }
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:

◆ get_bucket_key_for_value_impl()

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

Definition at line 96 of file JoinHashTableQueryRuntime.cpp.

References DEVICE, and NEVER_INLINE.

Referenced by get_bucket_key_for_range_compressed_impl(), and get_bucket_key_for_range_double().

97  {
98  return static_cast<int64_t>(floor(static_cast<double>(value) * bucket_size));
99 }
+ Here is the caller graph for this function:

◆ get_composite_key_index_32()

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 160 of file JoinHashTableQueryRuntime.cpp.

References DEVICE, get_composite_key_index_impl(), and NEVER_INLINE.

163  {
165  key, key_component_count, composite_key_dict, entry_count);
166 }
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:

◆ get_composite_key_index_64()

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 169 of file JoinHashTableQueryRuntime.cpp.

References get_composite_key_index_impl().

172  {
174  key, key_component_count, composite_key_dict, entry_count);
175 }
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:

◆ get_composite_key_index_impl()

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 136 of file JoinHashTableQueryRuntime.cpp.

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

Referenced by get_composite_key_index_32(), and get_composite_key_index_64().

139  {
140  const uint32_t h = MurmurHash1(key, key_component_count * sizeof(T), 0) % entry_count;
141  uint32_t off = h * key_component_count;
142  if (keys_are_equal(&composite_key_dict[off], key, key_component_count)) {
143  return h;
144  }
145  uint32_t h_probe = (h + 1) % entry_count;
146  while (h_probe != h) {
147  off = h_probe * key_component_count;
148  if (keys_are_equal(&composite_key_dict[off], key, key_component_count)) {
149  return h_probe;
150  }
151  if (composite_key_dict[off] == SUFFIX(get_invalid_key) < T > ()) {
152  return -1;
153  }
154  h_probe = (h_probe + 1) % entry_count;
155  }
156  return -1;
157 }
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:

◆ get_matching_slot()

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 40 of file JoinHashTableQueryRuntime.cpp.

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

43  {
44  const auto lookup_result_ptr = hash_buff + h * (key_bytes + sizeof(T));
45  if (compare_to_key(lookup_result_ptr, key, key_bytes)) {
46  return *reinterpret_cast<const T*>(lookup_result_ptr + key_bytes);
47  }
48  if (*reinterpret_cast<const T*>(lookup_result_ptr) ==
49  SUFFIX(get_invalid_key) < T > ()) {
50  return kNotPresent;
51  }
52  return kNoMatch;
53 }
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: