Examples for graph database query classification include receiving a graph query and determining if the graph query matches benchmark data. In the event that the graph query does not match benchmark data, the query may be parsed, a canonical internal representation of the query may be determined, the representation may be mapped to a rule, and the query may be classified based on the rule. In the event that the confidence score for the query classification does not exceed a threshold, the query may be sent to a synthetic graph or synopsis for simulation. In some examples, the simulation may include selecting computationally expensive graph operators in the query for simulation.