Data outsourcing or database as a service is a new paradigm for data management. The third party service provider hosts databases as a service. These parties provide efficient and cheap data management by obviating the need to purchase expensive hardware and software, deal with software upgrades and hire professionals for administrative and maintenance tasks. However, due to recent governmental legislations, competition among companies and database thefts, companies cannot use database service providers directly. They need secure and privacy preserving data management techniques to be able to use them in practice. Since data is remotely stored in a privacy preserving manner, there are efficiency related problems such as poor query response time. We propose a new framework that provides efficient and scalable query response times by reducing the computation and communication costs. Furthermore, the proposed technique uses several service providers to guarantee the availability of the services while detecting the dishonest or faulty service providers without introducing additional overhead on the query response time. The evaluations demonstrate that our data outsourcing framework is scalable and practical.