Yes, the database wasn’t there. I found solution here (`command-not-found` unable to open database - #8 by cdepillabout)
I just run sudo nix-channel --update to fix that.
But unfortunately, programs.sqlite maps executable name to package name, I need full file index. Maybe it will be useful for someone, programs.sqlite contains only in nixos channels. FYI you can download it from Channels for NixOS project(s) nixexprs.tar.xz file.
Thanks, the issue is closed now.