Repository: alibaba/GraphScope (language: python)

Issue:
Introduce the high-order statistics provider `GLogue`
**Is your feature request related to a problem? Please describe.**

Introduce the high-order statistics provider `GLogue`, which precomputed and preserves the frequency of small graph patterns (a.k.a., motifs) with size up to $k$ in the data graph. These advanced high-order statistics can afford the optimizer with more precise cost estimation for query patterns, thereby enhancing the effectiveness of the optimization.



Discussion / hints:

Fix patch:
diff --git a/interactive_engine/compiler/pom.xml b/interactive_engine/compiler/pom.xml
index eccc2c3724b0..87e49188cebc 100644
--- a/interactive_engine/compiler/pom.xml
+++ b/interactive_engine/compiler/pom.xml
@@ -173,6 +173,16 @@
             <artifactId>opentelemetry-instrumentation-annotations</artifactId>
             <version>2.1.0</version>
         </dependency>
+        <dependency>
+            <groupId>org.jgrapht</groupId>
+            <artifactId>jgrapht-core</artifactId>
+            <version>1.4.0</version>
+        </dependency>
+        <dependency>
+            <groupId>org.jgrapht</groupId>
+            <artifactId>jgrapht-ext</artifactId>
+            <version>1.0.1</version>
+        </dependency>
     </dependencies>
 
     <profiles>
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/ExtendEdge.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/ExtendEdge.java
new file mode 100644
index 000000000000..66beecab6db0
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/ExtendEdge.java
@@ -0,0 +1,80 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.PatternDirection;
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.EdgeTypeId;
+import com.google.common.collect.ImmutableList;
+
+import java.util.Collections;
+import java.util.List;
+
+public class ExtendEdge {
+    // the src vertex to extend the edge
+    private int srcVertexOrder;
+    // the types of the extend edge
+    private final List<EdgeTypeId> edgeTypeIds;
+    // the direction of the extend edge
+    private PatternDirection direction;
+    // the weight of the extend edge, which indicates the cost to expand the edge.
+    private Double weight;
+
+    public ExtendEdge(int srcVertexOrder, EdgeTypeId edgeTypeId, PatternDirection direction) {
+        this.srcVertexOrder = srcVertexOrder;
+        this.edgeTypeIds = ImmutableList.of(edgeTypeId);
+        this.direction = direction;
+    }
+
+    public ExtendEdge(
+            int srcVertexOrder, List<EdgeTypeId> edgeTypeIds, PatternDirection direction) {
+        this.srcVertexOrder = srcVertexOrder;
+        this.edgeTypeIds = edgeTypeIds;
+        this.direction = direction;
+    }
+
+    public int getSrcVertexOrder() {
+        return srcVertexOrder;
+    }
+
+    public EdgeTypeId getEdgeTypeId() {
+        return edgeTypeIds.get(0);
+    }
+
+    public List<EdgeTypeId> getEdgeTypeIds() {
+        return Collections.unmodifiableList(edgeTypeIds);
+    }
+
+    public PatternDirection getDirection() {
+        return direction;
+    }
+
+    public void setWeight(Double weight) {
+        this.weight = weight;
+    }
+
+    public Double getWeight() {
+        return weight;
+    }
+
+    @Override
+    public String toString() {
+        return srcVertexOrder
+                + (edgeTypeIds.size() == 1 ? edgeTypeIds.get(0).toString() : edgeTypeIds.toString())
+                + ": "
+                + weight;
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/ExtendStep.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/ExtendStep.java
new file mode 100644
index 000000000000..187a89fa75d6
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/ExtendStep.java
@@ -0,0 +1,80 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue;
+
+import java.util.List;
+
+public class ExtendStep {
+    // The dst vertex (type) that will be added in the pattern expansion.
+    private Integer targetVertexType;
+    // the dst vertex order that will be added in the pattern expansion.
+    private Integer targetVertexOrder;
+    // The edges that will be extended in the pattern expansion.
+    private List<ExtendEdge> extendEdges;
+    // The weight of the extend step, which indicates the cost to expand the step.
+    private Double weight;
+
+    public ExtendStep(Integer targetVertexType, List<ExtendEdge> extendEdges) {
+        this.targetVertexType = targetVertexType;
+        this.extendEdges = extendEdges;
+    }
+
+    public Integer getTargetVertexType() {
+        return targetVertexType;
+    }
+
+    public List<ExtendEdge> getExtendEdges() {
+        return extendEdges;
+    }
+
+    public void sortExtendEdges() {
+        extendEdges.sort(
+                (o1, o2) -> {
+                    return o1.getWeight().compareTo(o2.getWeight());
+                });
+    }
+
+    public void setTargetVertexOrder(Integer targetVertexOrder) {
+        this.targetVertexOrder = targetVertexOrder;
+    }
+
+    public Integer getTargetVertexOrder() {
+        return targetVertexOrder;
+    }
+
+    public void setWeight(Double weight) {
+        this.weight = weight;
+    }
+
+    public Double getWeight() {
+        return weight;
+    }
+
+    @Override
+    public String toString() {
+        return "ExtendStep{"
+                + "targetType="
+                + targetVertexType
+                + ", targetOrder="
+                + targetVertexOrder
+                + ", weight="
+                + weight
+                + ", extendEdges="
+                + extendEdges
+                + '}';
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/Glogue.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/Glogue.java
new file mode 100644
index 000000000000..f635d65ac2d0
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/Glogue.java
@@ -0,0 +1,208 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.Pattern;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.PatternVertex;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.SinglePatternVertex;
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.GlogueSchema;
+
+import org.jgrapht.Graph;
+import org.jgrapht.graph.DirectedPseudograph;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import java.util.*;
+
+public class Glogue {
+    // the topology of GLogue graph
+    private Graph<Pattern, GlogueEdge> glogueGraph;
+    // the cardinality estimation of patterns in Glogue
+    private GlogueCardinalityEstimation glogueCardinalityEstimation;
+    // the root patterns in Glogue, i.e., those one-vertex patterns.
+    private List<Pattern> roots;
+    // maxPatternId records the max pattern id in Glogue
+    private int maxPatternId;
+    private int maxPatternSize;
+
+    private static Logger logger = LoggerFactory.getLogger(Glogue.class);
+
+    public Glogue(GlogueSchema schema, int maxPatternSize) {
+        glogueGraph = new DirectedPseudograph<Pattern, GlogueEdge>(GlogueEdge.class);
+        roots = new ArrayList<>();
+        maxPatternId = 0;
+        create(schema, maxPatternSize);
+    }
+
+    // Construct Glogue from a glogue schema with given max pattern size
+    private Glogue create(GlogueSchema schema, int maxPatternSize) {
+        this.maxPatternSize = maxPatternSize;
+        Deque<Pattern> patternQueue = new ArrayDeque<>();
+        for (Integer vertexTypeId : schema.getVertexTypes()) {
+            PatternVertex vertex = new SinglePatternVertex(vertexTypeId);
+            Pattern new_pattern = new Pattern(vertex);
+            this.addPattern(new_pattern);
+            this.addRoot(new_pattern);
+            patternQueue.add(new_pattern);
+        }
+        while (patternQueue.size() > 0) {
+            Pattern pattern = patternQueue.pop();
+            if (pattern.getVertexNumber() >= maxPatternSize) {
+                continue;
+            }
+            List<ExtendStep> extendSteps = pattern.getExtendSteps(schema);
+            for (ExtendStep extendStep : extendSteps) {
+                logger.debug(extendStep.toString());
+                Pattern newPattern = pattern.extend(extendStep);
+                Optional<Pattern> existingPattern = this.getGlogueVertex(newPattern);
+                if (!existingPattern.isPresent()) {
+                    this.addPattern(newPattern);
+                    Map<Integer, Integer> srcToDstPatternMapping =
+                            this.computePatternMapping(pattern, newPattern, extendStep);
+                    this.addEdge(pattern, newPattern, extendStep, srcToDstPatternMapping);
+                    patternQueue.add(newPattern);
+                } else {
+                    if (!this.containsEdge(pattern, existingPattern.get())) {
+                        // notice that the mapping should be computed based on pattern to
+                        // newPattern,
+                        // rather than pattern to existingPattern
+                        Map<Integer, Integer> srcToDstPatternMapping =
+                                this.computePatternMapping(pattern, newPattern, extendStep);
+                        this.addEdge(
+                                pattern, existingPattern.get(), extendStep, srcToDstPatternMapping);
+                    }
+                }
+            }
+        }
+        // compute pattern cardinality
+        this.glogueCardinalityEstimation = new GlogueBasicCardinalityEstimationImpl(this, schema);
+        logger.debug("GlogueGraph\n" + this.toString());
+
+        return this;
+    }
+
+    public Set<GlogueEdge> getOutEdges(Pattern pattern) {
+        Optional<Pattern> vertex = getGlogueVertex(pattern);
+        if (vertex.isPresent()) {
+            return getGlogueOutEdges(vertex.get());
+        } else {
+            logger.warn("pattern not found in glogue graph, queried pattern " + pattern);
+            return new HashSet<>();
+        }
+    }
+
+    public Set<GlogueEdge> getInEdges(Pattern pattern) {
+        Optional<Pattern> vertex = getGlogueVertex(pattern);
+        if (vertex.isPresent()) {
+            return getGlogueInEdges(vertex.get());
+        } else {
+            logger.warn("pattern not found in glogue graph, queried pattern " + pattern);
+            return new HashSet<>();
+        }
+    }
+
+    public Double getRowCount(Pattern pattern) {
+        return this.glogueCardinalityEstimation.getCardinality(pattern);
+    }
+
+    public int getMaxPatternSize() {
+        return maxPatternSize;
+    }
+
+    protected Set<GlogueEdge> getGlogueOutEdges(Pattern pattern) {
+        return glogueGraph.outgoingEdgesOf(pattern);
+    }
+
+    protected Set<GlogueEdge> getGlogueInEdges(Pattern pattern) {
+        return glogueGraph.incomingEdgesOf(pattern);
+    }
+
+    private void addRoot(Pattern pattern) {
+        this.roots.add(pattern);
+    }
+
+    protected List<Pattern> getRoots() {
+        return roots;
+    }
+
+    private Optional<Pattern> getGlogueVertex(Pattern pattern) {
+        for (Pattern p : this.glogueGraph.vertexSet()) {
+            if (p.equals(pattern)) {
+                return Optional.of(p);
+            }
+        }
+        return Optional.empty();
+    }
+
+    private boolean containsEdge(Pattern srcPattern, Pattern dstPattern) {
+        return this.glogueGraph.containsEdge(srcPattern, dstPattern);
+    }
+
+    private boolean addPattern(Pattern pattern) {
+        pattern.setPatternId(this.maxPatternId++);
+        return this.glogueGraph.addVertex(pattern);
+    }
+
+    private boolean addEdge(
+            Pattern srcPattern,
+            Pattern dstPattern,
+            ExtendStep edge,
+            Map<Integer, Integer> srcToDstIdMapping) {
+        GlogueExtendIntersectEdge glogueEdge =
+                new GlogueExtendIntersectEdge(srcPattern, dstPattern, edge, srcToDstIdMapping);
+        return this.glogueGraph.addEdge(srcPattern, dstPattern, glogueEdge);
+    }
+
+    /// Compute the mapping from src pattern to dst pattern.
+    /// The mapping preserves srcPatternVertexOrder -> dstPatternVertexOrder,
+    /// and the target vertex order will be assigned.
+    /// Notice that, the dstPattern should be extended from srcPattern.
+    private Map<Integer, Integer> computePatternMapping(
+            Pattern srcPattern, Pattern dstPattern, ExtendStep extendStep) {
+        Map<Integer, Integer> srcToDstPatternMapping = new HashMap<>();
+        for (PatternVertex dstVertex : dstPattern.getVertexSet()) {
+            Integer dstVertexOrder = dstPattern.getVertexOrder(dstVertex);
+            // srcPattern is extended from dstPattern, so they have the same vertex id.
+            PatternVertex srcVertex = srcPattern.getVertexById(dstVertex.getId());
+            if (srcVertex == null) {
+                // i.e., the dstVertex is a new vertex added in dstPattern
+                extendStep.setTargetVertexOrder(dstVertexOrder);
+            } else {
+                Integer srcVertexOrder = srcPattern.getVertexOrder(srcVertex);
+                srcToDstPatternMapping.put(srcVertexOrder, dstVertexOrder);
+            }
+        }
+        return srcToDstPatternMapping;
+    }
+
+    @Override
+    public String toString() {
+        String s = "GlogueVertices:\n";
+        for (Pattern p : this.glogueGraph.vertexSet()) {
+            s += p.toString() + "\n";
+        }
+        s += "\nGlogueEdges:\n";
+        for (GlogueEdge e : this.glogueGraph.edgeSet()) {
+            s += e.toString() + "\n";
+        }
+        if (this.glogueCardinalityEstimation != null) {
+            s += "\nGlogueCardinalityEstimation:\n";
+            s += this.glogueCardinalityEstimation.toString();
+        }
+        return s;
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueBasicCardinalityEstimationImpl.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueBasicCardinalityEstimationImpl.java
new file mode 100644
index 000000000000..ee24b7aa3a16
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueBasicCardinalityEstimationImpl.java
@@ -0,0 +1,180 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.Pattern;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.PatternDirection;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.PatternVertex;
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.GlogueSchema;
+
+import org.javatuples.Pair;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import java.util.ArrayDeque;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+
+public class GlogueBasicCardinalityEstimationImpl implements GlogueCardinalityEstimation {
+    private Map<Pattern, Double> patternCardinality;
+    private static Logger logger =
+            LoggerFactory.getLogger(GlogueBasicCardinalityEstimationImpl.class);
+
+    public GlogueBasicCardinalityEstimationImpl(Glogue glogue, GlogueSchema schema) {
+        this.patternCardinality = new HashMap<Pattern, Double>();
+        create(glogue, schema);
+    }
+
+    private GlogueBasicCardinalityEstimationImpl create(Glogue glogue, GlogueSchema schema) {
+        Deque<Pattern> patternQueue = new ArrayDeque<>();
+        List<Pattern> roots = glogue.getRoots();
+        for (Pattern pattern : roots) {
+            // single vertex pattern
+            PatternVertex singleVertexPattern = pattern.getVertexSet().iterator().next();
+            if (singleVertexPattern.getVertexTypeIds().size() != 1) {
+                throw new UnsupportedOperationException(
+                        "In GlogueBasicCardinalityEstimationImpl creation, singleVertexPattern "
+                                + singleVertexPattern
+                                + " is not of basic type.");
+            }
+            Integer vertexTypeId = singleVertexPattern.getVertexTypeIds().get(0);
+            Double singleVertexPatternCount = schema.getVertexTypeCardinality(vertexTypeId);
+            this.patternCardinality.put(pattern, singleVertexPatternCount);
+            patternQueue.add(pattern);
+        }
+
+        while (patternQueue.size() > 0) {
+            Pattern pattern = patternQueue.pop();
+            Double patternCount = this.patternCardinality.get(pattern);
+            for (GlogueEdge edge : glogue.getGlogueOutEdges(pattern)) {
+                GlogueExtendIntersectEdge extendIntersectEdge = (GlogueExtendIntersectEdge) edge;
+                Pattern newPattern = extendIntersectEdge.getDstPattern();
+                ExtendStep extendStep = extendIntersectEdge.getExtendStep();
+
+                if (this.containsPattern(newPattern)) {
+                    // if the cardinality of the pattern is already computed previously, compute the
+                    // pattern extension cost.
+                    Double extendStepWeight = estimateExtendWeight(schema, extendStep);
+                    extendStep.setWeight(extendStepWeight);
+                } else {
+                    // otherwise, compute the cardinality of the pattern, together with the pattern
+                    // extension cost.
+                    Pair<Double, Double> patternCountWithWeight =
+                            estimatePatternCountWithExtendWeight(schema, patternCount, extendStep);
+                    this.patternCardinality.put(newPattern, patternCountWithWeight.getValue0());
+                    extendStep.setWeight(patternCountWithWeight.getValue1());
+                    patternQueue.add(newPattern);
+                }
+            }
+        }
+
+        return this;
+    }
+
+    /// Given the src pattern and extend step, estimate the cardinality of the
+    /// target pattern by extending the extendStep from srcPattern, together with
+    /// pattern extension cost.
+    /// Return the pair of (targetPatternCardinality, extendStepWeight)
+    private Pair<Double, Double> estimatePatternCountWithExtendWeight(
+            GlogueSchema schema, Double srcPatternCount, ExtendStep extendStep) {
+        initEdgeWeightsInExtendStep(schema, extendStep);
+        // estimate pattern count and the weight of the extend step
+        Double commonTargetVertexTypeCount =
+                schema.getVertexTypeCardinality(extendStep.getTargetVertexType());
+        Iterator<ExtendEdge> iter = extendStep.getExtendEdges().iterator();
+        Double targetPatternCount = srcPatternCount * iter.next().getWeight();
+        Double intermediate = targetPatternCount;
+        while (iter.hasNext()) {
+            ExtendEdge extendEdge = iter.next();
+            targetPatternCount *= extendEdge.getWeight() / commonTargetVertexTypeCount;
+            intermediate += targetPatternCount;
+        }
+        return Pair.with(targetPatternCount, intermediate / srcPatternCount);
+    }
+
+    /// Given the src pattern and extend step, estimate the pattern extension cost.
+    /// Return the estimated extendStepWeight.
+    /// Currently, we compute the weight of the extend step in a greedy way;
+    /// we can also compute it in a more accurate way (e.g., enumerate all
+    /// combinations and get the best one)
+    private Double estimateExtendWeight(GlogueSchema schema, ExtendStep extendStep) {
+        initEdgeWeightsInExtendStep(schema, extendStep);
+        Double commonTargetVertexCount =
+                schema.getVertexTypeCardinality(extendStep.getTargetVertexType());
+        Iterator<ExtendEdge> iter = extendStep.getExtendEdges().iterator();
+        Double extendStepWeight = iter.next().getWeight();
+        Double intermediate = 1.0;
+        while (iter.hasNext()) {
+            ExtendEdge extendEdge = iter.next();
+            intermediate *= extendEdge.getWeight() / commonTargetVertexCount;
+            extendStepWeight += intermediate;
+        }
+        return extendStepWeight;
+    }
+
+    private void initEdgeWeightsInExtendStep(GlogueSchema schema, ExtendStep extendStep) {
+        for (ExtendEdge extendEdge : extendStep.getExtendEdges()) {
+            // each extendEdge extends to a new edge
+            // estimate the cardinality by multiplying the edge type cardinality
+            Double extendEdgeCount = schema.getEdgeTypeCardinality(extendEdge.getEdgeTypeId());
+            // each srcVertex is a common vertex when extending the edge
+            // estimate the cardinality by dividing the src vertex type cardinality
+            Integer srcVertexType;
+            if (extendEdge.getDirection().equals(PatternDirection.OUT)) {
+                srcVertexType = extendEdge.getEdgeTypeId().getSrcLabelId();
+            } else {
+                srcVertexType = extendEdge.getEdgeTypeId().getDstLabelId();
+            }
+            Double commonSrcVertexCount = schema.getVertexTypeCardinality(srcVertexType);
+            // Set the ExtendEdge weight: the estimated average pattern cardinality after
+            // extending current expand edge
+            extendEdge.setWeight(extendEdgeCount / commonSrcVertexCount);
+        }
+        extendStep.sortExtendEdges();
+    }
+
+    private boolean containsPattern(Pattern pattern) {
+        return this.patternCardinality.containsKey(pattern);
+    }
+
+    @Override
+    public Double getCardinality(Pattern queryPattern) {
+        for (Pattern pattern : this.patternCardinality.keySet()) {
+            if (pattern.equals(queryPattern)) {
+                return this.patternCardinality.get(pattern);
+            }
+        }
+        return 0.0;
+    }
+
+    @Override
+    public String toString() {
+        String s = "";
+        for (Pattern pattern : this.patternCardinality.keySet()) {
+            s +=
+                    "Pattern "
+                            + pattern.getPatternId()
+                            + ": "
+                            + this.patternCardinality.get(pattern)
+                            + "\n";
+        }
+        return s;
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueCardinalityEstimation.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueCardinalityEstimation.java
new file mode 100644
index 000000000000..5f45743f9ec9
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueCardinalityEstimation.java
@@ -0,0 +1,24 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.Pattern;
+
+public interface GlogueCardinalityEstimation {
+
+    public Double getCardinality(Pattern pattern);
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueEdge.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueEdge.java
new file mode 100644
index 000000000000..40afa8d79b8c
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueEdge.java
@@ -0,0 +1,25 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.Pattern;
+
+public abstract class GlogueEdge {
+    public abstract Pattern getDstPattern();
+
+    public abstract Pattern getSrcPattern();
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueExtendIntersectEdge.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueExtendIntersectEdge.java
new file mode 100644
index 000000000000..3bf93c29e0f9
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueExtendIntersectEdge.java
@@ -0,0 +1,75 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.Pattern;
+
+import java.util.Map;
+
+public class GlogueExtendIntersectEdge extends GlogueEdge {
+    /// a mapping from src pattern vertex order to target pattern vertex order
+    private Map<Integer, Integer> srcToTargetOrderMapping;
+    /// a extend step records how to extend the src pattern to the target pattern
+    private ExtendStep extendStep;
+    /// the src pattern
+    private Pattern srcPattern;
+    /// the target pattern
+    private Pattern dstPattern;
+
+    public GlogueExtendIntersectEdge(
+            Pattern srcPattern,
+            Pattern dstPattern,
+            ExtendStep extendStep,
+            Map<Integer, Integer> srcToTargetOrderMapping) {
+        this.extendStep = extendStep;
+        this.srcPattern = srcPattern;
+        this.dstPattern = dstPattern;
+        this.srcToTargetOrderMapping = srcToTargetOrderMapping;
+    }
+
+    public Map<Integer, Integer> getSrcToTargetOrderMapping() {
+        return srcToTargetOrderMapping;
+    }
+
+    @Override
+    public Pattern getSrcPattern() {
+        return srcPattern;
+    }
+
+    @Override
+    public Pattern getDstPattern() {
+        return dstPattern;
+    }
+
+    public ExtendStep getExtendStep() {
+        return extendStep;
+    }
+
+    @Override
+    public String toString() {
+        return "ExtendIntersectEdge{"
+                + "srcPattern="
+                + srcPattern.getPatternId()
+                + ", dstPattern="
+                + dstPattern.getPatternId()
+                + ", extendStep="
+                + extendStep
+                + ", srcToTargetIdMapping="
+                + srcToTargetOrderMapping
+                + '}';
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueQuery.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueQuery.java
new file mode 100644
index 000000000000..c9205aef64f9
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/GlogueQuery.java
@@ -0,0 +1,69 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.*;
+
+import java.util.Set;
+
+public class GlogueQuery {
+    private Glogue glogue;
+
+    public GlogueQuery(Glogue glogue) {
+        this.glogue = glogue;
+    }
+
+    /**
+     * Get in edges for the given pattern
+     * @param pattern
+     * @return
+     */
+    public Set<GlogueEdge> getInEdges(Pattern pattern) {
+        return glogue.getInEdges(pattern);
+    }
+
+    /**
+     * Get out edges for the given pattern
+     * @param pattern
+     * @return
+     */
+    public Set<GlogueEdge> getOutEdges(Pattern pattern) {
+        return glogue.getOutEdges(pattern);
+    }
+
+    /**
+     * get pattern count
+     * @param pattern
+     * @return
+     */
+    public Double getRowCount(Pattern pattern) {
+        return glogue.getRowCount(pattern);
+    }
+
+    /**
+     * get the max size of the preserved pattern
+     * @return
+     */
+    public int getMaxPatternSize() {
+        return glogue.getMaxPatternSize();
+    }
+
+    @Override
+    public String toString() {
+        return glogue.toString();
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/EdgeIsomorphismChecker.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/EdgeIsomorphismChecker.java
new file mode 100644
index 000000000000..af0e281ac3a7
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/EdgeIsomorphismChecker.java
@@ -0,0 +1,71 @@
+/*
+ * Copyright 2020 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.EdgeTypeId;
+
+import java.util.Collections;
+import java.util.List;
+import java.util.Objects;
+
+public class EdgeIsomorphismChecker implements IsomorphismChecker<EdgeIsomorphismChecker> {
+    private final boolean isBoth;
+    private final List<EdgeTypeId> typeIds;
+    private final ElementDetails details;
+
+    public EdgeIsomorphismChecker(
+            List<EdgeTypeId> typeIds, boolean isBoth, ElementDetails details) {
+        Collections.sort(typeIds, EdgeTypeId::compareTo);
+        this.typeIds = typeIds;
+        this.isBoth = isBoth;
+        this.details = details;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) return true;
+        if (o == null || getClass() != o.getClass()) return false;
+        EdgeIsomorphismChecker that = (EdgeIsomorphismChecker) o;
+        return isBoth == that.isBoth
+                && Objects.equals(typeIds, that.typeIds)
+                && Objects.equals(details, that.details);
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(isBoth, typeIds, details);
+    }
+
+    @Override
+    public int compareTo(EdgeIsomorphismChecker o) {
+        if (this.equals(o)) {
+            return 0;
+        }
+        if (this.typeIds.size() != o.typeIds.size()) {
+            return this.typeIds.size() - o.typeIds.size();
+        }
+        for (int i = 0; i < this.typeIds.size(); i++) {
+            if (!this.typeIds.get(i).equals(o.typeIds.get(i))) {
+                return this.typeIds.get(i).compareTo(o.typeIds.get(i));
+            }
+        }
+        if (this.isBoth != o.isBoth) {
+            return this.isBoth ? 1 : -1;
+        }
+        return this.details.compareTo(o.details);
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/ElementDetails.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/ElementDetails.java
new file mode 100644
index 000000000000..18e68bc6640a
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/ElementDetails.java
@@ -0,0 +1,53 @@
+/*
+ * Copyright 2020 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern;
+
+import java.util.Objects;
+
+public class ElementDetails implements Comparable<ElementDetails> {
+    private final double selectivity;
+
+    public ElementDetails() {
+        this(1.0d);
+    }
+
+    public ElementDetails(double selectivity) {
+        this.selectivity = selectivity;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) return true;
+        if (o == null || getClass() != o.getClass()) return false;
+        ElementDetails that = (ElementDetails) o;
+        return Double.compare(that.selectivity, selectivity) == 0;
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(selectivity);
+    }
+
+    public double getSelectivity() {
+        return selectivity;
+    }
+
+    @Override
+    public int compareTo(ElementDetails o) {
+        return Double.compare(selectivity, o.selectivity);
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/FuzzyPatternEdge.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/FuzzyPatternEdge.java
new file mode 100644
index 000000000000..c7da21a42d4e
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/FuzzyPatternEdge.java
@@ -0,0 +1,67 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.EdgeTypeId;
+
+import java.util.List;
+
+public class FuzzyPatternEdge extends PatternEdge {
+    private int id;
+    private List<EdgeTypeId> edgeTypeIds;
+    private PatternVertex srcVertex;
+    private PatternVertex dstVertex;
+
+    public FuzzyPatternEdge(
+            PatternVertex src, PatternVertex dst, List<EdgeTypeId> edgeTypeIds, int id) {
+        this(src, dst, edgeTypeIds, id, false, new ElementDetails());
+    }
+
+    public FuzzyPatternEdge(
+            PatternVertex src,
+            PatternVertex dst,
+            List<EdgeTypeId> edgeTypeIds,
+            int id,
+            boolean isBoth,
+            ElementDetails details) {
+        super(isBoth, details, new EdgeIsomorphismChecker(edgeTypeIds, isBoth, details));
+        this.edgeTypeIds = edgeTypeIds;
+        this.id = id;
+        this.srcVertex = src;
+        this.dstVertex = dst;
+    }
+
+    @Override
+    public PatternVertex getSrcVertex() {
+        return srcVertex;
+    }
+
+    @Override
+    public PatternVertex getDstVertex() {
+        return dstVertex;
+    }
+
+    @Override
+    public List<EdgeTypeId> getEdgeTypeIds() {
+        return edgeTypeIds;
+    }
+
+    @Override
+    public Integer getId() {
+        return id;
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/FuzzyPatternVertex.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/FuzzyPatternVertex.java
new file mode 100644
index 000000000000..aacde5185a04
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/FuzzyPatternVertex.java
@@ -0,0 +1,49 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern;
+
+import java.util.List;
+
+public class FuzzyPatternVertex extends PatternVertex {
+
+    private Integer id;
+    private List<Integer> vertexTypeIds;
+
+    public FuzzyPatternVertex(List<Integer> vertexTypeIds) {
+        this(vertexTypeIds, 0);
+    }
+
+    public FuzzyPatternVertex(List<Integer> vertexTypeIds, int id) {
+        this(vertexTypeIds, id, new ElementDetails());
+    }
+
+    public FuzzyPatternVertex(List<Integer> typeIds, int id, ElementDetails details) {
+        super(details, new VertexIsomorphismChecker(typeIds, details));
+        this.vertexTypeIds = typeIds;
+        this.id = id;
+    }
+
+    @Override
+    public Integer getId() {
+        return id;
+    }
+
+    @Override
+    public List<Integer> getVertexTypeIds() {
+        return vertexTypeIds;
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/IsomorphismChecker.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/IsomorphismChecker.java
new file mode 100644
index 000000000000..a5eb42278216
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/IsomorphismChecker.java
@@ -0,0 +1,19 @@
+/*
+ * Copyright 2020 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern;
+
+public interface IsomorphismChecker<T> extends Comparable<T> {}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/Pattern.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/Pattern.java
new file mode 100644
index 000000000000..b2c690141083
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/Pattern.java
@@ -0,0 +1,430 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.ExtendEdge;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.ExtendStep;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.utils.Combinations;
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.EdgeTypeId;
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.GlogueSchema;
+
+import org.jgrapht.Graph;
+import org.jgrapht.alg.connectivity.ConnectivityInspector;
+import org.jgrapht.alg.isomorphism.VF2GraphIsomorphismInspector;
+import org.jgrapht.graph.SimpleDirectedGraph;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import java.util.*;
+
+public class Pattern {
+    /// pattern id, i.e., the index of the pattern in Glogue
+    private int id;
+    /// pattern graph, i.e., the topology of the pattern
+    private final Graph<PatternVertex, PatternEdge> patternGraph;
+    /// maxVertexId and maxEdgeId to record the max vertex id and max edge id in the
+    /// pattern
+    private int maxVertexId;
+    private int maxEdgeId;
+    // PatternOrder is used for reordering vertices in Pattern.
+    // Noticed that it is not an identifier of Pattern. i.e., two patterns with same
+    // pattern ordering may not be isomorphic.
+    private PatternOrder patternOrder;
+
+    private final ConnectivityInspector<PatternVertex, PatternEdge> connectivityInspector;
+
+    private static Logger logger = LoggerFactory.getLogger(Pattern.class);
+
+    // vertex type comparator and edge type comparator are used for isomorphism
+    // inspector
+    static final Comparator<PatternVertex> vertexTypeComparator =
+            Comparator.comparing(o -> o.getIsomorphismChecker());
+    static final Comparator<PatternEdge> edgeTypeComparator =
+            Comparator.comparing(o -> o.getIsomorphismChecker());
+
+    public Pattern() {
+        this.patternGraph = new SimpleDirectedGraph<PatternVertex, PatternEdge>(PatternEdge.class);
+        this.connectivityInspector = new ConnectivityInspector<>(this.patternGraph);
+        this.maxVertexId = 0;
+        this.maxEdgeId = 0;
+    }
+
+    public Pattern(Graph<PatternVertex, PatternEdge> patternGraph) {
+        this.patternGraph = patternGraph;
+        this.connectivityInspector = new ConnectivityInspector<>(this.patternGraph);
+        this.maxVertexId = patternGraph.vertexSet().size();
+        this.maxEdgeId = patternGraph.edgeSet().size();
+        this.reordering();
+    }
+
+    public Pattern(Pattern pattern) {
+        this.patternGraph = new SimpleDirectedGraph<PatternVertex, PatternEdge>(PatternEdge.class);
+        for (PatternVertex vertex : pattern.getVertexSet()) {
+            addVertex(vertex);
+        }
+        for (PatternEdge edge : pattern.getEdgeSet()) {
+            addEdge(edge.getSrcVertex(), edge.getDstVertex(), edge);
+        }
+        this.connectivityInspector = new ConnectivityInspector<>(this.patternGraph);
+        this.maxVertexId = pattern.maxVertexId;
+        this.maxEdgeId = pattern.maxEdgeId;
+        this.patternOrder = pattern.patternOrder;
+    }
+
+    public Pattern(PatternVertex vertex) {
+        this.patternGraph = new SimpleDirectedGraph<PatternVertex, PatternEdge>(PatternEdge.class);
+        this.patternGraph.addVertex(vertex);
+        this.connectivityInspector = new ConnectivityInspector<>(this.patternGraph);
+        this.maxVertexId = 1;
+        this.maxEdgeId = 0;
+        this.reordering();
+    }
+
+    public void setPatternId(int id) {
+        this.id = id;
+    }
+
+    public Integer getVertexNumber() {
+        return this.maxVertexId;
+    }
+
+    public Integer getEdgeNumber() {
+        return this.maxEdgeId;
+    }
+
+    public Set<PatternVertex> getVertexSet() {
+        return this.patternGraph.vertexSet();
+    }
+
+    public Set<PatternEdge> getEdgeSet() {
+        return this.patternGraph.edgeSet();
+    }
+
+    public Set<PatternEdge> getEdgesOf(PatternVertex vertex) {
+        return this.patternGraph.edgesOf(vertex);
+    }
+
+    /**
+     * Get all possible extend steps of current pattern based on the given GlogueSchema
+     * @param glogue schema
+     * @return a list of extend steps
+     */
+    public List<ExtendStep> getExtendSteps(GlogueSchema schema) {
+        // For each vertexType in GlogueSchema (i.e., targetPatternVertexType),
+        // consider all possible extend steps from each vertex in current pattern (i.e.,
+        // srcPatternVertexType) to targetPatternVertexType.
+        List<ExtendStep> extendSteps = new ArrayList<>();
+        // Get all vertex labels from pattern meta as the possible extend target vertex
+        List<Integer> targetVertexTypes = schema.getVertexTypes();
+        // targetVertexTypeId -> List of ExtendEdges extend to targetVertex
+        Map<Integer, List<ExtendEdge>> extendEdgesWithDstType = new HashMap<>();
+        for (Integer targetVertexType : targetVertexTypes) {
+            Set<Integer> consideredGroup = new HashSet<>();
+            for (PatternVertex srcPatternVertex : this.getVertexSet()) {
+                Integer srcVertexOrder = this.getVertexOrder(srcPatternVertex);
+                if (consideredGroup.contains(this.getVertexGroup(srcPatternVertex))) {
+                    // Notice that before consider extend edges, skip if the
+                    // srcPatternVertexType is already considered (i.e., if any
+                    // vertex from the same color group is already considered)
+                    continue;
+                } else {
+                    consideredGroup.add(srcVertexOrder);
+                }
+                if (srcPatternVertex.getVertexTypeIds().size() != 1) {
+                    throw new UnsupportedOperationException(
+                            "In ExtendStep, srcPatternVertex "
+                                    + srcPatternVertex
+                                    + " is of basic type");
+                }
+                Integer srcVertexType = srcPatternVertex.getVertexTypeIds().get(0);
+                // Get all adjacent edges from srcVertex to targetVertex
+                List<EdgeTypeId> outEdges = schema.getEdgeTypes(srcVertexType, targetVertexType);
+                for (EdgeTypeId outEdge : outEdges) {
+                    if (srcVertexType.equals(outEdge.getSrcLabelId())) {
+                        ExtendEdge extendEdge =
+                                new ExtendEdge(srcVertexOrder, outEdge, PatternDirection.OUT);
+                        if (extendEdgesWithDstType.containsKey(outEdge.getDstLabelId())) {
+                            extendEdgesWithDstType.get(outEdge.getDstLabelId()).add(extendEdge);
+                        } else {
+                            extendEdgesWithDstType.put(
+                                    outEdge.getDstLabelId(),
+                                    new ArrayList<ExtendEdge>(Arrays.asList(extendEdge)));
+                        }
+                    } else {
+                        throw new UnsupportedOperationException(
+                                "In ExtendStep, srcVertexType "
+                                        + srcVertexType
+                                        + " is not equal to outEdge srcLabelId "
+                                        + outEdge.getSrcLabelId());
+                    }
+                }
+                // Get all adjacent edges from targetVertex to srcVertex
+                List<EdgeTypeId> inEdges = schema.getEdgeTypes(targetVertexType, srcVertexType);
+                for (EdgeTypeId inEdge : inEdges) {
+                    if (srcVertexType.equals(inEdge.getDstLabelId())) {
+                        ExtendEdge extendEdge =
+                                new ExtendEdge(srcVertexOrder, inEdge, PatternDirection.IN);
+                        if (extendEdgesWithDstType.containsKey(inEdge.getSrcLabelId())) {
+                            extendEdgesWithDstType.get(inEdge.getSrcLabelId()).add(extendEdge);
+                        } else {
+                            extendEdgesWithDstType.put(
+                                    inEdge.getSrcLabelId(),
+                                    new ArrayList<ExtendEdge>(Arrays.asList(extendEdge)));
+                        }
+                    } else {
+                        throw new UnsupportedOperationException(
+                                "In ExtendStep, srcVertexType "
+                                        + srcVertexType
+                                        + " is not equal to inEdge dstLabelId "
+                                        + inEdge.getDstLabelId());
+                    }
+                }
+            }
+        }
+
+        // get all subsets of extendEdgesWithDstId. Each subset corresponds to a
+        // possible extend.
+        for (Map.Entry entry : extendEdgesWithDstType.entrySet()) {
+            List<ExtendEdge> orginalSet = (List<ExtendEdge>) entry.getValue();
+            for (int k = 1; k <= orginalSet.size(); k++) {
+                List<List<ExtendEdge>> subsets = Combinations.getCombinations(orginalSet, k);
+                // A subset with duplicated edges. i.e., currently, we allow a pattern of person <->
+                // person
+                for (List<ExtendEdge> subset : subsets) {
+                    extendSteps.add(new ExtendStep((Integer) entry.getKey(), subset));
+                }
+            }
+        }
+
+        return extendSteps;
+    }
+
+    /**
+     * Extend current pattern with the given extendStep, and return the new pattern.
+     * @param extendStep
+     * @return new pattern
+     */
+    public Pattern extend(ExtendStep extendStep) {
+        Pattern newPattern = new Pattern(this);
+        Integer targetVertexTypeId = extendStep.getTargetVertexType();
+        PatternVertex targetVertex =
+                new SinglePatternVertex(targetVertexTypeId, newPattern.maxVertexId);
+        newPattern.addVertex(targetVertex);
+        for (ExtendEdge extendEdge : extendStep.getExtendEdges()) {
+            PatternDirection dir = extendEdge.getDirection();
+            Integer srcVertexOrder = extendEdge.getSrcVertexOrder();
+            PatternVertex srcVertex = newPattern.getVertexByOrder(srcVertexOrder);
+            EdgeTypeId edgeTypeId = extendEdge.getEdgeTypeId();
+            if (dir.equals(PatternDirection.OUT)) {
+                PatternEdge edge =
+                        new SinglePatternEdge(
+                                srcVertex, targetVertex, edgeTypeId, newPattern.maxEdgeId);
+                newPattern.addEdge(srcVertex, targetVertex, edge);
+            } else {
+                PatternEdge edge =
+                        new SinglePatternEdge(
+                                targetVertex, srcVertex, edgeTypeId, newPattern.maxEdgeId);
+                newPattern.addEdge(targetVertex, srcVertex, edge);
+            }
+        }
+        newPattern.reordering();
+        return newPattern;
+    }
+
+    public void reordering() {
+        PatternOrderCanonicalLabelingImpl patternOrder =
+                new PatternOrderCanonicalLabelingImpl(this.patternGraph);
+        this.patternOrder = patternOrder;
+    }
+
+    public boolean addVertex(Integer type) {
+        PatternVertex vertex = new SinglePatternVertex(type, this.maxVertexId);
+        return addVertex(vertex);
+    }
+
+    /**
+     * Add a vertex into pattern
+     * @param vertex
+     * @return true if the vertex is added successfully into pattern graph and false otherwise
+     */
+    public boolean addVertex(PatternVertex vertex) {
+        boolean added = this.patternGraph.addVertex(vertex);
+        if (added) {
+            this.maxVertexId++;
+        }
+        return added;
+    }
+
+    /**
+     * Remove a vertex with its adjacent edges from pattern, and return the connected components of the remaining pattern.
+     * @param vertex
+     * @return the connected components of the remaining pattern
+     */
+    public List<Set<PatternVertex>> removeVertex(PatternVertex vertex) {
+        boolean removed = this.patternGraph.removeVertex(vertex);
+        if (removed) {
+            this.maxVertexId = this.patternGraph.vertexSet().size();
+            this.maxEdgeId = this.patternGraph.edgeSet().size();
+            this.reordering();
+        }
+        return this.connectivityInspector.connectedSets();
+    }
+
+    public int getDegree(PatternVertex vertex) {
+        return this.patternGraph.degreeOf(vertex);
+    }
+
+    /**
+     * Add an edge into pattern
+     * @param srcVertex
+     * @param dstVertex
+     * @param edgeTypeId
+     * @return true if the edge is added successfully into pattern graph and false otherwise
+     */
+    public boolean addEdge(
+            PatternVertex srcVertex, PatternVertex dstVertex, EdgeTypeId edgeTypeId) {
+        PatternEdge edge = new SinglePatternEdge(srcVertex, dstVertex, edgeTypeId, this.maxEdgeId);
+        return addEdge(srcVertex, dstVertex, edge);
+    }
+
+    /**
+     * Add an edge into pattern
+     * @param srcVertex
+     * @param dstVertex
+     * @param edge
+     * @return true if the edge is added successfully into pattern graph and false otherwise
+     */
+    public boolean addEdge(PatternVertex srcVertex, PatternVertex dstVertex, PatternEdge edge) {
+        boolean added = this.patternGraph.addEdge(srcVertex, dstVertex, edge);
+        if (added) {
+            this.maxEdgeId++;
+        }
+        return added;
+    }
+
+    /**
+     * Get the vertex with the given vertex id
+     * @param vertexId
+     * @return the vertex with the given vertex id
+     */
+    public PatternVertex getVertexById(Integer vertexId) {
+        for (PatternVertex vertex : this.patternGraph.vertexSet()) {
+            if (vertex.getId().equals(vertexId)) {
+                return vertex;
+            }
+        }
+        return null;
+    }
+
+    /**
+     * Get the vertex with the given vertex order
+     * @param vertexId
+     * @return the vertex with the given vertex order
+     */
+    public PatternVertex getVertexByOrder(int vertexId) {
+        return this.patternOrder.getVertexByOrder(vertexId);
+    }
+
+    /**
+     * Get the vertex order of the given vertex
+     * @param vertex
+     * @return the vertex order of the given vertex
+     */
+    public Integer getVertexOrder(PatternVertex vertex) {
+        return this.patternOrder.getVertexOrder(vertex);
+    }
+
+    /**
+     * Get the vertex group of the given vertex
+     * @param vertex
+     * @return the vertex group of the given vertex
+     */
+    public Integer getVertexGroup(PatternVertex vertex) {
+        return this.patternOrder.getVertexGroup(vertex);
+    }
+
+    public int getPatternId() {
+        return this.id;
+    }
+
+    @Override
+    public String toString() {
+        return "Pattern "
+                + this.id
+                + " Vertices: "
+                + this.patternGraph.vertexSet().toString()
+                + ", PatternEdges: "
+                + this.patternGraph.edgeSet().toString()
+                + ", PatternOrder: "
+                + this.patternOrder;
+    }
+
+    private boolean preCheck(Pattern other) {
+        // compare vertex number and edge number
+        if (this.maxVertexId != other.maxVertexId || this.maxEdgeId != other.maxEdgeId) {
+            return false;
+        }
+        // compare pattern order
+        if (this.patternOrder == null) {
+            this.reordering();
+        }
+        if (other.patternOrder == null) {
+            other.reordering();
+        }
+        if (!this.patternOrder.equals(other.patternOrder)) {
+            return false;
+        }
+        return true;
+    }
+
+    public boolean isIsomorphicTo(Pattern other) {
+        return isIsomorphicTo(other, vertexTypeComparator, edgeTypeComparator);
+    }
+
+    public boolean isIsomorphicTo(
+            Pattern other,
+            Comparator<PatternVertex> vertexComparator,
+            Comparator<PatternEdge> edgeComparator) {
+        if (this == other) {
+            return true;
+        } else if (!this.preCheck(other)) {
+            return false;
+        } else {
+            VF2GraphIsomorphismInspector<PatternVertex, PatternEdge> isomorphismInspector =
+                    new VF2GraphIsomorphismInspector<PatternVertex, PatternEdge>(
+                            this.patternGraph,
+                            other.patternGraph,
+                            vertexComparator,
+                            edgeComparator);
+            return isomorphismInspector.isomorphismExists();
+        }
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj instanceof Pattern) {
+            Pattern other = (Pattern) obj;
+            return isIsomorphicTo(other);
+        }
+        return false;
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(this.maxVertexId, this.maxEdgeId, this.patternOrder);
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternDirection.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternDirection.java
new file mode 100644
index 000000000000..9efd4772ece2
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternDirection.java
@@ -0,0 +1,23 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern;
+
+public enum PatternDirection {
+    OUT,
+    IN,
+    BOTH
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternEdge.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternEdge.java
new file mode 100644
index 000000000000..273b6765e12b
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternEdge.java
@@ -0,0 +1,80 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.EdgeTypeId;
+
+import java.util.List;
+
+public abstract class PatternEdge {
+    private final boolean isBoth;
+    private final ElementDetails elementDetails;
+    private final IsomorphismChecker isomorphismChecker;
+
+    protected PatternEdge(
+            boolean isBoth, ElementDetails elementDetails, IsomorphismChecker isomorphismChecker) {
+        this.isBoth = isBoth;
+        this.elementDetails = elementDetails;
+        this.isomorphismChecker = isomorphismChecker;
+    }
+
+    public abstract PatternVertex getSrcVertex();
+
+    public abstract PatternVertex getDstVertex();
+
+    public abstract Integer getId();
+
+    public abstract List<EdgeTypeId> getEdgeTypeIds();
+
+    public boolean isBoth() {
+        return this.isBoth;
+    }
+
+    public ElementDetails getElementDetails() {
+        return elementDetails;
+    }
+
+    public IsomorphismChecker getIsomorphismChecker() {
+        return isomorphismChecker;
+    }
+
+    @Override
+    public String toString() {
+        return getSrcVertex().getId()
+                + "->"
+                + getDstVertex().getId()
+                + "["
+                + getEdgeTypeIds().toString()
+                + "]";
+    }
+
+    @Override
+    public int hashCode() {
+        return toString().hashCode();
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (!(o instanceof PatternEdge)) {
+            return false;
+        }
+        PatternEdge other = (PatternEdge) o;
+        return this.getSrcVertex().equals(other.getSrcVertex())
+                && this.getDstVertex().equals(other.getDstVertex())
+                && this.getEdgeTypeIds().equals(other.getEdgeTypeIds());
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternOrder.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternOrder.java
new file mode 100644
index 000000000000..7533e89e62e2
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternOrder.java
@@ -0,0 +1,29 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern;
+
+/// PatternOrder is used to reorder the Pattern, and assign a new order id to each PatternVertex.
+/// A good pattern order can help to reduce the search space of the pattern matching.
+public abstract class PatternOrder {
+    /// Given a PatternVertex v, return its new order after pattern ordering.
+    public abstract Integer getVertexOrder(PatternVertex vertex);
+    /// Given a PatternVertex v, return its group id after pattern ordering.
+    /// Notice if two vertices have the same group id, they must structurally equivalent.
+    public abstract Integer getVertexGroup(PatternVertex vertex);
+    /// Given a order id, return the PatternVertex with the order id after pattern ordering.
+    public abstract PatternVertex getVertexByOrder(Integer id);
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternOrderCanonicalLabelingImpl.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternOrderCanonicalLabelingImpl.java
new file mode 100644
index 000000000000..e919abdcb72e
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternOrderCanonicalLabelingImpl.java
@@ -0,0 +1,221 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern;
+
+import org.jgrapht.Graph;
+import org.jgrapht.alg.color.ColorRefinementAlgorithm;
+import org.jgrapht.alg.interfaces.VertexColoringAlgorithm.Coloring;
+import org.jgrapht.alg.interfaces.VertexColoringAlgorithm.ColoringImpl;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import java.util.*;
+
+public class PatternOrderCanonicalLabelingImpl extends PatternOrder {
+
+    // the initial mapping of vertices <-> colors, i.e., vertices <-> groups.
+    // vertices belongs to the same color means they are structurally equivalent in
+    // the patternGraph
+    private Coloring<PatternVertex> initColoring;
+
+    // the refined mapping of vertices <-> colors that each vertex is assigned a
+    // unique color
+    private Coloring<PatternVertex> uniqueColoring;
+
+    // the mapping of vertex types <-> groups, used for pattern matching
+    // filtering
+    // the key is a IsomorphismChecker (comparator) for vertices, and
+    // the value is a list of group ids
+    private Map<IsomorphismChecker, List<Integer>> mapCheckerToGroup;
+
+    private static Logger logger = LoggerFactory.getLogger(PatternOrderCanonicalLabelingImpl.class);
+
+    public PatternOrderCanonicalLabelingImpl(Graph<PatternVertex, PatternEdge> patternGraph) {
+        // different vertex types are initialized with different colors;
+        // if with multiple vertex types, initialize the colors in order of vertex types
+        Map<PatternVertex, Integer> initialColors = new HashMap<>();
+        Map<IsomorphismChecker, Integer> initialMapCheckerToColor = new HashMap<>();
+        Integer colorId = 0;
+
+        // first, sort the initial types, and assign the color id in order to each
+        // type(s).
+        Set<IsomorphismChecker> checkerSet = new TreeSet();
+        for (PatternVertex patternVertex : patternGraph.vertexSet()) {
+            checkerSet.add(patternVertex.getIsomorphismChecker());
+        }
+        for (IsomorphismChecker checker : checkerSet) {
+            initialMapCheckerToColor.put(checker, colorId);
+            colorId++;
+        }
+
+        // then, assign the color id to each vertex
+        for (PatternVertex patternVertex : patternGraph.vertexSet()) {
+            initialColors.put(
+                    patternVertex,
+                    initialMapCheckerToColor.get(patternVertex.getIsomorphismChecker()));
+        }
+
+        ColoringImpl<PatternVertex> initialColoringImpl =
+                new ColoringImpl<PatternVertex>(initialColors, colorId);
+        ColorRefinementAlgorithm<PatternVertex, PatternEdge> colorRefinementAlgorithm =
+                new ColorRefinementAlgorithm<PatternVertex, PatternEdge>(
+                        patternGraph, initialColoringImpl);
+        Coloring<PatternVertex> initColoring = colorRefinementAlgorithm.getColoring();
+        setTypeGroupMapping(initColoring);
+        this.initColoring = initColoring;
+
+        boolean isUniqueColor = checkUniqueColor(initColoring);
+        Coloring<PatternVertex> newColor;
+        if (!isUniqueColor) {
+            newColor = colorRefinementAlgorithm.getColoring();
+        } else {
+            newColor = initColoring;
+        }
+        while (!isUniqueColor) {
+            newColor = recolor(patternGraph, newColor);
+            isUniqueColor = checkUniqueColor(newColor);
+        }
+        this.uniqueColoring = newColor;
+    }
+
+    // check whether the color is uniquely determined.
+    private boolean checkUniqueColor(Coloring<PatternVertex> patternColoring) {
+        for (Set<PatternVertex> coloredVertices : patternColoring.getColorClasses()) {
+            if (coloredVertices.size() > 1) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    // recolor if the current color is not unique
+    private Coloring<PatternVertex> recolor(
+            Graph<PatternVertex, PatternEdge> patternGraph,
+            Coloring<PatternVertex> patternColoring) {
+        Map<PatternVertex, Integer> initialColors = patternColoring.getColors();
+        int maxColorId = patternColoring.getColorClasses().size();
+        for (Set<PatternVertex> coloredVertices : patternColoring.getColorClasses()) {
+            if (coloredVertices.size() > 1) {
+                // give the structurally-equalled vertex a new color
+                initialColors.put(coloredVertices.iterator().next(), maxColorId++);
+                break;
+            }
+        }
+        ColoringImpl initialColoringImpl = new ColoringImpl(initialColors, maxColorId);
+        ColorRefinementAlgorithm colorRefinementAlgorithm =
+                new ColorRefinementAlgorithm(patternGraph, initialColoringImpl);
+        Coloring<PatternVertex> newColor = colorRefinementAlgorithm.getColoring();
+        return newColor;
+    }
+
+    private void setTypeGroupMapping(Coloring<PatternVertex> color) {
+        mapCheckerToGroup = new TreeMap();
+        Integer groupId = 0;
+        for (Set<PatternVertex> coloredPatternVertices : color.getColorClasses()) {
+            IsomorphismChecker checker =
+                    coloredPatternVertices.iterator().next().getIsomorphismChecker();
+            if (mapCheckerToGroup.containsKey(checker)) {
+                mapCheckerToGroup.get(checker).add(groupId);
+            } else {
+                mapCheckerToGroup.put(checker, new ArrayList<Integer>(Arrays.asList(groupId)));
+            }
+            groupId++;
+        }
+    }
+
+    @Override
+    public Integer getVertexOrder(PatternVertex vertex) {
+        return uniqueColoring.getColors().get(vertex);
+    }
+
+    @Override
+    public Integer getVertexGroup(PatternVertex vertex) {
+        return initColoring.getColors().get(vertex);
+    }
+
+    @Override
+    public PatternVertex getVertexByOrder(Integer id) {
+        return uniqueColoring.getColorClasses().get(id).iterator().next();
+    }
+
+    @Override
+    public String toString() {
+        return "uniqueColoring :"
+                + this.uniqueColoring.toString()
+                + ", groupColoring: "
+                + this.initColoring.toString();
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj instanceof PatternOrderCanonicalLabelingImpl) {
+            PatternOrderCanonicalLabelingImpl other = (PatternOrderCanonicalLabelingImpl) obj;
+            // should have the same number of types and groups
+            if (this.mapCheckerToGroup.size() != other.mapCheckerToGroup.size()
+                    || this.initColoring.getColorClasses().size()
+                            != other.initColoring.getColorClasses().size()) {
+                return false;
+            }
+            // each type should have the same number of groups
+            else {
+                // first compare if types are the same
+                List<IsomorphismChecker> thisTypeList =
+                        new ArrayList<>(this.mapCheckerToGroup.keySet());
+                List<IsomorphismChecker> otherTypeList =
+                        new ArrayList<>(other.mapCheckerToGroup.keySet());
+                if (!thisTypeList.equals(otherTypeList)) {
+                    return false;
+                }
+                // then compare the number of groups for each type
+                for (IsomorphismChecker checker : this.mapCheckerToGroup.keySet()) {
+                    if (this.mapCheckerToGroup.get(checker).size()
+                            != other.mapCheckerToGroup.get(checker).size()) {
+                        logger.debug(
+                                "In color comparing, numbers of groups for type "
+                                        + checker
+                                        + " not equal: "
+                                        + this.mapCheckerToGroup.get(checker).size()
+                                        + " vs "
+                                        + other.mapCheckerToGroup.get(checker).size());
+                        return false;
+                    } else {
+                        List<Integer> colors1 = this.mapCheckerToGroup.get(checker);
+                        colors1.sort(Comparator.naturalOrder());
+                        List<Integer> colors2 = other.mapCheckerToGroup.get(checker);
+                        colors2.sort(Comparator.naturalOrder());
+                        if (!colors1.equals(colors2)) {
+                            logger.debug(
+                                    "In groups comparing, groups for type "
+                                            + checker
+                                            + " not equal: "
+                                            + colors1.toString()
+                                            + " vs "
+                                            + colors2.toString());
+                            return false;
+                        }
+                    }
+                }
+            }
+        }
+        return true;
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(initColoring, mapCheckerToGroup);
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternVertex.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternVertex.java
new file mode 100644
index 000000000000..df080ee40763
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/PatternVertex.java
@@ -0,0 +1,61 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern;
+
+import java.util.List;
+
+public abstract class PatternVertex {
+    private final ElementDetails details;
+    private final IsomorphismChecker isomorphismChecker;
+
+    protected PatternVertex(ElementDetails details, IsomorphismChecker isomorphismChecker) {
+        this.details = details;
+        this.isomorphismChecker = isomorphismChecker;
+    }
+
+    public abstract Integer getId();
+
+    public abstract List<Integer> getVertexTypeIds();
+
+    public IsomorphismChecker getIsomorphismChecker() {
+        return isomorphismChecker;
+    }
+
+    public ElementDetails getDetails() {
+        return details;
+    }
+
+    @Override
+    public String toString() {
+        return getId().toString() + "[" + getVertexTypeIds().toString() + "]";
+    }
+
+    @Override
+    public int hashCode() {
+        return toString().hashCode();
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (!(o instanceof PatternVertex)) {
+            return false;
+        }
+        PatternVertex other = (PatternVertex) o;
+        return this.getId().equals(other.getId())
+                && this.getVertexTypeIds().equals(other.getVertexTypeIds());
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/SinglePatternEdge.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/SinglePatternEdge.java
new file mode 100644
index 000000000000..79b154408cca
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/SinglePatternEdge.java
@@ -0,0 +1,71 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.EdgeTypeId;
+import com.google.common.collect.Lists;
+
+import java.util.Arrays;
+import java.util.List;
+
+public class SinglePatternEdge extends PatternEdge {
+    private int id;
+    private EdgeTypeId edgeTypeId;
+    private PatternVertex srcVertex;
+    private PatternVertex dstVertex;
+
+    public SinglePatternEdge(PatternVertex src, PatternVertex dst, EdgeTypeId edgeTypeId, int id) {
+        this(src, dst, edgeTypeId, id, false, new ElementDetails());
+    }
+
+    public SinglePatternEdge(
+            PatternVertex src,
+            PatternVertex dst,
+            EdgeTypeId edgeTypeId,
+            int id,
+            boolean isBoth,
+            ElementDetails details) {
+        super(
+                isBoth,
+                details,
+                new EdgeIsomorphismChecker(Lists.newArrayList(edgeTypeId), isBoth, details));
+        this.edgeTypeId = edgeTypeId;
+        this.id = id;
+        this.srcVertex = src;
+        this.dstVertex = dst;
+    }
+
+    @Override
+    public PatternVertex getSrcVertex() {
+        return srcVertex;
+    }
+
+    @Override
+    public PatternVertex getDstVertex() {
+        return dstVertex;
+    }
+
+    @Override
+    public List<EdgeTypeId> getEdgeTypeIds() {
+        return Arrays.asList(edgeTypeId);
+    }
+
+    @Override
+    public Integer getId() {
+        return id;
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/SinglePatternVertex.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/SinglePatternVertex.java
new file mode 100644
index 000000000000..1afffb488a7d
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/SinglePatternVertex.java
@@ -0,0 +1,51 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern;
+
+import com.google.common.collect.Lists;
+
+import java.util.Arrays;
+import java.util.List;
+
+public class SinglePatternVertex extends PatternVertex {
+    private Integer vertexTypeId;
+    private Integer id;
+
+    public SinglePatternVertex(Integer vertexTypeId) {
+        this(vertexTypeId, 0);
+    }
+
+    public SinglePatternVertex(Integer vertexTypeId, int id) {
+        this(vertexTypeId, id, new ElementDetails());
+    }
+
+    public SinglePatternVertex(Integer typeId, int id, ElementDetails details) {
+        super(details, new VertexIsomorphismChecker(Lists.newArrayList(typeId), details));
+        this.vertexTypeId = typeId;
+        this.id = id;
+    }
+
+    @Override
+    public List<Integer> getVertexTypeIds() {
+        return Arrays.asList(vertexTypeId);
+    }
+
+    @Override
+    public Integer getId() {
+        return id;
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/VertexIsomorphismChecker.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/VertexIsomorphismChecker.java
new file mode 100644
index 000000000000..f995ac92e73b
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/pattern/VertexIsomorphismChecker.java
@@ -0,0 +1,61 @@
+/*
+ * Copyright 2020 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern;
+
+import java.util.Collections;
+import java.util.List;
+import java.util.Objects;
+
+public class VertexIsomorphismChecker implements IsomorphismChecker<VertexIsomorphismChecker> {
+    private final List<Integer> typeIds;
+    private final ElementDetails details;
+
+    public VertexIsomorphismChecker(List<Integer> typeIds, ElementDetails details) {
+        Collections.sort(typeIds, Integer::compareTo);
+        this.typeIds = typeIds;
+        this.details = details;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) return true;
+        if (o == null || getClass() != o.getClass()) return false;
+        VertexIsomorphismChecker that = (VertexIsomorphismChecker) o;
+        return Objects.equals(typeIds, that.typeIds) && Objects.equals(details, that.details);
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(typeIds, details);
+    }
+
+    @Override
+    public int compareTo(VertexIsomorphismChecker o) {
+        if (this.equals(o)) {
+            return 0;
+        }
+        if (this.typeIds.size() != o.typeIds.size()) {
+            return this.typeIds.size() - o.typeIds.size();
+        }
+        for (int i = 0; i < this.typeIds.size(); i++) {
+            if (!this.typeIds.get(i).equals(o.typeIds.get(i))) {
+                return this.typeIds.get(i) - o.typeIds.get(i);
+            }
+        }
+        return this.details.compareTo(o.details);
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/utils/Combinations.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/utils/Combinations.java
new file mode 100644
index 000000000000..1615f2de0dac
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/glogue/utils/Combinations.java
@@ -0,0 +1,48 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.glogue.utils;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class Combinations {
+    public static <T> List<List<T>> getCombinations(List<T> elements, int k) {
+        List<List<T>> results = new ArrayList<>();
+        getCombinationsHelper(elements, k, 0, new ArrayList<>(), results);
+        return results;
+    }
+
+    private static <T> void getCombinationsHelper(
+            List<T> elements,
+            int k,
+            int startIndex,
+            List<T> currentCombination,
+            List<List<T>> results) {
+        if (currentCombination.size() == k) {
+            results.add(new ArrayList<>(currentCombination));
+            return;
+        }
+        if (startIndex >= elements.size()
+                || elements.size() - startIndex < k - currentCombination.size()) {
+            return;
+        }
+        currentCombination.add(elements.get(startIndex));
+        getCombinationsHelper(elements, k, startIndex + 1, currentCombination, results);
+        currentCombination.remove(currentCombination.size() - 1);
+        getCombinationsHelper(elements, k, startIndex + 1, currentCombination, results);
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/schema/EdgeTypeId.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/schema/EdgeTypeId.java
new file mode 100644
index 000000000000..34bb82a5f092
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/schema/EdgeTypeId.java
@@ -0,0 +1,71 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.schema;
+
+import org.javatuples.Triplet;
+
+public class EdgeTypeId {
+    // srcLabelId, dstLabelId, edgeLabelId
+    private final Triplet<Integer, Integer, Integer> edgeType;
+
+    public EdgeTypeId(int srcLabelId, int dstLabelId, int edgeLabelId) {
+        this.edgeType = new Triplet<>(srcLabelId, dstLabelId, edgeLabelId);
+    }
+
+    public Integer getSrcLabelId() {
+        return edgeType.getValue0();
+    }
+
+    public Integer getDstLabelId() {
+        return edgeType.getValue1();
+    }
+
+    public Integer getEdgeLabelId() {
+        return edgeType.getValue2();
+    }
+
+    public Triplet<Integer, Integer, Integer> getEdgeType() {
+        return edgeType;
+    }
+
+    @Override
+    public String toString() {
+        return String.format("[%d-%d->%d]", getSrcLabelId(), getEdgeLabelId(), getDstLabelId());
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (obj instanceof EdgeTypeId) {
+            return this.edgeType.equals(((EdgeTypeId) obj).edgeType);
+        }
+        return false;
+    }
+
+    @Override
+    public int hashCode() {
+        return this.edgeType.hashCode();
+    }
+
+    @Override
+    public EdgeTypeId clone() {
+        return new EdgeTypeId(this.getSrcLabelId(), this.getDstLabelId(), this.getEdgeLabelId());
+    }
+
+    public int compareTo(EdgeTypeId other) {
+        return this.edgeType.compareTo(other.edgeType);
+    }
+}
diff --git a/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/schema/GlogueSchema.java b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/schema/GlogueSchema.java
new file mode 100644
index 000000000000..535e72ae193a
--- /dev/null
+++ b/interactive_engine/compiler/src/main/java/com/alibaba/graphscope/common/ir/rel/metadata/schema/GlogueSchema.java
@@ -0,0 +1,147 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata.schema;
+
+import com.alibaba.graphscope.groot.common.schema.api.EdgeRelation;
+import com.alibaba.graphscope.groot.common.schema.api.GraphEdge;
+import com.alibaba.graphscope.groot.common.schema.api.GraphSchema;
+import com.alibaba.graphscope.groot.common.schema.api.GraphVertex;
+import com.alibaba.graphscope.groot.common.schema.impl.DefaultEdgeRelation;
+import com.alibaba.graphscope.groot.common.schema.impl.DefaultGraphEdge;
+import com.alibaba.graphscope.groot.common.schema.impl.DefaultGraphSchema;
+import com.alibaba.graphscope.groot.common.schema.impl.DefaultGraphVertex;
+import com.google.common.collect.Maps;
+
+import org.jgrapht.*;
+import org.jgrapht.graph.*;
+
+import java.io.BufferedReader;
+import java.io.FileReader;
+import java.io.IOException;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+public class GlogueSchema {
+    private Graph<Integer, EdgeTypeId> schemaGraph;
+    private HashMap<Integer, Double> vertexTypeCardinality;
+    private HashMap<EdgeTypeId, Double> edgeTypeCardinality;
+
+    public GlogueSchema(
+            GraphSchema graphSchema,
+            HashMap<Integer, Double> vertexTypeCardinality,
+            HashMap<EdgeTypeId, Double> edgeTypeCardinality) {
+        this.schemaGraph = new DirectedPseudograph<Integer, EdgeTypeId>(EdgeTypeId.class);
+        for (GraphVertex vertex : graphSchema.getVertexList()) {
+            this.schemaGraph.addVertex(vertex.getLabelId());
+        }
+        for (GraphEdge edge : graphSchema.getEdgeList()) {
+            for (EdgeRelation relation : edge.getRelationList()) {
+                int sourceType = relation.getSource().getLabelId();
+                int targetType = relation.getTarget().getLabelId();
+                EdgeTypeId edgeType = new EdgeTypeId(sourceType, targetType, edge.getLabelId());
+                this.schemaGraph.addEdge(sourceType, targetType, edgeType);
+            }
+        }
+
+        this.vertexTypeCardinality = vertexTypeCardinality;
+        this.edgeTypeCardinality = edgeTypeCardinality;
+    }
+
+    public static GlogueSchema fromFile(String schemaPath) throws IOException {
+        try (BufferedReader bufferedReader = new BufferedReader(new FileReader(schemaPath))) {
+            Map<String, GraphVertex> vertexList = Maps.newHashMap();
+            Map<String, GraphEdge> edgeList = Maps.newHashMap();
+            HashMap<Integer, Double> vertexTypeCardinality = new HashMap<Integer, Double>();
+            HashMap<EdgeTypeId, Double> edgeTypeCardinality = new HashMap<EdgeTypeId, Double>();
+            String line;
+            while ((line = bufferedReader.readLine()) != null) {
+                // seperate by comma
+                String[] parts = line.split(",");
+                // vertex
+                if (parts[0].equals("v")) {
+                    // v, 0, person, 3
+                    // v, 1, software, 4
+                    int labelId = Integer.parseInt(parts[1]);
+                    String label = parts[2];
+                    Double statistics = Double.parseDouble(parts[3]);
+                    DefaultGraphVertex vertex =
+                            new DefaultGraphVertex(labelId, label, List.of(), List.of(), 0, -1);
+                    vertexList.put(label, vertex);
+                    vertexTypeCardinality.put(labelId, statistics);
+                }
+                // edge
+                else if (parts[0].equals("e")) {
+                    // e, 0, knows, person, person, 5
+                    // e, 1, created, person, software, 6
+                    int labelId = Integer.parseInt(parts[1]);
+                    String label = parts[2];
+                    GraphVertex srcGraphVertex = vertexList.get(parts[3]);
+                    GraphVertex dstGraphVertex = vertexList.get(parts[4]);
+                    Double statistics = Double.parseDouble(parts[5]);
+                    int srcLabelId = srcGraphVertex.getLabelId();
+                    int dstLabelId = dstGraphVertex.getLabelId();
+                    DefaultEdgeRelation relation =
+                            new DefaultEdgeRelation(srcGraphVertex, dstGraphVertex);
+                    DefaultGraphEdge edge =
+                            new DefaultGraphEdge(labelId, label, List.of(), List.of(relation), 0);
+                    String edgeLabel = srcLabelId + label + dstLabelId;
+                    edgeList.put(edgeLabel, edge);
+                    edgeTypeCardinality.put(
+                            new EdgeTypeId(srcLabelId, dstLabelId, labelId), statistics);
+                }
+            }
+            DefaultGraphSchema graphSchema =
+                    new DefaultGraphSchema(vertexList, edgeList, Maps.newHashMap());
+            return new GlogueSchema(graphSchema, vertexTypeCardinality, edgeTypeCardinality);
+        }
+    }
+
+    public List<Integer> getVertexTypes() {
+        return List.copyOf(this.schemaGraph.vertexSet());
+    }
+
+    public List<EdgeTypeId> getEdgeTypes() {
+        return List.copyOf(this.schemaGraph.edgeSet());
+    }
+
+    public List<EdgeTypeId> getAdjEdgeTypes(Integer source) {
+        return List.copyOf(this.schemaGraph.edgesOf(source));
+    }
+
+    public List<EdgeTypeId> getEdgeTypes(Integer source, Integer target) {
+        return List.copyOf(this.schemaGraph.getAllEdges(source, target));
+    }
+
+    public Double getVertexTypeCardinality(Integer vertexType) {
+        Double cardinality = this.vertexTypeCardinality.get(vertexType);
+        if (cardinality == null) {
+            return 0.0;
+        } else {
+            return cardinality;
+        }
+    }
+
+    public Double getEdgeTypeCardinality(EdgeTypeId edgeType) {
+        Double cardinality = this.edgeTypeCardinality.get(edgeType);
+        if (cardinality == null) {
+            return 0.0;
+        } else {
+            return cardinality;
+        }
+    }
+}
diff --git a/interactive_engine/compiler/src/main/resources/statistics/ldbc1_statistics.txt b/interactive_engine/compiler/src/main/resources/statistics/ldbc1_statistics.txt
new file mode 100644
index 000000000000..598b185bb1bb
--- /dev/null
+++ b/interactive_engine/compiler/src/main/resources/statistics/ldbc1_statistics.txt
@@ -0,0 +1,31 @@
+v,3,post,1121227
+v,2,comment,1739439
+v,7,tag,16081
+v,0,place,1461
+v,4,forum,100828
+v,6,tagclass,72
+v,1,person,10296
+v,5,orgnisation,7956
+e,15,studyat,person,orgnisation,8310
+e,16,workat,person,orgnisation,22045
+e,17,ispartof,place,place,1455
+e,22,issubclassof,tagclass,tagclass,71
+e,6,hasmember,forum,person,2909769
+e,3,replyof,comment,comment,789021
+e,3,replyof,comment,post,950419
+e,13,likes,person,comment,1109814
+e,13,likes,person,post,760456
+e,10,hasinterest,person,tag,238053
+e,21,hastype,tag,tagclass,16081
+e,12,knows,person,person,173015
+e,0,hascreator,comment,person,1739439
+e,0,hascreator,post,person,1121227
+e,5,containerof,forum,post,1121227
+e,7,hasmoderator,forum,person,100828
+e,11,islocatedin,person,place,10296
+e,11,islocatedin,orgnisation,place,7956
+e,11,islocatedin,comment,place,1739439
+e,11,islocatedin,post,place,1121227
+e,1,hastag,forum,tag,328585
+e,1,hastag,post,tag,751934
+e,1,hastag,comment,tag,2176132
\ No newline at end of file
diff --git a/interactive_engine/compiler/src/main/resources/statistics/modern_statistics.txt b/interactive_engine/compiler/src/main/resources/statistics/modern_statistics.txt
new file mode 100644
index 000000000000..f77f4583de25
--- /dev/null
+++ b/interactive_engine/compiler/src/main/resources/statistics/modern_statistics.txt
@@ -0,0 +1,4 @@
+v,0,person,3
+v,1,software,4
+e,0,knows,person,person,5
+e,1,created,person,software,6
\ No newline at end of file
diff --git a/interactive_engine/compiler/src/main/resources/statistics/movie_statistics.txt b/interactive_engine/compiler/src/main/resources/statistics/movie_statistics.txt
new file mode 100644
index 000000000000..ff2b2a3d2229
--- /dev/null
+++ b/interactive_engine/compiler/src/main/resources/statistics/movie_statistics.txt
@@ -0,0 +1,9 @@
+v,0,movie,38
+v,1,person,130
+v,2,user,7
+e,0,acted_in,person,movie,172
+e,1,directed,person,movie,44
+e,2,review,user,movie,16
+e,3,follows,user,person,8
+e,4,wrote,person,movie,10
+e,5,produced,person,movie,15
\ No newline at end of file


Test patch:
diff --git a/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/rel/metadata/GLogueCardinalityTest.java b/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/rel/metadata/GLogueCardinalityTest.java
new file mode 100644
index 000000000000..7b1335b535f4
--- /dev/null
+++ b/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/rel/metadata/GLogueCardinalityTest.java
@@ -0,0 +1,100 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.alibaba.graphscope.common.ir.rel.metadata;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.Glogue;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.GlogueBasicCardinalityEstimationImpl;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.Pattern;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.PatternVertex;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.SinglePatternVertex;
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.EdgeTypeId;
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.GlogueSchema;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+public class GLogueCardinalityTest {
+    static GlogueSchema g = GLogueSchemaTest.mockGlogueSchema();
+    static Glogue gl = new Glogue(g, 3);
+    static Integer person = 0;
+    static Integer software = 1;
+    // person -> software
+    static EdgeTypeId creates = new EdgeTypeId(0, 1, 1);
+    // person -> person
+    static EdgeTypeId knows = new EdgeTypeId(0, 0, 0);
+    static Double delta = 0.00001;
+
+    @Test
+    public void basic_pattern_cardinality_estimation_test() {
+        GlogueBasicCardinalityEstimationImpl basicCardinalityEstimation =
+                new GlogueBasicCardinalityEstimationImpl(gl, g);
+        PatternVertex v0 = new SinglePatternVertex(person, 0);
+        PatternVertex v1 = new SinglePatternVertex(software, 1);
+        PatternVertex v2 = new SinglePatternVertex(person, 2);
+
+        // low order statistics
+        Pattern p0 = new Pattern(v0);
+        Pattern p1 = new Pattern(v1);
+        Pattern p2 = new Pattern();
+        p2.addVertex(v0);
+        p2.addVertex(v1);
+        p2.addEdge(v0, v1, creates);
+        Pattern p3 = new Pattern();
+        p3.addVertex(v0);
+        p3.addVertex(v2);
+        p3.addEdge(v0, v2, knows);
+        Assert.assertEquals(
+                4.0, basicCardinalityEstimation.getCardinality(p0).doubleValue(), delta);
+        Assert.assertEquals(
+                2.0, basicCardinalityEstimation.getCardinality(p1).doubleValue(), delta);
+        Assert.assertEquals(
+                4.0, basicCardinalityEstimation.getCardinality(p2).doubleValue(), delta);
+        Assert.assertEquals(
+                2.0, basicCardinalityEstimation.getCardinality(p3).doubleValue(), delta);
+
+        // high order statistics
+        // sofware<-person0->person2
+        Pattern p4 = new Pattern(p2);
+        p4.addVertex(v2);
+        p4.addEdge(v0, v2, knows);
+        p4.reordering();
+        Assert.assertEquals(
+                2.0, basicCardinalityEstimation.getCardinality(p4).doubleValue(), delta);
+
+        // sofware<-person0->person2 + person2->software
+        Pattern p5 = new Pattern(p4);
+        p5.addEdge(v2, v1, creates);
+        p5.reordering();
+        Assert.assertEquals(
+                1.0, basicCardinalityEstimation.getCardinality(p5).doubleValue(), delta);
+
+        // person1<-person0->person2
+        Pattern p6 = new Pattern(p3);
+        PatternVertex v3 = new SinglePatternVertex(person, 3);
+        p6.addVertex(v3);
+        p6.addEdge(v0, v3, knows);
+        p6.reordering();
+        Assert.assertEquals(
+                1.0, basicCardinalityEstimation.getCardinality(p6).doubleValue(), delta);
+
+        //  person1<-person0->person2 + person1->person2
+        Pattern p7 = new Pattern(p6);
+        p7.addEdge(v2, v3, knows);
+        p7.reordering();
+        Assert.assertEquals(
+                0.125, basicCardinalityEstimation.getCardinality(p7).doubleValue(), delta);
+    }
+}
diff --git a/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/rel/metadata/GLogueSchemaTest.java b/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/rel/metadata/GLogueSchemaTest.java
new file mode 100644
index 000000000000..86b27ee9459c
--- /dev/null
+++ b/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/rel/metadata/GLogueSchemaTest.java
@@ -0,0 +1,81 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata;
+
+import com.alibaba.graphscope.common.ir.Utils;
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.EdgeTypeId;
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.GlogueSchema;
+import com.alibaba.graphscope.groot.common.schema.api.GraphSchema;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.HashMap;
+
+public class GLogueSchemaTest {
+    @Test
+    public void glogue_schema_test() {
+        GlogueSchema g = mockGlogueSchema();
+        Double delta = 0.00001;
+
+        Integer person = 0;
+        Integer software = 1;
+        EdgeTypeId knows = new EdgeTypeId(0, 0, 0);
+        EdgeTypeId creates = new EdgeTypeId(0, 1, 1);
+
+        Assert.assertEquals(2, g.getVertexTypes().size());
+        Assert.assertEquals(2, g.getEdgeTypes().size());
+
+        // test get type cardinality
+        Assert.assertEquals(4.0, g.getVertexTypeCardinality(person), delta);
+        Assert.assertEquals(2.0, g.getVertexTypeCardinality(software), delta);
+        Assert.assertEquals(0.0, g.getVertexTypeCardinality(2), delta);
+        Assert.assertEquals(2.0, g.getEdgeTypeCardinality(knows), delta);
+        Assert.assertEquals(4.0, g.getEdgeTypeCardinality(creates), delta);
+        Assert.assertEquals(0.0, g.getEdgeTypeCardinality(new EdgeTypeId(0, 0, 2)), delta);
+
+        // test get types
+        Assert.assertEquals(2, g.getAdjEdgeTypes(person).size());
+        Assert.assertEquals(1, g.getAdjEdgeTypes(software).size());
+        Assert.assertEquals(1, g.getEdgeTypes(person, person).size());
+        Assert.assertEquals(1, g.getEdgeTypes(person, software).size());
+        Assert.assertEquals(0, g.getEdgeTypes(software, person).size());
+    }
+
+    static GlogueSchema mockGlogueSchema() {
+        // modern graph schema
+        // person: label 0, statistics 4;
+        // software: label 1, statistics 2;
+        // person-knows->person: label 0, statistics 2;
+        // person-created->software: label 1, statistics 4;
+        GraphSchema graphSchema = Utils.schemaMeta.getSchema();
+        graphSchema.getElement("person").getLabelId();
+        Integer person = graphSchema.getElement("person").getLabelId();
+        Integer software = graphSchema.getElement("software").getLabelId();
+        EdgeTypeId knows = new EdgeTypeId(0, 0, graphSchema.getElement("knows").getLabelId());
+        EdgeTypeId creates = new EdgeTypeId(0, 1, graphSchema.getElement("created").getLabelId());
+        HashMap<Integer, Double> vertexTypeCardinality = new HashMap<Integer, Double>();
+        vertexTypeCardinality.put(person, 4.0);
+        vertexTypeCardinality.put(software, 2.0);
+        HashMap<EdgeTypeId, Double> edgeTypeCardinality = new HashMap<EdgeTypeId, Double>();
+        edgeTypeCardinality.put(knows, 2.0);
+        edgeTypeCardinality.put(creates, 4.0);
+
+        GlogueSchema g = new GlogueSchema(graphSchema, vertexTypeCardinality, edgeTypeCardinality);
+        return g;
+    }
+}
diff --git a/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/rel/metadata/GlogueTest.java b/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/rel/metadata/GlogueTest.java
new file mode 100644
index 000000000000..9a589b354152
--- /dev/null
+++ b/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/rel/metadata/GlogueTest.java
@@ -0,0 +1,235 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.ExtendEdge;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.ExtendStep;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.Glogue;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.GlogueEdge;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.GlogueExtendIntersectEdge;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.Pattern;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.PatternVertex;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.SinglePatternVertex;
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.EdgeTypeId;
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.GlogueSchema;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.Set;
+
+public class GlogueTest {
+
+    static GlogueSchema g = GLogueSchemaTest.mockGlogueSchema();
+    static Glogue gl = new Glogue(g, 3);
+    static Double delta = 0.00001;
+    static Integer person = 0;
+    static Integer software = 1;
+    static EdgeTypeId knows = new EdgeTypeId(0, 0, 0);
+    static EdgeTypeId creates = new EdgeTypeId(0, 1, 1);
+
+    @Test
+    public void glogue_get_row_count_test() {
+
+        // p1 -> s0 <- p2 + p1 -> p2
+        // v0: software, v1: person1, v2: person2
+        PatternVertex v0 = new SinglePatternVertex(software, 0);
+        PatternVertex v1 = new SinglePatternVertex(person, 1);
+        PatternVertex v2 = new SinglePatternVertex(person, 2);
+
+        // pattern1: person2 <- person1 -> software
+        Pattern pattern1 = new Pattern();
+        pattern1.addVertex(v0);
+        pattern1.addVertex(v1);
+        pattern1.addVertex(v2);
+        pattern1.addEdge(v1, v0, creates);
+        pattern1.addEdge(v1, v2, knows);
+        pattern1.reordering();
+
+        Double count1 = gl.getRowCount(pattern1);
+        Assert.assertEquals(2.0d, count1, delta);
+
+        // pattern2: person2 <- person1 -> software + person2 -> software
+        Pattern pattern2 = new Pattern();
+        pattern2.addVertex(v0);
+        pattern2.addVertex(v1);
+        pattern2.addVertex(v2);
+        pattern2.addEdge(v1, v0, creates);
+        pattern2.addEdge(v1, v2, knows);
+        pattern2.addEdge(v2, v0, creates);
+        pattern2.reordering();
+
+        Double count2 = gl.getRowCount(pattern2);
+        Assert.assertEquals(1.0d, count2, delta);
+
+        // pattern3: person2 <- person1 <- software (not exist)
+        Pattern pattern3 = new Pattern();
+        pattern3.addVertex(v0);
+        pattern3.addVertex(v1);
+        pattern3.addVertex(v2);
+        pattern3.addEdge(v0, v1, creates);
+        pattern3.addEdge(v1, v2, knows);
+        pattern3.reordering();
+
+        Double count3 = gl.getRowCount(pattern3);
+        Assert.assertEquals(0.0d, count3, delta);
+    }
+
+    @Test
+    public void glogue_get_neighbors_test() {
+        // v0: software, v1: person1, v2: person2
+        PatternVertex v0 = new SinglePatternVertex(software, 0);
+        PatternVertex v1 = new SinglePatternVertex(person, 1);
+        PatternVertex v2 = new SinglePatternVertex(person, 2);
+
+        // pattern1: person2 <- person1 -> software
+        Pattern pattern1 = new Pattern();
+        pattern1.addVertex(v0);
+        pattern1.addVertex(v1);
+        pattern1.addVertex(v2);
+        pattern1.addEdge(v1, v0, creates);
+        pattern1.addEdge(v1, v2, knows);
+        pattern1.reordering();
+
+        Set<GlogueEdge> outEdges = gl.getOutEdges(pattern1);
+        Set<GlogueEdge> inEdges = gl.getInEdges(pattern1);
+        Assert.assertEquals(0, outEdges.size());
+        Assert.assertEquals(2, inEdges.size());
+
+        // pattern2: person2 <- person1 -> software + person2 -> software
+        Pattern pattern2 = new Pattern();
+        pattern2.addVertex(v0);
+        pattern2.addVertex(v1);
+        pattern2.addVertex(v2);
+        pattern2.addEdge(v1, v0, creates);
+        pattern2.addEdge(v1, v2, knows);
+        pattern2.addEdge(v2, v0, creates);
+        pattern2.reordering();
+
+        outEdges = gl.getOutEdges(pattern2);
+        inEdges = gl.getInEdges(pattern2);
+        Assert.assertEquals(0, outEdges.size());
+        Assert.assertEquals(2, inEdges.size());
+
+        // pattern3: person1 -> person2
+        Pattern pattern3 = new Pattern();
+        pattern3.addVertex(v1);
+        pattern3.addVertex(v2);
+        pattern3.addEdge(v1, v2, knows);
+        pattern3.reordering();
+
+        outEdges = gl.getOutEdges(pattern3);
+        inEdges = gl.getInEdges(pattern3);
+        Assert.assertEquals(14, outEdges.size());
+        Assert.assertEquals(1, inEdges.size());
+
+        // pattern4: person1 -> software
+        Pattern pattern4 = new Pattern();
+        pattern4.addVertex(v0);
+        pattern4.addVertex(v1);
+        pattern4.addEdge(v1, v0, creates);
+        pattern4.reordering();
+
+        outEdges = gl.getOutEdges(pattern4);
+        inEdges = gl.getInEdges(pattern4);
+        Assert.assertEquals(7, outEdges.size());
+        Assert.assertEquals(2, inEdges.size());
+    }
+
+    @Test
+    public void glogue_edge_weight_test() {
+        // v0: software, v1: person1, v2: person2
+        PatternVertex v0 = new SinglePatternVertex(software, 0);
+        PatternVertex v1 = new SinglePatternVertex(person, 1);
+        PatternVertex v2 = new SinglePatternVertex(person, 2);
+
+        // pattern1: person2 <- person1 -> software
+        Pattern pattern1 = new Pattern();
+        pattern1.addVertex(v0);
+        pattern1.addVertex(v1);
+        pattern1.addVertex(v2);
+        pattern1.addEdge(v1, v0, creates);
+        pattern1.addEdge(v1, v2, knows);
+        pattern1.reordering();
+
+        Set<GlogueEdge> outEdges = gl.getOutEdges(pattern1);
+        Set<GlogueEdge> inEdges = gl.getInEdges(pattern1);
+        Assert.assertEquals(0, outEdges.size());
+        Assert.assertEquals(2, inEdges.size());
+
+        for (GlogueEdge edge : inEdges) {
+
+            GlogueExtendIntersectEdge e = (GlogueExtendIntersectEdge) edge;
+            Assert.assertEquals(2, e.getSrcPattern().getVertexSet().size());
+            ExtendStep step = e.getExtendStep();
+            if (step.getTargetVertexType() == software) {
+                // person2<-person1 + extend: person1->software
+                Assert.assertEquals(1, step.getExtendEdges().size());
+                Assert.assertEquals(1.0, step.getWeight().doubleValue(), delta);
+            } else if (step.getTargetVertexType() == person) {
+                // person1->software + extend: person1->person2
+                Assert.assertEquals(1, step.getExtendEdges().size());
+                Assert.assertEquals(0.5, step.getWeight().doubleValue(), delta);
+            }
+        }
+
+        // pattern1: person2 <- person1 -> software + person2->software
+        Pattern pattern2 = new Pattern(pattern1);
+        pattern2.addEdge(v2, v0, creates);
+        pattern2.reordering();
+
+        Set<GlogueEdge> outEdges2 = gl.getOutEdges(pattern2);
+        Set<GlogueEdge> inEdges2 = gl.getInEdges(pattern2);
+        Assert.assertEquals(0, outEdges2.size());
+        Assert.assertEquals(2, inEdges2.size());
+
+        for (GlogueEdge edge : inEdges2) {
+            GlogueExtendIntersectEdge e = (GlogueExtendIntersectEdge) edge;
+            Assert.assertEquals(2, e.getSrcPattern().getVertexSet().size());
+            ExtendStep step = e.getExtendStep();
+            // srcPattern: person1<-person2, extend: person1->software, person2->software
+            if (step.getTargetVertexType() == software) {
+
+                Assert.assertEquals(2, step.getExtendEdges().size());
+                // edge weight: |person->software| / |person| = 4 / 4 = 1.0
+                Assert.assertEquals(
+                        1.0, step.getExtendEdges().get(0).getWeight().doubleValue(), delta);
+                // step weight: sum(|intermediate results|)/|srcPattern|,
+                // i.e., |person1<-person2->software| + |triangle| / |person1->person2| =  (2+1)/2 =
+                // 1.5
+                Assert.assertEquals(1.5, step.getWeight().doubleValue(), delta);
+            }
+            // srcPattern: person1->software, extend: person1->person2, software<-person2
+            else if (step.getTargetVertexType() == person) {
+                Assert.assertEquals(2, step.getExtendEdges().size());
+                for (ExtendEdge e1 : step.getExtendEdges()) {
+                    if (e1.getEdgeTypeId() == knows) {
+                        // edge weight: |person->person| / |person| = 2 / 4 = 0.5
+                        Assert.assertEquals(0.5, e1.getWeight().doubleValue(), delta);
+                    } else if (e1.getEdgeTypeId() == creates) {
+                        // edge weight: |person->software| / |software| = 4 / 2 = 2.0
+                        Assert.assertEquals(2.0, e1.getWeight().doubleValue(), delta);
+                    }
+                }
+                // step weight: sum(|intermediate results|)/|srcPattern|,
+                // i.e., |person1<-person2->software| + |triangle| / |person1->software| =  (2+1)/4
+                // = 0.75
+                Assert.assertEquals(0.75, step.getWeight().doubleValue(), delta);
+            }
+        }
+    }
+}
diff --git a/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/rel/metadata/PatternTest.java b/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/rel/metadata/PatternTest.java
new file mode 100644
index 000000000000..2754d03ed704
--- /dev/null
+++ b/interactive_engine/compiler/src/test/java/com/alibaba/graphscope/common/ir/rel/metadata/PatternTest.java
@@ -0,0 +1,235 @@
+/*
+ * Copyright 2024 Alibaba Group Holding Limited.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.alibaba.graphscope.common.ir.rel.metadata;
+
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.ExtendEdge;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.ExtendStep;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.Pattern;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.PatternDirection;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.PatternVertex;
+import com.alibaba.graphscope.common.ir.rel.metadata.glogue.pattern.SinglePatternVertex;
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.EdgeTypeId;
+import com.alibaba.graphscope.common.ir.rel.metadata.schema.GlogueSchema;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+public class PatternTest {
+    static GlogueSchema g = GLogueSchemaTest.mockGlogueSchema();
+    static Integer person = 0;
+    static Integer software = 1;
+    // person -> software
+    static EdgeTypeId creates = new EdgeTypeId(0, 1, 1);
+    // person -> person
+    static EdgeTypeId knows = new EdgeTypeId(0, 0, 0);
+
+    @Test
+    public void basic_pattern_order_test() {
+        PatternVertex v0 = new SinglePatternVertex(person, 0);
+        PatternVertex v1 = new SinglePatternVertex(software, 1);
+        PatternVertex v2 = new SinglePatternVertex(person, 2);
+
+        // test group:
+
+        // p1: person -> person, the two persons are not in the same group
+        Pattern p1 = new Pattern();
+        p1.addVertex(v0);
+        p1.addVertex(v2);
+        p1.addEdge(v0, v2, knows);
+        p1.reordering();
+        Assert.assertNotEquals(p1.getVertexGroup(v0), p1.getVertexGroup(v2));
+
+        // p2: person <-> person, the two persons are in the same group
+        Pattern p2 = new Pattern(p1);
+        p2.addEdge(v2, v0, knows);
+        p2.reordering();
+        Assert.assertEquals(p2.getVertexGroup(v0), p2.getVertexGroup(v2));
+
+        // p3: person -> software <- person, the two persons are in the same group
+        Pattern p3 = new Pattern();
+        p3.addVertex(v0);
+        p3.addVertex(v1);
+        p3.addVertex(v2);
+        p3.addEdge(v0, v1, creates);
+        p3.addEdge(v2, v1, creates);
+        p3.reordering();
+        Assert.assertEquals(p3.getVertexGroup(v0), p3.getVertexGroup(v2));
+        Assert.assertNotEquals(p3.getVertexGroup(v0), p3.getVertexGroup(v1));
+
+        // test order:
+
+        // p4: person0->person1->person2, p5: person0->person2->person1, p6:
+        // person1->person0->person2
+        // the three patterns are isomorphic, and the order of the corresponding
+        // vertices must be the same
+        PatternVertex v00 = new SinglePatternVertex(person, 0);
+        PatternVertex v11 = new SinglePatternVertex(person, 1);
+        PatternVertex v22 = new SinglePatternVertex(person, 2);
+        Pattern p4 = new Pattern();
+        p4.addVertex(v00);
+        p4.addVertex(v11);
+        p4.addVertex(v22);
+        p4.addEdge(v00, v11, knows);
+        p4.addEdge(v11, v22, knows);
+        p4.reordering();
+        Pattern p5 = new Pattern();
+        p5.addVertex(v00);
+        p5.addVertex(v11);
+        p5.addVertex(v22);
+        p5.addEdge(v00, v22, knows);
+        p5.addEdge(v22, v11, knows);
+        p5.reordering();
+        Pattern p6 = new Pattern();
+        p6.addVertex(v00);
+        p6.addVertex(v11);
+        p6.addVertex(v22);
+        p6.addEdge(v11, v00, knows);
+        p6.addEdge(v00, v22, knows);
+        p6.reordering();
+        Assert.assertEquals(p4.getVertexOrder(v00), p5.getVertexOrder(v00));
+        Assert.assertEquals(p4.getVertexOrder(v11), p5.getVertexOrder(v22));
+        Assert.assertEquals(p4.getVertexOrder(v22), p5.getVertexOrder(v11));
+        Assert.assertEquals(p4.getVertexOrder(v00), p6.getVertexOrder(v11));
+        Assert.assertEquals(p4.getVertexOrder(v11), p6.getVertexOrder(v00));
+        Assert.assertEquals(p4.getVertexOrder(v22), p6.getVertexOrder(v22));
+    }
+
+    @Test
+    public void basic_pattern_extend_test() {
+        // person
+        PatternVertex v0 = new SinglePatternVertex(person, 0);
+        Pattern p0 = new Pattern(v0);
+        p0.reordering();
+        Assert.assertEquals(1, p0.getVertexNumber().intValue());
+        Assert.assertEquals(0, p0.getEdgeNumber().intValue());
+
+        // test getExtendSteps:
+        // expected: person -> software, person -> person, person <- person, person <-> person
+        List<ExtendStep> steps0 = p0.getExtendSteps(g);
+        List<ExtendEdge> edge1 = List.of(new ExtendEdge(0, creates, PatternDirection.OUT));
+        List<ExtendEdge> edge2 = List.of(new ExtendEdge(0, knows, PatternDirection.OUT));
+        List<ExtendEdge> edge3 = List.of(new ExtendEdge(0, knows, PatternDirection.IN));
+        List<ExtendEdge> edge4 =
+                List.of(
+                        new ExtendEdge(0, knows, PatternDirection.OUT),
+                        new ExtendEdge(0, knows, PatternDirection.IN));
+
+        // person -> software
+        ExtendStep step1 = new ExtendStep(software, edge1);
+        // person -> person(new)
+        ExtendStep step2 = new ExtendStep(person, edge2);
+        // person <- person(new)
+        ExtendStep step3 = new ExtendStep(person, edge3);
+        // person <-> person(new)
+        ExtendStep step4 = new ExtendStep(person, edge4);
+        List<ExtendStep> expectedExtendSteps =
+                new ArrayList<>(Arrays.asList(step1, step2, step3, step4));
+        expectedExtendSteps.sort((o1, o2) -> o1.toString().compareTo(o2.toString()));
+        steps0.sort((o1, o2) -> o1.toString().compareTo(o2.toString()));
+        Assert.assertEquals(expectedExtendSteps.toString(), steps0.toString());
+
+        // test extend:
+        Pattern p1 = p0.extend(step1);
+        Assert.assertEquals(2, p1.getVertexNumber().intValue());
+        Assert.assertEquals(1, p1.getEdgeNumber().intValue());
+        Assert.assertEquals(software, p1.getVertexById(1).getVertexTypeIds().get(0));
+        Pattern p2 = p0.extend(step2);
+        Assert.assertEquals(2, p2.getVertexNumber().intValue());
+        Assert.assertEquals(1, p2.getEdgeNumber().intValue());
+        Assert.assertEquals(person, p2.getVertexById(1).getVertexTypeIds().get(0));
+        Pattern p3 = p0.extend(step3);
+        Assert.assertEquals(2, p3.getVertexNumber().intValue());
+        Assert.assertEquals(1, p3.getEdgeNumber().intValue());
+        Assert.assertEquals(person, p3.getVertexById(1).getVertexTypeIds().get(0));
+        Assert.assertTrue(p2.isIsomorphicTo(p3));
+        Pattern p4 = p0.extend(step4);
+        Assert.assertEquals(2, p4.getVertexNumber().intValue());
+        Assert.assertEquals(2, p4.getEdgeNumber().intValue());
+        Assert.assertEquals(person, p4.getVertexById(1).getVertexTypeIds().get(0));
+        Assert.assertFalse(p2.isIsomorphicTo(p4));
+    }
+
+    @Test
+    public void basic_pattern_isomorphism_test() {
+        // v0: software
+        // v1: person
+        // v2: person
+        PatternVertex v0 = new SinglePatternVertex(software, 0);
+        PatternVertex v1 = new SinglePatternVertex(person, 1);
+        PatternVertex v2 = new SinglePatternVertex(person, 2);
+
+        // p1 -> s0 <- p2
+        Pattern p0 = new Pattern();
+        p0.addVertex(v0);
+        p0.addVertex(v1);
+        p0.addVertex(v2);
+        p0.addEdge(v1, v0, creates);
+        p0.addEdge(v2, v0, creates);
+
+        // p0 -> s1 <- p2
+        Pattern p1 = new Pattern();
+        PatternVertex v00 = new SinglePatternVertex(person, 0);
+        PatternVertex v11 = new SinglePatternVertex(software, 1);
+        p1.addVertex(v00);
+        p1.addVertex(v11);
+        p1.addVertex(v2);
+        p1.addEdge(v00, v11, creates);
+        p1.addEdge(v2, v11, creates);
+        // p1 -> s0 <- p2 v.s. p0 -> s1 <- p2
+        Assert.assertTrue(p0.equals(p1));
+
+        // p1 -> s0 -> p2
+        Pattern p2 = new Pattern();
+        p2.addVertex(v0);
+        p2.addVertex(v1);
+        p2.addVertex(v2);
+        p2.addEdge(v1, v0, creates);
+        p2.addEdge(v0, v2, creates);
+        // p1 -> s0 <- p2 v.s. p1 -> s0 -> p2
+        Assert.assertFalse(p0.equals(p2));
+
+        // p1 -> s0 <- p2 + p1 -> p2
+        Pattern p3 = new Pattern(p0);
+        p3.addEdge(v1, v2, knows);
+        // p1 -> s0 <- p2 + p1 <- p2
+        Pattern p4 = new Pattern(p0);
+        p4.addEdge(v2, v1, knows);
+        Assert.assertTrue(p3.equals(p4));
+
+        // p2 <- p1 -> s0
+        Pattern p5 = new Pattern();
+        p5.addVertex(v0);
+        p5.addVertex(v1);
+        PatternVertex v222 = new SinglePatternVertex(person, 2);
+        p5.addVertex(v222);
+        p5.addEdge(v1, v0, creates);
+        p5.addEdge(v1, v222, knows);
+        // p1 -> s0 <-p2
+        Pattern p6 = new Pattern();
+        p6.addVertex(v0);
+        p6.addVertex(v1);
+        PatternVertex v2222 = new SinglePatternVertex(software, 2);
+        p6.addVertex(v2222);
+        p6.addEdge(v1, v0, creates);
+        p6.addEdge(v1, v2222, creates);
+        Assert.assertFalse(p5.equals(p6));
+    }
+}