Technologies are generally provided for progressive key value store switchover by evaluating a maturity of a migrated data store and allowing piecewise switching of substructure area query servicing from an origin data store to a destination data store. In some examples, abstractions of origin and destination tree structures may be compared to each other in order to generate an evaluation metric at substantially reduced performance evaluation load. The evaluation metric may target performance sampling while assuring a desired performance level with localized query servicing switchover. Piecewise data transfer may also be optionally enabled such that overall storage can be similar to the storage of a single data store copy while reducing an impact on existing data store services.