~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/myisam/mi_range.c

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
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= 0;
 
197
  my_bool after_key;
 
198
  uchar *keypos,*buff;
 
199
  double offset;
 
200
  DBUG_ENTER("_mi_search_pos");
 
201
 
 
202
  if (pos == HA_OFFSET_ERROR)
 
203
    DBUG_RETURN(0.5);
 
204
 
 
205
  if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,1)))
 
206
    goto err;
 
207
  flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
 
208
                              &keypos,info->lastkey, &after_key);
 
209
  nod_flag=mi_test_if_nod(buff);
 
210
  keynr=_mi_keynr(info,keyinfo,buff,keypos,&max_keynr);
 
211
 
 
212
  if (flag)
 
213
  {
 
214
    if (flag == MI_FOUND_WRONG_KEY)
 
215
      DBUG_RETURN(-1);                          /* error */
 
216
    /*
 
217
      Didn't found match. keypos points at next (bigger) key
 
218
      Try to find a smaller, better matching key.
 
219
      Matches keynr + [0-1]
 
220
    */
 
221
    if (flag > 0 && ! nod_flag)
 
222
      offset= 1.0;
 
223
    else if ((offset=_mi_search_pos(info,keyinfo,key,key_len,nextflag,
 
224
                                    _mi_kpos(nod_flag,keypos))) < 0)
 
225
      DBUG_RETURN(offset);
 
226
  }
 
227
  else
 
228
  {
 
229
    /*
 
230
      Found match. Keypos points at the start of the found key
 
231
      Matches keynr+1
 
232
    */
 
233
    offset=1.0;                                 /* Matches keynr+1 */
 
234
    if ((nextflag & SEARCH_FIND) && nod_flag &&
 
235
        ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
 
236
         key_len != USE_WHOLE_KEY))
 
237
    {
 
238
      /*
 
239
        There may be identical keys in the tree. Try to match on of those.
 
240
        Matches keynr + [0-1]
 
241
      */
 
242
      if ((offset=_mi_search_pos(info,keyinfo,key,key_len,SEARCH_FIND,
 
243
                                 _mi_kpos(nod_flag,keypos))) < 0)
 
244
        DBUG_RETURN(offset);                    /* Read error */
 
245
    }
 
246
  }
 
247
  DBUG_PRINT("info",("keynr: %d  offset: %g  max_keynr: %d  nod: %d  flag: %d",
 
248
                     keynr,offset,max_keynr,nod_flag,flag));
 
249
  DBUG_RETURN((keynr+offset)/(max_keynr+1));
 
250
err:
 
251
  DBUG_PRINT("exit",("Error: %d",my_errno));
 
252
  DBUG_RETURN (-1.0);
 
253
}
 
254
 
 
255
 
 
256
        /* Get keynummer of current key and max number of keys in nod */
 
257
 
 
258
static uint _mi_keynr(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
 
259
                      uchar *keypos, uint *ret_max_key)
 
260
{
 
261
  uint nod_flag,keynr,max_key;
 
262
  uchar t_buff[MI_MAX_KEY_BUFF],*end;
 
263
 
 
264
  end= page+mi_getint(page);
 
265
  nod_flag=mi_test_if_nod(page);
 
266
  page+=2+nod_flag;
 
267
 
 
268
  if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
 
269
  {
 
270
    *ret_max_key= (uint) (end-page)/(keyinfo->keylength+nod_flag);
 
271
    return (uint) (keypos-page)/(keyinfo->keylength+nod_flag);
 
272
  }
 
273
 
 
274
  max_key=keynr=0;
 
275
  t_buff[0]=0;                                  /* Safety */
 
276
  while (page < end)
 
277
  {
 
278
    if (!(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff))
 
279
      return 0;                                 /* Error */
 
280
    max_key++;
 
281
    if (page == keypos)
 
282
      keynr=max_key;
 
283
  }
 
284
  *ret_max_key=max_key;
 
285
  return(keynr);
 
286
}