OmniSciDB  6686921089
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
JoinLoop.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 #pragma once
18 
19 #include <llvm/IR/BasicBlock.h>
20 #include <llvm/IR/IRBuilder.h>
21 #include <llvm/IR/Value.h>
22 #include "Logger/Logger.h"
23 
24 #include "../../Shared/sqldefs.h"
25 #include "../CgenState.h"
26 #include "../IRCodegenUtils.h"
27 
28 #include <functional>
29 #include <vector>
30 
31 enum class JoinLoopKind {
32  UpperBound, // loop join
33  Set, // one to many hash join
34  Singleton, // one to one hash join
35  MultiSet // many to many hash join
36 };
37 
38 // The domain of iteration for a join:
39 // 1. For loop join, from 0 to `upper_bound`.
40 // 2. For one-to-one joins, at most one value: `slot_lookup_result` if valid (greater than
41 // or equal to zero).
42 // 3. For one-to-many joins, the `element_count` values in `values_buffer`.
44  union {
45  llvm::Value* upper_bound; // for UpperBound
46  llvm::Value* element_count; // for Set
47  llvm::Value* slot_lookup_result; // for Singleton
48  };
49  llvm::Value* values_buffer; // used for Set
50 };
51 
52 // Any join is logically a loop. Hash joins just limit the domain of iteration,
53 // which can be as little as one element for one to one hash join, in which case
54 // we'll not generate IR for an actual loop.
55 class JoinLoop {
56  public:
57  using HoistedFiltersCallback = std::function<llvm::BasicBlock*(llvm::BasicBlock*,
58  llvm::BasicBlock*,
59  const std::string&,
60  llvm::Function*,
62 
63  JoinLoop(const JoinLoopKind,
64  const JoinType,
65  const std::function<JoinLoopDomain(const std::vector<llvm::Value*>&)>&
66  iteration_domain_codegen,
67  const std::function<llvm::Value*(const std::vector<llvm::Value*>&)>&
68  outer_condition_match,
69  const std::function<void(llvm::Value*)>& found_outer_matches,
70  const HoistedFiltersCallback& hoisted_filters,
71  const std::function<llvm::Value*(const std::vector<llvm::Value*>& prev_iters,
72  llvm::Value*)>& is_deleted,
73  const std::string& name = "");
74 
75  static llvm::BasicBlock* codegen(
76  const std::vector<JoinLoop>& join_loops,
77  const std::function<llvm::BasicBlock*(const std::vector<llvm::Value*>&)>&
78  body_codegen,
79  llvm::Value* outer_iter,
80  llvm::BasicBlock* exit_bb,
81  CgenState* cgen_state);
82 
83  JoinLoopKind kind() const { return kind_; }
84 
85  private:
86  static std::pair<llvm::BasicBlock*, llvm::Value*> evaluateOuterJoinCondition(
87  const JoinLoop& join_loop,
88  const JoinLoopDomain& iteration_domain,
89  const std::vector<llvm::Value*>& iterators,
90  llvm::Value* iteration_counter,
91  llvm::Value* have_more_inner_rows,
92  llvm::Value* found_an_outer_match_ptr,
93  llvm::Value* current_condition_match_ptr,
94  CgenState* cgen_state);
95 
97  // SQL type of the join.
98  const JoinType type_;
99  // Callback provided from the executor which generates the code for the given join
100  // domain of iteration.
101  const std::function<JoinLoopDomain(const std::vector<llvm::Value*>&)>
103  // Callback provided from the executor which generates true iff the outer condition
104  // evaluates to true.
105  const std::function<llvm::Value*(const std::vector<llvm::Value*>&)>
107  // Callback provided from the executor which receives the IR boolean value which tracks
108  // whether there are matches for the current iteration.
109  const std::function<void(llvm::Value*)> found_outer_matches_;
110  // Callback to hoist left hand side filters through the join, evaluating the filters
111  // prior to evaluating the join (but within the same kernel)
113  // Callback provided from the executor which returns if the current row (given by
114  // position) is deleted. The second argument is true iff the iteration isn't done yet.
115  // Useful for UpperBound and Set, which need to avoid fetching the deleted column from a
116  // past-the-end position. It's null for Singleton.
117  const std::function<llvm::Value*(const std::vector<llvm::Value*>& prev_iters,
118  llvm::Value*)>
120  const std::string name_;
121 };
JoinType
Definition: sqldefs.h:108
llvm::Value * element_count
Definition: JoinLoop.h:46
llvm::Value * values_buffer
Definition: JoinLoop.h:49
std::function< llvm::BasicBlock *(llvm::BasicBlock *, llvm::BasicBlock *, const std::string &, llvm::Function *, CgenState *)> HoistedFiltersCallback
Definition: JoinLoop.h:61
string name
Definition: setup.in.py:72
const std::function< llvm::Value *(const std::vector< llvm::Value * > &)> outer_condition_match_
Definition: JoinLoop.h:106
const JoinType type_
Definition: JoinLoop.h:98
const JoinLoopKind kind_
Definition: JoinLoop.h:96
const std::function< JoinLoopDomain(const std::vector< llvm::Value * > &)> iteration_domain_codegen_
Definition: JoinLoop.h:102
const std::function< void(llvm::Value *)> found_outer_matches_
Definition: JoinLoop.h:109
const std::string name_
Definition: JoinLoop.h:120
static llvm::BasicBlock * codegen(const std::vector< JoinLoop > &join_loops, const std::function< llvm::BasicBlock *(const std::vector< llvm::Value * > &)> &body_codegen, llvm::Value *outer_iter, llvm::BasicBlock *exit_bb, CgenState *cgen_state)
Definition: JoinLoop.cpp:48
JoinLoopKind kind() const
Definition: JoinLoop.h:83
llvm::Value * slot_lookup_result
Definition: JoinLoop.h:47
llvm::Value * upper_bound
Definition: JoinLoop.h:45
const std::function< llvm::Value *(const std::vector< llvm::Value * > &prev_iters, llvm::Value *)> is_deleted_
Definition: JoinLoop.h:119
JoinLoop(const JoinLoopKind, const JoinType, const std::function< JoinLoopDomain(const std::vector< llvm::Value * > &)> &iteration_domain_codegen, const std::function< llvm::Value *(const std::vector< llvm::Value * > &)> &outer_condition_match, const std::function< void(llvm::Value *)> &found_outer_matches, const HoistedFiltersCallback &hoisted_filters, const std::function< llvm::Value *(const std::vector< llvm::Value * > &prev_iters, llvm::Value *)> &is_deleted, const std::string &name="")
Definition: JoinLoop.cpp:25
JoinLoopKind
Definition: JoinLoop.h:31
const HoistedFiltersCallback hoisted_filters_
Definition: JoinLoop.h:112
static std::pair< llvm::BasicBlock *, llvm::Value * > evaluateOuterJoinCondition(const JoinLoop &join_loop, const JoinLoopDomain &iteration_domain, const std::vector< llvm::Value * > &iterators, llvm::Value *iteration_counter, llvm::Value *have_more_inner_rows, llvm::Value *found_an_outer_match_ptr, llvm::Value *current_condition_match_ptr, CgenState *cgen_state)
Definition: JoinLoop.cpp:285