First part

In the last link at 51 slide are very good one tip witch I think should get more attention. Basic idea is to make one additional filter based on previous result set. Meanwhile my gallery implements subselects for performance improvements, but with records more than 100K records speed also degrades, so i think this performance tip can make a big difference but requires some additional work. Basic Idea i think is to shard table not sharding it actualy. For example.

Our shard status precompiled table could look like this:
 

So if we need to get some page result set, first we request bigger pid than our current one and limit max pid by the pid fined in this table. I will extend this part of the article then I implement this stuff in gallery, it should boost pagination with large offsets.

Update 

This is basic function witch does all the job. It automaticly adds additional fiters based on $params array. Also returns new key if it's needed to store.

public static function getShardFilter($params)
   {
       $shardPartSplit = 5000;
       $safeAheadOffset = 100;
       
       if (($params['offset'] / $shardPartSplit) > 1)
       {
           $db = ezcDbInstance::get(); 
           $sortKey = md5($params['sort']);
           $filterKey = md5( erLhcoreClassGallery::multi_implode(',',$params['filter']) );
           $offsetKey = floor($params['offset'] / $shardPartSplit);
           
           // Left offset filter
           $q = $db->createSelectQuery();
           $q->select( 'pid,offset' )
                ->from( 'lh_gallery_shard_limit' )
                ->where(
                   $q->expr->land(
                       $q->expr->lte( 'offset', $q->bindValue($params['offset']) ),
                       $q->expr->eq(  'identifier', $q->bindValue($params['identifier']) ),                    
                       $q->expr->eq(  'filter', $q->bindValue($filterKey )),
                       $q->expr->eq(  'sort', $q->bindValue($sortKey) ) 
                   ))
                ->limit(1,0)
                ->orderBy('offset DESC');

           $stmt = $q->prepare();
           $stmt->execute();
           $data = $stmt->fetch(PDO::FETCH_ASSOC);
         
           $appendShardData = array('filter_key' => $filterKey, 'offset' => $params['offset'], 'identifier' => $params['identifier'],'sort_key' => $sortKey );
           $returnShardFilter = array('filter' => false,'append_shard' => false );
                       
           $leftFilter = 'filterlte';
           $rightFilter = 'filtergte';
           
           if (isset($params['reverse']) && $params['reverse'] === true) {
               $leftFilter = 'filtergte';
               $rightFilter = 'filterlte';
           }
       
           
           if ($data !== false && $data['pid'] !== false ) {              
               $returnShardFilter['filter'][$leftFilter] = array('pid' => $data['pid']);
               $returnShardFilter['filter']['shard_deduct_limit'] = $data['offset'];                                   
           }
          
           // Right offset filter
           $q2 = $db->createSelectQuery();
           $q2->select( 'pid,offset' )
              ->from( 'lh_gallery_shard_limit' )
              ->where(
                   $q2->expr->land (                           
                       $q2->expr->gte( 'offset', $q2->bindValue($params['offset']) ),
                       $q2->expr->eq(  'identifier', $q2->bindValue($params['identifier']) ),                          
                       $q2->expr->eq(  'filter', $q2->bindValue($filterKey )),
                       $q2->expr->eq(  'sort', $q2->bindValue($sortKey) ) 
                   ))
               ->limit(1,0)
               ->orderBy('offset ASC');

           $stmt = $q2->prepare();
           $stmt->execute();
           $dataMin = $stmt->fetch(PDO::FETCH_ASSOC);
           
           if ($dataMin !== false && $dataMin['pid'] !== false && ($dataMin['offset'] > $params['offset'] + ($shardPartSplit/10))) {  
               $returnShardFilter['filter'][$rightFilter] =  array('pid' => $dataMin['pid']);                             
           }
           
           if (isset($data['offset']) && !isset($dataMin['pid']) && ($params['offset'] - $data['offset']) > $shardPartSplit) {               
               $returnShardFilter['append_shard'] = $appendShardData;               
           } elseif (isset($data['offset']) && isset($dataMin['offset']) && ($params['offset'] - $data['offset']) > $shardPartSplit && ($dataMin['offset'] - $params['offset']) > $shardPartSplit) {               
               $returnShardFilter['append_shard'] = $appendShardData;               
           } elseif (!isset($data['offset']) && isset($dataMin['offset']) && ($dataMin['offset']-$params['offset']) > $shardPartSplit) {
               $returnShardFilter['append_shard'] = $appendShardData;
           } elseif (!isset($data['offset']) && !isset($dataMin['offset'])) {
               $returnShardFilter['append_shard'] = $appendShardData;
           } 
       
           return $returnShardFilter;
           
       } else {
           // Offset is less than shard split part, no need any special actions
           return array('filter' => false,'append_shard' => false);
       }
   }

If everyone is interested in real live example i suggest just see the http://code.google.com/p/hppg/source/browse/trunk/lib/core/lhgallery/lhgallery.php. Currently this function is used in last uploads/albums mode, also supports ascending descending ordering. It performs well currently but in order to support different types of ordering more job involves.

Second part

One thing I found usefull then sometimes MySQL query planner chooses wrong index, and makes index merges instead of good one. So I had to use "USE INDEX (<index_name>)" it boost'ed performance and server mysql process now is not in the top :), PHP is :)