A method and apparatus for accessing information using indexes on versioned tables is described that exploits the power of partitioned indexing to index versioned data. In partitioned indexing, an index is divided in sub-indexes, referred to as index partitions. An index may be, for example, partitioned according to a particular version identified by a version id, that is, each index partition indexes the rows in a versioned table that belong to the version identified by a particular version id. Partitioned indexes can be more efficient to use to access versioned data. The utility of partitioned indexes extends beyond indexing versioned data.