summaryrefslogtreecommitdiff
path: root/sql/item_subselect.h
blob: aa01f571a3df1b9f5a3e396d7641fb79fc7ce224 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
#ifndef ITEM_SUBSELECT_INCLUDED
#define ITEM_SUBSELECT_INCLUDED

/* Copyright (c) 2002, 2011, Oracle and/or its affiliates.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; version 2 of the License.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA */

/* subselect Item */

#ifdef USE_PRAGMA_INTERFACE
#pragma interface			/* gcc class implementation */
#endif

#include <queues.h>

class st_select_lex;
class st_select_lex_unit;
class JOIN;
class select_result_interceptor;
class subselect_engine;
class subselect_hash_sj_engine;
class Item_bool_func2;
class Comp_creator;

typedef class st_select_lex SELECT_LEX;

/**
  Convenience typedef used in this file, and further used by any files
  including this file.
*/
typedef Comp_creator* (*chooser_compare_func_creator)(bool invert);
class Cached_item;

/* base class for subselects */

class Item_subselect :public Item_result_field,
                      protected Used_tables_and_const_cache
{
  bool value_assigned;   /* value already assigned to subselect */
  bool own_engine;  /* the engine was not taken from other Item_subselect */
protected:
  /* thread handler, will be assigned in fix_fields only */
  THD *thd;
  /* old engine if engine was changed */
  subselect_engine *old_engine;
  /* allowed number of columns (1 for single value subqueries) */
  uint max_columns;
  /* where subquery is placed */
  enum_parsing_place parsing_place;
  /* work with 'substitution' */
  bool have_to_be_excluded;
  
  bool inside_first_fix_fields;
  bool done_first_fix_fields;
  Item *expr_cache;
  /*
    Set to TRUE if at optimization or execution time we determine that this
    item's value is a constant. We need this member because it is not possible
    to substitute 'this' with a constant item.
  */
  bool forced_const;
#ifndef DBUG_OFF
  /* Count the number of times this subquery predicate has been executed. */
  uint exec_counter;
#endif
public:
  /* 
    Used inside Item_subselect::fix_fields() according to this scenario:
      > Item_subselect::fix_fields
        > engine->prepare
          > child_join->prepare
            (Here we realize we need to do the rewrite and set
             substitution= some new Item, eg. Item_in_optimizer )
          < child_join->prepare
        < engine->prepare
        *ref= substitution;
        substitution= NULL;
      < Item_subselect::fix_fields
  */
  /* TODO make this protected member again. */
  Item *substitution;
  /* engine that perform execution of subselect (single select or union) */
  /* TODO make this protected member again. */
  subselect_engine *engine;
  /* unit of subquery */
  st_select_lex_unit *unit;
  /* Cached buffers used when calling filesort in sub queries */
  Filesort_buffer filesort_buffer;
  LEX_STRING sortbuffer;
  /* A reference from inside subquery predicate to somewhere outside of it */
  class Ref_to_outside : public Sql_alloc
  {
  public:
    st_select_lex *select; /* Select where the reference is pointing to */
    /* 
      What is being referred. This may be NULL when we're referring to an
      aggregate function.
    */ 
    Item *item; 
  };
  /*
    References from within this subquery to somewhere outside of it (i.e. to
    parent select, grandparent select, etc)
  */
  List<Ref_to_outside> upper_refs;
  st_select_lex *parent_select;

  /*
   TRUE<=>Table Elimination has made it redundant to evaluate this select
          (and so it is not part of QEP, etc)
  */
  bool eliminated;
  
  /* subquery is transformed */
  bool changed;

  /* TRUE <=> The underlying SELECT is correlated w.r.t some ancestor select */
  bool is_correlated;

  /* 
    TRUE <=> the subquery contains a recursive reference in the FROM list
    of one of its selects. In this case some of subquery optimization
    strategies cannot be applied for the subquery;
  */
  bool with_recursive_reference; 

  enum subs_type {UNKNOWN_SUBS, SINGLEROW_SUBS,
		  EXISTS_SUBS, IN_SUBS, ALL_SUBS, ANY_SUBS};

  Item_subselect(THD *thd);

  virtual subs_type substype() { return UNKNOWN_SUBS; }
  bool is_in_predicate()
  {
    return (substype() == Item_subselect::IN_SUBS ||
            substype() == Item_subselect::ALL_SUBS ||
            substype() == Item_subselect::ANY_SUBS);
  }

  /*
    We need this method, because some compilers do not allow 'this'
    pointer in constructor initialization list, but we need to pass a pointer
    to subselect Item class to select_result_interceptor's constructor.
  */
  virtual void init (st_select_lex *select_lex,
		     select_result_interceptor *result);

  ~Item_subselect();
  void cleanup();
  virtual void reset()
  {
    eliminated= FALSE;
    null_value= 1;
  }
  /**
    Set the subquery result to a default value consistent with the semantics of
    the result row produced for queries with implicit grouping.
  */
  void no_rows_in_result()= 0;
  virtual bool select_transformer(JOIN *join);
  bool assigned() { return value_assigned; }
  void assigned(bool a) { value_assigned= a; }
  enum Type type() const;
  bool is_null()
  {
    update_null_value();
    return null_value;
  }
  bool fix_fields(THD *thd, Item **ref);
  bool mark_as_dependent(THD *thd, st_select_lex *select, Item *item);
  void fix_after_pullout(st_select_lex *new_parent, Item **ref);
  void recalc_used_tables(st_select_lex *new_parent, bool after_pullout);
  virtual bool exec();
  /*
    If subquery optimization or execution determines that the subquery has
    an empty result, mark the subquery predicate as a constant value.
  */
  void make_const()
  { 
    used_tables_cache= 0;
    const_item_cache= 0;
    forced_const= TRUE; 
  }
  virtual void fix_length_and_dec();
  table_map used_tables() const;
  table_map not_null_tables() const { return 0; }
  bool const_item() const;
  inline table_map get_used_tables_cache() { return used_tables_cache; }
  Item *get_tmp_table_item(THD *thd);
  void update_used_tables();
  virtual void print(String *str, enum_query_type query_type);
  virtual bool have_guarded_conds() { return FALSE; }
  bool change_engine(subselect_engine *eng)
  {
    old_engine= engine;
    engine= eng;
    return eng == 0;
  }
  bool engine_changed(subselect_engine *eng) { return engine != eng; }
  /*
    True if this subquery has been already evaluated. Implemented only for
    single select and union subqueries only.
  */
  bool is_evaluated() const;
  bool is_uncacheable() const;
  bool is_expensive();

  /*
    Used by max/min subquery to initialize value presence registration
    mechanism. Engine call this method before rexecution query.
  */
  virtual void reset_value_registration() {}
  enum_parsing_place place() { return parsing_place; }
  bool walk(Item_processor processor, bool walk_subquery, void *arg);
  bool mark_as_eliminated_processor(void *arg);
  bool eliminate_subselect_processor(void *arg);
  bool set_fake_select_as_master_processor(void *arg);
  bool enumerate_field_refs_processor(void *arg);
  bool check_vcol_func_processor(void *arg) 
  {
    return mark_unsupported_function("select ...", arg, VCOL_IMPOSSIBLE);
  }
  /**
    Callback to test if an IN predicate is expensive.

    @notes
    The return value affects the behavior of make_cond_for_table().

    @retval TRUE  if the predicate is expensive
    @retval FALSE otherwise
  */
  bool is_expensive_processor(void *arg) { return is_expensive(); }

  /**
    Get the SELECT_LEX structure associated with this Item.
    @return the SELECT_LEX structure associated with this Item
  */
  st_select_lex* get_select_lex();
  virtual bool expr_cache_is_needed(THD *);
  virtual void get_cache_parameters(List<Item> &parameters);
  virtual bool is_subquery_processor (void *opt_arg) { return 1; }
  bool exists2in_processor(void *opt_arg) { return 0; }
  bool limit_index_condition_pushdown_processor(void *opt_arg) 
  {
    return TRUE;
  }

  void init_expr_cache_tracker(THD *thd);
  
  Item* build_clone(THD *thd, MEM_ROOT *mem_root) { return 0; }
  Item* get_copy(THD *thd, MEM_ROOT *mem_root) { return 0; }


  friend class select_result_interceptor;
  friend class Item_in_optimizer;
  friend bool Item_field::fix_fields(THD *, Item **);
  friend int  Item_field::fix_outer_field(THD *, Field **, Item **);
  friend bool Item_ref::fix_fields(THD *, Item **);
  friend void mark_select_range_as_dependent(THD*,
                                             st_select_lex*, st_select_lex*,
                                             Field*, Item*, Item_ident*);
  friend bool convert_join_subqueries_to_semijoins(JOIN *join);
};

/* single value subselect */

class Item_cache;
class Item_singlerow_subselect :public Item_subselect
{
protected:
  Item_cache *value, **row;
public:
  Item_singlerow_subselect(THD *thd_arg, st_select_lex *select_lex);
  Item_singlerow_subselect(THD *thd_arg): Item_subselect(thd_arg), value(0), row (0)
  {}

  void cleanup();
  subs_type substype() { return SINGLEROW_SUBS; }

  void reset();
  void no_rows_in_result();
  bool select_transformer(JOIN *join);
  void store(uint i, Item* item);
  double val_real();
  longlong val_int ();
  String *val_str (String *);
  my_decimal *val_decimal(my_decimal *);
  bool val_bool();
  bool get_date(MYSQL_TIME *ltime, ulonglong fuzzydate);
  enum Item_result result_type() const;
  enum Item_result cmp_type() const;
  enum_field_types field_type() const;
  void fix_length_and_dec();

  uint cols();
  Item* element_index(uint i) { return reinterpret_cast<Item*>(row[i]); }
  Item** addr(uint i) { return (Item**)row + i; }
  bool check_cols(uint c);
  bool null_inside();
  void bring_value();

  /**
    This method is used to implement a special case of semantic tree
    rewriting, mandated by a SQL:2003 exception in the specification.
    The only caller of this method is handle_sql2003_note184_exception(),
    see the code there for more details.
    Note that this method breaks the object internal integrity, by
    removing it's association with the corresponding SELECT_LEX,
    making this object orphan from the parse tree.
    No other method, beside the destructor, should be called on this
    object, as it is now invalid.
    @return the SELECT_LEX structure that was given in the constructor.
  */
  st_select_lex* invalidate_and_restore_select_lex();

  Item* expr_cache_insert_transformer(THD *thd, uchar *unused);

  friend class select_singlerow_subselect;
};

/* used in static ALL/ANY optimization */
class select_max_min_finder_subselect;
class Item_maxmin_subselect :public Item_singlerow_subselect
{
protected:
  bool max;
  bool was_values;  // Set if we have found at least one row
public:
  Item_maxmin_subselect(THD *thd, Item_subselect *parent,
			st_select_lex *select_lex, bool max);
  virtual void print(String *str, enum_query_type query_type);
  void cleanup();
  bool any_value() { return was_values; }
  void register_value() { was_values= TRUE; }
  void reset_value_registration() { was_values= FALSE; }
  void no_rows_in_result();
};

/* exists subselect */

class Item_exists_subselect :public Item_subselect
{
protected:
  Item_func_not *upper_not;
  bool value; /* value of this item (boolean: exists/not-exists) */
  bool abort_on_null;

  void init_length_and_dec();
  bool select_prepare_to_be_in();

public:
  /*
    Used by subquery optimizations to keep track about in which clause this
    subquery predicate is located: 
      NO_JOIN_NEST      - the predicate is an AND-part of the WHERE
      join nest pointer - the predicate is an AND-part of ON expression
                          of a join nest   
      NULL              - for all other locations
  */
  TABLE_LIST *emb_on_expr_nest;
  /**
    Reference on the Item_in_optimizer wrapper of this subquery
  */
  Item_in_optimizer *optimizer;
  /* true if we got this from EXISTS or to IN */
  bool exists_transformed;

  Item_exists_subselect(THD *thd_arg, st_select_lex *select_lex);
  Item_exists_subselect(THD *thd_arg):
    Item_subselect(thd_arg), upper_not(NULL), abort_on_null(0),
    emb_on_expr_nest(NULL), optimizer(0), exists_transformed(0)
  {}

  subs_type substype() { return EXISTS_SUBS; }
  void reset() 
  {
    eliminated= FALSE;
    value= 0;
  }
  void no_rows_in_result();

  enum Item_result result_type() const { return INT_RESULT;}
  enum_field_types field_type() const { return MYSQL_TYPE_LONGLONG; }
  longlong val_int();
  double val_real();
  String *val_str(String*);
  my_decimal *val_decimal(my_decimal *);
  bool val_bool();
  bool fix_fields(THD *thd, Item **ref);
  void fix_length_and_dec();
  void print(String *str, enum_query_type query_type);
  bool select_transformer(JOIN *join);
  void top_level_item() { abort_on_null=1; }
  inline bool is_top_level_item() { return abort_on_null; }
  bool exists2in_processor(void *opt_arg);

  Item* expr_cache_insert_transformer(THD *thd, uchar *unused);

  void mark_as_condition_AND_part(TABLE_LIST *embedding)
  {
    emb_on_expr_nest= embedding;
  }
  virtual void under_not(Item_func_not *upper) { upper_not= upper; };

  void set_exists_transformed() { exists_transformed= TRUE; }

  friend class select_exists_subselect;
  friend class subselect_uniquesubquery_engine;
  friend class subselect_indexsubquery_engine;
};


TABLE_LIST * const NO_JOIN_NEST=(TABLE_LIST*)0x1;

/*
  Possible methods to execute an IN predicate. These are set by the optimizer
  based on user-set optimizer switches, semantic analysis and cost comparison.
*/
#define SUBS_NOT_TRANSFORMED 0 /* No execution method was chosen for this IN. */
/* The Final decision about the strategy is made. */
#define SUBS_STRATEGY_CHOSEN 1
#define SUBS_SEMI_JOIN 2       /* IN was converted to semi-join. */
#define SUBS_IN_TO_EXISTS 4    /* IN was converted to correlated EXISTS. */
#define SUBS_MATERIALIZATION 8 /* Execute IN via subquery materialization. */
/* Partial matching substrategies of MATERIALIZATION. */
#define SUBS_PARTIAL_MATCH_ROWID_MERGE 16
#define SUBS_PARTIAL_MATCH_TABLE_SCAN 32
/* ALL/ANY will be transformed with max/min optimization */
/*   The subquery has not aggregates, transform it into a MAX/MIN query. */
#define SUBS_MAXMIN_INJECTED 64
/*   The subquery has aggregates, use a special max/min subselect engine. */
#define SUBS_MAXMIN_ENGINE 128


/**
  Representation of IN subquery predicates of the form
  "left_expr IN (SELECT ...)".

  @details
  This class has: 
   - A "subquery execution engine" (as a subclass of Item_subselect) that allows
     it to evaluate subqueries. (and this class participates in execution by
     having was_null variable where part of execution result is stored.
   - Transformation methods (todo: more on this).

  This class is not used directly, it is "wrapped" into Item_in_optimizer
  which provides some small bits of subquery evaluation.
*/

class Item_in_subselect :public Item_exists_subselect
{
protected:
  /*
    Cache of the left operand of the subquery predicate. Allocated in the
    runtime memory root, for each execution, thus need not be freed.
  */
  List<Cached_item> *left_expr_cache;
  bool first_execution;

  /*
    expr & optimizer used in subselect rewriting to store Item for
    all JOIN in UNION
  */
  Item *expr;
  bool was_null;
  /* A bitmap of possible execution strategies for an IN predicate. */
  uchar in_strategy;
protected:
  /* Used to trigger on/off conditions that were pushed down to subselect */
  bool *pushed_cond_guards;
  Comp_creator *func;

protected:
  bool init_cond_guards();
  bool select_in_like_transformer(JOIN *join);
  bool single_value_transformer(JOIN *join);
  bool row_value_transformer(JOIN * join);
  bool fix_having(Item *having, st_select_lex *select_lex);
  bool create_single_in_to_exists_cond(JOIN * join,
                                       Item **where_item,
                                       Item **having_item);
  bool create_row_in_to_exists_cond(JOIN * join,
                                    Item **where_item,
                                    Item **having_item);
public:
  Item *left_expr;
  /*
    Important for PS/SP: left_expr_orig is the item that left_expr originally
    pointed at. That item is allocated on the statement arena, while
    left_expr could later be changed to something on the execution arena.
  */
  Item *left_expr_orig;
  /* Priority of this predicate in the convert-to-semi-join-nest process. */
  int sj_convert_priority;
  /*
    Types of left_expr and subquery's select list allow to perform subquery
    materialization. Currently, we set this to FALSE when it as well could
    be TRUE. This is to be properly addressed with fix for BUG#36752.
  */
  bool types_allow_materialization;

  /* 
    Same as above, but they also allow to scan the materialized table. 
  */
  bool sjm_scan_allowed;

  /* 
    JoinTaB Materialization (JTBM) members
  */
  
  /* 
    TRUE <=> This subselect has been converted into non-mergeable semi-join
    table.
  */
  bool is_jtbm_merged;
  
  /* (Applicable if is_jtbm_merged==TRUE) Time required to run the materialized join */
  double jtbm_read_time;

  /* (Applicable if is_jtbm_merged==TRUE) Number of output rows in materialized join */
  double jtbm_record_count;   
  
  /*
    (Applicable if is_jtbm_merged==TRUE) TRUE <=> The materialized subselect is
    a degenerate subselect which produces 0 or 1 rows, which we know at
    optimization phase.
    Examples:
    1. subquery has "Impossible WHERE": 

      SELECT * FROM ot WHERE ot.column IN (SELECT it.col FROM it WHERE 2 > 3)
    
    2. Subquery produces one row which opt_sum.cc is able to get with one lookup:

      SELECT * FROM ot WHERE ot.column IN (SELECT MAX(it.key_col) FROM it)
  */
  bool is_jtbm_const_tab;
  
  /* 
    (Applicable if is_jtbm_const_tab==TRUE) Whether the subquery has produced 
     the row (or not)
  */
  bool jtbm_const_row_found;
  
  /*
    TRUE<=>this is a flattenable semi-join, false overwise.
  */
  bool is_flattenable_semijoin;

  /*
    TRUE<=>registered in the list of semijoins in outer select
  */
  bool is_registered_semijoin;
  
  /*
    Used to determine how this subselect item is represented in the item tree,
    in case there is a need to locate it there and replace with something else.
    Two options are possible:
      1. This item is there 'as-is'.
      1. This item is wrapped within Item_in_optimizer.
  */
  Item *original_item()
  {
    return (is_flattenable_semijoin && !exists_transformed ?
            (Item*)this :
            (Item*)optimizer);
  }
  
  bool *get_cond_guard(int i)
  {
    return pushed_cond_guards ? pushed_cond_guards + i : NULL;
  }
  void set_cond_guard_var(int i, bool v) 
  { 
    if ( pushed_cond_guards)
      pushed_cond_guards[i]= v;
  }
  bool have_guarded_conds() { return MY_TEST(pushed_cond_guards); }

  Item_func_not_all *upper_item; // point on NOT/NOP before ALL/SOME subquery

  Item_in_subselect(THD *thd_arg, Item * left_expr, st_select_lex *select_lex);
  Item_in_subselect(THD *thd_arg):
    Item_exists_subselect(thd_arg), left_expr_cache(0), first_execution(TRUE),
    in_strategy(SUBS_NOT_TRANSFORMED),
    pushed_cond_guards(NULL), func(NULL), is_jtbm_merged(FALSE),
    is_jtbm_const_tab(FALSE), upper_item(0) {}
  void cleanup();
  subs_type substype() { return IN_SUBS; }
  void reset() 
  {
    eliminated= FALSE;
    value= 0;
    null_value= 0;
    was_null= 0;
  }
  bool select_transformer(JOIN *join);
  bool create_in_to_exists_cond(JOIN *join_arg);
  bool inject_in_to_exists_cond(JOIN *join_arg);

  virtual bool exec();
  longlong val_int();
  double val_real();
  String *val_str(String*);
  my_decimal *val_decimal(my_decimal *);
  void update_null_value () { (void) val_bool(); }
  bool val_bool();
  bool test_limit(st_select_lex_unit *unit);
  void print(String *str, enum_query_type query_type);
  enum precedence precedence() const { return CMP_PRECEDENCE; }
  bool fix_fields(THD *thd, Item **ref);
  void fix_length_and_dec();
  void fix_after_pullout(st_select_lex *new_parent, Item **ref);
  bool const_item() const
  {
    return Item_subselect::const_item() && left_expr->const_item();
  }
  void update_used_tables();
  bool setup_mat_engine();
  bool init_left_expr_cache();
  /* Inform 'this' that it was computed, and contains a valid result. */
  void set_first_execution() { if (first_execution) first_execution= FALSE; }
  bool expr_cache_is_needed(THD *thd);
  inline bool left_expr_has_null();

  void disable_cond_guard_for_const_null_left_expr(int i)
  {
    if (left_expr->const_item() && !left_expr->is_expensive())
    {
      if (left_expr->element_index(i)->is_null())
        set_cond_guard_var(i,FALSE);
    }
  }

  int optimize(double *out_rows, double *cost);
  /*
    Return the identifier that we could use to identify the subquery for the
    user.
  */
  int get_identifier();

  bool test_strategy(uchar strategy)
  { return MY_TEST(in_strategy & strategy); }

  /**
    Test that the IN strategy was chosen for execution. This is so
    when the CHOSEN flag is ON, and there is no other strategy.
  */
  bool test_set_strategy(uchar strategy)
  {
    DBUG_ASSERT(strategy == SUBS_SEMI_JOIN ||
                strategy == SUBS_IN_TO_EXISTS ||
                strategy == SUBS_MATERIALIZATION ||
                strategy == SUBS_PARTIAL_MATCH_ROWID_MERGE ||
                strategy == SUBS_PARTIAL_MATCH_TABLE_SCAN ||
                strategy == SUBS_MAXMIN_INJECTED ||
                strategy == SUBS_MAXMIN_ENGINE);
    return ((in_strategy & SUBS_STRATEGY_CHOSEN) &&
            (in_strategy & ~SUBS_STRATEGY_CHOSEN) == strategy);
  }

  bool is_set_strategy()
  { return MY_TEST(in_strategy & SUBS_STRATEGY_CHOSEN); }

  bool has_strategy()
  { return in_strategy != SUBS_NOT_TRANSFORMED; }

  void add_strategy (uchar strategy)
  {
    DBUG_ENTER("Item_in_subselect::add_strategy");
    DBUG_PRINT("enter", ("current: %u  add: %u",
                         (uint) in_strategy, (uint) strategy));
    DBUG_ASSERT(strategy != SUBS_NOT_TRANSFORMED);
    DBUG_ASSERT(!(strategy & SUBS_STRATEGY_CHOSEN));
    /*
      TODO: PS re-execution breaks this condition, because
      check_and_do_in_subquery_rewrites() is called for each reexecution
      and re-adds the same strategies.
      DBUG_ASSERT(!(in_strategy & SUBS_STRATEGY_CHOSEN));
    */
    in_strategy|= strategy;
    DBUG_VOID_RETURN;
  }

  void reset_strategy(uchar strategy)
  {
    DBUG_ENTER("Item_in_subselect::reset_strategy");
    DBUG_PRINT("enter", ("current: %u  new: %u",
                         (uint) in_strategy, (uint) strategy));
    DBUG_ASSERT(strategy != SUBS_NOT_TRANSFORMED);
    in_strategy= strategy;
    DBUG_VOID_RETURN;
  }

  void set_strategy(uchar strategy)
  {
    DBUG_ENTER("Item_in_subselect::set_strategy");
    DBUG_PRINT("enter", ("current: %u  set: %u",
                         (uint) in_strategy,
                         (uint) (SUBS_STRATEGY_CHOSEN | strategy)));
    /* Check that only one strategy is set for execution. */
    DBUG_ASSERT(strategy == SUBS_SEMI_JOIN ||
                strategy == SUBS_IN_TO_EXISTS ||
                strategy == SUBS_MATERIALIZATION ||
                strategy == SUBS_PARTIAL_MATCH_ROWID_MERGE ||
                strategy == SUBS_PARTIAL_MATCH_TABLE_SCAN ||
                strategy == SUBS_MAXMIN_INJECTED ||
                strategy == SUBS_MAXMIN_ENGINE);
    in_strategy= (SUBS_STRATEGY_CHOSEN | strategy);
    DBUG_VOID_RETURN;
  }
  bool exists2in_processor(void *opt_arg __attribute__((unused)))
  {
    return 0;
  };

  friend class Item_ref_null_helper;
  friend class Item_is_not_null_test;
  friend class Item_in_optimizer;
  friend class subselect_indexsubquery_engine;
  friend class subselect_hash_sj_engine;
  friend class subselect_partial_match_engine;
  friend class Item_exists_subselect;
};


/* ALL/ANY/SOME subselect */
class Item_allany_subselect :public Item_in_subselect
{
public:
  chooser_compare_func_creator func_creator;
  bool all;

  Item_allany_subselect(THD *thd_arg, Item * left_expr,
                        chooser_compare_func_creator fc,
                        st_select_lex *select_lex, bool all);

  void cleanup();
  // only ALL subquery has upper not
  subs_type substype() { return all?ALL_SUBS:ANY_SUBS; }
  bool select_transformer(JOIN *join);
  void create_comp_func(bool invert) { func= func_creator(invert); }
  void print(String *str, enum_query_type query_type);
  bool is_maxmin_applicable(JOIN *join);
  bool transform_into_max_min(JOIN *join);
  void no_rows_in_result();
};


class subselect_engine: public Sql_alloc
{
protected:
  select_result_interceptor *result; /* results storage class */
  THD *thd; /* pointer to current THD */
  Item_subselect *item; /* item, that use this engine */
  enum Item_result res_type; /* type of results */
  enum Item_result cmp_type; /* how to compare the results */
  enum_field_types res_field_type; /* column type of the results */
  bool maybe_null; /* may be null (first item in select) */
public:

  enum enum_engine_type {ABSTRACT_ENGINE, SINGLE_SELECT_ENGINE,
                         UNION_ENGINE, UNIQUESUBQUERY_ENGINE,
                         INDEXSUBQUERY_ENGINE, HASH_SJ_ENGINE,
                         ROWID_MERGE_ENGINE, TABLE_SCAN_ENGINE};

  subselect_engine(Item_subselect *si,
                   select_result_interceptor *res):
    thd(NULL)
  {
    result= res;
    item= si;
    cmp_type= res_type= STRING_RESULT;
    res_field_type= MYSQL_TYPE_VAR_STRING;
    maybe_null= 0;
  }
  virtual ~subselect_engine() {}; // to satisfy compiler
  virtual void cleanup()= 0;

  /*
    Also sets "thd" for subselect_engine::result.
    Should be called before prepare().
  */
  void set_thd(THD *thd_arg);
  THD * get_thd() { return thd ? thd : current_thd; }
  virtual int prepare(THD *)= 0;
  virtual void fix_length_and_dec(Item_cache** row)= 0;
  /*
    Execute the engine

    SYNOPSIS
      exec()

    DESCRIPTION
      Execute the engine. The result of execution is subquery value that is
      either captured by previously set up select_result-based 'sink' or
      stored somewhere by the exec() method itself.

      A required side effect: If at least one pushed-down predicate is
      disabled, subselect_engine->no_rows() must return correct result after 
      the exec() call.

    RETURN
      0 - OK
      1 - Either an execution error, or the engine was "changed", and the
          caller should call exec() again for the new engine.
  */
  virtual int exec()= 0;
  virtual uint cols()= 0; /* return number of columns in select */
  virtual uint8 uncacheable()= 0; /* query is uncacheable */
  enum Item_result type() { return res_type; }
  enum Item_result cmptype() { return cmp_type; }
  enum_field_types field_type() { return res_field_type; }
  virtual void exclude()= 0;
  virtual bool may_be_null() { return maybe_null; };
  virtual table_map upper_select_const_tables()= 0;
  static table_map calc_const_tables(TABLE_LIST *);
  static table_map calc_const_tables(List<TABLE_LIST> &list);
  virtual void print(String *str, enum_query_type query_type)= 0;
  virtual bool change_result(Item_subselect *si,
                             select_result_interceptor *result,
                             bool temp= FALSE)= 0;
  virtual bool no_tables()= 0;
  virtual bool is_executed() const { return FALSE; }
  /* Check if subquery produced any rows during last query execution */
  virtual bool no_rows() = 0;
  virtual enum_engine_type engine_type() { return ABSTRACT_ENGINE; }
  virtual int get_identifier() { DBUG_ASSERT(0); return 0; }
protected:
  void set_row(List<Item> &item_list, Item_cache **row);
};


class subselect_single_select_engine: public subselect_engine
{
  bool prepared;       /* simple subselect is prepared */
  bool executed;       /* simple subselect is executed */
  st_select_lex *select_lex; /* corresponding select_lex */
  JOIN * join; /* corresponding JOIN structure */
public:
  subselect_single_select_engine(st_select_lex *select,
				 select_result_interceptor *result,
				 Item_subselect *item);
  void cleanup();
  int prepare(THD *thd);
  void fix_length_and_dec(Item_cache** row);
  int exec();
  uint cols();
  uint8 uncacheable();
  void exclude();
  table_map upper_select_const_tables();
  void print (String *str, enum_query_type query_type);
  bool change_result(Item_subselect *si,
                     select_result_interceptor *result,
                     bool temp);
  bool no_tables();
  bool may_be_null();
  bool is_executed() const { return executed; }
  bool no_rows();
  virtual enum_engine_type engine_type() { return SINGLE_SELECT_ENGINE; }
  int get_identifier();

  friend class subselect_hash_sj_engine;
  friend class Item_in_subselect;
  friend bool setup_jtbm_semi_joins(JOIN *join, List<TABLE_LIST> *join_list,
                                    Item **join_where);

};


class subselect_union_engine: public subselect_engine
{
  st_select_lex_unit *unit;  /* corresponding unit structure */
public:
  subselect_union_engine(st_select_lex_unit *u,
			 select_result_interceptor *result,
			 Item_subselect *item);
  void cleanup();
  int prepare(THD *);
  void fix_length_and_dec(Item_cache** row);
  int exec();
  uint cols();
  uint8 uncacheable();
  void exclude();
  table_map upper_select_const_tables();
  void print (String *str, enum_query_type query_type);
  bool change_result(Item_subselect *si,
                     select_result_interceptor *result,
                     bool temp= FALSE);
  bool no_tables();
  bool is_executed() const;
  bool no_rows();
  virtual enum_engine_type engine_type() { return UNION_ENGINE; }
};


struct st_join_table;


/*
  A subquery execution engine that evaluates the subquery by doing one index
  lookup in a unique index.

  This engine is used to resolve subqueries in forms
  
    outer_expr IN (SELECT tbl.unique_key FROM tbl WHERE subq_where) 
    
  or, tuple-based:
  
    (oe1, .. oeN) IN (SELECT uniq_key_part1, ... uniq_key_partK
                      FROM tbl WHERE subqwhere) 
  
  i.e. the subquery is a single table SELECT without GROUP BY, aggregate
  functions, etc.
*/

class subselect_uniquesubquery_engine: public subselect_engine
{
protected:
  st_join_table *tab;
  Item *cond; /* The WHERE condition of subselect */
  /* 
    TRUE<=> last execution produced empty set. Valid only when left
    expression is NULL.
  */
  bool empty_result_set;
public:

  // constructor can assign THD because it will be called after JOIN::prepare
  subselect_uniquesubquery_engine(THD *thd_arg, st_join_table *tab_arg,
				  Item_subselect *subs, Item *where)
    :subselect_engine(subs, 0), tab(tab_arg), cond(where)
  {}
  ~subselect_uniquesubquery_engine();
  void cleanup();
  int prepare(THD *);
  void fix_length_and_dec(Item_cache** row);
  int exec();
  uint cols() { return 1; }
  uint8 uncacheable() { return UNCACHEABLE_DEPENDENT_INJECTED; }
  void exclude();
  table_map upper_select_const_tables() { return 0; }
  void print (String *str, enum_query_type query_type);
  bool change_result(Item_subselect *si,
                     select_result_interceptor *result,
                     bool temp= FALSE);
  bool no_tables();
  int index_lookup(); /* TIMOUR: this method needs refactoring. */
  int scan_table();
  bool copy_ref_key(bool skip_constants);
  bool no_rows() { return empty_result_set; }
  virtual enum_engine_type engine_type() { return UNIQUESUBQUERY_ENGINE; }
};


class subselect_indexsubquery_engine: public subselect_uniquesubquery_engine
{
  /* FALSE for 'ref', TRUE for 'ref-or-null'. */
  bool check_null;
  /* 
    The "having" clause. This clause (further reffered to as "artificial
    having") was inserted by subquery transformation code. It contains 
    Item(s) that have a side-effect: they record whether the subquery has 
    produced a row with NULL certain components. We need to use it for cases
    like
      (oe1, oe2) IN (SELECT t.key, t.no_key FROM t1)
    where we do index lookup on t.key=oe1 but need also to check if there
    was a row such that t.no_key IS NULL.
    
    NOTE: This is currently here and not in the uniquesubquery_engine. Ideally
    it should have been in uniquesubquery_engine in order to allow execution of
    subqueries like
    
      (oe1, oe2) IN (SELECT primary_key, non_key_maybe_null_field FROM tbl)

    We could use uniquesubquery_engine for the first component and let
    Item_is_not_null_test( non_key_maybe_null_field) to handle the second.

    However, subqueries like the above are currently not handled by index
    lookup-based subquery engines, the engine applicability check misses
    them: it doesn't switch the engine for case of artificial having and
    [eq_]ref access (only for artifical having + ref_or_null or no having).
    The above example subquery is handled as a full-blown SELECT with eq_ref
    access to one table.

    Due to this limitation, the "artificial having" currently needs to be 
    checked by only in indexsubquery_engine.
  */
  Item *having;
public:

  // constructor can assign THD because it will be called after JOIN::prepare
  subselect_indexsubquery_engine(THD *thd_arg, st_join_table *tab_arg,
				 Item_subselect *subs, Item *where,
                                 Item *having_arg, bool chk_null)
    :subselect_uniquesubquery_engine(thd_arg, tab_arg, subs, where),
     check_null(chk_null),
     having(having_arg)
  {}
  int exec();
  void print (String *str, enum_query_type query_type);
  virtual enum_engine_type engine_type() { return INDEXSUBQUERY_ENGINE; }
};

/*
  This function is actually defined in sql_parse.cc, but it depends on
  chooser_compare_func_creator defined in this file.
 */
Item * all_any_subquery_creator(THD *thd, Item *left_expr,
                                chooser_compare_func_creator cmp,
                                bool all,
                                SELECT_LEX *select_lex);


inline bool Item_subselect::is_evaluated() const
{
  return engine->is_executed();
}


inline bool Item_subselect::is_uncacheable() const
{
  return engine->uncacheable();
}

/**
  Compute an IN predicate via a hash semi-join. This class is responsible for
  the materialization of the subquery, and the selection of the correct and
  optimal execution method (e.g. direct index lookup, or partial matching) for
  the IN predicate.
*/

class subselect_hash_sj_engine : public subselect_engine
{
public:
  /* The table into which the subquery is materialized. */
  TABLE *tmp_table;
  /* TRUE if the subquery was materialized into a temp table. */
  bool is_materialized;
  /*
    The old engine already chosen at parse time and stored in permanent memory.
    Through this member we can re-create and re-prepare materialize_join for
    each execution of a prepared statement. We also reuse the functionality
    of subselect_single_select_engine::[prepare | cols].
  */
  subselect_single_select_engine *materialize_engine;
  /*
    QEP to execute the subquery and materialize its result into a
    temporary table. Created during the first call to exec().
  */
  JOIN *materialize_join;
  /*
    A conjunction of all the equality condtions between all pairs of expressions
    that are arguments of an IN predicate. We need these to post-filter some
    IN results because index lookups sometimes match values that are actually
    not equal to the search key in SQL terms.
  */
  Item_cond_and *semi_join_conds;
  Name_resolution_context *semi_join_conds_context;


  subselect_hash_sj_engine(THD *thd_arg, Item_subselect *in_predicate,
                           subselect_single_select_engine *old_engine)
    : subselect_engine(in_predicate, NULL),
      tmp_table(NULL), is_materialized(FALSE), materialize_engine(old_engine),
      materialize_join(NULL),  semi_join_conds(NULL), lookup_engine(NULL),
      count_partial_match_columns(0), count_null_only_columns(0),
      count_columns_with_nulls(0), strategy(UNDEFINED)
  {}
  ~subselect_hash_sj_engine();

  bool init(List<Item> *tmp_columns, uint subquery_id);
  void cleanup();
  int prepare(THD *);
  int exec();
  void print(String *str, enum_query_type query_type);
  uint cols() { return materialize_engine->cols(); }
  uint8 uncacheable() { return materialize_engine->uncacheable(); }
  table_map upper_select_const_tables() { return 0; }
  bool no_rows() { return !tmp_table->file->stats.records; }
  virtual enum_engine_type engine_type() { return HASH_SJ_ENGINE; }
  /*
    TODO: factor out all these methods in a base subselect_index_engine class
    because all of them have dummy implementations and should never be called.
  */
  void fix_length_and_dec(Item_cache** row);//=>base class
  void exclude(); //=>base class
  //=>base class
  bool change_result(Item_subselect *si,
                     select_result_interceptor *result,
                     bool temp= FALSE);
  bool no_tables();//=>base class

protected:
  /* The engine used to compute the IN predicate. */
  subselect_engine *lookup_engine;
  /* Keyparts of the only non-NULL composite index in a rowid merge. */
  MY_BITMAP non_null_key_parts;
  /* Keyparts of the single column indexes with NULL, one keypart per index. */
  MY_BITMAP partial_match_key_parts;
  uint count_partial_match_columns;
  uint count_null_only_columns;
  uint count_columns_with_nulls;
  /* Possible execution strategies that can be used to compute hash semi-join.*/
  enum exec_strategy {
    UNDEFINED,
    COMPLETE_MATCH, /* Use regular index lookups. */
    PARTIAL_MATCH,  /* Use some partial matching strategy. */
    PARTIAL_MATCH_MERGE, /* Use partial matching through index merging. */
    PARTIAL_MATCH_SCAN,  /* Use partial matching through table scan. */
    IMPOSSIBLE      /* Subquery materialization is not applicable. */
  };
  /* The chosen execution strategy. Computed after materialization. */
  exec_strategy strategy;
  exec_strategy get_strategy_using_schema();
  exec_strategy get_strategy_using_data();
  ulonglong rowid_merge_buff_size(bool has_non_null_key,
                                  bool has_covering_null_row,
                                  MY_BITMAP *partial_match_key_parts);
  void choose_partial_match_strategy(bool has_non_null_key,
                                     bool has_covering_null_row,
                                     MY_BITMAP *partial_match_key_parts);
  bool make_semi_join_conds();
  subselect_uniquesubquery_engine* make_unique_engine();

};


/*
  Distinguish the type of (0-based) row numbers from the type of the index into
  an array of row numbers.
*/
typedef ha_rows rownum_t;


/*
  An Ordered_key is an in-memory table index that allows O(log(N)) time
  lookups of a multi-part key.

  If the index is over a single column, then this column may contain NULLs, and
  the NULLs are stored and tested separately for NULL in O(1) via is_null().
  Multi-part indexes assume that the indexed columns do not contain NULLs.

  TODO:
  = Due to the unnatural assymetry between single and multi-part indexes, it
    makes sense to somehow refactor or extend the class.

  = This class can be refactored into a base abstract interface, and two
    subclasses:
    - one to represent single-column indexes, and
    - another to represent multi-column indexes.
    Such separation would allow slightly more efficient implementation of
    the single-column indexes.
  = The current design requires such indexes to be fully recreated for each
    PS (re)execution, however most of the comprising objects can be reused.
*/

class Ordered_key : public Sql_alloc
{
protected:
  /*
    Index of the key in an array of keys. This index allows to
    construct (sub)sets of keys represented by bitmaps.
  */
  uint keyid;
  /* The table being indexed. */
  TABLE *tbl;
  /* The columns being indexed. */
  Item_field **key_columns;
  /* Number of elements in 'key_columns' (number of key parts). */
  uint key_column_count;
  /*
    An expression, or sequence of expressions that forms the search key.
    The search key is a sequence when it is Item_row. Each element of the
    sequence is accessible via Item::element_index(int i).
  */
  Item *search_key;

/* Value index related members. */
  /*
    The actual value index, consists of a sorted sequence of row numbers.
  */
  rownum_t *key_buff;
  /* Number of elements in key_buff. */
  ha_rows key_buff_elements;
  /* Current element in 'key_buff'. */
  ha_rows cur_key_idx;
  /*
    Mapping from row numbers to row ids. The element row_num_to_rowid[i]
    contains a buffer with the rowid for the row numbered 'i'.
    The memory for this member is not maintanined by this class because
    all Ordered_key indexes of the same table share the same mapping.
  */
  uchar *row_num_to_rowid;
  /*
    A sequence of predicates to compare the search key with the corresponding
    columns of a table row from the index.
  */
  Item_func_lt **compare_pred;

/* Null index related members. */
  MY_BITMAP null_key;
  /* Count of NULLs per column. */
  ha_rows null_count;
  /* The row number that contains the first NULL in a column. */
  rownum_t min_null_row;
  /* The row number that contains the last NULL in a column. */
  rownum_t max_null_row;

protected:
  bool alloc_keys_buffers();
  /*
    Quick sort comparison function that compares two rows of the same table
    indentfied with their row numbers.
  */
  int cmp_keys_by_row_data(rownum_t a, rownum_t b);
  static int cmp_keys_by_row_data_and_rownum(Ordered_key *key,
                                             rownum_t* a, rownum_t* b);

  int cmp_key_with_search_key(rownum_t row_num);

public:
  Ordered_key(uint keyid_arg, TABLE *tbl_arg,
              Item *search_key_arg, ha_rows null_count_arg,
              ha_rows min_null_row_arg, ha_rows max_null_row_arg,
              uchar *row_num_to_rowid_arg);
  ~Ordered_key();
  void cleanup();
  /* Initialize a multi-column index. */
  bool init(MY_BITMAP *columns_to_index);
  /* Initialize a single-column index. */
  bool init(int col_idx);

  uint get_column_count() { return key_column_count; }
  uint get_keyid() { return keyid; }
  Field *get_field(uint i)
  {
    DBUG_ASSERT(i < key_column_count);
    return key_columns[i]->field;
  }
  rownum_t get_min_null_row() { return min_null_row; }
  rownum_t get_max_null_row() { return max_null_row; }
  MY_BITMAP * get_null_key() { return &null_key; }
  ha_rows get_null_count() { return null_count; }
  /*
    Get the search key element that corresponds to the i-th key part of this
    index.
  */
  Item *get_search_key(uint i)
  {
    return search_key->element_index(key_columns[i]->field->field_index);
  }
  void add_key(rownum_t row_num)
  {
    /* The caller must know how many elements to add. */
    DBUG_ASSERT(key_buff_elements && cur_key_idx < key_buff_elements);
    key_buff[cur_key_idx]= row_num;
    ++cur_key_idx;
  }

  void sort_keys();
  double null_selectivity();

  /*
    Position the current element at the first row that matches the key.
    The key itself is propagated by evaluating the current value(s) of
    this->search_key.
  */
  bool lookup();
  /* Move the current index cursor to the first key. */
  void first()
  {
    DBUG_ASSERT(key_buff_elements);
    cur_key_idx= 0;
  }
  /* TODO */
  bool next_same();
  /* Move the current index cursor to the next key. */
  bool next()
  {
    DBUG_ASSERT(key_buff_elements);
    if (cur_key_idx < key_buff_elements - 1)
    {
      ++cur_key_idx;
      return TRUE;
    }
    return FALSE;
  };
  /* Return the current index element. */
  rownum_t current()
  {
    DBUG_ASSERT(key_buff_elements && cur_key_idx < key_buff_elements);
    return key_buff[cur_key_idx];
  }

  void set_null(rownum_t row_num)
  {
    bitmap_set_bit(&null_key, (uint)row_num);
  }
  bool is_null(rownum_t row_num)
  {
    /*
      Indexes consisting of only NULLs do not have a bitmap buffer at all.
      Their only initialized member is 'n_bits', which is equal to the number
      of temp table rows.
    */
    if (null_count == tbl->file->stats.records)
    {
      DBUG_ASSERT(tbl->file->stats.records == null_key.n_bits);
      return TRUE;
    }
    if (row_num > max_null_row || row_num < min_null_row)
      return FALSE;
    return bitmap_is_set(&null_key, (uint)row_num);
  }
  void print(String *str);
};


class subselect_partial_match_engine : public subselect_engine
{
protected:
  /* The temporary table that contains a materialized subquery. */
  TABLE *tmp_table;
  /*
    The engine used to check whether an IN predicate is TRUE or not. If not
    TRUE, then subselect_rowid_merge_engine further distinguishes between
    FALSE and UNKNOWN.
  */
  subselect_uniquesubquery_engine *lookup_engine;
  /* A list of equalities between each pair of IN operands. */
  List<Item> *equi_join_conds;
  /*
    True if there is an all NULL row in tmp_table. If so, then if there is
    no complete match, there is a guaranteed partial match.
  */
  bool has_covering_null_row;

  /*
    True if all nullable columns of tmp_table consist of only NULL values.
    If so, then if there is a match in the non-null columns, there is a
    guaranteed partial match.
  */
  bool has_covering_null_columns;
  uint count_columns_with_nulls;

protected:
  virtual bool partial_match()= 0;
public:
  subselect_partial_match_engine(subselect_uniquesubquery_engine *engine_arg,
                                 TABLE *tmp_table_arg, Item_subselect *item_arg,
                                 select_result_interceptor *result_arg,
                                 List<Item> *equi_join_conds_arg,
                                 bool has_covering_null_row_arg,
                                 bool has_covering_null_columns_arg,
                                 uint count_columns_with_nulls_arg);
  int prepare(THD *thd_arg) { set_thd(thd_arg); return 0; }
  int exec();
  void fix_length_and_dec(Item_cache**) {}
  uint cols() { /* TODO: what is the correct value? */ return 1; }
  uint8 uncacheable() { return UNCACHEABLE_DEPENDENT; }
  void exclude() {}
  table_map upper_select_const_tables() { return 0; }
  bool change_result(Item_subselect*,
                     select_result_interceptor*,
                     bool temp= FALSE)
  { DBUG_ASSERT(FALSE); return false; }
  bool no_tables() { return false; }
  bool no_rows()
  {
    /*
      TODO: It is completely unclear what is the semantics of this
      method. The current result is computed so that the call to no_rows()
      from Item_in_optimizer::val_int() sets Item_in_optimizer::null_value
      correctly.
    */
    return !(((Item_in_subselect *) item)->null_value);
  }
  void print(String*, enum_query_type);

  friend void subselect_hash_sj_engine::cleanup();
};


class subselect_rowid_merge_engine: public subselect_partial_match_engine
{
protected:
  /*
    Mapping from row numbers to row ids. The rowids are stored sequentially
    in the array - rowid[i] is located in row_num_to_rowid + i * rowid_length.
  */
  uchar *row_num_to_rowid;
  /*
    A subset of all the keys for which there is a match for the same row.
    Used during execution. Computed for each outer reference
  */
  MY_BITMAP matching_keys;
  /*
    The columns of the outer reference that are NULL. Computed for each
    outer reference.
  */
  MY_BITMAP matching_outer_cols;
  /*
    Indexes of row numbers, sorted by <column_value, row_number>. If an
    index may contain NULLs, the NULLs are stored efficiently in a bitmap.

    The indexes are sorted by the selectivity of their NULL sub-indexes, the
    one with the fewer NULLs is first. Thus, if there is any index on
    non-NULL columns, it is contained in keys[0].
  */
  Ordered_key **merge_keys;
  /* The number of elements in merge_keys. */
  uint merge_keys_count;
  /* The NULL bitmaps of merge keys.*/
  MY_BITMAP   **null_bitmaps;
  /*
    An index on all non-NULL columns of 'tmp_table'. The index has the
    logical form: <[v_i1 | ... | v_ik], rownum>. It allows to find the row
    number where the columns c_i1,...,c1_k contain the values v_i1,...,v_ik.
    If such an index exists, it is always the first element of 'merge_keys'.
  */
  Ordered_key *non_null_key;
  /*
    Priority queue of Ordered_key indexes, one per NULLable column.
    This queue is used by the partial match algorithm in method exec().
  */
  QUEUE pq;
protected:
  /*
    Comparison function to compare keys in order of decreasing bitmap
    selectivity.
  */
  static int cmp_keys_by_null_selectivity(Ordered_key **k1, Ordered_key **k2);
  /*
    Comparison function used by the priority queue pq, the 'smaller' key
    is the one with the smaller current row number.
  */
  static int cmp_keys_by_cur_rownum(void *arg, uchar *k1, uchar *k2);

  bool test_null_row(rownum_t row_num);
  bool exists_complementing_null_row(MY_BITMAP *keys_to_complement);
  bool partial_match();
public:
  subselect_rowid_merge_engine(subselect_uniquesubquery_engine *engine_arg,
                               TABLE *tmp_table_arg, uint merge_keys_count_arg,
                               bool has_covering_null_row_arg,
                               bool has_covering_null_columns_arg,
                               uint count_columns_with_nulls_arg,
                               Item_subselect *item_arg,
                               select_result_interceptor *result_arg,
                               List<Item> *equi_join_conds_arg)
    :subselect_partial_match_engine(engine_arg, tmp_table_arg,
                                    item_arg, result_arg, equi_join_conds_arg,
                                    has_covering_null_row_arg,
                                    has_covering_null_columns_arg,
                                    count_columns_with_nulls_arg),
    merge_keys_count(merge_keys_count_arg), non_null_key(NULL)
  {}
  ~subselect_rowid_merge_engine();
  bool init(MY_BITMAP *non_null_key_parts, MY_BITMAP *partial_match_key_parts);
  void cleanup();
  virtual enum_engine_type engine_type() { return ROWID_MERGE_ENGINE; }
};


class subselect_table_scan_engine: public subselect_partial_match_engine
{
protected:
  bool partial_match();
public:
  subselect_table_scan_engine(subselect_uniquesubquery_engine *engine_arg,
                              TABLE *tmp_table_arg, Item_subselect *item_arg,
                              select_result_interceptor *result_arg,
                              List<Item> *equi_join_conds_arg,
                              bool has_covering_null_row_arg,
                              bool has_covering_null_columns_arg,
                              uint count_columns_with_nulls_arg);
  void cleanup();
  virtual enum_engine_type engine_type() { return TABLE_SCAN_ENGINE; }
};
#endif /* ITEM_SUBSELECT_INCLUDED */