A change in URL slug in database returns 404, how can I do auto-redirect?

If you look in the database in the $wpdb->postmeta table you will see a meta_key named _wp_old_slug. That is how WordPress tracks slug changes. By editing the database directly you bypassed the mechanisms that create that postmeta entry.

You never want to edit the database directly if you can use WordPress Core functions instead. Attempting that kind of shortcut only causes problems, expecially if you don’t have a deep and thorough grasp of WordPress internals.

What you want to do instead is run a function similar to this one from another answer:

function fix_post_slugs() {
  $posts = new WP_Query(array('post_type'=>'book'));
  if (empty($posts->posts)) return false;
  foreach ($posts->posts as $p) {
    wp_update_post((array)$p);
  }
}
fix_post_slugs();

In your case, this will do it I believe:

function fix_post_slugs() {
  $posts = new WP_Query(array('post_type'=>'post','post_per_page' =>3));
  if (empty($posts->posts)) return false;
  foreach ($posts->posts as $p) {
    // edit below to search and replace as needed
    $p->post_title = str_replace(' ','+',$p->post_title);
    $p->post_name = sanitize_title_with_dashes($p->post_title);
    wp_update_post((array)$p);
  }
}
fix_post_slugs();

I don’t know if you are in a position to back up and do that. If not, you will have to manually map your old slugs to the new ones.