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

Commit5df33e2

Browse files
author
Nikita Glukhov
committed
Sort jsonb object values by length
1 parent8c8ced1 commit5df33e2

File tree

2 files changed

+173
-29
lines changed

2 files changed

+173
-29
lines changed

‎src/backend/utils/adt/jsonb_util.c

Lines changed: 164 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,8 @@
3030
#include"utils/memutils.h"
3131
#include"utils/varlena.h"
3232

33+
#defineJSONB_SORTED_VALUES 1
34+
3335
/*
3436
* Maximum number of elements in an array (or key/value pairs in an object).
3537
* This is limited by two things: the size of the JEntry array must fit
@@ -82,6 +84,7 @@ typedef struct jsonbIterator
8284
constJEntry*children;/* JEntrys for child nodes */
8385
/* Data proper. This points to the beginning of the variable-length data */
8486
char*dataProper;
87+
uint32*kvMap;
8588

8689
/* Current item in buffer (up to nElems) */
8790
intcurIndex;
@@ -556,6 +559,8 @@ jsonbFindKeyInObject(JsonContainer *jsc, const char *keyVal, int keyLen,
556559
constJEntry*children=container->children;
557560
intcount=JsonContainerSize(jsc);
558561
char*baseAddr;
562+
boolsorted_values= (container->header&JBC_TMASK)==JBC_TOBJECT_SORTED;
563+
constuint32*kvmap;
559564
uint32stopLow,
560565
stopHigh;
561566

@@ -569,7 +574,16 @@ jsonbFindKeyInObject(JsonContainer *jsc, const char *keyVal, int keyLen,
569574
* Binary search the container. Since we know this is an object, account
570575
* for *Pairs* of Jentrys
571576
*/
572-
baseAddr= (char*) (children+count*2);
577+
if (sorted_values)
578+
{
579+
kvmap=&children[count*2];
580+
baseAddr= (char*)&kvmap[count];
581+
}
582+
else
583+
{
584+
kvmap=NULL;
585+
baseAddr= (char*) (children+count*2);
586+
}
573587
stopLow=0;
574588
stopHigh=count;
575589
while (stopLow<stopHigh)
@@ -590,7 +604,7 @@ jsonbFindKeyInObject(JsonContainer *jsc, const char *keyVal, int keyLen,
590604
if (difference==0)
591605
{
592606
/* Found our key, return corresponding value */
593-
intindex=stopMiddle+count;
607+
intindex=(sorted_values ?kvmap[stopMiddle] :stopMiddle)+count;
594608

595609
if (!res)
596610
res=palloc(sizeof(JsonbValue));
@@ -1203,14 +1217,18 @@ jsonbIteratorNext(JsonIterator **jsit, JsonbValue *val, bool skipNested)
12031217
(*it)->state=JBI_OBJECT_KEY;
12041218

12051219
fillCompressedJsonbValue((*it)->compressed, (*it)->container,
1206-
(*it)->curIndex+ (*it)->nElems,
1207-
(*it)->dataProper, (*it)->curValueOffset,
1220+
((*it)->kvMap ? (*it)->kvMap[(*it)->curIndex] : (*it)->curIndex)+ (*it)->nElems,
1221+
(*it)->dataProper,
1222+
(*it)->kvMap ?
1223+
getJsonbOffset((*it)->container, (*it)->kvMap[(*it)->curIndex]+ (*it)->nElems) :
1224+
(*it)->curValueOffset,
12081225
val);
12091226

12101227
JBE_ADVANCE_OFFSET((*it)->curDataOffset,
12111228
(*it)->children[(*it)->curIndex]);
1212-
JBE_ADVANCE_OFFSET((*it)->curValueOffset,
1213-
(*it)->children[(*it)->curIndex+ (*it)->nElems]);
1229+
if (!(*it)->kvMap)
1230+
JBE_ADVANCE_OFFSET((*it)->curValueOffset,
1231+
(*it)->children[(*it)->curIndex+ (*it)->nElems]);
12141232
(*it)->curIndex++;
12151233

12161234
/*
@@ -1263,24 +1281,34 @@ jsonbIteratorInitExt(JsonContainer *cont,
12631281
/* Array starts just after header */
12641282
it->children=container->children;
12651283

1266-
switch (container->header&(JBC_FARRAY |JBC_FOBJECT))
1284+
switch (container->header&JBC_TMASK)
12671285
{
1268-
caseJBC_FARRAY:
1286+
caseJBC_TSCALAR:
1287+
it->isScalar= true;
1288+
/* FALLTHROUGH */
1289+
caseJBC_TARRAY:
12691290
it->dataProper=
12701291
(char*)it->children+it->nElems*sizeof(JEntry);
1271-
it->isScalar= (container->header&JBC_FSCALAR)!=0;
12721292
/* This is either a "raw scalar", or an array */
12731293
Assert(!it->isScalar||it->nElems==1);
12741294

12751295
it->state=JBI_ARRAY_START;
12761296
break;
12771297

1278-
caseJBC_FOBJECT:
1298+
caseJBC_TOBJECT:
1299+
it->kvMap=NULL;
12791300
it->dataProper=
12801301
(char*)it->children+it->nElems*sizeof(JEntry)*2;
12811302
it->state=JBI_OBJECT_START;
12821303
break;
12831304

1305+
caseJBC_TOBJECT_SORTED:
1306+
it->kvMap= (uint32*)
1307+
((char*)it->children+it->nElems*sizeof(JEntry)*2);
1308+
it->dataProper= (char*)&it->kvMap[it->nElems];
1309+
it->state=JBI_OBJECT_START;
1310+
break;
1311+
12841312
default:
12851313
elog(ERROR,"unknown type of jsonb container");
12861314
}
@@ -1887,13 +1915,14 @@ convertJsonbArray(StringInfo buffer, JEntry *pheader, const JsonbValue *val, int
18871915
* Construct the header Jentry and store it in the beginning of the
18881916
* variable-length payload.
18891917
*/
1890-
header=nElems |JBC_FARRAY;
18911918
if (val->val.array.rawScalar)
18921919
{
18931920
Assert(nElems==1);
18941921
Assert(level==0);
1895-
header|=JBC_FSCALAR;
1922+
header=nElems |JBC_TSCALAR;
18961923
}
1924+
else
1925+
header=nElems |JBC_TARRAY;
18971926

18981927
appendToBuffer(buffer, (char*)&header,sizeof(uint32));
18991928

@@ -1951,6 +1980,48 @@ convertJsonbArray(StringInfo buffer, JEntry *pheader, const JsonbValue *val, int
19511980
*pheader=JENTRY_ISCONTAINER |totallen;
19521981
}
19531982

1983+
staticint
1984+
int_cmp(constvoid*a,constvoid*b)
1985+
{
1986+
intx=*(constint*)a;
1987+
inty=*(constint*)b;
1988+
1989+
returnx==y ?0 :x>y ?1 :-1;
1990+
}
1991+
1992+
staticint
1993+
estimateJsonbValueSize(constJsonbValue*jbv)
1994+
{
1995+
intsize;
1996+
1997+
switch (jbv->type)
1998+
{
1999+
casejbvNull:
2000+
casejbvBool:
2001+
return0;
2002+
casejbvString:
2003+
returnjbv->val.string.len;
2004+
casejbvNumeric:
2005+
returnVARSIZE_ANY(jbv->val.numeric);
2006+
casejbvArray:
2007+
size= offsetof(JsonbContainerHeader,children[jbv->val.array.nElems]);
2008+
for (inti=0;i<jbv->val.array.nElems;i++)
2009+
size+=estimateJsonbValueSize(&jbv->val.array.elems[i]);
2010+
returnsize;
2011+
casejbvObject:
2012+
size= offsetof(JsonbContainerHeader,children[jbv->val.object.nPairs*2]);
2013+
for (inti=0;i<jbv->val.object.nPairs;i++)
2014+
{
2015+
size+=estimateJsonbValueSize(&jbv->val.object.pairs[i].key);
2016+
size+=estimateJsonbValueSize(&jbv->val.object.pairs[i].value);
2017+
}
2018+
returnsize;
2019+
default:
2020+
elog(ERROR,"invalid jsonb value type: %d",jbv->type);
2021+
return0;
2022+
}
2023+
}
2024+
19542025
staticvoid
19552026
convertJsonbObject(StringInfobuffer,JEntry*pheader,constJsonbValue*val,intlevel)
19562027
{
@@ -1960,9 +2031,39 @@ convertJsonbObject(StringInfo buffer, JEntry *pheader, const JsonbValue *val, in
19602031
inttotallen;
19612032
uint32header;
19622033
intnPairs=val->val.object.nPairs;
2034+
intreserved_size;
2035+
boolsorted_values=JSONB_SORTED_VALUES&&nPairs>1;
2036+
struct
2037+
{
2038+
intsize;
2039+
int32index;
2040+
}*values=sorted_values ?palloc(sizeof(*values)*nPairs) :NULL;
19632041

19642042
Assert(nPairs >=0);
19652043

2044+
if (sorted_values)
2045+
{
2046+
for (i=0;i<nPairs;i++)
2047+
{
2048+
values[i].index=i;
2049+
values[i].size=estimateJsonbValueSize(&val->val.object.pairs[i].value);
2050+
}
2051+
2052+
qsort(values,nPairs,sizeof(*values),int_cmp);
2053+
2054+
/* check if keys were really moved */
2055+
sorted_values= false;
2056+
2057+
for (i=0;i<nPairs;i++)
2058+
{
2059+
if (values[i].index!=i)
2060+
{
2061+
sorted_values= true;
2062+
break;
2063+
}
2064+
}
2065+
}
2066+
19662067
/* Remember where in the buffer this object starts. */
19672068
base_offset=buffer->len;
19682069

@@ -1973,17 +2074,30 @@ convertJsonbObject(StringInfo buffer, JEntry *pheader, const JsonbValue *val, in
19732074
* Construct the header Jentry and store it in the beginning of the
19742075
* variable-length payload.
19752076
*/
1976-
header=nPairs |JBC_FOBJECT;
2077+
header=nPairs |(sorted_values ?JBC_TOBJECT_SORTED :JBC_TOBJECT);
19772078
appendToBuffer(buffer, (char*)&header,sizeof(uint32));
19782079

19792080
/* Reserve space for the JEntries of the keys and values. */
1980-
jentry_offset=reserveFromBuffer(buffer,sizeof(JEntry)*nPairs*2);
2081+
reserved_size=sizeof(JEntry)*nPairs*2;
2082+
if (sorted_values)
2083+
reserved_size+=sizeof(int32)*nPairs;
2084+
2085+
jentry_offset=reserveFromBuffer(buffer,reserved_size);
2086+
2087+
/* Write key-value map */
2088+
if (sorted_values)
2089+
{
2090+
for (i=0;i<nPairs;i++)
2091+
copyToBuffer(buffer,jentry_offset+sizeof(JEntry)*nPairs*2+values[i].index*sizeof(int32),
2092+
(void*)&i,sizeof(int32));
2093+
}
19812094

19822095
/*
19832096
* Iterate over the keys, then over the values, since that is the ordering
19842097
* we want in the on-disk representation.
19852098
*/
19862099
totallen=0;
2100+
19872101
for (i=0;i<nPairs;i++)
19882102
{
19892103
JsonbPair*pair=&val->val.object.pairs[i];
@@ -2019,9 +2133,11 @@ convertJsonbObject(StringInfo buffer, JEntry *pheader, const JsonbValue *val, in
20192133
copyToBuffer(buffer,jentry_offset, (char*)&meta,sizeof(JEntry));
20202134
jentry_offset+=sizeof(JEntry);
20212135
}
2136+
20222137
for (i=0;i<nPairs;i++)
20232138
{
2024-
JsonbPair*pair=&val->val.object.pairs[i];
2139+
intval_index=sorted_values ?values[i].index :i;
2140+
JsonbPair*pair=&val->val.object.pairs[val_index];
20252141
intlen;
20262142
JEntrymeta;
20272143

@@ -2055,6 +2171,9 @@ convertJsonbObject(StringInfo buffer, JEntry *pheader, const JsonbValue *val, in
20552171
jentry_offset+=sizeof(JEntry);
20562172
}
20572173

2174+
if (values)
2175+
pfree(values);
2176+
20582177
/* Total data size is everything we've appended to buffer */
20592178
totallen=buffer->len-base_offset;
20602179

@@ -2280,17 +2399,36 @@ uniqueifyJsonbObject(JsonbValue *object, bool unique_keys, bool skip_nulls)
22802399
}
22812400
}
22822401

2402+
staticvoid
2403+
jsonbInitContainerFromHeader(JsonContainerData*jc,JsonbContainerHeader*jbc)
2404+
{
2405+
jc->size=jbc->header&JBC_CMASK;
2406+
switch (jbc->header&JBC_TMASK)
2407+
{
2408+
caseJBC_TOBJECT:
2409+
caseJBC_TOBJECT_SORTED:
2410+
jc->type=jbvObject;
2411+
break;
2412+
caseJBC_TARRAY:
2413+
jc->type=jbvArray;
2414+
break;
2415+
caseJBC_TSCALAR:
2416+
jc->type=jbvArray |jbvScalar;
2417+
break;
2418+
default:
2419+
elog(ERROR,"invalid jsonb container type: %d",
2420+
jbc->header&JBC_TMASK);
2421+
}
2422+
}
2423+
22832424
staticvoid
22842425
jsonbInitContainer(JsonContainerData*jc,JsonbContainerHeader*jbc,intlen)
22852426
{
22862427
jc->ops=&jsonbContainerOps;
22872428
JsonContainerDataPtr(jc)=jbc;
22882429
jc->len=len;
22892430
jc->toasterid=InvalidOid;
2290-
jc->size=jbc->header&JBC_CMASK;
2291-
jc->type=jbc->header&JBC_FOBJECT ?jbvObject :
2292-
jbc->header&JBC_FSCALAR ?jbvArray |jbvScalar :
2293-
jbvArray;
2431+
jsonbInitContainerFromHeader(jc,jbc);
22942432
}
22952433

22962434
staticvoid
@@ -2406,10 +2544,7 @@ jsonbzInitContainer(JsonContainerData *jc, CompressedJsonb *cjb, int len)
24062544

24072545
jc->ops=&jsonbzContainerOps;
24082546
jc->len=len;
2409-
jc->size=jbc->header&JBC_CMASK;
2410-
jc->type=jbc->header&JBC_FOBJECT ?jbvObject :
2411-
jbc->header&JBC_FSCALAR ?jbvArray |jbvScalar :
2412-
jbvArray;
2547+
jsonbInitContainerFromHeader(jc,jbc);
24132548
}
24142549

24152550
staticJsonbContainer*
@@ -2479,12 +2614,15 @@ findValueInCompressedJsonbObject(CompressedJsonb *cjb, const char *keystr, int k
24792614
JEntry*children=container->children;
24802615
intcount=container->header&JBC_CMASK;
24812616
/* Since this is an object, account for *Pairs* of Jentrys */
2482-
char*base_addr= (char*) (children+count*2);
2617+
boolsorted_values= (container->header&JBC_TMASK)==JBC_TOBJECT_SORTED;
2618+
char*base_addr= (char*) (children+count*2)+ (sorted_values ?sizeof(uint32)*count :0);
2619+
uint32*kvmap=sorted_values ?&container->children[count*2] :NULL;
24832620
Sizebase_offset=base_addr- (char*)jb;
24842621
uint32stopLow=0,
24852622
stopHigh=count;
24862623

2487-
Assert(jb->root.header&JB_FOBJECT);
2624+
Assert((jb->root.header&JBC_TMASK)==JBC_TOBJECT||
2625+
(jb->root.header&JBC_TMASK)==JBC_TOBJECT_SORTED);
24882626

24892627
/* Quick out if object/array is empty */
24902628
if (count <=0)
@@ -2521,7 +2659,7 @@ findValueInCompressedJsonbObject(CompressedJsonb *cjb, const char *keystr, int k
25212659
if (difference==0)
25222660
{
25232661
/* Found our key, return corresponding value */
2524-
intindex=stopMiddle+count;
2662+
intindex=(sorted_values ?kvmap[stopMiddle] :stopMiddle)+count;
25252663

25262664
if (!res)
25272665
res=palloc(sizeof(*res));

‎src/include/utils/jsonb_internals.h

Lines changed: 9 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -144,9 +144,15 @@ typedef struct JsonbContainerHeader
144144

145145
/* flags for the header-field in JsonbContainer */
146146
#defineJBC_CMASK0x0FFFFFFF/* mask for count field */
147-
#defineJBC_FSCALAR0x10000000/* flag bits */
148-
#defineJBC_FOBJECT0x20000000
149-
#defineJBC_FARRAY0x40000000
147+
#defineJBC_TMASK0x70000000/* mask for container type */
148+
/* container types */
149+
#defineJBC_TOBJECT0x20000000/* object with key-value pairs
150+
* sorted by key length-alpha */
151+
#defineJBC_TOBJECT_SORTED0x30000000/* object with keys sorted by
152+
* length-alpha; values sorted by
153+
* length */
154+
#defineJBC_TARRAY0x40000000/* array */
155+
#defineJBC_TSCALAR0x50000000/* scalar pseudo-array */
150156

151157
/* The top-level on-disk format for a jsonb datum. */
152158
typedefstruct

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp