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