OmniSciDB  8fa3bf436f
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GroupByAndAggregate.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 #ifndef QUERYENGINE_GROUPBYANDAGGREGATE_H
18 #define QUERYENGINE_GROUPBYANDAGGREGATE_H
19 
20 #include "BufferCompaction.h"
21 #include "ColumnarResults.h"
22 #include "CompilationOptions.h"
23 #include "GpuMemUtils.h"
24 #include "GpuSharedMemoryContext.h"
25 #include "InputMetadata.h"
26 #include "QueryExecutionContext.h"
27 #include "Rendering/RenderInfo.h"
28 #include "RuntimeFunctions.h"
29 
31 
32 #include "../Shared/sqltypes.h"
33 #include "Logger/Logger.h"
34 
35 #include <llvm/IR/Function.h>
36 #include <llvm/IR/Instructions.h>
37 #include <llvm/IR/Value.h>
38 #include <boost/algorithm/string/join.hpp>
39 #include <boost/make_unique.hpp>
40 
41 #include <stack>
42 #include <vector>
43 
44 extern bool g_enable_smem_group_by;
45 extern bool g_bigint_count;
46 
47 struct ColRangeInfo {
49  int64_t min;
50  int64_t max;
51  int64_t bucket;
52  bool has_nulls;
53  bool isEmpty() { return min == 0 && max == -1; }
54 };
55 
56 struct KeylessInfo {
57  const bool keyless;
58  const int32_t target_index;
59 };
60 
62  public:
63  GroupByAndAggregate(Executor* executor,
64  const ExecutorDeviceType device_type,
65  const RelAlgExecutionUnit& ra_exe_unit,
66  const std::vector<InputTableInfo>& query_infos,
67  std::shared_ptr<RowSetMemoryOwner> row_set_mem_owner,
68  const std::optional<int64_t>& group_cardinality_estimation);
69 
70  // returns true iff checking the error code after every row
71  // is required -- slow path group by queries for now
72  bool codegen(llvm::Value* filter_result,
73  llvm::BasicBlock* sc_false,
75  const CompilationOptions& co,
76  const GpuSharedMemoryContext& gpu_smem_context);
77 
78  static void addTransientStringLiterals(
79  const RelAlgExecutionUnit& ra_exe_unit,
80  Executor* executor,
81  std::shared_ptr<RowSetMemoryOwner> row_set_mem_owner);
82 
83  static size_t shard_count_for_top_groups(const RelAlgExecutionUnit& ra_exe_unit,
84  const Catalog_Namespace::Catalog& catalog);
85 
86  private:
87  bool gpuCanHandleOrderEntries(const std::list<Analyzer::OrderEntry>& order_entries);
88 
89  std::unique_ptr<QueryMemoryDescriptor> initQueryMemoryDescriptor(
90  const bool allow_multifrag,
91  const size_t max_groups_buffer_entry_count,
92  const int8_t crt_min_byte_width,
93  RenderInfo* render_info,
94  const bool output_columnar_hint);
95 
96  std::unique_ptr<QueryMemoryDescriptor> initQueryMemoryDescriptorImpl(
97  const bool allow_multifrag,
98  const size_t max_groups_buffer_entry_count,
99  const int8_t crt_min_byte_width,
100  const bool sort_on_gpu_hint,
101  RenderInfo* render_info,
102  const bool must_use_baseline_sort,
103  const bool output_columnar_hint);
104 
105  int64_t getShardedTopBucket(const ColRangeInfo& col_range_info,
106  const size_t shard_count) const;
107 
109 
110  llvm::Value* codegenOutputSlot(llvm::Value* groups_buffer,
111  const QueryMemoryDescriptor& query_mem_desc,
112  const CompilationOptions& co,
113  DiamondCodegen& diamond_codegen);
114 
115  std::tuple<llvm::Value*, llvm::Value*> codegenGroupBy(
116  const QueryMemoryDescriptor& query_mem_desc,
117  const CompilationOptions& co,
118  DiamondCodegen& codegen);
119 
120  std::tuple<llvm::Value*, llvm::Value*> codegenSingleColumnPerfectHash(
121  const QueryMemoryDescriptor& query_mem_desc,
122  const CompilationOptions& co,
123  llvm::Value* groups_buffer,
124  llvm::Value* group_expr_lv_translated,
125  llvm::Value* group_expr_lv_original,
126  const int32_t row_size_quad);
127 
128  std::tuple<llvm::Value*, llvm::Value*> codegenMultiColumnPerfectHash(
129  llvm::Value* groups_buffer,
130  llvm::Value* group_key,
131  llvm::Value* key_size_lv,
132  const QueryMemoryDescriptor& query_mem_desc,
133  const int32_t row_size_quad);
134  llvm::Function* codegenPerfectHashFunction();
135 
136  std::tuple<llvm::Value*, llvm::Value*> codegenMultiColumnBaselineHash(
137  const CompilationOptions& co,
138  llvm::Value* groups_buffer,
139  llvm::Value* group_key,
140  llvm::Value* key_size_lv,
141  const QueryMemoryDescriptor& query_mem_desc,
142  const size_t key_width,
143  const int32_t row_size_quad);
144 
146 
147  static int64_t getBucketedCardinality(const ColRangeInfo& col_range_info);
148 
149  llvm::Value* convertNullIfAny(const SQLTypeInfo& arg_type,
150  const TargetInfo& agg_info,
151  llvm::Value* target);
152 
153  bool codegenAggCalls(const std::tuple<llvm::Value*, llvm::Value*>& agg_out_ptr_w_idx,
154  const std::vector<llvm::Value*>& agg_out_vec,
155  const QueryMemoryDescriptor& query_mem_desc,
156  const CompilationOptions& co,
157  const GpuSharedMemoryContext& gpu_smem_context,
158  DiamondCodegen& diamond_codegen);
159 
160  llvm::Value* codegenWindowRowPointer(const Analyzer::WindowFunction* window_func,
161  const QueryMemoryDescriptor& query_mem_desc,
162  const CompilationOptions& co,
163  DiamondCodegen& diamond_codegen);
164 
165  llvm::Value* codegenAggColumnPtr(
166  llvm::Value* output_buffer_byte_stream,
167  llvm::Value* out_row_idx,
168  const std::tuple<llvm::Value*, llvm::Value*>& agg_out_ptr_w_idx,
169  const QueryMemoryDescriptor& query_mem_desc,
170  const size_t chosen_bytes,
171  const size_t agg_out_off,
172  const size_t target_idx);
173 
174  void codegenEstimator(std::stack<llvm::BasicBlock*>& array_loops,
175  DiamondCodegen& diamond_codegen,
176  const QueryMemoryDescriptor& query_mem_desc,
177  const CompilationOptions&);
178 
179  void codegenCountDistinct(const size_t target_idx,
180  const Analyzer::Expr* target_expr,
181  std::vector<llvm::Value*>& agg_args,
182  const QueryMemoryDescriptor&,
183  const ExecutorDeviceType);
184 
185  void codegenApproxMedian(const size_t target_idx,
186  const Analyzer::Expr* target_expr,
187  std::vector<llvm::Value*>& agg_args,
188  const QueryMemoryDescriptor& query_mem_desc,
189  const ExecutorDeviceType device_type);
190 
191  llvm::Value* getAdditionalLiteral(const int32_t off);
192 
193  std::vector<llvm::Value*> codegenAggArg(const Analyzer::Expr* target_expr,
194  const CompilationOptions& co);
195 
196  llvm::Value* emitCall(const std::string& fname, const std::vector<llvm::Value*>& args);
197 
198  void checkErrorCode(llvm::Value* retCode);
199 
200  bool needsUnnestDoublePatch(llvm::Value const* val_ptr,
201  const std::string& agg_base_name,
202  const bool threads_share_memory,
203  const CompilationOptions& co) const;
204 
205  void prependForceSync();
206 
209  const std::vector<InputTableInfo>& query_infos_;
210  std::shared_ptr<RowSetMemoryOwner> row_set_mem_owner_;
213 
214  const std::optional<int64_t> group_cardinality_estimation_;
215 
216  friend class Executor;
217  friend class QueryMemoryDescriptor;
218  friend class CodeGenerator;
219  friend class ExecutionKernel;
220  friend struct TargetExprCodegen;
222 };
223 
224 inline int64_t extract_from_datum(const Datum datum, const SQLTypeInfo& ti) {
225  const auto type = ti.is_decimal() ? decimal_to_int_type(ti) : ti.get_type();
226  switch (type) {
227  case kBOOLEAN:
228  return datum.tinyintval;
229  case kTINYINT:
230  return datum.tinyintval;
231  case kSMALLINT:
232  return datum.smallintval;
233  case kCHAR:
234  case kVARCHAR:
235  case kTEXT:
237  case kINT:
238  return datum.intval;
239  case kBIGINT:
240  return datum.bigintval;
241  case kTIME:
242  case kTIMESTAMP:
243  case kDATE:
244  return datum.bigintval;
245  default:
246  abort();
247  }
248 }
249 
250 inline int64_t extract_min_stat(const ChunkStats& stats, const SQLTypeInfo& ti) {
251  return extract_from_datum(stats.min, ti);
252 }
253 
254 inline int64_t extract_max_stat(const ChunkStats& stats, const SQLTypeInfo& ti) {
255  return extract_from_datum(stats.max, ti);
256 }
257 
258 inline size_t get_count_distinct_sub_bitmap_count(const size_t bitmap_sz_bits,
260  const ExecutorDeviceType device_type) {
261  // For count distinct on a column with a very small number of distinct values
262  // contention can be very high, especially for non-grouped queries. We'll split
263  // the bitmap into multiple sub-bitmaps which are unified to get the full result.
264  // The threshold value for bitmap_sz_bits works well on Kepler.
265  return bitmap_sz_bits < 50000 && ra_exe_unit.groupby_exprs.empty() &&
266  (device_type == ExecutorDeviceType::GPU || g_cluster)
267  ? 64 // NB: must be a power of 2 to keep runtime offset computations cheap
268  : 1;
269 }
270 
271 #endif // QUERYENGINE_GROUPBYANDAGGREGATE_H
int8_t tinyintval
Definition: sqltypes.h:206
const RelAlgExecutionUnit & ra_exe_unit
#define CHECK_EQ(x, y)
Definition: Logger.h:211
bool g_enable_smem_group_by
bool gpuCanHandleOrderEntries(const std::list< Analyzer::OrderEntry > &order_entries)
static int64_t getBucketedCardinality(const ColRangeInfo &col_range_info)
llvm::Value * getAdditionalLiteral(const int32_t off)
llvm::Value * codegenAggColumnPtr(llvm::Value *output_buffer_byte_stream, llvm::Value *out_row_idx, const std::tuple< llvm::Value *, llvm::Value * > &agg_out_ptr_w_idx, const QueryMemoryDescriptor &query_mem_desc, const size_t chosen_bytes, const size_t agg_out_off, const size_t target_idx)
: returns the pointer to where the aggregation should be stored.
bool codegenAggCalls(const std::tuple< llvm::Value *, llvm::Value * > &agg_out_ptr_w_idx, const std::vector< llvm::Value * > &agg_out_vec, const QueryMemoryDescriptor &query_mem_desc, const CompilationOptions &co, const GpuSharedMemoryContext &gpu_smem_context, DiamondCodegen &diamond_codegen)
class for a per-database catalog. also includes metadata for the current database and the current use...
Definition: Catalog.h:102
Definition: sqltypes.h:48
const bool keyless
ExecutorDeviceType
std::unique_ptr< QueryMemoryDescriptor > initQueryMemoryDescriptorImpl(const bool allow_multifrag, const size_t max_groups_buffer_entry_count, const int8_t crt_min_byte_width, const bool sort_on_gpu_hint, RenderInfo *render_info, const bool must_use_baseline_sort, const bool output_columnar_hint)
void codegenApproxMedian(const size_t target_idx, const Analyzer::Expr *target_expr, std::vector< llvm::Value * > &agg_args, const QueryMemoryDescriptor &query_mem_desc, const ExecutorDeviceType device_type)
ColRangeInfo getColRangeInfo()
bool codegen(llvm::Value *filter_result, llvm::BasicBlock *sc_false, const QueryMemoryDescriptor &query_mem_desc, const CompilationOptions &co, const GpuSharedMemoryContext &gpu_smem_context)
QueryDescriptionType hash_type_
llvm::Value * emitCall(const std::string &fname, const std::vector< llvm::Value * > &args)
std::shared_ptr< RowSetMemoryOwner > row_set_mem_owner_
void checkErrorCode(llvm::Value *retCode)
const std::list< std::shared_ptr< Analyzer::Expr > > groupby_exprs
HOST DEVICE SQLTypes get_type() const
Definition: sqltypes.h:314
bool needsUnnestDoublePatch(llvm::Value const *val_ptr, const std::string &agg_base_name, const bool threads_share_memory, const CompilationOptions &co) const
std::tuple< llvm::Value *, llvm::Value * > codegenMultiColumnBaselineHash(const CompilationOptions &co, llvm::Value *groups_buffer, llvm::Value *group_key, llvm::Value *key_size_lv, const QueryMemoryDescriptor &query_mem_desc, const size_t key_width, const int32_t row_size_quad)
int64_t extract_from_datum(const Datum datum, const SQLTypeInfo &ti)
int32_t intval
Definition: sqltypes.h:208
size_t get_count_distinct_sub_bitmap_count(const size_t bitmap_sz_bits, const RelAlgExecutionUnit &ra_exe_unit, const ExecutorDeviceType device_type)
GroupByAndAggregate(Executor *executor, const ExecutorDeviceType device_type, const RelAlgExecutionUnit &ra_exe_unit, const std::vector< InputTableInfo > &query_infos, std::shared_ptr< RowSetMemoryOwner > row_set_mem_owner, const std::optional< int64_t > &group_cardinality_estimation)
llvm::Value * convertNullIfAny(const SQLTypeInfo &arg_type, const TargetInfo &agg_info, llvm::Value *target)
int64_t bigintval
Definition: sqltypes.h:209
std::tuple< llvm::Value *, llvm::Value * > codegenSingleColumnPerfectHash(const QueryMemoryDescriptor &query_mem_desc, const CompilationOptions &co, llvm::Value *groups_buffer, llvm::Value *group_expr_lv_translated, llvm::Value *group_expr_lv_original, const int32_t row_size_quad)
std::tuple< llvm::Value *, llvm::Value * > codegenGroupBy(const QueryMemoryDescriptor &query_mem_desc, const CompilationOptions &co, DiamondCodegen &codegen)
bool g_bigint_count
int16_t smallintval
Definition: sqltypes.h:207
void codegenCountDistinct(const size_t target_idx, const Analyzer::Expr *target_expr, std::vector< llvm::Value * > &agg_args, const QueryMemoryDescriptor &, const ExecutorDeviceType)
std::tuple< llvm::Value *, llvm::Value * > codegenMultiColumnPerfectHash(llvm::Value *groups_buffer, llvm::Value *group_key, llvm::Value *key_size_lv, const QueryMemoryDescriptor &query_mem_desc, const int32_t row_size_quad)
int64_t getShardedTopBucket(const ColRangeInfo &col_range_info, const size_t shard_count) const
SQLTypes decimal_to_int_type(const SQLTypeInfo &ti)
Definition: Datum.cpp:419
const int32_t target_index
Definition: sqltypes.h:51
Definition: sqltypes.h:52
const std::vector< InputTableInfo > & query_infos_
HOST DEVICE EncodingType get_compression() const
Definition: sqltypes.h:322
std::unique_ptr< QueryMemoryDescriptor > initQueryMemoryDescriptor(const bool allow_multifrag, const size_t max_groups_buffer_entry_count, const int8_t crt_min_byte_width, RenderInfo *render_info, const bool output_columnar_hint)
const ExecutorDeviceType device_type_
void codegenEstimator(std::stack< llvm::BasicBlock * > &array_loops, DiamondCodegen &diamond_codegen, const QueryMemoryDescriptor &query_mem_desc, const CompilationOptions &)
std::vector< llvm::Value * > codegenAggArg(const Analyzer::Expr *target_expr, const CompilationOptions &co)
llvm::Function * codegenPerfectHashFunction()
llvm::Value * codegenWindowRowPointer(const Analyzer::WindowFunction *window_func, const QueryMemoryDescriptor &query_mem_desc, const CompilationOptions &co, DiamondCodegen &diamond_codegen)
Definition: sqltypes.h:40
const std::optional< int64_t > group_cardinality_estimation_
llvm::Value * codegenOutputSlot(llvm::Value *groups_buffer, const QueryMemoryDescriptor &query_mem_desc, const CompilationOptions &co, DiamondCodegen &diamond_codegen)
int64_t extract_min_stat(const ChunkStats &stats, const SQLTypeInfo &ti)
QueryDescriptionType
Definition: Types.h:26
bool g_cluster
Definition: sqltypes.h:44
const RelAlgExecutionUnit & ra_exe_unit_
bool is_decimal() const
Definition: sqltypes.h:492
int64_t extract_max_stat(const ChunkStats &stats, const SQLTypeInfo &ti)
static size_t shard_count_for_top_groups(const RelAlgExecutionUnit &ra_exe_unit, const Catalog_Namespace::Catalog &catalog)