I have to agree with you guys, that block can couse mysql overload on popular websites, but fortunately there is a simple workaround:
you can change the $cRelatedDays variable (which is equal to 7 by default) to 1. Smaller number means less records in the "related" table, i.e. faster mysql responce.
If that will not increase your site's speed drastically, you can make the time interval even shorter by experimenting with this line:
// Remove obsolete records
$delta = ...
And again, the smaler delta is, the faster your query is.