VIATRA/Query/UserDocumentation/API/LocalSearch

Since version 0.9, there is a possibility to refer to alternative search engines in addition to Rete-based incremental engines; version 1.0 includes a local search based search algorithm usable with the VIATRA Query matcher API.

The most important steps to perform:

• Add a dependency to the optional plug-in org.eclipse.viatra.query.runtime.localsearch
• Explicitly ask for a local search-based matcher when initializing the matcher instance:

IQuerySpecification<?> specification = ...;
QueryEvaluationHint hint = LocalSearchHints.getDefault().build();
AdvancedViatraQueryEngine.from(queryEngine).getMatcher(specification, hint);

• Or alternatively, set the local search as default for a query engine:

ViatraQueryEngine queryEngine = ViatraQueryEngine.on(scope, ViatraQueryEngineOptions.defineOptions().withDefaultHint(LocalSearchHints.getDefault().build()));

• After initialization, the existing pattern matcher API constructs can be used over the local search engine.

Parameterizing local search

Parameterization of the planner algorithm is possible via the hinting mechanism. In the current release three hint keys are provided for this purpose in the LocalSearchHintKeys class:

• • USE_BASE_INDEX: allow/disallow the usage of the index at runtime. Its value may be true or false. Currently the default is true.
  • ALLOW_INVERSE_NAVIGATION: allow/disallow inverse navigation along EReferences without an EOpposite. Its value may be true or false. Currently the default is true.
  • PLANNER_TABLE_ROW_COUNT: An internal parameter, bigger values often mean longer plan generation times, and potentially search plans with lower cost. Its value may be a positive int, the default is 4 in this release.
  • PLANNER_COST_FUNCTION: The cost function to be used by the planner. Must implement org.eclipse.viatra.query.runtime.localsearch.planner.cost.ICostFunction
  • FLATTEN_CALL_PREDICATE: The predicate to control which operation calls shall be flattened before planning

For example, to disable the use of base index:

IQuerySpecification<?> specification = ...;
QueryEvaluationHint hint = LocalSearchHints.getDefault().setUseBase(false).build();
AdvancedViatraQueryEngine.from(queryEngine).getMatcher(specification, hint);

Cost function

The default cost function estimates operation costs based on the statistical structure of the model, which is obtained using the base index. This is true even if USE_BASE_INDEX is set to false, in which case a plan is created which does not rely on the base index at execution time. Since 1.4.0 the base index is capable of providing only statistical information with much less overhead compared to instance indexing. To avoid using base index even in the planning phase, the cost function can be replaced to another implementation. For this purpose, two alternative implementations are provided:

• org.eclipse.viatra.query.runtime.localsearch.planner.cost.impl.VariableBindingBasedCostFunction estimates the operation costs using the number of variables it binds. This cost function usually results in lower performance executions.
• The abstract class org.eclipse.viatra.query.runtime.localsearch.planner.cost.impl.StatisticsBasedConstraintCostFunction can be used to provide model statistics from different sources, e.g. a previously populated map:

final Map<IInputKey, Long> statistics = ..
QueryEvaluationHint hint = LocalSearchHints.getDefault().setCostFunction(new StatisticsBasedConstraintCostFunction(){
  public long countTuples(IConstraintEvaluationContext input, IInputKey supplierKey){
    return statistics.get(supplierKey);
  }
}).build();

The latter is advised to be used if the model is expected to be changed after the planning phase to ensure that the planing is based on a realistic model statistics which resembles the actual structure which the pattern is executed on.

Known limitations

• A local search matcher cannot provide change notifications on pattern matches. If asked, an UnsupportedOperationException is thrown.
• For now, it is not possible to combine different pattern matching algorithms. Either the entire search must use Rete or Local search based algorithms.