Original: Costello didn't record it himself until 1996, on his album of the same title.
Simplified: Costello didn't record it himself until 1996, on his album All This Useless Beauty.