The Quest for Performance: smart Rete layouts

[eclipse-viatra-bot]

| --- | --- |
| Bugzilla Link | 398763 |
| Status | NEW |
| Importance | P3 normal |
| Reported | Jan 22, 2013 11:02 EDT |
| Modified | Jul 06, 2018 03:55 EDT |
| Version | oldinquery |
| Depends on | 399667, 493140, 493256 |
| Reporter | Gabor Bergmann |

Description

Cloned from: 326: The Quest for Performance: smart Rete layouts
http://github.com/ujhelyiz/EMF-IncQuery/issues/issue/326

Implement various ideas for building a more clever Rete structure:

• ASAP trimming of variables not used later
• Clever node reuse\

• Find if a stub join also happens to join alternate stubs with the same underlying Rete node, and then consider the "free accidental" stub in further joins.
  • And so on with filters etc.
  • More powerful case: cross-pattern sharing. Check whether existing Rete structure built for other patterns already checks some constraints.\
• Potential source of good test case: the thesis about GPU vs. EIQ performance supervised by @abelhegedus

• Suggested order of join preference:\

• trivial joins (stub a = stub b)\
• high selectivity filters

• supressed by joincandidate if already checked on other side
• apply first to narrower stubs\

• aggregator quasijoins, let-expressions (?)\
• true joins

• except cartesians
• TBD: ranking based on what constraints the join will enable\

• low-selectivity filters (injectivity)\
• cartesian joins

[eclipse-viatra-bot]

By Gabor Bergmann on Feb 13, 2013 13:26

New refinement requiring functional dependency analysis:\

• aggregator quasijoins, let-expressions (?) AND Heath-joins (XY join YZ where Y implies either X or Z)

[eclipse-viatra-bot]

By Gabor Bergmann on Mar 12, 2013 19:37

• Expanding thoughts on cross-pattern node sharing:\
  • once it is really reliable, private patterns (especially if only used by one public pattern) could be cannibalized (flattened) by calling patterns
    • if the called pattern really belongs together, this does not change anything, but otherwise there may be cross-pattern optimization (especially if called by only one host)
    • inline patterns should be automatically private in this case\
  • more importantly, in case of NAC or aggregation, if the called private pattern is only weakly connected, then it is possible to carry over enumerable constraints from the calling pattern

[eclipse-viatra-bot]

By Gabor Bergmann on Mar 13, 2013 10:19

More ideas:

• type inference on called patterns to eliminate type checks
• on joins, consider which should be the left side \

• the one with more variables? so that left inheritance is more useful

[eclipse-viatra-bot]

By Gabor Bergmann on Apr 19, 2013 04:39

Functional dependencies again: prefer the join candidate where the operands have a smaller closure (the sum of their closure is smaller?). Motivation: if X->Y->Z, joining Y and Z first and then joining X against (YZ) is more efficient, as there are probably fewer variations of Y and Z (not more than variations of X).

[eclipse-viatra-bot]

By Gabor Bergmann on May 10, 2013 08:22

• ASAP trimming of variables not used later\
  • and prefer join candidates that would let us do this\
  • (see ase13 performance tests, e.g. ase_locals and ase_references)

[eclipse-viatra-bot]

By Gabor Bergmann on May 10, 2013 14:45

In commit a8dd786, Added eager trimming of variables - no planning ahead yet. Let's hope for good results.

[eclipse-viatra-bot]

By Istvan Rath on May 20, 2013 04:35

I'm setting version to "unspecified" as we currently do not (firmly) know when these future ideas will be addressed.

[eclipse-viatra-bot]

By Gabor Bergmann on Jun 05, 2014 05:51

The query planner should recognize deferred constraints that depend on no variables, and treat them as enumerable.

Examples:

• eval(1L); (Inspired by Bug 398769)
• count find foobar(_, _, _);

[eclipse-viatra-bot]

By Gabor Bergmann on Jun 02, 2015 10:14

Foreseen improvements to support the decision making of the query planner:

• PositivePatternCall PConstraint should provide functional dependency and type info
• Eval and aggregation should provide type info (JavaTransitiveInstancesKey)

[eclipse-viatra-bot]

By Abel Hegedus on Apr 19, 2016 05:24

Updating to correct milestone.

[eclipse-viatra-bot]

By Gabor Bergmann on May 09, 2016 11:32

• Query planning: make constant filters reusable (is this applicable for inputs or other nodes as well? maybe depart from quasitree?)

[eclipse-viatra-bot]

By Gabor Bergmann on May 09, 2016 11:37

• on joins, consider which should be the left side
  • the one with more variables? so that left inheritance is more useful

...and change TupleMask#combine so that it just returns unmasked for empty complementer masks - thus filter-only joins will reuse tuples, should be nice memory win.

[eclipse-viatra-bot]

By Gabor Bergmann on May 27, 2016 03:54

• ASAP trimming of variables not used later

Improve the currently implemented trimming so that it results in the same order of indexes every time - improves reuse of trimmer nodes and their descendants

[eclipse-viatra-bot]

By Gabor Bergmann on Jul 06, 2018 03:55

Refactor the notion of 'Production' node so that it is not a node type but rather a role that pretty much any Supplier node may take. Foreseen benefits:

(a) saves memory when there is no need to enforce uniqueness (single body, no projection at the end), and a join or trimmer node can represent the match set of the pattern;

(b) better node sharing among isomorphic patterns.

Be careful with recursion, with traceability and with how the result appears in Rete visualizer.