As the Internet of Things (IoT) is evolving at a fast pace, the need for contextual intelligence has become more crucial for delivering IoT intelligence, efficiency, effectiveness, performance, and sustainability. Contextual intelligence enables interactions between IoT devices such as sensors/actuators, smartphones and connected vehicles, to name but a few. Context management platforms (CMP) are emerging as a promising solution to deliver contextual intelligence for IoT. However, the development of a generic solution that allows IoT devices and services to publish, consume, monitor, and share context is still in its infancy. In this paper, we propose, validate and explain the details of a novel mechanism called Context Query Engine (CQE), which is an integral part of a pioneering CMP called Context-as-a-Service (CoaaS). CQE is responsible for efficient execution of context queries in near real-time. We present the architecture of CQE and illuminate its workflows. We also conduct extensive experimental performance and scalability evaluation of the proposed CQE. Results of experimental evaluation convincingly demonstrate that CoaaS outperforms its competitors in executing complex context queries. Moreover, the advanced functionality of the embedded query language makes CoaaS a decent candidate for real-life deployments.