How many records did you insert before running the SP another time? If it was a significant amount, then it will greatly affect index fragmentation. Rebuilding the index for the 'uid' field might help with that. If there isn't an index on the uid, then you'll definitely want that.

What performance tier is your database? If it's Basic, then I believe you're still using shared resources and performance can greatly vary.