OmniSciDB  340b00dbf6
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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 };
36 
37 // The domain of iteration for a join:
38 // 1. For loop join, from 0 to `upper_bound`.
39 // 2. For one-to-one joins, at most one value: `slot_lookup_result` if valid (greater than
40 // or equal to zero).
41 // 3. For one-to-many joins, the `element_count` values in `values_buffer`.
43  union {
44  llvm::Value* upper_bound; // for UpperBound
45  llvm::Value* element_count; // for Set
46  llvm::Value* slot_lookup_result; // for Singleton
47  };
48  llvm::Value* values_buffer; // used for Set
49 };
50 
51 // Any join is logically a loop. Hash joins just limit the domain of iteration,
52 // which can be as little as one element for one to one hash join, in which case
53 // we'll not generate IR for an actual loop.
54 class JoinLoop {
55  public:
56  JoinLoop(const JoinLoopKind,
57  const JoinType,
58  const std::function<JoinLoopDomain(const std::vector<llvm::Value*>&)>&,
59  const std::function<llvm::Value*(const std::vector<llvm::Value*>&)>&,
60  const std::function<void(llvm::Value*)>&,
61  const std::function<llvm::Value*(const std::vector<llvm::Value*>& prev_iters,
62  llvm::Value*)>&,
63  const std::string& name = "");
64 
65  static llvm::BasicBlock* codegen(
66  const std::vector<JoinLoop>& join_loops,
67  const std::function<llvm::BasicBlock*(const std::vector<llvm::Value*>&)>&
68  body_codegen,
69  llvm::Value* outer_iter,
70  llvm::BasicBlock* exit_bb,
71  CgenState* cgen_state);
72 
73  private:
74  static std::pair<llvm::BasicBlock*, llvm::Value*> evaluateOuterJoinCondition(
75  const JoinLoop& join_loop,
76  const JoinLoopDomain& iteration_domain,
77  const std::vector<llvm::Value*>& iterators,
78  llvm::Value* iteration_counter,
79  llvm::Value* have_more_inner_rows,
80  llvm::Value* found_an_outer_match_ptr,
81  llvm::Value* current_condition_match_ptr,
82  CgenState* cgen_state);
83 
85  // SQL type of the join.
86  const JoinType type_;
87  // Callback provided from the executor which generates the code for the given join
88  // domain of iteration.
89  const std::function<JoinLoopDomain(const std::vector<llvm::Value*>&)>
91  // Callback provided from the executor which generates true iff the outer condition
92  // evaluates to true.
93  const std::function<llvm::Value*(const std::vector<llvm::Value*>&)>
95  // Callback provided from the executor which receives the IR boolean value which tracks
96  // whether there are matches for the current iteration.
97  const std::function<void(llvm::Value*)> found_outer_matches_;
98  // Callback provided from the executor which returns if the current row (given by
99  // position) is deleted. The second argument is true iff the iteration isn't done yet.
100  // Useful for UpperBound and Set, which need to avoid fetching the deleted column from a
101  // past-the-end position. It's null for Singleton.
102  const std::function<llvm::Value*(const std::vector<llvm::Value*>& prev_iters,
103  llvm::Value*)>
105  const std::string name_;
106 };
JoinType
Definition: sqldefs.h:107
llvm::Value * element_count
Definition: JoinLoop.h:45
llvm::Value * values_buffer
Definition: JoinLoop.h:48
const std::function< llvm::Value *(const std::vector< llvm::Value * > &)> outer_condition_match_
Definition: JoinLoop.h:94
const JoinType type_
Definition: JoinLoop.h:86
const JoinLoopKind kind_
Definition: JoinLoop.h:84
const std::function< JoinLoopDomain(const std::vector< llvm::Value * > &)> iteration_domain_codegen_
Definition: JoinLoop.h:90
const std::function< void(llvm::Value *)> found_outer_matches_
Definition: JoinLoop.h:97
const std::string name_
Definition: JoinLoop.h:105
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:46
llvm::Value * slot_lookup_result
Definition: JoinLoop.h:46
llvm::Value * upper_bound
Definition: JoinLoop.h:44
const std::function< llvm::Value *(const std::vector< llvm::Value * > &prev_iters, llvm::Value *)> is_deleted_
Definition: JoinLoop.h:104
JoinLoop(const JoinLoopKind, const JoinType, const std::function< JoinLoopDomain(const std::vector< llvm::Value * > &)> &, const std::function< llvm::Value *(const std::vector< llvm::Value * > &)> &, const std::function< void(llvm::Value *)> &, const std::function< llvm::Value *(const std::vector< llvm::Value * > &prev_iters, llvm::Value *)> &, const std::string &name="")
Definition: JoinLoop.cpp:25
JoinLoopKind
Definition: JoinLoop.h:31
string name
Definition: setup.py:35
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:216