A method of processing a query to a graph database using processors. The method comprises providing threads to be executed on processors, each the thread is associated with one of a plurality of unique thread identifiers, providing a graph database having a plurality of graph database nodes and a plurality of graph database edges, each the graph database edge represents a relationship between two of the plurality of graph database nodes, receiving a query tree that defines a tree comprising plurality of query nodes connected by a plurality of query tree edges, and searching at least part of the graph database for a match with the query tree, wherein the searching is executed by the processors, and wherein each processor searches one of a plurality of sub-graphs of the graph database, each the sub-graph is defined by one of the plurality of thread identifiers.