Description of the issue:
Clone of upstream issue: https://github.com/gluster/glusterfs/issues/2611

Number of lookups in granular entry self-heal is very high compared to full entry self-heal. Here are the numbers for the following workload:

Once a replica 3 volume(r3) is created and mounted:
gluster volume profile r3 start
pushd /mnt/r3
mkdir d
cd d
kill -9 $(gluster volume status | grep Brick | awk '{print $NF}' | head -1)
for i in {1..100000}; do touch $i; done
gluster volume profile r3 info incremental
gluster volume start r3 force
popd
Once heal completes, take one more profile info incremental.

base-full-heal.txt:      52.72  38828.24  ns  20130.00  ns  31109878.00  ns  300024   LOOKUP
base-full-heal.txt:      65.47  41799.10  ns  10173.00  ns  2497157.00   ns  400022   LOOKUP
base-full-heal.txt:      66.68  70149.87  ns  34635.00  ns  1554337.00   ns  200017   LOOKUP

base-granular-heal.txt:  72.06  57450.77  ns  20245.00  ns  23499908.00  ns  800010   LOOKUP
base-granular-heal.txt:  79.99  57926.16  ns  12702.00  ns  12933708.00  ns  900008   LOOKUP
base-granular-heal.txt:  82.11  69301.03  ns  27820.00  ns  12533029.00  ns  700006   LOOKUP

This is happening because there is a check for stale index before triggering the actual heal which is triggering extra lookups. This lookup happens on AFR xlator which will try metadata heal etc so the number of lookups increases even more.