asami.planner — org.clojars.quoll/asami 0.4.9

Namespace for functions that plan queries

addset clj/s

Aggregate clj/s

aggregate-constraint clj/s

(aggregate-constraint aggregating? needed-vars aggregate-vars constraint)

Inputs: [aggregating? :- s/Bool needed-vars :- #{Var} aggregate-vars :- #{Var} constraint :- Pattern] Returns: (s/maybe Pattern)

Returns a constraint when it does or does not contains aggregates, selected by the aggregating? flag. For a compound constraint (and, or, not) then returns all non-empty elements that contain or do-not-contain aggregate vars.

aggregate-form? clj/s

(aggregate-form? s)

Determines if a term is an aggregate

aggregate-types clj/s

append clj/s

(append s e)

Inputs: [s e]

Appends a single element to the end of a seq

Bindings clj/s

bindings-chain clj/s

(bindings-chain evs bound-vars patterns)

Inputs: [evs :- [EvalPattern] bound-vars :- #{Var} patterns :- [EPVPattern]] Returns: (s/maybe [(s/one [EvalPattern] "eval-patterns that can be used to bind a pattern") (s/one [EvalPattern] "eval-patterns that cannot be used to bind a pattern")])

This is a helper function for first-group. When first-group has found a set of patterns that share vars with each other, this will look for any eval-patterns (binding through evaluation) which, if added, would allow even more patterns to be added to the group. So if we had: [?a :prop ?b] [?a :attr ?c] [(inc ?c) ?d] [(str ?b "-" ?d) ?e] [(dec ?c) ?f] [?x :label ?e] [?y :included true] Then first-group would find the first 2 patterns, which would bind: #{?a ?b ?c} This function is then called, with: evs = [[(inc ?c) ?d] [(str ?b "-" ?d) ?e] [(dec ?c) ?f]] bound-vars = #{?a ?b ?c} patterns = [[?x :label ?e] [?y :included true]] It will identify that [?x :label ?e] can be included if the first 2 evaluations are used, since they can be used to bind ?e. The result will be a split of the bindings that can be used to match a pattern, and the bindings which cannot: [ [[(inc ?c) ?d] [(str ?b "-" ?d) ?e]] , [[(dec ?c) ?f]] ] The loop in first-group will then use this result to pull in all possible patterns.

Finds all bindings will can be used to connect unused patterns to a group. Returns a pair: Bindings that can be used to connect patterns to the current group / Remaining bindings evs: eval patterns that are available to use bound-vars: the vars that have been bound for the current group patterns: the patterns that aren't used in any groups yet

bindings? clj/s

(bindings? b)

CountablePattern clj/s

estimated-counts clj/s

(estimated-counts count-map path)

Inputs: [count-map :- {CountablePattern s/Num} path :- [CountablePattern]] Returns: [s/Num]

Return list of ordered counts for the patterns. This skips the eval-patterns. It also attaches meta-data to indicate if a path can short circuit comparisons.

extract-patterns-by-type clj/s

(extract-patterns-by-type patterns)

Inputs: [patterns :- [PatternOrBindings]] Returns: #:s{Keyword [PatternOrBindings]}

Categorizes elements of a WHERE clause, returning a keyword map

find-first clj/s

(find-first count-map [first-path & all-paths])

Inputs: [count-map :- {CountablePattern s/Num} [first-path & all-paths] :- CountablePattern] Returns: [CountablePattern]

Finds a min (or approximate minimum) path

find-start clj/s

(find-start pattern-counts patterns)

Inputs: [pattern-counts :- {CountablePattern s/Num} patterns :- [CountablePattern]] Returns: CountablePattern

Returns the first pattern with the smallest count

first-group clj/s

Queries are often executed multiple times. Memoizing first-group* allows the optimizer to avoid redundant work.

first-group* clj/s

(first-group* bound patterns eval-patterns)

Inputs: [bound :- (s/maybe #{Var}) patterns :- [CountablePattern] eval-patterns :- [EvalPattern]] Returns: [(s/one [CountablePattern] "group") (s/one [CountablePattern] "remainder") (s/one [EvalPattern] "unused eval bindings")]

Finds a group from a sequence of patterns. A group is defined by every pattern sharing at least one var with at least one other pattern. This is done to group patterns by those which can be joined with inner joins. Groups do not share variables, so a join from a group to any pattern in a different group will be an outer join. The optimizer has to work on one group at a time. For the following query: [?a :prop ?b] [?a :attr ?c] [(inc ?c) ?d] [(str ?b "-" ?d) ?e] [(dec ?c) ?f] [?x :label ?e] [?y :included true] All patterns except the last one are in the same group. Returns a pair. The first returned element is the Patterns in the group, the second is what was left over. This remainder contains all the patterns that appear in other groups. The function can be called again on the remainder.

HasVars clj/s protocol

get-vars clj/s

(get-vars this)

Returns the vars for the object

merge-operations clj/s

(merge-operations graph
                  options
                  planned-patterns
                  general-patterns
                  filter-patterns
                  not-patterns)

Inputs: [graph options planned-patterns general-patterns filter-patterns not-patterns]

Merges filters and NOT operations into the sequence of patterns, so that they appear as soon as all their variables are first bound. By pushing filters as far to the front as possible, it minimizes the work of subsequent joins. TODO: if not-patterns relies on the output of an eval-pattern, then the eval can be pushed further ahead in the path. This should happen before this merge is called.

min-join-path clj/s

(min-join-path bound count-map patterns eval-patterns)

Inputs: [bound :- (s/maybe #{Var}) count-map :- {CountablePattern s/Num} patterns :- [CountablePattern] eval-patterns :- [EvalPattern]] Returns: [CountablePattern]

Calculates a plan based on no outer joins (a cross product), and minimized joins. A plan is the order in which to evaluate constraints and join them to the accumulated evaluated data. If it is not possible to create a path without a cross product, then return a plan which is a concatenation of all inner-product groups, where the groups are all ordered by minimized joins.

minimal-first-planner clj/s

(minimal-first-planner graph patterns options)

Inputs: [graph patterns :- [PatternOrBindings] options] Returns: [PatternOrBindings]

Attempts to optimize a query, based on the principle that if smaller resolutions appear first in a product term, then lazy evaluation will lead to less iteration on the later terms. This is not always true, but is in the general case.

nested-seq? clj/s

(nested-seq? s)

Test for Bindings, which can be [] or [[value] [value]...]

new-and clj/s

(new-and terms)

Inputs: [terms]

Create an AND expression from a sequence of arguments. If an argument is a nested AND, then these terms are flattened into this level.

new-or clj/s

(new-or terms)

Inputs: [terms]

Create an OR expression from a sequence of arguments. If an argument is a nested OR, then these terms are flattened into this level. If an argument is a NOT, then an exception is thrown.

normalize-sum-of-products clj/s

(normalize-sum-of-products patterns)

Inputs: [patterns]

Converts an expression that is not a sum into a sum operation of one argument.

not-operation? clj/s

(not-operation? pattern)

Inputs: [pattern :- PatternOrBindings] Returns: s/Bool

Returns true if a pattern is a NOT operation

order clj/s

(order patterns)

Inputs: [patterns :- [EvalPattern]] Returns: [EvalPattern]

Takes a sequence of Evaluation binding patterns and returns them in an internally consistent order

path clj/s

(path prebound patterns pattern-counts eval-patterns)

Inputs: [prebound :- (s/maybe #{Var}) patterns :- [CountablePattern] pattern-counts :- {CountablePattern s/Num} eval-patterns :- [EvalPattern]] Returns: [CountablePattern]

Returns an efficient path through the constraints. A path is defined by new patterns containing at least one variable common to the patterns that appeared before it. Patterns must form a group.

PatternOrBindings clj/s

plan-path clj/s

(plan-path graph patterns options)

Inputs: [graph patterns :- [PatternOrBindings] options] Returns: [PatternOrBindings]

Determines the order in which to perform the elements that go into a query. Tries to optimize, so it uses the graph to determine some of the properties of the query elements. Options can describe which planner to use. Planning will determine the resolution map, and this is returned with the plan. By default the min-join-path function is used. This can be overriden with options: [:planner plan] The plan can be one of :user, :min. :min is the default. :user means to execute in provided order.

simplify-algebra clj/s≠

clj

(simplify-algebra patterns)

(simplify-algebra patterns options)

cljs

(simplify-algebra G__27082)

(simplify-algebra G__27086 G__27087)

Inputs: ([patterns :- [PatternOrBindings]] [patterns :- [PatternOrBindings] options]) Returns: [PatternOrBindings]

This operation simplifies the algebra into a sum-of-products form.

split-aggregate-terms clj/s

(split-aggregate-terms constraints selection withs)

Inputs: [constraints :- Pattern selection :- [(s/cond-pre Var Aggregate)] withs :- [Var]] Returns: [(s/one [s/Any] "outer query constraints") (s/one [s/Any] "inner query constraints") (s/one #{Var} "vars to get aggregations for")]

Splits a WHERE clause up into the part suitable for an outer query, and the remaining constraints, which will be used for an inner query.

user-plan clj/s

(user-plan graph patterns options)

Inputs: [graph patterns :- [PatternOrBindings] options] Returns: [CountablePattern]

Returns the original order of patterns specified by the user. No optimization is attempted.

without clj/s

(without e s)

Inputs: [e :- s/Any s :- [s/Any]] Returns: [s/Any]

Returns a sequence minus a specific element