Data privacy is a major concern when users query public online data services. The privacy of millions of people has been jeopardized in numerous user data leakage incidents in many popular online applications. To address the critical problem of personal data leakage through queries, we enable private querying on public data services so that the contents of user queries and any user data are hidden and therefore not revealed to the online service provider. We propose two protocols for processing private database queries, namely BHE and HHE. BHE provides complete query privacy by using Paillier's homomorphic encryption along with the bucketization of public data. In contrast to traditional Private Information Retrieval (PIR) proposals, BHE only incurs one round of client server interaction for processing one query. Built upon BHE, HHE is a hybrid protocol that applies BHE computation and communication on a subset of the data buckets, such that this subset covers the actual requested data but also mimics frequent query patterns of common users, thus achieving practical query performance while providing proper privacy protection. Because of the use of frequent query patterns and data specific privacy protection, HHE is not vulnerable to traditional attacks on k-Anonymity that explore data similarity and skewness. Moreover, HHE consistently protects user query privacy for a sequence of queries in a query session.