Jump to: navigation, search

VIATRA/Query/UserDocumentation/API/LocalSearch

Introduction

Since version 1.4, the Local Search engine is considered stable, and users are encuraged to use it in applications where incrementality is not crucial. The Local Search engine reuses the same matcher API used in VIATRA Query.

  • When is local search the most beneficial?
    • A single, batch evaluation of models
    • Memory limit is severe and the Rete network does not fit into the memory
    • When all calls have one or more parameters bound, resulting in simple traversal
  • Harder cases
    • Repeated model execution
    • Query evaluation requires expensive model traversal (think about iterating over all instances in a model)

Using Local Search

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:
// Access the default local search hint
QueryEvaluationHint localSearchHint = LocalSearchHints.getDefault().build();
 
// Build an engine options with the local search hint
ViatraQueryEngineOptions options = ViatraQueryEngineOptions.
		defineOptions().
		withDefaultHint(localSearchHint).
                withDefaultBackend(localSearchHint.getQueryBackendFactory()). // this line is needed in 1.4 due to bug 507777
		build();
 
//Access the query engine
ViatraQueryEngine queryEngine = ViatraQueryEngine.on(scope, options);
  • After initialization, the existing pattern matcher API constructs can be used over the local search engine.

It is also possible to declare specific patterns to be executed by Local Search in the VQL file using the search, although this setting may be overridden by the hints given at the matcher creation.

search pattern minCPUs(n : java Integer) {
	n == min find cpus(_hi1, #_);
}

Parameterizing local search

Parameterization of the planner algorithm is possible via the hint mechanism. In version 1.4 the following hints 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.
  • 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 pattern composition calls shall be flattened before planning. By deafult all called patterns are flattened.
  • PLANNER_COST_FUNCTION: Allow to set up custom cost functions for the planner.

For example, to disable the use of base index:

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

In versions prior to 1.4, local search also supported a boolean hint called ALLOW_INVERSE_NAVIGATION: allow/disallow inverse navigation along EReferences without an EOpposite. We have found that this setting is unnecessary, and in version 1.4 is completely ignored.

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.

Important: we plan on providing a simpler way of setting up model statistics in VIATRA 1.5; so in later version this kind of setup might be changed.

Known limitations

  • A local search matcher cannot provide change notifications on pattern matches. If asked, an UnsupportedOperationException is thrown.
  • As of version 1.4, it is not possible to combine different pattern matching algorithms for the evaluation of a single pattern. Either the entire search must use Rete or Local search based algorithms.
  • The Local Search engine currently does not able to execute recursive queries. See bug 458278 for more details.