Many database users are not familiar with formal query languages, the concept of schema, or the exact content of their database. Thus, it is challenging for these users to formulate their information needs over semi-structured and structured databases. To address this problem, researchers have proposed usable query interfaces over which users can formulate their information needs without knowing about formal query languages, schema or the exact content of the database. Although the mentioned interfaces increase the us-ability of the databases, they inherently suﬀer from low eﬀectiveness and eﬃciency. The recent growth in databases’ content size and schema complexity only exacerbates this problem. In this dissertation, we present a set of approaches to redesign the components of database management systems to improve the eﬀectiveness and eﬃciency of query processing. We present theoretical and empirical results on the impact of database size and schema complexity on the eﬀectiveness of keyword query search. Based on these results, we propose a system that answers keyword queries more eﬀectively. Further-more, we present an online learning method that improves the response time of query processing over large databases.