I'm not sure either but I think it's the procedural mindset. People learning about relational databases hear about how a join is equivalent to cartesian product, then imagine the nested-loops implementation and think that k-way join query fundamentally has performance O(n^k).

They haven't wrapped their brain around the declarative mindset that a join doesn't mean looping any more than multiplication implies a loop of additions.

I think it would help if relational databases acted less like black boxes and exposed worst-case performance guarantees for particular queries. AFAIK no DBMS actually promises that an equi-join on an indexed column has constant-time overhead despite being implemented that way.