One way to conceptually tackle this count(*) issue would be to create a new index type for it. The index type would (logically) just need to implement insert and delete operations and keep a running count with a big lock around it. Users could then choose to trade off concurrent performance against the speed of count() by creating or dropping that index. Implementing that type of index might not even be that hard but convincing the planer and executor to use it without too many hardcoded cases seems more challenging.
