A system, method and software product provides for true multimedia document retrieval by receiving multimedia queries containing various types of data, such as text keywords, images, audio or other data types, and processing such queries against a multimedia index that commonly indexes multimedia documents, including any of their multimedia components. The unified index allows query retrieval by evaluation of a query structure which can contain any of the multimedia data types, and operators which can be evaluated on any of these data types. The system indexes multimedia documents by separating them into their multimedia components, and processing each component into a number of tokens. The tokens are stored in the index along with information identifying the documents that contain the token, and reference data describing the position of the token within the documents, and any other data extracted from the multimedia component of the document, such as color, texture, luminance, recognized speech, or the like. During retrieval, a query is decomposed into multimedia components, which are then converted to a set of tokens and query structure including mathematical and proximity operators. Query expansion is used to expand the query structure to include additional tokens corresponding to various ones of input query tokens. Because the multimedia components are all indexed in the unified index, there is no need to process different parts of the query against different indices and databases in order to select documents that best satisfy the query.