← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/opt_range.cc

  • Committer: devananda
  • Date: 2009-06-30 14:27:54 UTC
  • mfrom: (1030.2.4 trunk)
  • mto: (1093.1.7 captain)
  • mto: This revision was merged to the branch mainline in revision 1095.
  • Revision ID: devananda.vdv@gmail.com-20090630142754-vm9w374yxkf1pikc
merge from lp

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/opt_range.cc
114
114
#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
115
115
 
116
116
#include <string>
 
117
#include <vector>
117
118
 
118
119
using namespace std;
119
120
 
634
635
    Possible ways to read rows using index_merge. The list is non-empty only
635
636
    if type==KEY. Currently can be non empty only if keys_map.none().
636
637
  */
637
 
  List<SEL_IMERGE> merges;
 
638
  vector<SEL_IMERGE*> merges;
638
639
 
639
640
  /* The members below are filled/used only after get_mm_tree is done */
640
641
  key_map ror_scans_map;   /* bitmask of ROR scan-able elements in keys */
931
932
 
932
933
 
933
934
/*
934
 
  Perform AND operation on two index_merge lists and store result in *im1.
 
935
  Perform AND operation on two index_merge lists and store result in im1.
935
936
*/
936
937
 
937
 
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
 
938
inline void imerge_list_and_list(vector<SEL_IMERGE*> &im1, vector<SEL_IMERGE*> &im2)
938
939
{
939
 
  im1->concat(im2);
 
940
  im1.insert(im1.end(), im2.begin(), im2.end());
 
941
  im2.clear();
940
942
}
941
943
 
942
944
 
964
966
*/
965
967
 
966
968
int imerge_list_or_list(RANGE_OPT_PARAM *param,
967
 
                        List<SEL_IMERGE> *im1,
968
 
                        List<SEL_IMERGE> *im2)
 
969
                        vector<SEL_IMERGE*> &im1,
 
970
                        vector<SEL_IMERGE*> &im2)
969
971
{
970
 
  SEL_IMERGE *imerge= im1->head();
971
 
  im1->empty();
972
 
  im1->push_back(imerge);
 
972
  SEL_IMERGE *imerge= im1.front();
 
973
  im1.clear();
 
974
  im1.push_back(imerge);
973
975
 
974
 
  return imerge->or_sel_imerge_with_checks(param, im2->head());
 
976
  return imerge->or_sel_imerge_with_checks(param, im2.front());
975
977
}
976
978
 
977
979
 
979
981
  Perform OR operation on index_merge list and key tree.
980
982
 
981
983
  RETURN
982
 
    0     OK, result is stored in *im1.
983
 
    other Error
 
984
    false   OK, result is stored in im1.
 
985
    true    Error
984
986
*/
985
987
 
986
 
int imerge_list_or_tree(RANGE_OPT_PARAM *param,
987
 
                        List<SEL_IMERGE> *im1,
988
 
                        SEL_TREE *tree)
 
988
bool imerge_list_or_tree(RANGE_OPT_PARAM *param,
 
989
                         vector<SEL_IMERGE*> &im1,
 
990
                         SEL_TREE *tree)
989
991
{
990
 
  SEL_IMERGE *imerge;
991
 
  List_iterator<SEL_IMERGE> it(*im1);
992
 
  while ((imerge= it++))
 
992
  vector<SEL_IMERGE*>::iterator imerge= im1.begin();
 
993
 
 
994
  while (imerge != im1.end())
993
995
  {
994
 
    if (imerge->or_sel_tree_with_checks(param, tree))
995
 
      it.remove();
 
996
    if ((*imerge)->or_sel_tree_with_checks(param, tree))
 
997
      imerge= im1.erase( imerge );
 
998
    else
 
999
      ++imerge;
996
1000
  }
997
 
  return im1->is_empty();
 
1001
 
 
1002
  return im1.empty();
998
1003
}
999
1004
 
1000
1005
 
2344
2349
        It is possible to use a range-based quick select (but it might be
2345
2350
        slower than 'all' table scan).
2346
2351
      */
2347
 
      if (tree->merges.is_empty())
 
2352
      if (tree->merges.empty() == true)
2348
2353
      {
2349
2354
        TRP_RANGE         *range_trp;
2350
2355
        TRP_ROR_INTERSECT *rori_trp;
2388
2393
      else
2389
2394
      {
2390
2395
        /* Try creating index_merge/ROR-union scan. */
2391
 
        SEL_IMERGE *imerge;
2392
2396
        TABLE_READ_PLAN *best_conj_trp= NULL, *new_conj_trp;
2393
 
        List_iterator_fast<SEL_IMERGE> it(tree->merges);
2394
 
        while ((imerge= it++))
 
2397
        vector<SEL_IMERGE*>::iterator imerge= tree->merges.begin();
 
2398
        while (imerge != tree->merges.end())
2395
2399
        {
2396
 
          new_conj_trp= get_best_disjunct_quick(&param, imerge, best_read_time);
 
2400
          new_conj_trp= get_best_disjunct_quick(&param, *imerge, best_read_time);
2397
2401
          if (new_conj_trp)
2398
2402
            set_if_smaller(param.table->quick_condition_rows,
2399
2403
                           new_conj_trp->records);
 
2404
 
2400
2405
          if (!best_conj_trp || (new_conj_trp && new_conj_trp->read_cost <
2401
2406
                                 best_conj_trp->read_cost))
2402
2407
            best_conj_trp= new_conj_trp;
 
2408
 
 
2409
          ++imerge;
2403
2410
        }
2404
2411
        if (best_conj_trp)
2405
2412
          best_trp= best_conj_trp;
4857
4864
  /* dispose index_merge if there is a "range" option */
4858
4865
  if (result_keys.any())
4859
4866
  {
4860
 
    tree1->merges.empty();
 
4867
    tree1->merges.clear();
4861
4868
    return(tree1);
4862
4869
  }
4863
4870
 
4864
4871
  /* ok, both trees are index_merge trees */
4865
 
  imerge_list_and_list(&tree1->merges, &tree2->merges);
 
4872
  imerge_list_and_list(tree1->merges, tree2->merges);
4866
4873
  return(tree1);
4867
4874
}
4868
4875
 
5016
5023
  else
5017
5024
  {
5018
5025
    /* ok, two trees have KEY type but cannot be used without index merge */
5019
 
    if (tree1->merges.is_empty() && tree2->merges.is_empty())
 
5026
    if ((tree1->merges.empty() == true) && (tree2->merges.empty() == true))
5020
5027
    {
5021
5028
      if (param->remove_jump_scans)
5022
5029
      {
5025
5032
        if (no_trees)
5026
5033
          return(new SEL_TREE(SEL_TREE::ALWAYS));
5027
5034
      }
5028
 
      SEL_IMERGE *merge;
5029
 
      /* both trees are "range" trees, produce new index merge structure */
5030
 
      if (!(result= new SEL_TREE()) || !(merge= new SEL_IMERGE()) ||
5031
 
          (result->merges.push_back(merge)) ||
5032
 
          (merge->or_sel_tree(param, tree1)) ||
5033
 
          (merge->or_sel_tree(param, tree2)))
 
5035
 
 
5036
      /* both trees are "range" trees, produce new index merge structure. */
 
5037
      result= new SEL_TREE();
 
5038
      SEL_IMERGE *merge= new SEL_IMERGE();
 
5039
      result->merges.push_back(merge);
 
5040
 
 
5041
      if( merge->or_sel_tree(param, tree1) || merge->or_sel_tree(param, tree2))
5034
5042
        result= NULL;
5035
5043
      else
5036
5044
        result->type= tree1->type;
5037
5045
    }
5038
 
    else if (!tree1->merges.is_empty() && !tree2->merges.is_empty())
 
5046
    else if ((tree1->merges.empty() == false) && (tree2->merges.empty() == false))
5039
5047
    {
5040
 
      if (imerge_list_or_list(param, &tree1->merges, &tree2->merges))
 
5048
      if (imerge_list_or_list(param, tree1->merges, tree2->merges))
5041
5049
        result= new SEL_TREE(SEL_TREE::ALWAYS);
5042
5050
      else
5043
5051
        result= tree1;
5045
5053
    else
5046
5054
    {
5047
5055
      /* one tree is index merge tree and another is range tree */
5048
 
      if (tree1->merges.is_empty())
 
5056
      if (tree1->merges.empty() == true)
5049
5057
        std::swap(tree1, tree2);
5050
5058
 
5051
5059
      if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
5052
5060
         return(new SEL_TREE(SEL_TREE::ALWAYS));
 
5061
 
5053
5062
      /* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
5054
 
      if (imerge_list_or_tree(param, &tree1->merges, tree2))
 
5063
      if (imerge_list_or_tree(param, tree1->merges, tree2))
5055
5064
        result= new SEL_TREE(SEL_TREE::ALWAYS);
5056
5065
      else
5057
5066
        result= tree1;