19 files changed, 2754 insertions, 0 deletions

diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/ILocalSearchPlanner.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/ILocalSearchPlanner.java
new file mode 100644
index 00000000..dfd9a3c8
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/ILocalSearchPlanner.java
@@ -0,0 +1,38 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Zoltan Ujhelyi, IncQuery Labs Ltd.
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner;
+
+import java.util.Collection;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.localsearch.plan.SearchPlanForBody;
+import tools.refinery.viatra.runtime.matchers.ViatraQueryRuntimeException;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+
+/**
+ * @author Zoltan Ujhelyi
+ * @since 1.7
+ */
+public interface ILocalSearchPlanner {
+
+    /**
+     * Creates executable plans for the provided query. It is required to call one of the
+     * <code>initializePlanner()</code> methods before calling this method.
+     * 
+     * @param querySpec
+     * @param boundParameters
+     *            a set of bound parameters
+     * @return a mapping between ISearchOperation list and a mapping, that holds a PVariable-Integer mapping for the
+     *         list of ISearchOperations
+     * @throws ViatraQueryRuntimeException
+     */
+    Collection<SearchPlanForBody> plan(PQuery querySpec, Set<PParameter> boundParameters);
+
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/ISearchPlanCodeGenerator.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/ISearchPlanCodeGenerator.java
new file mode 100644
index 00000000..72218337
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/ISearchPlanCodeGenerator.java
@@ -0,0 +1,23 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Marton Bur, Akos Horvath, Zoltan Ujhelyi, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner;
+
+import java.util.List;
+
+import tools.refinery.viatra.runtime.localsearch.operations.ISearchOperation;
+
+/**
+ * @author Marton Bur
+ *
+ */
+public interface ISearchPlanCodeGenerator {
+
+    void compile(List<List<ISearchOperation>> plans);
+    
+}
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/LocalSearchPlanner.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/LocalSearchPlanner.java
new file mode 100644
index 00000000..f44be655
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/LocalSearchPlanner.java
@@ -0,0 +1,140 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Marton Bur, Akos Horvath, Zoltan Ujhelyi, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import org.apache.log4j.Logger;
+import tools.refinery.viatra.runtime.localsearch.matcher.integration.LocalSearchHints;
+import tools.refinery.viatra.runtime.localsearch.operations.ISearchOperation;
+import tools.refinery.viatra.runtime.localsearch.plan.SearchPlanForBody;
+import tools.refinery.viatra.runtime.localsearch.planner.compiler.IOperationCompiler;
+import tools.refinery.viatra.runtime.matchers.backend.ResultProviderRequestor;
+import tools.refinery.viatra.runtime.matchers.context.IQueryBackendContext;
+import tools.refinery.viatra.runtime.matchers.context.IQueryRuntimeContext;
+import tools.refinery.viatra.runtime.matchers.planning.SubPlan;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.ExportedParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.psystem.rewriters.PBodyNormalizer;
+import tools.refinery.viatra.runtime.matchers.psystem.rewriters.PDisjunctionRewriter;
+import tools.refinery.viatra.runtime.matchers.psystem.rewriters.PDisjunctionRewriterCacher;
+import tools.refinery.viatra.runtime.matchers.psystem.rewriters.PQueryFlattener;
+
+/**
+ * 
+ * @author Marton Bur
+ * @noreference This class is not intended to be referenced by clients.
+ */
+public class LocalSearchPlanner implements ILocalSearchPlanner {
+
+    // Externally set tools for planning
+    private final PDisjunctionRewriter preprocessor;
+    private final LocalSearchRuntimeBasedStrategy plannerStrategy;
+    private final IQueryRuntimeContext runtimeContext;
+    private final LocalSearchHints configuration;
+    private final IOperationCompiler operationCompiler;
+    private final IQueryBackendContext context;
+    private final ResultProviderRequestor resultRequestor;
+    
+    /**
+     * @param resultRequestor 
+     * @since 1.7
+     */
+    public LocalSearchPlanner(IQueryBackendContext backendContext, IOperationCompiler compiler, Logger logger, 
+            final LocalSearchHints configuration, ResultProviderRequestor resultRequestor) 
+    {
+
+        this.runtimeContext = backendContext.getRuntimeContext();
+        this.configuration = configuration;
+        this.operationCompiler = compiler;
+        this.resultRequestor = resultRequestor;
+        PQueryFlattener flattener = new PQueryFlattener(configuration.getFlattenCallPredicate());
+        /*
+         * TODO https://bugs.eclipse.org/bugs/show_bug.cgi?id=439358: The normalizer is initialized with the false
+         * parameter to turn off unary constraint elimination to work around an issue related to plan ordering: the
+         * current implementation of the feature target checking operations expect that the source types were checked
+         * before. However, this causes duplicate constraint checks in the search plan that might affect performance
+         * negatively.
+         */
+        PBodyNormalizer normalizer = new PBodyNormalizer(runtimeContext.getMetaContext()) {
+            
+            @Override
+            protected boolean shouldCalculateImpliedTypes(PQuery query) {
+                return false;
+            }
+        };
+        preprocessor = new PDisjunctionRewriterCacher(flattener, normalizer);
+
+        plannerStrategy = new LocalSearchRuntimeBasedStrategy();
+
+        context = backendContext;
+    }
+
+    /**
+     * Creates executable plans for the provided query. It is required to call one of the
+     * <code>initializePlanner()</code> methods before calling this method.
+     * 
+     * @param querySpec
+     * @param boundParameters
+     *            a set of bound parameters
+     * @return a mapping between ISearchOperation list and a mapping, that holds a PVariable-Integer mapping for the
+     *         list of ISearchOperations
+     */
+    @Override
+    public Collection<SearchPlanForBody> plan(PQuery querySpec, Set<PParameter> boundParameters) {
+        // 1. Preparation
+        preprocessor.setTraceCollector(configuration.getTraceCollector());
+        Set<PBody> normalizedBodies = preprocessor.rewrite(querySpec.getDisjunctBodies()).getBodies();
+
+        List<SearchPlanForBody> plansForBodies = new ArrayList<>(normalizedBodies.size());
+
+        for (PBody normalizedBody : normalizedBodies) {
+            // 2. Plan creation
+            // Context has matchers for the referred Queries (IQuerySpecifications)
+            Set<PVariable> boundVariables = calculatePatternAdornmentForPlanner(boundParameters, normalizedBody);
+            PlanState searchPlanInternal = plannerStrategy.plan(normalizedBody, boundVariables, context, resultRequestor, configuration);
+            SubPlan plan = plannerStrategy.convertPlan(boundVariables, searchPlanInternal);
+            // 3. PConstraint -> POperation compilation step
+            // * Pay extra caution to extend operations, when more than one variables are unbound
+            List<ISearchOperation> compiledOperations = operationCompiler.compile(plan, boundParameters);
+            // Store the variable mappings for the plans for debug purposes (traceability information)
+            SearchPlanForBody compiledPlan = new SearchPlanForBody(normalizedBody,
+                    operationCompiler.getVariableMappings(), plan, compiledOperations,
+                    operationCompiler.getDependencies(), 
+                    searchPlanInternal, searchPlanInternal.getCost());
+
+            plansForBodies.add(compiledPlan);
+        }
+
+        return plansForBodies;
+    }
+
+    private Set<PVariable> calculatePatternAdornmentForPlanner(Set<PParameter> boundParameters, PBody normalizedBody) {
+        Map<PParameter, PVariable> parameterMapping = new HashMap<>();
+        for (ExportedParameter constraint : normalizedBody.getSymbolicParameters()) {
+            parameterMapping.put(constraint.getPatternParameter(), constraint.getParameterVariable());
+        }
+        Set<PVariable> boundVariables = new HashSet<>();
+        for (PParameter parameter : boundParameters) {
+            PVariable mappedParameter = parameterMapping.get(parameter);
+            boundVariables.add(mappedParameter);
+        }
+        return boundVariables;
+    }
+
+}
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/LocalSearchRuntimeBasedStrategy.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/LocalSearchRuntimeBasedStrategy.java
new file mode 100644
index 00000000..1bebe37e
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/LocalSearchRuntimeBasedStrategy.java
@@ -0,0 +1,257 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Marton Bur, Akos Horvath, Zoltan Ujhelyi, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.localsearch.matcher.integration.LocalSearchHints;
+import tools.refinery.viatra.runtime.localsearch.planner.cost.ICostFunction;
+import tools.refinery.viatra.runtime.localsearch.planner.util.OperationCostComparator;
+import tools.refinery.viatra.runtime.matchers.backend.ResultProviderRequestor;
+import tools.refinery.viatra.runtime.matchers.context.IQueryBackendContext;
+import tools.refinery.viatra.runtime.matchers.planning.SubPlan;
+import tools.refinery.viatra.runtime.matchers.planning.SubPlanFactory;
+import tools.refinery.viatra.runtime.matchers.planning.operations.PApply;
+import tools.refinery.viatra.runtime.matchers.planning.operations.PProject;
+import tools.refinery.viatra.runtime.matchers.planning.operations.PStart;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.util.Sets;
+
+/**
+ * This class contains the logic for local search plan calculation based on costs of the operations.
+ * Its name refers to the fact that the strategy tries to use as much information as available about
+ * the model on which the matching is initiated. When no runtime info is available, it falls back to 
+ * the information available from the metamodel durint operation cost calculation.
+ * 
+ * The implementation is based on the paper "Gergely Varró, Frederik Deckwerth, Martin Wieber, and Andy Schürr: 
+ * An algorithm for generating model-sensitive search plans for pattern matching on EMF models" 
+ * (DOI: 10.1007/s10270-013-0372-2)
+ * 
+ * @author Marton Bur
+ * @noreference This class is not intended to be referenced by clients.
+ */
+public class LocalSearchRuntimeBasedStrategy {
+    
+    private final OperationCostComparator infoComparator = new OperationCostComparator();
+
+
+    /**
+     * Converts a plan to the standard format
+     */
+    protected SubPlan convertPlan(Set<PVariable> initialBoundVariables, PlanState searchPlan) {
+        PBody pBody;
+        pBody = searchPlan.getAssociatedPBody();
+        
+        // Create a starting plan
+        SubPlanFactory subPlanFactory = new SubPlanFactory(pBody);
+
+        // We assume that the adornment (now the bound variables) is previously set
+        SubPlan plan = subPlanFactory.createSubPlan(new PStart(initialBoundVariables));
+
+        List<PConstraintInfo> operations = searchPlan.getOperations();
+        for (PConstraintInfo pConstraintPlanInfo : operations) {
+            PConstraint pConstraint = pConstraintPlanInfo.getConstraint();
+            plan = subPlanFactory.createSubPlan(new PApply(pConstraint), plan);
+        }
+
+        return subPlanFactory.createSubPlan(new PProject(pBody.getSymbolicParameterVariables()), plan);
+    }
+
+    /**
+     * The implementation of a local search-based algorithm to create a search plan for a flattened (and normalized)
+     * PBody
+     * @param pBody for which the plan is to be created
+     * @param initialBoundVariables variables that are known to have already assigned values
+     * @param context the backend context
+     * @param resultProviderRequestor requestor for accessing result providers of called patterns
+     * @param configuration the planner configuration
+     * @return the complete search plan for the given {@link PBody}
+     * @since 2.1
+     */
+    protected PlanState plan(PBody pBody, Set<PVariable> initialBoundVariables,
+            IQueryBackendContext context, final ResultProviderRequestor resultProviderRequestor,
+            LocalSearchHints configuration) {
+        final ICostFunction costFunction = configuration.getCostFunction();
+        PConstraintInfoInferrer pConstraintInfoInferrer = new PConstraintInfoInferrer(
+                configuration.isUseBase(), context, resultProviderRequestor, costFunction::apply);
+        
+        // Create mask infos
+        Set<PConstraint> constraintSet = pBody.getConstraints();
+        List<PConstraintInfo> constraintInfos = 
+                pConstraintInfoInferrer.createPConstraintInfos(constraintSet);
+        
+        // Calculate the characteristic function
+        // The characteristic function tells whether a given adornment is backward reachable from the (B)* state, where
+        // each variable is bound.
+        // The characteristic function is represented as a set of set of variables
+        // TODO this calculation is not not implemented yet, thus the contents of the returned set is not considered later
+        List<Set<PVariable>> reachableBoundVariableSets = reachabilityAnalysis(pBody, constraintInfos);
+        int k = configuration.getRowCount();
+        PlanState searchPlan = calculateSearchPlan(pBody, initialBoundVariables, k, reachableBoundVariableSets, constraintInfos);
+        return searchPlan;
+    }
+
+    private PlanState calculateSearchPlan(PBody pBody, Set<PVariable> initialBoundVariables, int k,
+            List<Set<PVariable>> reachableBoundVariableSets, List<PConstraintInfo> allMaskInfos) {
+
+        List<PConstraintInfo> allPotentialExtendInfos = new ArrayList<>();
+        List<PConstraintInfo> allPotentialCheckInfos = new ArrayList<>();
+        Map<PVariable, List<PConstraintInfo>> checkOpsByVariables = new HashMap<>();
+        Map<PVariable, Collection<PConstraintInfo>> extendOpsByBoundVariables = new HashMap<>();
+        
+        for (PConstraintInfo op : allMaskInfos) {
+            if (op.getFreeVariables().isEmpty()) { // CHECK
+                allPotentialCheckInfos.add(op);
+            } else { // EXTEND
+                allPotentialExtendInfos.add(op);
+                for (PVariable variable : op.getBoundVariables()) {
+                    extendOpsByBoundVariables.computeIfAbsent(variable, v -> new ArrayList<>()).add(op);
+                }
+            }
+        }
+        // For CHECKs only, we must start from lists that are ordered by the cost of the constraint application
+        Collections.sort(allPotentialCheckInfos, infoComparator);  // costs are eagerly needed for check ops          
+        for (PConstraintInfo op : allPotentialCheckInfos) {
+            for (PVariable variable : op.getBoundVariables()) {
+                checkOpsByVariables.computeIfAbsent(variable, v -> new ArrayList<>()).add(op);
+            }
+        }
+        // costs are not needed for extend ops until they are first applied (TODO make cost computaiton on demand) 
+        
+        
+        // rename for better understanding
+        Set<PVariable> boundVariables = initialBoundVariables;
+        Set<PVariable> freeVariables = Sets.difference(pBody.getUniqueVariables(), initialBoundVariables);
+
+        int variableCount = pBody.getUniqueVariables().size();
+        int n = freeVariables.size();
+
+        List<List<PlanState>> stateTable = initializeStateTable(k, n);
+
+        // Set initial state: begin with an empty operation list
+        PlanState initialState = new PlanState(pBody, boundVariables);
+        
+        // Initial state creation, categorizes all operations; add present checks to operationsList
+        initialState.updateExtends(allPotentialExtendInfos);
+        initialState.applyChecks(allPotentialCheckInfos);
+        stateTable.get(n).add(0, initialState);
+        
+        // stateTable.get(0) will contain the states with adornment B*
+        for (int i = n; i > 0; i--) {
+            for (int j = 0; j < k && j < stateTable.get(i).size(); j++) {
+                PlanState currentState = stateTable.get(i).get(j);
+
+                for (PConstraintInfo constraintInfo : currentState.getPresentExtends()) {
+                    // for each present EXTEND operation
+                    PlanState newState = calculateNextState(currentState, constraintInfo);
+                    // also eagerly perform any CHECK operations that become applicable (extends still deferred)
+                    newState.applyChecksBasedOnDelta(checkOpsByVariables);
+                    
+                    if(currentState.getBoundVariables().size() == newState.getBoundVariables().size()){
+                        // This means no variable binding was done, go on with the next constraint info
+                        continue;
+                    }
+                    int i2 = variableCount - newState.getBoundVariables().size();
+                    
+                    List<Integer> newIndices = determineIndices(stateTable, i2, newState, k);
+                    int a = newIndices.get(0);
+                    int c = newIndices.get(1);
+
+                    if (checkInsertCondition(stateTable.get(i2), newState, reachableBoundVariableSets, a, c, k)) {
+                        updateExtends(newState, currentState, extendOpsByBoundVariables); // preprocess next steps 
+                        insert(stateTable,i2, newState, a, c, k);
+                    }
+                }
+            }
+        }
+
+        return stateTable.get(0).get(0);
+    }
+
+    private List<List<PlanState>> initializeStateTable(int k, int n) {
+        List<List<PlanState>> stateTable = new ArrayList<>();
+        // Initialize state table and fill it with null
+        for (int i = 0; i <= n ; i++) {
+            stateTable.add(new ArrayList<>());
+        }
+        return stateTable;
+    }
+
+    private void insert(List<List<PlanState>> stateTable, int idx, PlanState newState, int a, int c, int k) {
+        stateTable.get(idx).add(c, newState);
+        while(stateTable.get(idx).size() > k){
+            // Truncate back to size k when grows too big
+            stateTable.set(idx, stateTable.get(idx).subList(0, k));
+        }
+    }
+
+    private void updateExtends(PlanState newState, PlanState currentState,  
+            Map<PVariable, ? extends Collection<PConstraintInfo>> extendOpsByBoundVariables) 
+    {
+        List<PConstraintInfo> presentExtends = currentState.getPresentExtends();
+
+        // Recategorize operations
+        newState.updateExtendsBasedOnDelta(presentExtends, extendOpsByBoundVariables);
+        
+        return;
+    }
+
+    private boolean checkInsertCondition(List<PlanState> list, PlanState newState,
+            List<Set<PVariable>> reachableBoundVariableSets, int a, int c, int k) {
+//        boolean isAmongBestK = (a == (k + 1)) && c < a && reachableBoundVariableSets.contains(newState.getBoundVariables());
+        boolean isAmongBestK = a == k && c < a ;
+        boolean isBetterThanCurrent = a < k && c <= a;
+
+        return isAmongBestK || isBetterThanCurrent;
+    }
+
+    private List<Integer> determineIndices(List<List<PlanState>> stateTable, int i2, PlanState newState, int k) {
+        int a = k;
+        int c = 0;
+        List<Integer> acIndices = new ArrayList<>();
+        for (int j = 0; j < k; j++) {
+            if (j < stateTable.get(i2).size()) {
+                PlanState stateInTable = stateTable.get(i2).get(j);
+                if (newState.getBoundVariables().equals(stateInTable.getBoundVariables())) {
+                    // The new state has the same adornment as the stored one - they are not adornment disjoint
+                    a = j;
+                }
+                if (newState.getCost() >= stateInTable.getCost()) {
+                    c = j + 1;
+                }
+            } else {
+                break;
+            }
+        }
+
+        acIndices.add(a);
+        acIndices.add(c);
+        return acIndices;
+    }
+
+    private PlanState calculateNextState(PlanState currentState, PConstraintInfo constraintInfo) {
+        return currentState.cloneWithApplied(constraintInfo);
+    }
+
+    private List<Set<PVariable>> reachabilityAnalysis(PBody pBody, List<PConstraintInfo> constraintInfos) {
+        // TODO implement reachability analisys, also save/persist the results somewhere
+        List<Set<PVariable>> reachableBoundVariableSets = new ArrayList<>();
+        return reachableBoundVariableSets;
+    }
+
+    
+}
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PConstraintCategory.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PConstraintCategory.java
new file mode 100644
index 00000000..b98dd12e
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PConstraintCategory.java
@@ -0,0 +1,41 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, Marton Bur, Zoltan Ujhelyi, Akos Horvath, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner;
+
+
+/**
+ * Expresses the state of a PConstraint application 
+ * condition with respect to a given adornment.
+ * 
+ * @author Marton Bur
+ * @noreference This enum is not intended to be referenced by clients.
+ */
+public enum PConstraintCategory {
+    /*
+     * During plan creation an operation is considered a past 
+     * operation, if an already bound variable is free in the
+     * mask of the operation.
+     * (Mask of the operation: the required binding state of 
+     * the affected variables)
+     */
+    PAST, 
+    /*
+     * The binding states of the variables in the operation 
+     * mask correspond to the current binding states of the 
+     * variables in the search plan
+     */
+    PRESENT, 
+    /*
+     * There is at least one bound variable in the mask of 
+     * a future operation that is still free at the current 
+     * state of the plan. Also, a future operation can't be 
+     * PAST.
+     */
+    FUTURE;
+}
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PConstraintInfo.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PConstraintInfo.java
new file mode 100644
index 00000000..c2c76ef2
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PConstraintInfo.java
@@ -0,0 +1,142 @@
+/** 
+ * Copyright (c) 2010-2015, Marton Bur, Zoltan Ujhelyi, Akos Horvath, Istvan Rath and Danil Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.viatra.runtime.localsearch.planner;
+
+import java.util.Collections;
+import java.util.LinkedHashSet;
+import java.util.Set;
+import java.util.function.Function;
+
+import tools.refinery.viatra.runtime.localsearch.planner.cost.IConstraintEvaluationContext;
+import tools.refinery.viatra.runtime.matchers.backend.ResultProviderRequestor;
+import tools.refinery.viatra.runtime.matchers.context.IQueryBackendContext;
+import tools.refinery.viatra.runtime.matchers.context.IQueryResultProviderAccess;
+import tools.refinery.viatra.runtime.matchers.context.IQueryRuntimeContext;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.analysis.QueryAnalyzer;
+
+/** 
+ * Wraps a PConstraint together with information required for the planner. Currently contains information about the expected binding state of
+ * the affected variables also called application condition, and the cost of the enforcement, based on the meta and/or the runtime context.
+ *  
+ * @author Marton Bur
+ * @noreference This class is not intended to be referenced by clients.
+ */
+public class PConstraintInfo implements IConstraintEvaluationContext {
+
+    private PConstraint constraint;
+    private Set<PVariable> boundMaskVariables;
+    private Set<PVariable> freeMaskVariables;
+    private Set<PConstraintInfo> sameWithDifferentBindings;
+    private IQueryRuntimeContext runtimeContext;
+    private QueryAnalyzer queryAnalyzer;
+    private IQueryResultProviderAccess resultProviderAccess;
+    private ResultProviderRequestor resultRequestor;
+
+    private Double cost;
+    private Function<IConstraintEvaluationContext, Double> costFunction;
+    
+
+    /** 
+     * Instantiates the wrapper
+     * @param constraintfor which the information is added and stored
+     * @param boundMaskVariables the bound variables in the operation mask
+     * @param freeMaskVariables the free variables in the operation mask
+     * @param sameWithDifferentBindings during the planning process, multiple operation adornments are considered for a constraint, so that it
+     * is represented by multiple plan infos. This parameter contains all plan infos that are for the same
+     * constraint, but with different adornment
+     * @param context the query backend context
+     */
+    public PConstraintInfo(PConstraint constraint, Set<PVariable> boundMaskVariables, Set<PVariable> freeMaskVariables,
+        Set<PConstraintInfo> sameWithDifferentBindings, 
+        IQueryBackendContext context,
+        ResultProviderRequestor resultRequestor,
+        Function<IConstraintEvaluationContext, Double> costFunction) {
+        this.constraint = constraint;
+        this.costFunction = costFunction;
+        this.boundMaskVariables = new LinkedHashSet<>(boundMaskVariables);
+        this.freeMaskVariables = new LinkedHashSet<>(freeMaskVariables);
+        this.sameWithDifferentBindings = sameWithDifferentBindings;
+        this.resultRequestor = resultRequestor;
+        this.runtimeContext = context.getRuntimeContext();
+        this.queryAnalyzer = context.getQueryAnalyzer();
+        this.resultProviderAccess = context.getResultProviderAccess();
+
+        this.cost = null; // cost will be computed lazily (esp. important for pattern calls)
+    }
+    
+    @Override
+    public IQueryRuntimeContext getRuntimeContext() {
+        return runtimeContext;
+    }
+
+    @Override
+    public QueryAnalyzer getQueryAnalyzer() {
+        return queryAnalyzer;
+    }
+
+    @Override
+    public PConstraint getConstraint() {
+        return constraint;
+    }
+
+    @Override
+    public Set<PVariable> getFreeVariables() {
+        return freeMaskVariables;
+    }
+
+    @Override
+    public Set<PVariable> getBoundVariables() {
+        return boundMaskVariables;
+    }
+
+    public Set<PConstraintInfo> getSameWithDifferentBindings() {
+        return sameWithDifferentBindings;
+    }
+
+    public double getCost() {
+        if (cost == null) {
+            // Calculate cost of the constraint based on its type
+            cost = costFunction.apply(this);
+        }
+        return cost;
+    }
+
+    public PConstraintCategory getCategory(PBody pBody, Set<PVariable> boundVariables) {
+        if (!Collections.disjoint(boundVariables, this.freeMaskVariables)) {
+            return PConstraintCategory.PAST;
+        } else if (!boundVariables.containsAll(this.boundMaskVariables)) {
+            return PConstraintCategory.FUTURE;
+        } else {
+            return PConstraintCategory.PRESENT;
+        }
+    }
+
+    @Override
+    public String toString() {
+        return String.format("%s, bound variables: %s, cost: \"%.2f\"", constraint.toString(), boundMaskVariables.toString(), cost);
+    }
+
+    /**
+     * @deprecated use {@link #resultProviderRequestor()}
+     */
+    @Override
+    @Deprecated
+    public IQueryResultProviderAccess resultProviderAccess() {
+        return resultProviderAccess;
+    }
+    
+    @Override
+    public ResultProviderRequestor resultProviderRequestor() {
+        return resultRequestor;
+    }
+
+}
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PConstraintInfoInferrer.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PConstraintInfoInferrer.java
new file mode 100644
index 00000000..eeac07ce
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PConstraintInfoInferrer.java
@@ -0,0 +1,278 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Grill Balázs, IncQuery Labs Ltd.
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner;
+
+import tools.refinery.viatra.runtime.localsearch.planner.cost.IConstraintEvaluationContext;
+import tools.refinery.viatra.runtime.matchers.backend.ResultProviderRequestor;
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.context.IQueryBackendContext;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.*;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.AbstractTransitiveClosure;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.ConstantValue;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.TypeConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PParameterDirection;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+import tools.refinery.viatra.runtime.matchers.util.Sets;
+
+import java.util.*;
+import java.util.function.Function;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+
+/**
+ * @author Grill Balázs
+ * @noreference This class is not intended to be referenced by clients.
+ */
+class PConstraintInfoInferrer {
+
+    private static final Predicate<PVariable> SINGLE_USE_VARIABLE = input -> input != null && input.getReferringConstraints().size() == 1;
+
+    private final boolean useIndex;
+    private final Function<IConstraintEvaluationContext, Double> costFunction;
+    private final IQueryBackendContext context;
+    private final ResultProviderRequestor resultRequestor;
+
+
+    public PConstraintInfoInferrer(boolean useIndex,
+            IQueryBackendContext backendContext,
+            ResultProviderRequestor resultRequestor,
+            Function<IConstraintEvaluationContext, Double> costFunction) {
+        this.useIndex = useIndex;
+        this.context = backendContext;
+        this.resultRequestor = resultRequestor;
+        this.costFunction = costFunction;
+    }
+
+
+    /**
+     * Create all possible application condition for all constraint
+     *
+     * @param constraintSet the set of constraints
+     * @return a collection of the wrapper PConstraintInfo objects with all the allowed application conditions
+     */
+    public List<PConstraintInfo> createPConstraintInfos(Set<PConstraint> constraintSet) {
+        List<PConstraintInfo> constraintInfos = new ArrayList<>();
+
+        for (PConstraint pConstraint : constraintSet) {
+            createPConstraintInfoDispatch(constraintInfos, pConstraint);
+        }
+        return constraintInfos;
+    }
+
+    private void createPConstraintInfoDispatch(List<PConstraintInfo> resultList, PConstraint pConstraint){
+        if(pConstraint instanceof ExportedParameter){
+            createConstraintInfoExportedParameter(resultList, (ExportedParameter) pConstraint);
+        } else if(pConstraint instanceof TypeConstraint){
+            createConstraintInfoTypeConstraint(resultList, (TypeConstraint)pConstraint);
+        } else if(pConstraint instanceof TypeFilterConstraint){
+            createConstraintInfoTypeFilterConstraint(resultList, (TypeFilterConstraint)pConstraint);
+        } else if(pConstraint instanceof ConstantValue){
+            createConstraintInfoConstantValue(resultList, (ConstantValue)pConstraint);
+        } else if (pConstraint instanceof Inequality){
+            createConstraintInfoInequality(resultList, (Inequality) pConstraint);
+        } else if (pConstraint instanceof ExpressionEvaluation){
+            createConstraintInfoExpressionEvaluation(resultList, (ExpressionEvaluation)pConstraint);
+        } else if (pConstraint instanceof AggregatorConstraint){
+            createConstraintInfoAggregatorConstraint(resultList, pConstraint, ((AggregatorConstraint) pConstraint).getResultVariable());
+        } else if (pConstraint instanceof PatternMatchCounter){
+            createConstraintInfoAggregatorConstraint(resultList, pConstraint, ((PatternMatchCounter) pConstraint).getResultVariable());
+        } else if (pConstraint instanceof PositivePatternCall){
+            createConstraintInfoPositivePatternCall(resultList, (PositivePatternCall) pConstraint);
+        } else if (pConstraint instanceof AbstractTransitiveClosure) {
+            createConstraintInfoBinaryTransitiveClosure(resultList, (AbstractTransitiveClosure) pConstraint);
+        } else{
+            createConstraintInfoGeneric(resultList, pConstraint);
+        }
+    }
+
+    private void createConstraintInfoConstantValue(List<PConstraintInfo> resultList,
+            ConstantValue pConstraint) {
+        // A ConstantValue constraint has a single variable, which is allowed to be unbound
+        // (extending through ConstantValue is considered a cheap operation)
+        Set<PVariable> affectedVariables = pConstraint.getAffectedVariables();
+        Set<? extends Set<PVariable>> bindings = Sets.powerSet(affectedVariables);
+        doCreateConstraintInfos(resultList, pConstraint, affectedVariables, bindings);
+    }
+
+
+    private void createConstraintInfoPositivePatternCall(List<PConstraintInfo> resultList,
+            PositivePatternCall pCall) {
+        // A pattern call can have any of its variables unbound
+        Set<PVariable> affectedVariables = pCall.getAffectedVariables();
+        // IN parameters cannot be unbound and
+        // OUT parameters cannot be bound
+        Tuple variables = pCall.getVariablesTuple();
+        final Set<PVariable> inVariables = new HashSet<>();
+        Set<PVariable> inoutVariables = new HashSet<>();
+        List<PParameter> parameters = pCall.getReferredQuery().getParameters();
+        for(int i=0;i<parameters.size();i++){
+            switch(parameters.get(i).getDirection()){
+            case IN:
+                inVariables.add((PVariable) variables.get(i));
+                break;
+            case INOUT:
+                inoutVariables.add((PVariable) variables.get(i));
+                break;
+            case OUT:
+            default:
+                break;
+
+            }
+        }
+        Iterable<Set<PVariable>> bindings = Sets.powerSet(inoutVariables).stream()
+                .map(input -> Stream.concat(input.stream(), inVariables.stream()).collect(Collectors.toSet()))
+                .collect(Collectors.toSet());
+
+        doCreateConstraintInfos(resultList, pCall, affectedVariables, bindings);
+    }
+
+    private void createConstraintInfoBinaryTransitiveClosure(List<PConstraintInfo> resultList,
+            AbstractTransitiveClosure closure) {
+        // A pattern call can have any of its variables unbound
+
+        List<PParameter> parameters = closure.getReferredQuery().getParameters();
+        Tuple variables = closure.getVariablesTuple();
+
+        Set<Set<PVariable>> bindings = new HashSet<>();
+        PVariable firstVariable = (PVariable) variables.get(0);
+        PVariable secondVariable = (PVariable) variables.get(1);
+        // Check is always supported
+        bindings.add(new HashSet<>(Arrays.asList(firstVariable, secondVariable)));
+        // If first parameter is not bound mandatorily, it can be left out
+        if (parameters.get(0).getDirection() != PParameterDirection.IN) {
+            bindings.add(Collections.singleton(secondVariable));
+        }
+        // If second parameter is not bound mandatorily, it can be left out
+        if (parameters.get(1).getDirection() != PParameterDirection.IN) {
+            bindings.add(Collections.singleton(firstVariable));
+        }
+
+        doCreateConstraintInfos(resultList, closure, closure.getAffectedVariables(), bindings);
+    }
+
+
+
+    private void createConstraintInfoExportedParameter(List<PConstraintInfo> resultList,
+            ExportedParameter parameter) {
+        // In case of an exported parameter constraint, the parameter must be bound in order to execute
+        Set<PVariable> affectedVariables = parameter.getAffectedVariables();
+        doCreateConstraintInfos(resultList, parameter, affectedVariables, Collections.singleton(affectedVariables));
+    }
+
+    private void createConstraintInfoExpressionEvaluation(List<PConstraintInfo> resultList,
+            ExpressionEvaluation expressionEvaluation) {
+        // An expression evaluation can only have its output variable unbound. All other variables shall be bound
+        PVariable output = expressionEvaluation.getOutputVariable();
+        Set<Set<PVariable>> bindings = new HashSet<>();
+        Set<PVariable> affectedVariables = expressionEvaluation.getAffectedVariables();
+        // All variables bound -> check
+        bindings.add(affectedVariables);
+        // Output variable is not bound -> extend
+        bindings.add(affectedVariables.stream().filter(var -> !Objects.equals(var, output)).collect(Collectors.toSet()));
+        doCreateConstraintInfos(resultList, expressionEvaluation, affectedVariables, bindings);
+    }
+
+    private void createConstraintInfoTypeFilterConstraint(List<PConstraintInfo> resultList,
+            TypeFilterConstraint filter){
+        // In case of type filter, all affected variables must be bound in order to execute
+        Set<PVariable> affectedVariables = filter.getAffectedVariables();
+        doCreateConstraintInfos(resultList, filter, affectedVariables, Collections.singleton(affectedVariables));
+    }
+
+    private void createConstraintInfoInequality(List<PConstraintInfo> resultList,
+            Inequality inequality){
+        // In case of inequality, all affected variables must be bound in order to execute
+        Set<PVariable> affectedVariables = inequality.getAffectedVariables();
+        doCreateConstraintInfos(resultList, inequality, affectedVariables, Collections.singleton(affectedVariables));
+    }
+
+    private void createConstraintInfoAggregatorConstraint(List<PConstraintInfo> resultList,
+            PConstraint pConstraint, PVariable resultVariable){
+        Set<PVariable> affectedVariables = pConstraint.getAffectedVariables();
+
+        // The only variables which can be unbound are single-use
+        Set<PVariable> canBeUnboundVariables =
+                Stream.concat(Stream.of(resultVariable), affectedVariables.stream().filter(SINGLE_USE_VARIABLE)).collect(Collectors.toSet());
+
+        Set<Set<PVariable>> bindings = calculatePossibleBindings(canBeUnboundVariables, affectedVariables);
+
+        doCreateConstraintInfos(resultList, pConstraint, affectedVariables, bindings);
+    }
+
+    /**
+     *
+     * @param canBeUnboundVariables Variables which are allowed to be unbound
+     * @param affectedVariables All affected variables
+     * @return The set of possible bound variable sets
+     */
+    private Set<Set<PVariable>> calculatePossibleBindings(Set<PVariable> canBeUnboundVariables, Set<PVariable> affectedVariables){
+        final Set<PVariable> mustBindVariables = affectedVariables.stream().filter(input -> !canBeUnboundVariables.contains(input)).collect(Collectors.toSet());
+        return Sets.powerSet(canBeUnboundVariables).stream()
+                .map(input -> {
+                    //some variables have to be bound before executing this constraint
+                    Set<PVariable> result= new HashSet<>(input);
+                    result.addAll(mustBindVariables);
+                    return result;
+                })
+                .collect(Collectors.toSet());
+    }
+
+    private void createConstraintInfoGeneric(List<PConstraintInfo> resultList, PConstraint pConstraint){
+        Set<PVariable> affectedVariables = pConstraint.getAffectedVariables();
+
+        // The only variables which can be unbound are single use variables
+        Set<PVariable> canBeUnboundVariables = affectedVariables.stream().filter(SINGLE_USE_VARIABLE).collect(Collectors.toSet());
+
+        Set<Set<PVariable>> bindings = calculatePossibleBindings(canBeUnboundVariables, affectedVariables);
+
+        doCreateConstraintInfos(resultList, pConstraint, affectedVariables, bindings);
+    }
+
+    private void createConstraintInfoTypeConstraint(List<PConstraintInfo> resultList,
+            TypeConstraint typeConstraint) {
+        Set<PVariable> affectedVariables = typeConstraint.getAffectedVariables();
+        Set<? extends Set<PVariable>> bindings = null;
+
+        IInputKey inputKey = typeConstraint.getSupplierKey();
+        if(inputKey.isEnumerable()){
+            bindings = Sets.powerSet(affectedVariables);
+        }else{
+            // For not enumerable types, this constraint can only be a check
+            bindings = Collections.singleton(affectedVariables);
+        }
+
+        doCreateConstraintInfos(resultList, typeConstraint, affectedVariables, bindings);
+    }
+
+    private void doCreateConstraintInfos(List<PConstraintInfo> constraintInfos,
+            PConstraint pConstraint, Set<PVariable> affectedVariables, Iterable<? extends Set<PVariable>> bindings) {
+        Set<PConstraintInfo> sameWithDifferentBindings = new HashSet<>();
+        for (Set<PVariable> boundVariables : bindings) {
+
+            PConstraintInfo info = new PConstraintInfo(pConstraint, boundVariables,
+                    affectedVariables.stream().filter(input -> !boundVariables.contains(input)).collect(Collectors.toSet()),
+                    sameWithDifferentBindings, context, resultRequestor, costFunction);
+            constraintInfos.add(info);
+            sameWithDifferentBindings.add(info);
+        }
+    }
+
+    private Set<Set<PVariable>> excludeUnnavigableOperationMasks(TypeConstraint typeConstraint, Set<? extends Set<PVariable>> bindings) {
+        PVariable firstVariable = typeConstraint.getVariableInTuple(0);
+        return bindings.stream().filter(
+                boundVariablesSet -> (boundVariablesSet.isEmpty() || boundVariablesSet.contains(firstVariable)))
+                .collect(Collectors.toSet());
+    }
+}
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PlanState.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PlanState.java
new file mode 100644
index 00000000..e93b07bc
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PlanState.java
@@ -0,0 +1,283 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, Marton Bur, Zoltan Ujhelyi, Akos Horvath, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.localsearch.planner.util.OperationCostComparator;
+import tools.refinery.viatra.runtime.matchers.algorithms.OrderedIterableMerge;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+
+/**
+ * This class represents the state of the plan during planning.
+ * 
+ * <p> A PlanState represents a sequence of operations (operationsList) and caches the computed cost 
+ * for this operation sequence. The list and the cost are initialized in the constructor. 
+ * However, #categorizeChecks() also updates the operations list (by suffixing checks)
+ * 
+ * @author Marton Bur
+ * @noreference This class is not intended to be referenced by clients.
+ */
+public class PlanState {
+
+    private final PBody pBody;
+    private final List<PConstraintInfo> operationsList;
+    private final Set<PVariable> boundVariables;
+    private final Collection<PVariable> deltaVariables; /* bound since ancestor plan */
+    private final Set<PConstraint> enforcedConstraints;
+    
+    private double cummulativeProduct;
+    private double cost;
+
+    private static Comparator<PConstraintInfo> infoComparator = new OperationCostComparator();
+
+    /*
+     * For a short explanation of past, present and future operations,
+     * see class 
+     */
+    private List<PConstraintInfo> presentExtends;
+
+    /**
+     * Creates an initial state
+     */
+    public PlanState(PBody pBody, Set<PVariable> boundVariables) {
+
+        this(pBody, new ArrayList<>(), boundVariables, boundVariables /* also the delta */, 
+                0.0 /* initial cost */, 1.0 /*initial branch count */);
+    }
+    
+    public PlanState cloneWithApplied(PConstraintInfo op) {
+        // Create operation list based on the current state
+        ArrayList<PConstraintInfo> newOperationsList =  
+                // pre-reserve excess capacity for later addition of CHECK ops
+                new ArrayList<>(pBody.getConstraints().size());
+        newOperationsList.addAll(this.getOperations());
+        newOperationsList.add(op);
+        
+        // Bind the variables of the op
+        Collection<PVariable> deltaVariables = op.getFreeVariables();
+        Set<PVariable> allBoundVariables =
+                // pre-reserve exact capacity as variables are known 
+                // (will not be affected by adding CHECK ops later)
+                new HashSet<>(this.getBoundVariables().size() + deltaVariables.size());
+        allBoundVariables.addAll(this.getBoundVariables());
+        allBoundVariables.addAll(deltaVariables);
+        
+        PlanState newState = new PlanState(getAssociatedPBody(), newOperationsList, allBoundVariables, deltaVariables,
+                cost, cummulativeProduct);
+        newState.accountNewOperation(op);
+        return newState;
+    }
+
+    private PlanState(PBody pBody, List<PConstraintInfo> operationsList, 
+            Set<PVariable> boundVariables, Collection<PVariable> deltaVariables, 
+            double cost, double cummulativeProduct) 
+    {
+        this.pBody = pBody;
+        this.operationsList = operationsList;
+        this.boundVariables = boundVariables;
+        this.enforcedConstraints = new HashSet<>();
+        this.deltaVariables = deltaVariables;
+        this.cost = cost;
+        this.cummulativeProduct = cummulativeProduct;
+    }
+
+    // NOT included for EXTEND: bind all variables of op
+    private void accountNewOperation(PConstraintInfo constraintInfo) {
+        this.enforcedConstraints.add(constraintInfo.getConstraint());
+        accountCost(constraintInfo);
+    }
+
+    private void accountCost(PConstraintInfo constraintInfo) {
+        double constraintCost = constraintInfo.getCost();
+        double branchFactor = constraintCost;
+        if (constraintCost > 0){
+            cost += cummulativeProduct * constraintCost;
+            cummulativeProduct *= branchFactor;
+        }
+    }
+
+
+    public Set<PConstraint> getEnforcedConstraints() {
+        return enforcedConstraints;
+    }
+
+    /**
+     * Re-categorizes given extend operations into already applied or no longer applicable ones (discarded), 
+     * immediately applicable ones (saved as presently viable extends), 
+     * and not yet applicable ones (discarded).
+     * 
+     * @param allPotentialExtendInfos all other extends that may be applicable 
+     * to this plan state now or in the future;
+     * MUST consist of "extend" constraint applications only (at least one free variable)
+     */
+    public void updateExtends(Iterable<PConstraintInfo> allPotentialExtendInfos) {
+        presentExtends = new ArrayList<>();
+        
+        
+        // categorize future/present extend constraint infos
+        for (PConstraintInfo op : allPotentialExtendInfos) {
+            updateExtendInternal(op);
+        }
+    }
+
+    /**
+     * Re-categorizes given extend operations into already applied or no longer applicable ones (discarded), 
+     * immediately applicable ones (saved as presently viable extends),
+     * and not yet applicable ones (discarded).
+     * 
+     * @param extendOpsByBoundVariables all EXTEND operations indexed by affected <i>bound</i> variables
+     * MUST consist of "extend" constraint applications only (at least one free variable)
+     */
+    public void updateExtendsBasedOnDelta(
+            Iterable<PConstraintInfo> previousPresentExtends, 
+            Map<PVariable, ? extends Collection<PConstraintInfo>> extendOpsByBoundVariables) 
+    {
+        presentExtends = new ArrayList<>();
+        if (operationsList.isEmpty())
+            throw new IllegalStateException("Not applicable as starting step");     
+        
+        for (PConstraintInfo extend: previousPresentExtends) {
+            updateExtendInternal(extend);
+        }
+        
+        Set<PConstraintInfo> affectedExtends = new HashSet<>();
+        for (PVariable variable : deltaVariables) {
+            // only those check ops may become applicable that have an affected variable in the delta
+            Collection<PConstraintInfo> extendsForVariable = extendOpsByBoundVariables.get(variable);
+            if (null != extendsForVariable) {
+                affectedExtends.addAll(extendsForVariable);
+            }
+        }
+        for (PConstraintInfo extend: affectedExtends) {
+            updateExtendInternal(extend);
+        }
+    }
+    
+    private void updateExtendInternal(PConstraintInfo op) {
+        if(!enforcedConstraints.contains(op.getConstraint())) {
+            categorizeExtend(op);                
+        }
+    }
+    
+    /**
+     * Check operations that newly became applicable (see {@link #getDeltaVariables()}) 
+     * are appended to operations lists.
+     * 
+     * <p> Will never discover degenerate checks (of PConstraints with zero variables),
+     * so must not use on initial state.
+     * 
+     * @param allPotentialCheckInfos all CHECK operations
+     * MUST consist of "check" constraint applications only (no free variables) 
+     * and must be iterable in decreasing order of cost
+     * 
+     * 
+     */
+    public void applyChecks(List<PConstraintInfo> allPotentialCheckInfos) {
+        applyChecksInternal(allPotentialCheckInfos);        
+    }
+ 
+    /**
+     * Immediately applicable checks are appended to operations lists.
+     * 
+     * @param checkOpsByVariables all CHECK operations indexed by affected variables
+     * MUST consist of "check" constraint applications only (no free variables) 
+     * and each bucket must be iterable in decreasing order of cost
+     */
+    public void applyChecksBasedOnDelta(Map<PVariable, List<PConstraintInfo>> checkOpsByVariables) {
+        if (operationsList.isEmpty())
+            throw new IllegalStateException("Not applicable as starting step");     
+        
+        Iterable<PConstraintInfo> affectedChecks = Collections.emptyList();
+        
+        for (PVariable variable : deltaVariables) {
+            // only those check ops may become applicable that have an affected variable in the delta
+            List<PConstraintInfo> checksForVariable = checkOpsByVariables.get(variable);
+            if (null != checksForVariable) {
+                affectedChecks = OrderedIterableMerge.mergeUniques(affectedChecks, checksForVariable, infoComparator);
+            }
+        }
+        
+        // checks retain their order, no re-sorting needed
+        applyChecksInternal(affectedChecks);
+    }
+
+    private void applyChecksInternal(Iterable<PConstraintInfo> checks) {
+        for (PConstraintInfo checkInfo : checks) {
+            if (this.boundVariables.containsAll(checkInfo.getBoundVariables()) &&
+                    !enforcedConstraints.contains(checkInfo.getConstraint())) 
+            {
+                operationsList.add(checkInfo);
+                accountNewOperation(checkInfo);                    
+            }
+        }
+    }
+
+
+    private void categorizeExtend(PConstraintInfo constraintInfo) {
+        PConstraintCategory category = constraintInfo.getCategory(pBody, boundVariables);
+        if (category == PConstraintCategory.PRESENT) {
+            presentExtends.add(constraintInfo);
+        } else {
+            // do not categorize past/future operations
+        }
+    }
+
+
+    public PBody getAssociatedPBody() {
+        return pBody;
+    }
+
+    public List<PConstraintInfo> getOperations() {
+        return operationsList;
+    }
+
+    public Set<PVariable> getBoundVariables() {
+        return boundVariables;
+    }
+
+    /**
+     * @return the derived cost of the plan contained in the state
+     */
+    public double getCost() {
+        return cost;
+    }
+
+    
+    /**
+     * @return cumulative branching factor
+     * @since 2.1
+     */
+    public double getCummulativeProduct() {
+        return cummulativeProduct;
+    }
+
+    public List<PConstraintInfo> getPresentExtends() {
+        return presentExtends;
+    }
+
+    /**
+     * Contains only those variables that are added by the newest extend 
+     * (or the initially bound ones if no extend yet)
+     */
+    public Collection<PVariable> getDeltaVariables() {
+        return deltaVariables;
+    }
+
+    
+}
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/compiler/AbstractOperationCompiler.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/compiler/AbstractOperationCompiler.java
new file mode 100644
index 00000000..73312dc9
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/compiler/AbstractOperationCompiler.java
@@ -0,0 +1,430 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Zoltan Ujhelyi, IncQuery Labs Ltd.
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner.compiler;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+import tools.refinery.viatra.runtime.localsearch.matcher.CallWithAdornment;
+import tools.refinery.viatra.runtime.localsearch.operations.ISearchOperation;
+import tools.refinery.viatra.runtime.localsearch.operations.check.AggregatorCheck;
+import tools.refinery.viatra.runtime.localsearch.operations.check.BinaryTransitiveClosureCheck;
+import tools.refinery.viatra.runtime.localsearch.operations.check.CheckConstant;
+import tools.refinery.viatra.runtime.localsearch.operations.check.CheckPositivePatternCall;
+import tools.refinery.viatra.runtime.localsearch.operations.check.CountCheck;
+import tools.refinery.viatra.runtime.localsearch.operations.check.ExpressionCheck;
+import tools.refinery.viatra.runtime.localsearch.operations.check.ExpressionEvalCheck;
+import tools.refinery.viatra.runtime.localsearch.operations.check.InequalityCheck;
+import tools.refinery.viatra.runtime.localsearch.operations.check.NACOperation;
+import tools.refinery.viatra.runtime.localsearch.operations.extend.AggregatorExtend;
+import tools.refinery.viatra.runtime.localsearch.operations.extend.CountOperation;
+import tools.refinery.viatra.runtime.localsearch.operations.extend.ExpressionEval;
+import tools.refinery.viatra.runtime.localsearch.operations.extend.ExtendBinaryTransitiveClosure;
+import tools.refinery.viatra.runtime.localsearch.operations.extend.ExtendConstant;
+import tools.refinery.viatra.runtime.localsearch.operations.extend.ExtendPositivePatternCall;
+import tools.refinery.viatra.runtime.localsearch.operations.util.CallInformation;
+import tools.refinery.viatra.runtime.localsearch.planner.util.CompilerHelper;
+import tools.refinery.viatra.runtime.matchers.ViatraQueryRuntimeException;
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.context.IQueryRuntimeContext;
+import tools.refinery.viatra.runtime.matchers.planning.QueryProcessingException;
+import tools.refinery.viatra.runtime.matchers.planning.SubPlan;
+import tools.refinery.viatra.runtime.matchers.planning.operations.PApply;
+import tools.refinery.viatra.runtime.matchers.planning.operations.POperation;
+import tools.refinery.viatra.runtime.matchers.planning.operations.PProject;
+import tools.refinery.viatra.runtime.matchers.planning.operations.PStart;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.AggregatorConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.ExportedParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.ExpressionEvaluation;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.Inequality;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.NegativePatternCall;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.PatternMatchCounter;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.TypeFilterConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.BinaryReflexiveTransitiveClosure;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.BinaryTransitiveClosure;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.ConstantValue;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.TypeConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PParameter;
+
+/**
+ * @author Zoltan Ujhelyi
+ * @since 1.7
+ *
+ */
+public abstract class AbstractOperationCompiler implements IOperationCompiler {
+    
+    protected static final String UNSUPPORTED_TYPE_MESSAGE = "Unsupported type: ";
+
+    protected abstract void createExtend(TypeConstraint typeConstraint, Map<PVariable, Integer> variableMapping);
+
+    /**
+     * @throws ViatraQueryRuntimeException
+     */
+    protected abstract void createCheck(TypeConstraint typeConstraint, Map<PVariable, Integer> variableMapping);
+
+    /**
+     * @throws ViatraQueryRuntimeException
+     */
+    protected abstract void createCheck(TypeFilterConstraint typeConstraint, Map<PVariable, Integer> variableMapping);
+
+    /**
+     * @since 2.0
+     * @throws ViatraQueryRuntimeException
+     */
+    protected abstract void createUnaryTypeCheck(IInputKey type, int position);
+    
+    protected List<ISearchOperation> operations;
+    protected Set<CallWithAdornment> dependencies = new HashSet<>();
+    protected Map<PConstraint, Set<Integer>> variableBindings;
+    private Map<PVariable, Integer> variableMappings;
+    protected final IQueryRuntimeContext runtimeContext;
+
+    public AbstractOperationCompiler(IQueryRuntimeContext runtimeContext) {
+        this.runtimeContext = runtimeContext;
+    }
+
+    /**
+     * Compiles a plan of <code>POperation</code>s to a list of type <code>List&ltISearchOperation></code>
+     * 
+     * @param plan
+     * @param boundParameters
+     * @return an ordered list of POperations that make up the compiled search plan
+     * @throws ViatraQueryRuntimeException
+     */
+    @Override
+    public List<ISearchOperation> compile(SubPlan plan, Set<PParameter> boundParameters) {
+    
+        variableMappings = CompilerHelper.createVariableMapping(plan);
+        variableBindings = CompilerHelper.cacheVariableBindings(plan, variableMappings, boundParameters);
+    
+        operations = new ArrayList<>();
+    
+        List<POperation> operationList = CompilerHelper.createOperationsList(plan);
+        for (POperation pOperation : operationList) {
+            compile(pOperation, variableMappings);
+        }
+    
+        return operations;
+    }
+
+    private void compile(POperation pOperation, Map<PVariable, Integer> variableMapping) {
+    
+        if (pOperation instanceof PApply) {
+            PApply pApply = (PApply) pOperation;
+            PConstraint pConstraint = pApply.getPConstraint();
+           
+            if (isCheck(pConstraint, variableMapping)) {
+                // check
+                createCheckDispatcher(pConstraint, variableMapping);
+            } else {
+                // extend
+                createExtendDispatcher(pConstraint, variableMapping);
+            }
+    
+        } else if (pOperation instanceof PStart) {
+            // nop
+        } else if (pOperation instanceof PProject) {
+            // nop
+        } else {
+            throw new QueryProcessingException("PStart, PApply or PProject was expected, received: " + pOperation.getClass(), null,"Unexpected POperation type", null);
+        }
+    
+    }
+
+    private void createCheckDispatcher(PConstraint pConstraint, Map<PVariable, Integer> variableMapping) {
+        
+        
+        // DeferredPConstraint subclasses
+    
+        // Equalities are normalized
+    
+        if (pConstraint instanceof Inequality) {
+            createCheck((Inequality) pConstraint, variableMapping);
+        } else if (pConstraint instanceof PositivePatternCall){
+            createCheck((PositivePatternCall) pConstraint, variableMapping);
+        } else if (pConstraint instanceof NegativePatternCall) {
+            createCheck((NegativePatternCall) pConstraint,variableMapping);
+        } else if (pConstraint instanceof AggregatorConstraint) {
+            createCheck((AggregatorConstraint) pConstraint, variableMapping);
+        } else if (pConstraint instanceof PatternMatchCounter) {
+            createCheck((PatternMatchCounter) pConstraint, variableMapping);
+        } else if (pConstraint instanceof ExpressionEvaluation) {
+            createCheck((ExpressionEvaluation) pConstraint, variableMapping);
+        } else if (pConstraint instanceof TypeFilterConstraint) {
+            createCheck((TypeFilterConstraint) pConstraint,variableMapping);
+        } else if (pConstraint instanceof ExportedParameter) {
+            // Nothing to do here
+        } else
+        
+        // EnumerablePConstraint subclasses
+    
+        if (pConstraint instanceof BinaryTransitiveClosure) {
+            createCheck((BinaryTransitiveClosure) pConstraint, variableMapping);
+        } else if (pConstraint instanceof BinaryReflexiveTransitiveClosure) {
+            createCheck((BinaryReflexiveTransitiveClosure)pConstraint, variableMapping);
+        } else if (pConstraint instanceof ConstantValue) {
+            createCheck((ConstantValue) pConstraint, variableMapping);
+        } else if (pConstraint instanceof TypeConstraint) {
+            createCheck((TypeConstraint) pConstraint,variableMapping);
+        }  else {
+            String msg = "Unsupported Check constraint: "+pConstraint.toString();
+            throw new QueryProcessingException(msg, null, msg, null);
+        }
+    
+    }
+    
+    protected void createExtendDispatcher(PConstraint pConstraint, Map<PVariable, Integer> variableMapping) {
+    
+        // DeferredPConstraint subclasses
+        
+        // Equalities are normalized
+        if (pConstraint instanceof PositivePatternCall) {
+            createExtend((PositivePatternCall)pConstraint, variableMapping);
+        } else if (pConstraint instanceof AggregatorConstraint) {
+            createExtend((AggregatorConstraint) pConstraint, variableMapping);
+        } else if (pConstraint instanceof PatternMatchCounter) {
+            createExtend((PatternMatchCounter) pConstraint, variableMapping);
+        } else if (pConstraint instanceof ExpressionEvaluation) {
+            createExtend((ExpressionEvaluation) pConstraint, variableMapping);
+        } else if (pConstraint instanceof ExportedParameter) {
+            // ExportedParameters are compiled to NOP
+        } else
+        
+        // EnumerablePConstraint subclasses
+    
+        if (pConstraint instanceof ConstantValue) {
+            createExtend((ConstantValue) pConstraint, variableMapping);
+        } else if (pConstraint instanceof TypeConstraint) {
+            createExtend((TypeConstraint) pConstraint, variableMapping);
+        } else if (pConstraint instanceof BinaryTransitiveClosure) {
+            createExtend((BinaryTransitiveClosure)pConstraint, variableMapping);
+        } else if (pConstraint instanceof BinaryReflexiveTransitiveClosure) {
+            createExtend((BinaryReflexiveTransitiveClosure)pConstraint, variableMapping);
+        } else {
+            String msg = "Unsupported Extend constraint: "+pConstraint.toString();
+            throw new QueryProcessingException(msg, null, msg, null);
+        }
+    }
+    
+    private boolean isCheck(PConstraint pConstraint, final Map<PVariable, Integer> variableMapping) {
+        if (pConstraint instanceof NegativePatternCall){
+            return true;
+        }else if (pConstraint instanceof PositivePatternCall){
+            // Positive pattern call is check if all non-single used variables are bound
+            List<Integer> callVariables = pConstraint.getAffectedVariables().stream()
+                .filter(input -> input.getReferringConstraints().size() > 1)
+                .map(variableMapping::get)
+                .collect(Collectors.toList());
+            return variableBindings.get(pConstraint).containsAll(callVariables);
+        }else if (pConstraint instanceof AggregatorConstraint){
+            PVariable outputvar = ((AggregatorConstraint) pConstraint).getResultVariable();
+            return variableBindings.get(pConstraint).contains(variableMapping.get(outputvar));
+        }else if (pConstraint instanceof PatternMatchCounter){
+            PVariable outputvar = ((PatternMatchCounter) pConstraint).getResultVariable();
+            return variableBindings.get(pConstraint).contains(variableMapping.get(outputvar));
+        }else if (pConstraint instanceof ExpressionEvaluation){
+            PVariable outputvar = ((ExpressionEvaluation) pConstraint).getOutputVariable();
+            return outputvar == null || variableBindings.get(pConstraint).contains(variableMapping.get(outputvar));
+        } else {
+            // In other cases, all variables shall be bound to be a check
+            Set<PVariable> affectedVariables = pConstraint.getAffectedVariables();
+            Set<Integer> varIndices = new HashSet<>();
+            for (PVariable variable : affectedVariables) {
+                varIndices.add(variableMapping.get(variable));
+            }
+            return variableBindings.get(pConstraint).containsAll(varIndices);
+        }
+    }
+
+    @Override
+    public Set<CallWithAdornment> getDependencies() {
+        return dependencies;
+    }
+
+    /**
+     * @return the cached variable bindings for the previously created plan
+     */
+    @Override
+    public Map<PVariable, Integer> getVariableMappings() {
+        return variableMappings;
+    }
+
+    protected void createCheck(PatternMatchCounter counter, Map<PVariable, Integer> variableMapping) {
+        CallInformation information = CallInformation.create(counter, variableMapping, variableBindings.get(counter));
+        operations.add(new CountCheck(information, variableMapping.get(counter.getResultVariable())));
+        dependencies.add(information.getCallWithAdornment());
+    }
+
+    protected void createCheck(PositivePatternCall pCall, Map<PVariable, Integer> variableMapping) {
+        CallInformation information = CallInformation.create(pCall, variableMapping, variableBindings.get(pCall));
+        operations.add(new CheckPositivePatternCall(information));
+        dependencies.add(information.getCallWithAdornment());
+    }
+
+    protected void createCheck(ConstantValue constant, Map<PVariable, Integer> variableMapping) {
+        int position = variableMapping.get(constant.getVariablesTuple().get(0));
+        operations.add(new CheckConstant(position, constant.getSupplierKey()));
+    }
+
+    protected void createCheck(BinaryTransitiveClosure binaryTransitiveClosure, Map<PVariable, Integer> variableMapping) {
+        int sourcePosition = variableMapping.get(binaryTransitiveClosure.getVariablesTuple().get(0));
+        int targetPosition = variableMapping.get(binaryTransitiveClosure.getVariablesTuple().get(1));
+        
+        //The second parameter is NOT bound during execution!
+        CallInformation information = CallInformation.create(binaryTransitiveClosure, variableMapping, Stream.of(sourcePosition).collect(Collectors.toSet()));
+        operations.add(new BinaryTransitiveClosureCheck(information, sourcePosition, targetPosition, false));
+        dependencies.add(information.getCallWithAdornment());
+    }
+    
+    /**
+     * @since 2.0
+     */
+    protected void createCheck(BinaryReflexiveTransitiveClosure binaryTransitiveClosure, Map<PVariable, Integer> variableMapping) {
+        int sourcePosition = variableMapping.get(binaryTransitiveClosure.getVariablesTuple().get(0));
+        int targetPosition = variableMapping.get(binaryTransitiveClosure.getVariablesTuple().get(1));
+        
+        //The second parameter is NOT bound during execution!
+        CallInformation information = CallInformation.create(binaryTransitiveClosure, variableMapping, Stream.of(sourcePosition).collect(Collectors.toSet()));
+        createUnaryTypeCheck(binaryTransitiveClosure.getUniverseType(), sourcePosition);
+        operations.add(new BinaryTransitiveClosureCheck(information, sourcePosition, targetPosition, true));
+        dependencies.add(information.getCallWithAdornment());
+    }
+
+    protected void createCheck(ExpressionEvaluation expressionEvaluation, Map<PVariable, Integer> variableMapping) {
+        // Fill unbound variables with null; simply copy all variables. Unbound variables will be null anyway
+        Iterable<String> inputParameterNames = expressionEvaluation.getEvaluator().getInputParameterNames();
+        Map<String, Integer> nameMap = new HashMap<>();
+        
+        for (String pVariableName : inputParameterNames) {
+            PVariable pVariable = expressionEvaluation.getPSystem().getVariableByNameChecked(pVariableName);
+            nameMap.put(pVariableName, variableMapping.get(pVariable));
+        }
+        
+        // output variable can be null; if null it is an ExpressionCheck
+        if(expressionEvaluation.getOutputVariable() == null){
+            operations.add(new ExpressionCheck(expressionEvaluation.getEvaluator(), nameMap));
+        } else {
+            operations.add(new ExpressionEvalCheck(expressionEvaluation.getEvaluator(), nameMap, expressionEvaluation.isUnwinding(), variableMapping.get(expressionEvaluation.getOutputVariable())));
+        }
+    }
+
+    protected void createCheck(AggregatorConstraint aggregator, Map<PVariable, Integer> variableMapping) {
+        CallInformation information = CallInformation.create(aggregator, variableMapping, variableBindings.get(aggregator));
+        operations.add(new AggregatorCheck(information, aggregator, variableMapping.get(aggregator.getResultVariable())));
+        dependencies.add(information.getCallWithAdornment());
+    }
+
+    protected void createCheck(NegativePatternCall negativePatternCall, Map<PVariable, Integer> variableMapping) {
+        CallInformation information = CallInformation.create(negativePatternCall, variableMapping, variableBindings.get(negativePatternCall));
+        operations.add(new NACOperation(information));
+        dependencies.add(information.getCallWithAdornment());
+    }
+
+    protected void createCheck(Inequality inequality, Map<PVariable, Integer> variableMapping) {
+        operations.add(new InequalityCheck(variableMapping.get(inequality.getWho()), variableMapping.get(inequality.getWithWhom())));
+    }
+
+    protected void createExtend(PositivePatternCall pCall, Map<PVariable, Integer> variableMapping) {
+        CallInformation information = CallInformation.create(pCall, variableMapping, variableBindings.get(pCall));
+        operations.add(new ExtendPositivePatternCall(information));
+        dependencies.add(information.getCallWithAdornment());
+    }
+
+    protected void createExtend(BinaryTransitiveClosure binaryTransitiveClosure, Map<PVariable, Integer> variableMapping) {
+        int sourcePosition = variableMapping.get(binaryTransitiveClosure.getVariablesTuple().get(0));
+        int targetPosition = variableMapping.get(binaryTransitiveClosure.getVariablesTuple().get(1));
+        
+        boolean sourceBound = variableBindings.get(binaryTransitiveClosure).contains(sourcePosition);
+        boolean targetBound = variableBindings.get(binaryTransitiveClosure).contains(targetPosition);
+        
+        CallInformation information = CallInformation.create(binaryTransitiveClosure, variableMapping, variableBindings.get(binaryTransitiveClosure));
+        
+        if (sourceBound && !targetBound) {
+            operations.add(new ExtendBinaryTransitiveClosure.Forward(information, sourcePosition, targetPosition, false));
+            dependencies.add(information.getCallWithAdornment());            
+        } else if (!sourceBound && targetBound) {
+            operations.add(new ExtendBinaryTransitiveClosure.Backward(information, sourcePosition, targetPosition, false));
+            dependencies.add(information.getCallWithAdornment());                        
+        } else {
+            String msg = "Binary transitive closure not supported with two unbound parameters";
+            throw new QueryProcessingException(msg, null, msg, binaryTransitiveClosure.getPSystem().getPattern());
+        }
+    }
+    
+    /**
+     * @since 2.0
+     */
+    protected void createExtend(BinaryReflexiveTransitiveClosure binaryTransitiveClosure, Map<PVariable, Integer> variableMapping) {
+        int sourcePosition = variableMapping.get(binaryTransitiveClosure.getVariablesTuple().get(0));
+        int targetPosition = variableMapping.get(binaryTransitiveClosure.getVariablesTuple().get(1));
+        
+        boolean sourceBound = variableBindings.get(binaryTransitiveClosure).contains(sourcePosition);
+        boolean targetBound = variableBindings.get(binaryTransitiveClosure).contains(targetPosition);
+        
+        CallInformation information = CallInformation.create(binaryTransitiveClosure, variableMapping, variableBindings.get(binaryTransitiveClosure));
+        
+        if (sourceBound && !targetBound) {
+            createUnaryTypeCheck(binaryTransitiveClosure.getUniverseType(), sourcePosition);
+            operations.add(new ExtendBinaryTransitiveClosure.Forward(information, sourcePosition, targetPosition, true));
+            dependencies.add(information.getCallWithAdornment());            
+        } else if (!sourceBound && targetBound) {
+            createUnaryTypeCheck(binaryTransitiveClosure.getUniverseType(), targetPosition);
+            operations.add(new ExtendBinaryTransitiveClosure.Backward(information, sourcePosition, targetPosition, true));
+            dependencies.add(information.getCallWithAdornment());                        
+        } else {
+            String msg = "Binary reflective transitive closure not supported with two unbound parameters";
+            throw new QueryProcessingException(msg, null, msg, binaryTransitiveClosure.getPSystem().getPattern());
+        }
+    }
+
+    protected void createExtend(ConstantValue constant, Map<PVariable, Integer> variableMapping) {
+        int position = variableMapping.get(constant.getVariablesTuple().get(0));
+        operations.add(new ExtendConstant(position, constant.getSupplierKey()));        
+    }
+
+    protected void createExtend(ExpressionEvaluation expressionEvaluation, Map<PVariable, Integer> variableMapping) {
+        // Fill unbound variables with null; simply copy all variables. Unbound variables will be null anyway
+        Iterable<String> inputParameterNames = expressionEvaluation.getEvaluator().getInputParameterNames();
+        Map<String, Integer> nameMap = new HashMap<>();
+        
+        for (String pVariableName : inputParameterNames) {
+            PVariable pVariable = expressionEvaluation.getPSystem().getVariableByNameChecked(pVariableName);
+            nameMap.put(pVariableName, variableMapping.get(pVariable));
+        }
+        
+        // output variable can be null; if null it is an ExpressionCheck
+        if(expressionEvaluation.getOutputVariable() == null){
+            operations.add(new ExpressionCheck(expressionEvaluation.getEvaluator(), nameMap));
+        } else {
+            operations.add(new ExpressionEval(expressionEvaluation.getEvaluator(), nameMap, expressionEvaluation.isUnwinding(), variableMapping.get(expressionEvaluation.getOutputVariable())));
+        }
+    }
+
+    protected void createExtend(AggregatorConstraint aggregator, Map<PVariable, Integer> variableMapping) {
+        CallInformation information = CallInformation.create(aggregator, variableMapping, variableBindings.get(aggregator));
+        operations.add(new AggregatorExtend(information, aggregator, variableMapping.get(aggregator.getResultVariable())));
+        dependencies.add(information.getCallWithAdornment());
+    }
+
+    protected void createExtend(PatternMatchCounter patternMatchCounter, Map<PVariable, Integer> variableMapping) {
+        CallInformation information = CallInformation.create(patternMatchCounter, variableMapping, variableBindings.get(patternMatchCounter));
+        operations.add(new CountOperation(information, variableMapping.get(patternMatchCounter.getResultVariable())));
+        dependencies.add(information.getCallWithAdornment());
+    }
+    
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/compiler/GenericOperationCompiler.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/compiler/GenericOperationCompiler.java
new file mode 100644
index 00000000..d86982e9
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/compiler/GenericOperationCompiler.java
@@ -0,0 +1,101 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Zoltan Ujhelyi, IncQuery Labs Ltd.
+ * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner.compiler;
+
+import tools.refinery.viatra.runtime.localsearch.operations.generic.GenericTypeCheck;
+import tools.refinery.viatra.runtime.localsearch.operations.generic.GenericTypeExtend;
+import tools.refinery.viatra.runtime.localsearch.operations.generic.GenericTypeExtendSingleValue;
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.context.IQueryRuntimeContext;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.TypeFilterConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.TypeConstraint;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+import tools.refinery.viatra.runtime.matchers.tuple.TupleMask;
+
+import java.util.*;
+
+/**
+ * @author Zoltan Ujhelyi
+ * @since 1.7
+ *
+ */
+public class GenericOperationCompiler extends AbstractOperationCompiler {
+
+    public GenericOperationCompiler(IQueryRuntimeContext runtimeContext) {
+        super(runtimeContext);
+    }
+
+    @Override
+    protected void createCheck(TypeFilterConstraint typeConstraint, Map<PVariable, Integer> variableMapping) {
+        IInputKey inputKey = typeConstraint.getInputKey();
+        Tuple tuple = typeConstraint.getVariablesTuple();
+        int[] positions = new int[tuple.getSize()];
+        for (int i = 0; i < tuple.getSize(); i++) {
+            PVariable variable = (PVariable) tuple.get(i);
+            positions[i] = variableMapping.get(variable);
+        }
+        operations.add(new GenericTypeCheck(inputKey, positions, TupleMask.fromSelectedIndices(variableMapping.size(), positions)));
+
+    }
+
+    @Override
+    protected void createCheck(TypeConstraint typeConstraint, Map<PVariable, Integer> variableMapping) {
+        IInputKey inputKey = typeConstraint.getSupplierKey();
+        Tuple tuple = typeConstraint.getVariablesTuple();
+        int[] positions = new int[tuple.getSize()];
+        for (int i = 0; i < tuple.getSize(); i++) {
+            PVariable variable = (PVariable) tuple.get(i);
+            positions[i] = variableMapping.get(variable);
+        }
+        operations.add(new GenericTypeCheck(inputKey, positions, TupleMask.fromSelectedIndices(variableMapping.size(), positions)));
+    }
+
+    @Override
+    protected void createUnaryTypeCheck(IInputKey inputKey, int position) {
+        int[] positions = new int[] {position};
+        operations.add(new GenericTypeCheck(inputKey, positions, TupleMask.fromSelectedIndices(1, positions)));
+    }
+
+    @Override
+    protected void createExtend(TypeConstraint typeConstraint, Map<PVariable, Integer> variableMapping) {
+        IInputKey inputKey = typeConstraint.getSupplierKey();
+        Tuple tuple = typeConstraint.getVariablesTuple();
+
+        int[] positions = new int[tuple.getSize()];
+        List<Integer> boundVariableIndices = new ArrayList<>();
+        List<Integer> boundVariables = new ArrayList<>();
+        Set<Integer> unboundVariables = new HashSet<>();
+        for (int i = 0; i < tuple.getSize(); i++) {
+            PVariable variable = (PVariable) tuple.get(i);
+            Integer position = variableMapping.get(variable);
+            positions[i] = position;
+            if (variableBindings.get(typeConstraint).contains(position)) {
+                boundVariableIndices.add(i);
+                boundVariables.add(position);
+            } else {
+                unboundVariables.add(position);
+            }
+        }
+        TupleMask indexerMask = TupleMask.fromSelectedIndices(inputKey.getArity(), boundVariableIndices);
+        TupleMask callMask = TupleMask.fromSelectedIndices(variableMapping.size(), boundVariables);
+                // If multiple tuple elements from the indexer should be bound to the same variable, we must use a
+                // {@link GenericTypeExtend} check whether the tuple elements have the same value.
+                if (unboundVariables.size() == 1 && indexerMask.getSize() + 1 == indexerMask.getSourceWidth()) {
+            operations.add(new GenericTypeExtendSingleValue(inputKey, positions, callMask, indexerMask, unboundVariables.iterator().next()));
+        } else {
+            operations.add(new GenericTypeExtend(inputKey, positions, callMask, indexerMask, unboundVariables));
+        }
+
+    }
+
+
+
+}
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/compiler/IOperationCompiler.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/compiler/IOperationCompiler.java
new file mode 100644
index 00000000..625a7eb2
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/compiler/IOperationCompiler.java
@@ -0,0 +1,53 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Zoltan Ujhelyi, IncQuery Labs Ltd.
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner.compiler;
+
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.localsearch.matcher.CallWithAdornment;
+import tools.refinery.viatra.runtime.localsearch.matcher.MatcherReference;
+import tools.refinery.viatra.runtime.localsearch.operations.ISearchOperation;
+import tools.refinery.viatra.runtime.matchers.ViatraQueryRuntimeException;
+import tools.refinery.viatra.runtime.matchers.planning.SubPlan;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PParameter;
+
+/**
+ * An operation compiler is responsible for creating executable search plans from the subplan structure.
+ * 
+ * @author Zoltan Ujhelyi
+ * @since 1.7
+ *
+ */
+public interface IOperationCompiler {
+
+    /**
+     * Compiles a plan of <code>POperation</code>s to a list of type <code>List&ltISearchOperation></code>
+     * 
+     * @param plan
+     * @param boundParameters
+     * @return an ordered list of POperations that make up the compiled search plan
+     * @throws ViatraQueryRuntimeException 
+     */
+    List<ISearchOperation> compile(SubPlan plan, Set<PParameter> boundParameters);
+
+    /**
+     * Replaces previous method returning {@link MatcherReference}
+     * @since 2.1
+     */
+    Set<CallWithAdornment> getDependencies();
+
+    /**
+     * @return the cached variable bindings for the previously created plan
+     */
+    Map<PVariable, Integer> getVariableMappings();
+
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/IConstraintEvaluationContext.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/IConstraintEvaluationContext.java
new file mode 100644
index 00000000..9b44612b
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/IConstraintEvaluationContext.java
@@ -0,0 +1,63 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Grill Balázs, IncQuery Labs Ltd.
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner.cost;
+
+import tools.refinery.viatra.runtime.matchers.backend.ResultProviderRequestor;
+import tools.refinery.viatra.runtime.matchers.context.IQueryResultProviderAccess;
+import tools.refinery.viatra.runtime.matchers.context.IQueryRuntimeContext;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import java.util.Collection;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.analysis.QueryAnalyzer;
+
+/**
+ * This interface denotes the evaluation context of a constraint, intended for cost estimation. Provides access to information
+ * on which the cost function can base its calculation.
+ * 
+ * @author Grill Balázs
+ * @since 1.4
+ * @noimplement
+ */
+public interface IConstraintEvaluationContext {
+
+    /**
+     * Get the constraint to be evaluated
+     */
+    public PConstraint getConstraint();
+
+    /**
+     * Unbound variables at the time of evaluating the constraint
+     */
+    public Collection<PVariable> getFreeVariables();
+
+    /**
+     * Bound variables at the time of evaluating the constraint
+     */
+    public Collection<PVariable> getBoundVariables();
+    
+    public IQueryRuntimeContext getRuntimeContext();
+    
+    /**
+     * @since 1.5
+     */
+    public QueryAnalyzer getQueryAnalyzer();
+    
+    /**
+     * @deprecated use {@link #resultProviderRequestor()}
+     * @since 1.5
+     */
+    @Deprecated
+    public IQueryResultProviderAccess resultProviderAccess();
+    
+    /**
+     * @since 2.1
+     */
+    public ResultProviderRequestor resultProviderRequestor();
+    
+}
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/ICostFunction.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/ICostFunction.java
new file mode 100644
index 00000000..4d9d0708
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/ICostFunction.java
@@ -0,0 +1,22 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Grill Balázs, IncQuery Labs Ltd.
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner.cost;
+
+/**
+ * Common interface for cost function implementation
+ * 
+ * @author Grill Balázs
+ * @since 1.4
+ *
+ */
+public interface ICostFunction{
+
+    public double apply(IConstraintEvaluationContext input);
+    
+}
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/HybridMatcherConstraintCostFunction.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/HybridMatcherConstraintCostFunction.java
new file mode 100644
index 00000000..df9292f0
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/HybridMatcherConstraintCostFunction.java
@@ -0,0 +1,91 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Grill Balázs, IncQuery Labs Ltd
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner.cost.impl;
+
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import tools.refinery.viatra.runtime.localsearch.planner.cost.IConstraintEvaluationContext;
+import tools.refinery.viatra.runtime.matchers.backend.IQueryResultProvider;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.ConstantValue;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
+import tools.refinery.viatra.runtime.matchers.tuple.Tuples;
+
+/**
+ * This cost function is intended to be used on hybrid configuration, with the strict restriction than any
+ * non-flattened positive pattern call is executed with Rete engine. This implementation provides the exact number
+ * of matches by invoking the result provider for the called pattern.
+ * 
+ * @deprecated {@link StatisticsBasedConstraintCostFunction} should use {@link IQueryResultProvider#estimateCardinality(tools.refinery.viatra.runtime.matchers.tuple.TupleMask, org.eclipse.viatra.query.runtime.matchers.util.Accuracy)} 
+ */
+@Deprecated
+public class HybridMatcherConstraintCostFunction extends IndexerBasedConstraintCostFunction {
+    
+    @Override
+    protected double _calculateCost(PositivePatternCall patternCall, IConstraintEvaluationContext context) {
+        // Determine local constant constraints which is used to filter results
+        Tuple variables = patternCall.getVariablesTuple();
+        Set<Object> variablesSet = variables.getDistinctElements();
+        final Map<PVariable, Object> constantMap = new HashMap<>();
+        for (PConstraint _constraint : patternCall.getPSystem().getConstraints()) {
+            if (_constraint instanceof ConstantValue){
+                ConstantValue constraint = (ConstantValue) _constraint;
+                PVariable variable = (PVariable) constraint.getVariablesTuple().get(0);
+                if (variablesSet.contains(variable) && context.getBoundVariables().contains(variable)) {
+                    constantMap.put(variable, constraint.getSupplierKey());
+                }
+            }
+        }
+        
+        // Determine filter
+        Object[] filter = new Object[variables.getSize()];
+        for(int i=0; i < variables.getSize(); i++){
+            filter[i] = constantMap.get(variables.get(i));
+        }
+
+        // aggregate keys are the bound and not filtered variables
+        // These will be fixed in runtime, but unknown at planning time
+        // This is represented by indices to ease working with result tuples
+        final Map<Object, Integer> variableIndices = variables.invertIndex();
+        List<Integer> aggregateKeys = context.getBoundVariables().stream()
+                .filter(input -> !constantMap.containsKey(input))
+                .map(variableIndices::get)
+                .collect(Collectors.toList());
+
+        IQueryResultProvider resultProvider = context.resultProviderRequestor().requestResultProvider(patternCall, null);
+        Map<Tuple, Integer> aggregatedCounts = new HashMap<>();
+        
+        // Iterate over all matches and count together matches that has equal values on
+        // aggregateKeys positions. The cost of the pattern call is considered to be the
+        // Maximum of these counted values
+        
+        int result = 0;
+        // NOTE: a stream is not an iterable (cannot be iterated more than once), so to use it in a for-loop
+        // it has to be wrapped; in the following line a lambda is used to implement Iterable#iterator()
+        for (Tuple match : (Iterable<Tuple>) () -> resultProvider.getAllMatches(filter).iterator()) {
+            Tuple extracted = Tuples.flatTupleOf(aggregateKeys.stream().map(match::get).toArray());
+            int count = (aggregatedCounts.containsKey(extracted)) 
+                ? aggregatedCounts.get(extracted) + 1
+                : 1;                
+            aggregatedCounts.put(extracted, count);
+            if (result < count) {
+                result = count;
+            }
+        }
+
+        return result;
+    }
+    
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/IndexerBasedConstraintCostFunction.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/IndexerBasedConstraintCostFunction.java
new file mode 100644
index 00000000..9e2c8680
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/IndexerBasedConstraintCostFunction.java
@@ -0,0 +1,49 @@
+/** 
+ * Copyright (c) 2010-2016, Grill Balázs, IncQuery Labs Ltd.
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.viatra.runtime.localsearch.planner.cost.impl;
+
+import java.util.Optional;
+
+import tools.refinery.viatra.runtime.localsearch.planner.cost.IConstraintEvaluationContext;
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.tuple.TupleMask;
+import tools.refinery.viatra.runtime.matchers.util.Accuracy;
+
+/**
+ * Cost function which calculates cost based on the cardinality of items in the runtime model, provided by the base indexer
+ * 
+ * @author Grill Balázs
+ * @since 1.4
+ */
+public class IndexerBasedConstraintCostFunction extends StatisticsBasedConstraintCostFunction {
+    
+    
+    
+
+    /**
+     * 
+     */
+    public IndexerBasedConstraintCostFunction() {
+        super();
+    }
+
+    /**
+     * @param inverseNavigationPenalty
+     * @since 2.1
+     */
+    public IndexerBasedConstraintCostFunction(double inverseNavigationPenalty) {
+        super(inverseNavigationPenalty);
+    }
+
+    @Override
+    public Optional<Long> projectionSize(IConstraintEvaluationContext input, IInputKey supplierKey, TupleMask groupMask, Accuracy requiredAccuracy) {
+        return input.getRuntimeContext().estimateCardinality(supplierKey, groupMask, requiredAccuracy);
+    }
+    
+}
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/StatisticsBasedConstraintCostFunction.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/StatisticsBasedConstraintCostFunction.java
new file mode 100644
index 00000000..873be31d
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/StatisticsBasedConstraintCostFunction.java
@@ -0,0 +1,413 @@
+/**
+ * Copyright (c) 2010-2016, Grill Balázs, IncQuery Labs Ltd.
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.viatra.runtime.localsearch.planner.cost.impl;
+
+import static tools.refinery.viatra.runtime.matchers.planning.helpers.StatisticsHelper.min;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
+import java.util.Optional;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.localsearch.matcher.integration.AbstractLocalSearchResultProvider;
+import tools.refinery.viatra.runtime.localsearch.planner.cost.IConstraintEvaluationContext;
+import tools.refinery.viatra.runtime.localsearch.planner.cost.ICostFunction;
+import tools.refinery.viatra.runtime.matchers.ViatraQueryRuntimeException;
+import tools.refinery.viatra.runtime.matchers.backend.IQueryResultProvider;
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.planning.helpers.FunctionalDependencyHelper;
+import tools.refinery.viatra.runtime.matchers.psystem.IQueryReference;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.analysis.QueryAnalyzer;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.AggregatorConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.ExportedParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.ExpressionEvaluation;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.Inequality;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.NegativePatternCall;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.PatternMatchCounter;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.TypeFilterConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.BinaryReflexiveTransitiveClosure;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.BinaryTransitiveClosure;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.ConstantValue;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.TypeConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PParameter;
+import tools.refinery.viatra.runtime.matchers.tuple.TupleMask;
+import tools.refinery.viatra.runtime.matchers.util.Accuracy;
+import tools.refinery.viatra.runtime.matchers.util.Preconditions;
+
+/**
+ * Cost function which calculates cost based on the cardinality of items in the runtime model
+ * 
+ * <p> To provide custom statistics, override 
+ *  {@link #projectionSize(IConstraintEvaluationContext, IInputKey, TupleMask, Accuracy)} 
+ *  and {@link #bucketSize(IQueryReference, IConstraintEvaluationContext, TupleMask)}.
+ * 
+ * @author Grill Balázs
+ * @since 1.4
+ */
+public abstract class StatisticsBasedConstraintCostFunction implements ICostFunction {
+    protected static final double MAX_COST = 250.0;
+
+    protected static final double DEFAULT_COST = StatisticsBasedConstraintCostFunction.MAX_COST - 100.0;
+        
+    /**
+     * @since 2.1
+     */
+    public static final double INVERSE_NAVIGATION_PENALTY_DEFAULT = 0.10;
+    /**
+     * @since 2.1
+     */
+    public static final double INVERSE_NAVIGATION_PENALTY_GENERIC = 0.01;
+    /**
+     * @since 2.7
+     */
+    public static final double EVAL_UNWIND_EXTENSION_FACTOR = 3.0;
+    
+    private final double inverseNavigationPenalty;
+    
+    
+    /**
+     * @since 2.1
+     */
+    public StatisticsBasedConstraintCostFunction(double inverseNavigationPenalty) {
+        super();
+        this.inverseNavigationPenalty = inverseNavigationPenalty;
+    }
+    public StatisticsBasedConstraintCostFunction() {
+        this(INVERSE_NAVIGATION_PENALTY_DEFAULT);
+    }
+
+    /**
+     * @deprecated call and implement {@link #projectionSize(IConstraintEvaluationContext, IInputKey, TupleMask, Accuracy)} instead
+     */
+    @Deprecated
+    public long countTuples(final IConstraintEvaluationContext input, final IInputKey supplierKey) {
+        return projectionSize(input, supplierKey, TupleMask.identity(supplierKey.getArity()), Accuracy.EXACT_COUNT).orElse(-1L);
+    }
+    
+    /**
+     * Override this to provide custom statistics on edge/node counts.
+     * New implementors shall implement this instead of {@link #countTuples(IConstraintEvaluationContext, IInputKey)}
+     * @since 2.1
+     */
+    public Optional<Long> projectionSize(final IConstraintEvaluationContext input, final IInputKey supplierKey,
+            final TupleMask groupMask, Accuracy requiredAccuracy) {
+        long legacyCount = countTuples(input, supplierKey);
+        return legacyCount < 0 ? Optional.empty() : Optional.of(legacyCount);
+    }
+
+    /**
+     * Override this to provide custom estimates for match set sizes of called patterns.
+     * @since 2.1
+     */
+    public Optional<Double> bucketSize(final IQueryReference patternCall,
+            final IConstraintEvaluationContext input, TupleMask projMask) {
+        IQueryResultProvider resultProvider = input.resultProviderRequestor().requestResultProvider(patternCall, null);
+        // TODO hack: use LS cost instead of true bucket size estimate
+        if (resultProvider instanceof AbstractLocalSearchResultProvider) {
+            double estimatedCost = ((AbstractLocalSearchResultProvider) resultProvider).estimateCost(projMask);
+            return Optional.of(estimatedCost);
+        } else {            
+            return resultProvider.estimateAverageBucketSize(projMask, Accuracy.APPROXIMATION);
+        }
+    }
+   
+    
+
+    @Override
+    public double apply(final IConstraintEvaluationContext input) {
+        return this.calculateCost(input.getConstraint(), input);
+    }
+
+    protected double _calculateCost(final ConstantValue constant, final IConstraintEvaluationContext input) {
+        return 0.0f;
+    }
+
+    protected double _calculateCost(final TypeConstraint constraint, final IConstraintEvaluationContext input) {
+        final Collection<PVariable> freeMaskVariables = input.getFreeVariables();
+        final Collection<PVariable> boundMaskVariables = input.getBoundVariables();
+        IInputKey supplierKey = constraint.getSupplierKey();
+        long arity = supplierKey.getArity();
+
+        if ((arity == 1)) {
+            // unary constraint
+            return calculateUnaryConstraintCost(constraint, input);
+        } else if ((arity == 2)) {
+            // binary constraint
+            PVariable srcVariable = ((PVariable) constraint.getVariablesTuple().get(0));
+            PVariable dstVariable = ((PVariable) constraint.getVariablesTuple().get(1));
+            boolean isInverse = false;
+            // Check if inverse navigation is needed along the edge
+            if ((freeMaskVariables.contains(srcVariable) && boundMaskVariables.contains(dstVariable))) {
+                isInverse = true;
+            }
+            double binaryExtendCost = calculateBinaryCost(supplierKey, srcVariable, dstVariable, isInverse, input);
+            // Make inverse navigation slightly more expensive than forward navigation
+            // See https://bugs.eclipse.org/bugs/show_bug.cgi?id=501078
+            return (isInverse) ? binaryExtendCost + inverseNavigationPenalty : binaryExtendCost;
+        } else {
+            // n-ary constraint
+            throw new UnsupportedOperationException("Cost calculation for arity " + arity + " is not implemented yet");
+        }
+    }
+
+    
+    /**
+     * @deprecated use/implement {@link #calculateBinaryCost(IInputKey, PVariable, PVariable, boolean, IConstraintEvaluationContext)} instead
+     */
+    @Deprecated
+    protected double calculateBinaryExtendCost(final IInputKey supplierKey, final PVariable srcVariable,
+            final PVariable dstVariable, final boolean isInverse, long edgeCount /* TODO remove */,
+            final IConstraintEvaluationContext input) {
+        throw new UnsupportedOperationException();
+    }
+    
+    /**
+     * @since 2.1
+     */
+    protected double calculateBinaryCost(final IInputKey supplierKey, final PVariable srcVariable,
+            final PVariable dstVariable, final boolean isInverse, 
+            final IConstraintEvaluationContext input) {
+        final Collection<PVariable> freeMaskVariables = input.getFreeVariables();
+        final PConstraint constraint = input.getConstraint();
+        
+//        IQueryMetaContext metaContext = input.getRuntimeContext().getMetaContext();
+//        Collection<InputKeyImplication> implications = metaContext.getImplications(supplierKey);
+
+        Optional<Long> edgeUpper = projectionSize(input,   supplierKey,    TupleMask.identity(2),          Accuracy.BEST_UPPER_BOUND);
+        Optional<Long> srcUpper  = projectionSize(input,   supplierKey,    TupleMask.selectSingle(0, 2),   Accuracy.BEST_UPPER_BOUND);
+        Optional<Long> dstUpper  = projectionSize(input,   supplierKey,    TupleMask.selectSingle(1, 2),   Accuracy.BEST_UPPER_BOUND);
+
+        if (freeMaskVariables.contains(srcVariable) && freeMaskVariables.contains(dstVariable)) {
+            Double branchCount = edgeUpper.map(Long::doubleValue).orElse(
+                    srcUpper.map(Long::doubleValue).orElse(DEFAULT_COST)
+                    *
+                    dstUpper.map(Long::doubleValue).orElse(DEFAULT_COST)
+            );      
+            return branchCount;
+            
+        } else {
+            
+            Optional<Long> srcLower  = projectionSize(input,   supplierKey,    TupleMask.selectSingle(0, 2),   Accuracy.APPROXIMATION);
+            Optional<Long> dstLower  = projectionSize(input,   supplierKey,    TupleMask.selectSingle(1, 2),   Accuracy.APPROXIMATION);
+            
+            List<Optional<Long>> nodeLower = Arrays.asList(srcLower, dstLower);
+            List<Optional<Long>> nodeUpper = Arrays.asList(srcUpper, dstUpper);
+            
+            int from = isInverse ? 1 : 0;
+            int to   = isInverse ? 0 : 1;
+            
+            Optional<Double> costEstimate = Optional.empty();
+            
+            if (!freeMaskVariables.contains(srcVariable) && !freeMaskVariables.contains(dstVariable)) {
+                // both variables bound, this is a simple check
+                costEstimate = min(costEstimate, 0.9);
+            } // TODO use bucket size estimation in the runtime context
+            costEstimate = min(costEstimate, 
+                edgeUpper.flatMap(edges -> 
+                nodeLower.get(from).map(fromNodes ->
+                    // amortize edges over start nodes
+                    (fromNodes == 0) ? 0.0 : (((double) edges) / fromNodes)
+            )));
+            if (navigatesThroughFunctionalDependencyInverse(input, constraint)) {
+                costEstimate = min(costEstimate, nodeUpper.get(to).flatMap(toNodes -> 
+                        nodeLower.get(from).map(fromNodes ->
+                        // due to a reverse functional dependency, the destination count is an upper bound for the edge count
+                        (fromNodes == 0) ? 0.0 : ((double) toNodes) / fromNodes
+                    )));
+            }
+            if (! edgeUpper.isPresent()) {
+                costEstimate = min(costEstimate, nodeUpper.get(to).flatMap(toNodes -> 
+                        nodeLower.get(from).map(fromNodes ->
+                        // If count is 0, no such element exists in the model, so there will be no branching
+                        // TODO rethink, why dstNodeCount / srcNodeCount instead of dstNodeCount? 
+                        // The universally valid bound would be something like sparseEdgeEstimate = dstNodeCount + 1.0
+                        // If we assume sparseness, we can reduce it by a SPARSENESS_FACTOR (e.g. 0.1). 
+                        // Alternatively, discount dstNodeCount * srcNodeCount on a SPARSENESS_EXPONENT (e.g 0.75) and then amortize over srcNodeCount.
+                        fromNodes != 0 ? Math.max(1.0, ((double) toNodes) / fromNodes) : 1.0
+                    )));
+            } 
+            if (navigatesThroughFunctionalDependency(input, constraint)) {
+                // At most one destination value
+                costEstimate = min(costEstimate, 1.0); 
+            }
+            
+            return costEstimate.orElse(DEFAULT_COST);
+
+        }
+    }
+
+    /**
+     * @since 1.7
+     */
+    protected boolean navigatesThroughFunctionalDependency(final IConstraintEvaluationContext input,
+            final PConstraint constraint) {
+        return navigatesThroughFunctionalDependency(input, constraint, input.getBoundVariables(), input.getFreeVariables());
+    }
+    /**
+     * @since 2.1
+     */
+    protected boolean navigatesThroughFunctionalDependencyInverse(final IConstraintEvaluationContext input,
+            final PConstraint constraint) {
+        return navigatesThroughFunctionalDependency(input, constraint, input.getFreeVariables(), input.getBoundVariables());
+    }
+    /**
+     * @since 2.1
+     */
+    protected boolean navigatesThroughFunctionalDependency(final IConstraintEvaluationContext input,
+            final PConstraint constraint, Collection<PVariable> determining, Collection<PVariable> determined) {
+        final QueryAnalyzer queryAnalyzer = input.getQueryAnalyzer();
+        final Map<Set<PVariable>, Set<PVariable>> functionalDependencies = queryAnalyzer
+                .getFunctionalDependencies(Collections.singleton(constraint), false);
+        final Set<PVariable> impliedVariables = FunctionalDependencyHelper.closureOf(determining,
+                functionalDependencies);
+        return ((impliedVariables != null) && impliedVariables.containsAll(determined));
+    }
+    
+    protected double calculateUnaryConstraintCost(final TypeConstraint constraint,
+            final IConstraintEvaluationContext input) {
+        PVariable variable = (PVariable) constraint.getVariablesTuple().get(0);
+        if (input.getBoundVariables().contains(variable)) {
+            return 0.9;
+        } else {
+            return projectionSize(input, constraint.getSupplierKey(), TupleMask.identity(1), Accuracy.APPROXIMATION)
+                    .map(count -> 1.0 + count).orElse(DEFAULT_COST);
+        }
+    }
+
+    protected double _calculateCost(final ExportedParameter exportedParam, final IConstraintEvaluationContext input) {
+        return 0.0;
+    }
+
+    protected double _calculateCost(final TypeFilterConstraint exportedParam,
+            final IConstraintEvaluationContext input) {
+        return 0.0;
+    }
+
+    protected double _calculateCost(final PositivePatternCall patternCall, final IConstraintEvaluationContext input) {
+        final List<Integer> boundPositions = new ArrayList<>();
+        final List<PParameter> parameters = patternCall.getReferredQuery().getParameters();
+        for (int i = 0; (i < parameters.size()); i++) {
+            final PVariable variable = patternCall.getVariableInTuple(i);
+            if (input.getBoundVariables().contains(variable)) boundPositions.add(i);
+        }
+        TupleMask projMask = TupleMask.fromSelectedIndices(parameters.size(), boundPositions);
+        
+        return bucketSize(patternCall, input, projMask).orElse(DEFAULT_COST);        
+    }
+
+
+    /**
+     * @since 1.7
+     */
+    protected double _calculateCost(final ExpressionEvaluation evaluation, final IConstraintEvaluationContext input) {
+        // Even if there are multiple results here, if all output variable is bound eval unwind will not result in
+        // multiple branches in search graph
+        final double multiplier = evaluation.isUnwinding() && !input.getFreeVariables().isEmpty()
+                ? EVAL_UNWIND_EXTENSION_FACTOR
+                : 1.0;
+        return _calculateCost((PConstraint) evaluation, input) * multiplier;
+    }
+    
+    /**
+     * @since 1.7
+     */
+    protected double _calculateCost(final Inequality inequality, final IConstraintEvaluationContext input) {
+        return _calculateCost((PConstraint)inequality, input);
+    }
+    
+    /**
+     * @since 1.7
+     */
+    protected double _calculateCost(final AggregatorConstraint aggregator, final IConstraintEvaluationContext input) {
+        return _calculateCost((PConstraint)aggregator, input);
+    }
+    
+    /**
+     * @since 1.7
+     */
+    protected double _calculateCost(final NegativePatternCall call, final IConstraintEvaluationContext input) {
+        return _calculateCost((PConstraint)call, input);
+    }
+    
+    /**
+     * @since 1.7
+     */
+    protected double _calculateCost(final PatternMatchCounter counter, final IConstraintEvaluationContext input) {
+        return _calculateCost((PConstraint)counter, input);
+    }
+    
+    /**
+     * @since 1.7
+     */
+    protected double _calculateCost(final BinaryTransitiveClosure closure, final IConstraintEvaluationContext input) {
+        // if (input.getFreeVariables().size() == 1) return 3.0; 
+        return StatisticsBasedConstraintCostFunction.DEFAULT_COST;
+    }
+    
+    /**
+     * @since 2.0
+     */
+    protected double _calculateCost(final BinaryReflexiveTransitiveClosure closure, final IConstraintEvaluationContext input) {
+        // if (input.getFreeVariables().size() == 1) return 3.0; 
+        return StatisticsBasedConstraintCostFunction.DEFAULT_COST;
+    }
+    
+    /**
+     * Default cost calculation strategy
+     */
+    protected double _calculateCost(final PConstraint constraint, final IConstraintEvaluationContext input) {
+        if (input.getFreeVariables().isEmpty()) {
+            return 1.0;
+        } else {
+            return StatisticsBasedConstraintCostFunction.DEFAULT_COST;
+        }
+    }
+
+    /**
+     * @throws ViatraQueryRuntimeException
+     */
+    public double calculateCost(final PConstraint constraint, final IConstraintEvaluationContext input) {
+        Preconditions.checkArgument(constraint != null, "Set constraint value correctly");
+        if (constraint instanceof ExportedParameter) {
+            return _calculateCost((ExportedParameter) constraint, input);
+        } else if (constraint instanceof TypeFilterConstraint) {
+            return _calculateCost((TypeFilterConstraint) constraint, input);
+        } else if (constraint instanceof ConstantValue) {
+            return _calculateCost((ConstantValue) constraint, input);
+        } else if (constraint instanceof PositivePatternCall) {
+            return _calculateCost((PositivePatternCall) constraint, input);
+        } else if (constraint instanceof TypeConstraint) {
+            return _calculateCost((TypeConstraint) constraint, input);
+        } else if (constraint instanceof ExpressionEvaluation) {
+            return _calculateCost((ExpressionEvaluation) constraint, input);
+        } else if (constraint instanceof Inequality) {
+            return _calculateCost((Inequality) constraint, input);
+        } else if (constraint instanceof AggregatorConstraint) {
+            return _calculateCost((AggregatorConstraint) constraint, input);
+        } else if (constraint instanceof NegativePatternCall) {
+            return _calculateCost((NegativePatternCall) constraint, input);
+        } else if (constraint instanceof PatternMatchCounter) {
+            return _calculateCost((PatternMatchCounter) constraint, input);
+        } else if (constraint instanceof BinaryTransitiveClosure) {
+            return _calculateCost((BinaryTransitiveClosure) constraint, input);
+        } else if (constraint instanceof BinaryReflexiveTransitiveClosure) {
+            return _calculateCost((BinaryReflexiveTransitiveClosure) constraint, input);
+        } else {
+            // Default cost calculation
+            return _calculateCost(constraint, input);
+        }
+    }
+}
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/VariableBindingBasedCostFunction.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/VariableBindingBasedCostFunction.java
new file mode 100644
index 00000000..a517af25
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/VariableBindingBasedCostFunction.java
@@ -0,0 +1,95 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Marton Bur, Balazs Grill, Akos Horvath, Zoltan Ujhelyi, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner.cost.impl;
+
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.localsearch.planner.cost.IConstraintEvaluationContext;
+import tools.refinery.viatra.runtime.localsearch.planner.cost.ICostFunction;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.AggregatorConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.ExportedParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.NegativePatternCall;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.BinaryTransitiveClosure;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.ConstantValue;
+
+/**
+ * This class can be used to calculate cost of application of a constraint with a given adornment.
+ * 
+ * For now the logic is based on the following principles:
+ * 
+ * <li>The transitive closures, NACs and count finds are the most expensive operations
+ * 
+ * <li>The number of free variables increase the cost
+ * 
+ * <li>If all the variables of a constraint are free, then its cost equals to twice the number of its parameter
+ * variables. This solves the problem of unnecessary iteration over instances at the beginning of a plan (thus causing
+ * very long run times when executing the plan) by applying constraints based on structural features as soon as
+ * possible.
+ * 
+ * <br>
+ * 
+ * @author Marton Bur
+ * @since 1.4
+ *
+ */
+public class VariableBindingBasedCostFunction implements ICostFunction {
+
+    // Static cost definitions
+    private static int MAX = 1000;
+    private static int exportedParameterCost = MAX - 20;
+    private static int binaryTransitiveClosureCost = MAX - 50;
+    private static int nacCost = MAX - 100;
+    private static int aggregatorCost = MAX - 200;
+    private static int constantCost = 0;
+    
+    @Override
+    public double apply(IConstraintEvaluationContext input) {
+        PConstraint constraint = input.getConstraint();
+        Set<PVariable> affectedVariables = constraint.getAffectedVariables();
+
+        int cost = 0;
+
+        // For constants the cost is determined to be 0.0
+        // The following constraints should be checks:
+        // * Binary transitive closure
+        // * NAC
+        // * count
+        // * exported parameter - only a metadata
+        if (constraint instanceof ConstantValue) {
+            cost = constantCost;
+        } else if (constraint instanceof BinaryTransitiveClosure) {
+            cost = binaryTransitiveClosureCost;
+        } else if (constraint instanceof NegativePatternCall) {
+            cost = nacCost;
+        } else if (constraint instanceof AggregatorConstraint) {
+            cost = aggregatorCost;
+        } else if (constraint instanceof ExportedParameter) {
+            cost = exportedParameterCost;
+        } else {
+            // In case of other constraints count the number of unbound variables
+            for (PVariable pVariable : affectedVariables) {
+                if (input.getFreeVariables().contains(pVariable)) {
+                    // For each free variable ('without-value-variable') increase cost
+                    cost += 1;
+                }
+            }
+            if (cost == affectedVariables.size()) {
+                // If all the variables are free, double the cost.
+                // This ensures that iteration costs more
+                cost *= 2;
+            }
+
+        }
+
+        return Float.valueOf(cost);
+    }
+
+}
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/util/CompilerHelper.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/util/CompilerHelper.java
new file mode 100644
index 00000000..9b4e9ea5
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/util/CompilerHelper.java
@@ -0,0 +1,209 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2014, Marton Bur, Daniel Segesdi, Akos Horvath, Zoltan Ujhelyi, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner.util;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.planning.SubPlan;
+import tools.refinery.viatra.runtime.matchers.planning.operations.PApply;
+import tools.refinery.viatra.runtime.matchers.planning.operations.POperation;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.ExportedParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PParameter;
+
+/**
+ * 
+ * Helper methods for compiling SubPlans
+ * 
+ * @author Marton Bur
+ *
+ */
+public class CompilerHelper {
+
+    private CompilerHelper() {/*Utility class constructor*/}
+    
+    private static boolean isUserSpecified(PVariable var) {
+        return !var.isVirtual() && !var.getName().startsWith("_"); 
+    }
+    
+    public static Map<PVariable, Integer> createVariableMapping(SubPlan plan) {
+        Map<PVariable, Integer> variableMapping = new HashMap<>();
+
+        int variableNumber = 0;
+
+        // Important note: this list might contain duplications when parameters are made equal inside the pattern
+        // This is the expected and normal behavior
+        List<PVariable> symbolicParameterVariables = plan.getBody().getSymbolicParameterVariables();
+        for (PVariable pVariable : symbolicParameterVariables) {
+            if (!variableMapping.containsKey(pVariable)) {
+                variableMapping.put(pVariable, variableNumber++);
+            }
+        }
+
+        List<PVariable> allVariables = new ArrayList<>(plan.getBody().getUniqueVariables());
+        Collections.sort(allVariables, (left, right) -> {
+                    boolean leftUserSpecified = isUserSpecified(left);
+                    boolean rightUserSpecified = isUserSpecified(right);
+                    if (leftUserSpecified && !rightUserSpecified) {
+                        return -1;
+                    } else if (!leftUserSpecified && rightUserSpecified) {
+                        return +1;
+                    } else {
+                        return left.getName().compareTo(right.getName());
+                    }
+                });
+        for (PVariable pVariable : allVariables) {
+            if (!variableMapping.containsKey(pVariable)) {
+                variableMapping.put(pVariable, variableNumber++);
+            }
+        }
+
+        return variableMapping;
+    }
+
+    public static Map<PConstraint, Set<Integer>> cacheVariableBindings(SubPlan plan,
+            Map<PVariable, Integer> variableMappings, Set<PParameter> adornment) {
+
+        Set<Integer> externallyBoundVariables = getVariableIndicesForParameters(plan, variableMappings,
+                adornment);
+
+        Map<PConstraint, Set<Integer>> variableBindings = new HashMap<>();
+
+        List<SubPlan> allPlansInHierarchy = getAllParentPlans(plan);
+        for (SubPlan subPlan : allPlansInHierarchy) {
+            POperation operation = subPlan.getOperation();
+
+            if (operation instanceof PApply) {
+                PConstraint pConstraint = ((PApply) operation).getPConstraint();
+                Set<Integer> boundVariableIndices = getParametersBoundByParentPlan(variableMappings, subPlan);
+                boundVariableIndices.addAll(externallyBoundVariables);
+                
+                variableBindings.put(pConstraint, boundVariableIndices);
+            }
+        }
+        return variableBindings;
+    }
+
+    /**
+     * Returns the list of variable indexes that are bound by the parent plan.
+     */
+    private static Set<Integer> getParametersBoundByParentPlan(Map<PVariable, Integer> variableMappings,
+            SubPlan subPlan) {
+        if (!subPlan.getParentPlans().isEmpty()) {
+            SubPlan parentPlan = subPlan.getParentPlans().get(0);
+            Set<PConstraint> enforcedConstraints = parentPlan.getAllEnforcedConstraints();
+            Set<PVariable> affectedVariables = getAffectedVariables(enforcedConstraints);
+            return getVariableIndices(variableMappings, affectedVariables);
+        }
+        return Collections.emptySet();
+    }
+
+    /**
+     * @param plan
+     * @return all the ancestor plans including the given plan
+     */
+    private static List<SubPlan> getAllParentPlans(SubPlan plan) {
+        SubPlan currentPlan = plan;
+        List<SubPlan> allPlans = new ArrayList<>();
+        allPlans.add(plan);
+        while (!currentPlan.getParentPlans().isEmpty()) {
+            // In the local search it is assumed that only a single parent exists
+            currentPlan = currentPlan.getParentPlans().get(0);
+            allPlans.add(currentPlan);
+        }
+
+        return allPlans;
+    }
+
+    /**
+     * @param variableMappings
+     *            the mapping between variables and their indices
+     * @param variables
+     *            variables to get the indices for
+     * @return the set of variable indices for the given variables
+     */
+    private static Set<Integer> getVariableIndices(Map<PVariable, Integer> variableMappings,
+            Iterable<PVariable> variables) {
+        Set<Integer> variableIndices = new HashSet<>();
+        for (PVariable pVariable : variables) {
+            variableIndices.add(variableMappings.get(pVariable));
+        }
+        return variableIndices;
+    }
+
+    /**
+     * Returns all affected variables of the given PConstraints.
+     */
+    private static Set<PVariable> getAffectedVariables(Set<PConstraint> pConstraints) {
+        Set<PVariable> allDeducedVariables = new HashSet<>();
+        for (PConstraint pConstraint : pConstraints) {
+            allDeducedVariables.addAll(pConstraint.getAffectedVariables());
+        }
+        return allDeducedVariables;
+    }
+
+    /**
+     * Transforms the index of a parameter into the index of a variable of the normalized body.
+     * 
+     * @param plan
+     *            the SubPlan containing the original body and its parameters
+     * @param variableMappings
+     *            the mapping of PVariables to their indices
+     * @param parameters
+     *            a set of parameters
+     * @return the index of the variable corresponding to the parameter at the given index
+     */
+    private static Set<Integer> getVariableIndicesForParameters(SubPlan plan,
+            Map<PVariable, Integer> variableMappings, Set<PParameter> parameters) {
+        Map<PParameter, PVariable> parameterMapping = new HashMap<>();
+        for (ExportedParameter constraint : plan.getBody().getSymbolicParameters()) {
+            parameterMapping.put(constraint.getPatternParameter(), constraint.getParameterVariable());
+        }
+        
+        Set<Integer> variableIndices = new HashSet<>();
+        for (PParameter parameter : parameters) {
+            PVariable parameterVariable = parameterMapping.get(parameter);
+            if (parameterVariable == null) {
+                // XXX In case of older (pre-1.4) VIATRA versions, PParameters were not stable, see bug 498348
+                parameterVariable = plan.getBody().getVariableByNameChecked(parameter.getName());
+            }
+            Integer variableIndex = variableMappings.get(parameterVariable);
+            variableIndices.add(variableIndex);
+        }
+        return variableIndices;
+    }
+
+    /**
+     * Extracts the operations from a SubPlan into a list of POperations in the order of execution
+     * 
+     * @param plan
+     *            the SubPlan from wich the POperations should be extracted
+     * @return list of POperations extracted from the <code>plan</code>
+     */
+    public static List<POperation> createOperationsList(SubPlan plan) {
+        List<POperation> operationsList = new ArrayList<>();
+        while (plan.getParentPlans().size() > 0) {
+            operationsList.add(plan.getOperation());
+            SubPlan parentPlan = plan.getParentPlans().get(0);
+            plan = parentPlan;
+        }
+        operationsList.add(plan.getOperation());
+        
+        Collections.reverse(operationsList);
+        return operationsList; 
+    }
+
+}
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/util/OperationCostComparator.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/util/OperationCostComparator.java
new file mode 100644
index 00000000..58f4fc41
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/util/OperationCostComparator.java
@@ -0,0 +1,26 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2015, Marton Bur, Zoltan Ujhelyi, Akos Horvath, Istvan Rath and Danil Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.localsearch.planner.util;
+
+import java.util.Comparator;
+
+import tools.refinery.viatra.runtime.localsearch.planner.PConstraintInfo;
+
+/**
+ * @author Marton Bur
+ *
+ */
+public class OperationCostComparator implements Comparator<PConstraintInfo>{
+
+    @Override
+    public int compare(PConstraintInfo o1, PConstraintInfo o2) {
+        return Double.compare(o1.getCost(), o2.getCost());
+    }
+
+}