A massively parallel processing (MPP) database can be re-partitioned/re-balanced while remaining on-line through a staged migration procedure. Staged migration may include a first stage and a second stage. During the first stage, entries in an existing partition are reallocated to the new partition, and the catalog is updated to associate the re-allocated entries with both the existing partition and the new partition such that queries for the re-allocated entries are directed toward the existing partition and the new partition. During the second stage, the re-allocated entries are migrated from the existing partition to the new partition, and after the migration is complete, the catalog is re-updated to associate the migrated entries with the new partition such that new queries are directed toward the new partition.