PostgreSQL Source Code: src/backend/utils/adt/array_selfuncs.c Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
16
17#include <math.h>
18
23#include "utils/fmgrprotos.h"
27
28
29
30#define DEFAULT_CONTAIN_SEL 0.005
31
32
33#define DEFAULT_OVERLAP_SEL 0.01
34
35
36#define DEFAULT_SEL(operator) \
37 ((operator) == OID_ARRAY_OVERLAP_OP ? \
38 DEFAULT_OVERLAP_SEL : DEFAULT_CONTAIN_SEL)
39
41 Oid elemtype, Oid operator);
44 const Datum *mcelem, int nmcelem,
45 const float4 *numbers, int nnumbers,
46 const float4 *hist, int nhist,
47 Oid operator);
49 const float4 *numbers, int nnumbers,
53 const float4 *numbers, int nnumbers,
55 const float4 *hist, int nhist,
57static float *calc_hist(const float4 *hist, int nhist, int n);
58static float *calc_distr(const float *p, int n, int m, float rest);
62static int element_compare(const void *key1, const void *key2, void *arg);
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
83 Oid elemtype, bool isEquality, bool useOr,
84 int varRelid)
85{
91
92
93
94
96 if (!vardata.rel)
97 {
99 return -1.0;
100 }
101
102
103
104
106 {
108 return -1.0;
109 }
110 if (((Const *) leftop)->constisnull)
111 {
112
115 }
116 constval = ((Const *) leftop)->constvalue;
117
118
121 {
123 return -1.0;
124 }
126
127
128
129
130 if (!isEquality)
131 useOr = !useOr;
132
133
136 {
140
142
143
147 {
148
149 if (useOr ||
153 memset(&hslot, 0, sizeof(hslot));
154
155
156
157
158
159
160 if (useOr)
165 &constval, 1,
166 OID_ARRAY_CONTAINS_OP,
167 typentry);
168 else
173 &constval, 1,
176 OID_ARRAY_CONTAINED_OP,
177 typentry);
178
181 }
182 else
183 {
184
185 if (useOr)
187 NULL, 0,
188 &constval, 1,
189 OID_ARRAY_CONTAINS_OP,
190 typentry);
191 else
193 NULL, 0,
194 &constval, 1,
195 NULL, 0,
196 OID_ARRAY_CONTAINED_OP,
197 typentry);
198 }
199
200
201
202
203 selec *= (1.0 - stats->stanullfrac);
204 }
205 else
206 {
207
208 if (useOr)
210 NULL, 0,
211 &constval, 1,
212 OID_ARRAY_CONTAINS_OP,
213 typentry);
214 else
216 NULL, 0,
217 &constval, 1,
218 NULL, 0,
219 OID_ARRAY_CONTAINED_OP,
220 typentry);
221
222 }
223
225
226
227
228
229 if (!isEquality)
230 selec = 1.0 - selec;
231
233
234 return selec;
235}
236
237
238
239
242{
249 bool varonleft;
251 Oid element_typeid;
252
253
254
255
256
258 &vardata, &other, &varonleft))
260
261
262
263
265 {
268 }
269
270
271
272
273
274 if (((Const *) other)->constisnull)
275 {
278 }
279
280
281
282
283
284 if (!varonleft)
285 {
286 if (operator == OID_ARRAY_CONTAINS_OP)
287 operator = OID_ARRAY_CONTAINED_OP;
288 else if (operator == OID_ARRAY_CONTAINED_OP)
289 operator = OID_ARRAY_CONTAINS_OP;
290 }
291
292
293
294
295
296
297
301 {
303 element_typeid, operator);
304 }
305 else
306 {
308 }
309
311
313
315}
316
317
318
319
322{
323
325
327}
328
329
330
331
332
333
334
335
338 Oid elemtype, Oid operator)
339{
344
345
350
351
352
353
354
356
359 {
363
365
366
370 {
371
372
373
374
375 if (operator != OID_ARRAY_CONTAINED_OP ||
379 memset(&hslot, 0, sizeof(hslot));
380
381
386 operator);
387
390 }
391 else
392 {
393
395 NULL, 0, NULL, 0, NULL, 0,
396 operator);
397 }
398
399
400
401
402 selec *= (1.0 - stats->stanullfrac);
403 }
404 else
405 {
406
408 NULL, 0, NULL, 0, NULL, 0,
409 operator);
410
411 }
412
413
416
417 return selec;
418}
419
420
421
422
423
424
425
426
429 const Datum *mcelem, int nmcelem,
430 const float4 *numbers, int nnumbers,
431 const float4 *hist, int nhist,
432 Oid operator)
433{
435 int num_elems;
436 Datum *elem_values;
437 bool *elem_nulls;
438 bool null_present;
439 int nonnull_nitems;
440 int i;
441
442
443
444
445
451 &elem_values, &elem_nulls, &num_elems);
452
453
454 nonnull_nitems = 0;
455 null_present = false;
456 for (i = 0; i < num_elems; i++)
457 {
458 if (elem_nulls[i])
459 null_present = true;
460 else
461 elem_values[nonnull_nitems++] = elem_values[i];
462 }
463
464
465
466
467
468 if (null_present && operator == OID_ARRAY_CONTAINS_OP)
469 {
470 pfree(elem_values);
471 pfree(elem_nulls);
473 }
474
475
476 qsort_arg(elem_values, nonnull_nitems, sizeof(Datum),
478
479
480 if (operator == OID_ARRAY_CONTAINS_OP || operator == OID_ARRAY_OVERLAP_OP)
482 numbers, nnumbers,
483 elem_values, nonnull_nitems,
484 operator, typentry);
485 else if (operator == OID_ARRAY_CONTAINED_OP)
487 numbers, nnumbers,
488 elem_values, nonnull_nitems,
489 hist, nhist,
490 operator, typentry);
491 else
492 {
493 elog(ERROR, "arraycontsel called for unrecognized operator %u",
494 operator);
495 selec = 0.0;
496 }
497
498 pfree(elem_values);
499 pfree(elem_nulls);
500 return selec;
501}
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
522 const float4 *numbers, int nnumbers,
525{
527 elem_selec;
528 int mcelem_index,
529 i;
530 bool use_bsearch;
532
533
534
535
536
537
538
539 if (nnumbers != nmcelem + 3)
540 {
541 numbers = NULL;
542 nnumbers = 0;
543 }
544
545 if (numbers)
546 {
547
548 minfreq = numbers[nmcelem];
549 }
550 else
551 {
552
553
554
555
557 }
558
559
561 use_bsearch = true;
562 else
563 use_bsearch = false;
564
565 if (operator == OID_ARRAY_CONTAINS_OP)
566 {
567
568
569
570
571 selec = 1.0;
572 }
573 else
574 {
575
576
577
578
579 selec = 0.0;
580 }
581
582
583 mcelem_index = 0;
585 {
586 bool match = false;
587
588
589 if (i > 0 &&
590 element_compare(&array_data[i - 1], &array_data[i], typentry) == 0)
591 continue;
592
593
594 if (use_bsearch)
595 {
597 &mcelem_index, typentry);
598 }
599 else
600 {
601 while (mcelem_index < nmcelem)
602 {
604 &array_data[i],
605 typentry);
606
607 if (cmp < 0)
608 mcelem_index++;
609 else
610 {
611 if (cmp == 0)
612 match = true;
613 break;
614 }
615 }
616 }
617
618 if (match && numbers)
619 {
620
621 elem_selec = numbers[mcelem_index];
622 mcelem_index++;
623 }
624 else
625 {
626
627
628
629
630
631
632
634 }
635
636
637
638
639
640 if (operator == OID_ARRAY_CONTAINS_OP)
641 selec *= elem_selec;
642 else
643 selec = selec + elem_selec - selec * elem_selec;
644
645
647 }
648
649 return selec;
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
703 const float4 *numbers, int nnumbers,
705 const float4 *hist, int nhist,
707{
708 int mcelem_index,
709 i,
710 unique_nitems = 0;
711 float selec,
712 minfreq,
713 nullelem_freq;
714 float *dist,
715 *mcelem_dist,
716 *hist_part;
717 float avg_count,
718 mult,
719 rest;
720 float *elem_selec;
721
722
723
724
725
726
727
728 if (numbers == NULL || nnumbers != nmcelem + 3)
730
731
732 if (hist == NULL || nhist < 3)
734
735
736
737
738
739
740 minfreq = numbers[nmcelem];
741 nullelem_freq = numbers[nmcelem + 2];
742 avg_count = hist[nhist - 1];
743
744
745
746
747
748
749
750 rest = avg_count;
751
752
753
754
755
756 mult = 1.0f;
757
758
759
760
761
763
764
765 mcelem_index = 0;
767 {
768 bool match = false;
769
770
771 if (i > 0 &&
772 element_compare(&array_data[i - 1], &array_data[i], typentry) == 0)
773 continue;
774
775
776
777
778
779
780 while (mcelem_index < nmcelem)
781 {
783 &array_data[i],
784 typentry);
785
786 if (cmp < 0)
787 {
788 mult *= (1.0f - numbers[mcelem_index]);
789 rest -= numbers[mcelem_index];
790 mcelem_index++;
791 }
792 else
793 {
794 if (cmp == 0)
795 match = true;
796 break;
797 }
798 }
799
800 if (match)
801 {
802
803 elem_selec[unique_nitems] = numbers[mcelem_index];
804
805 rest -= numbers[mcelem_index];
806 mcelem_index++;
807 }
808 else
809 {
810
811
812
813
814
815
816
818 minfreq / 2);
819 }
820
821 unique_nitems++;
822 }
823
824
825
826
827
828 while (mcelem_index < nmcelem)
829 {
830 mult *= (1.0f - numbers[mcelem_index]);
831 rest -= numbers[mcelem_index];
832 mcelem_index++;
833 }
834
835
836
837
838
839
840
841 mult *= exp(-rest);
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862#define EFFORT 100
863
864 if ((nmcelem + unique_nitems) > 0 &&
865 unique_nitems > EFFORT * nmcelem / (nmcelem + unique_nitems))
866 {
867
868
869
870
871 double b = (double) nmcelem;
872 int n;
873
874 n = (int) ((sqrt(b * b + 4 * EFFORT * b) - b) / 2);
875
876
877 qsort(elem_selec, unique_nitems, sizeof(float),
879 unique_nitems = n;
880 }
881
882
883
884
885
886
887 dist = calc_distr(elem_selec, unique_nitems, unique_nitems, 0.0f);
888 mcelem_dist = calc_distr(numbers, nmcelem, unique_nitems, rest);
889
890
891 hist_part = calc_hist(hist, nhist - 1, unique_nitems);
892
893 selec = 0.0f;
894 for (i = 0; i <= unique_nitems; i++)
895 {
896
897
898
899
900
901 if (mcelem_dist[i] > 0)
902 selec += hist_part[i] * mult * dist[i] / mcelem_dist[i];
903 }
904
906 pfree(mcelem_dist);
907 pfree(hist_part);
908 pfree(elem_selec);
909
910
911 selec *= (1.0f - nullelem_freq);
912
914
915 return selec;
916}
917
918
919
920
921
922
923
924
925
926
927
928
929static float *
931{
932 float *hist_part;
933 int k,
934 i = 0;
935 float prev_interval = 0,
936 next_interval;
937 float frac;
938
940
941
942
943
944
945
946 frac = 1.0f / ((float) (nhist - 1));
947
948 for (k = 0; k <= n; k++)
949 {
950 int count = 0;
951
952
953
954
955
956
957
958 while (i < nhist && hist[i] <= k)
959 {
960 count++;
961 i++;
962 }
963
964 if (count > 0)
965 {
966
967 float val;
968
969
970 if (i < nhist)
971 next_interval = hist[i] - hist[i - 1];
972 else
973 next_interval = 0;
974
975
976
977
978
979
980 val = (float) (count - 1);
981 if (next_interval > 0)
982 val += 0.5f / next_interval;
983 if (prev_interval > 0)
984 val += 0.5f / prev_interval;
985 hist_part[k] = frac * val;
986
987 prev_interval = next_interval;
988 }
989 else
990 {
991
992 if (prev_interval > 0)
993 hist_part[k] = frac / prev_interval;
994 else
995 hist_part[k] = 0.0f;
996 }
997 }
998
999 return hist_part;
1000}
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018static float *
1020{
1021 float *row,
1022 *prev_row,
1023 *tmp;
1024 int i,
1025 j;
1026
1027
1028
1029
1030
1033
1034
1035 row[0] = 1.0f;
1037 {
1038 float t = p[i - 1];
1039
1040
1041 tmp = row;
1042 row = prev_row;
1043 prev_row = tmp;
1044
1045
1046 for (j = 0; j <= i && j <= m; j++)
1047 {
1048 float val = 0.0f;
1049
1051 val += prev_row[j] * (1.0f - t);
1052 if (j > 0)
1053 val += prev_row[j - 1] * t;
1055 }
1056 }
1057
1058
1059
1060
1061
1062
1064 {
1065 float t;
1066
1067
1068 tmp = row;
1069 row = prev_row;
1070 prev_row = tmp;
1071
1073 row[i] = 0.0f;
1074
1075
1076 t = exp(-rest);
1077
1078
1079
1080
1081
1083 {
1084 for (j = 0; j <= m - i; j++)
1085 row[j + i] += prev_row[j] * t;
1086
1087
1088 t *= rest / (float) (i + 1);
1089 }
1090 }
1091
1092 pfree(prev_row);
1093 return row;
1094}
1095
1096
1097static int
1099{
1100 int logval = 0;
1101
1102 if (n == 0)
1103 return -1;
1104 if (n >= (1 << 16))
1105 {
1106 n >>= 16;
1107 logval += 16;
1108 }
1109 if (n >= (1 << 8))
1110 {
1111 n >>= 8;
1112 logval += 8;
1113 }
1114 if (n >= (1 << 4))
1115 {
1116 n >>= 4;
1117 logval += 4;
1118 }
1119 if (n >= (1 << 2))
1120 {
1121 n >>= 2;
1122 logval += 2;
1123 }
1124 if (n >= (1 << 1))
1125 {
1126 logval += 1;
1127 }
1128 return logval;
1129}
1130
1131
1132
1133
1134
1135
1136
1137
1138static bool
1141{
1143 r = nmcelem - 1,
1144 i,
1145 res;
1146
1147 while (l <= r)
1148 {
1149 i = (l + r) / 2;
1151 if (res == 0)
1152 {
1154 return true;
1155 }
1156 else if (res < 0)
1157 l = i + 1;
1158 else
1159 r = i - 1;
1160 }
1162 return false;
1163}
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173static int
1175{
1181
1184}
1185
1186
1187
1188
1189static int
1191{
1192 float d1 = *((const float *) key1);
1193 float d2 = *((const float *) key2);
1194
1195 if (d1 > d2)
1196 return -1;
1197 else if (d1 < d2)
1198 return 1;
1199 else
1200 return 0;
1201}
#define DatumGetArrayTypeP(X)
Selectivity scalararraysel_containment(PlannerInfo *root, Node *leftop, Node *rightop, Oid elemtype, bool isEquality, bool useOr, int varRelid)
static int float_compare_desc(const void *key1, const void *key2)
#define DEFAULT_CONTAIN_SEL
static Selectivity calc_arraycontsel(VariableStatData *vardata, Datum constval, Oid elemtype, Oid operator)
static int floor_log2(uint32 n)
static float * calc_hist(const float4 *hist, int nhist, int n)
static Selectivity mcelem_array_contained_selec(const Datum *mcelem, int nmcelem, const float4 *numbers, int nnumbers, const Datum *array_data, int nitems, const float4 *hist, int nhist, Oid operator, TypeCacheEntry *typentry)
static int element_compare(const void *key1, const void *key2, void *arg)
static Selectivity mcelem_array_contain_overlap_selec(const Datum *mcelem, int nmcelem, const float4 *numbers, int nnumbers, const Datum *array_data, int nitems, Oid operator, TypeCacheEntry *typentry)
static bool find_next_mcelem(const Datum *mcelem, int nmcelem, Datum value, int *index, TypeCacheEntry *typentry)
static float * calc_distr(const float *p, int n, int m, float rest)
Datum arraycontsel(PG_FUNCTION_ARGS)
Datum arraycontjoinsel(PG_FUNCTION_ARGS)
#define DEFAULT_SEL(operator)
static Selectivity mcelem_array_selec(const ArrayType *array, TypeCacheEntry *typentry, const Datum *mcelem, int nmcelem, const float4 *numbers, int nnumbers, const float4 *hist, int nhist, Oid operator)
void deconstruct_array(const ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
#define OidIsValid(objectId)
#define palloc_array(type, count)
Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
#define PG_RETURN_FLOAT8(x)
#define PG_GETARG_POINTER(n)
#define PG_GETARG_INT32(n)
#define HeapTupleIsValid(tuple)
static void * GETSTRUCT(const HeapTupleData *tuple)
void free_attstatsslot(AttStatsSlot *sslot)
Oid get_base_element_type(Oid typid)
bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)
#define ATTSTATSSLOT_NUMBERS
#define ATTSTATSSLOT_VALUES
void pfree(void *pointer)
#define IsA(nodeptr, _type_)
FormData_pg_statistic * Form_pg_statistic
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
#define qsort(a, b, c, d)
static Datum PointerGetDatum(const void *X)
static int32 DatumGetInt32(Datum X)
static int cmp(const chr *x, const chr *y, size_t len)
bool get_restriction_variable(PlannerInfo *root, List *args, int varRelid, VariableStatData *vardata, Node **other, bool *varonleft)
void examine_variable(PlannerInfo *root, Node *node, int varRelid, VariableStatData *vardata)
bool statistic_proc_security_check(VariableStatData *vardata, Oid func_oid)
#define ReleaseVariableStats(vardata)
#define CLAMP_PROBABILITY(p)
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
#define TYPECACHE_CMP_PROC_FINFO