1. A method for building an efficient query plan for vertical schema, comprising: receiving query information including at least one constraint; retrieving an external histogram having information for name-value pairs of the vertical schema; determining selectivity estimates for the at least one constraint using the external histogram; and generating the query plan using at least some of the selectivity estimates.