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;

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}

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