class NoSE::Search::CompletePlanConstraints

Constraints that force each query to have an available plan

Public Class Methods

add_query_constraints(query, q, constraints, problem) click to toggle source

Add the discovered constraints to the problem

# File lib/nose/search/constraints.rb, line 57
def self.add_query_constraints(query, q, constraints, problem)
  constraints.each do |entities, constraint|
    name = "q#{q}_#{entities.map(&:name).join '_'}" \
        if ENV['NOSE_LOG'] == 'debug'

    # If this is a support query, then we might not need a plan
    if query.is_a? SupportQuery
      # Find the index associated with the support query and make
      # the requirement of a plan conditional on this index
      index_var = if problem.data[:by_id_graph]
                    problem.index_vars[query.index.to_id_graph]
                  else
                    problem.index_vars[query.index]
                  end
      next if index_var.nil?

      constr = MIPPeR::Constraint.new constraint + index_var * -1.0,
                                      :==, 0, name
    else
      constr = MIPPeR::Constraint.new constraint, :==, 1, name
    end

    problem.model << constr
  end
end
apply_query(query, q, problem) click to toggle source

Add complete query plan constraints

# File lib/nose/search/constraints.rb, line 84
def self.apply_query(query, q, problem)
  entities = query.join_order
  query_constraints = Hash[entities.each_cons(2).map do |e, next_e|
    [[e, next_e], MIPPeR::LinExpr.new]
  end]

  # Add the sentinel entities at the end and beginning
  last = Entity.new '__LAST__'
  query_constraints[[entities.last, last]] = MIPPeR::LinExpr.new
  first = Entity.new '__FIRST__'
  query_constraints[[entities.first, first]] = MIPPeR::LinExpr.new

  problem.data[:costs][query].each do |index, (steps, _)|
    # All indexes should advance a step if possible unless
    # this is either the last step from IDs to entity
    # data or the first step going from data to IDs
    index_step = steps.first
    fail if entities.length > 1 && index.graph.size == 1 && \
            !(steps.last.state.answered? ||
              index_step.parent.is_a?(Plans::RootPlanStep))

    # Join each step in the query graph
    index_var = problem.query_vars[index][query]
    index_entities = index.graph.entities.sort_by do |entity|
      entities.index entity
    end
    index_entities.each_cons(2) do |entity, next_entity|
      # Make sure the constraints go in the correct direction
      if query_constraints.key?([entity, next_entity])
        query_constraints[[entity, next_entity]] += index_var
      else
        query_constraints[[next_entity, entity]] += index_var
      end
    end

    # If this query has been answered, add the jump to the last step
    query_constraints[[entities.last, last]] += index_var \
      if steps.last.state.answered?

    # If this index is the first step, add this index to the beginning
    query_constraints[[entities.first, first]] += index_var \
      if index_step.parent.is_a?(Plans::RootPlanStep)

    # Ensure the previous index is available
    parent_index = index_step.parent.parent_index
    next if parent_index.nil?

    parent_var = problem.query_vars[parent_index][query]
    name = "q#{q}_#{index.key}_parent" if ENV['NOSE_LOG'] == 'debug'
    constr = MIPPeR::Constraint.new index_var * 1.0 + parent_var * -1.0,
                                    :<=, 0, name
    problem.model << constr
  end

  # Ensure we have exactly one index on each component of the query graph
  add_query_constraints query, q, query_constraints, problem
end