OmniSciDB  eb3a3d0a03
 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(_MSC_VER)
35 #define insert_key_cas(address, compare, val) \
36  InterlockedCompareExchange(reinterpret_cast<volatile long*>(address), \
37  static_cast<long>(val), \
38  static_cast<long>(compare))
39 #else
40 #define insert_key_cas(address, compare, val) \
41  __sync_val_compare_and_swap(address, compare, val)
42 #endif
43 
45  size_t idx,
46  int32_t* entry_ptr,
47  const int32_t invalid_slot_val) {
48  if (insert_key_cas(entry_ptr, invalid_slot_val, idx) != invalid_slot_val) {
49  return -1;
50  }
51  return 0;
52 }
53 
55  size_t idx,
56  int32_t* entry_ptr,
57  const int32_t invalid_slot_val) {
58  // just mark the existence of value to the corresponding hash slot
59  // regardless of hashtable collision
60  insert_key_cas(entry_ptr, invalid_slot_val, idx);
61  return 0;
62 }
63 
64 #undef insert_key_cas
65 
67  int32_t* buff,
68  const int64_t key,
69  const int64_t min_key,
70  const int64_t bucket_normalization) {
71  return buff + (key - min_key) / bucket_normalization;
72 }
73 
74 extern "C" ALWAYS_INLINE DEVICE int32_t* SUFFIX(get_hash_slot)(int32_t* buff,
75  const int64_t key,
76  const int64_t min_key) {
77  return buff + (key - min_key);
78 }
79 
81  int32_t* buff,
82  const int64_t key,
83  const int64_t min_key,
84  const uint32_t entry_count_per_shard,
85  const uint32_t num_shards,
86  const uint32_t device_count,
87  const int64_t bucket_normalization) {
88  const uint32_t shard = SHARD_FOR_KEY(key, num_shards);
89  const uint32_t shard_buffer_index =
90  shard / device_count; // shard sub-buffer index within `buff`
91  int32_t* shard_buffer = buff + shard_buffer_index * entry_count_per_shard;
92  return shard_buffer + (key - min_key) / bucket_normalization / num_shards;
93 }
94 
96  int32_t* buff,
97  const int64_t key,
98  const int64_t min_key,
99  const uint32_t entry_count_per_shard,
100  const uint32_t num_shards,
101  const uint32_t device_count) {
102  const uint32_t shard = SHARD_FOR_KEY(key, num_shards);
103  const uint32_t shard_buffer_index =
104  shard / device_count; // shard sub-buffer index within `buff`
105  int32_t* shard_buffer = buff + shard_buffer_index * entry_count_per_shard;
106  return shard_buffer + (key - min_key) / num_shards;
107 }
108 
110  int32_t* buff,
111  const int64_t key,
112  const int64_t min_key,
113  const uint32_t entry_count_per_shard,
114  const uint32_t shard,
115  const uint32_t num_shards,
116  const uint32_t device_count,
117  const int64_t bucket_normalization) {
118  const uint32_t shard_buffer_index =
119  shard / device_count; // shard sub-buffer index within `buff`
120  int32_t* shard_buffer = buff + shard_buffer_index * entry_count_per_shard;
121  return shard_buffer + (key - min_key) / bucket_normalization / num_shards;
122 }
123 
125  int32_t* buff,
126  const int64_t key,
127  const int64_t min_key,
128  const uint32_t entry_count_per_shard,
129  const uint32_t shard,
130  const uint32_t num_shards,
131  const uint32_t device_count) {
132  const uint32_t shard_buffer_index =
133  shard / device_count; // shard sub-buffer index within `buff`
134  int32_t* shard_buffer = buff + shard_buffer_index * entry_count_per_shard;
135  return shard_buffer + (key - min_key) / num_shards;
136 }
137 
138 #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:66
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:109
#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:54
#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:74
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:80
#define insert_key_cas(address, compare, val)
Definition: JoinHashImpl.h:40
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:124
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:95
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:44
#define ALWAYS_INLINE
#define SHARD_FOR_KEY(key, num_shards)
Definition: shard_key.h:20