PostgreSQL Source Code: src/backend/utils/adt/array_selfuncs.c File Reference (original) (raw)

#include "[postgres.h](postgres%5F8h%5Fsource.html)"
#include <math.h>
#include "[access/htup_details.h](htup%5F%5Fdetails%5F8h%5Fsource.html)"
#include "[catalog/pg_operator.h](pg%5F%5Foperator%5F8h%5Fsource.html)"
#include "[catalog/pg_statistic.h](pg%5F%5Fstatistic%5F8h%5Fsource.html)"
#include "[utils/array.h](array%5F8h%5Fsource.html)"
#include "utils/fmgrprotos.h"
#include "[utils/lsyscache.h](lsyscache%5F8h%5Fsource.html)"
#include "[utils/selfuncs.h](selfuncs%5F8h%5Fsource.html)"
#include "[utils/typcache.h](typcache%5F8h%5Fsource.html)"

Go to the source code of this file.

◆ DEFAULT_CONTAIN_SEL

#define DEFAULT_CONTAIN_SEL 0.005

◆ DEFAULT_OVERLAP_SEL

#define DEFAULT_OVERLAP_SEL 0.01

◆ DEFAULT_SEL

| #define DEFAULT_SEL | ( | | operator | ) | | -------------------- | - | | -------- | - |

Value:

((operator) == OID_ARRAY_OVERLAP_OP ? \

#define DEFAULT_CONTAIN_SEL

#define DEFAULT_OVERLAP_SEL

Definition at line 36 of file array_selfuncs.c.

◆ EFFORT

◆ arraycontjoinsel()

◆ arraycontsel()

Definition at line 241 of file array_selfuncs.c.

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}

static Selectivity calc_arraycontsel(VariableStatData *vardata, Datum constval, Oid elemtype, Oid operator)

#define PG_GETARG_POINTER(n)

#define PG_GETARG_INT32(n)

Oid get_base_element_type(Oid typid)

#define IsA(nodeptr, _type_)

bool get_restriction_variable(PlannerInfo *root, List *args, int varRelid, VariableStatData *vardata, Node **other, bool *varonleft)

#define ReleaseVariableStats(vardata)

#define CLAMP_PROBABILITY(p)

References generate_unaccent_rules::args, calc_arraycontsel(), CLAMP_PROBABILITY, DEFAULT_SEL, get_base_element_type(), get_restriction_variable(), InvalidOid, IsA, PG_GETARG_INT32, PG_GETARG_OID, PG_GETARG_POINTER, PG_RETURN_FLOAT8, ReleaseVariableStats, root, and VariableStatData::vartype.

Referenced by _int_contained_sel(), _int_contains_sel(), and _int_overlap_sel().

◆ calc_arraycontsel()

Definition at line 337 of file array_selfuncs.c.

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}

#define DatumGetArrayTypeP(X)

static Selectivity mcelem_array_selec(ArrayType *array, TypeCacheEntry *typentry, Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, float4 *hist, int nhist, Oid operator)

#define OidIsValid(objectId)

#define HeapTupleIsValid(tuple)

static void * GETSTRUCT(const HeapTupleData *tuple)

void free_attstatsslot(AttStatsSlot *sslot)

bool get_attstatsslot(AttStatsSlot *sslot, HeapTuple statstuple, int reqkind, Oid reqop, int flags)

#define ATTSTATSSLOT_NUMBERS

#define ATTSTATSSLOT_VALUES

void pfree(void *pointer)

FormData_pg_statistic * Form_pg_statistic

static Datum PointerGetDatum(const void *X)

bool statistic_proc_security_check(VariableStatData *vardata, Oid func_oid)

TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)

#define TYPECACHE_CMP_PROC_FINFO

References ATTSTATSSLOT_NUMBERS, ATTSTATSSLOT_VALUES, TypeCacheEntry::cmp_proc_finfo, DatumGetArrayTypeP, DEFAULT_SEL, FmgrInfo::fn_oid, free_attstatsslot(), get_attstatsslot(), GETSTRUCT(), HeapTupleIsValid, InvalidOid, lookup_type_cache(), mcelem_array_selec(), AttStatsSlot::nnumbers, AttStatsSlot::numbers, AttStatsSlot::nvalues, OidIsValid, pfree(), PointerGetDatum(), statistic_proc_security_check(), VariableStatData::statsTuple, TYPECACHE_CMP_PROC_FINFO, and AttStatsSlot::values.

Referenced by arraycontsel().

◆ calc_distr()

Definition at line 1010 of file array_selfuncs.c.

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;

1027 for (i = 1; i <= n; i++)

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

1041 if (j < i)

1042 val += prev_row[j] * (1.0f - t);

1043 if (j > 0)

1044 val += prev_row[j - 1] * t;

1045 row[j] = val;

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

1063 for (i = 0; i <= m; i++)

1064 row[i] = 0.0f;

1065

1066

1067 t = exp(-rest);

1068

1069

1070

1071

1072

1073 for (i = 0; i <= m; i++)

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}

References DEFAULT_CONTAIN_SEL, i, j, palloc(), pfree(), and val.

Referenced by mcelem_array_contained_selec().

◆ calc_hist()

Definition at line 921 of file array_selfuncs.c.

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}

References i, palloc(), and val.

Referenced by mcelem_array_contained_selec().

◆ element_compare()

Definition at line 1165 of file array_selfuncs.c.

1166{

1172

1175}

Datum FunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)

static int32 DatumGetInt32(Datum X)

References arg, TypeCacheEntry::cmp_proc_finfo, DatumGetInt32(), FunctionCall2Coll(), and TypeCacheEntry::typcollation.

Referenced by find_next_mcelem(), mcelem_array_contain_overlap_selec(), mcelem_array_contained_selec(), and mcelem_array_selec().

◆ find_next_mcelem()

Definition at line 1130 of file array_selfuncs.c.

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}

static int element_compare(const void *key1, const void *key2, void *arg)

References element_compare(), i, and value.

Referenced by mcelem_array_contain_overlap_selec().

◆ float_compare_desc()

Definition at line 1181 of file array_selfuncs.c.

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}

Referenced by mcelem_array_contained_selec().

◆ floor_log2()

Definition at line 1089 of file array_selfuncs.c.

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}

Referenced by mcelem_array_contain_overlap_selec().

◆ mcelem_array_contain_overlap_selec()

Definition at line 521 of file array_selfuncs.c.

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}

static int floor_log2(uint32 n)

static bool find_next_mcelem(Datum *mcelem, int nmcelem, Datum value, int *index, TypeCacheEntry *typentry)

static int cmp(const chr *x, const chr *y, size_t len)

References CLAMP_PROBABILITY, cmp(), DEFAULT_CONTAIN_SEL, element_compare(), find_next_mcelem(), floor_log2(), i, Min, and nitems.

Referenced by mcelem_array_selec(), and scalararraysel_containment().

◆ mcelem_array_contained_selec()

Definition at line 696 of file array_selfuncs.c.

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}

static int float_compare_desc(const void *key1, const void *key2)

static float * calc_hist(const float4 *hist, int nhist, int n)

static float * calc_distr(const float *p, int n, int m, float rest)

#define qsort(a, b, c, d)

References b, calc_distr(), calc_hist(), CLAMP_PROBABILITY, cmp(), DEFAULT_CONTAIN_SEL, EFFORT, element_compare(), float_compare_desc(), i, Min, nitems, palloc(), pfree(), and qsort.

Referenced by mcelem_array_selec(), and scalararraysel_containment().

◆ mcelem_array_selec()

Definition at line 428 of file array_selfuncs.c.

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}

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)

static Selectivity mcelem_array_contain_overlap_selec(Datum *mcelem, int nmcelem, float4 *numbers, int nnumbers, Datum *array_data, int nitems, Oid operator, TypeCacheEntry *typentry)

void deconstruct_array(ArrayType *array, Oid elmtype, int elmlen, bool elmbyval, char elmalign, Datum **elemsp, bool **nullsp, int *nelemsp)

void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)

References deconstruct_array(), element_compare(), elog, ERROR, i, mcelem_array_contain_overlap_selec(), mcelem_array_contained_selec(), pfree(), qsort_arg(), TypeCacheEntry::typalign, TypeCacheEntry::typbyval, TypeCacheEntry::type_id, and TypeCacheEntry::typlen.

Referenced by calc_arraycontsel().

◆ scalararraysel_containment()

Definition at line 81 of file array_selfuncs.c.

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}

void examine_variable(PlannerInfo *root, Node *node, int varRelid, VariableStatData *vardata)

References ATTSTATSSLOT_NUMBERS, ATTSTATSSLOT_VALUES, CLAMP_PROBABILITY, TypeCacheEntry::cmp_proc_finfo, examine_variable(), FmgrInfo::fn_oid, free_attstatsslot(), get_attstatsslot(), GETSTRUCT(), HeapTupleIsValid, InvalidOid, IsA, lookup_type_cache(), mcelem_array_contain_overlap_selec(), mcelem_array_contained_selec(), AttStatsSlot::nnumbers, AttStatsSlot::numbers, AttStatsSlot::nvalues, OidIsValid, VariableStatData::rel, ReleaseVariableStats, root, statistic_proc_security_check(), VariableStatData::statsTuple, TYPECACHE_CMP_PROC_FINFO, and AttStatsSlot::values.

Referenced by scalararraysel().