开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数据库系统 > MySQL数据库 > 查看源码
pars0opt.c
资源名称：mysql-4.1.16-win-src.zip　[点击查看]
上传用户：romrleung
上传日期：2022-05-23
资源大小：18897k
文件大小：31k
源码类别：

MySQL数据库

开发平台：

Visual C++

pars0opt.c：源码内容
  1. /******************************************************
  2. Simple SQL optimizer
  4. (c) 1997 Innobase Oy
  6. Created 12/21/1997 Heikki Tuuri
  7. *******************************************************/
  9. #include "pars0opt.h"
  11. #ifdef UNIV_NONINL
  12. #include "pars0opt.ic"
  13. #endif
  15. #include "row0sel.h"
  16. #include "row0ins.h"
  17. #include "row0upd.h"
  18. #include "dict0dict.h"
  19. #include "dict0mem.h"
  20. #include "que0que.h"
  21. #include "pars0grm.h"
  22. #include "pars0pars.h"
  23. #include "lock0lock.h"
  25. #define OPT_EQUAL 1 /* comparison by = */
  26. #define OPT_COMPARISON 2 /* comparison by <, >, <=, or >= */
  28. #define OPT_NOT_COND 1
  29. #define OPT_END_COND 2
  30. #define OPT_TEST_COND 3
  31. #define OPT_SCROLL_COND 4
  34. /***********************************************************************
  35. Inverts a comparison operator. */
  36. static
  37. int
  38. opt_invert_cmp_op(
  39. /*==============*/
  40. /* out: the equivalent operator when the order of
  41. the arguments is switched */
  42. int op) /* in: operator */
  43. {
  44. if (op == '<') {
  45. return('>');
  46. } else if (op == '>') {
  47. return('<');
  48. } else if (op == '=') {
  49. return('=');
  50. } else if (op == PARS_LE_TOKEN) {
  51. return(PARS_GE_TOKEN);
  52. } else if (op == PARS_GE_TOKEN) {
  53. return(PARS_LE_TOKEN);
  54. } else {
  55. ut_error;
  56. }
  58. return(0);
  59. }
  61. /***********************************************************************
  62. Checks if the value of an expression can be calculated BEFORE the nth table
  63. in a join is accessed. If this is the case, it can possibly be used in an
  64. index search for the nth table. */
  65. static
  66. ibool
  67. opt_check_exp_determined_before(
  68. /*============================*/
  69. /* out: TRUE if already determined */
  70. que_node_t* exp, /* in: expression */
  71. sel_node_t* sel_node, /* in: select node */
  72. ulint nth_table) /* in: nth table will be accessed */
  73. {
  74. func_node_t* func_node;
  75. sym_node_t* sym_node;
  76. dict_table_t* table;
  77. que_node_t* arg;
  78. ulint i;
  80. ut_ad(exp && sel_node);
  82. if (que_node_get_type(exp) == QUE_NODE_FUNC) {
  83. func_node = exp;
  85. arg = func_node->args;
  87. while (arg) {
  88. if (!opt_check_exp_determined_before(arg, sel_node,
  89. nth_table)) {
  90. return(FALSE);
  91. }
  93. arg = que_node_get_next(arg);
  94. }
  96. return(TRUE);
  97. }
  99. ut_a(que_node_get_type(exp) == QUE_NODE_SYMBOL);
  101. sym_node = exp;
  103. if (sym_node->token_type != SYM_COLUMN) {
  105. return(TRUE);
  106. }
  108. for (i = 0; i < nth_table; i++) {
  110. table = sel_node_get_nth_plan(sel_node, i)->table;
  112. if (sym_node->table == table) {
  114. return(TRUE);
  115. }
  116. }
  118. return(FALSE);
  119. }
  121. /***********************************************************************
  122. Looks in a comparison condition if a column value is already restricted by
  123. it BEFORE the nth table is accessed. */
  124. static
  125. que_node_t*
  126. opt_look_for_col_in_comparison_before(
  127. /*==================================*/
  128. /* out: expression restricting the
  129. value of the column, or NULL if not
  130. known */
  131. ulint cmp_type, /* in: OPT_EQUAL, OPT_COMPARISON */
  132. ulint col_no, /* in: column number */
  133. func_node_t* search_cond, /* in: comparison condition */
  134. sel_node_t* sel_node, /* in: select node */
  135. ulint nth_table, /* in: nth table in a join (a query
  136. from a single table is considered a
  137. join of 1 table) */
  138. ulint* op) /* out: comparison operator ('=',
  139. PARS_GE_TOKEN, ... ); this is inverted
  140. if the column appears on the right
  141. side */
  142. {
  143. sym_node_t* sym_node;
  144. dict_table_t* table;
  145. que_node_t* exp;
  146. que_node_t* arg;
  148. ut_ad(search_cond);
  150. ut_a((search_cond->func == '<')
  151.      || (search_cond->func == '>')
  152.      || (search_cond->func == '=')
  153.      || (search_cond->func == PARS_GE_TOKEN)
  154.      || (search_cond->func == PARS_LE_TOKEN));
  156. table = sel_node_get_nth_plan(sel_node, nth_table)->table;
  158. if ((cmp_type == OPT_EQUAL) && (search_cond->func != '=')) {
  160. return(NULL);
  162. } else if ((cmp_type == OPT_COMPARISON)
  163. && (search_cond->func != '<')
  164. && (search_cond->func != '>')
  165. && (search_cond->func != PARS_GE_TOKEN)
  166. && (search_cond->func != PARS_LE_TOKEN)) {
  168. return(NULL);
  169. }
  171. arg = search_cond->args;
  173. if (que_node_get_type(arg) == QUE_NODE_SYMBOL) {
  174. sym_node = arg;
  176. if ((sym_node->token_type == SYM_COLUMN)
  177. && (sym_node->table == table)
  178. && (sym_node->col_no == col_no)) {
  180. /* sym_node contains the desired column id */
  182. /* Check if the expression on the right side of the
  183. operator is already determined */
  185. exp = que_node_get_next(arg);
  187. if (opt_check_exp_determined_before(exp, sel_node,
  188. nth_table)) {
  189. *op = search_cond->func;
  191. return(exp);
  192. }
  193. }
  194.      }
  196.      exp = search_cond->args;
  197.         arg = que_node_get_next(arg);
  199. if (que_node_get_type(arg) == QUE_NODE_SYMBOL) {
  200. sym_node = arg;
  202. if ((sym_node->token_type == SYM_COLUMN)
  203. && (sym_node->table == table)
  204. && (sym_node->col_no == col_no)) {
  206. if (opt_check_exp_determined_before(exp, sel_node,
  207. nth_table)) {
  208. *op = opt_invert_cmp_op(search_cond->func);
  210. return(exp);
  211. }
  212. }
  213.      }
  215. return(NULL);
  216. }
  218. /***********************************************************************
  219. Looks in a search condition if a column value is already restricted by the
  220. search condition BEFORE the nth table is accessed. Takes into account that
  221. if we will fetch in an ascending order, we cannot utilize an upper limit for
  222. a column value; in a descending order, respectively, a lower limit. */
  223. static
  224. que_node_t*
  225. opt_look_for_col_in_cond_before(
  226. /*============================*/
  227. /* out: expression restricting the
  228. value of the column, or NULL if not
  229. known */
  230. ulint cmp_type, /* in: OPT_EQUAL, OPT_COMPARISON */
  231. ulint col_no, /* in: column number */
  232. func_node_t* search_cond, /* in: search condition or NULL */
  233. sel_node_t* sel_node, /* in: select node */
  234. ulint nth_table, /* in: nth table in a join (a query
  235. from a single table is considered a
  236. join of 1 table) */
  237. ulint* op) /* out: comparison operator ('=',
  238. PARS_GE_TOKEN, ... ) */
  239. {
  240. func_node_t* new_cond;
  241. que_node_t* exp;
  243. if (search_cond == NULL) {
  245. return(NULL);
  246. }
  248. ut_a(que_node_get_type(search_cond) == QUE_NODE_FUNC);
  249. ut_a(search_cond->func != PARS_OR_TOKEN);
  250. ut_a(search_cond->func != PARS_NOT_TOKEN);
  252. if (search_cond->func == PARS_AND_TOKEN) {
  253. new_cond = search_cond->args;
  255. exp = opt_look_for_col_in_cond_before(cmp_type, col_no,
  256. new_cond, sel_node, nth_table, op);
  257. if (exp) {
  259. return(exp);
  260. }
  262. new_cond = que_node_get_next(new_cond);
  264. exp = opt_look_for_col_in_cond_before(cmp_type, col_no,
  265. new_cond, sel_node, nth_table, op);
  266. return(exp);
  267. }
  269. exp = opt_look_for_col_in_comparison_before(cmp_type, col_no,
  270. search_cond, sel_node, nth_table, op);
  271. if (exp == NULL) {
  273. return(NULL);
  274. }
  276. /* If we will fetch in an ascending order, we cannot utilize an upper
  277. limit for a column value; in a descending order, respectively, a lower
  278. limit */
  280. if (sel_node->asc && ((*op == '<') || (*op == PARS_LE_TOKEN))) {
  282. return(NULL);
  284. } else if (!sel_node->asc && ((*op == '>') || (*op == PARS_GE_TOKEN))) {
  286. return(NULL);
  287. }
  289. return(exp);
  290. }
  292. /***********************************************************************
  293. Calculates the goodness for an index according to a select node. The
  294. goodness is 4 times the number of first fields in index whose values we
  295. already know exactly in the query. If we have a comparison condition for
  296. an additional field, 2 point are added. If the index is unique, and we know
  297. all the unique fields for the index we add 1024 points. For a clustered index
  298. we add 1 point. */
  299. static
  300. ulint
  301. opt_calc_index_goodness(
  302. /*====================*/
  303. /* out: goodness */
  304. dict_index_t* index, /* in: index */
  305. sel_node_t* sel_node, /* in: parsed select node */
  306. ulint nth_table, /* in: nth table in a join */
  307. que_node_t** index_plan, /* in/out: comparison expressions for
  308. this index */
  309. ulint* last_op) /* out: last comparison operator, if
  310. goodness > 1 */
  311. {
  312. que_node_t* exp;
  313. ulint goodness;
  314. ulint n_fields;
  315. ulint col_no;
  316. ulint mix_id_col_no;
  317. ulint op;
  318. ulint j;
  320. goodness = 0;
  322. /* Note that as higher level node pointers in the B-tree contain
  323. page addresses as the last field, we must not put more fields in
  324. the search tuple than dict_index_get_n_unique_in_tree(index); see
  325. the note in btr_cur_search_to_nth_level. */
  327. n_fields = dict_index_get_n_unique_in_tree(index);
  329. mix_id_col_no = dict_table_get_sys_col_no(index->table, DATA_MIX_ID);
  331. for (j = 0; j < n_fields; j++) {
  333. col_no = dict_index_get_nth_col_no(index, j);
  335. exp = opt_look_for_col_in_cond_before(OPT_EQUAL, col_no,
  336. sel_node->search_cond,
  337. sel_node, nth_table, &op);
  338. if (col_no == mix_id_col_no) {
  339. ut_ad(exp == NULL);
  341. index_plan[j] = NULL;
  342. *last_op = '=';
  343. goodness += 4;
  344. } else if (exp) {
  345. /* The value for this column is exactly known already
  346. at this stage of the join */
  348. index_plan[j] = exp;
  349. *last_op = op;
  350. goodness += 4;
  351. } else {
  352. /* Look for non-equality comparisons */
  354. exp = opt_look_for_col_in_cond_before(OPT_COMPARISON,
  355. col_no, sel_node->search_cond,
  356. sel_node, nth_table, &op);
  357. if (exp) {
  358. index_plan[j] = exp;
  359. *last_op = op;
  360. goodness += 2;
  361. }
  363. break;
  364. }
  365. }
  367. if (goodness >= 4 * dict_index_get_n_unique(index)) {
  368. goodness += 1024;
  370. if (index->type & DICT_CLUSTERED) {
  372. goodness += 1024;
  373. }
  374. }
  376. /* We have to test for goodness here, as last_op may note be set */
  377. if (goodness && index->type & DICT_CLUSTERED) {
  379. goodness++;
  380. }
  382. return(goodness);
  383. }
  385. /***********************************************************************
  386. Calculates the number of matched fields based on an index goodness. */
  387. UNIV_INLINE
  388. ulint
  389. opt_calc_n_fields_from_goodness(
  390. /*============================*/
  391. /* out: number of excatly or partially matched
  392. fields */
  393. ulint goodness) /* in: goodness */
  394. {
  395. return(((goodness % 1024) + 2) / 4);
  396. }
  398. /***********************************************************************
  399. Converts a comparison operator to the corresponding search mode PAGE_CUR_GE,
  400. ... */
  401. UNIV_INLINE
  402. ulint
  403. opt_op_to_search_mode(
  404. /*==================*/
  405. /* out: search mode */
  406. ibool asc, /* in: TRUE if the rows should be fetched in an
  407. ascending order */
  408. ulint op) /* in: operator '=', PARS_GE_TOKEN, ... */
  409. {
  410. if (op == '=') {
  411. if (asc) {
  412. return(PAGE_CUR_GE);
  413. } else {
  414. return(PAGE_CUR_LE);
  415. }
  416. } else if (op == '<') {
  417. ut_a(!asc);
  418. return(PAGE_CUR_L);
  419. } else if (op == '>') {
  420. ut_a(asc);
  421. return(PAGE_CUR_G);
  422. } else if (op == PARS_GE_TOKEN) {
  423. ut_a(asc);
  424. return(PAGE_CUR_GE);
  425. } else if (op == PARS_LE_TOKEN) {
  426. ut_a(!asc);
  427. return(PAGE_CUR_LE);
  428. } else {
  429. ut_error;
  430. }
  432. return(0);
  433. }
  435. /***********************************************************************
  436. Determines if a node is an argument node of a function node. */
  437. static
  438. ibool
  439. opt_is_arg(
  440. /*=======*/
  441. /* out: TRUE if is an argument */
  442. que_node_t* arg_node, /* in: possible argument node */
  443. func_node_t* func_node) /* in: function node */
  444. {
  445. que_node_t* arg;
  447. arg = func_node->args;
  449. while (arg) {
  450. if (arg == arg_node) {
  452. return(TRUE);
  453. }
  455. arg = que_node_get_next(arg);
  456. }
  458. return(FALSE);
  459. }
  461. /***********************************************************************
  462. Decides if the fetching of rows should be made in a descending order, and
  463. also checks that the chosen query plan produces a result which satisfies
  464. the order-by. */
  465. static
  466. void
  467. opt_check_order_by(
  468. /*===============*/
  469. sel_node_t* sel_node) /* in: select node; asserts an error
  470. if the plan does not agree with the
  471. order-by */
  472. {
  473. order_node_t* order_node;
  474. dict_table_t* order_table;
  475. ulint order_col_no;
  476. plan_t* plan;
  477. ulint i;
  479. if (!sel_node->order_by) {
  481. return;
  482. }
  484. order_node = sel_node->order_by;
  485. order_col_no = order_node->column->col_no;
  486. order_table = order_node->column->table;
  488. /* If there is an order-by clause, the first non-exactly matched field
  489. in the index used for the last table in the table list should be the
  490. column defined in the order-by clause, and for all the other tables
  491. we should get only at most a single row, otherwise we cannot presently
  492. calculate the order-by, as we have no sort utility */
  494. for (i = 0; i < sel_node->n_tables; i++) {
  496. plan = sel_node_get_nth_plan(sel_node, i);
  498. if (i < sel_node->n_tables - 1) {
  499. ut_a(dict_index_get_n_unique(plan->index)
  500. <= plan->n_exact_match);
  501. } else {
  502. ut_a(plan->table == order_table);
  504. ut_a((dict_index_get_n_unique(plan->index)
  505. <= plan->n_exact_match)
  506.      || (dict_index_get_nth_col_no(plan->index,
  507.       plan->n_exact_match)
  508.     == order_col_no));
  509. }
  510. }
  511. }
  513. /***********************************************************************
  514. Optimizes a select. Decides which indexes to tables to use. The tables
  515. are accessed in the order that they were written to the FROM part in the
  516. select statement. */
  517. static
  518. void
  519. opt_search_plan_for_table(
  520. /*======================*/
  521. sel_node_t* sel_node, /* in: parsed select node */
  522. ulint i, /* in: this is the ith table */
  523. dict_table_t* table) /* in: table */
  524. {
  525. plan_t* plan;
  526. dict_index_t* index;
  527. dict_index_t* best_index;
  528. ulint n_fields;
  529. ulint goodness;
  530. ulint last_op = 75946965; /* Eliminate a Purify
  531. warning */
  532. ulint best_goodness;
  533. ulint best_last_op = 0; /* remove warning */
  534. ulint mix_id_pos;
  535. que_node_t* index_plan[256];
  536. que_node_t* best_index_plan[256];
  538. plan = sel_node_get_nth_plan(sel_node, i);
  540. plan->table = table;
  541. plan->asc = sel_node->asc;
  542. plan->pcur_is_open = FALSE;
  543. plan->cursor_at_end = FALSE;
  545. /* Calculate goodness for each index of the table */
  547. index = dict_table_get_first_index(table);
  548. best_index = index; /* Eliminate compiler warning */
  549. best_goodness = 0;
  551. /* should be do ... until ? comment by Jani */
  552. while (index) {
  553. goodness = opt_calc_index_goodness(index, sel_node, i,
  554. index_plan, &last_op);
  555. if (goodness > best_goodness) {
  557. best_index = index;
  558. best_goodness = goodness;
  559. n_fields = opt_calc_n_fields_from_goodness(goodness);
  561. ut_memcpy(best_index_plan, index_plan,
  562. n_fields * sizeof(void*));
  563. best_last_op = last_op;
  564. }
  566. index = dict_table_get_next_index(index);
  567. }
  569. plan->index = best_index;
  571. n_fields = opt_calc_n_fields_from_goodness(best_goodness);
  573. if (n_fields == 0) {
  574. plan->tuple = NULL;
  575. plan->n_exact_match = 0;
  576. } else {
  577. plan->tuple = dtuple_create(pars_sym_tab_global->heap,
  578. n_fields);
  579. dict_index_copy_types(plan->tuple, plan->index, n_fields);
  581. plan->tuple_exps = mem_heap_alloc(pars_sym_tab_global->heap,
  582. n_fields * sizeof(void*));
  584. ut_memcpy(plan->tuple_exps, best_index_plan,
  585.    n_fields * sizeof(void*));
  586. if (best_last_op == '=') {
  587. plan->n_exact_match = n_fields;
  588. } else {
  589. plan->n_exact_match = n_fields - 1;
  590. }
  592. plan->mode = opt_op_to_search_mode(sel_node->asc,
  593. best_last_op);
  594. }
  596. if ((best_index->type & DICT_CLUSTERED)
  597.     && (plan->n_exact_match >= dict_index_get_n_unique(best_index))) {
  599. plan->unique_search = TRUE;
  600. } else {
  601. plan->unique_search = FALSE;
  602. }
  604. if ((table->type != DICT_TABLE_ORDINARY)
  605.      && (best_index->type & DICT_CLUSTERED)) {
  607.      plan->mixed_index = TRUE;
  609.      mix_id_pos = table->mix_len;
  611.      if (mix_id_pos < n_fields) {
  612.      /* We have to add the mix id as a (string) literal
  613. expression to the tuple_exps */
  615. plan->tuple_exps[mix_id_pos] =
  616. sym_tab_add_str_lit(pars_sym_tab_global,
  617. table->mix_id_buf,
  618. table->mix_id_len);
  619.      }
  620. } else {
  621. plan->mixed_index = FALSE;
  622. }
  624. plan->old_vers_heap = NULL;
  626. btr_pcur_init(&(plan->pcur));
  627. btr_pcur_init(&(plan->clust_pcur));
  628. }
  630. /***********************************************************************
  631. Looks at a comparison condition and decides if it can, and need, be tested for
  632. a table AFTER the table has been accessed. */
  633. static
  634. ulint
  635. opt_classify_comparison(
  636. /*====================*/
  637. /* out: OPT_NOT_COND if not for this
  638. table, else OPT_END_COND,
  639. OPT_TEST_COND, or OPT_SCROLL_COND,
  640. where the last means that the
  641. condition need not be tested, except
  642. when scroll cursors are used */
  643. sel_node_t* sel_node, /* in: select node */
  644. ulint i, /* in: ith table in the join */
  645. func_node_t* cond) /* in: comparison condition */
  646. {
  647. plan_t* plan;
  648. ulint n_fields;
  649. ulint op;
  650. ulint j;
  652. ut_ad(cond && sel_node);
  654. plan = sel_node_get_nth_plan(sel_node, i);
  656. /* Check if the condition is determined after the ith table has been
  657. accessed, but not after the i - 1:th */
  659. if (!opt_check_exp_determined_before(cond, sel_node, i + 1)) {
  661. return(OPT_NOT_COND);
  662. }
  664. if ((i > 0) && opt_check_exp_determined_before(cond, sel_node, i)) {
  666. return(OPT_NOT_COND);
  667. }
  669. /* If the condition is an exact match condition used in constructing
  670. the search tuple, it is classified as OPT_END_COND */
  672. if (plan->tuple) {
  673. n_fields = dtuple_get_n_fields(plan->tuple);
  674. } else {
  675. n_fields = 0;
  676. }
  678. for (j = 0; j < plan->n_exact_match; j++) {
  680. if (opt_is_arg(plan->tuple_exps[j], cond)) {
  682. return(OPT_END_COND);
  683. }
  684. }
  686. /* If the condition is an non-exact match condition used in
  687. constructing the search tuple, it is classified as OPT_SCROLL_COND.
  688. When the cursor is positioned, and if a non-scroll cursor is used,
  689. there is no need to test this condition; if a scroll cursor is used
  690. the testing is necessary when the cursor is reversed. */
  692. if ((n_fields > plan->n_exact_match)
  693.      && opt_is_arg(plan->tuple_exps[n_fields - 1], cond)) {
  695.      return(OPT_SCROLL_COND);
  696. }
  698. /* If the condition is a non-exact match condition on the first field
  699. in index for which there is no exact match, and it limits the search
  700. range from the opposite side of the search tuple already BEFORE we
  701. access the table, it is classified as OPT_END_COND */
  703. if ((dict_index_get_n_fields(plan->index) > plan->n_exact_match)
  704.     && opt_look_for_col_in_comparison_before(
  705. OPT_COMPARISON,
  706.      dict_index_get_nth_col_no(plan->index,
  707.      plan->n_exact_match),
  708.      cond, sel_node, i, &op)) {
  709.     
  710. if (sel_node->asc && ((op == '<') || (op == PARS_LE_TOKEN))) {
  712. return(OPT_END_COND);
  713. }
  715. if (!sel_node->asc && ((op == '>') || (op == PARS_GE_TOKEN))) {
  717. return(OPT_END_COND);
  718. }
  719. }
  721. /* Otherwise, cond is classified as OPT_TEST_COND */
  723. return(OPT_TEST_COND);
  724. }
  726. /***********************************************************************
  727. Recursively looks for test conditions for a table in a join. */
  728. static
  729. void
  730. opt_find_test_conds(
  731. /*================*/
  732. sel_node_t* sel_node, /* in: select node */
  733. ulint i, /* in: ith table in the join */
  734. func_node_t* cond) /* in: conjunction of search
  735. conditions or NULL */
  736. {
  737. func_node_t* new_cond;
  738. ulint class;
  739. plan_t* plan;
  741. if (cond == NULL) {
  743. return;
  744. }
  746. if (cond->func == PARS_AND_TOKEN) {
  747. new_cond = cond->args;
  749. opt_find_test_conds(sel_node, i, new_cond);
  751. new_cond = que_node_get_next(new_cond);
  753. opt_find_test_conds(sel_node, i, new_cond);
  755. return;
  756. }
  758. plan = sel_node_get_nth_plan(sel_node, i);
  760. class = opt_classify_comparison(sel_node, i, cond);
  762. if (class == OPT_END_COND) {
  763. UT_LIST_ADD_LAST(cond_list, plan->end_conds, cond);
  765. } else if (class == OPT_TEST_COND) {
  766. UT_LIST_ADD_LAST(cond_list, plan->other_conds, cond);
  768. }
  769. }
  771. /***********************************************************************
  772. Normalizes a list of comparison conditions so that a column of the table
  773. appears on the left side of the comparison if possible. This is accomplished
  774. by switching the arguments of the operator. */
  775. static
  776. void
  777. opt_normalize_cmp_conds(
  778. /*====================*/
  779. func_node_t* cond, /* in: first in a list of comparison
  780. conditions, or NULL */
  781. dict_table_t* table) /* in: table */
  782. {
  783. que_node_t* arg1;
  784. que_node_t* arg2;
  785. sym_node_t* sym_node;
  787. while (cond) {
  788. arg1 = cond->args;
  789. arg2 = que_node_get_next(arg1);
  791. if (que_node_get_type(arg2) == QUE_NODE_SYMBOL) {
  793. sym_node = arg2;
  795. if ((sym_node->token_type == SYM_COLUMN)
  796. && (sym_node->table == table)) {
  798. /* Switch the order of the arguments */
  800. cond->args = arg2;
  801. que_node_list_add_last(NULL, arg2);
  802. que_node_list_add_last(arg2, arg1);
  804. /* Invert the operator */
  805. cond->func = opt_invert_cmp_op(cond->func);
  806. }
  807. }
  809. cond = UT_LIST_GET_NEXT(cond_list, cond);
  810. }
  811. }
  813. /***********************************************************************
  814. Finds out the search condition conjuncts we can, and need, to test as the ith
  815. table in a join is accessed. The search tuple can eliminate the need to test
  816. some conjuncts. */
  817. static
  818. void
  819. opt_determine_and_normalize_test_conds(
  820. /*===================================*/
  821. sel_node_t* sel_node, /* in: select node */
  822. ulint i) /* in: ith table in the join */
  823. {
  824. plan_t* plan;
  826. plan = sel_node_get_nth_plan(sel_node, i);
  828. UT_LIST_INIT(plan->end_conds);
  829. UT_LIST_INIT(plan->other_conds);
  831. /* Recursively go through the conjuncts and classify them */
  833. opt_find_test_conds(sel_node, i, sel_node->search_cond);
  835. opt_normalize_cmp_conds(UT_LIST_GET_FIRST(plan->end_conds),
  836. plan->table);
  838. ut_a(UT_LIST_GET_LEN(plan->end_conds) >= plan->n_exact_match);
  839. }
  841. /***********************************************************************
  842. Looks for occurrences of the columns of the table in the query subgraph and
  843. adds them to the list of columns if an occurrence of the same column does not
  844. already exist in the list. If the column is already in the list, puts a value
  845. indirection to point to the occurrence in the column list, except if the
  846. column occurrence we are looking at is in the column list, in which case
  847. nothing is done. */
  849. void
  850. opt_find_all_cols(
  851. /*==============*/
  852. ibool copy_val, /* in: if TRUE, new found columns are
  853. added as columns to copy */
  854. dict_index_t* index, /* in: index of the table to use */
  855. sym_node_list_t* col_list, /* in: base node of a list where
  856. to add new found columns */
  857. plan_t* plan, /* in: plan or NULL */
  858. que_node_t* exp) /* in: expression or condition or
  859. NULL */
  860. {
  861. func_node_t* func_node;
  862. que_node_t* arg;
  863. sym_node_t* sym_node;
  864. sym_node_t* col_node;
  865. ulint col_pos;
  867. if (exp == NULL) {
  869. return;
  870. }
  872. if (que_node_get_type(exp) == QUE_NODE_FUNC) {
  873. func_node = exp;
  875. arg = func_node->args;
  877. while (arg) {
  878. opt_find_all_cols(copy_val, index, col_list, plan,
  879. arg);
  880. arg = que_node_get_next(arg);
  881. }
  883. return;
  884. }
  886. ut_a(que_node_get_type(exp) == QUE_NODE_SYMBOL);
  888. sym_node = exp;
  890. if (sym_node->token_type != SYM_COLUMN) {
  892. return;
  893. }
  895. if (sym_node->table != index->table) {
  897. return;
  898. }
  900. /* Look for an occurrence of the same column in the plan column
  901. list */
  903. col_node = UT_LIST_GET_FIRST(*col_list);
  905. while (col_node) {
  906. if (col_node->col_no == sym_node->col_no) {
  908. if (col_node == sym_node) {
  909. /* sym_node was already in a list: do
  910. nothing */
  912. return;
  913. }
  915. /* Put an indirection */
  916. sym_node->indirection = col_node;
  917. sym_node->alias = col_node;
  919. return;
  920. }
  922. col_node = UT_LIST_GET_NEXT(col_var_list, col_node);
  923. }
  925. /* The same column did not occur in the list: add it */
  927. UT_LIST_ADD_LAST(col_var_list, *col_list, sym_node);
  929. sym_node->copy_val = copy_val;
  931. /* Fill in the field_no fields in sym_node */
  933. sym_node->field_nos[SYM_CLUST_FIELD_NO]
  934. = dict_index_get_nth_col_pos(
  935. dict_table_get_first_index(index->table),
  936. sym_node->col_no);
  937. if (!(index->type & DICT_CLUSTERED)) {
  939. ut_a(plan);
  941. col_pos = dict_index_get_nth_col_pos(index, sym_node->col_no);
  943. if (col_pos == ULINT_UNDEFINED) {
  945. plan->must_get_clust = TRUE;
  946. }
  948. sym_node->field_nos[SYM_SEC_FIELD_NO] = col_pos;
  949. }
  950. }
  952. /***********************************************************************
  953. Looks for occurrences of the columns of the table in conditions which are
  954. not yet determined AFTER the join operation has fetched a row in the ith
  955. table. The values for these column must be copied to dynamic memory for
  956. later use. */
  957. static
  958. void
  959. opt_find_copy_cols(
  960. /*===============*/
  961. sel_node_t* sel_node, /* in: select node */
  962. ulint i, /* in: ith table in the join */
  963. func_node_t* search_cond) /* in: search condition or NULL */
  964. {
  965. func_node_t* new_cond;
  966. plan_t* plan;
  968. if (search_cond == NULL) {
  970. return;
  971. }
  973. ut_ad(que_node_get_type(search_cond) == QUE_NODE_FUNC);
  975. if (search_cond->func == PARS_AND_TOKEN) {
  976. new_cond = search_cond->args;
  978. opt_find_copy_cols(sel_node, i, new_cond);
  980. new_cond = que_node_get_next(new_cond);
  982. opt_find_copy_cols(sel_node, i, new_cond);
  984. return;
  985. }
  987. if (!opt_check_exp_determined_before(search_cond, sel_node, i + 1)) {
  989. /* Any ith table columns occurring in search_cond should be
  990. copied, as this condition cannot be tested already on the
  991. fetch from the ith table */
  993. plan = sel_node_get_nth_plan(sel_node, i);
  995. opt_find_all_cols(TRUE, plan->index, &(plan->columns), plan,
  996. search_cond);
  997. }
  998. }
  1000. /***********************************************************************
  1001. Classifies the table columns according to whether we use the column only while
  1002. holding the latch on the page, or whether we have to copy the column value to
  1003. dynamic memory. Puts the first occurrence of a column to either list in the
  1004. plan node, and puts indirections to later occurrences of the column. */
  1005. static
  1006. void
  1007. opt_classify_cols(
  1008. /*==============*/
  1009. sel_node_t* sel_node, /* in: select node */
  1010. ulint i) /* in: ith table in the join */
  1011. {
  1012. plan_t* plan;
  1013. que_node_t* exp;
  1015. plan = sel_node_get_nth_plan(sel_node, i);
  1017. /* The final value of the following field will depend on the
  1018. environment of the select statement: */
  1020. plan->must_get_clust = FALSE;
  1022. UT_LIST_INIT(plan->columns);
  1024. /* All select list columns should be copied: therefore TRUE as the
  1025. first argument */
  1027. exp = sel_node->select_list;
  1029. while (exp) {
  1030. opt_find_all_cols(TRUE, plan->index, &(plan->columns), plan,
  1031. exp);
  1032. exp = que_node_get_next(exp);
  1033. }
  1035. opt_find_copy_cols(sel_node, i, sel_node->search_cond);
  1037. /* All remaining columns in the search condition are temporary
  1038. columns: therefore FALSE */
  1040. opt_find_all_cols(FALSE, plan->index, &(plan->columns), plan,
  1041. sel_node->search_cond);
  1042. }
  1044. /***********************************************************************
  1045. Fills in the info in plan which is used in accessing a clustered index
  1046. record. The columns must already be classified for the plan node. */
  1047. static
  1048. void
  1049. opt_clust_access(
  1050. /*=============*/
  1051. sel_node_t* sel_node, /* in: select node */
  1052. ulint n) /* in: nth table in select */
  1053. {
  1054. plan_t* plan;
  1055. dict_table_t* table;
  1056. dict_index_t* clust_index;
  1057. dict_index_t* index;
  1058. dfield_t* dfield;
  1059. mem_heap_t* heap;
  1060. ulint n_fields;
  1061. ulint pos;
  1062. ulint i;
  1064. plan = sel_node_get_nth_plan(sel_node, n);
  1066. index = plan->index;
  1068. /* The final value of the following field depends on the environment
  1069. of the select statement: */
  1071. plan->no_prefetch = FALSE;
  1073. if (index->type & DICT_CLUSTERED) {
  1074. plan->clust_map = NULL;
  1075. plan->clust_ref = NULL;
  1077. return;
  1078. }
  1080. table = index->table;
  1082. clust_index = dict_table_get_first_index(table);
  1084. n_fields = dict_index_get_n_unique(clust_index);
  1086. heap = pars_sym_tab_global->heap;
  1088. plan->clust_ref = dtuple_create(heap, n_fields);
  1090. dict_index_copy_types(plan->clust_ref, clust_index, n_fields);
  1092. plan->clust_map = mem_heap_alloc(heap, n_fields * sizeof(ulint));
  1094. for (i = 0; i < n_fields; i++) {
  1095. pos = dict_index_get_nth_field_pos(index, clust_index, i);
  1097. ut_a(pos != ULINT_UNDEFINED);
  1099. /* We optimize here only queries to InnoDB's internal system
  1100. tables, and they should not contain column prefix indexes. */
  1102. if (dict_index_get_nth_field(index, pos)->prefix_len != 0
  1103.     || dict_index_get_nth_field(clust_index, i)
  1104. ->prefix_len != 0) {
  1105. fprintf(stderr,
  1106. "InnoDB: Error in pars0opt.c: table %s has prefix_len != 0n",
  1107. index->table_name);
  1108. }
  1110. *(plan->clust_map + i) = pos;
  1112. ut_ad((pos != ULINT_UNDEFINED)
  1113. || ((table->type == DICT_TABLE_CLUSTER_MEMBER)
  1114.   && (i == table->mix_len)));
  1115. }
  1117. if (table->type == DICT_TABLE_CLUSTER_MEMBER) {
  1119. /* Preset the mix id field to the mix id constant */
  1121. dfield = dtuple_get_nth_field(plan->clust_ref, table->mix_len);
  1123. dfield_set_data(dfield, mem_heap_alloc(heap,
  1124. table->mix_id_len),
  1125. table->mix_id_len);
  1126. ut_memcpy(dfield_get_data(dfield), table->mix_id_buf,
  1127. table->mix_id_len);
  1128. }
  1129. }
  1131. /***********************************************************************
  1132. Optimizes a select. Decides which indexes to tables to use. The tables
  1133. are accessed in the order that they were written to the FROM part in the
  1134. select statement. */
  1136. void
  1137. opt_search_plan(
  1138. /*============*/
  1139. sel_node_t* sel_node) /* in: parsed select node */
  1140. {
  1141. sym_node_t* table_node;
  1142. dict_table_t* table;
  1143. order_node_t* order_by;
  1144. ulint i;
  1146. sel_node->plans = mem_heap_alloc(pars_sym_tab_global->heap,
  1147. sel_node->n_tables * sizeof(plan_t));
  1149. /* Analyze the search condition to find out what we know at each
  1150. join stage about the conditions that the columns of a table should
  1151. satisfy */
  1153. table_node = sel_node->table_list;
  1155. if (sel_node->order_by == NULL) {
  1156. sel_node->asc = TRUE;
  1157. } else {
  1158. order_by = sel_node->order_by;
  1160. sel_node->asc = order_by->asc;
  1161. }
  1163. for (i = 0; i < sel_node->n_tables; i++) {
  1165. table = table_node->table;
  1167. /* Choose index through which to access the table */
  1169. opt_search_plan_for_table(sel_node, i, table);
  1171. /* Determine the search condition conjuncts we can test at
  1172. this table; normalize the end conditions */
  1174. opt_determine_and_normalize_test_conds(sel_node, i);
  1176. table_node = que_node_get_next(table_node);
  1177. }
  1179. table_node = sel_node->table_list;
  1181. for (i = 0; i < sel_node->n_tables; i++) {
  1183. /* Classify the table columns into those we only need to access
  1184. but not copy, and to those we must copy to dynamic memory */
  1186. opt_classify_cols(sel_node, i);
  1188. /* Calculate possible info for accessing the clustered index
  1189. record */
  1191. opt_clust_access(sel_node, i);
  1193. table_node = que_node_get_next(table_node);
  1194. }
  1196. /* Check that the plan obeys a possible order-by clause: if not,
  1197. an assertion error occurs */
  1199. opt_check_order_by(sel_node);
  1201. #ifdef UNIV_SQL_DEBUG
  1202. opt_print_query_plan(sel_node);
  1203. #endif
  1204. }
  1206. /************************************************************************
  1207. Prints info of a query plan. */
  1209. void
  1210. opt_print_query_plan(
  1211. /*=================*/
  1212. sel_node_t* sel_node) /* in: select node */
  1213. {
  1214. plan_t* plan;
  1215. ulint n_fields;
  1216. ulint i;
  1218. fputs("QUERY PLAN FOR A SELECT NODEn", stderr);
  1220. fputs(sel_node->asc ? "Asc. search; " : "Desc. search; ", stderr);
  1222. if (sel_node->set_x_locks) {
  1223. fputs("sets row x-locks; ", stderr);
  1224. ut_a(sel_node->row_lock_mode == LOCK_X);
  1225. ut_a(!sel_node->consistent_read);
  1226. } else if (sel_node->consistent_read) {
  1227. fputs("consistent read; ", stderr);
  1228. } else {
  1229. ut_a(sel_node->row_lock_mode == LOCK_S);
  1230. fputs("sets row s-locks; ", stderr);
  1231. }
  1233. putc('n', stderr);
  1235. for (i = 0; i < sel_node->n_tables; i++) {
  1236. plan = sel_node_get_nth_plan(sel_node, i);
  1238. if (plan->tuple) {
  1239. n_fields = dtuple_get_n_fields(plan->tuple);
  1240. } else {
  1241. n_fields = 0;
  1242. }
  1244. fputs("Table ", stderr);
  1245. dict_index_name_print(stderr, NULL, plan->index);
  1246. fprintf(stderr,"; exact m. %lu, match %lu, end conds %lun",
  1247.         (unsigned long) plan->n_exact_match,
  1248.         (unsigned long) n_fields,
  1249. (unsigned long) UT_LIST_GET_LEN(plan->end_conds));
  1250. }
  1251. }