diff --git a/expressions/ExpressionFactories.cpp b/expressions/ExpressionFactories.cpp
index 871db50..cab99fd 100644
--- a/expressions/ExpressionFactories.cpp
+++ b/expressions/ExpressionFactories.cpp
@@ -52,6 +52,8 @@
 
 namespace quickstep {
 
+namespace S = serialization;
+
 class Type;
 
 Predicate* PredicateFactory::ReconstructFromProto(const serialization::Predicate &proto,
@@ -163,9 +165,22 @@
     case serialization::Scalar::ATTRIBUTE: {
       const relation_id rel_id = proto.GetExtension(serialization::ScalarAttribute::relation_id);
 
+      Scalar::JoinSide join_side;
+      switch (proto.GetExtension(S::ScalarAttribute::join_side)) {
+        case S::ScalarAttribute::NONE:
+          join_side = Scalar::kNone;
+          break;
+        case S::ScalarAttribute::LEFT_SIDE:
+          join_side = Scalar::kLeftSide;
+          break;
+        case S::ScalarAttribute::RIGHT_SIDE:
+          join_side = Scalar::kRightSide;
+          break;
+      }
+
       DCHECK(database.hasRelationWithId(rel_id));
       return new ScalarAttribute(*database.getRelationSchemaById(rel_id).getAttributeById(
-          proto.GetExtension(serialization::ScalarAttribute::attribute_id)));
+          proto.GetExtension(serialization::ScalarAttribute::attribute_id)), join_side);
     }
     case serialization::Scalar::UNARY_EXPRESSION: {
       return new ScalarUnaryExpression(
diff --git a/expressions/Expressions.proto b/expressions/Expressions.proto
index 8b4611e..aabb707 100644
--- a/expressions/Expressions.proto
+++ b/expressions/Expressions.proto
@@ -95,9 +95,16 @@
 }
 
 message ScalarAttribute {
+  enum JoinSide {
+    NONE = 0;
+    LEFT_SIDE = 1;
+    RIGHT_SIDE = 2;
+  }
+
   extend Scalar {
     optional int32 relation_id = 64;
     optional int32 attribute_id = 65;
+    optional JoinSide join_side = 66;
   }
 }
 
diff --git a/expressions/predicate/ComparisonPredicate.cpp b/expressions/predicate/ComparisonPredicate.cpp
index 2f7b84b..0417170 100644
--- a/expressions/predicate/ComparisonPredicate.cpp
+++ b/expressions/predicate/ComparisonPredicate.cpp
@@ -94,28 +94,22 @@
 
 bool ComparisonPredicate::matchesForJoinedTuples(
     const ValueAccessor &left_accessor,
-    const relation_id left_relation_id,
     const tuple_id left_tuple_id,
     const ValueAccessor &right_accessor,
-    const relation_id right_relation_id,
     const tuple_id right_tuple_id) const {
   if (fast_comparator_.get() == nullptr) {
     return static_result_;
-  } else {
-    return fast_comparator_->compareTypedValues(
-        left_operand_->getValueForJoinedTuples(left_accessor,
-                                               left_relation_id,
-                                               left_tuple_id,
-                                               right_accessor,
-                                               right_relation_id,
-                                               right_tuple_id),
-        right_operand_->getValueForJoinedTuples(left_accessor,
-                                                left_relation_id,
-                                                left_tuple_id,
-                                                right_accessor,
-                                                right_relation_id,
-                                                right_tuple_id));
   }
+
+  return fast_comparator_->compareTypedValues(
+      left_operand_->getValueForJoinedTuples(left_accessor,
+                                             left_tuple_id,
+                                             right_accessor,
+                                             right_tuple_id),
+      right_operand_->getValueForJoinedTuples(left_accessor,
+                                              left_tuple_id,
+                                              right_accessor,
+                                              right_tuple_id));
 }
 
 TupleIdSequence* ComparisonPredicate::getAllMatches(
diff --git a/expressions/predicate/ComparisonPredicate.hpp b/expressions/predicate/ComparisonPredicate.hpp
index 1ef2cb1..014e378 100644
--- a/expressions/predicate/ComparisonPredicate.hpp
+++ b/expressions/predicate/ComparisonPredicate.hpp
@@ -83,10 +83,8 @@
 
   bool matchesForJoinedTuples(
       const ValueAccessor &left_accessor,
-      const relation_id left_relation_id,
       const tuple_id left_tuple_id,
       const ValueAccessor &right_accessor,
-      const relation_id right_relation_id,
       const tuple_id right_tuple_id) const override;
 
   TupleIdSequence* getAllMatches(ValueAccessor *accessor,
diff --git a/expressions/predicate/ConjunctionPredicate.cpp b/expressions/predicate/ConjunctionPredicate.cpp
index 4f5cc77..39d9e58 100644
--- a/expressions/predicate/ConjunctionPredicate.cpp
+++ b/expressions/predicate/ConjunctionPredicate.cpp
@@ -85,10 +85,8 @@
 
 bool ConjunctionPredicate::matchesForJoinedTuples(
     const ValueAccessor &left_accessor,
-    const relation_id left_relation_id,
     const tuple_id left_tuple_id,
     const ValueAccessor &right_accessor,
-    const relation_id right_relation_id,
     const tuple_id right_tuple_id) const {
   if (has_static_result_) {
     return static_result_;
@@ -97,10 +95,8 @@
          it != dynamic_operand_list_.end();
          ++it) {
       if (!it->matchesForJoinedTuples(left_accessor,
-                                      left_relation_id,
                                       left_tuple_id,
                                       right_accessor,
-                                      right_relation_id,
                                       right_tuple_id)) {
         return false;
       }
diff --git a/expressions/predicate/ConjunctionPredicate.hpp b/expressions/predicate/ConjunctionPredicate.hpp
index b24036a..07148a7 100644
--- a/expressions/predicate/ConjunctionPredicate.hpp
+++ b/expressions/predicate/ConjunctionPredicate.hpp
@@ -63,10 +63,8 @@
 
   bool matchesForJoinedTuples(
       const ValueAccessor &left_accessor,
-      const relation_id left_relation_id,
       const tuple_id left_tuple_id,
       const ValueAccessor &right_accessor,
-      const relation_id right_relation_id,
       const tuple_id right_tuple_id) const override;
 
   TupleIdSequence* getAllMatches(ValueAccessor *accessor,
diff --git a/expressions/predicate/DisjunctionPredicate.cpp b/expressions/predicate/DisjunctionPredicate.cpp
index e117c99..4ac3bd7 100644
--- a/expressions/predicate/DisjunctionPredicate.cpp
+++ b/expressions/predicate/DisjunctionPredicate.cpp
@@ -85,10 +85,8 @@
 
 bool DisjunctionPredicate::matchesForJoinedTuples(
     const ValueAccessor &left_accessor,
-    const relation_id left_relation_id,
     const tuple_id left_tuple_id,
     const ValueAccessor &right_accessor,
-    const relation_id right_relation_id,
     const tuple_id right_tuple_id) const {
   if (has_static_result_) {
     return static_result_;
@@ -97,10 +95,8 @@
          it != dynamic_operand_list_.end();
          ++it) {
       if (it->matchesForJoinedTuples(left_accessor,
-                                     left_relation_id,
                                      left_tuple_id,
                                      right_accessor,
-                                     right_relation_id,
                                      right_tuple_id)) {
         return true;
       }
diff --git a/expressions/predicate/DisjunctionPredicate.hpp b/expressions/predicate/DisjunctionPredicate.hpp
index 2127573..2b237e6 100644
--- a/expressions/predicate/DisjunctionPredicate.hpp
+++ b/expressions/predicate/DisjunctionPredicate.hpp
@@ -63,10 +63,8 @@
 
   bool matchesForJoinedTuples(
       const ValueAccessor &left_accessor,
-      const relation_id left_relation_id,
       const tuple_id left_tuple_id,
       const ValueAccessor &right_accessor,
-      const relation_id right_relation_id,
       const tuple_id right_tuple_id) const override;
 
   TupleIdSequence* getAllMatches(ValueAccessor *accessor,
diff --git a/expressions/predicate/NegationPredicate.cpp b/expressions/predicate/NegationPredicate.cpp
index 92a8411..ad3238a 100644
--- a/expressions/predicate/NegationPredicate.cpp
+++ b/expressions/predicate/NegationPredicate.cpp
@@ -54,19 +54,15 @@
 
 bool NegationPredicate::matchesForJoinedTuples(
     const ValueAccessor &left_accessor,
-    const relation_id left_relation_id,
     const tuple_id left_tuple_id,
     const ValueAccessor &right_accessor,
-    const relation_id right_relation_id,
     const tuple_id right_tuple_id) const {
   if (has_static_result_) {
     return static_result_;
   } else {
     return !(operand_->matchesForJoinedTuples(left_accessor,
-                                              left_relation_id,
                                               left_tuple_id,
                                               right_accessor,
-                                              right_relation_id,
                                               right_tuple_id));
   }
 }
diff --git a/expressions/predicate/NegationPredicate.hpp b/expressions/predicate/NegationPredicate.hpp
index ec005ea..7afcf1c 100644
--- a/expressions/predicate/NegationPredicate.hpp
+++ b/expressions/predicate/NegationPredicate.hpp
@@ -91,10 +91,8 @@
 
   bool matchesForJoinedTuples(
       const ValueAccessor &left_accessor,
-      const relation_id left_relation_id,
       const tuple_id left_tuple_id,
       const ValueAccessor &right_accessor,
-      const relation_id right_relation_id,
       const tuple_id right_tuple_id) const override;
 
   TupleIdSequence* getAllMatches(ValueAccessor *accessor,
diff --git a/expressions/predicate/Predicate.hpp b/expressions/predicate/Predicate.hpp
index df04644..31fbb9a 100644
--- a/expressions/predicate/Predicate.hpp
+++ b/expressions/predicate/Predicate.hpp
@@ -123,15 +123,11 @@
    * @param left_accessor The ValueAccessor that the first of the joined tuples
    *        will be read from (this does NOT necessarily correspond to the left
    *        operand of a binary operation).
-   * @param left_relation_id The ID of the relation that left_accessor provides
-   *        access to.
    * @param left_tuple_id The ID of the tuple (the absolute position) from
    *        left_accessor to evaluate this Predicate for.
    * @param right_accessor The ValueAccessor that the second of the joined
    *        tuples will be read from (this does NOT necessarily correspond to
    *        the right operand of a binary operation).
-   * @param right_relation_id The ID of the relation that right_accessor
-   *        provides access to.
    * @param right_tuple_id The ID of the tuple (the absolute position) from
    *        right_accessor to evaluate this Predicate for.
    * @return Whether this predicate is true for the given tuples.
@@ -144,10 +140,8 @@
   // a smallish set of matches from a hash-join by a residual predicate).
   virtual bool matchesForJoinedTuples(
       const ValueAccessor &left_accessor,
-      const relation_id left_relation_id,
       const tuple_id left_tuple_id,
       const ValueAccessor &right_accessor,
-      const relation_id right_relation_id,
       const tuple_id right_tuple_id) const = 0;
 
   /**
diff --git a/expressions/predicate/TrivialPredicates.hpp b/expressions/predicate/TrivialPredicates.hpp
index 4e44976..e313cd5 100644
--- a/expressions/predicate/TrivialPredicates.hpp
+++ b/expressions/predicate/TrivialPredicates.hpp
@@ -84,10 +84,8 @@
 
   bool matchesForJoinedTuples(
       const ValueAccessor &left_accessor,
-      const relation_id left_relation_id,
       const tuple_id left_tuple_id,
       const ValueAccessor &right_accessor,
-      const relation_id right_relation_id,
       const tuple_id right_tuple_id) const override {
     return true;
   }
@@ -137,10 +135,8 @@
 
   bool matchesForJoinedTuples(
       const ValueAccessor &left_accessor,
-      const relation_id left_relation_id,
       const tuple_id left_tuple_id,
       const ValueAccessor &right_accessor,
-      const relation_id right_relation_id,
       const tuple_id right_tuple_id) const override {
     return false;
   }
diff --git a/expressions/scalar/Scalar.hpp b/expressions/scalar/Scalar.hpp
index 6e482c2..0c1cba1 100644
--- a/expressions/scalar/Scalar.hpp
+++ b/expressions/scalar/Scalar.hpp
@@ -51,6 +51,15 @@
 class Scalar : public Expression {
  public:
   /**
+   * @brief The possible binary join side of Scalar values.
+   **/
+  enum JoinSide {
+    kNone = 0,
+    kLeftSide,
+    kRightSide
+  };
+
+  /**
    * @brief The possible provenance of Scalar values.
    **/
   enum ScalarDataSource {
@@ -128,28 +137,35 @@
    * @param left_accessor The ValueAccessor that the first of the joined
    *        tuples can be read from (this does NOT necessarily correspond to
    *        the left operand of a binary operation).
-   * @param left_relation_id The ID of the relation that left_tuple_store
-   *        belongs to.
    * @param left_tuple_id The ID of the tuple in left_tuple_store to evaluate
    *        this Scalar for.
    * @param right_accessor The ValueAccessor that the second of the joined
    *        tuples can be read from (this does NOT necessarily correspond to
    *        the right operand of a binary operation).
-   * @param right_relation_id The ID of the relation that right_tuple_store
-   *        belongs to.
    * @param right_tuple_id The ID of the tuple in right_tuple_store to evaluate
    *        this Scalar for.
    * @return The value of this scalar for the given tuples.
    **/
   virtual TypedValue getValueForJoinedTuples(
       const ValueAccessor &left_accessor,
-      const relation_id left_relation_id,
       const tuple_id left_tuple_id,
       const ValueAccessor &right_accessor,
-      const relation_id right_relation_id,
       const tuple_id right_tuple_id) const = 0;
 
   /**
+   * @brief If it is possible to get this Scalar's values directly from a
+   *        ValueAccessor, return the binary join side of the ValueAccessor
+   *        should belong to.
+   *
+   * @return The binary join side for ValueAccessors that can directly produce
+   *         this Scalar's values, or kNone if values can not be obtained
+   *         directly from a ValueAccessor.
+   **/
+  JoinSide join_side() const {
+    return join_side_;
+  }
+
+  /**
    * @brief Determine whether this Scalar's value is static (i.e. whether it is
    *        the same regardless of tuple).
    *
@@ -181,19 +197,6 @@
   }
 
   /**
-   * @brief If it is possible to get this Scalar's values directly from a
-   *        ValueAccessor, return the ID of the relation that such a
-   *        ValueAccessor should belong to.
-   *
-   * @return The relation_id for ValueAccessors that can directly produce this
-   *         Scalar's values, or -1 if values can not be obtained directly from
-   *         a ValueAccessor.
-   **/
-  virtual relation_id getRelationIdForValueAccessor() const {
-    return -1;
-  }
-
-  /**
    * @brief Get this Scalar's values for all tuples accesible via a
    *        ValueAccessor.
    *
@@ -217,10 +220,8 @@
    * @brief Get this Scalar's value for all specified joined tuples from two
    *        ValueAccessors.
    *
-   * @param left_relation_id The ID of the left relation in the join.
    * @param left_accessor A ValueAccessor which will be used to access tuples
    *        from the left relation.
-   * @param right_relation_id The ID of the right relation in the join.
    * @param right_accessor A ValueAccessor which will be used to access tuples
    *        from the right relation.
    * @param joined_tuple_ids A series of pairs of tuple ids from the left and
@@ -231,9 +232,7 @@
    *         specified by joined_tuple_ids.
    **/
   virtual ColumnVectorPtr getAllValuesForJoin(
-      const relation_id left_relation_id,
       ValueAccessor *left_accessor,
-      const relation_id right_relation_id,
       ValueAccessor *right_accessor,
       const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
       ColumnVectorCache *cv_cache) const = 0;
@@ -247,10 +246,11 @@
       std::vector<std::string> *container_child_field_names,
       std::vector<std::vector<const Expression*>> *container_child_fields) const override;
 
-  explicit Scalar(const Type &type)
-      : Expression(), type_(type) {}
+  explicit Scalar(const Type &type, const JoinSide join_side = kNone)
+      : Expression(), type_(type), join_side_(join_side) {}
 
   const Type &type_;
+  const JoinSide join_side_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(Scalar);
diff --git a/expressions/scalar/ScalarAttribute.cpp b/expressions/scalar/ScalarAttribute.cpp
index 944dc35..8a75bb0 100644
--- a/expressions/scalar/ScalarAttribute.cpp
+++ b/expressions/scalar/ScalarAttribute.cpp
@@ -28,6 +28,7 @@
 #include "catalog/CatalogRelationSchema.hpp"
 #include "catalog/CatalogTypedefs.hpp"
 #include "expressions/Expressions.pb.h"
+#include "expressions/scalar/Scalar.hpp"
 #include "storage/StorageBlockInfo.hpp"
 #include "storage/ValueAccessor.hpp"
 #include "storage/ValueAccessorUtil.hpp"
@@ -40,8 +41,11 @@
 
 namespace quickstep {
 
-ScalarAttribute::ScalarAttribute(const CatalogAttribute &attribute)
-    : Scalar(attribute.getType()),
+namespace S = serialization;
+
+ScalarAttribute::ScalarAttribute(const CatalogAttribute &attribute,
+                                 const JoinSide join_side)
+    : Scalar(attribute.getType(), join_side),
       attribute_(attribute) {
 }
 
@@ -51,11 +55,25 @@
   proto.SetExtension(serialization::ScalarAttribute::relation_id, attribute_.getParent().getID());
   proto.SetExtension(serialization::ScalarAttribute::attribute_id, attribute_.getID());
 
+  S::ScalarAttribute::JoinSide join_side_proto;
+  switch (join_side_) {
+    case kNone:
+      join_side_proto = S::ScalarAttribute::NONE;
+      break;
+    case kLeftSide:
+      join_side_proto = S::ScalarAttribute::LEFT_SIDE;
+      break;
+    case kRightSide:
+      join_side_proto = S::ScalarAttribute::RIGHT_SIDE;
+      break;
+  }
+  proto.SetExtension(S::ScalarAttribute::join_side, join_side_proto);
+
   return proto;
 }
 
 Scalar* ScalarAttribute::clone() const {
-  return new ScalarAttribute(attribute_);
+  return new ScalarAttribute(attribute_, join_side_);
 }
 
 TypedValue ScalarAttribute::getValueForSingleTuple(const ValueAccessor &accessor,
@@ -65,18 +83,16 @@
 
 TypedValue ScalarAttribute::getValueForJoinedTuples(
     const ValueAccessor &left_accessor,
-    const relation_id left_relation_id,
     const tuple_id left_tuple_id,
     const ValueAccessor &right_accessor,
-    const relation_id right_relation_id,
     const tuple_id right_tuple_id) const {
-  // FIXME(chasseur): This can get confused and break for self-joins.
-  DCHECK((attribute_.getParent().getID() == left_relation_id)
-         || (attribute_.getParent().getID() == right_relation_id));
-  if (attribute_.getParent().getID() == left_relation_id) {
+  DCHECK(join_side_ != kNone);
+
+  if (join_side_ == kLeftSide) {
     return left_accessor.getTypedValueAtAbsolutePositionVirtual(attribute_.getID(),
                                                                 left_tuple_id);
   } else {
+    DCHECK(join_side_ == kRightSide);
     return right_accessor.getTypedValueAtAbsolutePositionVirtual(attribute_.getID(),
                                                                  right_tuple_id);
   }
@@ -86,10 +102,6 @@
   return attribute_.getID();
 }
 
-relation_id ScalarAttribute::getRelationIdForValueAccessor() const {
-  return attribute_.getParent().getID();
-}
-
 ColumnVectorPtr ScalarAttribute::getAllValues(
     ValueAccessor *accessor,
     const SubBlocksReference *sub_blocks_ref,
@@ -157,19 +169,16 @@
 }
 
 ColumnVectorPtr ScalarAttribute::getAllValuesForJoin(
-    const relation_id left_relation_id,
     ValueAccessor *left_accessor,
-    const relation_id right_relation_id,
     ValueAccessor *right_accessor,
     const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
     ColumnVectorCache *cv_cache) const {
-  DCHECK((attribute_.getParent().getID() == left_relation_id)
-         || (attribute_.getParent().getID() == right_relation_id));
+  DCHECK(join_side_ != kNone);
 
   const attribute_id attr_id = attribute_.getID();
   const Type &result_type = attribute_.getType();
 
-  const bool using_left_relation = (attribute_.getParent().getID() == left_relation_id);
+  const bool using_left_relation = (join_side_ == kLeftSide);
   ValueAccessor *accessor = using_left_relation ? left_accessor
                                                 : right_accessor;
 
@@ -232,6 +241,19 @@
 
   inline_field_names->emplace_back("attribute");
   inline_field_values->emplace_back(std::to_string(attribute_.getID()));
+
+  switch (join_side_) {
+    case kNone:
+      break;
+    case kLeftSide:
+      inline_field_names->emplace_back("join_side");
+      inline_field_values->push_back("left_side");
+      break;
+    case kRightSide:
+      inline_field_names->emplace_back("join_side");
+      inline_field_values->push_back("right_side");
+      break;
+  }
 }
 
 }  // namespace quickstep
diff --git a/expressions/scalar/ScalarAttribute.hpp b/expressions/scalar/ScalarAttribute.hpp
index 4d30fe9..cd718c8 100644
--- a/expressions/scalar/ScalarAttribute.hpp
+++ b/expressions/scalar/ScalarAttribute.hpp
@@ -53,8 +53,10 @@
    * @brief Constructor.
    *
    * @param attribute The attribute to use.
+   * @param join_side The join side of which this attribute belongs to.
    **/
-  explicit ScalarAttribute(const CatalogAttribute &attribute);
+  explicit ScalarAttribute(const CatalogAttribute &attribute,
+                           const JoinSide join_side = kNone);
 
   serialization::Scalar getProto() const override;
 
@@ -69,24 +71,18 @@
 
   TypedValue getValueForJoinedTuples(
       const ValueAccessor &left_accessor,
-      const relation_id left_relation_id,
       const tuple_id left_tuple_id,
       const ValueAccessor &right_accessor,
-      const relation_id right_relation_id,
       const tuple_id right_tuple_id) const override;
 
   attribute_id getAttributeIdForValueAccessor() const override;
 
-  relation_id getRelationIdForValueAccessor() const override;
-
   ColumnVectorPtr getAllValues(ValueAccessor *accessor,
                                const SubBlocksReference *sub_blocks_ref,
                                ColumnVectorCache *cv_cache) const override;
 
   ColumnVectorPtr getAllValuesForJoin(
-      const relation_id left_relation_id,
       ValueAccessor *left_accessor,
-      const relation_id right_relation_id,
       ValueAccessor *right_accessor,
       const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
       ColumnVectorCache *cv_cache) const override;
diff --git a/expressions/scalar/ScalarBinaryExpression.cpp b/expressions/scalar/ScalarBinaryExpression.cpp
index b3568f8..ecbe84f 100644
--- a/expressions/scalar/ScalarBinaryExpression.cpp
+++ b/expressions/scalar/ScalarBinaryExpression.cpp
@@ -79,26 +79,20 @@
 
 TypedValue ScalarBinaryExpression::getValueForJoinedTuples(
     const ValueAccessor &left_accessor,
-    const relation_id left_relation_id,
     const tuple_id left_tuple_id,
     const ValueAccessor &right_accessor,
-    const relation_id right_relation_id,
     const tuple_id right_tuple_id) const {
   if (fast_operator_.get() == nullptr) {
     return static_value_.makeReferenceToThis();
   } else {
     return fast_operator_->applyToTypedValues(
         left_operand_->getValueForJoinedTuples(left_accessor,
-                                               left_relation_id,
                                                left_tuple_id,
                                                right_accessor,
-                                               right_relation_id,
                                                right_tuple_id),
         right_operand_->getValueForJoinedTuples(left_accessor,
-                                                left_relation_id,
                                                 left_tuple_id,
                                                 right_accessor,
-                                                right_relation_id,
                                                 right_tuple_id));
   }
 }
@@ -199,9 +193,7 @@
 }
 
 ColumnVectorPtr ScalarBinaryExpression::getAllValuesForJoin(
-    const relation_id left_relation_id,
     ValueAccessor *left_accessor,
-    const relation_id right_relation_id,
     ValueAccessor *right_accessor,
     const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
     ColumnVectorCache *cv_cache) const {
@@ -216,12 +208,9 @@
       const attribute_id right_operand_attr_id
           = right_operand_->getAttributeIdForValueAccessor();
       if (right_operand_attr_id != -1) {
-        const relation_id right_operand_relation_id
-            = right_operand_->getRelationIdForValueAccessor();
-        DCHECK_NE(right_operand_relation_id, -1);
-        DCHECK((right_operand_relation_id == left_relation_id)
-               || (right_operand_relation_id == right_relation_id));
-        const bool using_left_relation = (right_operand_relation_id == left_relation_id);
+        const JoinSide join_side = right_operand_->join_side();
+        DCHECK(join_side != kNone);
+        const bool using_left_relation = (join_side == kLeftSide);
         ValueAccessor *right_operand_accessor = using_left_relation ? left_accessor
                                                                     : right_accessor;
         return ColumnVectorPtr(
@@ -235,9 +224,7 @@
 #endif  // QUICKSTEP_ENABLE_VECTOR_COPY_ELISION_JOIN
 
       ColumnVectorPtr right_result(
-          right_operand_->getAllValuesForJoin(left_relation_id,
-                                              left_accessor,
-                                              right_relation_id,
+          right_operand_->getAllValuesForJoin(left_accessor,
                                               right_accessor,
                                               joined_tuple_ids,
                                               cv_cache));
@@ -250,12 +237,9 @@
       const attribute_id left_operand_attr_id
           = left_operand_->getAttributeIdForValueAccessor();
       if (left_operand_attr_id != -1) {
-        const relation_id left_operand_relation_id
-            = left_operand_->getRelationIdForValueAccessor();
-        DCHECK_NE(left_operand_relation_id, -1);
-        DCHECK((left_operand_relation_id == left_relation_id)
-               || (left_operand_relation_id == right_relation_id));
-        const bool using_left_relation = (left_operand_relation_id == left_relation_id);
+        const JoinSide join_side = left_operand_->join_side();
+        DCHECK(join_side != kNone);
+        const bool using_left_relation = (join_side == kLeftSide);
         ValueAccessor *left_operand_accessor = using_left_relation ? left_accessor
                                                                    : right_accessor;
         return ColumnVectorPtr(
@@ -269,9 +253,7 @@
 #endif  // QUICKSTEP_ENABLE_VECTOR_COPY_ELISION_JOIN
 
       ColumnVectorPtr left_result(
-          left_operand_->getAllValuesForJoin(left_relation_id,
-                                             left_accessor,
-                                             right_relation_id,
+          left_operand_->getAllValuesForJoin(left_accessor,
                                              right_accessor,
                                              joined_tuple_ids,
                                              cv_cache));
@@ -286,25 +268,17 @@
       const attribute_id right_operand_attr_id
           = right_operand_->getAttributeIdForValueAccessor();
       if (left_operand_attr_id != -1) {
-        const relation_id left_operand_relation_id
-            = left_operand_->getRelationIdForValueAccessor();
-        DCHECK_NE(left_operand_relation_id, -1);
-        DCHECK((left_operand_relation_id == left_relation_id)
-               || (left_operand_relation_id == right_relation_id));
-        const bool using_left_relation_for_left_operand
-            = (left_operand_relation_id == left_relation_id);
+        const JoinSide join_side = left_operand_->join_side();
+        DCHECK(join_side != kNone);
+        const bool using_left_relation_for_left_operand = (join_side == kLeftSide);
         ValueAccessor *left_operand_accessor = using_left_relation_for_left_operand ? left_accessor
                                                                                     : right_accessor;
 
 #ifdef QUICKSTEP_ENABLE_VECTOR_COPY_ELISION_JOIN_WITH_BINARY_EXPRESSIONS
         if (right_operand_attr_id != -1) {
-          const relation_id right_operand_relation_id
-              = right_operand_->getRelationIdForValueAccessor();
-          DCHECK_NE(right_operand_relation_id, -1);
-          DCHECK((right_operand_relation_id == left_relation_id)
-                 || (right_operand_relation_id == right_relation_id));
-          const bool using_left_relation_for_right_operand
-              = (right_operand_relation_id == left_relation_id);
+          const JoinSide join_side = right_operand_->join_side();
+          DCHECK(join_side != kNone);
+          const bool using_left_relation_for_right_operand = (join_side == kLeftSide);
           ValueAccessor *right_operand_accessor = using_left_relation_for_right_operand ? left_accessor
                                                                                         : right_accessor;
           return ColumnVectorPtr(
@@ -318,9 +292,7 @@
         }
 #endif  // QUICKSTEP_ENABLE_VECTOR_COPY_ELISION_JOIN_WITH_BINARY_EXPRESSIONS
         ColumnVectorPtr right_result(
-            right_operand_->getAllValuesForJoin(left_relation_id,
-                                                left_accessor,
-                                                right_relation_id,
+            right_operand_->getAllValuesForJoin(left_accessor,
                                                 right_accessor,
                                                 joined_tuple_ids,
                                                 cv_cache));
@@ -333,20 +305,14 @@
                 *right_result,
                 joined_tuple_ids));
       } else if (right_operand_attr_id != -1) {
-        const relation_id right_operand_relation_id
-            = right_operand_->getRelationIdForValueAccessor();
-        DCHECK_NE(right_operand_relation_id, -1);
-        DCHECK((right_operand_relation_id == left_relation_id)
-               || (right_operand_relation_id == right_relation_id));
-        const bool using_left_relation_for_right_operand
-            = (right_operand_relation_id == left_relation_id);
+        const JoinSide join_side = right_operand_->join_side();
+        DCHECK(join_side != kNone);
+        const bool using_left_relation_for_right_operand = (join_side == kLeftSide);
         ValueAccessor *right_operand_accessor = using_left_relation_for_right_operand ? left_accessor
                                                                                       : right_accessor;
 
         ColumnVectorPtr left_result(
-            left_operand_->getAllValuesForJoin(left_relation_id,
-                                               left_accessor,
-                                               right_relation_id,
+            left_operand_->getAllValuesForJoin(left_accessor,
                                                right_accessor,
                                                joined_tuple_ids,
                                                cv_cache));
@@ -361,16 +327,12 @@
 #endif  // QUICKSTEP_ENABLE_VECTOR_COPY_ELISION_JOIN
 
       ColumnVectorPtr left_result(
-          left_operand_->getAllValuesForJoin(left_relation_id,
-                                             left_accessor,
-                                             right_relation_id,
+          left_operand_->getAllValuesForJoin(left_accessor,
                                              right_accessor,
                                              joined_tuple_ids,
                                              cv_cache));
       ColumnVectorPtr right_result(
-          right_operand_->getAllValuesForJoin(left_relation_id,
-                                              left_accessor,
-                                              right_relation_id,
+          right_operand_->getAllValuesForJoin(left_accessor,
                                               right_accessor,
                                               joined_tuple_ids,
                                               cv_cache));
diff --git a/expressions/scalar/ScalarBinaryExpression.hpp b/expressions/scalar/ScalarBinaryExpression.hpp
index 4ac1f62..6f9c41d 100644
--- a/expressions/scalar/ScalarBinaryExpression.hpp
+++ b/expressions/scalar/ScalarBinaryExpression.hpp
@@ -84,10 +84,8 @@
 
   TypedValue getValueForJoinedTuples(
       const ValueAccessor &left_accessor,
-      const relation_id left_relation_id,
       const tuple_id left_tuple_id,
       const ValueAccessor &right_accessor,
-      const relation_id right_relation_id,
       const tuple_id right_tuple_id) const override;
 
   bool hasStaticValue() const override {
@@ -104,9 +102,7 @@
                                ColumnVectorCache *cv_cache) const override;
 
   ColumnVectorPtr getAllValuesForJoin(
-      const relation_id left_relation_id,
       ValueAccessor *left_accessor,
-      const relation_id right_relation_id,
       ValueAccessor *right_accessor,
       const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
       ColumnVectorCache *cv_cache) const override;
diff --git a/expressions/scalar/ScalarCaseExpression.cpp b/expressions/scalar/ScalarCaseExpression.cpp
index c2af83b..39e19c6 100644
--- a/expressions/scalar/ScalarCaseExpression.cpp
+++ b/expressions/scalar/ScalarCaseExpression.cpp
@@ -247,47 +247,27 @@
 
 TypedValue ScalarCaseExpression::getValueForJoinedTuples(
     const ValueAccessor &left_accessor,
-    const relation_id left_relation_id,
     const tuple_id left_tuple_id,
     const ValueAccessor &right_accessor,
-    const relation_id right_relation_id,
     const tuple_id right_tuple_id) const {
   if (has_static_value_) {
     return static_value_.makeReferenceToThis();
   } else if (fixed_result_expression_ != nullptr) {
-    return fixed_result_expression_->getValueForJoinedTuples(left_accessor,
-                                                             left_relation_id,
-                                                             left_tuple_id,
-                                                             right_accessor,
-                                                             right_relation_id,
-                                                             right_tuple_id);
+    return fixed_result_expression_->getValueForJoinedTuples(
+        left_accessor, left_tuple_id, right_accessor, right_tuple_id);
   }
 
   for (std::vector<std::unique_ptr<Predicate>>::size_type case_idx = 0;
        case_idx < when_predicates_.size();
        ++case_idx) {
-    if (when_predicates_[case_idx]->matchesForJoinedTuples(left_accessor,
-                                                           left_relation_id,
-                                                           left_tuple_id,
-                                                           right_accessor,
-                                                           right_relation_id,
-                                                           right_tuple_id)) {
+    if (when_predicates_[case_idx]->matchesForJoinedTuples(
+            left_accessor, left_tuple_id, right_accessor, right_tuple_id)) {
       return result_expressions_[case_idx]->getValueForJoinedTuples(
-          left_accessor,
-          left_relation_id,
-          left_tuple_id,
-          right_accessor,
-          right_relation_id,
-          right_tuple_id);
+          left_accessor, left_tuple_id, right_accessor, right_tuple_id);
     }
   }
   return else_result_expression_->getValueForJoinedTuples(
-      left_accessor,
-      left_relation_id,
-      left_tuple_id,
-      right_accessor,
-      right_relation_id,
-      right_tuple_id);
+      left_accessor, left_tuple_id, right_accessor, right_tuple_id);
 }
 
 ColumnVectorPtr ScalarCaseExpression::getAllValues(
@@ -370,9 +350,7 @@
 }
 
 ColumnVectorPtr ScalarCaseExpression::getAllValuesForJoin(
-    const relation_id left_relation_id,
     ValueAccessor *left_accessor,
-    const relation_id right_relation_id,
     ValueAccessor *right_accessor,
     const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
     ColumnVectorCache *cv_cache) const {
@@ -381,9 +359,7 @@
         ColumnVector::MakeVectorOfValue(type_, static_value_, joined_tuple_ids.size()));
   } else if (fixed_result_expression_) {
     return fixed_result_expression_->getAllValuesForJoin(
-        left_relation_id, left_accessor,
-        right_relation_id, right_accessor,
-        joined_tuple_ids, cv_cache);
+        left_accessor, right_accessor, joined_tuple_ids, cv_cache);
   }
 
   // Slice 'joined_tuple_ids' apart by case.
@@ -418,13 +394,9 @@
 
     const Predicate &case_predicate = *when_predicates_[case_idx];
     for (tuple_id pos : else_positions) {
-      const std::pair<tuple_id, tuple_id> check_pair = joined_tuple_ids[pos];
-      if (case_predicate.matchesForJoinedTuples(*left_accessor,
-                                                left_relation_id,
-                                                check_pair.first,
-                                                *right_accessor,
-                                                right_relation_id,
-                                                check_pair.second)) {
+      const std::pair<tuple_id, tuple_id> &check_pair = joined_tuple_ids[pos];
+      if (case_predicate.matchesForJoinedTuples(
+              *left_accessor, check_pair.first, *right_accessor, check_pair.second)) {
         current_case_positions->set(pos);
         current_case_matches.emplace_back(check_pair);
       }
@@ -439,12 +411,7 @@
        case_idx < case_matches.size();
        ++case_idx) {
     case_results.emplace_back(result_expressions_[case_idx]->getAllValuesForJoin(
-        left_relation_id,
-        left_accessor,
-        right_relation_id,
-        right_accessor,
-        case_matches[case_idx],
-        cv_cache));
+        left_accessor, right_accessor, case_matches[case_idx], cv_cache));
   }
 
   ColumnVectorPtr else_results;
@@ -455,12 +422,7 @@
     }
 
     else_results = else_result_expression_->getAllValuesForJoin(
-        left_relation_id,
-        left_accessor,
-        right_relation_id,
-        right_accessor,
-        else_matches,
-        cv_cache);
+        left_accessor, right_accessor, else_matches, cv_cache);
   }
 
   // Multiplex per-case results into a single ColumnVector with values in the
diff --git a/expressions/scalar/ScalarCaseExpression.hpp b/expressions/scalar/ScalarCaseExpression.hpp
index 22acfa8..14a2666 100644
--- a/expressions/scalar/ScalarCaseExpression.hpp
+++ b/expressions/scalar/ScalarCaseExpression.hpp
@@ -101,10 +101,8 @@
 
   TypedValue getValueForJoinedTuples(
       const ValueAccessor &left_accessor,
-      const relation_id left_relation_id,
       const tuple_id left_tuple_id,
       const ValueAccessor &right_accessor,
-      const relation_id right_relation_id,
       const tuple_id right_tuple_id) const override;
 
   bool hasStaticValue() const override {
@@ -129,9 +127,7 @@
                                ColumnVectorCache *cv_cache) const override;
 
   ColumnVectorPtr getAllValuesForJoin(
-      const relation_id left_relation_id,
       ValueAccessor *left_accessor,
-      const relation_id right_relation_id,
       ValueAccessor *right_accessor,
       const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
       ColumnVectorCache *cv_cache) const override;
diff --git a/expressions/scalar/ScalarLiteral.cpp b/expressions/scalar/ScalarLiteral.cpp
index 808953d..b5f5d17 100644
--- a/expressions/scalar/ScalarLiteral.cpp
+++ b/expressions/scalar/ScalarLiteral.cpp
@@ -59,9 +59,7 @@
 }
 
 ColumnVectorPtr ScalarLiteral::getAllValuesForJoin(
-    const relation_id left_relation_id,
     ValueAccessor *left_accessor,
-    const relation_id right_relation_id,
     ValueAccessor *right_accessor,
     const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
     ColumnVectorCache *cv_cache) const {
diff --git a/expressions/scalar/ScalarLiteral.hpp b/expressions/scalar/ScalarLiteral.hpp
index 2a4c396..3b3b994 100644
--- a/expressions/scalar/ScalarLiteral.hpp
+++ b/expressions/scalar/ScalarLiteral.hpp
@@ -87,10 +87,8 @@
 
   TypedValue getValueForJoinedTuples(
       const ValueAccessor &left_accessor,
-      const relation_id left_relation_id,
       const tuple_id left_tuple_id,
       const ValueAccessor &right_accessor,
-      const relation_id right_relation_id,
       const tuple_id right_tuple_id) const override {
     return internal_literal_.makeReferenceToThis();
   }
@@ -108,9 +106,7 @@
                                ColumnVectorCache *cv_cache) const override;
 
   ColumnVectorPtr getAllValuesForJoin(
-      const relation_id left_relation_id,
       ValueAccessor *left_accessor,
-      const relation_id right_relation_id,
       ValueAccessor *right_accessor,
       const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
       ColumnVectorCache *cv_cache) const override;
diff --git a/expressions/scalar/ScalarSharedExpression.cpp b/expressions/scalar/ScalarSharedExpression.cpp
index e301116..64bfb3f 100644
--- a/expressions/scalar/ScalarSharedExpression.cpp
+++ b/expressions/scalar/ScalarSharedExpression.cpp
@@ -55,16 +55,12 @@
 
 TypedValue ScalarSharedExpression::getValueForJoinedTuples(
     const ValueAccessor &left_accessor,
-    const relation_id left_relation_id,
     const tuple_id left_tuple_id,
     const ValueAccessor &right_accessor,
-    const relation_id right_relation_id,
     const tuple_id right_tuple_id) const {
   return operand_->getValueForJoinedTuples(left_accessor,
-                                           left_relation_id,
                                            left_tuple_id,
                                            right_accessor,
-                                           right_relation_id,
                                            right_tuple_id);
 }
 
@@ -87,16 +83,12 @@
 }
 
 ColumnVectorPtr ScalarSharedExpression::getAllValuesForJoin(
-    const relation_id left_relation_id,
     ValueAccessor *left_accessor,
-    const relation_id right_relation_id,
     ValueAccessor *right_accessor,
     const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
     ColumnVectorCache *cv_cache) const {
   if (cv_cache == nullptr) {
-    return operand_->getAllValuesForJoin(left_relation_id,
-                                         left_accessor,
-                                         right_relation_id,
+    return operand_->getAllValuesForJoin(left_accessor,
                                          right_accessor,
                                          joined_tuple_ids,
                                          cv_cache);
@@ -106,9 +98,7 @@
   if (cv_cache->contains(share_id_)) {
     result = cv_cache->get(share_id_);
   } else {
-    result = operand_->getAllValuesForJoin(left_relation_id,
-                                           left_accessor,
-                                           right_relation_id,
+    result = operand_->getAllValuesForJoin(left_accessor,
                                            right_accessor,
                                            joined_tuple_ids,
                                            cv_cache);
diff --git a/expressions/scalar/ScalarSharedExpression.hpp b/expressions/scalar/ScalarSharedExpression.hpp
index f39c45b..ba9f32e 100644
--- a/expressions/scalar/ScalarSharedExpression.hpp
+++ b/expressions/scalar/ScalarSharedExpression.hpp
@@ -83,10 +83,8 @@
 
   TypedValue getValueForJoinedTuples(
       const ValueAccessor &left_accessor,
-      const relation_id left_relation_id,
       const tuple_id left_tuple_id,
       const ValueAccessor &right_accessor,
-      const relation_id right_relation_id,
       const tuple_id right_tuple_id) const override;
 
   bool hasStaticValue() const override {
@@ -102,9 +100,7 @@
                                ColumnVectorCache *cv_cache) const override;
 
   ColumnVectorPtr getAllValuesForJoin(
-      const relation_id left_relation_id,
       ValueAccessor *left_accessor,
-      const relation_id right_relation_id,
       ValueAccessor *right_accessor,
       const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
       ColumnVectorCache *cv_cache) const override;
diff --git a/expressions/scalar/ScalarUnaryExpression.cpp b/expressions/scalar/ScalarUnaryExpression.cpp
index c51e38f..be47d43 100644
--- a/expressions/scalar/ScalarUnaryExpression.cpp
+++ b/expressions/scalar/ScalarUnaryExpression.cpp
@@ -76,19 +76,15 @@
 
 TypedValue ScalarUnaryExpression::getValueForJoinedTuples(
     const ValueAccessor &left_accessor,
-    const relation_id left_relation_id,
     const tuple_id left_tuple_id,
     const ValueAccessor &right_accessor,
-    const relation_id right_relation_id,
     const tuple_id right_tuple_id) const {
   if (fast_operator_.get() == nullptr) {
     return static_value_.makeReferenceToThis();
   } else {
     return fast_operator_->applyToTypedValue(operand_->getValueForJoinedTuples(left_accessor,
-                                                                               left_relation_id,
                                                                                left_tuple_id,
                                                                                right_accessor,
-                                                                               right_relation_id,
                                                                                right_tuple_id));
   }
 }
@@ -119,9 +115,7 @@
 }
 
 ColumnVectorPtr ScalarUnaryExpression::getAllValuesForJoin(
-    const relation_id left_relation_id,
     ValueAccessor *left_accessor,
-    const relation_id right_relation_id,
     ValueAccessor *right_accessor,
     const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
     ColumnVectorCache *cv_cache) const {
@@ -134,11 +128,9 @@
 #ifdef QUICKSTEP_ENABLE_VECTOR_COPY_ELISION_JOIN
     const attribute_id operand_attr_id = operand_->getAttributeIdForValueAccessor();
     if (operand_attr_id != -1) {
-      const relation_id operand_relation_id = operand_->getRelationIdForValueAccessor();
-      DCHECK_NE(operand_relation_id, -1);
-      DCHECK((operand_relation_id == left_relation_id)
-             || (operand_relation_id == right_relation_id));
-      const bool using_left_relation = (operand_relation_id == left_relation_id);
+      const JoinSide join_side = operand_->join_side();
+      DCHECK(join_side != kNone);
+      const bool using_left_relation = (join_side == kLeftSide);
       ValueAccessor *operand_accessor = using_left_relation ? left_accessor
                                                             : right_accessor;
       return ColumnVectorPtr(
@@ -150,9 +142,7 @@
 #endif  // QUICKSTEP_ENABLE_VECTOR_COPY_ELISION_JOIN
 
     ColumnVectorPtr operand_result(
-        operand_->getAllValuesForJoin(left_relation_id,
-                                      left_accessor,
-                                      right_relation_id,
+        operand_->getAllValuesForJoin(left_accessor,
                                       right_accessor,
                                       joined_tuple_ids,
                                       cv_cache));
diff --git a/expressions/scalar/ScalarUnaryExpression.hpp b/expressions/scalar/ScalarUnaryExpression.hpp
index 52edea7..a628bd0 100644
--- a/expressions/scalar/ScalarUnaryExpression.hpp
+++ b/expressions/scalar/ScalarUnaryExpression.hpp
@@ -79,10 +79,8 @@
 
   TypedValue getValueForJoinedTuples(
       const ValueAccessor &left_accessor,
-      const relation_id left_relation_id,
       const tuple_id left_tuple_id,
       const ValueAccessor &right_accessor,
-      const relation_id right_relation_id,
       const tuple_id right_tuple_id) const override;
 
   bool hasStaticValue() const override {
@@ -99,9 +97,7 @@
                                ColumnVectorCache *cv_cache) const override;
 
   ColumnVectorPtr getAllValuesForJoin(
-      const relation_id left_relation_id,
       ValueAccessor *left_accessor,
-      const relation_id right_relation_id,
       ValueAccessor *right_accessor,
       const std::vector<std::pair<tuple_id, tuple_id>> &joined_tuple_ids,
       ColumnVectorCache *cv_cache) const override;
diff --git a/expressions/scalar/tests/ScalarCaseExpression_unittest.cpp b/expressions/scalar/tests/ScalarCaseExpression_unittest.cpp
index f385b74..b9b2b38 100644
--- a/expressions/scalar/tests/ScalarCaseExpression_unittest.cpp
+++ b/expressions/scalar/tests/ScalarCaseExpression_unittest.cpp
@@ -916,8 +916,8 @@
       new ScalarLiteral(TypedValue(static_cast<int>(2)), int_type)));
   result_expressions.emplace_back(new ScalarBinaryExpression(
       BinaryOperationFactory::GetBinaryOperation(BinaryOperationID::kAdd),
-      new ScalarAttribute(*sample_relation_->getAttributeById(0)),
-      new ScalarAttribute(*other_relation.getAttributeById(1))));
+      new ScalarAttribute(*sample_relation_->getAttributeById(0), Scalar::kLeftSide),
+      new ScalarAttribute(*other_relation.getAttributeById(1), Scalar::kRightSide)));
 
   const int kConstant = 72;
   // WHEN 1 < 2 THEN kConstant
@@ -931,8 +931,8 @@
   // WHEN double_attr = other_double THEN 0
   when_predicates.emplace_back(new ComparisonPredicate(
       ComparisonFactory::GetComparison(ComparisonID::kEqual),
-      new ScalarAttribute(*sample_relation_->getAttributeById(1)),
-      new ScalarAttribute(*other_relation.getAttributeById(0))));
+      new ScalarAttribute(*sample_relation_->getAttributeById(1), Scalar::kLeftSide),
+      new ScalarAttribute(*other_relation.getAttributeById(0), Scalar::kRightSide)));
   result_expressions.emplace_back(new ScalarLiteral(TypedValue(0), TypeFactory::GetType(kInt)));
 
   const Type &int_nullable_type = TypeFactory::GetType(kInt, true);
@@ -947,14 +947,13 @@
   // Create a list of joined tuple-id pairs (just the cross-product of tuples).
   std::vector<std::pair<tuple_id, tuple_id>> joined_tuple_ids;
   for (std::size_t tuple_num = 0; tuple_num < kNumSampleTuples; ++tuple_num) {
+    // <LeftSide-tid, RightSide-tid>.
     joined_tuple_ids.emplace_back(tuple_num, 0);
     joined_tuple_ids.emplace_back(tuple_num, 1);
   }
 
   ColumnVectorPtr result_cv(case_expr.getAllValuesForJoin(
-      0,
       &sample_data_value_accessor_,
-      1,
       &other_accessor,
       joined_tuple_ids,
       nullptr /* cv_cache */));
@@ -1012,8 +1011,8 @@
       new ScalarLiteral(TypedValue(static_cast<int>(2)), int_type)));
   result_expressions.emplace_back(new ScalarBinaryExpression(
       BinaryOperationFactory::GetBinaryOperation(BinaryOperationID::kAdd),
-      new ScalarAttribute(*sample_relation_->getAttributeById(0)),
-      new ScalarAttribute(*other_relation.getAttributeById(1))));
+      new ScalarAttribute(*sample_relation_->getAttributeById(0), Scalar::kLeftSide),
+      new ScalarAttribute(*other_relation.getAttributeById(1), Scalar::kRightSide)));
 
   // WHEN 1 < 2 THEN int_attr
   when_predicates.emplace_back(new ComparisonPredicate(
@@ -1021,13 +1020,13 @@
       new ScalarLiteral(TypedValue(static_cast<int>(1)), int_type),
       new ScalarLiteral(TypedValue(static_cast<int>(2)), int_type)));
   result_expressions.emplace_back(
-      new ScalarAttribute(*sample_relation_->getAttributeById(0)));
+      new ScalarAttribute(*sample_relation_->getAttributeById(0), Scalar::kLeftSide));
 
   // WHEN double_attr = other_double THEN 0
   when_predicates.emplace_back(new ComparisonPredicate(
       ComparisonFactory::GetComparison(ComparisonID::kEqual),
-      new ScalarAttribute(*sample_relation_->getAttributeById(1)),
-      new ScalarAttribute(*other_relation.getAttributeById(0))));
+      new ScalarAttribute(*sample_relation_->getAttributeById(1), Scalar::kLeftSide),
+      new ScalarAttribute(*other_relation.getAttributeById(0), Scalar::kRightSide)));
   result_expressions.emplace_back(new ScalarLiteral(TypedValue(0), TypeFactory::GetType(kInt)));
 
   const Type &int_nullable_type = TypeFactory::GetType(kInt, true);
@@ -1042,14 +1041,13 @@
   // Create a list of joined tuple-id pairs (just the cross-product of tuples).
   std::vector<std::pair<tuple_id, tuple_id>> joined_tuple_ids;
   for (std::size_t tuple_num = 0; tuple_num < kNumSampleTuples; ++tuple_num) {
+    // <LeftSide-tid, RightSide-tid>.
     joined_tuple_ids.emplace_back(tuple_num, 0);
     joined_tuple_ids.emplace_back(tuple_num, 1);
   }
 
   ColumnVectorPtr result_cv(case_expr.getAllValuesForJoin(
-      0,
       &sample_data_value_accessor_,
-      1,
       &other_accessor,
       joined_tuple_ids,
       nullptr /* cv_cache */));
@@ -1116,8 +1114,8 @@
       new ScalarLiteral(TypedValue(static_cast<int>(2)), int_type)));
   result_expressions.emplace_back(new ScalarBinaryExpression(
       BinaryOperationFactory::GetBinaryOperation(BinaryOperationID::kAdd),
-      new ScalarAttribute(*sample_relation_->getAttributeById(0)),
-      new ScalarAttribute(*other_relation.getAttributeById(1))));
+      new ScalarAttribute(*sample_relation_->getAttributeById(0), Scalar::kLeftSide),
+      new ScalarAttribute(*other_relation.getAttributeById(1), Scalar::kRightSide)));
 
   // WHEN 1 < 2 THEN int_attr * other_int
   when_predicates.emplace_back(new ComparisonPredicate(
@@ -1126,14 +1124,14 @@
       new ScalarLiteral(TypedValue(static_cast<int>(2)), int_type)));
   result_expressions.emplace_back(new ScalarBinaryExpression(
       BinaryOperationFactory::GetBinaryOperation(BinaryOperationID::kMultiply),
-      new ScalarAttribute(*sample_relation_->getAttributeById(0)),
-      new ScalarAttribute(*other_relation.getAttributeById(1))));
+      new ScalarAttribute(*sample_relation_->getAttributeById(0), Scalar::kLeftSide),
+      new ScalarAttribute(*other_relation.getAttributeById(1), Scalar::kRightSide)));
 
   // WHEN double_attr = other_double THEN 0
   when_predicates.emplace_back(new ComparisonPredicate(
       ComparisonFactory::GetComparison(ComparisonID::kEqual),
-      new ScalarAttribute(*sample_relation_->getAttributeById(1)),
-      new ScalarAttribute(*other_relation.getAttributeById(0))));
+      new ScalarAttribute(*sample_relation_->getAttributeById(1), Scalar::kLeftSide),
+      new ScalarAttribute(*other_relation.getAttributeById(0), Scalar::kRightSide)));
   result_expressions.emplace_back(new ScalarLiteral(TypedValue(0), TypeFactory::GetType(kInt)));
 
   const Type &int_nullable_type = TypeFactory::GetType(kInt, true);
@@ -1148,14 +1146,13 @@
   // Create a list of joined tuple-id pairs (just the cross-product of tuples).
   std::vector<std::pair<tuple_id, tuple_id>> joined_tuple_ids;
   for (std::size_t tuple_num = 0; tuple_num < kNumSampleTuples; ++tuple_num) {
+    // <LeftSide-tid, RightSide-tid>.
     joined_tuple_ids.emplace_back(tuple_num, 0);
     joined_tuple_ids.emplace_back(tuple_num, 1);
   }
 
   ColumnVectorPtr result_cv(case_expr.getAllValuesForJoin(
-      0,
       &sample_data_value_accessor_,
-      1,
       &other_accessor,
       joined_tuple_ids,
       nullptr /* cv_cache */));
@@ -1217,22 +1214,22 @@
   // WHEN double_attr > other_double THEN int_attr + other_int
   when_predicates.emplace_back(new ComparisonPredicate(
       ComparisonFactory::GetComparison(ComparisonID::kGreater),
-      new ScalarAttribute(*sample_relation_->getAttributeById(1)),
-      new ScalarAttribute(*other_relation.getAttributeById(0))));
+      new ScalarAttribute(*sample_relation_->getAttributeById(1), Scalar::kLeftSide),
+      new ScalarAttribute(*other_relation.getAttributeById(0), Scalar::kRightSide)));
   result_expressions.emplace_back(new ScalarBinaryExpression(
       BinaryOperationFactory::GetBinaryOperation(BinaryOperationID::kAdd),
-      new ScalarAttribute(*sample_relation_->getAttributeById(0)),
-      new ScalarAttribute(*other_relation.getAttributeById(1))));
+      new ScalarAttribute(*sample_relation_->getAttributeById(0), Scalar::kLeftSide),
+      new ScalarAttribute(*other_relation.getAttributeById(1), Scalar::kRightSide)));
 
   // WHEN double_attr < other_double THEN int_attr * other_int
   when_predicates.emplace_back(new ComparisonPredicate(
       ComparisonFactory::GetComparison(ComparisonID::kLess),
-      new ScalarAttribute(*sample_relation_->getAttributeById(1)),
-      new ScalarAttribute(*other_relation.getAttributeById(0))));
+      new ScalarAttribute(*sample_relation_->getAttributeById(1), Scalar::kLeftSide),
+      new ScalarAttribute(*other_relation.getAttributeById(0), Scalar::kRightSide)));
   result_expressions.emplace_back(new ScalarBinaryExpression(
       BinaryOperationFactory::GetBinaryOperation(BinaryOperationID::kMultiply),
-      new ScalarAttribute(*sample_relation_->getAttributeById(0)),
-      new ScalarAttribute(*other_relation.getAttributeById(1))));
+      new ScalarAttribute(*sample_relation_->getAttributeById(0), Scalar::kLeftSide),
+      new ScalarAttribute(*other_relation.getAttributeById(1), Scalar::kRightSide)));
 
   // ELSE 0
   ScalarCaseExpression case_expr(
@@ -1244,14 +1241,13 @@
   // Create a list of joined tuple-id pairs (just the cross-product of tuples).
   std::vector<std::pair<tuple_id, tuple_id>> joined_tuple_ids;
   for (std::size_t tuple_num = 0; tuple_num < kNumSampleTuples; ++tuple_num) {
+    // <LeftSide-tid, RightSide-tid>.
     joined_tuple_ids.emplace_back(tuple_num, 0);
     joined_tuple_ids.emplace_back(tuple_num, 1);
   }
 
   ColumnVectorPtr result_cv(case_expr.getAllValuesForJoin(
-      0,
       &sample_data_value_accessor_,
-      1,
       &other_accessor,
       joined_tuple_ids,
       nullptr /* cv_cache */));
diff --git a/query_optimizer/ExecutionGenerator.cpp b/query_optimizer/ExecutionGenerator.cpp
index cc1319c..b413a97 100644
--- a/query_optimizer/ExecutionGenerator.cpp
+++ b/query_optimizer/ExecutionGenerator.cpp
@@ -29,16 +29,12 @@
 #include <string>
 #include <type_traits>
 #include <unordered_map>
-
-#include "query_optimizer/QueryOptimizerConfig.h"  // For QUICKSTEP_DISTRIBUTED.
-
-#ifdef QUICKSTEP_DISTRIBUTED
 #include <unordered_set>
-#endif
-
 #include <utility>
 #include <vector>
 
+#include "query_optimizer/QueryOptimizerConfig.h"  // For QUICKSTEP_DISTRIBUTED.
+
 #ifdef QUICKSTEP_DISTRIBUTED
 #include "catalog/Catalog.pb.h"
 #endif
@@ -72,6 +68,7 @@
 #include "query_optimizer/expressions/Alias.hpp"
 #include "query_optimizer/expressions/AttributeReference.hpp"
 #include "query_optimizer/expressions/ComparisonExpression.hpp"
+#include "query_optimizer/expressions/ExprId.hpp"
 #include "query_optimizer/expressions/ExpressionType.hpp"
 #include "query_optimizer/expressions/PatternMatcher.hpp"
 #include "query_optimizer/expressions/Scalar.hpp"
@@ -573,7 +570,9 @@
 
 void ExecutionGenerator::convertNamedExpressions(
     const std::vector<E::NamedExpressionPtr> &named_expressions,
-    S::QueryContext::ScalarGroup *scalar_group_proto) {
+    S::QueryContext::ScalarGroup *scalar_group_proto,
+    const std::unordered_set<E::ExprId> &left_expr_ids,
+    const std::unordered_set<E::ExprId> &right_expr_ids) {
   for (const E::NamedExpressionPtr &project_expression : named_expressions) {
     unique_ptr<const Scalar> execution_scalar;
     E::AliasPtr alias;
@@ -583,9 +582,11 @@
       // so all child expressions of an Alias should be a Scalar.
       CHECK(E::SomeScalar::MatchesWithConditionalCast(alias->expression(), &scalar))
           << alias->toString();
-      execution_scalar.reset(scalar->concretize(attribute_substitution_map_));
+      execution_scalar.reset(
+          scalar->concretize(attribute_substitution_map_, left_expr_ids, right_expr_ids));
     } else {
-      execution_scalar.reset(project_expression->concretize(attribute_substitution_map_));
+      execution_scalar.reset(
+          project_expression->concretize(attribute_substitution_map_, left_expr_ids, right_expr_ids));
     }
 
     scalar_group_proto->add_scalars()->MergeFrom(execution_scalar->getProto());
@@ -593,8 +594,10 @@
 }
 
 Predicate* ExecutionGenerator::convertPredicate(
-    const expressions::PredicatePtr &optimizer_predicate) const {
-  return optimizer_predicate->concretize(attribute_substitution_map_);
+    const expressions::PredicatePtr &optimizer_predicate,
+    const std::unordered_set<E::ExprId> &left_expr_ids,
+    const std::unordered_set<E::ExprId> &right_expr_ids) const {
+  return optimizer_predicate->concretize(attribute_substitution_map_, left_expr_ids, right_expr_ids);
 }
 
 void ExecutionGenerator::convertTableReference(
@@ -941,12 +944,27 @@
     key_types.push_back(&left_attribute_type);
   }
 
+  std::unordered_set<E::ExprId> probe_expr_ids;
+  const auto probe_output_attributes = probe_physical->getOutputAttributes();
+  probe_expr_ids.reserve(probe_output_attributes.size());
+  for (const auto &probe_output_attribute : probe_output_attributes) {
+    probe_expr_ids.insert(probe_output_attribute->id());
+  }
+
+  std::unordered_set<E::ExprId> build_expr_ids;
+  const auto build_output_attributes = build_physical->getOutputAttributes();
+  build_expr_ids.reserve(build_output_attributes.size());
+  for (const auto &build_output_attribute : build_output_attributes) {
+    build_expr_ids.insert(build_output_attribute->id());
+  }
+
   // Convert the residual predicate proto.
   QueryContext::predicate_id residual_predicate_index = QueryContext::kInvalidPredicateId;
   if (physical_plan->residual_predicate()) {
     residual_predicate_index = query_context_proto_->predicates_size();
 
-    unique_ptr<const Predicate> residual_predicate(convertPredicate(physical_plan->residual_predicate()));
+    unique_ptr<const Predicate> residual_predicate(
+        convertPredicate(physical_plan->residual_predicate(), probe_expr_ids, build_expr_ids));
     query_context_proto_->add_predicates()->MergeFrom(residual_predicate->getProto());
   }
 
@@ -955,7 +973,8 @@
   if (physical_plan->build_predicate()) {
     build_predicate_index = query_context_proto_->predicates_size();
 
-    unique_ptr<const Predicate> build_predicate(convertPredicate(physical_plan->build_predicate()));
+    unique_ptr<const Predicate> build_predicate(
+        convertPredicate(physical_plan->build_predicate(), probe_expr_ids, build_expr_ids));
     query_context_proto_->add_predicates()->MergeFrom(build_predicate->getProto());
   }
 
@@ -963,7 +982,7 @@
   const QueryContext::scalar_group_id project_expressions_group_index =
       query_context_proto_->scalar_groups_size();
   convertNamedExpressions(physical_plan->project_expressions(),
-                          query_context_proto_->add_scalar_groups());
+                          query_context_proto_->add_scalar_groups(), probe_expr_ids, build_expr_ids);
 
   const CatalogRelationInfo *build_relation_info =
       findRelationInfoOutputByPhysical(build_physical);
@@ -979,19 +998,12 @@
         new std::vector<bool>(
             E::MarkExpressionsReferingAnyAttribute(
                 physical_plan->project_expressions(),
-                build_physical->getOutputAttributes())));
+                build_output_attributes)));
   }
 
   const CatalogRelation *build_relation = build_relation_info->relation;
   const CatalogRelation *probe_relation = probe_relation_info->relation;
 
-  // FIXME(quickstep-team): Add support for self-join.
-  // We check to see if the build_predicate is null as certain queries that
-  // support hash-select fuse will result in the first check being true.
-  if (build_relation == probe_relation && physical_plan->build_predicate() == nullptr) {
-    THROW_SQL_ERROR() << "Self-join is not supported";
-  }
-
   // Create join hash table proto.
   const QueryContext::join_hash_table_id join_hash_table_index =
       query_context_proto_->join_hash_tables_size();
@@ -1129,10 +1141,28 @@
     const P::NestedLoopsJoinPtr &physical_plan) {
   // NestedLoopsJoin is converted to a NestedLoopsJoin operator.
 
+  const P::PhysicalPtr &left_physical = physical_plan->left();
+  const P::PhysicalPtr &right_physical = physical_plan->right();
+
+  std::unordered_set<E::ExprId> left_expr_ids;
+  const auto left_output_attributes = left_physical->getOutputAttributes();
+  left_expr_ids.reserve(left_output_attributes.size());
+  for (const auto &left_output_attribute : left_output_attributes) {
+    left_expr_ids.insert(left_output_attribute->id());
+  }
+
+  std::unordered_set<E::ExprId> right_expr_ids;
+  const auto right_output_attributes = right_physical->getOutputAttributes();
+  right_expr_ids.reserve(right_output_attributes.size());
+  for (const auto &right_output_attribute : right_output_attributes) {
+    right_expr_ids.insert(right_output_attribute->id());
+  }
+
   // Convert the join predicate proto.
   const QueryContext::predicate_id execution_join_predicate_index = query_context_proto_->predicates_size();
   if (physical_plan->join_predicate()) {
-    unique_ptr<const Predicate> execution_join_predicate(convertPredicate(physical_plan->join_predicate()));
+    unique_ptr<const Predicate> execution_join_predicate(
+        convertPredicate(physical_plan->join_predicate(), left_expr_ids, right_expr_ids));
     query_context_proto_->add_predicates()->MergeFrom(execution_join_predicate->getProto());
   } else {
     query_context_proto_->add_predicates()->set_predicate_type(S::Predicate::TRUE);
@@ -1142,20 +1172,16 @@
   const QueryContext::scalar_group_id project_expressions_group_index =
       query_context_proto_->scalar_groups_size();
   convertNamedExpressions(physical_plan->project_expressions(),
-                          query_context_proto_->add_scalar_groups());
+                          query_context_proto_->add_scalar_groups(),
+                          left_expr_ids, right_expr_ids);
 
   const CatalogRelationInfo *left_relation_info =
-      findRelationInfoOutputByPhysical(physical_plan->left());
+      findRelationInfoOutputByPhysical(left_physical);
   const CatalogRelation &left_relation = *left_relation_info->relation;
   const CatalogRelationInfo *right_relation_info =
-      findRelationInfoOutputByPhysical(physical_plan->right());
+      findRelationInfoOutputByPhysical(right_physical);
   const CatalogRelation &right_relation = *right_relation_info->relation;
 
-  // FIXME(quickstep-team): Add support for self-join.
-  if (left_relation.getID() == right_relation.getID()) {
-    THROW_SQL_ERROR() << "NestedLoopsJoin does not support self-join yet";
-  }
-
   const std::size_t num_partitions = left_relation.getNumPartitions();
 
 #ifdef QUICKSTEP_DEBUG
diff --git a/query_optimizer/ExecutionGenerator.hpp b/query_optimizer/ExecutionGenerator.hpp
index bc9f88b..1385757 100644
--- a/query_optimizer/ExecutionGenerator.hpp
+++ b/query_optimizer/ExecutionGenerator.hpp
@@ -24,11 +24,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
-
-#ifdef QUICKSTEP_DISTRIBUTED
 #include <unordered_set>
-#endif
-
 #include <vector>
 
 #include "catalog/CatalogTypedefs.hpp"
@@ -388,10 +384,16 @@
    * @param named_expressions The list of NamedExpressions to be converted.
    * @param scalar_group_proto The corresponding scalars proto in QueryContext
    *        proto.
+   * @param left_expr_ids The ExprIds from the left hand side.
+   * @param right_expr_ids The ExprIds from the right hand side.
    */
   void convertNamedExpressions(
       const std::vector<expressions::NamedExpressionPtr> &named_expressions,
-      serialization::QueryContext::ScalarGroup *scalar_group_proto);
+      serialization::QueryContext::ScalarGroup *scalar_group_proto,
+      const std::unordered_set<expressions::ExprId> &left_expr_ids =
+          std::unordered_set<expressions::ExprId>(),
+      const std::unordered_set<expressions::ExprId> &right_expr_ids =
+          std::unordered_set<expressions::ExprId>());
 
   /**
    * @brief Converts a Predicate in the optimizer expression system to a
@@ -399,9 +401,16 @@
    *        takes ownership of the returned pointer.
    *
    * @param optimizer_predicate The Predicate to be converted.
+   * @param left_expr_ids The ExprIds from the left hand side.
+   * @param right_expr_ids The ExprIds from the right hand side.
    * @return The corresponding Predicate in the execution expression system.
    */
-  Predicate* convertPredicate(const expressions::PredicatePtr &optimizer_predicate) const;
+  Predicate* convertPredicate(
+      const expressions::PredicatePtr &optimizer_predicate,
+      const std::unordered_set<expressions::ExprId> &left_expr_ids =
+          std::unordered_set<expressions::ExprId>(),
+      const std::unordered_set<expressions::ExprId> &right_expr_ids =
+          std::unordered_set<expressions::ExprId>()) const;
 
   /**
    * @brief Drops all temporary relations created by the generator
diff --git a/query_optimizer/expressions/Alias.cpp b/query_optimizer/expressions/Alias.cpp
index f2b2795..0e3541d 100644
--- a/query_optimizer/expressions/Alias.cpp
+++ b/query_optimizer/expressions/Alias.cpp
@@ -21,6 +21,7 @@
 
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "catalog/CatalogTypedefs.hpp"
@@ -65,7 +66,9 @@
 }
 
 ::quickstep::Scalar *Alias::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   // Alias should be converted to a CatalogAttribute.
   LOG(FATAL) << "Cannot concretize Alias to a scalar for evaluation";
 }
diff --git a/query_optimizer/expressions/Alias.hpp b/query_optimizer/expressions/Alias.hpp
index e0ee959..16d3715 100644
--- a/query_optimizer/expressions/Alias.hpp
+++ b/query_optimizer/expressions/Alias.hpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/OptimizerTree.hpp"
@@ -81,7 +82,9 @@
   }
 
   ::quickstep::Scalar *concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   /**
    * @brief Creates an immutable Alias. If \p expression is also an Alias,
diff --git a/query_optimizer/expressions/AttributeReference.cpp b/query_optimizer/expressions/AttributeReference.cpp
index facfb39..86a1711 100644
--- a/query_optimizer/expressions/AttributeReference.cpp
+++ b/query_optimizer/expressions/AttributeReference.cpp
@@ -23,8 +23,10 @@
 #include <functional>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
+#include "expressions/scalar/Scalar.hpp"
 #include "expressions/scalar/ScalarAttribute.hpp"
 #include "query_optimizer/expressions/ExprId.hpp"
 #include "query_optimizer/expressions/Expression.hpp"
@@ -53,11 +55,22 @@
 }
 
 ::quickstep::Scalar *AttributeReference::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
+  const ExprId expr_id = id();
   const std::unordered_map<ExprId, const CatalogAttribute*>::const_iterator found_it =
-      substitution_map.find(id());
+      substitution_map.find(expr_id);
   DCHECK(found_it != substitution_map.end()) << toString();
-  return new ::quickstep::ScalarAttribute(*found_it->second);
+
+  ::quickstep::Scalar::JoinSide join_side = ::quickstep::Scalar::kNone;
+  if (left_expr_ids.find(expr_id) != left_expr_ids.end()) {
+    join_side = ::quickstep::Scalar::kLeftSide;
+  } else if (right_expr_ids.find(expr_id) != right_expr_ids.end()) {
+    join_side = ::quickstep::Scalar::kRightSide;
+  }
+
+  return new ::quickstep::ScalarAttribute(*found_it->second, join_side);
 }
 
 std::size_t AttributeReference::computeHash() const {
diff --git a/query_optimizer/expressions/AttributeReference.hpp b/query_optimizer/expressions/AttributeReference.hpp
index ca796ba..0a8b855 100644
--- a/query_optimizer/expressions/AttributeReference.hpp
+++ b/query_optimizer/expressions/AttributeReference.hpp
@@ -24,6 +24,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "catalog/CatalogTypedefs.hpp"
@@ -88,7 +89,9 @@
   std::vector<AttributeReferencePtr> getReferencedAttributes() const override;
 
   ::quickstep::Scalar* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   bool equals(const ScalarPtr &other) const override;
 
diff --git a/query_optimizer/expressions/BinaryExpression.cpp b/query_optimizer/expressions/BinaryExpression.cpp
index 07eb5ff..af4929c 100644
--- a/query_optimizer/expressions/BinaryExpression.cpp
+++ b/query_optimizer/expressions/BinaryExpression.cpp
@@ -23,6 +23,7 @@
 #include <cstddef>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <utility>
 #include <vector>
 
@@ -101,11 +102,13 @@
 }
 
 ::quickstep::Scalar *BinaryExpression::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   return new ::quickstep::ScalarBinaryExpression(
       operation_,
-      left_->concretize(substitution_map),
-      right_->concretize(substitution_map));
+      left_->concretize(substitution_map, left_expr_ids, right_expr_ids),
+      right_->concretize(substitution_map, left_expr_ids, right_expr_ids));
 }
 
 std::size_t BinaryExpression::computeHash() const {
diff --git a/query_optimizer/expressions/BinaryExpression.hpp b/query_optimizer/expressions/BinaryExpression.hpp
index df7454c..92419f6 100644
--- a/query_optimizer/expressions/BinaryExpression.hpp
+++ b/query_optimizer/expressions/BinaryExpression.hpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/OptimizerTree.hpp"
@@ -88,7 +89,9 @@
   std::vector<AttributeReferencePtr> getReferencedAttributes() const override;
 
   ::quickstep::Scalar* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   bool equals(const ScalarPtr &other) const override;
 
diff --git a/query_optimizer/expressions/CMakeLists.txt b/query_optimizer/expressions/CMakeLists.txt
index 7032f05..03a8247 100644
--- a/query_optimizer/expressions/CMakeLists.txt
+++ b/query_optimizer/expressions/CMakeLists.txt
@@ -79,6 +79,7 @@
 target_link_libraries(quickstep_queryoptimizer_expressions_AttributeReference
                       glog
                       quickstep_catalog_CatalogTypedefs
+                      quickstep_expressions_scalar_Scalar
                       quickstep_expressions_scalar_ScalarAttribute
                       quickstep_queryoptimizer_expressions_ExprId
                       quickstep_queryoptimizer_expressions_Expression
diff --git a/query_optimizer/expressions/Cast.cpp b/query_optimizer/expressions/Cast.cpp
index e6eb1bd..c5d8f94 100644
--- a/query_optimizer/expressions/Cast.cpp
+++ b/query_optimizer/expressions/Cast.cpp
@@ -22,6 +22,7 @@
 #include <cstddef>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "expressions/scalar/Scalar.hpp"
@@ -52,9 +53,12 @@
 }
 
 ::quickstep::Scalar *Cast::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
-  return new ::quickstep::ScalarUnaryExpression(::quickstep::NumericCastOperation::Instance(target_type_),
-                                                operand_->concretize(substitution_map));
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
+  return new ::quickstep::ScalarUnaryExpression(
+      ::quickstep::NumericCastOperation::Instance(target_type_),
+      operand_->concretize(substitution_map, left_expr_ids, right_expr_ids));
 }
 
 std::size_t Cast::computeHash() const {
diff --git a/query_optimizer/expressions/Cast.hpp b/query_optimizer/expressions/Cast.hpp
index fa40242..2e7ea96 100644
--- a/query_optimizer/expressions/Cast.hpp
+++ b/query_optimizer/expressions/Cast.hpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/OptimizerTree.hpp"
@@ -76,7 +77,9 @@
       const std::vector<ExpressionPtr> &new_children) const override;
 
   ::quickstep::Scalar* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   bool equals(const ScalarPtr &other) const override;
 
diff --git a/query_optimizer/expressions/CommonSubexpression.cpp b/query_optimizer/expressions/CommonSubexpression.cpp
index 4b13a0e..dcd3f1f 100644
--- a/query_optimizer/expressions/CommonSubexpression.cpp
+++ b/query_optimizer/expressions/CommonSubexpression.cpp
@@ -22,6 +22,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "expressions/scalar/ScalarSharedExpression.hpp"
@@ -47,10 +48,12 @@
 }
 
 ::quickstep::Scalar* CommonSubexpression::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   return new ::quickstep::ScalarSharedExpression(
       static_cast<int>(common_subexpression_id_),
-      operand_->concretize(substitution_map));
+      operand_->concretize(substitution_map, left_expr_ids, right_expr_ids));
 }
 
 void CommonSubexpression::getFieldStringItems(
diff --git a/query_optimizer/expressions/CommonSubexpression.hpp b/query_optimizer/expressions/CommonSubexpression.hpp
index 2c2d86c..f0482c9 100644
--- a/query_optimizer/expressions/CommonSubexpression.hpp
+++ b/query_optimizer/expressions/CommonSubexpression.hpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/expressions/AttributeReference.hpp"
@@ -93,7 +94,9 @@
   }
 
   ::quickstep::Scalar* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   /**
    * @brief Creates an immutable CommonSubexpression.
diff --git a/query_optimizer/expressions/ComparisonExpression.cpp b/query_optimizer/expressions/ComparisonExpression.cpp
index 8d93794..5529eef 100644
--- a/query_optimizer/expressions/ComparisonExpression.cpp
+++ b/query_optimizer/expressions/ComparisonExpression.cpp
@@ -21,6 +21,7 @@
 
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "expressions/predicate/ComparisonPredicate.hpp"
@@ -80,11 +81,13 @@
 }
 
 ::quickstep::Predicate* ComparisonExpression::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   return new ::quickstep::ComparisonPredicate(
       comparison_,
-      left_->concretize(substitution_map),
-      right_->concretize(substitution_map));
+      left_->concretize(substitution_map, left_expr_ids, right_expr_ids),
+      right_->concretize(substitution_map, left_expr_ids, right_expr_ids));
 }
 
 void ComparisonExpression::getFieldStringItems(
diff --git a/query_optimizer/expressions/ComparisonExpression.hpp b/query_optimizer/expressions/ComparisonExpression.hpp
index f119f71..26d44fc 100644
--- a/query_optimizer/expressions/ComparisonExpression.hpp
+++ b/query_optimizer/expressions/ComparisonExpression.hpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/OptimizerTree.hpp"
@@ -89,7 +90,9 @@
   std::vector<AttributeReferencePtr> getReferencedAttributes() const override;
 
   ::quickstep::Predicate* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   /**
    * @brief Creates an immutable ComparisonExpression.
diff --git a/query_optimizer/expressions/Exists.cpp b/query_optimizer/expressions/Exists.cpp
index bf4cb72..792704b 100644
--- a/query_optimizer/expressions/Exists.cpp
+++ b/query_optimizer/expressions/Exists.cpp
@@ -21,6 +21,7 @@
 
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <utility>
 #include <vector>
 
@@ -38,7 +39,9 @@
 namespace expressions {
 
 ::quickstep::Predicate* Exists::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   LOG(FATAL) << "Exists predicate should not be concretized";
   return nullptr;
 }
diff --git a/query_optimizer/expressions/Exists.hpp b/query_optimizer/expressions/Exists.hpp
index e90348e..7f1046d 100644
--- a/query_optimizer/expressions/Exists.hpp
+++ b/query_optimizer/expressions/Exists.hpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/OptimizerTree.hpp"
@@ -86,7 +87,9 @@
   }
 
   ::quickstep::Predicate* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   /**
    * @brief Create an Exists predicate expression.
diff --git a/query_optimizer/expressions/InTableQuery.cpp b/query_optimizer/expressions/InTableQuery.cpp
index 79018e5..29d8a4e 100644
--- a/query_optimizer/expressions/InTableQuery.cpp
+++ b/query_optimizer/expressions/InTableQuery.cpp
@@ -21,6 +21,7 @@
 
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/OptimizerTree.hpp"
@@ -33,7 +34,9 @@
 namespace expressions {
 
 ::quickstep::Predicate* InTableQuery::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   LOG(FATAL) << "InTableQuery predicate should not be concretized";
 }
 
diff --git a/query_optimizer/expressions/InTableQuery.hpp b/query_optimizer/expressions/InTableQuery.hpp
index 245ff0d..bb659fb 100644
--- a/query_optimizer/expressions/InTableQuery.hpp
+++ b/query_optimizer/expressions/InTableQuery.hpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/OptimizerTree.hpp"
@@ -96,7 +97,9 @@
   }
 
   ::quickstep::Predicate* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   /**
    * @brief Create an IN predicate with a subquery.
diff --git a/query_optimizer/expressions/InValueList.cpp b/query_optimizer/expressions/InValueList.cpp
index d968d48..55f65b1 100644
--- a/query_optimizer/expressions/InValueList.cpp
+++ b/query_optimizer/expressions/InValueList.cpp
@@ -22,6 +22,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "expressions/predicate/DisjunctionPredicate.hpp"
@@ -40,7 +41,9 @@
 namespace expressions {
 
 ::quickstep::Predicate* InValueList::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   std::unique_ptr<quickstep::DisjunctionPredicate>
       disjunction_predicate(new quickstep::DisjunctionPredicate());
   for (const ScalarPtr &match_expression : match_expressions_) {
@@ -51,7 +54,7 @@
             match_expression);
 
     disjunction_predicate->addPredicate(
-        match_predicate->concretize(substitution_map));
+        match_predicate->concretize(substitution_map, left_expr_ids, right_expr_ids));
   }
   return disjunction_predicate.release();
 }
diff --git a/query_optimizer/expressions/InValueList.hpp b/query_optimizer/expressions/InValueList.hpp
index e0f1f57..3d37352 100644
--- a/query_optimizer/expressions/InValueList.hpp
+++ b/query_optimizer/expressions/InValueList.hpp
@@ -24,6 +24,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/OptimizerTree.hpp"
@@ -109,7 +110,9 @@
   }
 
   ::quickstep::Predicate* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   /**
    * @brief Create an IN predicate with a value list.
diff --git a/query_optimizer/expressions/LogicalAnd.cpp b/query_optimizer/expressions/LogicalAnd.cpp
index a3908bd..9bcc02c 100644
--- a/query_optimizer/expressions/LogicalAnd.cpp
+++ b/query_optimizer/expressions/LogicalAnd.cpp
@@ -22,6 +22,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "expressions/predicate/ConjunctionPredicate.hpp"
@@ -86,13 +87,15 @@
 }
 
 ::quickstep::Predicate* LogicalAnd::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   if (operands_.empty()) {
     return new TruePredicate();
   }
 
   if (operands_.size() == 1u) {
-    return operands_[0]->concretize(substitution_map);
+    return operands_[0]->concretize(substitution_map, left_expr_ids, right_expr_ids);
   }
 
   std::unique_ptr<::quickstep::ConjunctionPredicate> concretized_predicate;
@@ -100,7 +103,7 @@
 
   for (const PredicatePtr &operand : operands_) {
     concretized_predicate->addPredicate(
-        operand->concretize(substitution_map));
+        operand->concretize(substitution_map, left_expr_ids, right_expr_ids));
   }
 
   return concretized_predicate.release();
diff --git a/query_optimizer/expressions/LogicalAnd.hpp b/query_optimizer/expressions/LogicalAnd.hpp
index 8785fc8..93dc39c 100644
--- a/query_optimizer/expressions/LogicalAnd.hpp
+++ b/query_optimizer/expressions/LogicalAnd.hpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/OptimizerTree.hpp"
@@ -88,7 +89,9 @@
   std::vector<AttributeReferencePtr> getReferencedAttributes() const override;
 
   ::quickstep::Predicate* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   /**
    * @brief Creates an immutable LogicalAnd. If any operand is also a LogicalAnd,
diff --git a/query_optimizer/expressions/LogicalNot.cpp b/query_optimizer/expressions/LogicalNot.cpp
index dce13a9..a6ccbd2 100644
--- a/query_optimizer/expressions/LogicalNot.cpp
+++ b/query_optimizer/expressions/LogicalNot.cpp
@@ -21,6 +21,7 @@
 
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "expressions/predicate/NegationPredicate.hpp"
@@ -44,9 +45,11 @@
 }
 
 ::quickstep::Predicate* LogicalNot::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   return new ::quickstep::NegationPredicate(
-      operand_->concretize(substitution_map));
+      operand_->concretize(substitution_map, left_expr_ids, right_expr_ids));
 }
 
 void LogicalNot::getFieldStringItems(
diff --git a/query_optimizer/expressions/LogicalNot.hpp b/query_optimizer/expressions/LogicalNot.hpp
index 7c4e660..9d773c5 100644
--- a/query_optimizer/expressions/LogicalNot.hpp
+++ b/query_optimizer/expressions/LogicalNot.hpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/OptimizerTree.hpp"
@@ -73,7 +74,9 @@
   }
 
   ::quickstep::Predicate* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   /**
    * @brief Creates an immutable LogicalNot.
diff --git a/query_optimizer/expressions/LogicalOr.cpp b/query_optimizer/expressions/LogicalOr.cpp
index c89fd5a..4126493 100644
--- a/query_optimizer/expressions/LogicalOr.cpp
+++ b/query_optimizer/expressions/LogicalOr.cpp
@@ -22,6 +22,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "expressions/predicate/DisjunctionPredicate.hpp"
@@ -84,13 +85,15 @@
 }
 
 ::quickstep::Predicate* LogicalOr::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   if (operands_.empty()) {
     return new FalsePredicate();
   }
 
   if (operands_.size() == 1u) {
-    return operands_[0]->concretize(substitution_map);
+    return operands_[0]->concretize(substitution_map, left_expr_ids, right_expr_ids);
   }
 
   std::unique_ptr<::quickstep::DisjunctionPredicate> concretized_predicate;
@@ -98,7 +101,7 @@
 
   for (const PredicatePtr &operand : operands_) {
     concretized_predicate->addPredicate(
-        operand->concretize(substitution_map));
+        operand->concretize(substitution_map, left_expr_ids, right_expr_ids));
   }
 
   return concretized_predicate.release();
diff --git a/query_optimizer/expressions/LogicalOr.hpp b/query_optimizer/expressions/LogicalOr.hpp
index 2e40c56..52f9ad3 100644
--- a/query_optimizer/expressions/LogicalOr.hpp
+++ b/query_optimizer/expressions/LogicalOr.hpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/OptimizerTree.hpp"
@@ -88,7 +89,9 @@
   std::vector<AttributeReferencePtr> getReferencedAttributes() const override;
 
   ::quickstep::Predicate* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   /**
    * @brief Creates an immutable LogicalOr. If any operand is also a LogicalOr,
diff --git a/query_optimizer/expressions/Predicate.hpp b/query_optimizer/expressions/Predicate.hpp
index 444af6b..a0918e6 100644
--- a/query_optimizer/expressions/Predicate.hpp
+++ b/query_optimizer/expressions/Predicate.hpp
@@ -22,6 +22,7 @@
 
 #include <memory>
 #include <unordered_map>
+#include <unordered_set>
 
 #include "query_optimizer/expressions/ExprId.hpp"
 #include "query_optimizer/expressions/Expression.hpp"
@@ -70,10 +71,14 @@
    *
    * @param substitution_map Map from ExprId to CatalogAttribute for use in
    *                         replacing AttributeReference.
+   * @param left_expr_ids The ExprIds from the left hand side.
+   * @param right_expr_ids The ExprIds from the right hand side.
    * @return A concretized predicate for evaluation.
    */
   virtual ::quickstep::Predicate* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*>& substitution_map) const = 0;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const = 0;
 
  protected:
   Predicate() {}
diff --git a/query_optimizer/expressions/PredicateLiteral.cpp b/query_optimizer/expressions/PredicateLiteral.cpp
index 724458e..fb48eb3 100644
--- a/query_optimizer/expressions/PredicateLiteral.cpp
+++ b/query_optimizer/expressions/PredicateLiteral.cpp
@@ -21,6 +21,7 @@
 
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "expressions/predicate/TrivialPredicates.hpp"
@@ -40,7 +41,9 @@
 }
 
 ::quickstep::Predicate* PredicateLiteral::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   if (is_true()) {
     return new TruePredicate();
   } else {
diff --git a/query_optimizer/expressions/PredicateLiteral.hpp b/query_optimizer/expressions/PredicateLiteral.hpp
index f354a83..f53b6e3 100644
--- a/query_optimizer/expressions/PredicateLiteral.hpp
+++ b/query_optimizer/expressions/PredicateLiteral.hpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/OptimizerTree.hpp"
@@ -70,7 +71,9 @@
   }
 
   ::quickstep::Predicate* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   /**
    * @brief Creates an immutable PredicateLiteral.
diff --git a/query_optimizer/expressions/Scalar.hpp b/query_optimizer/expressions/Scalar.hpp
index a163b21..5635a10 100644
--- a/query_optimizer/expressions/Scalar.hpp
+++ b/query_optimizer/expressions/Scalar.hpp
@@ -23,6 +23,7 @@
 #include <cstddef>
 #include <memory>
 #include <unordered_map>
+#include <unordered_set>
 
 #include "query_optimizer/expressions/Expression.hpp"
 #include "query_optimizer/expressions/ExprId.hpp"
@@ -61,11 +62,14 @@
    * @param substitution_map Map from ExprId to CatalogAttribute for use in
    *                         substituting CatalogAttribute for
    *                         AttributeReference.
+   * @param left_expr_ids The ExprIds from the left hand side.
+   * @param right_expr_ids The ExprIds from the right hand side.
    * @return Concretized expression for evaluation.
    */
   virtual ::quickstep::Scalar* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*>& substitution_map)
-      const = 0;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const = 0;
 
   /**
    * @brief Check whether this scalar is semantically equivalent to \p other.
diff --git a/query_optimizer/expressions/ScalarLiteral.cpp b/query_optimizer/expressions/ScalarLiteral.cpp
index d2ab527..3b1bef5 100644
--- a/query_optimizer/expressions/ScalarLiteral.cpp
+++ b/query_optimizer/expressions/ScalarLiteral.cpp
@@ -22,6 +22,7 @@
 #include <cstddef>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "expressions/scalar/ScalarLiteral.hpp"
@@ -50,7 +51,9 @@
 }
 
 ::quickstep::Scalar *ScalarLiteral::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   return new ::quickstep::ScalarLiteral(value_, value_type_);
 }
 
diff --git a/query_optimizer/expressions/ScalarLiteral.hpp b/query_optimizer/expressions/ScalarLiteral.hpp
index 7fab1d0..fc5e09d 100644
--- a/query_optimizer/expressions/ScalarLiteral.hpp
+++ b/query_optimizer/expressions/ScalarLiteral.hpp
@@ -24,6 +24,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/OptimizerTree.hpp"
@@ -80,7 +81,9 @@
   }
 
   ::quickstep::Scalar* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   bool equals(const ScalarPtr &other) const override;
 
diff --git a/query_optimizer/expressions/SearchedCase.cpp b/query_optimizer/expressions/SearchedCase.cpp
index c53e030..8e40b7b 100644
--- a/query_optimizer/expressions/SearchedCase.cpp
+++ b/query_optimizer/expressions/SearchedCase.cpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <utility>
 #include <vector>
 
@@ -114,15 +115,21 @@
 }
 
 ::quickstep::Scalar* SearchedCase::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   std::vector<std::unique_ptr<quickstep::Predicate>> when_predicates;
+  when_predicates.reserve(condition_predicates_.size());
   for (const PredicatePtr &predicate : condition_predicates_) {
-    when_predicates.emplace_back(predicate->concretize(substitution_map));
+    when_predicates.emplace_back(
+        predicate->concretize(substitution_map, left_expr_ids, right_expr_ids));
   }
 
   std::vector<std::unique_ptr<quickstep::Scalar>> result_expressions;
+  result_expressions.reserve(conditional_result_expressions_.size());
   for (const ScalarPtr &expression : conditional_result_expressions_) {
-    result_expressions.emplace_back(expression->concretize(substitution_map));
+    result_expressions.emplace_back(
+        expression->concretize(substitution_map, left_expr_ids, right_expr_ids));
   }
 
   std::unique_ptr<quickstep::Scalar> else_result_expression;
@@ -131,14 +138,14 @@
         new quickstep::ScalarLiteral(value_type_.makeNullValue(), value_type_));
   } else {
     else_result_expression.reset(
-        else_result_expression_->concretize(substitution_map));
+        else_result_expression_->concretize(substitution_map, left_expr_ids, right_expr_ids));
   }
 
   return new quickstep::ScalarCaseExpression(
       value_type_,
       std::move(when_predicates),
       std::move(result_expressions),
-      else_result_expression_->concretize(substitution_map));
+      else_result_expression_->concretize(substitution_map, left_expr_ids, right_expr_ids));
 }
 
 void SearchedCase::getFieldStringItems(
diff --git a/query_optimizer/expressions/SearchedCase.hpp b/query_optimizer/expressions/SearchedCase.hpp
index 3466396..8744642 100644
--- a/query_optimizer/expressions/SearchedCase.hpp
+++ b/query_optimizer/expressions/SearchedCase.hpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "expressions/scalar/Scalar.hpp"
@@ -101,7 +102,9 @@
       const std::vector<ExpressionPtr> &new_children) const override;
 
   ::quickstep::Scalar* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*>& substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   /**
    * @brief Creates an immutable SearchedCase.
diff --git a/query_optimizer/expressions/SimpleCase.cpp b/query_optimizer/expressions/SimpleCase.cpp
index f11c8c8..21ee244 100644
--- a/query_optimizer/expressions/SimpleCase.cpp
+++ b/query_optimizer/expressions/SimpleCase.cpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <utility>
 #include <vector>
 
@@ -133,8 +134,11 @@
 }
 
 ::quickstep::Scalar* SimpleCase::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   std::vector<std::unique_ptr<quickstep::Predicate>> when_predicates;
+  when_predicates.reserve(condition_operands_.size());
   for (const ScalarPtr &condition_operand : condition_operands_) {
     const PredicatePtr predicate =
         ComparisonExpression::Create(
@@ -145,6 +149,7 @@
   }
 
   std::vector<std::unique_ptr<quickstep::Scalar>> result_expressions;
+  result_expressions.reserve(conditional_result_expressions_.size());
   for (const ScalarPtr &expression : conditional_result_expressions_) {
     result_expressions.emplace_back(expression->concretize(substitution_map));
   }
diff --git a/query_optimizer/expressions/SimpleCase.hpp b/query_optimizer/expressions/SimpleCase.hpp
index b42c034..e05c4ef 100644
--- a/query_optimizer/expressions/SimpleCase.hpp
+++ b/query_optimizer/expressions/SimpleCase.hpp
@@ -24,6 +24,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "expressions/scalar/Scalar.hpp"
@@ -109,7 +110,9 @@
       const std::vector<ExpressionPtr> &new_children) const override;
 
   ::quickstep::Scalar* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*>& substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   bool equals(const ScalarPtr &other) const override;
 
diff --git a/query_optimizer/expressions/SubqueryExpression.cpp b/query_optimizer/expressions/SubqueryExpression.cpp
index bc5a6d3..b6c4772 100644
--- a/query_optimizer/expressions/SubqueryExpression.cpp
+++ b/query_optimizer/expressions/SubqueryExpression.cpp
@@ -21,6 +21,7 @@
 
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/OptimizerTree.hpp"
@@ -38,7 +39,9 @@
 namespace expressions {
 
 ::quickstep::Scalar* SubqueryExpression::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   LOG(FATAL) << "SubqueryExpression should not be concretized";
 }
 
diff --git a/query_optimizer/expressions/SubqueryExpression.hpp b/query_optimizer/expressions/SubqueryExpression.hpp
index 184bc8c..96bf204 100644
--- a/query_optimizer/expressions/SubqueryExpression.hpp
+++ b/query_optimizer/expressions/SubqueryExpression.hpp
@@ -23,6 +23,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/expressions/AttributeReference.hpp"
@@ -87,7 +88,9 @@
   }
 
   ::quickstep::Scalar* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   /**
    * @brief Creates a subquery expression.
diff --git a/query_optimizer/expressions/UnaryExpression.cpp b/query_optimizer/expressions/UnaryExpression.cpp
index b448553..4d91e03 100644
--- a/query_optimizer/expressions/UnaryExpression.cpp
+++ b/query_optimizer/expressions/UnaryExpression.cpp
@@ -22,6 +22,7 @@
 #include <cstddef>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "expressions/scalar/ScalarUnaryExpression.hpp"
@@ -53,9 +54,11 @@
 }
 
 ::quickstep::Scalar* UnaryExpression::concretize(
-    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const {
+    const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+    const std::unordered_set<ExprId> &left_expr_ids,
+    const std::unordered_set<ExprId> &right_expr_ids) const {
   return new ::quickstep::ScalarUnaryExpression(
-      operation_, operand_->concretize(substitution_map));
+      operation_, operand_->concretize(substitution_map, left_expr_ids, right_expr_ids));
 }
 
 std::size_t UnaryExpression::computeHash() const {
diff --git a/query_optimizer/expressions/UnaryExpression.hpp b/query_optimizer/expressions/UnaryExpression.hpp
index 9b99377..314ad5d 100644
--- a/query_optimizer/expressions/UnaryExpression.hpp
+++ b/query_optimizer/expressions/UnaryExpression.hpp
@@ -24,6 +24,7 @@
 #include <memory>
 #include <string>
 #include <unordered_map>
+#include <unordered_set>
 #include <vector>
 
 #include "query_optimizer/expressions/AttributeReference.hpp"
@@ -84,7 +85,9 @@
   }
 
   ::quickstep::Scalar* concretize(
-      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map) const override;
+      const std::unordered_map<ExprId, const CatalogAttribute*> &substitution_map,
+      const std::unordered_set<ExprId> &left_expr_ids = std::unordered_set<ExprId>(),
+      const std::unordered_set<ExprId> &right_expr_ids = std::unordered_set<ExprId>()) const override;
 
   bool equals(const ScalarPtr &other) const override;
 
diff --git a/query_optimizer/tests/execution_generator/Select.test b/query_optimizer/tests/execution_generator/Select.test
index 494e759..ee9c18e 100644
--- a/query_optimizer/tests/execution_generator/Select.test
+++ b/query_optimizer/tests/execution_generator/Select.test
@@ -269,7 +269,6 @@
 +-----------+--------------------+
 ==
 
-# The execution engine currently does not support self-join.
 SELECT a.int_col,
        a.int_col*b.int_col,
        b.long_col
@@ -277,7 +276,32 @@
      test AS b
 WHERE a.int_col*b.int_col = b.long_col;
 --
-ERROR: NestedLoopsJoin does not support self-join yet
++-----------+---------------------+--------------------+
+|int_col    |(a.int_col*b.int_col)|long_col            |
++-----------+---------------------+--------------------+
+|         -1|                    1|                   1|
+|          2|                    4|                   4|
+|         -3|                    9|                   9|
+|          4|                   16|                  16|
+|         -5|                   25|                  25|
+|          6|                   36|                  36|
+|         -7|                   49|                  49|
+|          8|                   64|                  64|
+|         -9|                   81|                  81|
+|        -11|                  121|                 121|
+|         12|                  144|                 144|
+|        -13|                  169|                 169|
+|         14|                  196|                 196|
+|        -15|                  225|                 225|
+|         16|                  256|                 256|
+|        -17|                  289|                 289|
+|         18|                  324|                 324|
+|        -19|                  361|                 361|
+|        -21|                  441|                 441|
+|         22|                  484|                 484|
+|        -23|                  529|                 529|
+|         24|                  576|                 576|
++-----------+---------------------+--------------------+
 ==
 
 # The nested loops join is not a self-join, because the predicate "a.int_col<10" is pushed under the join, which results
@@ -305,14 +329,38 @@
 +-----------+---------------------+--------------------+
 ==
 
-# Hash join does not support the self-join.
 SELECT a.int_col,
        b.int_col
 FROM test AS a,
      test AS b
 WHERE a.int_col = b.int_col;
 --
-ERROR: Self-join is not supported
++-----------+-----------+
+|int_col    |int_col    |
++-----------+-----------+
+|         -1|         -1|
+|          2|          2|
+|         -3|         -3|
+|          4|          4|
+|         -5|         -5|
+|          6|          6|
+|         -7|         -7|
+|          8|          8|
+|         -9|         -9|
+|        -11|        -11|
+|         12|         12|
+|        -13|        -13|
+|         14|         14|
+|        -15|        -15|
+|         16|         16|
+|        -17|        -17|
+|         18|         18|
+|        -19|        -19|
+|        -21|        -21|
+|         22|         22|
+|        -23|        -23|
+|         24|         24|
++-----------+-----------+
 ==
 
 # This is not a self-join, because there is a Select under the HashJoin for "a.long_col < 50".
diff --git a/relational_operators/HashJoinOperator.cpp b/relational_operators/HashJoinOperator.cpp
index 4083bd3..f08de9d 100644
--- a/relational_operators/HashJoinOperator.cpp
+++ b/relational_operators/HashJoinOperator.cpp
@@ -72,7 +72,7 @@
 // Functor passed to HashTable::getAllFromValueAccessor() to collect matching
 // tuples from the inner relation. It stores matching tuple ID pairs
 // in an unordered_map keyed by inner block ID and a vector of
-// pairs of (build-tupleID, probe-tuple-ID).
+// pairs of (probe-tupleID, build-tuple-ID).
 class VectorsOfPairsJoinedTuplesCollector {
  public:
   VectorsOfPairsJoinedTuplesCollector() {
@@ -81,7 +81,7 @@
   template <typename ValueAccessorT>
   inline void operator()(const ValueAccessorT &accessor,
                          const TupleReference &tref) {
-    joined_tuples_[tref.block].emplace_back(tref.tuple, accessor.getCurrentPosition());
+    joined_tuples_[tref.block].emplace_back(accessor.getCurrentPosition(), tref.tuple);
   }
 
   // Get a mutable pointer to the collected map of joined tuple ID pairs. The
@@ -102,7 +102,7 @@
 };
 
 // Another collector using an unordered_map keyed on inner block just like above,
-// except that it uses of a pair of (build-tupleIDs-vector, probe-tuple-IDs-vector).
+// except that it uses of a pair of (probe-tupleIDs-vector, build-tuple-IDs-vector).
 class PairsOfVectorsJoinedTuplesCollector {
  public:
   PairsOfVectorsJoinedTuplesCollector() {
@@ -112,8 +112,8 @@
   inline void operator()(const ValueAccessorT &accessor,
                          const TupleReference &tref) {
     auto &entry = joined_tuples_[tref.block];
-    entry.first.emplace_back(tref.tuple);
-    entry.second.emplace_back(accessor.getCurrentPosition());
+    entry.first.emplace_back(accessor.getCurrentPosition());
+    entry.second.emplace_back(tref.tuple);
   }
 
   // Get a mutable pointer to the collected map of joined tuple ID pairs. The
@@ -151,7 +151,8 @@
   template <typename ValueAccessorT>
   inline void operator()(const ValueAccessorT &accessor,
                          const TupleReference &tref) {
-    joined_tuples_[tref.block].emplace_back(tref.tuple, accessor.getCurrentPosition());
+    // <probe-tid, build-tid>.
+    joined_tuples_[tref.block].emplace_back(accessor.getCurrentPosition(), tref.tuple);
   }
 
   template <typename ValueAccessorT>
@@ -165,7 +166,7 @@
   }
 
  private:
-  std::unordered_map<block_id, std::vector<std::pair<tuple_id, tuple_id>>> joined_tuples_;
+  std::unordered_map<block_id, VectorOfTupleIdPair> joined_tuples_;
   // BitVector on the probe relation. 1 if the corresponding tuple has no match.
   TupleIdSequence *filter_;
 };
@@ -490,9 +491,6 @@
         &collector);
   }
 
-  const relation_id build_relation_id = build_relation_.getID();
-  const relation_id probe_relation_id = probe_relation_.getID();
-
   for (std::pair<const block_id, VectorOfTupleIdPair>
            &build_block_entry : *collector.getJoinedTuples()) {
     BlockReference build_block =
@@ -515,11 +513,9 @@
 
       for (const std::pair<tuple_id, tuple_id> &hash_match
            : build_block_entry.second) {
-        if (residual_predicate_->matchesForJoinedTuples(*build_accessor,
-                                                        build_relation_id,
+        if (residual_predicate_->matchesForJoinedTuples(*probe_accessor,
                                                         hash_match.first,
-                                                        *probe_accessor,
-                                                        probe_relation_id,
+                                                        *build_accessor,
                                                         hash_match.second)) {
           filtered_matches.emplace_back(hash_match);
         }
@@ -533,10 +529,8 @@
     for (auto selection_cit = selection_.begin();
          selection_cit != selection_.end();
          ++selection_cit) {
-      temp_result.addColumn((*selection_cit)->getAllValuesForJoin(build_relation_id,
+      temp_result.addColumn((*selection_cit)->getAllValuesForJoin(probe_accessor,
                                                                   build_accessor.get(),
-                                                                  probe_relation_id,
-                                                                  probe_accessor,
                                                                   build_block_entry.second,
                                                                   cv_cache.get()));
     }
@@ -562,9 +556,6 @@
         &collector);
   }
 
-  const relation_id build_relation_id = build_relation_.getID();
-  const relation_id probe_relation_id = probe_relation_.getID();
-
   constexpr std::size_t kNumIndexes = 3u;
   constexpr std::size_t kBuildIndex = 0, kProbeIndex = 1u, kTempIndex = 2u;
 
@@ -584,11 +575,15 @@
       accessor_attribute_map[kTempIndex].second[dest_attr] = non_trivial_expressions.size();
       non_trivial_expressions.emplace_back(scalar.get());
     } else {
-      const CatalogAttribute &attr = static_cast<const ScalarAttribute *>(scalar.get())->getAttribute();
-      const attribute_id attr_id = attr.getID();
-      if (attr.getParent().getID() == build_relation_id) {
+      const Scalar::JoinSide join_side = scalar->join_side();
+      DCHECK(join_side != Scalar::kNone);
+
+      const attribute_id attr_id =
+          static_cast<const ScalarAttribute *>(scalar.get())->getAttribute().getID();
+      if (join_side == Scalar::kRightSide) {
         accessor_attribute_map[kBuildIndex].second[dest_attr] = attr_id;
       } else {
+        DCHECK(join_side == Scalar::kLeftSide);
         accessor_attribute_map[kProbeIndex].second[dest_attr] = attr_id;
       }
     }
@@ -601,8 +596,8 @@
         storage_manager_->getBlock(build_block_entry.first, build_relation_);
     const TupleStorageSubBlock &build_store = build_block->getTupleStorageSubBlock();
     std::unique_ptr<ValueAccessor> build_accessor(build_store.createValueAccessor());
-    const std::vector<tuple_id> &build_tids = build_block_entry.second.first;
-    const std::vector<tuple_id> &probe_tids = build_block_entry.second.second;
+    const std::vector<tuple_id> &build_tids = build_block_entry.second.second;
+    const std::vector<tuple_id> &probe_tids = build_block_entry.second.first;
 
     // Evaluate '*residual_predicate_', if any.
     //
@@ -618,14 +613,12 @@
       PairOfTupleIdVector filtered_matches;
 
       for (std::size_t i = 0; i < build_tids.size(); ++i) {
-        if (residual_predicate_->matchesForJoinedTuples(*build_accessor,
-                                                        build_relation_id,
-                                                        build_tids[i],
-                                                        *probe_accessor,
-                                                        probe_relation_id,
-                                                        probe_tids[i])) {
-          filtered_matches.first.emplace_back(build_tids[i]);
-          filtered_matches.second.emplace_back(probe_tids[i]);
+        if (residual_predicate_->matchesForJoinedTuples(*probe_accessor,
+                                                        probe_tids[i],
+                                                        *build_accessor,
+                                                        build_tids[i])) {
+          filtered_matches.first.emplace_back(probe_tids[i]);
+          filtered_matches.second.emplace_back(build_tids[i]);
         }
       }
 
@@ -646,15 +639,13 @@
       // zip our two vectors together.
       VectorOfTupleIdPair zipped_joined_tuple_ids;
       for (std::size_t i = 0; i < build_tids.size(); ++i) {
-        zipped_joined_tuple_ids.emplace_back(build_tids[i], probe_tids[i]);
+        zipped_joined_tuple_ids.emplace_back(probe_tids[i], build_tids[i]);
       }
 
       ColumnVectorCache cv_cache;
       for (const Scalar *scalar : non_trivial_expressions) {
-        temp_result.addColumn(scalar->getAllValuesForJoin(build_relation_id,
+        temp_result.addColumn(scalar->getAllValuesForJoin(probe_accessor,
                                                           build_accessor.get(),
-                                                          probe_relation_id,
-                                                          probe_accessor,
                                                           zipped_joined_tuple_ids,
                                                           &cv_cache));
       }
@@ -690,9 +681,6 @@
 }
 
 void HashSemiJoinWorkOrder::executeWithResidualPredicate() {
-  const relation_id build_relation_id = build_relation_.getID();
-  const relation_id probe_relation_id = probe_relation_.getID();
-
   BlockReference probe_block = storage_manager_->getBlock(block_id_,
                                                           probe_relation_);
   const TupleStorageSubBlock &probe_store = probe_block->getTupleStorageSubBlock();
@@ -752,11 +740,9 @@
         // probe side, skip it.
         continue;
       }
-      if (residual_predicate_->matchesForJoinedTuples(*build_accessor,
-                                                      build_relation_id,
+      if (residual_predicate_->matchesForJoinedTuples(*probe_accessor,
                                                       hash_match.first,
-                                                      *probe_accessor,
-                                                      probe_relation_id,
+                                                      *build_accessor,
                                                       hash_match.second)) {
         filter.set(hash_match.second);
       }
@@ -910,9 +896,6 @@
 }
 
 void HashAntiJoinWorkOrder::executeWithResidualPredicate() {
-  const relation_id build_relation_id = build_relation_.getID();
-  const relation_id probe_relation_id = probe_relation_.getID();
-
   BlockReference probe_block = storage_manager_->getBlock(block_id_,
                                                           probe_relation_);
   const TupleStorageSubBlock &probe_store = probe_block->getTupleStorageSubBlock();
@@ -970,11 +953,9 @@
         // We have already seen this tuple, skip it.
         continue;
       }
-      if (residual_predicate_->matchesForJoinedTuples(*build_accessor,
-                                                      build_relation_id,
+      if (residual_predicate_->matchesForJoinedTuples(*probe_accessor,
                                                       hash_match.first,
-                                                      *probe_accessor,
-                                                      probe_relation_id,
+                                                      *build_accessor,
                                                       hash_match.second)) {
         // Note that the existence map marks a match as false, as needed by the
         // anti join definition.
@@ -1008,9 +989,6 @@
 void HashOuterJoinWorkOrder::execute() {
   output_destination_->setInputPartitionId(partition_id_);
 
-  const relation_id build_relation_id = build_relation_.getID();
-  const relation_id probe_relation_id = probe_relation_.getID();
-
   const BlockReference probe_block = storage_manager_->getBlock(block_id_,
                                                                 probe_relation_);
   const TupleStorageSubBlock &probe_store = probe_block->getTupleStorageSubBlock();
@@ -1061,10 +1039,8 @@
          ++selection_it) {
       temp_result.addColumn(
           (*selection_it)->getAllValuesForJoin(
-              build_relation_id,
-              build_accessor.get(),
-              probe_relation_id,
               probe_accessor.get(),
+              build_accessor.get(),
               build_block_entry.second,
               cv_cache.get()));
     }
diff --git a/relational_operators/NestedLoopsJoinOperator.cpp b/relational_operators/NestedLoopsJoinOperator.cpp
index 658f84b..8be9cb3 100644
--- a/relational_operators/NestedLoopsJoinOperator.cpp
+++ b/relational_operators/NestedLoopsJoinOperator.cpp
@@ -407,9 +407,6 @@
 template <bool LEFT_PACKED, bool RIGHT_PACKED>
 void NestedLoopsJoinWorkOrder::executeHelper(const TupleStorageSubBlock &left_store,
                                              const TupleStorageSubBlock &right_store) {
-  const relation_id left_input_relation_id = left_input_relation_.getID();
-  const relation_id right_input_relation_id = right_input_relation_.getID();
-
   const tuple_id left_max_tid = left_store.getMaxTupleID();
   const tuple_id right_max_tid = right_store.getMaxTupleID();
 
@@ -428,10 +425,8 @@
         if (RIGHT_PACKED || right_store.hasTupleWithID(right_tid)) {
           // For each tuple in the right block...
           if (join_predicate_->matchesForJoinedTuples(*left_accessor,
-                                                      left_input_relation_id,
                                                       left_tid,
                                                       *right_accessor,
-                                                      right_input_relation_id,
                                                       right_tid)) {
             joined_tuple_ids.emplace_back(left_tid, right_tid);
           }
@@ -460,9 +455,7 @@
     for (vector<unique_ptr<const Scalar>>::const_iterator selection_cit = selection_.begin();
          selection_cit != selection_.end();
          ++selection_cit) {
-      temp_result.addColumn((*selection_cit)->getAllValuesForJoin(left_input_relation_id,
-                                                                  left_accessor.get(),
-                                                                  right_input_relation_id,
+      temp_result.addColumn((*selection_cit)->getAllValuesForJoin(left_accessor.get(),
                                                                   right_accessor.get(),
                                                                   joined_tuple_ids,
                                                                   cv_cache.get()));
diff --git a/relational_operators/tests/HashJoinOperator_unittest.cpp b/relational_operators/tests/HashJoinOperator_unittest.cpp
index eeeca4b..1ea1a37 100644
--- a/relational_operators/tests/HashJoinOperator_unittest.cpp
+++ b/relational_operators/tests/HashJoinOperator_unittest.cpp
@@ -432,7 +432,7 @@
 
   // Create the prober operator with one selection attribute.
   const QueryContext::scalar_group_id selection_index = query_context_proto.scalar_groups_size();
-  ScalarAttribute scalar_attr(dim_col_long);
+  ScalarAttribute scalar_attr(dim_col_long, Scalar::kRightSide);
   query_context_proto.add_scalar_groups()->add_scalars()->MergeFrom(scalar_attr.getProto());
 
   // Create result_table, owned by db_.
@@ -581,9 +581,9 @@
   const QueryContext::scalar_group_id selection_index = query_context_proto.scalar_groups_size();
   serialization::QueryContext::ScalarGroup *scalar_group_proto = query_context_proto.add_scalar_groups();
 
-  ScalarAttribute scalar_attr_dim(dim_col_long);
+  ScalarAttribute scalar_attr_dim(dim_col_long, Scalar::kRightSide);
   scalar_group_proto->add_scalars()->MergeFrom(scalar_attr_dim.getProto());
-  ScalarAttribute scalar_attr_fact(fact_col_long);
+  ScalarAttribute scalar_attr_fact(fact_col_long, Scalar::kLeftSide);
   scalar_group_proto->add_scalars()->MergeFrom(scalar_attr_fact.getProto());
 
   // Create result_table, owned by db_.
@@ -745,7 +745,7 @@
 
   // Create prober operator with one selection attribute.
   const QueryContext::scalar_group_id selection_index = query_context_proto.scalar_groups_size();
-  ScalarAttribute scalar_attr(dim_col_long);
+  ScalarAttribute scalar_attr(dim_col_long, Scalar::kRightSide);
   query_context_proto.add_scalar_groups()->add_scalars()->MergeFrom(scalar_attr.getProto());
 
   // Create result_table, owned by db_.
@@ -887,9 +887,9 @@
   const QueryContext::scalar_group_id selection_index = query_context_proto.scalar_groups_size();
   serialization::QueryContext::ScalarGroup *scalar_group_proto = query_context_proto.add_scalar_groups();
 
-  ScalarAttribute scalar_attr_dim(dim_col_long);
+  ScalarAttribute scalar_attr_dim(dim_col_long, Scalar::kRightSide);
   scalar_group_proto->add_scalars()->MergeFrom(scalar_attr_dim.getProto());
-  ScalarAttribute scalar_attr_fact(fact_col_long);
+  ScalarAttribute scalar_attr_fact(fact_col_long, Scalar::kLeftSide);
   scalar_group_proto->add_scalars()->MergeFrom(scalar_attr_fact.getProto());
 
   // Create result_table, owned by db_.
@@ -1063,9 +1063,9 @@
   const QueryContext::scalar_group_id selection_index = query_context_proto.scalar_groups_size();
   serialization::QueryContext::ScalarGroup *scalar_group_proto = query_context_proto.add_scalar_groups();
 
-  ScalarAttribute scalar_attr_dim(dim_col_long);
+  ScalarAttribute scalar_attr_dim(dim_col_long, Scalar::kRightSide);
   scalar_group_proto->add_scalars()->MergeFrom(scalar_attr_dim.getProto());
-  ScalarAttribute scalar_attr_fact(fact_col_long);
+  ScalarAttribute scalar_attr_fact(fact_col_long, Scalar::kLeftSide);
   scalar_group_proto->add_scalars()->MergeFrom(scalar_attr_fact.getProto());
 
   // Create result_table, owned by db_.
@@ -1244,9 +1244,9 @@
   const QueryContext::scalar_group_id selection_index = query_context_proto.scalar_groups_size();
   serialization::QueryContext::ScalarGroup *scalar_group_proto = query_context_proto.add_scalar_groups();
 
-  ScalarAttribute scalar_attr_dim(dim_col_long);
+  ScalarAttribute scalar_attr_dim(dim_col_long, Scalar::kRightSide);
   scalar_group_proto->add_scalars()->MergeFrom(scalar_attr_dim.getProto());
-  ScalarAttribute scalar_attr_fact(fact_col_long);
+  ScalarAttribute scalar_attr_fact(fact_col_long, Scalar::kLeftSide);
   scalar_group_proto->add_scalars()->MergeFrom(scalar_attr_fact.getProto());
 
   // Create result_table, owned by db_.
@@ -1269,7 +1269,7 @@
   unique_ptr<Predicate> residual_pred(new ComparisonPredicate(
       ComparisonFactory::GetComparison(
           ComparisonID::kLess),
-          new ScalarAttribute(dim_col_long),
+          new ScalarAttribute(dim_col_long, Scalar::kRightSide),
           new ScalarLiteral(TypedValue(static_cast<std::int64_t>(15)), LongType::InstanceNonNullable())));
 
   std::vector<attribute_id> fact_key_attrs;
@@ -1436,7 +1436,7 @@
 
   // Create the prober operator with one selection attribute.
   const QueryContext::scalar_group_id selection_index = query_context_proto.scalar_groups_size();
-  ScalarAttribute scalar_attr(dim_col_long);
+  ScalarAttribute scalar_attr(dim_col_long, Scalar::kRightSide);
   query_context_proto.add_scalar_groups()->add_scalars()->MergeFrom(scalar_attr.getProto());
 
   // Create result_table, owned by db_.
@@ -1580,9 +1580,9 @@
   const QueryContext::scalar_group_id selection_index = query_context_proto.scalar_groups_size();
   serialization::QueryContext::ScalarGroup *scalar_group_proto = query_context_proto.add_scalar_groups();
 
-  ScalarAttribute scalar_attr_dim(dim_col_long);
+  ScalarAttribute scalar_attr_dim(dim_col_long, Scalar::kRightSide);
   scalar_group_proto->add_scalars()->MergeFrom(scalar_attr_dim.getProto());
-  ScalarAttribute scalar_attr_fact(fact_col_long);
+  ScalarAttribute scalar_attr_fact(fact_col_long, Scalar::kLeftSide);
   scalar_group_proto->add_scalars()->MergeFrom(scalar_attr_fact.getProto());
 
   // Create result_table, owned by db_.
@@ -1752,9 +1752,9 @@
   const QueryContext::scalar_group_id selection_index = query_context_proto.scalar_groups_size();
   serialization::QueryContext::ScalarGroup *scalar_group_proto = query_context_proto.add_scalar_groups();
 
-  ScalarAttribute scalar_attr_dim(dim_col_long);
+  ScalarAttribute scalar_attr_dim(dim_col_long, Scalar::kRightSide);
   scalar_group_proto->add_scalars()->MergeFrom(scalar_attr_dim.getProto());
-  ScalarAttribute scalar_attr_fact(fact_col_long);
+  ScalarAttribute scalar_attr_fact(fact_col_long, Scalar::kLeftSide);
   scalar_group_proto->add_scalars()->MergeFrom(scalar_attr_fact.getProto());
 
   // Create result_table, owned by db_.
@@ -1777,7 +1777,7 @@
   unique_ptr<Predicate> residual_pred(new ComparisonPredicate(
       ComparisonFactory::GetComparison(
           ComparisonID::kLess),
-          new ScalarAttribute(dim_col_long),
+          new ScalarAttribute(dim_col_long, Scalar::kRightSide),
           new ScalarLiteral(TypedValue(static_cast<std::int64_t>(15)), LongType::InstanceNonNullable())));
 
   const QueryContext::predicate_id residual_pred_index = query_context_proto.predicates_size();