Question: I'm trying neo4j with 20 million nodes. When I call a simple match statement like "MATCH (n:MYLABEL {Id:5}) RETURN n", it takes about 2 minutes from the web interface and also from the console. Is there something wrong about taking that much time?

Answer: 
Have you tried to create an index on this label and property?
The problem was caused by the configuration of my windows machine. I tried it with a mac and the performance becomes very good. I can match an indexed attribute within 0.1 second in a database of 10 millions nodes. Thank you all for suggestions.