Security and privacy concerns, as well as legal considerations, force many companies to encrypt the sensitive data in their databases. However, storing the data in encrypted format entails significant performance penalties during query processing. In this paper, we address several design issues related to querying encrypted relational databases. The experiments we conducted on benchmark datasets show that excessive decryption costs during query processing result in CPU bottleneck. As a solution we propose a new method based on schema decomposition that partitions sensitive and non-sensitive attributes of a relation into two separate relations. Our method improves the system performance dramatically by parallelizing disk IO latency with CPU-intensive operations (i.e., encryption/decryption).