dkubb/axiom-optimizer

# encoding: utf-8

module Axiom
  class Optimizer
    module Algebra

      # Abstract base class representing Join optimizations
      class Join < Relation::Operation::Combination

        CONTRADICTION = Axiom::Function::Proposition::Contradiction.instance

      private

        # Return the key to join the operations with
        #
        # @return [Header]
        #
        # @todo find a minimal key from the header
        #
        # @api private
        def join_key
          operation.join_header
        end

        # Return a predicate that matches every tuple in the materialized operand
        #
        # @return [Function]
        #
        # @api private
        def materialized_predicate
          matching_projection.reduce(CONTRADICTION) do |accumulator, element|
            accumulator.or(element.predicate)
          end.optimize
        end

        # Optimize when operands' headers are equal
        class EqualHeaders < self

          # Test if the operands' headers are equal
          #
          # @return [Boolean]
          #
          # @api private
          def optimizable?
            left.header.eql?(right.header)
          end

          # A Join with equal headers is an Intersection
          #
          # @return [Algebra::Intersection]
          #
          # @api private
          def optimize
            left.intersect(right)
          end

        end # class EqualHeaders

        # Optimize when operands' headers are disjoint
        class DisjointHeaders < self

          # Test if the operands' headers are disjoint
          #
          # @return [Boolean]
          #
          # @api private
          def optimizable?
            (left.header & right.header).none?
          end

          # A Join with disjoint headers is a Product
          #
          # @return [Algebra::Product]
          #
          # @api private
          def optimize
            left.product(right)
          end

        end # class EqualHeaders

        # Optimize when the left operand is materialized
        class MaterializedLeft < self

          # Test if the left operand is materialized
          #
          # @return [Boolean]
          #
          # @api private
          def optimizable?
            left.materialized? && !right_matching_left?
          end

          # Return the join of the left and right with the right restricted
          #
          # @return [Algebra::Join]
          #
          # @api private
          def optimize
            left.join(right.restrict(materialized_predicate))
          end

        private

          # Test if the right operand is a restriction matching the left
          #
          # @return [Boolean]
          #
          # @api private
          def right_matching_left?
            right.kind_of?(Axiom::Algebra::Restriction) && right.predicate.eql?(materialized_predicate)
          end

          # Return a the matching projection of the materializd relation
          #
          # @return [Projection]
          #
          # @api private
          def matching_projection
            left.project(join_key)
          end

        end # class MaterializedLeft

        # Optimize when the right operand is materialized
        class MaterializedRight < self

          # Test if the right operand is materialized
          #
          # @return [Boolean]
          #
          # @api private
          def optimizable?
            right.materialized? && !left_matching_right?
          end

          # Return the join of the left and right with the left restricted
          #
          # @return [Algebra::Join]
          #
          # @api private
          def optimize
            left.restrict(materialized_predicate).join(right)
          end

        private

          # Test if the left operand is a restriction matching the right
          #
          # @return [Boolean]
          #
          # @api private
          def left_matching_right?
            left.kind_of?(Axiom::Algebra::Restriction) && left.predicate.eql?(materialized_predicate)
          end

          # Return a the matching projection of the materializd relation
          #
          # @return [Projection]
          #
          # @api private
          def matching_projection
            right.project(join_key)
          end

        end # class MaterializedRight

        Axiom::Algebra::Join.optimizer = chain(
          EmptyLeft,
          EmptyRight,
          EqualHeaders,
          DisjointHeaders,
          SortedLeft,
          SortedRight,
          MaterializedOperands,
          MaterializedLeft,
          MaterializedRight,
          UnoptimizedOperands
        )

        memoize :materialized_predicate

      end # class Join
    end # module Algebra
  end # class Optimizer
end # module Axiom