I don’t know the other plugin.
I don’t consider the Related plugin as having many database connections. Standard WordPress caching can take some of the effort away.
You can easily test it with the following code in your footer.php:
<p><?php echo get_num_queries(); ?> db queries in <?php timer_stop(1); ?> seconds.</p>
That will list the database queries. In my testing, having a post with and a post without related posts in the content filter makes no difference in database queries. I think the standard WordPress caching does all the hard work here. In your setup, it might differ, so you should test yourself.
The plugin uses the get_post function. I once tried to refactor it using WP_Query directly, but it even resulted in more db queries. So it seems pretty good as it is.
If you have suggestions code-wise to improve db-handling, I’m willing to listen :).
