1/*
2 Copyright (c) 2011, 2012, Monty Program Ab
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1301 USA */
16
17/*
18 This file contains declarations for implementations
19 of block based join algorithms
20*/
21
22#define JOIN_CACHE_INCREMENTAL_BIT 1
23#define JOIN_CACHE_HASHED_BIT 2
24#define JOIN_CACHE_BKA_BIT 4
25
26/*
27 Categories of data fields of variable length written into join cache buffers.
28 The value of any of these fields is written into cache together with the
29 prepended length of the value.
30*/
31#define CACHE_BLOB 1 /* blob field */
32#define CACHE_STRIPPED 2 /* field stripped of trailing spaces */
33#define CACHE_VARSTR1 3 /* short string value (length takes 1 byte) */
34#define CACHE_VARSTR2 4 /* long string value (length takes 2 bytes) */
35#define CACHE_ROWID 5 /* ROWID field */
36
37/*
38 The CACHE_FIELD structure used to describe fields of records that
39 are written into a join cache buffer from record buffers and backward.
40*/
41typedef struct st_cache_field {
42 uchar *str; /**< buffer from/to where the field is to be copied */
43 uint length; /**< maximal number of bytes to be copied from/to str */
44 /*
45 Field object for the moved field
46 (0 - for a flag field, see JOIN_CACHE::create_flag_fields).
47 */
48 Field *field;
49 uint type; /**< category of the of the copied field (CACHE_BLOB et al.) */
50 /*
51 The number of the record offset value for the field in the sequence
52 of offsets placed after the last field of the record. These
53 offset values are used to access fields referred to from other caches.
54 If the value is 0 then no offset for the field is saved in the
55 trailing sequence of offsets.
56 */
57 uint referenced_field_no;
58 /* The remaining structure fields are used as containers for temp values */
59 uint blob_length; /**< length of the blob to be copied */
60 uint offset; /**< field offset to be saved in cache buffer */
61} CACHE_FIELD;
62
63
64class JOIN_TAB_SCAN;
65
66class EXPLAIN_BKA_TYPE;
67
68/*
69 JOIN_CACHE is the base class to support the implementations of
70 - Block Nested Loop (BNL) Join Algorithm,
71 - Block Nested Loop Hash (BNLH) Join Algorithm,
72 - Batched Key Access (BKA) Join Algorithm.
73
74 The first algorithm is supported by the derived class JOIN_CACHE_BNL,
75 the second algorithm is supported by the derived class JOIN_CACHE_BNLH,
76 while the third algorithm is implemented in two variant supported by
77 the classes JOIN_CACHE_BKA and JOIN_CACHE_BKAH.
78 These three algorithms have a lot in common. Each of them first accumulates
79 the records of the left join operand in a join buffer and then searches for
80 matching rows of the second operand for all accumulated records.
81 For the first two algorithms this strategy saves on logical I/O operations:
82 the entire set of records from the join buffer requires only one look-through
83 of the records provided by the second operand.
84 For the third algorithm the accumulation of records allows to optimize
85 fetching rows of the second operand from disk for some engines (MyISAM,
86 InnoDB), or to minimize the number of round-trips between the Server and
87 the engine nodes.
88*/
89
90class JOIN_CACHE :public Sql_alloc
91{
92
93private:
94
95 /* Size of the offset of a record from the cache */
96 uint size_of_rec_ofs;
97 /* Size of the length of a record in the cache */
98 uint size_of_rec_len;
99 /* Size of the offset of a field within a record in the cache */
100 uint size_of_fld_ofs;
101
102 /* This structure is used only for explain, not for execution */
103 bool for_explain_only;
104
105protected:
106
107 /* 3 functions below actually do not use the hidden parameter 'this' */
108
109 /* Calculate the number of bytes used to store an offset value */
110 uint offset_size(size_t len)
111 { return (len < 256 ? 1 : len < 256*256 ? 2 : 4); }
112
113 /* Get the offset value that takes ofs_sz bytes at the position ptr */
114 ulong get_offset(uint ofs_sz, uchar *ptr)
115 {
116 switch (ofs_sz) {
117 case 1: return uint(*ptr);
118 case 2: return uint2korr(ptr);
119 case 4: return uint4korr(ptr);
120 }
121 return 0;
122 }
123
124 /* Set the offset value ofs that takes ofs_sz bytes at the position ptr */
125 void store_offset(uint ofs_sz, uchar *ptr, ulong ofs)
126 {
127 switch (ofs_sz) {
128 case 1: *ptr= (uchar) ofs; return;
129 case 2: int2store(ptr, (uint16) ofs); return;
130 case 4: int4store(ptr, (uint32) ofs); return;
131 }
132 }
133
134 /*
135 The maximum total length of the fields stored for a record in the cache.
136 For blob fields only the sizes of the blob lengths are taken into account.
137 */
138 uint length;
139
140 /*
141 Representation of the executed multi-way join through which all needed
142 context can be accessed.
143 */
144 JOIN *join;
145
146 /*
147 JOIN_TAB of the first table that can have it's fields in the join cache.
148 That is, tables in the [start_tab, tab) range can have their fields in the
149 join cache.
150 If a join tab in the range represents an SJM-nest, then all tables from the
151 nest can have their fields in the join cache, too.
152 */
153 JOIN_TAB *start_tab;
154
155 /*
156 The total number of flag and data fields that can appear in a record
157 written into the cache. Fields with null values are always skipped
158 to save space.
159 */
160 uint fields;
161
162 /*
163 The total number of flag fields in a record put into the cache. They are
164 used for table null bitmaps, table null row flags, and an optional match
165 flag. Flag fields go before other fields in a cache record with the match
166 flag field placed always at the very beginning of the record.
167 */
168 uint flag_fields;
169
170 /* The total number of blob fields that are written into the cache */
171 uint blobs;
172
173 /*
174 The total number of fields referenced from field descriptors for other join
175 caches. These fields are used to construct key values.
176 When BKA join algorithm is employed the constructed key values serve to
177 access matching rows with index lookups.
178 The key values are put into a hash table when the BNLH join algorithm
179 is employed and when BKAH is used for the join operation.
180 */
181 uint referenced_fields;
182
183 /*
184 The current number of already created data field descriptors.
185 This number can be useful for implementations of the init methods.
186 */
187 uint data_field_count;
188
189 /*
190 The current number of already created pointers to the data field
191 descriptors. This number can be useful for implementations of
192 the init methods.
193 */
194 uint data_field_ptr_count;
195
196 /*
197 Array of the descriptors of fields containing 'fields' elements.
198 These are all fields that are stored for a record in the cache.
199 */
200 CACHE_FIELD *field_descr;
201
202 /*
203 Array of pointers to the blob descriptors that contains 'blobs' elements.
204 */
205 CACHE_FIELD **blob_ptr;
206
207 /*
208 This flag indicates that records written into the join buffer contain
209 a match flag field. The flag must be set by the init method.
210 */
211 bool with_match_flag;
212 /*
213 This flag indicates that any record is prepended with the length of the
214 record which allows us to skip the record or part of it without reading.
215 */
216 bool with_length;
217
218 /*
219 The maximal number of bytes used for a record representation in
220 the cache excluding the space for blob data.
221 For future derived classes this representation may contains some
222 redundant info such as a key value associated with the record.
223 */
224 uint pack_length;
225 /*
226 The value of pack_length incremented by the total size of all
227 pointers of a record in the cache to the blob data.
228 */
229 uint pack_length_with_blob_ptrs;
230
231 /*
232 The total size of the record base prefix. The base prefix of record may
233 include the following components:
234 - the length of the record
235 - the link to a record in a previous buffer.
236 Each record in the buffer are supplied with the same set of the components.
237 */
238 uint base_prefix_length;
239
240 /*
241 The expected length of a record in the join buffer together with
242 all prefixes and postfixes
243 */
244 size_t avg_record_length;
245
246 /* The expected size of the space per record in the auxiliary buffer */
247 size_t avg_aux_buffer_incr;
248
249 /* Expected join buffer space used for one record */
250 size_t space_per_record;
251
252 /* Pointer to the beginning of the join buffer */
253 uchar *buff;
254 /*
255 Size of the entire memory allocated for the join buffer.
256 Part of this memory may be reserved for the auxiliary buffer.
257 */
258 size_t buff_size;
259 /* The minimal join buffer size when join buffer still makes sense to use */
260 size_t min_buff_size;
261 /* The maximum expected size if the join buffer to be used */
262 size_t max_buff_size;
263 /* Size of the auxiliary buffer */
264 size_t aux_buff_size;
265
266 /* The number of records put into the join buffer */
267 size_t records;
268 /*
269 The number of records in the fully refilled join buffer of
270 the minimal size equal to min_buff_size
271 */
272 size_t min_records;
273 /*
274 The maximum expected number of records to be put in the join buffer
275 at one refill
276 */
277 size_t max_records;
278
279 /*
280 Pointer to the current position in the join buffer.
281 This member is used both when writing to buffer and
282 when reading from it.
283 */
284 uchar *pos;
285 /*
286 Pointer to the first free position in the join buffer,
287 right after the last record into it.
288 */
289 uchar *end_pos;
290
291 /*
292 Pointer to the beginning of the first field of the current read/write
293 record from the join buffer. The value is adjusted by the
294 get_record/put_record functions.
295 */
296 uchar *curr_rec_pos;
297 /*
298 Pointer to the beginning of the first field of the last record
299 from the join buffer.
300 */
301 uchar *last_rec_pos;
302
303 /*
304 Flag is set if the blob data for the last record in the join buffer
305 is in record buffers rather than in the join cache.
306 */
307 bool last_rec_blob_data_is_in_rec_buff;
308
309 /*
310 Pointer to the position to the current record link.
311 Record links are used only with linked caches. Record links allow to set
312 connections between parts of one join record that are stored in different
313 join buffers.
314 In the simplest case a record link is just a pointer to the beginning of
315 the record stored in the buffer.
316 In a more general case a link could be a reference to an array of pointers
317 to records in the buffer.
318 */
319 uchar *curr_rec_link;
320
321 /*
322 This flag is set to TRUE if join_tab is the first inner table of an outer
323 join and the latest record written to the join buffer is detected to be
324 null complemented after checking on conditions over the outer tables for
325 this outer join operation
326 */
327 bool last_written_is_null_compl;
328
329 /*
330 The number of fields put in the join buffer of the join cache that are
331 used in building keys to access the table join_tab
332 */
333 uint local_key_arg_fields;
334 /*
335 The total number of the fields in the previous caches that are used
336 in building keys to access the table join_tab
337 */
338 uint external_key_arg_fields;
339
340 /*
341 This flag indicates that the key values will be read directly from the join
342 buffer. It will save us building key values in the key buffer.
343 */
344 bool use_emb_key;
345 /* The length of an embedded key value */
346 uint emb_key_length;
347
348 /*
349 This object provides the methods to iterate over records of
350 the joined table join_tab when looking for join matches between
351 records from join buffer and records from join_tab.
352 BNL and BNLH join algorithms retrieve all records from join_tab,
353 while BKA/BKAH algorithm iterates only over those records from
354 join_tab that can be accessed by look-ups with join keys built
355 from records in join buffer.
356 */
357 JOIN_TAB_SCAN *join_tab_scan;
358
359 void calc_record_fields();
360 void collect_info_on_key_args();
361 int alloc_fields();
362 void create_flag_fields();
363 void create_key_arg_fields();
364 void create_remaining_fields();
365 void set_constants();
366 int alloc_buffer();
367
368 /* Shall reallocate the join buffer */
369 virtual int realloc_buffer();
370
371 /* Check the possibility to read the access keys directly from join buffer */
372 bool check_emb_key_usage();
373
374 uint get_size_of_rec_offset() { return size_of_rec_ofs; }
375 uint get_size_of_rec_length() { return size_of_rec_len; }
376 uint get_size_of_fld_offset() { return size_of_fld_ofs; }
377
378 uchar *get_rec_ref(uchar *ptr)
379 {
380 return buff+get_offset(size_of_rec_ofs, ptr-size_of_rec_ofs);
381 }
382 ulong get_rec_length(uchar *ptr)
383 {
384 return (ulong) get_offset(size_of_rec_len, ptr);
385 }
386 ulong get_fld_offset(uchar *ptr)
387 {
388 return (ulong) get_offset(size_of_fld_ofs, ptr);
389 }
390
391 void store_rec_ref(uchar *ptr, uchar* ref)
392 {
393 store_offset(size_of_rec_ofs, ptr-size_of_rec_ofs, (ulong) (ref-buff));
394 }
395 void store_rec_length(uchar *ptr, ulong len)
396 {
397 store_offset(size_of_rec_len, ptr, len);
398 }
399 void store_fld_offset(uchar *ptr, ulong ofs)
400 {
401 store_offset(size_of_fld_ofs, ptr, ofs);
402 }
403
404 /* Write record fields and their required offsets into the join buffer */
405 uint write_record_data(uchar *link, bool *is_full);
406
407 /* Get the total length of all prefixes of a record in the join buffer */
408 virtual uint get_prefix_length() { return base_prefix_length; }
409 /* Get maximum total length of all affixes of a record in the join buffer */
410 virtual uint get_record_max_affix_length();
411
412 /*
413 Shall get maximum size of the additional space per record used for
414 record keys
415 */
416 virtual uint get_max_key_addon_space_per_record() { return 0; }
417
418 /*
419 This method must determine for how much the auxiliary buffer should be
420 incremented when a new record is added to the join buffer.
421 If no auxiliary buffer is needed the function should return 0.
422 */
423 virtual uint aux_buffer_incr(size_t recno);
424
425 /* Shall calculate how much space is remaining in the join buffer */
426 virtual size_t rem_space()
427 {
428 return MY_MAX(buff_size-(end_pos-buff)-aux_buff_size,0);
429 }
430
431 /*
432 Shall calculate how much space is taken by allocation of the key
433 for a record in the join buffer
434 */
435 virtual uint extra_key_length() { return 0; }
436
437 /* Read all flag and data fields of a record from the join buffer */
438 uint read_all_record_fields();
439
440 /* Read all flag fields of a record from the join buffer */
441 uint read_flag_fields();
442
443 /* Read a data record field from the join buffer */
444 uint read_record_field(CACHE_FIELD *copy, bool last_record);
445
446 /* Read a referenced field from the join buffer */
447 bool read_referenced_field(CACHE_FIELD *copy, uchar *rec_ptr, uint *len);
448
449 /*
450 Shall skip record from the join buffer if its match flag
451 is set to MATCH_FOUND
452 */
453 virtual bool skip_if_matched();
454
455 /*
456 Shall skip record from the join buffer if its match flag
457 commands to do so
458 */
459 virtual bool skip_if_not_needed_match();
460
461 /*
462 True if rec_ptr points to the record whose blob data stay in
463 record buffers
464 */
465 bool blob_data_is_in_rec_buff(uchar *rec_ptr)
466 {
467 return rec_ptr == last_rec_pos && last_rec_blob_data_is_in_rec_buff;
468 }
469
470 /* Find matches from the next table for records from the join buffer */
471 virtual enum_nested_loop_state join_matching_records(bool skip_last);
472
473 /* Shall set an auxiliary buffer up (currently used only by BKA joins) */
474 virtual int setup_aux_buffer(HANDLER_BUFFER &aux_buff)
475 {
476 DBUG_ASSERT(0);
477 return 0;
478 }
479
480 /*
481 Shall get the number of ranges in the cache buffer passed
482 to the MRR interface
483 */
484 virtual uint get_number_of_ranges_for_mrr() { return 0; };
485
486 /*
487 Shall prepare to look for records from the join cache buffer that would
488 match the record of the joined table read into the record buffer
489 */
490 virtual bool prepare_look_for_matches(bool skip_last)= 0;
491 /*
492 Shall return a pointer to the record from join buffer that is checked
493 as the next candidate for a match with the current record from join_tab.
494 Each implementation of this virtual function should bare in mind
495 that the record position it returns shall be exactly the position
496 passed as the parameter to the implementations of the virtual functions
497 skip_next_candidate_for_match and read_next_candidate_for_match.
498 */
499 virtual uchar *get_next_candidate_for_match()= 0;
500 /*
501 Shall check whether the given record from the join buffer has its match
502 flag settings commands to skip the record in the buffer.
503 */
504 virtual bool skip_next_candidate_for_match(uchar *rec_ptr)= 0;
505 /*
506 Shall read the given record from the join buffer into the
507 the corresponding record buffer
508 */
509 virtual void read_next_candidate_for_match(uchar *rec_ptr)= 0;
510
511 /*
512 Shall return the location of the association label returned by
513 the multi_read_range_next function for the current record loaded
514 into join_tab's record buffer
515 */
516 virtual uchar **get_curr_association_ptr() { return 0; };
517
518 /* Add null complements for unmatched outer records from the join buffer */
519 virtual enum_nested_loop_state join_null_complements(bool skip_last);
520
521 /* Restore the fields of the last record from the join buffer */
522 virtual void restore_last_record();
523
524 /* Set match flag for a record in join buffer if it has not been set yet */
525 bool set_match_flag_if_none(JOIN_TAB *first_inner, uchar *rec_ptr);
526
527 enum_nested_loop_state generate_full_extensions(uchar *rec_ptr);
528
529 /* Check matching to a partial join record from the join buffer */
530 bool check_match(uchar *rec_ptr);
531
532 /*
533 This constructor creates an unlinked join cache. The cache is to be
534 used to join table 'tab' to the result of joining the previous tables
535 specified by the 'j' parameter.
536 */
537 JOIN_CACHE(JOIN *j, JOIN_TAB *tab)
538 {
539 join= j;
540 join_tab= tab;
541 prev_cache= next_cache= 0;
542 buff= 0;
543 }
544
545 /*
546 This constructor creates a linked join cache. The cache is to be
547 used to join table 'tab' to the result of joining the previous tables
548 specified by the 'j' parameter. The parameter 'prev' specifies the previous
549 cache object to which this cache is linked.
550 */
551 JOIN_CACHE(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev)
552 {
553 join= j;
554 join_tab= tab;
555 next_cache= 0;
556 prev_cache= prev;
557 buff= 0;
558 if (prev)
559 prev->next_cache= this;
560 }
561
562public:
563
564 /*
565 The enumeration type Join_algorithm includes a mnemonic constant for
566 each join algorithm that employs join buffers
567 */
568
569 enum Join_algorithm
570 {
571 BNL_JOIN_ALG, /* Block Nested Loop Join algorithm */
572 BNLH_JOIN_ALG, /* Block Nested Loop Hash Join algorithm */
573 BKA_JOIN_ALG, /* Batched Key Access Join algorithm */
574 BKAH_JOIN_ALG /* Batched Key Access with Hash Table Join Algorithm */
575 };
576
577 /*
578 The enumeration type Match_flag describes possible states of the match flag
579 field stored for the records of the first inner tables of outer joins and
580 semi-joins in the cases when the first match strategy is used for them.
581 When a record with match flag field is written into the join buffer the
582 state of the field usually is MATCH_NOT_FOUND unless this is a record of the
583 first inner table of the outer join for which the on precondition (the
584 condition from on expression over outer tables) has turned out not to be
585 true. In the last case the state of the match flag is MATCH_IMPOSSIBLE.
586 The state of the match flag field is changed to MATCH_FOUND as soon as
587 the first full matching combination of inner tables of the outer join or
588 the semi-join is discovered.
589 */
590 enum Match_flag { MATCH_NOT_FOUND, MATCH_FOUND, MATCH_IMPOSSIBLE };
591
592 /* Table to be joined with the partial join records from the cache */
593 JOIN_TAB *join_tab;
594
595 /* Pointer to the previous join cache if there is any */
596 JOIN_CACHE *prev_cache;
597 /* Pointer to the next join cache if there is any */
598 JOIN_CACHE *next_cache;
599
600 /* Shall initialize the join cache structure */
601 virtual int init(bool for_explain);
602
603 /* Get the current size of the cache join buffer */
604 size_t get_join_buffer_size() { return buff_size; }
605 /* Set the size of the cache join buffer to a new value */
606 void set_join_buffer_size(size_t sz) { buff_size= sz; }
607
608 /* Get the minimum possible size of the cache join buffer */
609 virtual size_t get_min_join_buffer_size();
610 /* Get the maximum possible size of the cache join buffer */
611 virtual size_t get_max_join_buffer_size(bool optimize_buff_size);
612
613 /* Shrink the size if the cache join buffer in a given ratio */
614 bool shrink_join_buffer_in_ratio(ulonglong n, ulonglong d);
615
616 /* Shall return the type of the employed join algorithm */
617 virtual enum Join_algorithm get_join_alg()= 0;
618
619 /*
620 The function shall return TRUE only when there is a key access
621 to the join table
622 */
623 virtual bool is_key_access()= 0;
624
625 /* Shall reset the join buffer for reading/writing */
626 virtual void reset(bool for_writing);
627
628 /*
629 This function shall add a record into the join buffer and return TRUE
630 if it has been decided that it should be the last record in the buffer.
631 */
632 virtual bool put_record();
633
634 /*
635 This function shall read the next record into the join buffer and return
636 TRUE if there is no more next records.
637 */
638 virtual bool get_record();
639
640 /*
641 This function shall read the record at the position rec_ptr
642 in the join buffer
643 */
644 virtual void get_record_by_pos(uchar *rec_ptr);
645
646 /* Shall return the value of the match flag for the positioned record */
647 virtual enum Match_flag get_match_flag_by_pos(uchar *rec_ptr);
648
649 /* Shall return the position of the current record */
650 virtual uchar *get_curr_rec() { return curr_rec_pos; }
651
652 /* Shall set the current record link */
653 virtual void set_curr_rec_link(uchar *link) { curr_rec_link= link; }
654
655 /* Shall return the current record link */
656 virtual uchar *get_curr_rec_link()
657 {
658 return (curr_rec_link ? curr_rec_link : get_curr_rec());
659 }
660
661 /* Join records from the join buffer with records from the next join table */
662 enum_nested_loop_state join_records(bool skip_last);
663
664 /* Add a comment on the join algorithm employed by the join cache */
665 virtual bool save_explain_data(EXPLAIN_BKA_TYPE *explain);
666
667 THD *thd();
668
669 virtual ~JOIN_CACHE() {}
670 void reset_join(JOIN *j) { join= j; }
671 void free()
672 {
673 my_free(buff);
674 buff= 0;
675 }
676
677 friend class JOIN_CACHE_HASHED;
678 friend class JOIN_CACHE_BNL;
679 friend class JOIN_CACHE_BKA;
680 friend class JOIN_TAB_SCAN;
681 friend class JOIN_TAB_SCAN_MRR;
682
683};
684
685
686/*
687 The class JOIN_CACHE_HASHED is the base class for the classes
688 JOIN_CACHE_HASHED_BNL and JOIN_CACHE_HASHED_BKA. The first of them supports
689 an implementation of Block Nested Loop Hash (BNLH) Join Algorithm,
690 while the second is used for a variant of the BKA Join algorithm that performs
691 only one lookup for any records from join buffer with the same key value.
692 For a join cache of this class the records from the join buffer that have
693 the same access key are linked into a chain attached to a key entry structure
694 that either itself contains the key value, or, in the case when the keys are
695 embedded, refers to its occurrence in one of the records from the chain.
696 To build the chains with the same keys a hash table is employed. It is placed
697 at the very end of the join buffer. The array of hash entries is allocated
698 first at the very bottom of the join buffer, while key entries are placed
699 before this array.
700 A hash entry contains a header of the list of the key entries with the same
701 hash value.
702 Each key entry is a structure of the following type:
703 struct st_join_cache_key_entry {
704 union {
705 uchar[] value;
706 cache_ref *value_ref; // offset from the beginning of the buffer
707 } hash_table_key;
708 key_ref next_key; // offset backward from the beginning of hash table
709 cache_ref *last_rec // offset from the beginning of the buffer
710 }
711 The references linking the records in a chain are always placed at the very
712 beginning of the record info stored in the join buffer. The records are
713 linked in a circular list. A new record is always added to the end of this
714 list.
715
716 The following picture represents a typical layout for the info stored in the
717 join buffer of a join cache object of the JOIN_CACHE_HASHED class.
718
719 buff
720 V
721 +----------------------------------------------------------------------------+
722 | |[*]record_1_1| |
723 | ^ | |
724 | | +--------------------------------------------------+ |
725 | | |[*]record_2_1| | |
726 | | ^ | V |
727 | | | +------------------+ |[*]record_1_2| |
728 | | +--------------------+-+ | |
729 |+--+ +---------------------+ | | +-------------+ |
730 || | | V | | |
731 |||[*]record_3_1| |[*]record_1_3| |[*]record_2_2| | |
732 ||^ ^ ^ | |
733 ||+----------+ | | | |
734 ||^ | |<---------------------------+-------------------+ |
735 |++ | | ... mrr | buffer ... ... | | |
736 | | | | |
737 | +-----+--------+ | +-----|-------+ |
738 | V | | | V | | |
739 ||key_3|[/]|[*]| | | |key_2|[/]|[*]| | |
740 | +-+---|-----------------------+ | |
741 | V | | | | |
742 | |key_1|[*]|[*]| | | ... |[*]| ... |[*]| ... | |
743 +----------------------------------------------------------------------------+
744 ^ ^ ^
745 | i-th entry j-th entry
746 hash table
747
748 i-th hash entry:
749 circular record chain for key_1:
750 record_1_1
751 record_1_2
752 record_1_3 (points to record_1_1)
753 circular record chain for key_3:
754 record_3_1 (points to itself)
755
756 j-th hash entry:
757 circular record chain for key_2:
758 record_2_1
759 record_2_2 (points to record_2_1)
760
761*/
762
763class JOIN_CACHE_HASHED: public JOIN_CACHE
764{
765
766 typedef uint (JOIN_CACHE_HASHED::*Hash_func) (uchar *key, uint key_len);
767 typedef bool (JOIN_CACHE_HASHED::*Hash_cmp_func) (uchar *key1, uchar *key2,
768 uint key_len);
769
770private:
771
772 /* Size of the offset of a key entry in the hash table */
773 uint size_of_key_ofs;
774
775 /*
776 Length of the key entry in the hash table.
777 A key entry either contains the key value, or it contains a reference
778 to the key value if use_emb_key flag is set for the cache.
779 */
780 uint key_entry_length;
781
782 /* The beginning of the hash table in the join buffer */
783 uchar *hash_table;
784 /* Number of hash entries in the hash table */
785 uint hash_entries;
786
787
788 /* The position of the currently retrieved key entry in the hash table */
789 uchar *curr_key_entry;
790
791 /* The offset of the data fields from the beginning of the record fields */
792 uint data_fields_offset;
793
794 inline uint get_hash_idx_simple(uchar *key, uint key_len);
795 inline uint get_hash_idx_complex(uchar *key, uint key_len);
796
797 inline bool equal_keys_simple(uchar *key1, uchar *key2, uint key_len);
798 inline bool equal_keys_complex(uchar *key1, uchar *key2, uint key_len);
799
800 int init_hash_table();
801 void cleanup_hash_table();
802
803protected:
804
805 /*
806 Index info on the TABLE_REF object used by the hash join
807 to look for matching records
808 */
809 KEY *ref_key_info;
810 /*
811 Number of the key parts the TABLE_REF object used by the hash join
812 to look for matching records
813 */
814 uint ref_used_key_parts;
815
816 /*
817 The hash function used in the hash table,
818 usually set by the init() method
819 */
820 Hash_func hash_func;
821 /*
822 The function to check whether two key entries in the hash table
823 are equal or not, usually set by the init() method
824 */
825 Hash_cmp_func hash_cmp_func;
826
827 /*
828 Length of a key value.
829 It is assumed that all key values have the same length.
830 */
831 uint key_length;
832 /* Buffer to store key values for probing */
833 uchar *key_buff;
834
835 /* Number of key entries in the hash table (number of distinct keys) */
836 uint key_entries;
837
838 /* The position of the last key entry in the hash table */
839 uchar *last_key_entry;
840
841 /*
842 The offset of the record fields from the beginning of the record
843 representation. The record representation starts with a reference to
844 the next record in the key record chain followed by the length of
845 the trailing record data followed by a reference to the record segment
846 in the previous cache, if any, followed by the record fields.
847 */
848 uint rec_fields_offset;
849
850 uint get_size_of_key_offset() { return size_of_key_ofs; }
851
852 /*
853 Get the position of the next_key_ptr field pointed to by
854 a linking reference stored at the position key_ref_ptr.
855 This reference is actually the offset backward from the
856 beginning of hash table.
857 */
858 uchar *get_next_key_ref(uchar *key_ref_ptr)
859 {
860 return hash_table-get_offset(size_of_key_ofs, key_ref_ptr);
861 }
862
863 /*
864 Store the linking reference to the next_key_ptr field at
865 the position key_ref_ptr. The position of the next_key_ptr
866 field is pointed to by ref. The stored reference is actually
867 the offset backward from the beginning of the hash table.
868 */
869 void store_next_key_ref(uchar *key_ref_ptr, uchar *ref)
870 {
871 store_offset(size_of_key_ofs, key_ref_ptr, (ulong) (hash_table-ref));
872 }
873
874 /*
875 Check whether the reference to the next_key_ptr field at the position
876 key_ref_ptr contains a nil value.
877 */
878 bool is_null_key_ref(uchar *key_ref_ptr)
879 {
880 ulong nil= 0;
881 return memcmp(key_ref_ptr, &nil, size_of_key_ofs ) == 0;
882 }
883
884 /*
885 Set the reference to the next_key_ptr field at the position
886 key_ref_ptr equal to nil.
887 */
888 void store_null_key_ref(uchar *key_ref_ptr)
889 {
890 ulong nil= 0;
891 store_offset(size_of_key_ofs, key_ref_ptr, nil);
892 }
893
894 uchar *get_next_rec_ref(uchar *ref_ptr)
895 {
896 return buff+get_offset(get_size_of_rec_offset(), ref_ptr);
897 }
898
899 void store_next_rec_ref(uchar *ref_ptr, uchar *ref)
900 {
901 store_offset(get_size_of_rec_offset(), ref_ptr, (ulong) (ref-buff));
902 }
903
904 /*
905 Get the position of the embedded key value for the current
906 record pointed to by get_curr_rec().
907 */
908 uchar *get_curr_emb_key()
909 {
910 return get_curr_rec()+data_fields_offset;
911 }
912
913 /*
914 Get the position of the embedded key value pointed to by a reference
915 stored at ref_ptr. The stored reference is actually the offset from
916 the beginning of the join buffer.
917 */
918 uchar *get_emb_key(uchar *ref_ptr)
919 {
920 return buff+get_offset(get_size_of_rec_offset(), ref_ptr);
921 }
922
923 /*
924 Store the reference to an embedded key at the position key_ref_ptr.
925 The position of the embedded key is pointed to by ref. The stored
926 reference is actually the offset from the beginning of the join buffer.
927 */
928 void store_emb_key_ref(uchar *ref_ptr, uchar *ref)
929 {
930 store_offset(get_size_of_rec_offset(), ref_ptr, (ulong) (ref-buff));
931 }
932
933 /* Get the total length of all prefixes of a record in hashed join buffer */
934 uint get_prefix_length()
935 {
936 return base_prefix_length + get_size_of_rec_offset();
937 }
938
939 /*
940 Get maximum size of the additional space per record used for
941 the hash table with record keys
942 */
943 uint get_max_key_addon_space_per_record();
944
945 /*
946 Calculate how much space in the buffer would not be occupied by
947 records, key entries and additional memory for the MMR buffer.
948 */
949 size_t rem_space()
950 {
951 return MY_MAX(last_key_entry-end_pos-aux_buff_size,0);
952 }
953
954 /*
955 Calculate how much space is taken by allocation of the key
956 entry for a record in the join buffer
957 */
958 uint extra_key_length() { return key_entry_length; }
959
960 /*
961 Skip record from a hashed join buffer if its match flag
962 is set to MATCH_FOUND
963 */
964 bool skip_if_matched();
965
966 /*
967 Skip record from a hashed join buffer if its match flag setting
968 commands to do so
969 */
970 bool skip_if_not_needed_match();
971
972 /* Search for a key in the hash table of the join buffer */
973 bool key_search(uchar *key, uint key_len, uchar **key_ref_ptr);
974
975 /* Reallocate the join buffer of a hashed join cache */
976 int realloc_buffer();
977
978 /*
979 This constructor creates an unlinked hashed join cache. The cache is to be
980 used to join table 'tab' to the result of joining the previous tables
981 specified by the 'j' parameter.
982 */
983 JOIN_CACHE_HASHED(JOIN *j, JOIN_TAB *tab) :JOIN_CACHE(j, tab) {}
984
985 /*
986 This constructor creates a linked hashed join cache. The cache is to be
987 used to join table 'tab' to the result of joining the previous tables
988 specified by the 'j' parameter. The parameter 'prev' specifies the previous
989 cache object to which this cache is linked.
990 */
991 JOIN_CACHE_HASHED(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev)
992 :JOIN_CACHE(j, tab, prev) {}
993
994public:
995
996 /* Initialize a hashed join cache */
997 int init(bool for_explain);
998
999 /* Reset the buffer of a hashed join cache for reading/writing */
1000 void reset(bool for_writing);
1001
1002 /* Add a record into the buffer of a hashed join cache */
1003 bool put_record();
1004
1005 /* Read the next record from the buffer of a hashed join cache */
1006 bool get_record();
1007
1008 /*
1009 Shall check whether all records in a key chain have
1010 their match flags set on
1011 */
1012 virtual bool check_all_match_flags_for_key(uchar *key_chain_ptr);
1013
1014 uint get_next_key(uchar **key);
1015
1016 /* Get the head of the record chain attached to the current key entry */
1017 uchar *get_curr_key_chain()
1018 {
1019 return get_next_rec_ref(curr_key_entry+key_entry_length-
1020 get_size_of_rec_offset());
1021 }
1022
1023};
1024
1025
1026/*
1027 The class JOIN_TAB_SCAN is a companion class for the classes JOIN_CACHE_BNL
1028 and JOIN_CACHE_BNLH. Actually the class implements the iterator over the
1029 table joinded by BNL/BNLH join algorithm.
1030 The virtual functions open, next and close are called for any iteration over
1031 the table. The function open is called to initiate the process of the
1032 iteration. The function next shall read the next record from the joined
1033 table. The record is read into the record buffer of the joined table.
1034 The record is to be matched with records from the join cache buffer.
1035 The function close shall perform the finalizing actions for the iteration.
1036*/
1037
1038class JOIN_TAB_SCAN: public Sql_alloc
1039{
1040
1041private:
1042 /* TRUE if this is the first record from the joined table to iterate over */
1043 bool is_first_record;
1044
1045protected:
1046
1047 /* The joined table to be iterated over */
1048 JOIN_TAB *join_tab;
1049 /* The join cache used to join the table join_tab */
1050 JOIN_CACHE *cache;
1051 /*
1052 Representation of the executed multi-way join through which
1053 all needed context can be accessed.
1054 */
1055 JOIN *join;
1056
1057public:
1058
1059 JOIN_TAB_SCAN(JOIN *j, JOIN_TAB *tab)
1060 {
1061 join= j;
1062 join_tab= tab;
1063 cache= join_tab->cache;
1064 }
1065
1066 virtual ~JOIN_TAB_SCAN() {}
1067
1068 /*
1069 Shall calculate the increment of the auxiliary buffer for a record
1070 write if such a buffer is used by the table scan object
1071 */
1072 virtual uint aux_buffer_incr(size_t recno) { return 0; }
1073
1074 /* Initiate the process of iteration over the joined table */
1075 virtual int open();
1076 /*
1077 Shall read the next candidate for matches with records from
1078 the join buffer.
1079 */
1080 virtual int next();
1081 /*
1082 Perform the finalizing actions for the process of iteration
1083 over the joined_table.
1084 */
1085 virtual void close();
1086
1087};
1088
1089/*
1090 The class JOIN_CACHE_BNL is used when the BNL join algorithm is
1091 employed to perform a join operation
1092*/
1093
1094class JOIN_CACHE_BNL :public JOIN_CACHE
1095{
1096private:
1097 /*
1098 The number of the records in the join buffer that have to be
1099 checked yet for a match with the current record of join_tab
1100 read into the record buffer.
1101 */
1102 uint rem_records;
1103
1104protected:
1105
1106 bool prepare_look_for_matches(bool skip_last);
1107
1108 uchar *get_next_candidate_for_match();
1109
1110 bool skip_next_candidate_for_match(uchar *rec_ptr);
1111
1112 void read_next_candidate_for_match(uchar *rec_ptr);
1113
1114public:
1115
1116 /*
1117 This constructor creates an unlinked BNL join cache. The cache is to be
1118 used to join table 'tab' to the result of joining the previous tables
1119 specified by the 'j' parameter.
1120 */
1121 JOIN_CACHE_BNL(JOIN *j, JOIN_TAB *tab) :JOIN_CACHE(j, tab) {}
1122
1123 /*
1124 This constructor creates a linked BNL join cache. The cache is to be
1125 used to join table 'tab' to the result of joining the previous tables
1126 specified by the 'j' parameter. The parameter 'prev' specifies the previous
1127 cache object to which this cache is linked.
1128 */
1129 JOIN_CACHE_BNL(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev)
1130 :JOIN_CACHE(j, tab, prev) {}
1131
1132 /* Initialize the BNL cache */
1133 int init(bool for_explain);
1134
1135 enum Join_algorithm get_join_alg() { return BNL_JOIN_ALG; }
1136
1137 bool is_key_access() { return FALSE; }
1138
1139};
1140
1141
1142/*
1143 The class JOIN_CACHE_BNLH is used when the BNLH join algorithm is
1144 employed to perform a join operation
1145*/
1146
1147class JOIN_CACHE_BNLH :public JOIN_CACHE_HASHED
1148{
1149
1150protected:
1151
1152 /*
1153 The pointer to the last record from the circular list of the records
1154 that match the join key built out of the record in the join buffer for
1155 the join_tab table
1156 */
1157 uchar *last_matching_rec_ref_ptr;
1158 /*
1159 The pointer to the next current record from the circular list of the
1160 records that match the join key built out of the record in the join buffer
1161 for the join_tab table. This pointer is used by the class method
1162 get_next_candidate_for_match to iterate over records from the circular
1163 list.
1164 */
1165 uchar *next_matching_rec_ref_ptr;
1166
1167 /*
1168 Get the chain of records from buffer matching the current candidate
1169 record for join
1170 */
1171 uchar *get_matching_chain_by_join_key();
1172
1173 bool prepare_look_for_matches(bool skip_last);
1174
1175 uchar *get_next_candidate_for_match();
1176
1177 bool skip_next_candidate_for_match(uchar *rec_ptr);
1178
1179 void read_next_candidate_for_match(uchar *rec_ptr);
1180
1181public:
1182
1183 /*
1184 This constructor creates an unlinked BNLH join cache. The cache is to be
1185 used to join table 'tab' to the result of joining the previous tables
1186 specified by the 'j' parameter.
1187 */
1188 JOIN_CACHE_BNLH(JOIN *j, JOIN_TAB *tab) : JOIN_CACHE_HASHED(j, tab) {}
1189
1190 /*
1191 This constructor creates a linked BNLH join cache. The cache is to be
1192 used to join table 'tab' to the result of joining the previous tables
1193 specified by the 'j' parameter. The parameter 'prev' specifies the previous
1194 cache object to which this cache is linked.
1195 */
1196 JOIN_CACHE_BNLH(JOIN *j, JOIN_TAB *tab, JOIN_CACHE *prev)
1197 : JOIN_CACHE_HASHED(j, tab, prev) {}
1198
1199 /* Initialize the BNLH cache */
1200 int init(bool for_explain);
1201
1202 enum Join_algorithm get_join_alg() { return BNLH_JOIN_ALG; }
1203
1204 bool is_key_access() { return TRUE; }
1205
1206};
1207
1208
1209/*
1210 The class JOIN_TAB_SCAN_MRR is a companion class for the classes
1211 JOIN_CACHE_BKA and JOIN_CACHE_BKAH. Actually the class implements the
1212 iterator over the records from join_tab selected by BKA/BKAH join
1213 algorithm as the candidates to be joined.
1214 The virtual functions open, next and close are called for any iteration over
1215 join_tab record candidates. The function open is called to initiate the
1216 process of the iteration. The function next shall read the next record from
1217 the set of the record candidates. The record is read into the record buffer
1218 of the joined table. The function close shall perform the finalizing actions
1219 for the iteration.
1220*/
1221
1222class JOIN_TAB_SCAN_MRR: public JOIN_TAB_SCAN
1223{
1224 /* Interface object to generate key ranges for MRR */
1225 RANGE_SEQ_IF range_seq_funcs;
1226
1227 /* Number of ranges to be processed by the MRR interface */
1228 uint ranges;
1229
1230 /* Flag to to be passed to the MRR interface */
1231 uint mrr_mode;
1232
1233 /* MRR buffer assotiated with this join cache */
1234 HANDLER_BUFFER mrr_buff;
1235
1236 /* Shall initialize the MRR buffer */
1237 virtual void init_mrr_buff()
1238 {
1239 cache->setup_aux_buffer(mrr_buff);
1240 }
1241
1242public:
1243
1244 JOIN_TAB_SCAN_MRR(JOIN *j, JOIN_TAB *tab, uint flags, RANGE_SEQ_IF rs_funcs)
1245 :JOIN_TAB_SCAN(j, tab), range_seq_funcs(rs_funcs), mrr_mode(flags) {}
1246
1247 uint aux_buffer_incr(size_t recno);
1248
1249 int open();
1250
1251 int next();
1252
1253 friend class JOIN_CACHE_BKA; /* it needs to add an mrr_mode flag after JOIN_CACHE::init() call */
1254};
1255
1256/*
1257 The class JOIN_CACHE_BKA is used when the BKA join algorithm is
1258 employed to perform a join operation
1259*/
1260
1261class JOIN_CACHE_BKA :public JOIN_CACHE
1262{
1263private:
1264
1265 /* Flag to to be passed to the companion JOIN_TAB_SCAN_MRR object */
1266 uint mrr_mode;
1267
1268 /*
1269 This value is set to 1 by the class prepare_look_for_matches method
1270 and back to 0 by the class get_next_candidate_for_match method
1271 */
1272 uint rem_records;
1273
1274 /*
1275 This field contains the current association label set by a call of
1276 the multi_range_read_next handler function.
1277 See the function JOIN_CACHE_BKA::get_curr_key_association()
1278 */
1279 uchar *curr_association;
1280
1281protected:
1282
1283 /*
1284 Get the number of ranges in the cache buffer passed to the MRR
1285 interface. For each record its own range is passed.
1286 */
1287 uint get_number_of_ranges_for_mrr() { return (uint)records; }
1288
1289 /*
1290 Setup the MRR buffer as the space between the last record put
1291 into the join buffer and the very end of the join buffer
1292 */
1293 int setup_aux_buffer(HANDLER_BUFFER &aux_buff)
1294 {
1295 aux_buff.buffer= end_pos;
1296 aux_buff.buffer_end= buff+buff_size;
1297 return 0;
1298 }
1299
1300 bool prepare_look_for_matches(bool skip_last);
1301
1302 uchar *get_next_candidate_for_match();
1303
1304 bool skip_next_candidate_for_match(uchar *rec_ptr);
1305
1306 void read_next_candidate_for_match(uchar *rec_ptr);
1307
1308public:
1309
1310 /*
1311 This constructor creates an unlinked BKA join cache. The cache is to be
1312 used to join table 'tab' to the result of joining the previous tables
1313 specified by the 'j' parameter.
1314 The MRR mode initially is set to 'flags'.
1315 */
1316 JOIN_CACHE_BKA(JOIN *j, JOIN_TAB *tab, uint flags)
1317 :JOIN_CACHE(j, tab), mrr_mode(flags) {}
1318 /*
1319 This constructor creates a linked BKA join cache. The cache is to be
1320 used to join table 'tab' to the result of joining the previous tables
1321 specified by the 'j' parameter. The parameter 'prev' specifies the previous
1322 cache object to which this cache is linked.
1323 The MRR mode initially is set to 'flags'.
1324 */
1325 JOIN_CACHE_BKA(JOIN *j, JOIN_TAB *tab, uint flags, JOIN_CACHE *prev)
1326 :JOIN_CACHE(j, tab, prev), mrr_mode(flags) {}
1327
1328 JOIN_CACHE_BKA(JOIN_CACHE_BKA *bka)
1329 :JOIN_CACHE(bka->join, bka->join_tab, bka->prev_cache),
1330 mrr_mode(bka->mrr_mode) {}
1331
1332 uchar **get_curr_association_ptr() { return &curr_association; }
1333
1334 /* Initialize the BKA cache */
1335 int init(bool for_explain);
1336
1337 enum Join_algorithm get_join_alg() { return BKA_JOIN_ALG; }
1338
1339 bool is_key_access() { return TRUE; }
1340
1341 /* Get the key built over the next record from the join buffer */
1342 uint get_next_key(uchar **key);
1343
1344 /* Check index condition of the joined table for a record from BKA cache */
1345 bool skip_index_tuple(range_id_t range_info);
1346
1347 bool save_explain_data(EXPLAIN_BKA_TYPE *explain);
1348};
1349
1350
1351
1352/*
1353 The class JOIN_CACHE_BKAH is used when the BKAH join algorithm is
1354 employed to perform a join operation
1355*/
1356
1357class JOIN_CACHE_BKAH :public JOIN_CACHE_BNLH
1358{
1359
1360private:
1361 /* Flag to to be passed to the companion JOIN_TAB_SCAN_MRR object */
1362 uint mrr_mode;
1363
1364 /*
1365 This flag is set to TRUE if the implementation of the MRR interface cannot
1366 handle range association labels and does not return them to the caller of
1367 the multi_range_read_next handler function. E.g. the implementation of
1368 the MRR inteface for the Falcon engine could not return association
1369 labels to the caller of multi_range_read_next.
1370 The flag is set by JOIN_CACHE_BKA::init() and is not ever changed.
1371 */
1372 bool no_association;
1373
1374 /*
1375 This field contains the association label returned by the
1376 multi_range_read_next function.
1377 See the function JOIN_CACHE_BKAH::get_curr_key_association()
1378 */
1379 uchar *curr_matching_chain;
1380
1381protected:
1382
1383 uint get_number_of_ranges_for_mrr() { return key_entries; }
1384
1385 /*
1386 Initialize the MRR buffer allocating some space within the join buffer.
1387 The entire space between the last record put into the join buffer and the
1388 last key entry added to the hash table is used for the MRR buffer.
1389 */
1390 int setup_aux_buffer(HANDLER_BUFFER &aux_buff)
1391 {
1392 aux_buff.buffer= end_pos;
1393 aux_buff.buffer_end= last_key_entry;
1394 return 0;
1395 }
1396
1397 bool prepare_look_for_matches(bool skip_last);
1398
1399 /*
1400 The implementations of the methods
1401 - get_next_candidate_for_match
1402 - skip_recurrent_candidate_for_match
1403 - read_next_candidate_for_match
1404 are inherited from the JOIN_CACHE_BNLH class
1405 */
1406
1407public:
1408
1409 /*
1410 This constructor creates an unlinked BKAH join cache. The cache is to be
1411 used to join table 'tab' to the result of joining the previous tables
1412 specified by the 'j' parameter.
1413 The MRR mode initially is set to 'flags'.
1414 */
1415 JOIN_CACHE_BKAH(JOIN *j, JOIN_TAB *tab, uint flags)
1416 :JOIN_CACHE_BNLH(j, tab), mrr_mode(flags) {}
1417
1418 /*
1419 This constructor creates a linked BKAH join cache. The cache is to be
1420 used to join table 'tab' to the result of joining the previous tables
1421 specified by the 'j' parameter. The parameter 'prev' specifies the previous
1422 cache object to which this cache is linked.
1423 The MRR mode initially is set to 'flags'.
1424 */
1425 JOIN_CACHE_BKAH(JOIN *j, JOIN_TAB *tab, uint flags, JOIN_CACHE *prev)
1426 :JOIN_CACHE_BNLH(j, tab, prev), mrr_mode(flags) {}
1427
1428 JOIN_CACHE_BKAH(JOIN_CACHE_BKAH *bkah)
1429 :JOIN_CACHE_BNLH(bkah->join, bkah->join_tab, bkah->prev_cache),
1430 mrr_mode(bkah->mrr_mode) {}
1431
1432 uchar **get_curr_association_ptr() { return &curr_matching_chain; }
1433
1434 /* Initialize the BKAH cache */
1435 int init(bool for_explain);
1436
1437 enum Join_algorithm get_join_alg() { return BKAH_JOIN_ALG; }
1438
1439 /* Check index condition of the joined table for a record from BKAH cache */
1440 bool skip_index_tuple(range_id_t range_info);
1441
1442 bool save_explain_data(EXPLAIN_BKA_TYPE *explain);
1443};
1444