It looks like permissions are broken after upgrade to 19.04 for the following files:
$ ls -l /var/lib/command-not-found
total 3184
-rw-r----- 1 root root 3252224 Apr 23 23:01 commands.db
-rw-r----- 1 root root 2403 Apr 23 23:01 commands.db.metadata
I've repaired them with
$ sudo chmod ugo+r /var/lib/command-not-found/commands.db*
It looks like permissions are broken after upgrade to 19.04 for the following files: command- not-found db.metadata
$ ls -l /var/lib/
total 3184
-rw-r----- 1 root root 3252224 Apr 23 23:01 commands.db
-rw-r----- 1 root root 2403 Apr 23 23:01 commands.
I've repaired them with command- not-found/ commands. db*
$ sudo chmod ugo+r /var/lib/
command-not-found is not crashing after that.