asami.planner
Namespace for functions that plan queries
Namespace for functions that plan queries
bindings-chainclj/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
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 yetestimated-countsclj/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
Inputs: [count-map :- {CountablePattern s/Num} path :- [CountablePattern]]
Returns: [s/Num]
Return list of ordered counts for the patterns. This skips the eval-patternsextract-patterns-by-typeclj/s
(extract-patterns-by-type patterns)Inputs: [patterns :- [PatternOrBindings]] Returns: #:s{Keyword [PatternOrBindings]}
Categorizes elements of a WHERE clause, returning a keyword map
Inputs: [patterns :- [PatternOrBindings]]
Returns: #:s{Keyword [PatternOrBindings]}
Categorizes elements of a WHERE clause, returning a keyword mapfind-startclj/s
(find-start pattern-counts patterns)Inputs: [pattern-counts :- {CountablePattern s/Num} patterns :- [CountablePattern]] Returns: CountablePattern
Returns the first pattern with the smallest count
Inputs: [pattern-counts :- {CountablePattern s/Num} patterns :- [CountablePattern]]
Returns: CountablePattern
Returns the first pattern with the smallest countfirst-groupclj/s
Queries are often executed multiple times. Memoizing first-group* allows the optimizer to avoid redundant work.
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.
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.HasVarsclj/s≠protocol
get-varsclj/s
(get-vars this)Returns the vars for the object
Returns the vars for the object
merge-operationsclj/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.
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-pathclj/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.
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-plannerclj/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.
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]...]
Test for Bindings, which can be [] or [[value] [value]...]
not-operation?clj/s
(not-operation? pattern)Inputs: [pattern :- PatternOrBindings] Returns: s/Bool
Returns true if a pattern is a NOT operation
Inputs: [pattern :- PatternOrBindings] Returns: s/Bool Returns true if a pattern is a NOT operation
orderclj/s
(order patterns)Inputs: [patterns :- [EvalPattern]] Returns: [EvalPattern]
Takes a sequence of Evaluation binding patterns and returns them in an internally consistent order
Inputs: [patterns :- [EvalPattern]] Returns: [EvalPattern] Takes a sequence of Evaluation binding patterns and returns them in an internally consistent order
pathsclj/s
(paths prebound patterns pattern-counts eval-patterns)Inputs: [prebound :- (s/maybe #{Var}) patterns :- [CountablePattern] pattern-counts :- {CountablePattern s/Num} eval-patterns :- [EvalPattern]]
Returns: CountablePattern
Returns a seq of all paths 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. Paths can be envisioned as a tree, like: A-+--B1-+--C1 | | | +--C2 | +--B2-+--C3 | +--C4 The result of this expands the tree into a flattened form: [[A,B1,C1] [A,B1,C2] [A,B2,C3] [A,B2,C4]] These paths provide all the options for the optimizer to choose from.
Inputs: [prebound :- (s/maybe #{Var}) patterns :- [CountablePattern] pattern-counts :- {CountablePattern s/Num} eval-patterns :- [EvalPattern]]
Returns: [[CountablePattern]]
Returns a seq of all paths 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.
Paths can be envisioned as a tree, like:
A-+--B1-+--C1
| |
| +--C2
|
+--B2-+--C3
|
+--C4
The result of this expands the tree into a flattened form:
[[A,B1,C1] [A,B1,C2] [A,B2,C3] [A,B2,C4]]
These paths provide all the options for the optimizer to choose from.plan-pathclj/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.
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-algebraclj/s
(simplify-algebra patterns options)Inputs: [patterns :- [PatternOrBindings] options] Returns: [PatternOrBindings]
This operation simplifies the algebra into a sum-of-products form. Currently a placeholder that does nothing.
Inputs: [patterns :- [PatternOrBindings] options] Returns: [PatternOrBindings] This operation simplifies the algebra into a sum-of-products form. Currently a placeholder that does nothing.
user-planclj/s
(user-plan graph patterns {:keys [simplify] :as options})Inputs: [graph patterns :- [CountablePattern] {:keys [simplify], :as options}] Returns: [CountablePattern]
Returns the original order of patterns specified by the user. No optimization is attempted.
Inputs: [graph patterns :- [CountablePattern] {:keys [simplify], :as options}]
Returns: [CountablePattern]
Returns the original order of patterns specified by the user. No optimization is attempted.withoutclj/s
(without e s)Inputs: [e :- s/Any s :- [s/Any]] Returns: [s/Any]
Returns a sequence minus a specific element
Inputs: [e :- s/Any s :- [s/Any]] Returns: [s/Any] Returns a sequence minus a specific element
cljdoc is a website building & hosting documentation for Clojure/Script libraries
× close