Phoenix-180

A fresh pull request with all the changes for guideposts. 
Tested in a single cluster for different combinations. 
"SELECT count(*) FROM  %s WHERE host='CS' AND domain='Apple.com' AND FEATURE >= 'Dashboard' AND FEATURE <= 'Report';" % (table)) 
With 5000000 rows
Withoutpatch
===========
COUNT(1)
----------
    555169
Time: 2.264 sec(s)
Withpatch
=========
  COUNT(1)
----------
    555169
Time: 0.813 sec(s)

Withoutpatch
==========
  COUNT(1)
----------
   1002201
Time: 1.889 sec(s)
Withpatch
==========
  COUNT(1)
----------
   1002201
Time: 1.075 sec(s)

Am sure we would get better results if we are able to tune the guidePosts width so that instead of fetching in the range of 1000s inside a region we can fetch 10ks of result in every chunk.  Also should work with bigger tables and more rows.
The tests were performed with 256*1024 and 1024 * 1024 as the guidepostsWidth size. 
The main thing you can observe in the above case is that the query targetted to single region is parallelized and distributed to smaller chunks and so the work done by every thread is less. 
This isn't quite right and is doing more comparisons than necessary. Try this instead (and you can use this to replace the if statement too if you ensure your getGuidePosts() method return an empty list instead of null which IMHO is better):

        byte[] currentKey = regions.get(0).getRegionInfo().getStartKey();
        int regionIndex = 0;
        int guideIndex = 0;
        int gpsSize = gps.size();
        int lastRegionIndex = regions.size() - 1;
        // Merge bisect with guideposts for all but the last region
        while (regionIndex < lastRegionIndex) {
            byte[] currentGuidePost;
            byte[] endKey = regions.get(regionIndex++).getRegionInfo().getEndKey();
            while (guideIndex < gpsSize && Bytes.compareTo(currentGuidePost = gps.get(guideIndex), endKey) <= 0) {
                KeyRange keyRange = KeyRange.getKeyRange(currentKey, currentGuidePost);
                if (keyRange != KeyRange.EMPTY_RANGE) {
                    guidePosts.add(keyRange);
                }
                currentKey = currentGuidePost;
                if (++guideIndex == gpsSize) {
                    break;
                }
                currentGuidePost = gps.get(guideIndex);
            }
            KeyRange keyRange = KeyRange.getKeyRange(currentKey, endKey);
            if (keyRange != KeyRange.EMPTY_RANGE) {
                guidePosts.add(keyRange);
            }
            currentKey = endKey;
        }
        // While more guideposts, add them as we're at the last region and thus
        // no longer need to compare against the end key
        while (guideIndex < gpsSize) {
            currentGuidePost = gps.get(guideIndex++);
            KeyRange keyRange = KeyRange.getKeyRange(currentKey, currentGuidePost);
            if (keyRange != KeyRange.EMPTY_RANGE) {
                guidePosts.add(keyRange);
            }
            currentKey = currentGuidePost;
        }
        // Add last range that spans until the end of the region
        KeyRange keyRange = KeyRange.getKeyRange(currentKey, KeyRange.UNBOUND);
        if (keyRange != KeyRange.EMPTY_RANGE) {
            guidePosts.add(keyRange);
        }
        if (logger.isDebugEnabled()) {
            logger.debug("The captured guideposts are: " + guidePosts);
        }
        return guidePosts;