We check key and value types for each record - this should be removed from the tight loop. Maybe an assertion.