Percona Server moved to https://jira.percona.com/projects/PS

Merge lp:~tsarev/percona-server/19957 into lp:percona-server/rnt-5.1

  1. 19957
  2. Merge into rnt-5.1
Proposed by Oleg Tsarev
Status: Merged
Approved by: Oleg Tsarev
Approved revision: no longer in the source branch.
Merged at revision: 208
Proposed branch: lp:~tsarev/percona-server/19957
Merge into: lp:percona-server/rnt-5.1
Prerequisite: lp:~tsarev/percona-server/rnt-5.1_fix_bug_911237
Diff against target: 745 lines (+733/-0)
2 files modified
patches/bug63320.patch (+732/-0)
patches/series (+1/-0)
To merge this branch: bzr merge lp:~tsarev/percona-server/19957
Reviewer Review Type Date Requested Status
Laurynas Biveinis (community) Approve
Oleg Tsarev (community) Needs Resubmitting
Review via email: mp+87362@code.launchpad.net

This proposal supersedes a proposal from 2012-01-02.

Description of the change

Jenkins: http://jenkins.percona.com/view/Percona%20Server%205.1/job/percona-server-5.1-param/224/

Return back Percona's "innodb_stats_method=nulls_ignored" algorithm.

Related Launchpad bug #892405
Related MySQL bug http://bugs.mysql.com/bug.php?id=63320

I added new value "nulls_ignored_exact" for variable innodb_stats_method.

Current upsteam "nulls_ignored" algorithm calculate not_null values on every estimated (random) page, and after that try to approximates total value count.
Unfortunately, this algorithm works incorrectly on mostly null indexes (see MySQL Bug #63320).

Percona'a algorithm excludes from estimation pages with nulls, calculates the count of different values and approximates total value count.
This algorithm works correctly on mostly null indexes, but has limitation - it works correctly just on one-column-key indexes. On compound-keys algorithm can works incorrectly (I didn't test this).
Unfortunately, I can't imagine now how to discard this limitation.

To post a comment you must log in.
Revision history for this message
Laurynas Biveinis (laurynas-biveinis) wrote :

If upstream analysis is correct, then this patch will be short-lived.

When you say "return back percona algorithm", do you mean that there was an old implementation? Can you give branch/revno for it?

review: Needs Information
Revision history for this message
Oleg Tsarev (tsarev) wrote :

Laurynas,

1) Upstream bug analyze has been received after MP review submit
2) Upstream bug analyze doesn't provide way to fix customer problem _right now_.
3) Upstream bug analyze doesn't provide way to fix customer problem in suitable way (without full scan). From this point of view this fix would be not a short-live.
4) Previous Percona's algorithm has been implemented in patch innodb_stats.patch, and has been removed from Percona-Server after integration of upstream algorithm (this was Percona-Server 5.5.8 and Percona-Server 5.1.56)
Here is Yasufumi commit to lp:percona-server/5.1 with remove of the Percona's algorithm.
------------------------------------------------------------
revno: 208
committer: Yasufumi Kinoshita <kinoyasu@rynex6>
branch nick: 5.1.56-tmp
timestamp: Sat 2011-03-12 00:25:38 +0900
message:
  Yasufumi patches and several are ported to 5.1.56; Note: option innodb_stats_method was removed from innodb_stats.patch, because implemented officially. And, bug733317 should be fixed before release
------------------------------------------------------------

Revision history for this message
Oleg Tsarev (tsarev) wrote :

Information provided, comment just for "resubmit" status

review: Needs Resubmitting
Revision history for this message
Laurynas Biveinis (laurynas-biveinis) wrote :

I don't see how 1) is relevant.

Just to be clear, is this patch just a straightforward port of a previously present feature of Percona Server?

review: Needs Information
Revision history for this message
Oleg Tsarev (tsarev) wrote :

The 1) JFYI.

Yes, this is "a straightforward port of a previously present feature of Percona Server" integrated with current upstream implementation.

Current upstream works as before (nulls_equal, nulls_unequal, nulls_ignored) and previously present feature also works (nulls_ignored_exact).

review: Needs Resubmitting
Revision history for this message
Laurynas Biveinis (laurynas-biveinis) wrote :

LGTM (for RNT branch only)

review: Approve

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1=== added file 'patches/bug63320.patch'
2--- patches/bug63320.patch 1970-01-01 00:00:00 +0000
3+++ patches/bug63320.patch 2012-01-03 14:13:50 +0000
4@@ -0,0 +1,732 @@
5+--- a/mysql-test/include/restart_mysqld.inc
6++++ b/mysql-test/include/restart_mysqld.inc
7+@@ -18,8 +18,13 @@
8+ shutdown_server 10;
9+
10+ # Write file to make mysql-test-run.pl start up the server again
11+---exec echo "restart" > $_expect_file_name
12++if ($restart_mysqld_options) {
13++--exec echo "restart: $restart_mysqld_options" > $_expect_file_name
14++}
15+
16++if (!$restart_mysqld_options) {
17++--exec echo "restart" > $_expect_file_name
18++}
19+ # Turn on reconnect
20+ --enable_reconnect
21+
22+--- /dev/null
23++++ b/mysql-test/r/percona_stats_null.result
24+@@ -0,0 +1,25 @@
25++restart_mysqld_options=--default-storage-engine=myisam --myisam_stats_method=nulls_equal
26++restart_mysqld_options=--default-storage-engine=myisam --myisam_stats_method=nulls_unequal
27++restart_mysqld_options=--default-storage-engine=myisam --myisam_stats_method=nulls_ignored
28++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=1000 --innodb_stats_method=nulls_equal
29++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=1000 --innodb_stats_method=nulls_unequal
30++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=1000 --innodb_stats_method=nulls_ignored_exact
31++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=500 --innodb_stats_method=nulls_equal
32++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=500 --innodb_stats_method=nulls_unequal
33++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=500 --innodb_stats_method=nulls_ignored_exact
34++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=250 --innodb_stats_method=nulls_equal
35++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=250 --innodb_stats_method=nulls_unequal
36++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=250 --innodb_stats_method=nulls_ignored_exact
37++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=100 --innodb_stats_method=nulls_equal
38++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=100 --innodb_stats_method=nulls_unequal
39++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=100 --innodb_stats_method=nulls_ignored_exact
40++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=50 --innodb_stats_method=nulls_equal
41++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=50 --innodb_stats_method=nulls_unequal
42++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=50 --innodb_stats_method=nulls_ignored_exact
43++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=25 --innodb_stats_method=nulls_equal
44++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=25 --innodb_stats_method=nulls_unequal
45++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=25 --innodb_stats_method=nulls_ignored_exact
46++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=10 --innodb_stats_method=nulls_equal
47++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=10 --innodb_stats_method=nulls_unequal
48++restart_mysqld_options=--default-storage-engine=innodb --innodb_stats_on_metadata=0 --innodb_stats_sample_pages=10 --innodb_stats_method=nulls_ignored_exact
49++DROP TABLE t;
50+--- /dev/null
51++++ b/mysql-test/t/percona_stats_null.test
52+@@ -0,0 +1,136 @@
53++--source include/have_innodb.inc
54++
55++--enable_result_log
56++--enable_query_log
57++
58++--let delta_coeff=0.2
59++
60++# engine
61++# 2 - myisam
62++# 1 - innodb
63++# 0 - end
64++--let engine_index=2
65++
66++while ($engine_index)
67++{
68++
69++--let engine=`SELECT CASE $engine_index WHEN 2 THEN 'myisam' WHEN 1 THEN 'innodb' END`
70++
71++--let engine_cmd=`SELECT CONCAT('--default-storage-engine=', '$engine')`
72++
73++--let additional_cmd=`SELECT CASE $engine_index WHEN 2 THEN '' WHEN 1 THEN '--innodb_stats_on_metadata=0' END`
74++
75++# sample_pages_index
76++# 7 - 1000
77++# 6 - 500
78++# 5 - 250
79++# 4 - 100
80++# 3 - 50
81++# 2 - 25
82++# 1 - 10
83++# 0 - end
84++--let sample_pages_index=`SELECT CASE $engine_index WHEN 2 THEN 1 WHEN 1 THEN 7 END`
85++
86++while ($sample_pages_index)
87++{
88++--let sample_pages=`SELECT CASE $sample_pages_index WHEN 7 THEN 1000 WHEN 6 THEN 500 WHEN 5 THEN 250 WHEN 4 THEN 100 WHEN 3 THEN 50 WHEN 2 THEN 25 WHEN 1 THEN 10 END`
89++--let sample_pages_cmd=`SELECT CASE $engine_index WHEN 2 THEN '' WHEN 1 THEN (SELECT CONCAT('--innodb_stats_sample_pages=', $sample_pages)) END`
90++
91++# stats_method_index
92++
93++# 3 - nulls_equal
94++# 2 - nulls_unequal
95++# 1 - nulls_ignored | nulls_ignored_exact
96++# 0 - end
97++--let stats_method_index=3
98++
99++while ($stats_method_index)
100++{
101++--let stats_method=`SELECT CASE $stats_method_index WHEN 3 THEN 'nulls_equal' WHEN 2 THEN 'nulls_unequal' WHEN 1 THEN (CASE $engine_index WHEN 2 THEN 'nulls_ignored' WHEN 1 THEN 'nulls_ignored_exact' END) END`
102++--let stats_method_cmd=`SELECT CONCAT('--', '$engine', '_stats_method=', '$stats_method')`
103++--let expected_not_null=`SELECT CASE $stats_method_index WHEN 3 THEN TRUE WHEN 2 THEN FALSE WHEN 1 THEN TRUE END`
104++--let expected_null=`SELECT CASE $stats_method_index WHEN 3 THEN FALSE WHEN 2 THEN TRUE WHEN 1 THEN FALSE END`
105++
106++--let restart_mysqld_options=$engine_cmd $additional_cmd $sample_pages_cmd $stats_method_cmd
107++--echo restart_mysqld_options=$restart_mysqld_options
108++--source include/restart_mysqld.inc
109++
110++# prepare data
111++
112++--disable_query_log
113++--disable_result_log
114++
115++--disable_warnings
116++DROP TABLE IF EXISTS t;
117++--enable_warnings
118++
119++eval CREATE TABLE `t` (`id` int(11) DEFAULT NULL, KEY `t$id` (`id`)) ENGINE=$engine;
120++
121++# insert 100 null values
122++--let i=100
123++while($i)
124++{
125++ eval INSERT INTO t VALUES();
126++ dec $i;
127++}
128++# insert 6 not null values
129++--let i=6
130++while($i)
131++{
132++eval INSERT INTO t(id) VALUES ($i);
133++dec $i;
134++}
135++
136++# clone to 100000
137++INSERT INTO t SELECT a.* FROM t as a, t as b, t as c LIMIT 99894;
138++
139++ANALYZE TABLE t;
140++
141++--enable_query_log
142++--enable_result_log
143++
144++--let count= `SELECT count(*) FROM t`
145++--let null_count= `SELECT count(*) FROM t WHERE id IS NULL`
146++--let not_null_count=`SELECT count(*) FROM t WHERE id IS NOT NULL`
147++--let cardinality= query_get_value('SHOW INDEXES FROM t', Cardinality, 1)
148++--let delta=`SELECT $count * $delta_coeff`
149++
150++--let cardinality_not_null_low=`SELECT IF($not_null_count < $delta, 0, $not_null_count - $delta)`
151++--let cardinality_not_null_high=`SELECT $not_null_count + $delta`
152++--let cardinality_null_low=`SELECT IF($null_count < $delta, 0, $null_count - $delta)`
153++--let cardinality_null_high=`SELECT $null_count + $delta`
154++
155++--let cardinality_near_not_null=`SELECT ($cardinality_not_null_low <= $cardinality) AND ($cardinality <= $cardinality_not_null_high)`
156++--let cardinality_near_null=`SELECT ($cardinality_null_low <= $cardinality) AND ($cardinality <= $cardinality_null_high)`
157++
158++--let not_null_ok=`SELECT $cardinality_near_not_null = $expected_not_null`
159++--let null_ok=`SELECT $cardinality_near_null = $expected_null`
160++
161++--let ok=`SELECT ($not_null_ok = TRUE) and ($null_ok = TRUE)`
162++#--let ok=1
163++if (!$ok)
164++{
165++--echo Failed with '$restart_mysqld_options'
166++--echo Delta is $delta_coeff
167++--echo Engine is $engine
168++--echo Sample pages is $sample_pages
169++--echo Count is $count
170++--echo Not null count is $not_null_count
171++--echo Null count is $null_count
172++--echo Cardinality is $cardinality
173++--echo Expected range of not null $cardinality_not_null_low...$cardinality_not_null_high
174++--echo Expected range of null $cardinality_null_low...$cardinality_null_high
175++--echo Expected near not null is $expected_not_null
176++--echo Expected near null is $expected_null
177++}
178++
179++ dec $stats_method_index;
180++}
181++
182++ dec $sample_pages_index;
183++}
184++
185++ dec $engine_index;
186++}
187++
188++DROP TABLE t;
189+--- a/storage/innodb_plugin/btr/btr0cur.c
190++++ b/storage/innodb_plugin/btr/btr0cur.c
191+@@ -108,8 +108,8 @@
192+ @param ext_size external stored data size
193+ @param not_empty table not empty
194+ @return estimated table wide stats from sampled value */
195+-#define BTR_TABLE_STATS_FROM_SAMPLE(value, index, sample, ext_size, not_empty)\
196+- (((value) * (ib_int64_t) index->stat_n_leaf_pages \
197++#define BTR_TABLE_STATS_FROM_SAMPLE(value, effective_pages, sample, ext_size, not_empty) \
198++ (((value) * (ib_int64_t) effective_pages \
199+ + (sample) - 1 + (ext_size) + (not_empty)) / ((sample) + (ext_size)))
200+
201+ /* @} */
202+@@ -973,6 +973,108 @@
203+ }
204+ }
205+
206++
207++/**********************************************************************//**
208++Positions a cursor at a randomly chosen position within a B-tree
209++after the given path
210++@return TRUE if the position is at the first page, and cursor must point
211++ the first record for used by the caller.*/
212++UNIV_INTERN
213++ibool
214++btr_cur_open_at_rnd_pos_after_path(
215++/*====================*/
216++ dict_index_t* index, /*!< in: index */
217++ ulint latch_mode, /*!< in: BTR_SEARCH_LEAF, ... */
218++ btr_path_t* first_rec_path,
219++ btr_cur_t* cursor, /*!< in/out: B-tree cursor */
220++ mtr_t* mtr) /*!< in: mtr */
221++{
222++ page_cur_t* page_cursor;
223++ btr_path_t* slot;
224++ ibool is_first_rec = TRUE;
225++ ulint page_no;
226++ ulint space;
227++ ulint zip_size;
228++ ulint height;
229++ rec_t* node_ptr;
230++ mem_heap_t* heap = NULL;
231++ ulint offsets_[REC_OFFS_NORMAL_SIZE];
232++ ulint* offsets = offsets_;
233++ rec_offs_init(offsets_);
234++
235++ if (latch_mode == BTR_MODIFY_TREE) {
236++ mtr_x_lock(dict_index_get_lock(index), mtr);
237++ } else {
238++ mtr_s_lock(dict_index_get_lock(index), mtr);
239++ }
240++
241++ page_cursor = btr_cur_get_page_cur(cursor);
242++ cursor->index = index;
243++
244++ space = dict_index_get_space(index);
245++ zip_size = dict_table_zip_size(index->table);
246++ page_no = dict_index_get_page(index);
247++
248++ height = ULINT_UNDEFINED;
249++ slot = first_rec_path;
250++
251++ for (;;) {
252++ buf_block_t* block;
253++ page_t* page;
254++
255++ block = buf_page_get_gen(space, zip_size, page_no,
256++ RW_NO_LATCH, NULL, BUF_GET,
257++ __FILE__, __LINE__, mtr);
258++ page = buf_block_get_frame(block);
259++ ut_ad(0 == ut_dulint_cmp(index->id,
260++ btr_page_get_index_id(page)));
261++
262++ if (height == ULINT_UNDEFINED) {
263++ /* We are in the root node */
264++
265++ height = btr_page_get_level(page, mtr);
266++ }
267++
268++ if (height == 0) {
269++ btr_cur_latch_leaves(page, space, zip_size, page_no,
270++ latch_mode, cursor, mtr);
271++ }
272++
273++ if (is_first_rec && slot->nth_rec != ULINT_UNDEFINED) {
274++ if (height == 0) {
275++ /* must open the first rec */
276++ page_cur_open_on_nth_user_rec(block, page_cursor, slot->nth_rec);
277++ } else {
278++ is_first_rec = page_cur_open_on_rnd_user_rec_after_nth(block,
279++ page_cursor, slot->nth_rec);
280++ }
281++ } else {
282++ is_first_rec = FALSE;
283++ page_cur_open_on_rnd_user_rec(block, page_cursor);
284++ }
285++
286++ if (height == 0) {
287++ break;
288++ }
289++
290++ ut_ad(height > 0);
291++
292++ height--;
293++ slot++;
294++
295++ node_ptr = page_cur_get_rec(page_cursor);
296++ offsets = rec_get_offsets(node_ptr, cursor->index, offsets,
297++ ULINT_UNDEFINED, &heap);
298++ /* Go to the child node */
299++ page_no = btr_node_ptr_get_child_page_no(node_ptr, offsets);
300++ }
301++
302++ if (UNIV_LIKELY_NULL(heap)) {
303++ mem_heap_free(heap);
304++ }
305++
306++ return (is_first_rec);
307++}
308+ /*==================== B-TREE INSERT =========================*/
309+
310+ /*************************************************************//**
311+@@ -3615,6 +3717,154 @@
312+ }
313+
314+ /*******************************************************************//**
315++Estimates the number of pages which have not null value of the key of n_cols.
316++@return estimated number of pages */
317++UNIV_INTERN
318++ulint
319++btr_estimate_n_pages_not_null(
320++/*=========================*/
321++ dict_index_t* index, /*!< in: index */
322++ ulint n_cols, /*!< in: The cols should be not null */
323++ btr_path_t* path1) /*!< in: path1[BTR_PATH_ARRAY_N_SLOTS] */
324++{
325++ dtuple_t* tuple1;
326++ btr_path_t path2[BTR_PATH_ARRAY_N_SLOTS];
327++ btr_cur_t cursor;
328++ btr_path_t* slot1;
329++ btr_path_t* slot2;
330++ ibool diverged;
331++ ibool diverged_lot;
332++ ulint divergence_level;
333++ ulint n_pages;
334++ ulint i;
335++ mtr_t mtr;
336++ mem_heap_t* heap;
337++
338++ heap = mem_heap_create(n_cols * sizeof(dfield_t)
339++ + sizeof(dtuple_t));
340++
341++ /* make tuple1 (NULL,NULL,,,) from n_cols */
342++ tuple1 = dtuple_create(heap, n_cols);
343++ dict_index_copy_types(tuple1, index, n_cols);
344++
345++ for (i = 0; i < n_cols; i++) {
346++ dfield_set_null(dtuple_get_nth_field(tuple1, i));
347++ }
348++
349++ mtr_start(&mtr);
350++
351++ cursor.path_arr = path1;
352++
353++ btr_cur_search_to_nth_level(index, 0, tuple1, PAGE_CUR_G,
354++ BTR_SEARCH_LEAF | BTR_ESTIMATE,
355++ &cursor, 0, __FILE__, __LINE__, &mtr);
356++
357++ mtr_commit(&mtr);
358++
359++
360++
361++ mtr_start(&mtr);
362++
363++ cursor.path_arr = path2;
364++
365++ btr_cur_open_at_index_side(FALSE, index,
366++ BTR_SEARCH_LEAF | BTR_ESTIMATE,
367++ &cursor, &mtr);
368++
369++ mtr_commit(&mtr);
370++
371++ mem_heap_free(heap);
372++
373++ /* We have the path information for the range in path1 and path2 */
374++
375++ n_pages = 1;
376++ diverged = FALSE; /* This becomes true when the path is not
377++ the same any more */
378++ diverged_lot = FALSE; /* This becomes true when the paths are
379++ not the same or adjacent any more */
380++ divergence_level = 1000000; /* This is the level where paths diverged
381++ a lot */
382++ for (i = 0; ; i++) {
383++ ut_ad(i < BTR_PATH_ARRAY_N_SLOTS);
384++
385++ slot1 = path1 + i;
386++ slot2 = path2 + i;
387++
388++ if ((slot1 + 1)->nth_rec == ULINT_UNDEFINED
389++ || (slot2 + 1)->nth_rec == ULINT_UNDEFINED) {
390++
391++ if (i > divergence_level + 1) {
392++ /* In trees whose height is > 1 our algorithm
393++ tends to underestimate: multiply the estimate
394++ by 2: */
395++
396++ n_pages = n_pages * 2;
397++ }
398++
399++ /* Do not estimate the number of rows in the range
400++ to over 1 / 2 of the estimated rows in the whole
401++ table */
402++
403++ if (n_pages > index->stat_n_leaf_pages / 2) {
404++ n_pages = index->stat_n_leaf_pages / 2;
405++
406++ /* If there are just 0 or 1 rows in the table,
407++ then we estimate all rows are in the range */
408++
409++ if (n_pages == 0) {
410++ n_pages = index->stat_n_leaf_pages;
411++ }
412++ }
413++
414++ return(n_pages);
415++ }
416++
417++ if (!diverged && slot1->nth_rec != slot2->nth_rec) {
418++
419++ diverged = TRUE;
420++
421++ if (slot1->nth_rec < slot2->nth_rec) {
422++ n_pages = slot2->nth_rec - slot1->nth_rec;
423++
424++ if (n_pages > 1) {
425++ diverged_lot = TRUE;
426++ divergence_level = i;
427++ }
428++ } else {
429++ /* Maybe the tree has changed between
430++ searches */
431++
432++ return(10);
433++ }
434++
435++ } else if (diverged && !diverged_lot) {
436++
437++ if (slot1->nth_rec < slot1->n_recs
438++ || slot2->nth_rec > 1) {
439++
440++ diverged_lot = TRUE;
441++ divergence_level = i;
442++
443++ n_pages = 0;
444++
445++ if (slot1->nth_rec < slot1->n_recs) {
446++ n_pages += slot1->n_recs
447++ - slot1->nth_rec;
448++ }
449++
450++ if (slot2->nth_rec > 1) {
451++ n_pages += slot2->nth_rec - 1;
452++ }
453++ }
454++ } else if (diverged_lot) {
455++
456++ n_pages = (n_pages * (slot1->n_recs + slot2->n_recs))
457++ / 2;
458++ }
459++ }
460++}
461++
462++/*******************************************************************//**
463+ Estimates the number of different key values in a given index, for
464+ each n-column prefix of the index where n <= dict_index_get_n_unique(index).
465+ The estimates are stored in the array index->stat_n_diff_key_vals.
466+@@ -3646,9 +3896,30 @@
467+ mem_heap_t* heap = NULL;
468+ ulint* offsets_rec = NULL;
469+ ulint* offsets_next_rec = NULL;
470++ btr_path_t first_rec_path[BTR_PATH_ARRAY_N_SLOTS];
471++ ulint effective_pages; /* effective leaf pages */
472+
473+ n_cols = dict_index_get_n_unique(index);
474+
475++ if (srv_innodb_stats_method == SRV_STATS_NULLS_IGNORED_EXACT) {
476++ /* estimate effective pages and path for the first effective record */
477++ /* TODO: make it work also for n_cols > 1. */
478++ effective_pages = btr_estimate_n_pages_not_null(index,
479++ 1 /*k*/,
480++ first_rec_path);
481++
482++ if (!effective_pages) {
483++ for (j = 0; j <= n_cols; j++) {
484++ index->stat_n_diff_key_vals[j] = (ib_int64_t)index->stat_n_leaf_pages;
485++ }
486++ return;
487++ } else if (effective_pages > index->stat_n_leaf_pages) {
488++ effective_pages = index->stat_n_leaf_pages;
489++ }
490++ } else {
491++ effective_pages = index->stat_n_leaf_pages;
492++ }
493++
494+ heap = mem_heap_create((sizeof *n_diff + sizeof *n_not_null)
495+ * (n_cols + 1)
496+ + dict_index_get_n_fields(index)
497+@@ -3668,6 +3939,7 @@
498+ * sizeof *n_not_null);
499+ /* fall through */
500+
501++ case SRV_STATS_NULLS_IGNORED_EXACT:
502+ case SRV_STATS_NULLS_UNEQUAL:
503+ /* for both SRV_STATS_NULLS_IGNORED and SRV_STATS_NULLS_UNEQUAL
504+ case, we will treat NULLs as unequal value */
505+@@ -3684,9 +3956,9 @@
506+
507+ /* It makes no sense to test more pages than are contained
508+ in the index, thus we lower the number if it is too high */
509+- if (srv_stats_sample_pages > index->stat_index_size) {
510+- if (index->stat_index_size > 0) {
511+- n_sample_pages = index->stat_index_size;
512++ if (srv_stats_sample_pages > effective_pages) {
513++ if (effective_pages > 0) {
514++ n_sample_pages = effective_pages;
515+ } else {
516+ n_sample_pages = 1;
517+ }
518+@@ -3697,9 +3969,22 @@
519+ /* We sample some pages in the index to get an estimate */
520+
521+ for (i = 0; i < n_sample_pages; i++) {
522++ ibool is_first_page = TRUE;
523+ mtr_start(&mtr);
524+
525+- btr_cur_open_at_rnd_pos(index, BTR_SEARCH_LEAF, &cursor, &mtr);
526++ if (srv_innodb_stats_method == SRV_STATS_NULLS_IGNORED_EXACT) {
527++ is_first_page =
528++ btr_cur_open_at_rnd_pos_after_path(index,
529++ BTR_SEARCH_LEAF,
530++ first_rec_path,
531++ &cursor,
532++ &mtr);
533++ } else {
534++ btr_cur_open_at_rnd_pos(index,
535++ BTR_SEARCH_LEAF,
536++ &cursor,
537++ &mtr);
538++ }
539+
540+ /* Count the number of different key values for each prefix of
541+ the key on this index page. If the prefix does not determine
542+@@ -3714,7 +3999,14 @@
543+ }
544+ ut_a(page);
545+
546+- rec = page_rec_get_next(page_get_infimum_rec(page));
547++ if (srv_innodb_stats_method == SRV_STATS_NULLS_IGNORED_EXACT &&
548++ is_first_page) {
549++ /* the cursor should be the first record of the page. */
550++ /* Counting should be started from here. */
551++ rec = btr_cur_get_rec(&cursor);
552++ } else {
553++ rec = page_rec_get_next(page_get_infimum_rec(page));
554++ }
555+
556+ if (!page_rec_is_supremum(rec)) {
557+ not_empty_flag = 1;
558+@@ -3810,8 +4102,11 @@
559+ for (j = 0; j <= n_cols; j++) {
560+ index->stat_n_diff_key_vals[j]
561+ = BTR_TABLE_STATS_FROM_SAMPLE(
562+- n_diff[j], index, n_sample_pages,
563+- total_external_size, not_empty_flag);
564++ n_diff[j],
565++ effective_pages,
566++ n_sample_pages,
567++ total_external_size,
568++ not_empty_flag);
569+
570+ /* If the tree is small, smaller than
571+ 10 * n_sample_pages + total_external_size, then
572+@@ -3821,7 +4116,7 @@
573+ different key values, or even more. Let us try to approximate
574+ that: */
575+
576+- add_on = index->stat_n_leaf_pages
577++ add_on = effective_pages
578+ / (10 * (n_sample_pages
579+ + total_external_size));
580+
581+@@ -3838,8 +4133,24 @@
582+ if (n_not_null != NULL && (j < n_cols)) {
583+ index->stat_n_non_null_key_vals[j] =
584+ BTR_TABLE_STATS_FROM_SAMPLE(
585+- n_not_null[j], index, n_sample_pages,
586+- total_external_size, not_empty_flag);
587++ n_not_null[j],
588++ effective_pages,
589++ n_sample_pages,
590++ total_external_size,
591++ not_empty_flag);
592++ }
593++
594++ if (srv_innodb_stats_method == SRV_STATS_NULLS_IGNORED_EXACT) {
595++ /* index->stat_n_diff_key_vals[k] is used for calc
596++ rec_per_key, as
597++ "stats.records / index->stat_n_diff_key_vals[x]".
598++ So it should be adjusted to the value which is based
599++ on whole of the index.
600++ */
601++ index->stat_n_diff_key_vals[j] =
602++ index->stat_n_diff_key_vals[j]
603++ * (ib_int64_t)index->stat_n_leaf_pages
604++ / (ib_int64_t)effective_pages;
605+ }
606+ }
607+
608+--- a/storage/innodb_plugin/include/page0cur.h
609++++ b/storage/innodb_plugin/include/page0cur.h
610+@@ -293,6 +293,22 @@
611+ /*==========================*/
612+ buf_block_t* block, /*!< in: page */
613+ page_cur_t* cursor);/*!< out: page cursor */
614++
615++UNIV_INTERN
616++void
617++page_cur_open_on_nth_user_rec(
618++/*==========================*/
619++ buf_block_t* block, /*!< in: page */
620++ page_cur_t* cursor, /*!< out: page cursor */
621++ ulint nth);
622++
623++UNIV_INTERN
624++ibool
625++page_cur_open_on_rnd_user_rec_after_nth(
626++/*==========================*/
627++ buf_block_t* block, /*!< in: page */
628++ page_cur_t* cursor, /*!< out: page cursor */
629++ ulint nth);
630+ #endif /* !UNIV_HOTBACKUP */
631+ /***********************************************************//**
632+ Parses a log record of a record insert on a page.
633+--- a/storage/innodb_plugin/include/srv0srv.h
634++++ b/storage/innodb_plugin/include/srv0srv.h
635+@@ -425,7 +425,11 @@
636+ for innodb_stats_method */
637+ SRV_STATS_NULLS_UNEQUAL, /* All NULL values are treated as
638+ NOT equal. */
639+- SRV_STATS_NULLS_IGNORED /* NULL values are ignored */
640++ SRV_STATS_NULLS_IGNORED, /* NULL values are ignored */
641++ SRV_STATS_NULLS_IGNORED_EXACT /* NULL values are ignored exact
642++ (direct skip of null pages)
643++ (limited by key with length 1)
644++ */
645+ };
646+
647+ typedef enum srv_stats_method_name_enum srv_stats_method_name_t;
648+--- a/storage/innodb_plugin/page/page0cur.c
649++++ b/storage/innodb_plugin/page/page0cur.c
650+@@ -564,6 +564,76 @@
651+ } while (rnd--);
652+ }
653+
654++
655++UNIV_INTERN
656++void
657++page_cur_open_on_nth_user_rec(
658++/*==========================*/
659++ buf_block_t* block, /*!< in: page */
660++ page_cur_t* cursor, /*!< out: page cursor */
661++ ulint nth)
662++{
663++ ulint n_recs = page_get_n_recs(buf_block_get_frame(block));
664++
665++ page_cur_set_before_first(block, cursor);
666++
667++ if (UNIV_UNLIKELY(n_recs == 0)) {
668++
669++ return;
670++ }
671++
672++ nth--;
673++
674++ if (nth >= n_recs) {
675++ nth = n_recs - 1;
676++ }
677++
678++ do {
679++ page_cur_move_to_next(cursor);
680++ } while (nth--);
681++}
682++
683++
684++UNIV_INTERN
685++ibool
686++page_cur_open_on_rnd_user_rec_after_nth(
687++/*==========================*/
688++ buf_block_t* block, /*!< in: page */
689++ page_cur_t* cursor, /*!< out: page cursor */
690++ ulint nth)
691++{
692++ ulint rnd;
693++ ulint n_recs = page_get_n_recs(buf_block_get_frame(block));
694++ ibool ret;
695++
696++ page_cur_set_before_first(block, cursor);
697++
698++ if (UNIV_UNLIKELY(n_recs == 0)) {
699++
700++ return (FALSE);
701++ }
702++
703++ nth--;
704++
705++ if (nth >= n_recs) {
706++ nth = n_recs - 1;
707++ }
708++
709++ rnd = (ulint) (nth + page_cur_lcg_prng() % (n_recs - nth));
710++
711++ if (rnd == nth) {
712++ ret = TRUE;
713++ } else {
714++ ret = FALSE;
715++ }
716++
717++ do {
718++ page_cur_move_to_next(cursor);
719++ } while (rnd--);
720++
721++ return (ret);
722++}
723++
724+ /***********************************************************//**
725+ Writes the log record of a record insert on a page. */
726+ static
727+--- a/storage/innodb_plugin/handler/ha_innodb.cc
728++++ b/storage/innodb_plugin/handler/ha_innodb.cc
729+@@ -216,6 +216,7 @@
730+ "nulls_equal",
731+ "nulls_unequal",
732+ "nulls_ignored",
733++ "nulls_ignored_exact",
734+ NullS
735+ };
736+
737
738=== modified file 'patches/series'
739--- patches/series 2011-11-17 12:41:18 +0000
740+++ patches/series 2012-01-03 14:13:50 +0000
741@@ -86,3 +86,4 @@
742 bug54127.patch
743 replication_slave_skip_columns.patch
744 mysql-test-rnt.diff
745+bug63320.patch

Subscribers

People subscribed via source and target branches