LTP GCOV extension - code coverage report
Current view: directory - storage/maria - ma_range.c
Test: mtr_and_unit.info
Date: 2009-03-05 Instrumented lines: 91
Code covered: 76.9 % Executed lines: 70

       1                 : /* Copyright (C) 2006 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
       2                 : 
       3                 :    This program is free software; you can redistribute it and/or modify
       4                 :    it under the terms of the GNU General Public License as published by
       5                 :    the Free Software Foundation; version 2 of the License.
       6                 : 
       7                 :    This program is distributed in the hope that it will be useful,
       8                 :    but WITHOUT ANY WARRANTY; without even the implied warranty of
       9                 :    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      10                 :    GNU General Public License for more details.
      11                 : 
      12                 :    You should have received a copy of the GNU General Public License
      13                 :    along with this program; if not, write to the Free Software
      14                 :    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
      15                 : 
      16                 : /*
      17                 :   Gives a approximated number of how many records there is between two keys.
      18                 :   Used when optimizing querries.
      19                 :  */
      20                 : 
      21                 : #include "maria_def.h"
      22                 : #include "ma_rt_index.h"
      23                 : 
      24                 : static ha_rows _ma_record_pos(MARIA_HA *,const uchar *, key_part_map,
      25                 :                               enum ha_rkey_function);
      26                 : static double _ma_search_pos(MARIA_HA *, MARIA_KEY *, uint32, my_off_t);
      27                 : static uint _ma_keynr(MARIA_PAGE *page, uchar *keypos, uint *ret_max_key);
      28                 : 
      29                 : 
      30                 : /**
      31                 :    @brief Estimate how many records there is in a given range
      32                 : 
      33                 :    @param  info            MARIA handler
      34                 :    @param  inx             Index to use
      35                 :    @param  min_key         Min key. Is = 0 if no min range
      36                 :    @param  max_key         Max key. Is = 0 if no max range
      37                 : 
      38                 :    @note
      39                 :      We should ONLY return 0 if there is no rows in range
      40                 : 
      41                 :    @return Estimated number of rows or error
      42                 :      @retval HA_POS_ERROR  error (or we can't estimate number of rows)
      43                 :      @retval number        Estimated number of rows
      44                 : */
      45                 : 
      46                 : ha_rows maria_records_in_range(MARIA_HA *info, int inx, key_range *min_key,
      47                 :                             key_range *max_key)
      48             881 : {
      49                 :   ha_rows start_pos,end_pos,res;
      50             881 :   MARIA_SHARE *share= info->s;
      51                 :   MARIA_KEY key;
      52                 :   MARIA_KEYDEF *keyinfo;
      53             881 :   DBUG_ENTER("maria_records_in_range");
      54                 : 
      55             881 :   if ((inx = _ma_check_index(info,inx)) < 0)
      56               0 :     DBUG_RETURN(HA_POS_ERROR);
      57                 : 
      58             881 :   if (fast_ma_readinfo(info))
      59               0 :     DBUG_RETURN(HA_POS_ERROR);
      60             881 :   info->update&= (HA_STATE_CHANGED+HA_STATE_ROW_CHANGED);
      61             881 :   keyinfo= share->keyinfo + inx;
      62             881 :   if (share->lock_key_trees)
      63               0 :     rw_rdlock(&keyinfo->root_lock);
      64                 : 
      65             881 :   switch (keyinfo->key_alg) {
      66                 : #ifdef HAVE_RTREE_KEYS
      67                 :   case HA_KEY_ALG_RTREE:
      68                 :   {
      69                 :     uchar *key_buff;
      70                 : 
      71                 :     /*
      72                 :       The problem is that the optimizer doesn't support
      73                 :       RTree keys properly at the moment.
      74                 :       Hope this will be fixed some day.
      75                 :       But now NULL in the min_key means that we
      76                 :       didn't make the task for the RTree key
      77                 :       and expect BTree functionality from it.
      78                 :       As it's not able to handle such request
      79                 :       we return the error.
      80                 :     */
      81               0 :     if (!min_key)
      82                 :     {
      83               0 :       res= HA_POS_ERROR;
      84               0 :       break;
      85                 :     }
      86               0 :     key_buff= info->last_key.data + share->base.max_key_length;
      87               0 :     _ma_pack_key(info, &key, inx, key_buff,
      88                 :                  min_key->key, min_key->keypart_map,
      89                 :                  (HA_KEYSEG**) 0);
      90               0 :     res= maria_rtree_estimate(info, &key, maria_read_vec[min_key->flag]);
      91               0 :     res= res ? res : 1;                       /* Don't return 0 */
      92               0 :     break;
      93                 :   }
      94                 : #endif
      95                 :   case HA_KEY_ALG_BTREE:
      96                 :   default:
      97             881 :     start_pos= (min_key ?
      98                 :                 _ma_record_pos(info, min_key->key, min_key->keypart_map,
      99                 :                                min_key->flag) :
     100                 :                 (ha_rows) 0);
     101             881 :     end_pos=   (max_key ?
     102                 :                 _ma_record_pos(info, max_key->key, max_key->keypart_map,
     103                 :                                max_key->flag) :
     104                 :                 info->state->records + (ha_rows) 1);
     105             881 :     res= (end_pos < start_pos ? (ha_rows) 0 :
     106                 :           (end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos));
     107             881 :     if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
     108               0 :       res=HA_POS_ERROR;
     109                 :   }
     110                 : 
     111             881 :   if (share->lock_key_trees)
     112               0 :     rw_unlock(&keyinfo->root_lock);
     113             881 :   fast_ma_writeinfo(info);
     114                 : 
     115                 :   /**
     116                 :      @todo LOCK
     117                 :      If res==0 (no rows), if we need to guarantee repeatability of the search,
     118                 :      we will need to set a next-key lock in this statement.
     119                 :      Also SELECT COUNT(*)...
     120                 :   */
     121                 : 
     122             881 :   DBUG_PRINT("info",("records: %ld",(ulong) (res)));
     123             881 :   DBUG_RETURN(res);
     124                 : }
     125                 : 
     126                 : 
     127                 :         /* Find relative position (in records) for key in index-tree */
     128                 : 
     129                 : static ha_rows _ma_record_pos(MARIA_HA *info, const uchar *key_data,
     130                 :                               key_part_map keypart_map,
     131                 :                               enum ha_rkey_function search_flag)
     132            1762 : {
     133            1762 :   uint inx= (uint) info->lastinx;
     134                 :   uint32 nextflag;
     135                 :   uchar *key_buff;
     136                 :   double pos;
     137                 :   MARIA_KEY key;
     138            1762 :   DBUG_ENTER("_ma_record_pos");
     139            1762 :   DBUG_PRINT("enter",("search_flag: %d",search_flag));
     140            1762 :   DBUG_ASSERT(keypart_map);
     141                 : 
     142            1762 :   key_buff= info->lastkey_buff+info->s->base.max_key_length;
     143            1762 :   _ma_pack_key(info, &key, inx, key_buff, key_data, keypart_map,
     144                 :                        (HA_KEYSEG**) 0);
     145            1762 :   DBUG_EXECUTE("key", _ma_print_key(DBUG_FILE, &key););
     146            1762 :   nextflag=maria_read_vec[search_flag];
     147                 : 
     148                 :   /*
     149                 :     my_handler.c:ha_compare_text() has a flag 'skip_end_space'.
     150                 :     This is set in my_handler.c:ha_key_cmp() in dependence on the
     151                 :     compare flags 'nextflag' and the column type.
     152                 : 
     153                 :     TEXT columns are of type HA_KEYTYPE_VARTEXT. In this case the
     154                 :     condition is skip_end_space= ((nextflag & (SEARCH_FIND |
     155                 :     SEARCH_UPDATE)) == SEARCH_FIND).
     156                 : 
     157                 :     SEARCH_FIND is used for an exact key search. The combination
     158                 :     SEARCH_FIND | SEARCH_UPDATE is used in write/update/delete
     159                 :     operations with a comment like "Not real duplicates", whatever this
     160                 :     means. From the condition above we can see that 'skip_end_space' is
     161                 :     always false for these operations. The result is that trailing space
     162                 :     counts in key comparison and hence, emtpy strings ('', string length
     163                 :     zero, but not NULL) compare less that strings starting with control
     164                 :     characters and these in turn compare less than strings starting with
     165                 :     blanks.
     166                 : 
     167                 :     When estimating the number of records in a key range, we request an
     168                 :     exact search for the minimum key. This translates into a plain
     169                 :     SEARCH_FIND flag. Using this alone would lead to a 'skip_end_space'
     170                 :     compare. Empty strings would be expected above control characters.
     171                 :     Their keys would not be found because they are located below control
     172                 :     characters.
     173                 : 
     174                 :     This is the reason that we add the SEARCH_UPDATE flag here. It makes
     175                 :     the key estimation compare in the same way like key write operations
     176                 :     do. Olny so we will find the keys where they have been inserted.
     177                 : 
     178                 :     Adding the flag unconditionally does not hurt as it is used in the
     179                 :     above mentioned condition only. So it can safely be used together
     180                 :     with other flags.
     181                 :   */
     182            1762 :   pos= _ma_search_pos(info, &key,
     183                 :                       nextflag | SEARCH_SAVE_BUFF | SEARCH_UPDATE,
     184                 :                       info->s->state.key_root[inx]);
     185            1762 :   if (pos >= 0.0)
     186                 :   {
     187            1762 :     DBUG_PRINT("exit",("pos: %ld",(ulong) (pos*info->state->records)));
     188            1762 :     DBUG_RETURN((ulong) (pos*info->state->records+0.5));
     189                 :   }
     190               0 :   DBUG_RETURN(HA_POS_ERROR);
     191                 : }
     192                 : 
     193                 : 
     194                 : /**
     195                 :   Find offset for key on index page
     196                 : 
     197                 :   @notes
     198                 :    Modified version of _ma_search()
     199                 : 
     200                 :   @return
     201                 :   @retval 0.0 <= x <= 1.0
     202                 : */
     203                 : 
     204                 : static double _ma_search_pos(MARIA_HA *info, MARIA_KEY *key,
     205                 :                              uint32 nextflag, my_off_t pos)
     206            3442 : {
     207                 :   int flag;
     208                 :   uint keynr, max_keynr;
     209                 :   my_bool after_key;
     210                 :   uchar *keypos;
     211                 :   double offset;
     212            3442 :   MARIA_KEYDEF *keyinfo= key->keyinfo;
     213                 :   MARIA_PAGE page;
     214            3442 :   DBUG_ENTER("_ma_search_pos");
     215            3442 :   LINT_INIT(max_keynr);
     216                 : 
     217            3442 :   if (pos == HA_OFFSET_ERROR)
     218             486 :     DBUG_RETURN(0.5);
     219                 : 
     220            2956 :   if (_ma_fetch_keypage(&page, info, keyinfo, pos,
     221                 :                         PAGECACHE_LOCK_LEFT_UNLOCKED, DFLT_INIT_HITS,
     222                 :                         info->buff, 1))
     223            2956 :     goto err;
     224            2956 :   flag= (*keyinfo->bin_search)(key, &page, nextflag, &keypos,
     225                 :                                info->lastkey_buff, &after_key);
     226            2956 :   keynr= _ma_keynr(&page, keypos, &max_keynr);
     227                 : 
     228            2956 :   if (flag)
     229                 :   {
     230            2465 :     if (flag == MARIA_FOUND_WRONG_KEY)
     231               0 :       DBUG_RETURN(-1);                          /* error */
     232                 :     /*
     233                 :       Didn't found match. keypos points at next (bigger) key
     234                 :       Try to find a smaller, better matching key.
     235                 :       Matches keynr + [0-1]
     236                 :     */
     237            3255 :     if (flag > 0 && ! page.node)
     238             790 :       offset= 1.0;
     239            1675 :     else if ((offset= _ma_search_pos(info, key, nextflag,
     240                 :                                      _ma_kpos(page.node,keypos))) < 0)
     241               0 :       DBUG_RETURN(offset);
     242                 :   }
     243                 :   else
     244                 :   {
     245                 :     /*
     246                 :       Found match. Keypos points at the start of the found key
     247                 :       Matches keynr+1
     248                 :     */
     249             491 :     offset=1.0;                                 /* Matches keynr+1 */
     250             491 :     if ((nextflag & SEARCH_FIND) && page.node &&
     251                 :         ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
     252                 :          (nextflag & (SEARCH_PREFIX | SEARCH_NO_FIND | SEARCH_LAST |
     253                 :                       SEARCH_PART_KEY))))
     254                 :     {
     255                 :       /*
     256                 :         There may be identical keys in the tree. Try to match on of those.
     257                 :         Matches keynr + [0-1]
     258                 :       */
     259               5 :       if ((offset= _ma_search_pos(info, key, SEARCH_FIND,
     260                 :                                   _ma_kpos(page.node,keypos))) < 0)
     261               0 :         DBUG_RETURN(offset);                    /* Read error */
     262                 :     }
     263                 :   }
     264            2956 :   DBUG_PRINT("info",("keynr: %d  offset: %g  max_keynr: %d  nod: %d  flag: %d",
     265                 :                      keynr,offset,max_keynr,page.node,flag));
     266            2956 :   DBUG_RETURN((keynr+offset)/(max_keynr+1));
     267               0 : err:
     268               0 :   DBUG_PRINT("exit",("Error: %d",my_errno));
     269               0 :   DBUG_RETURN (-1.0);
     270                 : }
     271                 : 
     272                 : 
     273                 : /* Get keynummer of current key and max number of keys in nod */
     274                 : 
     275                 : static uint _ma_keynr(MARIA_PAGE *page, uchar *keypos, uint *ret_max_key)
     276            2956 : {
     277                 :   uint page_flag, nod_flag, keynr, max_key;
     278                 :   uchar t_buff[MARIA_MAX_KEY_BUFF], *pos, *end;
     279            2956 :   const MARIA_KEYDEF *keyinfo= page->keyinfo;
     280                 :   MARIA_KEY key;
     281                 : 
     282            2956 :   page_flag= page->flag;
     283            2956 :   nod_flag=  page->node;
     284            2956 :   pos= page->buff + page->info->s->keypage_header + nod_flag;
     285            2956 :   end= page->buff + page->size;
     286                 : 
     287            2956 :   if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
     288                 :       ! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
     289                 :   {
     290            1688 :     *ret_max_key= (uint) (end - pos)/(keyinfo->keylength+nod_flag);
     291            1688 :     return (uint) (keypos - pos)/(keyinfo->keylength+nod_flag);
     292                 :   }
     293                 : 
     294            1268 :   max_key=keynr=0;
     295            1268 :   t_buff[0]=0;                                  /* Safety */
     296            1268 :   key.data= t_buff;
     297            1268 :   key.keyinfo= (MARIA_KEYDEF*) keyinfo;
     298                 : 
     299          610941 :   while (pos < end)
     300                 :   {
     301          608405 :     if (!(pos= (*keyinfo->skip_key)(&key, page_flag, nod_flag, pos)))
     302                 :     {
     303               0 :       DBUG_ASSERT(0);
     304                 :       return 0;                                 /* Error */
     305                 :     }
     306          608405 :     max_key++;
     307          608405 :     if (pos == keypos)
     308             878 :       keynr= max_key;
     309                 :   }
     310            1268 :   *ret_max_key=max_key;
     311            1268 :   return(keynr);
     312                 : }

Generated by: LTP GCOV extension version 1.4