Why the record in the DB is deleted? You should delete just records relative to cookies you know are expired.
A simple way to know is adding a timestamp column to the session table and then erase just sessions expired as they are older than the expire time you should set in the cookie (and you don't right now). The best way to handle this is with a job scheduled to run when you got low traffic on your website.

$|=$_="1g2i1u1l2i4e2n0k",map{print"\7",chop;select$,,$,,$,,$_/7}m{..}g