Relational databases are awesome if you are not dealing with huge amounts of data that your current hardware can't handle the relational way. There are some cases where you have a ridiculous amount of data(rows) and you simply can't store that in a relational database and you are happy to live without the benefits of relational databases.
If you have millions of rows, you are probably better off with something like MongoDB, if you need to search that, you should probably use something like Sphinx or Lucene anyway. But if you know that you won't have too much data for the forceable future, you should use relational databases. OR you could simply use both.
A relational database at very modest hardware can handle millions of rows, and with a solid database, good hardware and a DBA who knows his shit you can handle billions.
OpenStreetMap has over a billion nodes stored in a PostgreSQL database.
Billions of rows btw is not a problem even on modest hardware, with a half-decent db, etc. It's analytics on this where it become possibly an issue. Retrieving one row out of 1 billion is not that much more complex than retrieving one row out of 1 million, nor is it that much more expensive computationally assuming the right index is in place.
The problem comes with high concurrency, in particular very high write concurrency, or with very complex queries which require a lot of RAM to do properly. But that's where you need a solid db, good hardware, and a solid DBA.
I always get a kick out of Stonebraker selling NewSQL/VoltDB as the solution to this sort of problem. He provides a triangle where at the vertices are VoltDB, column stores, and NoSQL.
However, what he always fails to mention is that some of the most important OLTP that happens is in enterprise ERP systems, and these involve every kind of workload of all of these. Yes, you could probably get some additional performance gains by splitting up your ERP into VoltDB, Vertica, and CouchDB with connectors between them but why?
And relational data doesn't even start to get moderately big until you are in the TB range. This is true even of ERP apps.
Millions of rows are a problem? What are you using? Microsoft Access?
There may be cases where non-relational databases are the right solution, but unless you are using a toy RDBMS millions of rows is not considered a lot of data. Millions of rows added every day... now you're talking. Oracle handles that kind of thing just fine.
If you have millions of rows, you are probably better off with something like MongoDB, if you need to search that, you should probably use something like Sphinx or Lucene anyway. But if you know that you won't have too much data for the forceable future, you should use relational databases. OR you could simply use both.