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

Commit4ea51cd

Browse files
committed
Use abbreviated keys for faster sorting of text datums.
This commit extends the SortSupport infrastructure to allow operatorclasses the option to provide abbreviated representations of Datums;in the case of text, we abbreviate by taking the first few charactersof the strxfrm() blob. If the abbreviated comparison is insufficentto resolve the comparison, we fall back on the normal comparator.This can be much faster than the old way of doing sorting if thefirst few bytes of the string are usually sufficient to resolve thecomparison.There is the potential for a performance regression if all of thestrings to be sorted are identical for the first 8+ characters anddiffer only in later positions; therefore, the SortSupport machinerynow provides an infrastructure to abort the use of abbreviation ifit appears that abbreviation is producing comparatively few distinctkeys. HyperLogLog, a streaming cardinality estimator, is included inthis commit and used to make that determination for text.Peter Geoghegan, reviewed by me.
1 parent1605291 commit4ea51cd

File tree

13 files changed

+1149
-76
lines changed

13 files changed

+1149
-76
lines changed

‎src/backend/access/nbtree/nbtsort.c

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -717,6 +717,8 @@ _bt_load(BTWriteState *wstate, BTSpool *btspool, BTSpool *btspool2)
717717
sortKey->ssup_nulls_first=
718718
(scanKey->sk_flags&SK_BT_NULLS_FIRST)!=0;
719719
sortKey->ssup_attno=scanKey->sk_attno;
720+
/* Abbreviation is not supported here */
721+
sortKey->abbreviate= false;
720722

721723
AssertState(sortKey->ssup_attno!=0);
722724

‎src/backend/commands/analyze.c

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2301,6 +2301,12 @@ compute_scalar_stats(VacAttrStatsP stats,
23012301
/* We always use the default collation for statistics */
23022302
ssup.ssup_collation=DEFAULT_COLLATION_OID;
23032303
ssup.ssup_nulls_first= false;
2304+
/*
2305+
* For now, don't perform abbreviated key conversion, because full values
2306+
* are required for MCV slot generation. Supporting that optimization
2307+
* would necessitate teaching compare_scalars() to call a tie-breaker.
2308+
*/
2309+
ssup.abbreviate= false;
23042310

23052311
PrepareSortSupportFromOrderingOp(mystats->ltopr,&ssup);
23062312

‎src/backend/executor/nodeAgg.c

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -363,6 +363,10 @@ initialize_aggregates(AggState *aggstate,
363363
* We use a plain Datum sorter when there's a single input column;
364364
* otherwise sort the full tuple. (See comments for
365365
* process_ordered_aggregate_single.)
366+
*
367+
* In the future, we should consider forcing the
368+
* tuplesort_begin_heap() case when the abbreviated key
369+
* optimization can thereby be used, even when numInputs is 1.
366370
*/
367371
peraggstate->sortstate=
368372
(peraggstate->numInputs==1) ?

‎src/backend/executor/nodeMergeAppend.c

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -137,6 +137,15 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
137137
sortKey->ssup_nulls_first=node->nullsFirst[i];
138138
sortKey->ssup_attno=node->sortColIdx[i];
139139

140+
/*
141+
* It isn't feasible to perform abbreviated key conversion, since
142+
* tuples are pulled into mergestate's binary heap as needed. It would
143+
* likely be counter-productive to convert tuples into an abbreviated
144+
* representation as they're pulled up, so opt out of that additional
145+
* optimization entirely.
146+
*/
147+
sortKey->abbreviate= false;
148+
140149
PrepareSortSupportFromOrderingOp(node->sortOperators[i],sortKey);
141150
}
142151

‎src/backend/executor/nodeMergejoin.c

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -229,6 +229,14 @@ MJExamineQuals(List *mergeclauses,
229229
elog(ERROR,"cannot merge using non-equality operator %u",
230230
qual->opno);
231231

232+
/*
233+
* sortsupport routine must know if abbreviation optimization is
234+
* applicable in principle. It is never applicable for merge joins
235+
* because there is no convenient opportunity to convert to alternative
236+
* representation.
237+
*/
238+
clause->ssup.abbreviate= false;
239+
232240
/* And get the matching support or comparison function */
233241
Assert(clause->ssup.comparator==NULL);
234242
sortfunc=get_opfamily_proc(opfamily,

‎src/backend/lib/Makefile

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,6 @@ subdir = src/backend/lib
1212
top_builddir = ../../..
1313
include$(top_builddir)/src/Makefile.global
1414

15-
OBJS = ilist.o binaryheap.o pairingheap.o rbtree.o stringinfo.o
15+
OBJS = ilist.o binaryheap.ohyperloglog.opairingheap.o rbtree.o stringinfo.o
1616

1717
include$(top_srcdir)/src/backend/common.mk

‎src/backend/lib/hyperloglog.c

Lines changed: 228 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,228 @@
1+
/*-------------------------------------------------------------------------
2+
*
3+
* hyperloglog.c
4+
* HyperLogLog cardinality estimator
5+
*
6+
* Portions Copyright (c) 2014, PostgreSQL Global Development Group
7+
*
8+
* Based on Hideaki Ohno's C++ implementation. This is probably not ideally
9+
* suited to estimating the cardinality of very large sets; in particular, we
10+
* have not attempted to further optimize the implementation as described in
11+
* the Heule, Nunkesser and Hall paper "HyperLogLog in Practice: Algorithmic
12+
* Engineering of a State of The Art Cardinality Estimation Algorithm".
13+
*
14+
* A sparse representation of HyperLogLog state is used, with fixed space
15+
* overhead.
16+
*
17+
* The copyright terms of Ohno's original version (the MIT license) follow.
18+
*
19+
* IDENTIFICATION
20+
* src/backend/lib/hyperloglog.c
21+
*
22+
*-------------------------------------------------------------------------
23+
*/
24+
25+
/*
26+
* Copyright (c) 2013 Hideaki Ohno <hide.o.j55{at}gmail.com>
27+
*
28+
* Permission is hereby granted, free of charge, to any person obtaining a copy
29+
* of this software and associated documentation files (the 'Software'), to
30+
* deal in the Software without restriction, including without limitation the
31+
* rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
32+
* sell copies of the Software, and to permit persons to whom the Software is
33+
* furnished to do so, subject to the following conditions:
34+
*
35+
* The above copyright notice and this permission notice shall be included in
36+
* all copies or substantial portions of the Software.
37+
*
38+
* THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
39+
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
40+
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
41+
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
42+
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
43+
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
44+
* IN THE SOFTWARE.
45+
*/
46+
47+
#include"postgres.h"
48+
49+
#include<math.h>
50+
51+
#include"lib/hyperloglog.h"
52+
53+
#definePOW_2_32(4294967296.0)
54+
#defineNEG_POW_2_32(-4294967296.0)
55+
56+
staticinlineuint8rho(uint32x,uint8b);
57+
58+
/*
59+
* Initialize HyperLogLog track state
60+
*
61+
* bwidth is bit width (so register size will be 2 to the power of bwidth).
62+
* Must be between 4 and 16 inclusive.
63+
*/
64+
void
65+
initHyperLogLog(hyperLogLogState*cState,uint8bwidth)
66+
{
67+
doublealpha;
68+
69+
if (bwidth<4||bwidth>16)
70+
elog(ERROR,"bit width must be between 4 and 16 inclusive");
71+
72+
cState->registerWidth=bwidth;
73+
cState->nRegisters=1 <<bwidth;
74+
cState->arrSize=sizeof(uint8)*cState->nRegisters+1;
75+
76+
/*
77+
* Initialize hashes array to zero, not negative infinity, per discussion
78+
* of the coupon collector problem in the HyperLogLog paper
79+
*/
80+
cState->hashesArr=palloc0(cState->arrSize);
81+
82+
/*
83+
* "alpha" is a value that for each possible number of registers (m) is
84+
* used to correct a systematic multiplicative bias present in m ^ 2 Z (Z
85+
* is "the indicator function" through which we finally compute E,
86+
* estimated cardinality).
87+
*/
88+
switch (cState->nRegisters)
89+
{
90+
case16:
91+
alpha=0.673;
92+
break;
93+
case32:
94+
alpha=0.697;
95+
break;
96+
case64:
97+
alpha=0.709;
98+
break;
99+
default:
100+
alpha=0.7213 / (1.0+1.079 /cState->nRegisters);
101+
}
102+
103+
/*
104+
* Precalculate alpha m ^ 2, later used to generate "raw" HyperLogLog
105+
* estimate E
106+
*/
107+
cState->alphaMM=alpha*cState->nRegisters*cState->nRegisters;
108+
}
109+
110+
/*
111+
* Adds element to the estimator, from caller-supplied hash.
112+
*
113+
* It is critical that the hash value passed be an actual hash value, typically
114+
* generated using hash_any(). The algorithm relies on a specific bit-pattern
115+
* observable in conjunction with stochastic averaging. There must be a
116+
* uniform distribution of bits in hash values for each distinct original value
117+
* observed.
118+
*/
119+
void
120+
addHyperLogLog(hyperLogLogState*cState,uint32hash)
121+
{
122+
uint8count;
123+
uint32index;
124+
125+
/* Use the first "k" (registerWidth) bits as a zero based index */
126+
index=hash >> (BITS_PER_BYTE*sizeof(uint32)-cState->registerWidth);
127+
128+
/* Compute the rank of the remaining 32 - "k" (registerWidth) bits */
129+
count=rho(hash <<cState->registerWidth,
130+
BITS_PER_BYTE*sizeof(uint32)-cState->registerWidth);
131+
132+
cState->hashesArr[index]=Max(count,cState->hashesArr[index]);
133+
}
134+
135+
/*
136+
* Estimates cardinality, based on elements added so far
137+
*/
138+
double
139+
estimateHyperLogLog(hyperLogLogState*cState)
140+
{
141+
doubleresult;
142+
doublesum=0.0;
143+
inti;
144+
145+
for (i=0;i<cState->nRegisters;i++)
146+
{
147+
sum+=1.0 /pow(2.0,cState->hashesArr[i]);
148+
}
149+
150+
/* result set to "raw" HyperLogLog estimate (E in the HyperLogLog paper) */
151+
result=cState->alphaMM /sum;
152+
153+
if (result <= (5.0 /2.0)*cState->nRegisters)
154+
{
155+
/* Small range correction */
156+
intzero_count=0;
157+
158+
for (i=0;i<cState->nRegisters;i++)
159+
{
160+
if (cState->hashesArr[i]==0)
161+
zero_count++;
162+
}
163+
164+
if (zero_count!=0)
165+
result=cState->nRegisters*log((double)cState->nRegisters /
166+
zero_count);
167+
}
168+
elseif (result> (1.0 /30.0)*POW_2_32)
169+
{
170+
/* Large range correction */
171+
result=NEG_POW_2_32*log(1.0- (result /POW_2_32));
172+
}
173+
174+
returnresult;
175+
}
176+
177+
/*
178+
* Merges the estimate from one HyperLogLog state to another, returning the
179+
* estimate of their union.
180+
*
181+
* The number of registers in each must match.
182+
*/
183+
void
184+
mergeHyperLogLog(hyperLogLogState*cState,consthyperLogLogState*oState)
185+
{
186+
intr;
187+
188+
if (cState->nRegisters!=oState->nRegisters)
189+
elog(ERROR,"number of registers mismatch: %zu != %zu",
190+
cState->nRegisters,oState->nRegisters);
191+
192+
for (r=0;r<cState->nRegisters;++r)
193+
{
194+
cState->hashesArr[r]=Max(cState->hashesArr[r],oState->hashesArr[r]);
195+
}
196+
}
197+
198+
199+
/*
200+
* Worker for addHyperLogLog().
201+
*
202+
* Calculates the position of the first set bit in first b bits of x argument
203+
* starting from the first, reading from most significant to least significant
204+
* bits.
205+
*
206+
* Example (when considering fist 10 bits of x):
207+
*
208+
* rho(x = 0b1000000000) returns 1
209+
* rho(x = 0b0010000000) returns 3
210+
* rho(x = 0b0000000000) returns b + 1
211+
*
212+
* "The binary address determined by the first b bits of x"
213+
*
214+
* Return value "j" used to index bit pattern to watch.
215+
*/
216+
staticinlineuint8
217+
rho(uint32x,uint8b)
218+
{
219+
uint8j=1;
220+
221+
while (j <=b&& !(x&0x80000000))
222+
{
223+
j++;
224+
x <<=1;
225+
}
226+
227+
returnj;
228+
}

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

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -266,7 +266,13 @@ ordered_set_startup(FunctionCallInfo fcinfo, bool use_tuples)
266266
osastate->qstate=qstate;
267267
osastate->gcontext=gcontext;
268268

269-
/* Initialize tuplesort object */
269+
/*
270+
* Initialize tuplesort object.
271+
*
272+
* In the future, we should consider forcing the tuplesort_begin_heap()
273+
* case when the abbreviated key optimization can thereby be used, even
274+
* when !use_tuples.
275+
*/
270276
if (use_tuples)
271277
osastate->sortstate=tuplesort_begin_heap(qstate->tupdesc,
272278
qstate->numSortCols,

0 commit comments

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