← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/sql_select.cc

merge trunk

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/sql_select.cc
138
138
                      select_lex->where,
139
139
                      select_lex->order_list.elements +
140
140
                      select_lex->group_list.elements,
141
 
                      (order_st*) select_lex->order_list.first,
142
 
                      (order_st*) select_lex->group_list.first,
 
141
                      (Order*) select_lex->order_list.first,
 
142
                      (Order*) select_lex->group_list.first,
143
143
                      select_lex->having,
144
144
                      select_lex->options | session->options |
145
145
                      setup_tables_done_option,
352
352
                  List<Item> &fields,
353
353
                  COND *conds, 
354
354
                  uint32_t og_num,  
355
 
                  order_st *order, 
356
 
                  order_st *group,
 
355
                  Order *order,
 
356
                  Order *group,
357
357
                  Item *having, 
358
358
                  uint64_t select_options,
359
359
                  select_result *result, 
447
447
  return (cond? (new Item_cond_and(cond, item)) : item);
448
448
}
449
449
 
450
 
static void fix_list_after_tbl_changes(Select_Lex *new_parent, List<TableList> *tlist)
451
 
{
452
 
  List_iterator<TableList> it(*tlist);
453
 
  TableList *table;
454
 
  while ((table= it++))
455
 
  {
456
 
    if (table->on_expr)
457
 
      table->on_expr->fix_after_pullout(new_parent, &table->on_expr);
458
 
    if (table->getNestedJoin())
459
 
      fix_list_after_tbl_changes(new_parent, &table->getNestedJoin()->join_list);
460
 
  }
461
 
}
462
 
 
463
450
/*****************************************************************************
464
451
  Create JoinTableS, make a guess about the table types,
465
452
  Approximate how many records will be used in each table
673
660
        else if (use->getKeypart() != 0)                // First found must be 0
674
661
          continue;
675
662
 
676
 
#ifdef HAVE_purify
 
663
#ifdef HAVE_VALGRIND
677
664
        /* Valgrind complains about overlapped memcpy when save_pos==use. */
678
665
        if (save_pos != use)
679
666
#endif
756
743
{
757
744
  List<Item_field> indexed_fields;
758
745
  List_iterator<Item_field> indexed_fields_it(indexed_fields);
759
 
  order_st      *cur_group;
 
746
  Order      *cur_group;
760
747
  Item_field *cur_item;
761
748
  key_map possible_keys(0);
762
749
 
1216
1203
  return tmp;
1217
1204
}
1218
1205
 
1219
 
/*
1220
 
  Check if given expression uses only table fields covered by the given index
1221
 
 
1222
 
  SYNOPSIS
1223
 
    uses_index_fields_only()
1224
 
      item           Expression to check
1225
 
      tbl            The table having the index
1226
 
      keyno          The index number
1227
 
      other_tbls_ok  true <=> Fields of other non-const tables are allowed
1228
 
 
1229
 
  DESCRIPTION
1230
 
    Check if given expression only uses fields covered by index #keyno in the
1231
 
    table tbl. The expression can use any fields in any other tables.
1232
 
 
1233
 
    The expression is guaranteed not to be AND or OR - those constructs are
1234
 
    handled outside of this function.
1235
 
 
1236
 
  RETURN
1237
 
    true   Yes
1238
 
    false  No
1239
 
*/
1240
 
static bool uses_index_fields_only(Item *item, Table *tbl, uint32_t keyno, bool other_tbls_ok)
1241
 
{
1242
 
  if (item->const_item())
1243
 
    return true;
1244
 
 
1245
 
  /*
1246
 
    Don't push down the triggered conditions. Nested outer joins execution
1247
 
    code may need to evaluate a condition several times (both triggered and
1248
 
    untriggered), and there is no way to put thi
1249
 
    TODO: Consider cloning the triggered condition and using the copies for:
1250
 
      1. push the first copy down, to have most restrictive index condition
1251
 
         possible
1252
 
      2. Put the second copy into tab->select_cond.
1253
 
  */
1254
 
  if (item->type() == Item::FUNC_ITEM &&
1255
 
      ((Item_func*)item)->functype() == Item_func::TRIG_COND_FUNC)
1256
 
    return false;
1257
 
 
1258
 
  if (!(item->used_tables() & tbl->map))
1259
 
    return other_tbls_ok;
1260
 
 
1261
 
  Item::Type item_type= item->type();
1262
 
  switch (item_type) {
1263
 
  case Item::FUNC_ITEM:
1264
 
    {
1265
 
      /* This is a function, apply condition recursively to arguments */
1266
 
      Item_func *item_func= (Item_func*)item;
1267
 
      Item **child;
1268
 
      Item **item_end= (item_func->arguments()) + item_func->argument_count();
1269
 
      for (child= item_func->arguments(); child != item_end; child++)
1270
 
      {
1271
 
        if (!uses_index_fields_only(*child, tbl, keyno, other_tbls_ok))
1272
 
          return false;
1273
 
      }
1274
 
      return true;
1275
 
    }
1276
 
  case Item::COND_ITEM:
1277
 
    {
1278
 
      /* This is a function, apply condition recursively to arguments */
1279
 
      List_iterator<Item> li(*((Item_cond*)item)->argument_list());
1280
 
      Item *list_item;
1281
 
      while ((list_item=li++))
1282
 
      {
1283
 
        if (!uses_index_fields_only(item, tbl, keyno, other_tbls_ok))
1284
 
          return false;
1285
 
      }
1286
 
      return true;
1287
 
    }
1288
 
  case Item::FIELD_ITEM:
1289
 
    {
1290
 
      Item_field *item_field= (Item_field*)item;
1291
 
      if (item_field->field->getTable() != tbl)
1292
 
        return true;
1293
 
      return item_field->field->part_of_key.test(keyno);
1294
 
    }
1295
 
  case Item::REF_ITEM:
1296
 
    return uses_index_fields_only(item->real_item(), tbl, keyno,
1297
 
                                  other_tbls_ok);
1298
 
  default:
1299
 
    return false; /* Play it safe, don't push unknown non-const items */
1300
 
  }
1301
 
}
1302
 
 
1303
1206
#define ICP_COND_USES_INDEX_ONLY 10
1304
1207
 
1305
 
/*
1306
 
  Get a part of the condition that can be checked using only index fields
1307
 
 
1308
 
  SYNOPSIS
1309
 
    make_cond_for_index()
1310
 
      cond           The source condition
1311
 
      table          The table that is partially available
1312
 
      keyno          The index in the above table. Only fields covered by the index
1313
 
                     are available
1314
 
      other_tbls_ok  true <=> Fields of other non-const tables are allowed
1315
 
 
1316
 
  DESCRIPTION
1317
 
    Get a part of the condition that can be checked when for the given table
1318
 
    we have values only of fields covered by some index. The condition may
1319
 
    refer to other tables, it is assumed that we have values of all of their
1320
 
    fields.
1321
 
 
1322
 
    Example:
1323
 
      make_cond_for_index(
1324
 
         "cond(t1.field) AND cond(t2.key1) AND cond(t2.non_key) AND cond(t2.key2)",
1325
 
          t2, keyno(t2.key1))
1326
 
      will return
1327
 
        "cond(t1.field) AND cond(t2.key2)"
1328
 
 
1329
 
  RETURN
1330
 
    Index condition, or NULL if no condition could be inferred.
1331
 
*/
1332
 
static Item *make_cond_for_index(Item *cond, Table *table, uint32_t keyno, bool other_tbls_ok)
1333
 
{
1334
 
  if (!cond)
1335
 
    return NULL;
1336
 
  if (cond->type() == Item::COND_ITEM)
1337
 
  {
1338
 
    uint32_t n_marked= 0;
1339
 
    if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
1340
 
    {
1341
 
      Item_cond_and *new_cond=new Item_cond_and;
1342
 
      if (!new_cond)
1343
 
        return (COND*) 0;
1344
 
      List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
1345
 
      Item *item;
1346
 
      while ((item=li++))
1347
 
      {
1348
 
        Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
1349
 
        if (fix)
1350
 
          new_cond->argument_list()->push_back(fix);
1351
 
        n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
1352
 
      }
1353
 
      if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
1354
 
        cond->marker= ICP_COND_USES_INDEX_ONLY;
1355
 
      switch (new_cond->argument_list()->elements) {
1356
 
      case 0:
1357
 
        return (COND*) 0;
1358
 
      case 1:
1359
 
        return new_cond->argument_list()->head();
1360
 
      default:
1361
 
        new_cond->quick_fix_field();
1362
 
        return new_cond;
1363
 
      }
1364
 
    }
1365
 
    else /* It's OR */
1366
 
    {
1367
 
      Item_cond_or *new_cond=new Item_cond_or;
1368
 
      if (!new_cond)
1369
 
        return (COND*) 0;
1370
 
      List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
1371
 
      Item *item;
1372
 
      while ((item=li++))
1373
 
      {
1374
 
        Item *fix= make_cond_for_index(item, table, keyno, other_tbls_ok);
1375
 
        if (!fix)
1376
 
          return (COND*) 0;
1377
 
        new_cond->argument_list()->push_back(fix);
1378
 
        n_marked += test(item->marker == ICP_COND_USES_INDEX_ONLY);
1379
 
      }
1380
 
      if (n_marked ==((Item_cond*)cond)->argument_list()->elements)
1381
 
        cond->marker= ICP_COND_USES_INDEX_ONLY;
1382
 
      new_cond->quick_fix_field();
1383
 
      new_cond->top_level_item();
1384
 
      return new_cond;
1385
 
    }
1386
 
  }
1387
 
 
1388
 
  if (!uses_index_fields_only(cond, table, keyno, other_tbls_ok))
1389
 
    return (COND*) 0;
1390
 
  cond->marker= ICP_COND_USES_INDEX_ONLY;
1391
 
  return cond;
1392
 
}
1393
 
 
1394
 
 
1395
 
static Item *make_cond_remainder(Item *cond, bool exclude_index)
1396
 
{
1397
 
  if (exclude_index && cond->marker == ICP_COND_USES_INDEX_ONLY)
1398
 
    return 0; /* Already checked */
1399
 
 
1400
 
  if (cond->type() == Item::COND_ITEM)
1401
 
  {
1402
 
    table_map tbl_map= 0;
1403
 
    if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
1404
 
    {
1405
 
      /* Create new top level AND item */
1406
 
      Item_cond_and *new_cond=new Item_cond_and;
1407
 
      if (!new_cond)
1408
 
        return (COND*) 0;
1409
 
      List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
1410
 
      Item *item;
1411
 
      while ((item=li++))
1412
 
      {
1413
 
        Item *fix= make_cond_remainder(item, exclude_index);
1414
 
        if (fix)
1415
 
        {
1416
 
          new_cond->argument_list()->push_back(fix);
1417
 
          tbl_map |= fix->used_tables();
1418
 
        }
1419
 
      }
1420
 
      switch (new_cond->argument_list()->elements) {
1421
 
      case 0:
1422
 
        return (COND*) 0;
1423
 
      case 1:
1424
 
        return new_cond->argument_list()->head();
1425
 
      default:
1426
 
        new_cond->quick_fix_field();
1427
 
        ((Item_cond*)new_cond)->used_tables_cache= tbl_map;
1428
 
        return new_cond;
1429
 
      }
1430
 
    }
1431
 
    else /* It's OR */
1432
 
    {
1433
 
      Item_cond_or *new_cond=new Item_cond_or;
1434
 
      if (!new_cond)
1435
 
        return (COND*) 0;
1436
 
      List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
1437
 
      Item *item;
1438
 
      while ((item=li++))
1439
 
      {
1440
 
        Item *fix= make_cond_remainder(item, false);
1441
 
        if (!fix)
1442
 
          return (COND*) 0;
1443
 
        new_cond->argument_list()->push_back(fix);
1444
 
        tbl_map |= fix->used_tables();
1445
 
      }
1446
 
      new_cond->quick_fix_field();
1447
 
      ((Item_cond*)new_cond)->used_tables_cache= tbl_map;
1448
 
      new_cond->top_level_item();
1449
 
      return new_cond;
1450
 
    }
1451
 
  }
1452
 
  return cond;
1453
 
}
1454
1208
 
1455
1209
/**
1456
1210
  cleanup JoinTable.
1482
1236
  read_record.end_read_record();
1483
1237
}
1484
1238
 
1485
 
bool only_eq_ref_tables(Join *join,order_st *order,table_map tables)
 
1239
bool only_eq_ref_tables(Join *join,Order *order,table_map tables)
1486
1240
{
1487
1241
  for (JoinTable **tab=join->map2table ; tables ; tab++, tables>>=1)
1488
1242
  {
1511
1265
  SELECT * FROM t1,t2 WHERE t1.a=t2.a ORDER BY t2.b,t1.a
1512
1266
  @endcode
1513
1267
*/
1514
 
bool eq_ref_table(Join *join, order_st *start_order, JoinTable *tab)
 
1268
bool eq_ref_table(Join *join, Order *start_order, JoinTable *tab)
1515
1269
{
1516
1270
  if (tab->cached_eq_ref_table)                 // If cached
1517
1271
    return tab->eq_ref_table;
1530
1284
  {
1531
1285
    if (! (*ref_item)->const_item())
1532
1286
    {                                           // Not a const ref
1533
 
      order_st *order;
 
1287
      Order *order;
1534
1288
      for (order=start_order ; order ; order=order->next)
1535
1289
      {
1536
1290
        if ((*ref_item)->eq(order->item[0],0))
4500
4254
  @retval
4501
4255
    -1   Reverse key can be used
4502
4256
*/
4503
 
static int test_if_order_by_key(order_st *order, Table *table, uint32_t idx, uint32_t *used_key_parts)
 
4257
static int test_if_order_by_key(Order *order, Table *table, uint32_t idx, uint32_t *used_key_parts)
4504
4258
{
4505
4259
  KeyPartInfo *key_part= NULL;
4506
4260
  KeyPartInfo *key_part_end= NULL;
4606
4360
    - MAX_KEY                   If we can't use other key
4607
4361
    - the number of found key   Otherwise
4608
4362
*/
4609
 
static uint32_t test_if_subkey(order_st *order,
 
4363
static uint32_t test_if_subkey(Order *order,
4610
4364
                               Table *table,
4611
4365
                               uint32_t ref,
4612
4366
                               uint32_t ref_key_parts,
4708
4462
*/
4709
4463
bool find_field_in_order_list (Field *field, void *data)
4710
4464
{
4711
 
  order_st *group= (order_st *) data;
 
4465
  Order *group= (Order *) data;
4712
4466
  bool part_found= 0;
4713
 
  for (order_st *tmp_group= group; tmp_group; tmp_group=tmp_group->next)
 
4467
  for (Order *tmp_group= group; tmp_group; tmp_group=tmp_group->next)
4714
4468
  {
4715
4469
    Item *item= (*tmp_group->item)->real_item();
4716
4470
    if (item->type() == Item::FIELD_ITEM &&
4780
4534
  @retval
4781
4535
    1    We can use an index.
4782
4536
*/
4783
 
bool test_if_skip_sort_order(JoinTable *tab, order_st *order, ha_rows select_limit, bool no_changes, const key_map *map)
 
4537
bool test_if_skip_sort_order(JoinTable *tab, Order *order, ha_rows select_limit, bool no_changes, const key_map *map)
4784
4538
{
4785
4539
  int32_t ref_key;
4786
4540
  uint32_t ref_key_parts;
4797
4551
  */
4798
4552
  usable_keys= *map;
4799
4553
 
4800
 
  for (order_st *tmp_order=order; tmp_order ; tmp_order=tmp_order->next)
 
4554
  for (Order *tmp_order=order; tmp_order ; tmp_order=tmp_order->next)
4801
4555
  {
4802
4556
    Item *item= (*tmp_order->item)->real_item();
4803
4557
    if (item->type() != Item::FIELD_ITEM)
5223
4977
    -1          Some fatal error
5224
4978
    1           No records
5225
4979
*/
5226
 
int create_sort_index(Session *session, Join *join, order_st *order, ha_rows filesort_limit, ha_rows select_limit, bool is_order_by)
 
4980
int create_sort_index(Session *session, Join *join, Order *order, ha_rows filesort_limit, ha_rows select_limit, bool is_order_by)
5227
4981
{
5228
4982
  uint32_t length= 0;
5229
4983
  ha_rows examined_rows;
5250
5004
                              is_order_by ?  &table->keys_in_use_for_order_by :
5251
5005
                              &table->keys_in_use_for_group_by))
5252
5006
    return(0);
5253
 
  for (order_st *ord= join->order; ord; ord= ord->next)
 
5007
  for (Order *ord= join->order; ord; ord= ord->next)
5254
5008
    length++;
5255
5009
  if (!(join->sortorder=
5256
5010
        make_unireg_sortorder(order, &length, join->sortorder)))
5508
5262
  return(1);
5509
5263
}
5510
5264
 
5511
 
SortField *make_unireg_sortorder(order_st *order, uint32_t *length, SortField *sortorder)
 
5265
SortField *make_unireg_sortorder(Order *order, uint32_t *length, SortField *sortorder)
5512
5266
{
5513
5267
  uint32_t count;
5514
5268
  SortField *sort,*pos;
5515
5269
 
5516
5270
  count=0;
5517
 
  for (order_st *tmp = order; tmp; tmp=tmp->next)
 
5271
  for (Order *tmp = order; tmp; tmp=tmp->next)
5518
5272
    count++;
5519
5273
  if (!sortorder)
5520
5274
    sortorder= (SortField*) memory::sql_alloc(sizeof(SortField) *
5639
5393
static bool find_order_in_list(Session *session, 
5640
5394
                               Item **ref_pointer_array, 
5641
5395
                               TableList *tables,
5642
 
                               order_st *order,
 
5396
                               Order *order,
5643
5397
                               List<Item> &fields,
5644
5398
                               List<Item> &all_fields,
5645
5399
                               bool is_group_field)
5778
5532
                TableList *tables,
5779
5533
                            List<Item> &fields,
5780
5534
                List<Item> &all_fields,
5781
 
                order_st *order)
 
5535
                Order *order)
5782
5536
{
5783
5537
  session->where="order clause";
5784
5538
  for (; order; order=order->next)
5820
5574
                TableList *tables,
5821
5575
                      List<Item> &fields,
5822
5576
                List<Item> &all_fields,
5823
 
                order_st *order,
 
5577
                Order *order,
5824
5578
                      bool *hidden_group_fields)
5825
5579
{
5826
5580
  *hidden_group_fields=0;
5827
 
  order_st *ord;
 
5581
  Order *ord;
5828
5582
 
5829
5583
  if (!order)
5830
5584
    return 0;                           /* Everything is ok */
5914
5668
  Try to use the fields in the order given by 'order' to allow one to
5915
5669
  optimize away 'order by'.
5916
5670
*/
5917
 
order_st *create_distinct_group(Session *session,
 
5671
Order *create_distinct_group(Session *session,
5918
5672
                                Item **ref_pointer_array,
5919
 
                                order_st *order_list,
 
5673
                                Order *order_list,
5920
5674
                                List<Item> &fields,
5921
5675
                                List<Item> &,
5922
5676
                                bool *all_order_by_fields_used)
5923
5677
{
5924
5678
  List_iterator<Item> li(fields);
5925
5679
  Item *item;
5926
 
  order_st *order,*group,**prev;
 
5680
  Order *order,*group,**prev;
5927
5681
 
5928
5682
  *all_order_by_fields_used= 1;
5929
5683
  while ((item=li++))
5934
5688
  {
5935
5689
    if (order->in_field_list)
5936
5690
    {
5937
 
      order_st *ord=(order_st*) session->memdup((char*) order,sizeof(order_st));
 
5691
      Order *ord=(Order*) session->memdup((char*) order,sizeof(Order));
5938
5692
      if (!ord)
5939
5693
        return 0;
5940
5694
      *prev=ord;
5954
5708
        Don't put duplicate columns from the SELECT list into the
5955
5709
        GROUP BY list.
5956
5710
      */
5957
 
      order_st *ord_iter;
 
5711
      Order *ord_iter;
5958
5712
      for (ord_iter= group; ord_iter; ord_iter= ord_iter->next)
5959
5713
        if ((*ord_iter->item)->eq(item, 1))
5960
5714
          goto next_item;
5961
5715
 
5962
 
      order_st *ord=(order_st*) session->calloc(sizeof(order_st));
 
5716
      Order *ord=(Order*) session->calloc(sizeof(Order));
5963
5717
      if (!ord)
5964
5718
        return 0;
5965
5719
 
6158
5912
        {
6159
5913
          copy->set(tmp, item->result_field);
6160
5914
          item->result_field->move_field(copy->to_ptr,copy->to_null_ptr,1);
6161
 
#ifdef HAVE_purify
 
5915
#ifdef HAVE_VALGRIND
6162
5916
          copy->to_ptr[copy->from_length]= 0;
6163
5917
#endif
6164
5918
          copy++;
6495
6249
  @retval
6496
6250
    1   on error
6497
6251
*/
6498
 
bool change_group_ref(Session *session, Item_func *expr, order_st *group_list, bool *changed)
 
6252
bool change_group_ref(Session *session, Item_func *expr, Order *group_list, bool *changed)
6499
6253
{
6500
6254
  if (expr->arg_count)
6501
6255
  {
6509
6263
      Item *item= *arg;
6510
6264
      if (item->type() == Item::FIELD_ITEM || item->type() == Item::REF_ITEM)
6511
6265
      {
6512
 
        order_st *group_tmp;
 
6266
        Order *group_tmp;
6513
6267
        for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
6514
6268
        {
6515
6269
          if (item->eq(*group_tmp->item,0))
6661
6415
  if (group_list.elements)
6662
6416
  {
6663
6417
    str->append(STRING_WITH_LEN(" group by "));
6664
 
    print_order(str, (order_st *) group_list.first, query_type);
 
6418
    print_order(str, (Order *) group_list.first, query_type);
6665
6419
    switch (olap)
6666
6420
    {
6667
6421
      case CUBE_TYPE:
6692
6446
  if (order_list.elements)
6693
6447
  {
6694
6448
    str->append(STRING_WITH_LEN(" order by "));
6695
 
    print_order(str, (order_st *) order_list.first, query_type);
 
6449
    print_order(str, (Order *) order_list.first, query_type);
6696
6450
  }
6697
6451
 
6698
6452
  // limit