Accurate, efficiently computable cost functions are important for cost-based query optimizers. We investigate how to automatically find the best approximate cost functions minimizing the q-error for a hash join on measurements from extensive experiments. We systematically analyze which factors influence the approximation error, which input parameters are beneficial, and how this relates to plan quality in the big picture. From this, we derive suggestions for improvements for the query evaluation engine (QEE) that benefit both the hash join’s runtime and the approximation error.