← Back to branch summary

~ubuntu-branches/ubuntu/precise/mysql-5.1/precise

« back to all changes in this revision

Viewing changes to storage/myisam/mi_range.c

  • Committer: Bazaar Package Importer
  • Author(s): Norbert Tretkowski
  • Date: 2010-03-17 14:56:02 UTC
  • Revision ID: james.westby@ubuntu.com-20100317145602-x7e30l1b2sb5s6w6
Tags: upstream-5.1.45
Import upstream version 5.1.45

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/myisam/mi_range.c
 
1
/* Copyright (C) 2000-2004, 2006 MySQL 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 "myisamdef.h"
 
22
#include "rt_index.h"
 
23
 
 
24
static ha_rows _mi_record_pos(MI_INFO *, const uchar *, key_part_map,
 
25
                              enum ha_rkey_function);
 
26
static double _mi_search_pos(MI_INFO *,MI_KEYDEF *,uchar *, uint,uint,my_off_t);
 
27
static uint _mi_keynr(MI_INFO *info,MI_KEYDEF *,uchar *, uchar *,uint *);
 
28
 
 
29
/*
 
30
  Estimate how many records there is in a given range
 
31
 
 
32
  SYNOPSIS
 
33
    mi_records_in_range()
 
34
    info                MyISAM handler
 
35
    inx                 Index to use
 
36
    min_key             Min key. Is = 0 if no min range
 
37
    max_key             Max key. Is = 0 if no max range
 
38
 
 
39
  NOTES
 
40
    We should ONLY return 0 if there is no rows in range
 
41
 
 
42
  RETURN
 
43
    HA_POS_ERROR  error (or we can't estimate number of rows)
 
44
    number        Estimated number of rows
 
45
*/
 
46
  
 
47
ha_rows mi_records_in_range(MI_INFO *info, int inx,
 
48
                            key_range *min_key, key_range *max_key)
 
49
{
 
50
  ha_rows start_pos,end_pos,res;
 
51
  DBUG_ENTER("mi_records_in_range");
 
52
 
 
53
  if ((inx = _mi_check_index(info,inx)) < 0)
 
54
    DBUG_RETURN(HA_POS_ERROR);
 
55
 
 
56
  if (fast_mi_readinfo(info))
 
57
    DBUG_RETURN(HA_POS_ERROR);
 
58
  info->update&= (HA_STATE_CHANGED+HA_STATE_ROW_CHANGED);
 
59
  if (info->s->concurrent_insert)
 
60
    rw_rdlock(&info->s->key_root_lock[inx]);
 
61
 
 
62
  switch(info->s->keyinfo[inx].key_alg){
 
63
#ifdef HAVE_RTREE_KEYS
 
64
  case HA_KEY_ALG_RTREE:
 
65
  {
 
66
    uchar * key_buff;
 
67
    uint start_key_len;
 
68
 
 
69
    /*
 
70
      The problem is that the optimizer doesn't support
 
71
      RTree keys properly at the moment.
 
72
      Hope this will be fixed some day.
 
73
      But now NULL in the min_key means that we
 
74
      didn't make the task for the RTree key
 
75
      and expect BTree functionality from it.
 
76
      As it's not able to handle such request
 
77
      we return the error.
 
78
    */
 
79
    if (!min_key)
 
80
    {
 
81
      res= HA_POS_ERROR;
 
82
      break;
 
83
    }
 
84
    key_buff= info->lastkey+info->s->base.max_key_length;
 
85
    start_key_len= _mi_pack_key(info,inx, key_buff,
 
86
                                (uchar*) min_key->key, min_key->keypart_map,
 
87
                                (HA_KEYSEG**) 0);
 
88
    res= rtree_estimate(info, inx, key_buff, start_key_len,
 
89
                        myisam_read_vec[min_key->flag]);
 
90
    res= res ? res : 1;                       /* Don't return 0 */
 
91
    break;
 
92
  }
 
93
#endif
 
94
  case HA_KEY_ALG_BTREE:
 
95
  default:
 
96
    start_pos= (min_key ?  _mi_record_pos(info, min_key->key,
 
97
                                          min_key->keypart_map, min_key->flag)
 
98
                        : (ha_rows) 0);
 
99
    end_pos=   (max_key ?  _mi_record_pos(info, max_key->key,
 
100
                                          max_key->keypart_map, max_key->flag)
 
101
                        : info->state->records + (ha_rows) 1);
 
102
    res= (end_pos < start_pos ? (ha_rows) 0 :
 
103
          (end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos));
 
104
    if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
 
105
      res=HA_POS_ERROR;
 
106
  }
 
107
 
 
108
  if (info->s->concurrent_insert)
 
109
    rw_unlock(&info->s->key_root_lock[inx]);
 
110
  fast_mi_writeinfo(info);
 
111
 
 
112
  DBUG_PRINT("info",("records: %ld",(ulong) (res)));
 
113
  DBUG_RETURN(res);
 
114
}
 
115
 
 
116
 
 
117
        /* Find relative position (in records) for key in index-tree */
 
118
 
 
119
static ha_rows _mi_record_pos(MI_INFO *info, const uchar *key,
 
120
                              key_part_map keypart_map,
 
121
                              enum ha_rkey_function search_flag)
 
122
{
 
123
  uint inx=(uint) info->lastinx, nextflag, key_len;
 
124
  MI_KEYDEF *keyinfo=info->s->keyinfo+inx;
 
125
  uchar *key_buff;
 
126
  double pos;
 
127
 
 
128
  DBUG_ENTER("_mi_record_pos");
 
129
  DBUG_PRINT("enter",("search_flag: %d",search_flag));
 
130
  DBUG_ASSERT(keypart_map);
 
131
 
 
132
  key_buff=info->lastkey+info->s->base.max_key_length;
 
133
  key_len=_mi_pack_key(info,inx,key_buff,(uchar*) key, keypart_map,
 
134
                       (HA_KEYSEG**) 0);
 
135
  DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,
 
136
                                    (uchar*) key_buff,key_len););
 
137
  nextflag=myisam_read_vec[search_flag];
 
138
  if (!(nextflag & (SEARCH_FIND | SEARCH_NO_FIND | SEARCH_LAST)))
 
139
    key_len=USE_WHOLE_KEY;
 
140
 
 
141
  /*
 
142
    my_handler.c:ha_compare_text() has a flag 'skip_end_space'.
 
143
    This is set in my_handler.c:ha_key_cmp() in dependence on the
 
144
    compare flags 'nextflag' and the column type.
 
145
 
 
146
    TEXT columns are of type HA_KEYTYPE_VARTEXT. In this case the
 
147
    condition is skip_end_space= ((nextflag & (SEARCH_FIND |
 
148
    SEARCH_UPDATE)) == SEARCH_FIND).
 
149
 
 
150
    SEARCH_FIND is used for an exact key search. The combination
 
151
    SEARCH_FIND | SEARCH_UPDATE is used in write/update/delete
 
152
    operations with a comment like "Not real duplicates", whatever this
 
153
    means. From the condition above we can see that 'skip_end_space' is
 
154
    always false for these operations. The result is that trailing space
 
155
    counts in key comparison and hence, emtpy strings ('', string length
 
156
    zero, but not NULL) compare less that strings starting with control
 
157
    characters and these in turn compare less than strings starting with
 
158
    blanks.
 
159
 
 
160
    When estimating the number of records in a key range, we request an
 
161
    exact search for the minimum key. This translates into a plain
 
162
    SEARCH_FIND flag. Using this alone would lead to a 'skip_end_space'
 
163
    compare. Empty strings would be expected above control characters.
 
164
    Their keys would not be found because they are located below control
 
165
    characters.
 
166
 
 
167
    This is the reason that we add the SEARCH_UPDATE flag here. It makes
 
168
    the key estimation compare in the same way like key write operations
 
169
    do. Olny so we will find the keys where they have been inserted.
 
170
 
 
171
    Adding the flag unconditionally does not hurt as it is used in the
 
172
    above mentioned condition only. So it can safely be used together
 
173
    with other flags.
 
174
  */
 
175
  pos=_mi_search_pos(info,keyinfo,key_buff,key_len,
 
176
                     nextflag | SEARCH_SAVE_BUFF | SEARCH_UPDATE,
 
177
                     info->s->state.key_root[inx]);
 
178
  if (pos >= 0.0)
 
179
  {
 
180
    DBUG_PRINT("exit",("pos: %ld",(ulong) (pos*info->state->records)));
 
181
    DBUG_RETURN((ulong) (pos*info->state->records+0.5));
 
182
  }
 
183
  DBUG_RETURN(HA_POS_ERROR);
 
184
}
 
185
 
 
186
 
 
187
        /* This is a modified version of _mi_search */
 
188
        /* Returns offset for key in indextable (decimal 0.0 <= x <= 1.0) */
 
189
 
 
190
static double _mi_search_pos(register MI_INFO *info,
 
191
                             register MI_KEYDEF *keyinfo,
 
192
                             uchar *key, uint key_len, uint nextflag,
 
193
                             register my_off_t pos)
 
194
{
 
195
  int flag;
 
196
  uint nod_flag,keynr,max_keynr;
 
197
  my_bool after_key;
 
198
  uchar *keypos,*buff;
 
199
  double offset;
 
200
  DBUG_ENTER("_mi_search_pos");
 
201
  LINT_INIT(max_keynr);
 
202
 
 
203
  if (pos == HA_OFFSET_ERROR)
 
204
    DBUG_RETURN(0.5);
 
205
 
 
206
  if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,1)))
 
207
    goto err;
 
208
  flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
 
209
                              &keypos,info->lastkey, &after_key);
 
210
  nod_flag=mi_test_if_nod(buff);
 
211
  keynr=_mi_keynr(info,keyinfo,buff,keypos,&max_keynr);
 
212
 
 
213
  if (flag)
 
214
  {
 
215
    if (flag == MI_FOUND_WRONG_KEY)
 
216
      DBUG_RETURN(-1);                          /* error */
 
217
    /*
 
218
      Didn't found match. keypos points at next (bigger) key
 
219
      Try to find a smaller, better matching key.
 
220
      Matches keynr + [0-1]
 
221
    */
 
222
    if (flag > 0 && ! nod_flag)
 
223
      offset= 1.0;
 
224
    else if ((offset=_mi_search_pos(info,keyinfo,key,key_len,nextflag,
 
225
                                    _mi_kpos(nod_flag,keypos))) < 0)
 
226
      DBUG_RETURN(offset);
 
227
  }
 
228
  else
 
229
  {
 
230
    /*
 
231
      Found match. Keypos points at the start of the found key
 
232
      Matches keynr+1
 
233
    */
 
234
    offset=1.0;                                 /* Matches keynr+1 */
 
235
    if ((nextflag & SEARCH_FIND) && nod_flag &&
 
236
        ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
 
237
         key_len != USE_WHOLE_KEY))
 
238
    {
 
239
      /*
 
240
        There may be identical keys in the tree. Try to match on of those.
 
241
        Matches keynr + [0-1]
 
242
      */
 
243
      if ((offset=_mi_search_pos(info,keyinfo,key,key_len,SEARCH_FIND,
 
244
                                 _mi_kpos(nod_flag,keypos))) < 0)
 
245
        DBUG_RETURN(offset);                    /* Read error */
 
246
    }
 
247
  }
 
248
  DBUG_PRINT("info",("keynr: %d  offset: %g  max_keynr: %d  nod: %d  flag: %d",
 
249
                     keynr,offset,max_keynr,nod_flag,flag));
 
250
  DBUG_RETURN((keynr+offset)/(max_keynr+1));
 
251
err:
 
252
  DBUG_PRINT("exit",("Error: %d",my_errno));
 
253
  DBUG_RETURN (-1.0);
 
254
}
 
255
 
 
256
 
 
257
        /* Get keynummer of current key and max number of keys in nod */
 
258
 
 
259
static uint _mi_keynr(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
 
260
                      uchar *keypos, uint *ret_max_key)
 
261
{
 
262
  uint nod_flag,keynr,max_key;
 
263
  uchar t_buff[MI_MAX_KEY_BUFF],*end;
 
264
 
 
265
  end= page+mi_getint(page);
 
266
  nod_flag=mi_test_if_nod(page);
 
267
  page+=2+nod_flag;
 
268
 
 
269
  if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
 
270
  {
 
271
    *ret_max_key= (uint) (end-page)/(keyinfo->keylength+nod_flag);
 
272
    return (uint) (keypos-page)/(keyinfo->keylength+nod_flag);
 
273
  }
 
274
 
 
275
  max_key=keynr=0;
 
276
  t_buff[0]=0;                                  /* Safety */
 
277
  while (page < end)
 
278
  {
 
279
    if (!(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff))
 
280
      return 0;                                 /* Error */
 
281
    max_key++;
 
282
    if (page == keypos)
 
283
      keynr=max_key;
 
284
  }
 
285
  *ret_max_key=max_key;
 
286
  return(keynr);
 
287
}