>> I've found count(*) on any backend is just a slow operation

Interesting point. Regarding SQL Server, SELECT COUNT(*) FROM table will generate just has much work (defined as logical page I/O) as doing a SELECT * FROM table IF you do not have a non-clustered index on the table. SQL Server must read every page and count the number of rows on the page.

If the table does have a non-clustered index, SQL Server can scan the leaf-level pages of the index and count the number of keys on each page. This will give much better performance especially if one of the non-clustered indexes uses a very small key.

-Mike