In this research we study what is the theoretical complexity of Neo4J, OrientDB and GraphDB, (three known Graph Databases that can be accessed by a Java instance), and how this complexity is manifested in a real life performance, To study their practical performance, a software was implemented and named as a profiler, which is capable to profile, (to record the time that is needed), each operation, and display the results in an accurate and organized manner. The technical documentation of those 3 databases was reviewed as well, to identify how the databases work, and what are their strong and weak points. By the profiling process, the best performance was displayed by Neo4J, and while OrientDB failed to deliver, GraphDB takes the second place in terms of performance. We can identify a potential in OrientDB’s approach, but its structure is too complex and rigid. Neo4J has a robust structure and an architecture that gives to it a great performance, while the Cypher syntax, which Neo4J uses, minimizes the possibility of human error. GraphDB is optimized for large scale public-data operations but performs well as a stand-alone solution as well.