Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit9aef173

Browse files
committed
Refactor code for partition bound searching
Remove partition_bound_cmp() and partition_bound_bsearch(), whosevoid * argument could be, depending on the situation, of any ofthree different types: PartitionBoundSpec *, PartitionRangeBound *,Datum *.Instead, introduce separate bound-searching functions for eachsituation: partition_list_bsearch, partition_range_bsearch,partition_range_datum_bsearch, and partition_hash_bsearch. Thisrequires duplicating the code for binary search, but it makes thecode much more type safe, involves fewer branches at runtime, andat least in my opinion, is much easier to understand.Along the way, add an option to partition_range_datum_bsearchallowing the number of keys to be specified, so that we can searchfor partitions based on a prefix of the full list of partitionkeys. This is important for pending work to improve partitionpruning.Amit Langote, per a suggestion from me.Discussion:http://postgr.es/m/CA+TgmoaVLDLc8=YESRwD32gPhodU_ELmXyKs77gveiYp+JE4vQ@mail.gmail.com
1 parent9222c0d commit9aef173

File tree

1 file changed

+170
-95
lines changed

1 file changed

+170
-95
lines changed

‎src/backend/catalog/partition.c

Lines changed: 170 additions & 95 deletions
Original file line numberDiff line numberDiff line change
@@ -170,14 +170,21 @@ static int32 partition_rbound_cmp(PartitionKey key,
170170
boollower1,PartitionRangeBound*b2);
171171
staticint32partition_rbound_datum_cmp(PartitionKeykey,
172172
Datum*rb_datums,PartitionRangeDatumKind*rb_kind,
173-
Datum*tuple_datums);
173+
Datum*tuple_datums,intn_tuple_datums);
174174

175-
staticint32partition_bound_cmp(PartitionKeykey,
176-
PartitionBoundInfoboundinfo,
177-
intoffset,void*probe,boolprobe_is_bound);
178-
staticintpartition_bound_bsearch(PartitionKeykey,
175+
staticintpartition_list_bsearch(PartitionKeykey,
176+
PartitionBoundInfoboundinfo,
177+
Datumvalue,bool*is_equal);
178+
staticintpartition_range_bsearch(PartitionKeykey,
179179
PartitionBoundInfoboundinfo,
180-
void*probe,boolprobe_is_bound,bool*is_equal);
180+
PartitionRangeBound*probe,bool*is_equal);
181+
staticintpartition_range_datum_bsearch(PartitionKeykey,
182+
PartitionBoundInfoboundinfo,
183+
intnvalues,Datum*values,bool*is_equal);
184+
staticintpartition_hash_bsearch(PartitionKeykey,
185+
PartitionBoundInfoboundinfo,
186+
intmodulus,intremainder);
187+
181188
staticintget_partition_bound_num_indexes(PartitionBoundInfob);
182189
staticintget_greatest_modulus(PartitionBoundInfob);
183190
staticuint64compute_hash_value(PartitionKeykey,Datum*values,bool*isnull);
@@ -981,8 +988,7 @@ check_new_partition_bound(char *relname, Relation parent,
981988
intgreatest_modulus;
982989
intremainder;
983990
intoffset;
984-
boolequal,
985-
valid_modulus= true;
991+
boolvalid_modulus= true;
986992
intprev_modulus,/* Previous largest modulus */
987993
next_modulus;/* Next largest modulus */
988994

@@ -995,12 +1001,13 @@ check_new_partition_bound(char *relname, Relation parent,
9951001
* modulus 10 and a partition with modulus 15, because 10
9961002
* is not a factor of 15.
9971003
*
998-
* Get greatestbound in array boundinfo->datums which is
999-
* less than or equal tospec->modulus and
1000-
* spec->remainder.
1004+
* Getthegreatest(modulus, remainder) pair contained in
1005+
*boundinfo->datums that isless than or equal tothe
1006+
*(spec->modulus, spec->remainder) pair.
10011007
*/
1002-
offset=partition_bound_bsearch(key,boundinfo,spec,
1003-
true,&equal);
1008+
offset=partition_hash_bsearch(key,boundinfo,
1009+
spec->modulus,
1010+
spec->remainder);
10041011
if (offset<0)
10051012
{
10061013
next_modulus=DatumGetInt32(datums[0][0]);
@@ -1074,9 +1081,9 @@ check_new_partition_bound(char *relname, Relation parent,
10741081
intoffset;
10751082
boolequal;
10761083

1077-
offset=partition_bound_bsearch(key,boundinfo,
1078-
&val->constvalue,
1079-
true,&equal);
1084+
offset=partition_list_bsearch(key,boundinfo,
1085+
val->constvalue,
1086+
&equal);
10801087
if (offset >=0&&equal)
10811088
{
10821089
overlap= true;
@@ -1148,8 +1155,8 @@ check_new_partition_bound(char *relname, Relation parent,
11481155
* since the index array is initialised with an extra -1
11491156
* at the end.
11501157
*/
1151-
offset=partition_bound_bsearch(key,boundinfo,lower,
1152-
true,&equal);
1158+
offset=partition_range_bsearch(key,boundinfo,lower,
1159+
&equal);
11531160

11541161
if (boundinfo->indexes[offset+1]<0)
11551162
{
@@ -1162,10 +1169,16 @@ check_new_partition_bound(char *relname, Relation parent,
11621169
if (offset+1<boundinfo->ndatums)
11631170
{
11641171
int32cmpval;
1172+
Datum*datums;
1173+
PartitionRangeDatumKind*kind;
1174+
boolis_lower;
1175+
1176+
datums=boundinfo->datums[offset+1];
1177+
kind=boundinfo->kind[offset+1];
1178+
is_lower= (boundinfo->indexes[offset+1]==-1);
11651179

1166-
cmpval=partition_bound_cmp(key,boundinfo,
1167-
offset+1,upper,
1168-
true);
1180+
cmpval=partition_rbound_cmp(key,datums,kind,
1181+
is_lower,upper);
11691182
if (cmpval<0)
11701183
{
11711184
/*
@@ -2574,11 +2587,9 @@ get_partition_for_tuple(Relation relation, Datum *values, bool *isnull)
25742587
{
25752588
boolequal= false;
25762589

2577-
bound_offset=partition_bound_bsearch(key,
2578-
partdesc->boundinfo,
2579-
values,
2580-
false,
2581-
&equal);
2590+
bound_offset=partition_list_bsearch(key,
2591+
partdesc->boundinfo,
2592+
values[0],&equal);
25822593
if (bound_offset >=0&&equal)
25832594
part_index=partdesc->boundinfo->indexes[bound_offset];
25842595
}
@@ -2605,12 +2616,11 @@ get_partition_for_tuple(Relation relation, Datum *values, bool *isnull)
26052616

26062617
if (!range_partkey_has_null)
26072618
{
2608-
bound_offset=partition_bound_bsearch(key,
2609-
partdesc->boundinfo,
2610-
values,
2611-
false,
2612-
&equal);
2613-
2619+
bound_offset=partition_range_datum_bsearch(key,
2620+
partdesc->boundinfo,
2621+
key->partnatts,
2622+
values,
2623+
&equal);
26142624
/*
26152625
* The bound at bound_offset is less than or equal to the
26162626
* tuple value, so the bound at offset+1 is the upper
@@ -2881,12 +2891,12 @@ partition_rbound_cmp(PartitionKey key,
28812891
staticint32
28822892
partition_rbound_datum_cmp(PartitionKeykey,
28832893
Datum*rb_datums,PartitionRangeDatumKind*rb_kind,
2884-
Datum*tuple_datums)
2894+
Datum*tuple_datums,intn_tuple_datums)
28852895
{
28862896
inti;
28872897
int32cmpval=-1;
28882898

2889-
for (i=0;i<key->partnatts;i++)
2899+
for (i=0;i<n_tuple_datums;i++)
28902900
{
28912901
if (rb_kind[i]==PARTITION_RANGE_DATUM_MINVALUE)
28922902
return-1;
@@ -2905,84 +2915,104 @@ partition_rbound_datum_cmp(PartitionKey key,
29052915
}
29062916

29072917
/*
2908-
* partition_bound_cmp
2918+
* partition_list_bsearch
2919+
*Returns the index of the greatest bound datum that is less than equal
2920+
* to the given value or -1 if all of the bound datums are greater
29092921
*
2910-
*Return whether the bound at offset in boundinfo is <, =, or > the argument
2911-
*specified in *probe.
2922+
**is_equal is set to true if the bound datum at the returned index is equal
2923+
*to the input value.
29122924
*/
2913-
staticint32
2914-
partition_bound_cmp(PartitionKeykey,PartitionBoundInfoboundinfo,
2915-
intoffset,void*probe,boolprobe_is_bound)
2925+
staticint
2926+
partition_list_bsearch(PartitionKeykey,
2927+
PartitionBoundInfoboundinfo,
2928+
Datumvalue,bool*is_equal)
29162929
{
2917-
Datum*bound_datums=boundinfo->datums[offset];
2918-
int32cmpval=-1;
2930+
intlo,
2931+
hi,
2932+
mid;
29192933

2920-
switch (key->strategy)
2934+
lo=-1;
2935+
hi=boundinfo->ndatums-1;
2936+
while (lo<hi)
29212937
{
2922-
casePARTITION_STRATEGY_HASH:
2923-
{
2924-
PartitionBoundSpec*spec= (PartitionBoundSpec*)probe;
2938+
int32cmpval;
29252939

2926-
cmpval=partition_hbound_cmp(DatumGetInt32(bound_datums[0]),
2927-
DatumGetInt32(bound_datums[1]),
2928-
spec->modulus,spec->remainder);
2940+
mid= (lo+hi+1) /2;
2941+
cmpval=DatumGetInt32(FunctionCall2Coll(&key->partsupfunc[0],
2942+
key->partcollation[0],
2943+
boundinfo->datums[mid][0],
2944+
value));
2945+
if (cmpval <=0)
2946+
{
2947+
lo=mid;
2948+
*is_equal= (cmpval==0);
2949+
if (*is_equal)
29292950
break;
2930-
}
2931-
casePARTITION_STRATEGY_LIST:
2932-
cmpval=DatumGetInt32(FunctionCall2Coll(&key->partsupfunc[0],
2933-
key->partcollation[0],
2934-
bound_datums[0],
2935-
*(Datum*)probe));
2936-
break;
2951+
}
2952+
else
2953+
hi=mid-1;
2954+
}
29372955

2938-
casePARTITION_STRATEGY_RANGE:
2939-
{
2940-
PartitionRangeDatumKind*kind=boundinfo->kind[offset];
2956+
returnlo;
2957+
}
29412958

2942-
if (probe_is_bound)
2943-
{
2944-
/*
2945-
* We need to pass whether the existing bound is a lower
2946-
* bound, so that two equal-valued lower and upper bounds
2947-
* are not regarded equal.
2948-
*/
2949-
boollower=boundinfo->indexes[offset]<0;
2959+
/*
2960+
* partition_range_bsearch
2961+
*Returns the index of the greatest range bound that is less than or
2962+
*equal to the given range bound or -1 if all of the range bounds are
2963+
*greater
2964+
*
2965+
* *is_equal is set to true if the range bound at the returned index is equal
2966+
* to the input range bound
2967+
*/
2968+
staticint
2969+
partition_range_bsearch(PartitionKeykey,
2970+
PartitionBoundInfoboundinfo,
2971+
PartitionRangeBound*probe,bool*is_equal)
2972+
{
2973+
intlo,
2974+
hi,
2975+
mid;
29502976

2951-
cmpval=partition_rbound_cmp(key,
2952-
bound_datums,kind,lower,
2953-
(PartitionRangeBound*)probe);
2954-
}
2955-
else
2956-
cmpval=partition_rbound_datum_cmp(key,
2957-
bound_datums,kind,
2958-
(Datum*)probe);
2959-
break;
2960-
}
2977+
lo=-1;
2978+
hi=boundinfo->ndatums-1;
2979+
while (lo<hi)
2980+
{
2981+
int32cmpval;
29612982

2962-
default:
2963-
elog(ERROR,"unexpected partition strategy: %d",
2964-
(int)key->strategy);
2983+
mid= (lo+hi+1) /2;
2984+
cmpval=partition_rbound_cmp(key,
2985+
boundinfo->datums[mid],
2986+
boundinfo->kind[mid],
2987+
(boundinfo->indexes[mid]==-1),
2988+
probe);
2989+
if (cmpval <=0)
2990+
{
2991+
lo=mid;
2992+
*is_equal= (cmpval==0);
2993+
2994+
if (*is_equal)
2995+
break;
2996+
}
2997+
else
2998+
hi=mid-1;
29652999
}
29663000

2967-
returncmpval;
3001+
returnlo;
29683002
}
29693003

29703004
/*
2971-
* Binary search on a collection of partition bounds. Returns greatest
2972-
* bound in array boundinfo->datums which is less than or equal to *probe.
2973-
* If all bounds in the array are greater than *probe, -1 is returned.
2974-
*
2975-
* *probe could either be a partition bound or a Datum array representing
2976-
* the partition key of a tuple being routed; probe_is_bound tells which.
2977-
* We pass that down to the comparison function so that it can interpret the
2978-
* contents of *probe accordingly.
3005+
* partition_range_bsearch
3006+
*Returns the index of the greatest range bound that is less than or
3007+
*equal to the given tuple or -1 if all of the range bounds are greater
29793008
*
2980-
* *is_equal is set towhetherthe bound at the returned index is equal with
2981-
**probe.
3009+
* *is_equal is set totrue iftherangebound at the returned index is equal
3010+
*to the input tuple.
29823011
*/
29833012
staticint
2984-
partition_bound_bsearch(PartitionKeykey,PartitionBoundInfoboundinfo,
2985-
void*probe,boolprobe_is_bound,bool*is_equal)
3013+
partition_range_datum_bsearch(PartitionKeykey,
3014+
PartitionBoundInfoboundinfo,
3015+
intnvalues,Datum*values,bool*is_equal)
29863016
{
29873017
intlo,
29883018
hi,
@@ -2995,8 +3025,11 @@ partition_bound_bsearch(PartitionKey key, PartitionBoundInfo boundinfo,
29953025
int32cmpval;
29963026

29973027
mid= (lo+hi+1) /2;
2998-
cmpval=partition_bound_cmp(key,boundinfo,mid,probe,
2999-
probe_is_bound);
3028+
cmpval=partition_rbound_datum_cmp(key,
3029+
boundinfo->datums[mid],
3030+
boundinfo->kind[mid],
3031+
values,
3032+
nvalues);
30003033
if (cmpval <=0)
30013034
{
30023035
lo=mid;
@@ -3012,6 +3045,48 @@ partition_bound_bsearch(PartitionKey key, PartitionBoundInfo boundinfo,
30123045
returnlo;
30133046
}
30143047

3048+
/*
3049+
* partition_hash_bsearch
3050+
*Returns the index of the greatest (modulus, remainder) pair that is
3051+
*less than or equal to the given (modulus, remainder) pair or -1 if
3052+
*all of them are greater
3053+
*/
3054+
staticint
3055+
partition_hash_bsearch(PartitionKeykey,
3056+
PartitionBoundInfoboundinfo,
3057+
intmodulus,intremainder)
3058+
{
3059+
intlo,
3060+
hi,
3061+
mid;
3062+
3063+
lo=-1;
3064+
hi=boundinfo->ndatums-1;
3065+
while (lo<hi)
3066+
{
3067+
int32cmpval,
3068+
bound_modulus,
3069+
bound_remainder;
3070+
3071+
mid= (lo+hi+1) /2;
3072+
bound_modulus=DatumGetInt32(boundinfo->datums[mid][0]);
3073+
bound_remainder=DatumGetInt32(boundinfo->datums[mid][1]);
3074+
cmpval=partition_hbound_cmp(bound_modulus,bound_remainder,
3075+
modulus,remainder);
3076+
if (cmpval <=0)
3077+
{
3078+
lo=mid;
3079+
3080+
if (cmpval==0)
3081+
break;
3082+
}
3083+
else
3084+
hi=mid-1;
3085+
}
3086+
3087+
returnlo;
3088+
}
3089+
30153090
/*
30163091
* get_default_oid_from_partdesc
30173092
*

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp