class NoSE::Plans::QueryPlanner

A query planner which can construct a tree of query plans

Public Class Methods

new(model, indexes, cost_model) click to toggle source
# File lib/nose/plans/query_planner.rb, line 226
def initialize(model, indexes, cost_model)
  @logger = Logging.logger['nose::query_planner']

  @model = model
  @indexes = indexes
  @cost_model = cost_model
end

Public Instance Methods

find_plans_for_query(query) click to toggle source

Find a tree of plans for the given query @return [QueryPlanTree] @raise [NoPlanException]

# File lib/nose/plans/query_planner.rb, line 237
def find_plans_for_query(query)
  state = QueryState.new query, @model
  state.freeze
  tree = QueryPlanTree.new state, @cost_model

  indexes_by_joins = indexes_for_query(query, state.joins)
  find_plans_for_step tree.root, indexes_by_joins

  if tree.root.children.empty?
    tree = QueryPlanTree.new state, @cost_model
    find_plans_for_step tree.root, indexes_by_joins, prune: false
    fail NoPlanException, "#{query.inspect} #{tree.inspect}"
  end

  @logger.debug { "Plans for #{query.inspect}: #{tree.inspect}" }

  tree
end
min_plan(query) click to toggle source

Get the minimum cost plan for executing this query @return [QueryPlan]

# File lib/nose/plans/query_planner.rb, line 258
def min_plan(query)
  find_plans_for_query(query).min
end

Private Instance Methods

find_nonindexed_steps(parent, state) click to toggle source

Find all possible plan steps not using indexes @return [Array<PlanStep>]

# File lib/nose/plans/query_planner.rb, line 328
def find_nonindexed_steps(parent, state)
  steps = []
  return steps if parent.is_a? RootPlanStep

  [SortPlanStep, FilterPlanStep, LimitPlanStep].each \
    { |step| steps.push step.apply(parent, state) }
  steps.flatten!
  steps.compact!

  steps
end
find_plans_for_step(step, indexes_by_joins, prune: true) click to toggle source

Find possible query plans for a query starting at the given step @return [void]

# File lib/nose/plans/query_planner.rb, line 303
def find_plans_for_step(step, indexes_by_joins, prune: true)
  return if step.state.answered?

  steps = find_steps_for_state step, step.state, indexes_by_joins

  if !steps.empty?
    step.children = steps
    steps.each { |new_step| new_step.calculate_cost @cost_model }
    steps.each do |child_step|
      find_plans_for_step child_step, indexes_by_joins

      # Remove this step if finding a plan from here failed
      if child_step.children.empty? && !child_step.state.answered?
        step.children.delete child_step
      end
    end
  elsif prune
    return if step.is_a?(RootPlanStep) || prune_plan(step.parent)
  else
    step.children = [PrunedPlanStep.new]
  end
end
find_steps_for_state(parent, state, indexes_by_joins) click to toggle source

Get a list of possible next steps for a query in the given state @return [Array<PlanStep>]

# File lib/nose/plans/query_planner.rb, line 342
def find_steps_for_state(parent, state, indexes_by_joins)
  steps = find_nonindexed_steps parent, state
  return steps unless steps.empty?

  # Don't allow indices to be used multiple times
  indexes = (indexes_by_joins[state.joins.first] || Set.new).to_set
  used_indexes = parent.parent_steps.indexes.to_set
  (indexes - used_indexes).each do |index|
    new_step = IndexLookupPlanStep.apply parent, index, state
    next if new_step.nil?

    new_step.add_fields_from_index index
    steps.push new_step
  end

  steps
end
indexes_for_query(query, joins) click to toggle source

Produce indexes possibly useful for this query grouped by the first entity they join on @return [Hash]

# File lib/nose/plans/query_planner.rb, line 267
def indexes_for_query(query, joins)
  indexes_by_joins = Hash.new { |h, k| h[k] = Set.new }
  @indexes.each do |index|
    # Limit indices to those which cross the query path
    next unless index.graph.entities.to_set.subset? \
      query.graph.entities.to_set

    first_entity = joins.find do |entity|
      index.graph.entities.include?(entity)
    end
    indexes_by_joins[first_entity].add index
  end

  indexes_by_joins
end
prune_plan(prune_step) click to toggle source

Remove plans ending with this step in the tree @return true if pruning resulted in an empty tree

# File lib/nose/plans/query_planner.rb, line 285
def prune_plan(prune_step)
  # Walk up the tree and remove the branch for the failed plan
  while prune_step.children.length <= 1 &&
        !prune_step.is_a?(RootPlanStep)
    prune_step = prune_step.parent
    prev_step = prune_step
  end

  # If we reached the root, we have no plan
  return true if prune_step.is_a? RootPlanStep

  prune_step.children.delete prev_step

  false
end