A famous result by Jeavons, Cohen, and Gyssens shows that every constraint
satisfaction problem (CSP) where the constraints are preserved by a
semi-lattice operation can be solved in polynomial time. This is one of the
basic facts for the so-called universal-algebraic approach to a systematic
theory of tractability and hardness in finite domain constraint satisfaction.

Not surprisingly, the theorem of Jeavons et al. fails for arbitrary infinite
domain CSPs. Many CSPs of practical interest, though, and in particular those
CSPs that are motivated by qualitative reasoning calculi from Artificial
Intelligence, can be formulated with constraint languages that are rather
well-behaved from a model-theoretic point of view. In particular, the
automorphism group of these constraint languages tends to be large in the sense
that the number of orbits of n-subsets of the automorphism group is bounded by
some function in n.

In this paper we present a generalization of the theorem by Jeavons et al. to
infinite domain CSPs where the number of orbits of n-subsets grows
sub-exponentially in n, and prove that preservation under a semi-lattice
operation for such CSPs implies polynomial-time tractability. Unlike the result
of Jeavons et al., this includes many CSPs that cannot be solved by Datalog.