A technique is described for performing a maintenance operation within an apparatus that is used to control access to a memory device. The apparatus has a storage device for storing access requests to be issued to the memory device, and maintenance circuitry for performing a maintenance operation on storage elements provided within the storage device. Memory access execution circuitry is used to issue to a physical layer interface access requests selected from the storage device, for onward propagation from the physical layer interface to the memory device. Control circuitry is responsive to a training event to initiate a training operation of the physical layer interface. In addition, the control circuitry is further responsive to the training event to trigger performance of the maintenance operation by the maintenance circuitry whilst the training operation is being performed.