Since plain permalinks cause performance issues, would it be possible change the way they are store and fetched from the database to improve performance?
For performance reasons, it is not a good idea to start your permalink structure with the category, tag, author, or postname fields. The reason is that these are text fields, and using them at the beginning of your permalink structure it takes more time for WordPress to distinguish your Post URLs from Page URLs (which always use the text "page slug" as the URL), and to compensate, WordPress stores a lot of extra information in its database (so much that sites with lots of Pages have experienced difficulties). So, it is best to have at least two path segments in your post's permalink structure such as /%year%/%postname%/ or even /posts/%postname%/. (Some people recommend /%post_id%/%postname%/ which works for performance reasons but others recommend against it because it is unfriendly to users in the many contexts in which users interact with URLs.) See Otto's technical writeup on the topic as well as this wp-testers discussion.