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 Datum *mcelem, int nmcelem,
45 float4 *numbers, int nnumbers,
46 float4 *hist, int nhist,
47 Oid operator);
49 float4 *numbers, int nnumbers,
53 float4 *numbers, int nnumbers,
55 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 Datum *mcelem, int nmcelem,
430 float4 *numbers, int nnumbers,
431 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 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
554 }
555
556
558 use_bsearch = true;
559 else
560 use_bsearch = false;
561
562 if (operator == OID_ARRAY_CONTAINS_OP)
563 {
564
565
566
567
568 selec = 1.0;
569 }
570 else
571 {
572
573
574
575
576 selec = 0.0;
577 }
578
579
580 mcelem_index = 0;
582 {
583 bool match = false;
584
585
586 if (i > 0 &&
587 element_compare(&array_data[i - 1], &array_data[i], typentry) == 0)
588 continue;
589
590
591 if (use_bsearch)
592 {
594 &mcelem_index, typentry);
595 }
596 else
597 {
598 while (mcelem_index < nmcelem)
599 {
601 &array_data[i],
602 typentry);
603
604 if (cmp < 0)
605 mcelem_index++;
606 else
607 {
608 if (cmp == 0)
609 match = true;
610 break;
611 }
612 }
613 }
614
615 if (match && numbers)
616 {
617
618 elem_selec = numbers[mcelem_index];
619 mcelem_index++;
620 }
621 else
622 {
623
624
625
626
628 }
629
630
631
632
633
634 if (operator == OID_ARRAY_CONTAINS_OP)
635 selec *= elem_selec;
636 else
637 selec = selec + elem_selec - selec * elem_selec;
638
639
641 }
642
643 return selec;
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
697 float4 *numbers, int nnumbers,
699 float4 *hist, int nhist,
701{
702 int mcelem_index,
703 i,
704 unique_nitems = 0;
705 float selec,
706 minfreq,
707 nullelem_freq;
708 float *dist,
709 *mcelem_dist,
710 *hist_part;
711 float avg_count,
712 mult,
713 rest;
714 float *elem_selec;
715
716
717
718
719
720
721
722 if (numbers == NULL || nnumbers != nmcelem + 3)
724
725
726 if (hist == NULL || nhist < 3)
728
729
730
731
732
733
734 minfreq = numbers[nmcelem];
735 nullelem_freq = numbers[nmcelem + 2];
736 avg_count = hist[nhist - 1];
737
738
739
740
741
742
743
744 rest = avg_count;
745
746
747
748
749
750 mult = 1.0f;
751
752
753
754
755
756 elem_selec = (float *) palloc(sizeof(float) * nitems);
757
758
759 mcelem_index = 0;
761 {
762 bool match = false;
763
764
765 if (i > 0 &&
766 element_compare(&array_data[i - 1], &array_data[i], typentry) == 0)
767 continue;
768
769
770
771
772
773
774 while (mcelem_index < nmcelem)
775 {
777 &array_data[i],
778 typentry);
779
780 if (cmp < 0)
781 {
782 mult *= (1.0f - numbers[mcelem_index]);
783 rest -= numbers[mcelem_index];
784 mcelem_index++;
785 }
786 else
787 {
788 if (cmp == 0)
789 match = true;
790 break;
791 }
792 }
793
794 if (match)
795 {
796
797 elem_selec[unique_nitems] = numbers[mcelem_index];
798
799 rest -= numbers[mcelem_index];
800 mcelem_index++;
801 }
802 else
803 {
804
805
806
807
809 minfreq / 2);
810 }
811
812 unique_nitems++;
813 }
814
815
816
817
818
819 while (mcelem_index < nmcelem)
820 {
821 mult *= (1.0f - numbers[mcelem_index]);
822 rest -= numbers[mcelem_index];
823 mcelem_index++;
824 }
825
826
827
828
829
830
831
832 mult *= exp(-rest);
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853#define EFFORT 100
854
855 if ((nmcelem + unique_nitems) > 0 &&
856 unique_nitems > EFFORT * nmcelem / (nmcelem + unique_nitems))
857 {
858
859
860
861
862 double b = (double) nmcelem;
863 int n;
864
865 n = (int) ((sqrt(b * b + 4 * EFFORT * b) - b) / 2);
866
867
868 qsort(elem_selec, unique_nitems, sizeof(float),
870 unique_nitems = n;
871 }
872
873
874
875
876
877
878 dist = calc_distr(elem_selec, unique_nitems, unique_nitems, 0.0f);
879 mcelem_dist = calc_distr(numbers, nmcelem, unique_nitems, rest);
880
881
882 hist_part = calc_hist(hist, nhist - 1, unique_nitems);
883
884 selec = 0.0f;
885 for (i = 0; i <= unique_nitems; i++)
886 {
887
888
889
890
891
892 if (mcelem_dist[i] > 0)
893 selec += hist_part[i] * mult * dist[i] / mcelem_dist[i];
894 }
895
897 pfree(mcelem_dist);
898 pfree(hist_part);
899 pfree(elem_selec);
900
901
902 selec *= (1.0f - nullelem_freq);
903
905
906 return selec;
907}
908
909
910
911
912
913
914
915
916
917
918
919
920static float *
922{
923 float *hist_part;
924 int k,
925 i = 0;
926 float prev_interval = 0,
927 next_interval;
928 float frac;
929
930 hist_part = (float *) palloc((n + 1) * sizeof(float));
931
932
933
934
935
936
937 frac = 1.0f / ((float) (nhist - 1));
938
939 for (k = 0; k <= n; k++)
940 {
941 int count = 0;
942
943
944
945
946
947
948
949 while (i < nhist && hist[i] <= k)
950 {
951 count++;
952 i++;
953 }
954
955 if (count > 0)
956 {
957
958 float val;
959
960
961 if (i < nhist)
962 next_interval = hist[i] - hist[i - 1];
963 else
964 next_interval = 0;
965
966
967
968
969
970
971 val = (float) (count - 1);
972 if (next_interval > 0)
973 val += 0.5f / next_interval;
974 if (prev_interval > 0)
975 val += 0.5f / prev_interval;
976 hist_part[k] = frac * val;
977
978 prev_interval = next_interval;
979 }
980 else
981 {
982
983 if (prev_interval > 0)
984 hist_part[k] = frac / prev_interval;
985 else
986 hist_part[k] = 0.0f;
987 }
988 }
989
990 return hist_part;
991}
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009static float *
1011{
1012 float *row,
1013 *prev_row,
1014 *tmp;
1015 int i,
1016 j;
1017
1018
1019
1020
1021
1022 row = (float *) palloc((m + 1) * sizeof(float));
1023 prev_row = (float *) palloc((m + 1) * sizeof(float));
1024
1025
1026 row[0] = 1.0f;
1028 {
1029 float t = p[i - 1];
1030
1031
1032 tmp = row;
1033 row = prev_row;
1034 prev_row = tmp;
1035
1036
1037 for (j = 0; j <= i && j <= m; j++)
1038 {
1039 float val = 0.0f;
1040
1042 val += prev_row[j] * (1.0f - t);
1043 if (j > 0)
1044 val += prev_row[j - 1] * t;
1046 }
1047 }
1048
1049
1050
1051
1052
1053
1055 {
1056 float t;
1057
1058
1059 tmp = row;
1060 row = prev_row;
1061 prev_row = tmp;
1062
1064 row[i] = 0.0f;
1065
1066
1067 t = exp(-rest);
1068
1069
1070
1071
1072
1074 {
1075 for (j = 0; j <= m - i; j++)
1076 row[j + i] += prev_row[j] * t;
1077
1078
1079 t *= rest / (float) (i + 1);
1080 }
1081 }
1082
1083 pfree(prev_row);
1084 return row;
1085}
1086
1087
1088static int
1090{
1091 int logval = 0;
1092
1093 if (n == 0)
1094 return -1;
1095 if (n >= (1 << 16))
1096 {
1097 n >>= 16;
1098 logval += 16;
1099 }
1100 if (n >= (1 << 8))
1101 {
1102 n >>= 8;
1103 logval += 8;
1104 }
1105 if (n >= (1 << 4))
1106 {
1107 n >>= 4;
1108 logval += 4;
1109 }
1110 if (n >= (1 << 2))
1111 {
1112 n >>= 2;
1113 logval += 2;
1114 }
1115 if (n >= (1 << 1))
1116 {
1117 logval += 1;
1118 }
1119 return logval;
1120}
1121
1122
1123
1124
1125
1126
1127
1128
1129static bool
1132{
1134 r = nmcelem - 1,
1135 i,
1136 res;
1137
1138 while (l <= r)
1139 {
1140 i = (l + r) / 2;
1142 if (res == 0)
1143 {
1145 return true;
1146 }
1147 else if (res < 0)
1148 l = i + 1;
1149 else
1150 r = i - 1;
1151 }
1153 return false;
1154}
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164static int
1166{
1172
1175}
1176
1177
1178
1179
1180static int
1182{
1183 float d1 = *((const float *) key1);
1184 float d2 = *((const float *) key2);
1185
1186 if (d1 > d2)
1187 return -1;
1188 else if (d1 < d2)
1189 return 1;
1190 else
1191 return 0;
1192}
#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)
static Selectivity mcelem_array_contained_selec(Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, Datum *array_data, int nitems, float4 *hist, int nhist, Oid operator, TypeCacheEntry *typentry)
#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 int element_compare(const void *key1, const void *key2, void *arg)
static float * calc_distr(const float *p, int n, int m, float rest)
Datum arraycontsel(PG_FUNCTION_ARGS)
static Selectivity mcelem_array_selec(ArrayType *array, TypeCacheEntry *typentry, Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, float4 *hist, int nhist, Oid operator)
static Selectivity mcelem_array_contain_overlap_selec(Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, Datum *array_data, int nitems, Oid operator, TypeCacheEntry *typentry)
Datum arraycontjoinsel(PG_FUNCTION_ARGS)
#define DEFAULT_SEL(operator)
static bool find_next_mcelem(Datum *mcelem, int nmcelem, Datum value, int *index, TypeCacheEntry *typentry)
void deconstruct_array(ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)
#define OidIsValid(objectId)
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