class NoSE::IndexEnumerator

Produces potential indices to be used in schemas

Public Class Methods

new(workload) click to toggle source
# File lib/nose/enumerator.rb, line 8
def initialize(workload)
  @logger = Logging.logger['nose::enumerator']

  @workload = workload
end

Public Instance Methods

indexes_for_query(query) click to toggle source

Produce all possible indices for a given query @return [Array<Index>]

# File lib/nose/enumerator.rb, line 16
def indexes_for_query(query)
  @logger.debug "Enumerating indexes for query #{query.text}"

  range = if query.range_field.nil?
            query.order
          else
            [query.range_field] + query.order
          end

  eq = query.eq_fields.group_by(&:parent)
  eq.default_proc = ->(*) { [] }

  range = range.group_by(&:parent)
  range.default_proc = ->(*) { [] }

  query.graph.subgraphs.flat_map do |graph|
    indexes_for_graph graph, query.select, eq, range
  end.uniq << query.materialize_view
end
indexes_for_workload(additional_indexes = [], by_id_graph = false) click to toggle source

Produce all possible indices for a given workload @return [Set<Index>]

# File lib/nose/enumerator.rb, line 38
def indexes_for_workload(additional_indexes = [], by_id_graph = false)
  queries = @workload.queries
  indexes = Parallel.map(queries) do |query|
    indexes_for_query(query).to_a
  end.inject(additional_indexes, &:+)

  # Add indexes generated for support queries
  supporting = support_indexes indexes, by_id_graph
  supporting += support_indexes supporting, by_id_graph
  indexes += supporting

  # Deduplicate indexes, combine them and deduplicate again
  indexes.uniq!
  combine_indexes indexes
  indexes.uniq!

  @logger.debug do
    "Indexes for workload:\n" + indexes.map.with_index do |index, i|
      "#{i} #{index.inspect}"
    end.join("\n")
  end

  indexes
end

Private Instance Methods

combine_indexes(indexes) click to toggle source

Combine the data of indices based on matching hash fields

# File lib/nose/enumerator.rb, line 87
def combine_indexes(indexes)
  no_order_indexes = indexes.select do |index|
    index.order_fields.empty?
  end
  no_order_indexes = no_order_indexes.group_by do |index|
    [index.hash_fields, index.graph]
  end

  no_order_indexes.each do |(hash_fields, graph), hash_indexes|
    extra_choices = hash_indexes.map(&:extra).uniq

    # XXX More combos?
    combos = extra_choices.combination(2)

    combos.map do |combo|
      indexes << Index.new(hash_fields, [], combo.inject(Set.new, &:+),
                           graph)
      @logger.debug "Enumerated combined index #{indexes.last.inspect}"
    end
  end
end
eq_choices(graph, eq) click to toggle source

Get all possible choices of fields to use for equality @return [Array<Array>]

# File lib/nose/enumerator.rb, line 111
def eq_choices(graph, eq)
  entity_choices = graph.entities.flat_map do |entity|
    # Get the fields for the entity and add in the IDs
    entity_fields = eq[entity] << entity.id_field
    entity_fields.uniq!
    1.upto(entity_fields.count).flat_map do |n|
      entity_fields.permutation(n).to_a
    end
  end

  2.upto(graph.entities.length).flat_map do |n|
    entity_choices.permutation(n).map(&:flatten).to_a
  end + entity_choices
end
extra_choices(graph, select, eq, range) click to toggle source

Get fields which should be included in an index for the given graph @return [Array<Array>]

# File lib/nose/enumerator.rb, line 128
def extra_choices(graph, select, eq, range)
  choices = eq.values + range.values << select.to_a

  choices.each do |choice|
    choice.select { |field| graph.entities.include?(field.parent) }
  end

  choices.reject(&:empty?) << []
end
generate_index(hash, order, extra, graph) click to toggle source

Generate a new index and ignore if invalid @return [Index]

# File lib/nose/enumerator.rb, line 187
def generate_index(hash, order, extra, graph)
  begin
    index = Index.new hash, order.uniq, extra, graph
    @logger.debug { "Enumerated #{index.inspect}" }
  rescue InvalidIndexException
    # This combination of fields is not valid, that's ok
    index = nil
  end

  index
end
indexes_for_graph(graph, select, eq, range) click to toggle source

Get all possible indices which jump a given piece of a query graph @return [Array<Index>]

# File lib/nose/enumerator.rb, line 140
def indexes_for_graph(graph, select, eq, range)
  eq_choices = eq_choices graph, eq
  range_fields = graph.entities.map { |entity| range[entity] }.reduce(&:+)
  range_fields.uniq!
  order_choices = range_fields.prefixes.flat_map do |fields|
    fields.permutation.to_a
  end.uniq << []
  extra_choices = extra_choices graph, select, eq, range
  extra_choices = 1.upto(extra_choices.length).flat_map do |n|
    extra_choices.combination(n).map(&:flatten).map(&:uniq)
  end.uniq

  # Generate all possible indices based on the field choices
  choices = eq_choices.product(extra_choices)
  indexes = choices.map! do |index, extra|
    indexes = []

    order_choices.each do |order|
      # Append the primary key of the entities in the graph if needed
      order += graph.entities.sort_by(&:name).map(&:id_field) -
               (index + order)

      # Partition into the ordering portion
      index.partitions.each do |index_prefix, order_prefix|
        hash_fields = index_prefix.take_while do |field|
          field.parent == index.first.parent
        end
        order_fields = index_prefix[hash_fields.length..-1] + \
                       order_prefix + order
        extra_fields = extra - hash_fields - order_fields
        next if order_fields.empty? && extra_fields.empty?

        new_index = generate_index hash_fields, order_fields, extra_fields,
                                   graph
        indexes << new_index unless new_index.nil?
      end
    end

    indexes
  end.inject([], &:+)
  indexes.flatten!

  indexes
end
support_indexes(indexes, by_id_graph) click to toggle source

Produce the indexes necessary for support queries for these indexes @return [Array<Index>]

# File lib/nose/enumerator.rb, line 67
def support_indexes(indexes, by_id_graph)
  # If indexes are grouped by ID graph, convert them before updating
  # since other updates will be managed automatically by index maintenance
  indexes = indexes.map(&:to_id_graph).uniq if by_id_graph

  # Collect all possible support queries
  queries = indexes.flat_map do |index|
    @workload.updates.flat_map do |update|
      update.support_queries(index)
    end
  end

  # Enumerate indexes for each support query
  queries.uniq!
  queries.flat_map do |query|
    indexes_for_query(query).to_a
  end
end