In the original version of RapidStart Services, that was shipped with NAV 2013 R2, Microsoft was using the Table Information table to collect no. of records for each table. This was very slow as soon as you added more companies to the database. A coworker showed me this problem and I changed the functionality and sent a suggestion to Microsoft on how to change this.
And what do you know, they did exactly that. In the Update Rollup 3 for Microsoft Dynamics NAV 2013 R2 this has been fixed.
I also sent them an error regarding a local formatted date formula. And they fixed that to.
Good job Microsoft.