Links between knowledge bases build the backbone of the Linked Data Web. In previous works, the combination of the results of time-efficient algorithms through set-theoretical operators has been shown to be very time-efficient for Link Discovery. However, the further optimization of such link specifications has not been paid much attention to. We address the issue of further optimizing the runtime of link specifications by presenting Helios, a runtime optimizer for Link Discovery. Helios comprises both a rewriter and an execution planner for link specifications. The rewriter is a sequence of fixed-point iterators for algebraic rules. The planner relies on time-efficient evaluation functions to generate execution plans for link specifications. We evaluate Helios on 17 specifications created by human experts and 2180 specifications generated automatically. Our evaluation shows that Helios is up to 300 times faster than a canonical planner. Moreover, Helios’ improvements are statistically significant.