« back to all changes in this revision
Viewing changes to drizzled/optimizer/range.cc
- browse files at revision 1461.2.3
- compare with another revision
- compare with revision 2165.1.3
- download diff
- download tarball
- view history from revision 1461.2.3
- Committer: mordred
- Date: 2010-04-20 00:04:22 UTC
- mfrom: (1491 bad-staging)
- mto: This revision was merged to the branch mainline in revision 1498.
- Revision ID: mordred@orisndriz09-20100420000422-if6mil1596804mrj
Merged up with build.
- files added:
- plugin/simple_user_policy/policy.h
- files renamed:
- plugin/test_authz/ => plugin/simple_user_policy/
- plugin/test_authz/test_authz.cc => plugin/simple_user_policy/module.cc
- plugin/test_authz/tests/t/basic.disabled => plugin/simple_user_policy/tests/t/basic.test
- files modified:
- client/drizzledump.cc
added
removed
drizzled/optimizer/range.cc
272
272
bool *are_all_covering);
273
273
274
274
static
275
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
276
optimizer::SEL_TREE *tree,
277
double read_time);
278
279
static
280
275
optimizer::TableReadPlan *get_best_disjunct_quick(optimizer::Parameter *param,
281
276
optimizer::SEL_IMERGE *imerge,
282
277
double read_time);
542
537
uint32_t pk;
543
538
param->tmp_covered_fields.setBitmap(0);
544
539
param->fields_bitmap_size= table->s->column_bitmap_size;
545
if (!(tmp= (my_bitmap_map*) alloc_root(param->mem_root,
546
param->fields_bitmap_size)) ||
540
if (!(tmp= (my_bitmap_map*) param->mem_root->alloc_root(param->fields_bitmap_size)) ||
547
541
param->needed_fields.init(tmp, table->s->fields))
542
{
548
543
return 1;
544
}
549
545
550
546
param->needed_fields= *table->read_set;
551
547
bitmap_union(¶m->needed_fields, table->write_set);
686
682
687
683
session->no_errors=1; // Don't warn about NULL
688
684
memory::init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
689
if (!(param.key_parts= (KEY_PART*) alloc_root(&alloc,
690
sizeof(KEY_PART)*
691
head->s->key_parts)) ||
685
if (!(param.key_parts= (KEY_PART*) alloc.alloc_root( sizeof(KEY_PART) * head->s->key_parts)) ||
692
686
fill_used_fields_bitmap(¶m))
693
687
{
694
688
session->no_errors=0;
695
free_root(&alloc,MYF(0)); // Return memory & allocator
689
alloc.free_root(MYF(0)); // Return memory & allocator
690
696
691
return 0; // Can't use range
697
692
}
698
693
key_parts= param.key_parts;
816
811
{
817
812
best_trp= rori_trp;
818
813
best_read_time= best_trp->read_cost;
819
/*
820
Try constructing covering ROR-intersect only if it looks possible
821
and worth doing.
822
*/
823
if (rori_trp->isRowRetrievalNecessary() && can_build_covering &&
824
(rori_trp= get_best_covering_ror_intersect(¶m, tree,
825
best_read_time)))
826
best_trp= rori_trp;
827
814
}
828
815
}
829
816
}
863
850
}
864
851
865
852
free_mem:
866
free_root(&alloc,MYF(0)); // Return memory & allocator
853
alloc.free_root(MYF(0)); // Return memory & allocator
867
854
session->mem_root= param.old_root;
868
855
session->no_errors=0;
869
856
}
965
952
ha_rows roru_total_records;
966
953
double roru_intersect_part= 1.0;
967
954
968
if (! (range_scans= (optimizer::RangeReadPlan**)alloc_root(param->mem_root,
969
sizeof(optimizer::RangeReadPlan*)*
970
n_child_scans)))
955
if (! (range_scans= (optimizer::RangeReadPlan**)param->mem_root->alloc_root(sizeof(optimizer::RangeReadPlan*)* n_child_scans)))
956
{
971
957
return NULL;
958
}
959
972
960
/*
973
961
Collect best 'range' scan for each of disjuncts, and, while doing so,
974
962
analyze possibility of ROR scans. Also calculate some values needed by
1047
1035
param->session->variables.sortbuff_size);
1048
1036
if (param->imerge_cost_buff_size < unique_calc_buff_size)
1049
1037
{
1050
if (!(param->imerge_cost_buff= (uint*)alloc_root(param->mem_root,
1051
unique_calc_buff_size)))
1038
if (!(param->imerge_cost_buff= (uint*)param->mem_root->alloc_root(unique_calc_buff_size)))
1039
{
1052
1040
return NULL;
1041
}
1042
1053
1043
param->imerge_cost_buff_size= unique_calc_buff_size;
1054
1044
}
1055
1045
1078
1068
/* Ok, it is possible to build a ROR-union, try it. */
1079
1069
bool dummy;
1080
1070
if (! (roru_read_plans=
1081
(optimizer::TableReadPlan **) alloc_root(param->mem_root,
1082
sizeof(optimizer::TableReadPlan*)*
1083
n_child_scans)))
1071
(optimizer::TableReadPlan **) param->mem_root->alloc_root(sizeof(optimizer::TableReadPlan*) * n_child_scans)))
1072
{
1084
1073
return imerge_trp;
1074
}
1085
1075
skip_to_ror_scan:
1086
1076
roru_index_costs= 0.0;
1087
1077
roru_total_records= 0;
1221
1211
1222
1212
uint32_t keynr;
1223
1213
1224
if (!(ror_scan= (ROR_SCAN_INFO*)alloc_root(param->mem_root,
1225
sizeof(ROR_SCAN_INFO))))
1214
if (!(ror_scan= (ROR_SCAN_INFO*)param->mem_root->alloc_root(sizeof(ROR_SCAN_INFO))))
1226
1215
return NULL;
1227
1216
1228
1217
ror_scan->idx= idx;
1232
1221
ror_scan->sel_arg= sel_arg;
1233
1222
ror_scan->records= param->table->quick_rows[keynr];
1234
1223
1235
if (!(bitmap_buf= (my_bitmap_map*) alloc_root(param->mem_root,
1236
param->fields_bitmap_size)))
1224
if (!(bitmap_buf= (my_bitmap_map*) param->mem_root->alloc_root(param->fields_bitmap_size)))
1225
{
1237
1226
return NULL;
1227
}
1238
1228
1239
if (ror_scan->covered_fields.init(bitmap_buf,
1240
param->table->s->fields))
1229
if (ror_scan->covered_fields.init(bitmap_buf, param->table->s->fields))
1230
{
1241
1231
return NULL;
1232
}
1242
1233
ror_scan->covered_fields.clearAll();
1243
1234
1244
1235
KEY_PART_INFO *key_part= param->table->key_info[keynr].key_part;
1276
1267
return (val1 < val2)? -1: (val1 == val2)? 0 : 1;
1277
1268
}
1278
1269
1279
/*
1280
Compare two ROR_SCAN_INFO** by
1281
(#covered fields in F desc,
1282
#components asc,
1283
number of first not covered component asc)
1284
1285
SYNOPSIS
1286
cmp_ror_scan_info_covering()
1287
a ptr to first compared value
1288
b ptr to second compared value
1289
1290
RETURN
1291
-1 a < b
1292
0 a = b
1293
1 a > b
1294
*/
1295
1296
static int cmp_ror_scan_info_covering(ROR_SCAN_INFO** a, ROR_SCAN_INFO** b)
1297
{
1298
if ((*a)->used_fields_covered > (*b)->used_fields_covered)
1299
return -1;
1300
if ((*a)->used_fields_covered < (*b)->used_fields_covered)
1301
return 1;
1302
if ((*a)->key_components < (*b)->key_components)
1303
return -1;
1304
if ((*a)->key_components > (*b)->key_components)
1305
return 1;
1306
if ((*a)->first_uncovered_field < (*b)->first_uncovered_field)
1307
return -1;
1308
if ((*a)->first_uncovered_field > (*b)->first_uncovered_field)
1309
return 1;
1310
return 0;
1311
}
1312
1313
1270
1314
1271
/* Auxiliary structure for incremental ROR-intersection creation */
1315
1272
typedef struct
1348
1305
{
1349
1306
ROR_INTERSECT_INFO *info;
1350
1307
my_bitmap_map* buf;
1351
if (!(info= (ROR_INTERSECT_INFO*)alloc_root(param->mem_root,
1352
sizeof(ROR_INTERSECT_INFO))))
1308
if (!(info= (ROR_INTERSECT_INFO*)param->mem_root->alloc_root(sizeof(ROR_INTERSECT_INFO))))
1353
1309
return NULL;
1354
1310
info->param= param;
1355
if (!(buf= (my_bitmap_map*) alloc_root(param->mem_root,
1356
param->fields_bitmap_size)))
1311
if (!(buf= (my_bitmap_map*) param->mem_root->alloc_root(param->fields_bitmap_size)))
1357
1312
return NULL;
1358
1313
if (info->covered_fields.init(buf, param->table->s->fields))
1359
1314
return NULL;
1711
1666
uint32_t cpk_no= 0;
1712
1667
bool cpk_scan_used= false;
1713
1668
1714
if (! (tree->ror_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
1715
sizeof(ROR_SCAN_INFO*)*
1716
param->keys)))
1669
if (! (tree->ror_scans= (ROR_SCAN_INFO**)param->mem_root->alloc_root(sizeof(ROR_SCAN_INFO*)* param->keys)))
1670
{
1717
1671
return NULL;
1672
}
1718
1673
cpk_no= ((param->table->cursor->primary_key_is_clustered()) ?
1719
1674
param->table->s->primary_key : MAX_KEY);
1720
1675
1745
1700
1746
1701
ROR_SCAN_INFO **intersect_scans= NULL; /* ROR scans used in index intersection */
1747
1702
ROR_SCAN_INFO **intersect_scans_end= NULL;
1748
if (! (intersect_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
1749
sizeof(ROR_SCAN_INFO*)*
1750
tree->n_ror_scans)))
1703
if (! (intersect_scans= (ROR_SCAN_INFO**)param->mem_root->alloc_root(sizeof(ROR_SCAN_INFO*) * tree->n_ror_scans)))
1751
1704
return NULL;
1752
1705
intersect_scans_end= intersect_scans;
1753
1706
1830
1783
1831
1784
1832
1785
/*
1833
Get best covering ROR-intersection.
1834
SYNOPSIS
1835
get_best_covering_ror_intersect()
1836
param Parameter from test_quick_select function.
1837
tree optimizer::SEL_TREE with sets of intervals for different keys.
1838
read_time Don't return table read plans with cost > read_time.
1839
1840
RETURN
1841
Best covering ROR-intersection plan
1842
NULL if no plan found.
1843
1844
NOTES
1845
get_best_ror_intersect must be called for a tree before calling this
1846
function for it.
1847
This function invalidates tree->ror_scans member values.
1848
1849
The following approximate algorithm is used:
1850
I=set of all covering indexes
1851
F=set of all fields to cover
1852
S={}
1853
1854
do
1855
{
1856
Order I by (#covered fields in F desc,
1857
#components asc,
1858
number of first not covered component asc);
1859
F=F-covered by first(I);
1860
S=S+first(I);
1861
I=I-first(I);
1862
} while F is not empty.
1863
*/
1864
1865
static
1866
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
1867
optimizer::SEL_TREE *tree,
1868
double read_time)
1869
{
1870
ROR_SCAN_INFO **ror_scan_mark;
1871
ROR_SCAN_INFO **ror_scans_end= tree->ror_scans_end;
1872
1873
for (ROR_SCAN_INFO **scan= tree->ror_scans; scan != ror_scans_end; ++scan)
1874
(*scan)->key_components=
1875
param->table->key_info[(*scan)->keynr].key_parts;
1876
1877
/*
1878
Run covering-ROR-search algorithm.
1879
Assume set I is [ror_scan .. ror_scans_end)
1880
*/
1881
1882
/*I=set of all covering indexes */
1883
ror_scan_mark= tree->ror_scans;
1884
1885
MyBitmap *covered_fields= ¶m->tmp_covered_fields;
1886
if (! covered_fields->getBitmap())
1887
{
1888
my_bitmap_map *tmp_bitmap= (my_bitmap_map*)alloc_root(param->mem_root,
1889
param->fields_bitmap_size);
1890
covered_fields->setBitmap(tmp_bitmap);
1891
}
1892
if (! covered_fields->getBitmap() ||
1893
covered_fields->init(covered_fields->getBitmap(),
1894
param->table->s->fields))
1895
return 0;
1896
covered_fields->clearAll();
1897
1898
double total_cost= 0.0f;
1899
ha_rows records=0;
1900
bool all_covered;
1901
1902
do
1903
{
1904
/*
1905
Update changed sorting info:
1906
#covered fields,
1907
number of first not covered component
1908
Calculate and save these values for each of remaining scans.
1909
*/
1910
for (ROR_SCAN_INFO **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
1911
{
1912
bitmap_subtract(&(*scan)->covered_fields, covered_fields);
1913
(*scan)->used_fields_covered=
1914
(*scan)->covered_fields.getBitsSet();
1915
(*scan)->first_uncovered_field=
1916
(*scan)->covered_fields.getFirst();
1917
}
1918
1919
internal::my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark,
1920
sizeof(ROR_SCAN_INFO*),
1921
(qsort_cmp)cmp_ror_scan_info_covering);
1922
1923
/* I=I-first(I) */
1924
total_cost += (*ror_scan_mark)->index_read_cost;
1925
records += (*ror_scan_mark)->records;
1926
if (total_cost > read_time)
1927
return NULL;
1928
/* F=F-covered by first(I) */
1929
bitmap_union(covered_fields, &(*ror_scan_mark)->covered_fields);
1930
all_covered= bitmap_is_subset(¶m->needed_fields, covered_fields);
1931
} while ((++ror_scan_mark < ror_scans_end) && !all_covered);
1932
1933
if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
1934
return NULL;
1935
1936
/*
1937
Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
1938
cost total_cost.
1939
*/
1940
/* Add priority queue use cost. */
1941
total_cost += rows2double(records)*
1942
log((double)(ror_scan_mark - tree->ror_scans)) /
1943
(TIME_FOR_COMPARE_ROWID * M_LN2);
1944
1945
if (total_cost > read_time)
1946
return NULL;
1947
1948
optimizer::RorIntersectReadPlan *trp= NULL;
1949
if (! (trp= new (param->mem_root) optimizer::RorIntersectReadPlan))
1950
{
1951
return trp;
1952
}
1953
1954
uint32_t best_num= (ror_scan_mark - tree->ror_scans);
1955
trp->ror_range_scans.assign(tree->ror_scans, tree->ror_scans + best_num);
1956
trp->setRowRetrievalNecessary(true);
1957
trp->read_cost= total_cost;
1958
trp->records= records;
1959
trp->cpk_scan= NULL;
1960
set_if_smaller(param->table->quick_condition_rows, records);
1961
1962
return(trp);
1963
}
1964
1965
1966
/*
1967
1786
Get best "range" table read plan for given optimizer::SEL_TREE, also update some info
1968
1787
1969
1788
SYNOPSIS
2919
2738
{
2920
2739
if (unlikely(length < field_length))
2921
2740
{
2922
/*
2923
This can only happen in a table created with UNIREG where one key
2924
overlaps many fields
2925
*/
2926
length= field_length;
2741
/*
2742
This can only happen in a table created with UNIREG where one key
2743
overlaps many fields
2744
*/
2745
length= field_length;
2927
2746
}
2928
2747
else
2929
field_length= length;
2748
field_length= length;
2930
2749
}
2931
2750
length+=offset;
2932
if (!(min_str= (unsigned char*) alloc_root(alloc, length*2)))
2751
if (!(min_str= (unsigned char*) alloc->alloc_root(length*2)))
2752
{
2933
2753
goto end;
2754
}
2934
2755
2935
2756
max_str=min_str+length;
2936
2757
if (maybe_null)
3149
2970
tree= &optimizer::null_element; // cmp with NULL is never true
3150
2971
goto end;
3151
2972
}
3152
str= (unsigned char*) alloc_root(alloc, key_part->store_length+1);
2973
str= (unsigned char*) alloc->alloc_root(key_part->store_length+1);
3153
2974
if (!str)
3154
2975
goto end;
3155
2976
if (maybe_null)
4021
3842
{
4022
3843
quick->mrr_flags= mrr_flags;
4023
3844
quick->mrr_buf_size= mrr_buf_size;
4024
quick->key_parts=(KEY_PART*)
4025
memdup_root(parent_alloc? parent_alloc : &quick->alloc,
4026
(char*) param->key[idx],
4027
sizeof(KEY_PART)*
4028
param->table->key_info[param->real_keynr[idx]].key_parts);
3845
if (parent_alloc)
3846
{
3847
quick->key_parts=(KEY_PART*)
3848
parent_alloc->memdup_root( (char*) param->key[idx], sizeof(KEY_PART)* param->table->key_info[param->real_keynr[idx]].key_parts);
3849
}
3850
else
3851
{
3852
quick->key_parts=(KEY_PART*)
3853
quick->alloc.memdup_root((char*) param->key[idx], sizeof(KEY_PART)* param->table->key_info[param->real_keynr[idx]].key_parts);
3854
}
4029
3855
}
4030
3856
}
4031
3857
return quick;
4290
4116
4291
4117
4292
4118
if (!(quick->key_parts=key_part=(KEY_PART *)
4293
alloc_root(&quick->alloc,sizeof(KEY_PART)*ref->key_parts)))
4119
quick->alloc.alloc_root(sizeof(KEY_PART)*ref->key_parts)))
4294
4120
goto err;
4295
4121
4296
4122
for (part=0 ; part < ref->key_parts ;part++,key_part++)
Loggerhead is a web-based interface for Breezy
Version: 2.0.1