class NoSE::Search::Problem

A representation of a search problem as an ILP

Attributes

data[R]
index_vars[R]
indexes[R]
model[R]
objective_type[R]
objective_value[R]
queries[R]
query_vars[R]
status[R]
updates[R]

Public Class Methods

new(queries, updates, data, objective = Objective::COST) click to toggle source
# File lib/nose/search/problem.rb, line 33
def initialize(queries, updates, data, objective = Objective::COST)
  @queries = queries
  @updates = updates
  @data = data
  @indexes = @data[:costs].flat_map { |_, ic| ic.keys }.uniq
  @logger = Logging.logger['nose::search::problem']
  @status = nil
  @objective_type = objective

  setup_model
end

Public Instance Methods

result() click to toggle source

Return relevant data on the results of the ILP @return [Results]

# File lib/nose/search/problem.rb, line 87
def result
  result = Results.new self, @data[:by_id_graph]
  result.enumerated_indexes = indexes
  result.indexes = selected_indexes

  # TODO: Update for indexes grouped by ID path
  result.total_size = selected_indexes.sum_by(&:size)
  result.total_cost = @objective_value

  result
end
selected_indexes() click to toggle source

Return the selected indices @return [Set<Index>]

# File lib/nose/search/problem.rb, line 76
def selected_indexes
  return if @status.nil?
  return @selected_indexes if @selected_indexes

  @selected_indexes = @index_vars.each_key.select do |index|
    @index_vars[index].value
  end.to_set
end
solve(previous_type = nil) click to toggle source

Run the solver and make the selected indexes available @return [void]

# File lib/nose/search/problem.rb, line 47
def solve(previous_type = nil)
  return unless @status.nil?

  # Run the optimization
  @model.optimize
  @status = model.status
  fail NoSolutionException, @status if @status != :optimized

  # Store the objective value
  @objective_value = @obj_var.value

  if @objective_type != Objective::INDEXES && previous_type.nil?
    solve_next Objective::INDEXES
    return
  elsif !previous_type.nil? && previous_type != Objective::SPACE
    solve_next Objective::SPACE
    return
  elsif @objective_value.nil?
    @objective_value = @model.objective_value
  end

  @logger.debug do
    "Final objective value is #{@objective.inspect}" \
      " = #{@objective_value}"
  end
end
total_cost() click to toggle source

Get the cost of all queries in the workload @return [MIPPeR::LinExpr]

# File lib/nose/search/problem.rb, line 110
def total_cost
  cost = @queries.reduce(MIPPeR::LinExpr.new) do |expr, query|
    expr.add(@indexes.reduce(MIPPeR::LinExpr.new) do |subexpr, index|
      subexpr.add total_query_cost(@data[:costs][query][index],
                                   @query_vars[index][query],
                                   @sort_costs[query][index],
                                   @sort_vars[query][index])
    end)
  end

  cost = add_update_costs cost
  cost
end
total_indexes() click to toggle source

The total number of indexes @return [MIPPeR::LinExpr]

# File lib/nose/search/problem.rb, line 126
def total_indexes
  total = MIPPeR::LinExpr.new
  @index_vars.each_value { |var| total += var * 1.0 }

  total
end
total_size() click to toggle source

Get the size of all indexes in the workload @return [MIPPeR::LinExpr]

# File lib/nose/search/problem.rb, line 101
def total_size
  # TODO: Update for indexes grouped by ID path
  @indexes.map do |index|
    @index_vars[index] * (index.size * 1.0)
  end.reduce(&:+)
end

Private Instance Methods

add_constraints() click to toggle source

Add all necessary constraints to the model @return [void]

# File lib/nose/search/problem.rb, line 284
def add_constraints
  [
    IndexPresenceConstraints,
    SpaceConstraint,
    CompletePlanConstraints
  ].each { |constraint| constraint.apply self }

  @logger.debug do
    "Added #{@model.constraints.count} constraints to model"
  end
end
add_update_costs(min_cost) click to toggle source

Deal with updates which do not require support queries @return [MIPPeR::LinExpr]

# File lib/nose/search/problem.rb, line 298
def add_update_costs(min_cost)
  @updates.each do |update|
    @indexes.each do |index|
      index = index.to_id_graph if data[:by_id_graph]
      next unless update.modifies_index?(index)

      min_cost.add @index_vars[index] *
                   @data[:update_costs][update][index]
    end
  end

  min_cost
end
add_variables() click to toggle source

Initialize query and index variables @return [void]

# File lib/nose/search/problem.rb, line 212
def add_variables
  @index_vars = {}
  @query_vars = {}
  @indexes.each do |index|
    @query_vars[index] = {}
    @queries.each_with_index do |query, q|
      query_var = "q#{q}_#{index.key}" if ENV['NOSE_LOG'] == 'debug'
      var = MIPPeR::Variable.new 0, 1, 0, :binary, query_var
      @model << var
      @query_vars[index][query] = var
    end

    var_name = index.key if ENV['NOSE_LOG'] == 'debug'
    @index_vars[index] = MIPPeR::Variable.new 0, 1, 0, :binary, var_name

    # If needed when grouping by ID graph, add an extra
    # variable for the base index based on the ID graph
    next unless @data[:by_id_graph]
    id_graph = index.to_id_graph
    next if id_graph == index

    # Add a new variable for the ID graph if needed
    unless @index_vars.key? id_graph
      var_name = index.key if ENV['NOSE_LOG'] == 'debug'
      @index_vars[id_graph] = MIPPeR::Variable.new 0, 1, 0, :binary,
                                                   var_name
    end

    # Ensure that the ID graph of this index is present if we use it
    name = "ID_#{id_graph.key}_#{index.key}" \
      if ENV['NOSE_LOG'] == 'debug'
    constr = MIPPeR::Constraint.new @index_vars[id_graph] * 1.0 + \
                                    @index_vars[index] * -1.0,
                                    :>=, 0, name
    @model << constr
  end

  @index_vars.each_value { |var| @model << var }
end
define_objective(var_name = 'objective') click to toggle source

Set the value of the objective function (workload cost) @return [void]

# File lib/nose/search/problem.rb, line 185
def define_objective(var_name = 'objective')
  obj = case @objective_type
        when Objective::COST
          total_cost
        when Objective::SPACE
          total_size
        when Objective::INDEXES
          total_indexes
        end

  # Add the objective function as a variable
  var_name = nil unless ENV['NOSE_LOG'] == 'debug'
  @obj_var = MIPPeR::Variable.new 0, Float::INFINITY, 1.0,
                                  :continuous, var_name
  @model << @obj_var
  @model.update

  @model << MIPPeR::Constraint.new(obj + @obj_var * -1.0, :==, 0.0)

  @logger.debug { "Objective function is #{obj.inspect}" }

  @objective = obj
  @model.sense = :min
end
log_model(type) click to toggle source

Write a model to a temporary file and log the file name @return [void]

# File lib/nose/search/problem.rb, line 155
def log_model(type)
  @logger.debug do
    tmpfile = Tempfile.new ['model', '.mps']
    ObjectSpace.undefine_finalizer tmpfile
    @model.write_mps tmpfile.path
    "#{type} written to #{tmpfile.path}"
  end
end
prepare_sort_costs() click to toggle source

Prepare variables and constraints to account for the cost of sorting @return [void]

# File lib/nose/search/problem.rb, line 254
def prepare_sort_costs
  @sort_costs = {}
  @sort_vars = {}
  @data[:costs].each do |query, index_costs|
    @sort_costs[query] = {}
    @sort_vars[query] = {}

    index_costs.each do |index, (steps, _)|
      sort_step = steps.find { |s| s.is_a?(Plans::SortPlanStep) }
      next if sort_step.nil?

      @sort_costs[query][index] ||= sort_step.cost
      q = @queries.index query

      name = "s#{q}" if ENV['NOSE_LOG'] == 'debug'
      sort_var = MIPPeR::Variable.new 0, 1, 0, :binary, name
      @sort_vars[query][index] ||= sort_var
      @model << sort_var

      name = "q#{q}_#{index.key}_sort" if ENV['NOSE_LOG'] == 'debug'
      constr = MIPPeR::Constraint.new @sort_vars[query][index] * 1.0 +
                                      @query_vars[index][query] * -1.0,
                                      :>=, 0, name
      @model << constr
    end
  end
end
setup_model() click to toggle source

Build the ILP by creating all the variables and constraints @return [void]

# File lib/nose/search/problem.rb, line 166
def setup_model
  # Set up solver environment
  @model = MIPPeR::CbcModel.new

  add_variables
  prepare_sort_costs
  @model.update

  add_constraints
  define_objective
  @model.update

  log_model 'Model'
end
solve_next(objective_type) click to toggle source

Pin the current objective value and set a new objective @return [void]

# File lib/nose/search/problem.rb, line 137
def solve_next(objective_type)
  @obj_var.lower_bound = @objective_value
  @obj_var.upper_bound = @objective_value

  if objective_type == Objective::INDEXES
    @objective_type = Objective::INDEXES
    define_objective 'objective_indexes'
  elsif objective_type == Objective::SPACE
    @objective_type = Objective::SPACE
    define_objective 'objective_space'
  end

  @status = nil
  solve objective_type
end
total_query_cost(cost, query_var, sort_cost, sort_var) click to toggle source

Get the total cost of the query for the objective function @return [MIPPeR::LinExpr]

# File lib/nose/search/problem.rb, line 314
def total_query_cost(cost, query_var, sort_cost, sort_var)
  return MIPPeR::LinExpr.new if cost.nil?
  query_cost = cost.last * 1.0

  cost_expr = query_var * query_cost
  cost_expr += sort_var * sort_cost unless sort_cost.nil?

  cost_expr
end