OmniSciDB  91042dcc5b
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
JoinHashImpl.h
Go to the documentation of this file.
1 /*
2  * Copyright 2017 MapD Technologies, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 /*
18  * @file JoinHashImpl.h
19  * @author Alex Suhan <alex@mapd.com>
20  *
21  * Copyright (c) 2015 MapD Technologies, Inc. All rights reserved.
22  */
23 
24 #ifndef QUERYENGINE_GROUPBYFASTIMPL_H
25 #define QUERYENGINE_GROUPBYFASTIMPL_H
26 
27 #include <cstdint>
28 #include <functional>
29 #include "../../../Shared/funcannotations.h"
30 #include "../../../Shared/shard_key.h"
31 
32 #ifdef __CUDACC__
33 #define insert_key_cas(address, compare, val) atomicCAS(address, compare, val)
34 #elif defined(_WIN32)
35 #include "Shared/clean_windows.h"
36 #define insert_key_cas(address, compare, val) \
37  InterlockedCompareExchange(reinterpret_cast<volatile long*>(address), \
38  static_cast<long>(val), \
39  static_cast<long>(compare))
40 #else
41 #define insert_key_cas(address, compare, val) \
42  __sync_val_compare_and_swap(address, compare, val)
43 #endif
44 
46  size_t idx,
47  int32_t* entry_ptr,
48  const int32_t invalid_slot_val) {
49  if (insert_key_cas(entry_ptr, invalid_slot_val, idx) != invalid_slot_val) {
50  return -1;
51  }
52  return 0;
53 }
54 
56  size_t idx,
57  int32_t* entry_ptr,
58  const int32_t invalid_slot_val) {
59  // just mark the existence of value to the corresponding hash slot
60  // regardless of hashtable collision
61  insert_key_cas(entry_ptr, invalid_slot_val, idx);
62  return 0;
63 }
64 
65 #undef insert_key_cas
66 
68  int32_t* buff,
69  const int64_t key,
70  const int64_t min_key,
71  const int64_t bucket_normalization) {
72  return buff + (key - min_key) / bucket_normalization;
73 }
74 
75 extern "C" ALWAYS_INLINE DEVICE int32_t* SUFFIX(get_hash_slot)(int32_t* buff,
76  const int64_t key,
77  const int64_t min_key) {
78  return buff + (key - min_key);
79 }
80 
82  int32_t* buff,
83  const int64_t key,
84  const int64_t min_key,
85  const uint32_t entry_count_per_shard,
86  const uint32_t num_shards,
87  const uint32_t device_count,
88  const int64_t bucket_normalization) {
89  const uint32_t shard = SHARD_FOR_KEY(key, num_shards);
90  const uint32_t shard_buffer_index =
91  shard / device_count; // shard sub-buffer index within `buff`
92  int32_t* shard_buffer = buff + shard_buffer_index * entry_count_per_shard;
93  return shard_buffer + (key - min_key) / bucket_normalization / num_shards;
94 }
95 
97  int32_t* buff,
98  const int64_t key,
99  const int64_t min_key,
100  const uint32_t entry_count_per_shard,
101  const uint32_t num_shards,
102  const uint32_t device_count) {
103  const uint32_t shard = SHARD_FOR_KEY(key, num_shards);
104  const uint32_t shard_buffer_index =
105  shard / device_count; // shard sub-buffer index within `buff`
106  int32_t* shard_buffer = buff + shard_buffer_index * entry_count_per_shard;
107  return shard_buffer + (key - min_key) / num_shards;
108 }
109 
111  int32_t* buff,
112  const int64_t key,
113  const int64_t min_key,
114  const uint32_t entry_count_per_shard,
115  const uint32_t shard,
116  const uint32_t num_shards,
117  const uint32_t device_count,
118  const int64_t bucket_normalization) {
119  const uint32_t shard_buffer_index =
120  shard / device_count; // shard sub-buffer index within `buff`
121  int32_t* shard_buffer = buff + shard_buffer_index * entry_count_per_shard;
122  return shard_buffer + (key - min_key) / bucket_normalization / num_shards;
123 }
124 
126  int32_t* buff,
127  const int64_t key,
128  const int64_t min_key,
129  const uint32_t entry_count_per_shard,
130  const uint32_t shard,
131  const uint32_t num_shards,
132  const uint32_t device_count) {
133  const uint32_t shard_buffer_index =
134  shard / device_count; // shard sub-buffer index within `buff`
135  int32_t* shard_buffer = buff + shard_buffer_index * entry_count_per_shard;
136  return shard_buffer + (key - min_key) / num_shards;
137 }
138 
139 #endif // QUERYENGINE_GROUPBYFASTIMPL_H
ALWAYS_INLINE DEVICE int32_t *SUFFIX() get_bucketized_hash_slot(int32_t *buff, const int64_t key, const int64_t min_key, const int64_t bucket_normalization)
Definition: JoinHashImpl.h:67
ALWAYS_INLINE DEVICE int32_t *SUFFIX() get_bucketized_hash_slot_sharded_opt(int32_t *buff, const int64_t key, const int64_t min_key, const uint32_t entry_count_per_shard, const uint32_t shard, const uint32_t num_shards, const uint32_t device_count, const int64_t bucket_normalization)
Definition: JoinHashImpl.h:110
#define SUFFIX(name)
ALWAYS_INLINE DEVICE int SUFFIX() fill_hashtable_for_semi_join(size_t idx, int32_t *entry_ptr, const int32_t invalid_slot_val)
Definition: JoinHashImpl.h:55
#define DEVICE
ALWAYS_INLINE DEVICE int32_t *SUFFIX() get_hash_slot(int32_t *buff, const int64_t key, const int64_t min_key)
Definition: JoinHashImpl.h:75
ALWAYS_INLINE DEVICE int32_t *SUFFIX() get_bucketized_hash_slot_sharded(int32_t *buff, const int64_t key, const int64_t min_key, const uint32_t entry_count_per_shard, const uint32_t num_shards, const uint32_t device_count, const int64_t bucket_normalization)
Definition: JoinHashImpl.h:81
#define insert_key_cas(address, compare, val)
Definition: JoinHashImpl.h:41
ALWAYS_INLINE DEVICE int32_t *SUFFIX() get_hash_slot_sharded_opt(int32_t *buff, const int64_t key, const int64_t min_key, const uint32_t entry_count_per_shard, const uint32_t shard, const uint32_t num_shards, const uint32_t device_count)
Definition: JoinHashImpl.h:125
ALWAYS_INLINE DEVICE int32_t *SUFFIX() get_hash_slot_sharded(int32_t *buff, const int64_t key, const int64_t min_key, const uint32_t entry_count_per_shard, const uint32_t num_shards, const uint32_t device_count)
Definition: JoinHashImpl.h:96
ALWAYS_INLINE DEVICE int SUFFIX() fill_one_to_one_hashtable(size_t idx, int32_t *entry_ptr, const int32_t invalid_slot_val)
Definition: JoinHashImpl.h:45
#define ALWAYS_INLINE
#define SHARD_FOR_KEY(key, num_shards)
Definition: shard_key.h:20