A method and device for optimizing queries over a vertically stored database. Items in the database are partitioned into several partitions each having a partition signature. The method includes decomposing a first query received from a user into multiple first subqueries; generating a signature for each first subquery in a way corresponding to the way of generating the partition signature; comparing the signature of each first subquery with partition signatures of all partitions respectively to obtain all partitions matching the first subquery; rewriting a second subquery translated from the first subquery based on the matching partitions to obtain a rewritten second subquery; and composing rewritten second subqueries for all first subqueries to form a second query so that queries are executed over the database using the second query.