Why does changing the declared join column order introduce a sort?
Is this intentional?


It is by design, yes. The best public source for this assertion was unfortunately lost when Microsoft retired the Connect feedback site, obliterating many useful comments from developers on the SQL Server team.

Anyway, the current optimizer design does not actively seek to avoid unnecessary sorts per se. This is most often encountered with windowing functions and the like, but can also be seen with other operators that are sensitive to ordering, and in particular to preserved ordering between operators.

Nevertheless, the optimizer is quite good (in many cases) at avoiding unnecessary sorting, but this outcome normally occurs for reasons other than aggressively trying different ordering combinations. In that sense, it is not so much a question of 'search space' as it is of the complex interactions between orthogonal optimizer features that have been shown to increase general plan quality at acceptable cost.

For example, sorting can often be avoided simply by matching an ordering requirement (e.g. top-level ORDER BY) to an existing index. Trivially in your case that could mean adding ORDER BY l.a, l.b, l.c, l.d, l.e, l.f, l.g, l.h; but this is an over-simplification (and unacceptable because you do not want to change the query).

More generally, each memo group may be associated with required or desired properties, which may include input ordering. When there is no obvious reason to enforce a particular order (e.g. to satisfy an ORDER BY, or to ensure correct results from an order-sensitive physical operator), there is an element of 'luck' involved. I wrote more about the specifics of that as it pertains to merge join (in union or join mode) in Avoiding Sorts with Merge Join Concatenation. Much of that goes beyond the supported surface area of the product, so treat it as informational, and subject to change.

In your particular case, yes, you may adjust the indexing as jadarnel27 suggests to avoid the sorts; though there is little reason to actually prefer a merge join here. You could also hint a choice between hash or loop physical join with OPTION(HASH JOIN, LOOP JOIN) using a Plan Guide without changing the query, depending on your knowledge of the data, and the trade-off between best, worst, and average-case performance.

Finally, as a curiosity, note that the sorts can be avoided with a simple ORDER BY l.b, at the cost of a potentially less efficient many-to-many merge join on b alone, with a complex residual. I mention this mostly as an illustration of the interaction between optimizer features I mentioned previously, and the way top-level requirements can propagate.