The output of a query absolutely will depend on the plan. In ANSI SQL you're right it cannot (up to ordering), which is why ANSI SQL doesn't have anything like random() or nondeterministic user functions. But nearly all databases support something that is outside of that standard because it's genuinely useful, and then you get into poorly-defined situations that you need to deal with ad-hoc as an implementer.

E.g., for a very simple case, in SELECT * FROM a,b WHERE random() < 0.5, would you push random() down through the join or not? To one table? Both tables? Evaluate it once at the start of a query because it depends on neither a nor b? What if it's random() < a.x? Different databases have different and often poorly-defined semantics here.