Scalable query processing and scalable query engines over Cloud databases is a vibrant area of research, which has recently emerged within both the academic and industrial research community. This area has been further stirred-up by the current explosion of big data management and analytics models and techniques that, usually executed within the internal layer of public as well as private Clouds, pose severe (and new!) challenges to the annoying distributed query processing optimization problem in (distributed) database systems. Among other, taming the complexity of query execution plays a leading role, especially considering the typical Cloud environment that includes tens and tens of different-in-granularity data processing tasks (also at a different scale) over large-scale clusters. Inspired by these considerations, this paper focuses on models, paradigms, techniques and future challenges of scalable query processing and query engines over Cloud databases, by reporting on state-of-the-art results as well as emerging trends, with also criticisms on future work that we should expect from the community.