(addressed review input)
The issue was introduced by @@optimizer_max_sel_arg_weight code.
key_or() calls SEL_ARG::update_weight_locally().  That function
takes O(tree->elements) time.
Without that call, key_or(big_tree, one_element_tree) would take
O(log(big_tree)) when one_element_tree doesn't overlap with elements
of big_tree.
This means, update_weight_locally() can cause a big slowdown.

The fix:
1. key_or() actually doesn't need to call update_weight_locally().
  It calls SEL_ARG::tree_delete() and SEL_ARG::insert(). These functions
  update SEL_ARG::weight.
  It also manipulates the SEL_ARG objects directly, but these
  modifications do not change the weight of the tree.
  I've just removed the update_weight_locally() call.
2. and_all_keys() also calls update_weight_locally(). It manipulates the
  SEL_ARG graph directly.
  Removed that call and added the code to update the SEL_ARG graph weight.

Tests main.range and main.range_not_embedded already contain the queries
that have test coverage for the affected code.