Techniques are described herein for asynchronous execution of queries on statically replicated graph data. In an embodiment, a graph is partitioned among a plurality of computers executing the graph querying engine. One or more high-degree vertices of the graph are each replicated in each graph partition. The partitions, including the replicated high-degree vertices, are loaded in memory of the plurality of computers. To execute a query, a query plan is generated based on the query. The query plan specifies a plurality of operators and an order for the plurality of operators. The order is such that if an operator requires data generated by another operator, then the other operator is ordered before the operator in the query plan. Replicated copies of a vertex is visited if matches made by subsequent operator(s) are limited by data unique to the replicated vertices.