[hobofan]

Usually there are indices on the properties of specific labels (e.g. for the .population of :Country), in graph databases with labeled nodes (most of them), so in general pretty much the same as in a relational database.