You won't get (normal) joins in a database like MongoDB, so that's out of question but just why inability to know queries beforehand should necessarily imply no schema? Your data does have some structure after all?
From the link to another question it seems like you need fast text searches (LIKE/ILIKE?).
Well, for that new versions of Postgres would fit the bill just fine, provided you make use of
pg_trgm extension (http://www.postgresql.org/docs/9.1/static/pgtrgm.html). It implements index (as opposed to sequential scan) searches with LIKE/ILIKE operator with wildcards.
Thanks to this extension I have managed to create phenomenally fast search engine on ~TB sized PG database.
I have also written a boolean-like query engine using
pyparsing Python module that has typical
NOT operators and keywords corresponding to (
pg_trgm-indexed) columns. It translates high-level query into SQL (actually SQLAlchemy Core SQL Expressions). This way you can query the DB in quite a flexible way while still getting results very quickly. I don't know if search engine-like functionality is what you need, but I'm sure a grammar for this could be developed quite easily using
If you need something involving more of numerical computing, PyTables is extremely fast for operation on out-of-memory datasets (although string search operators are somewhat rudimentary there).