Debian Codegraph @

ext/misc/percentile.c

raw
1 /*
2 ** 2013-05-28
3 **
4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
6 **
7 ** May you do good and not evil.
8 ** May you find forgiveness for yourself and forgive others.
9 ** May you share freely, never taking more than you give.
10 **
11 ******************************************************************************
12 **
13 ** This file contains code to implement the percentile(Y,P) SQL function
14 ** and similar as described below:
15 **
16 ** (1) The percentile(Y,P) function is an aggregate function taking
17 ** exactly two arguments.
18 **
19 ** (2) If the P argument to percentile(Y,P) is not the same for every
20 ** row in the aggregate then an error is thrown. The word "same"
21 ** in the previous sentence means that the value differ by less
22 ** than 0.001.
23 **
24 ** (3) If the P argument to percentile(Y,P) evaluates to anything other
25 ** than a number in the range of 0.0 to 100.0 inclusive then an
26 ** error is thrown.
27 **
28 ** (4) If any Y argument to percentile(Y,P) evaluates to a value that
29 ** is not NULL and is not numeric then an error is thrown.
30 **
31 ** (5) If any Y argument to percentile(Y,P) evaluates to plus or minus
32 ** infinity then an error is thrown. (SQLite always interprets NaN
33 ** values as NULL.)
34 **
35 ** (6) Both Y and P in percentile(Y,P) can be arbitrary expressions,
36 ** including CASE WHEN expressions.
37 **
38 ** (7) The percentile(Y,P) aggregate is able to handle inputs of at least
39 ** one million (1,000,000) rows.
40 **
41 ** (8) If there are no non-NULL values for Y, then percentile(Y,P)
42 ** returns NULL.
43 **
44 ** (9) If there is exactly one non-NULL value for Y, the percentile(Y,P)
45 ** returns the one Y value.
46 **
47 ** (10) If there N non-NULL values of Y where N is two or more and
48 ** the Y values are ordered from least to greatest and a graph is
49 ** drawn from 0 to N-1 such that the height of the graph at J is
50 ** the J-th Y value and such that straight lines are drawn between
51 ** adjacent Y values, then the percentile(Y,P) function returns
52 ** the height of the graph at P*(N-1)/100.
53 **
54 ** (11) The percentile(Y,P) function always returns either a floating
55 ** point number or NULL.
56 **
57 ** (12) The percentile(Y,P) is implemented as a single C99 source-code
58 ** file that compiles into a shared-library or DLL that can be loaded
59 ** into SQLite using the sqlite3_load_extension() interface.
60 **
61 ** (13) A separate median(Y) function is the equivalent percentile(Y,50).
62 **
63 ** (14) A separate percentile_cont(Y,P) function is equivalent to
64 ** percentile(Y,P/100.0). In other words, the fraction value in
65 ** the second argument is in the range of 0 to 1 instead of 0 to 100.
66 **
67 ** (15) A separate percentile_disc(Y,P) function is like
68 ** percentile_cont(Y,P) except that instead of returning the weighted
69 ** average of the nearest two input values, it returns the next lower
70 ** value. So the percentile_disc(Y,P) will always return a value
71 ** that was one of the inputs.
72 **
73 ** (16) All of median(), percentile(Y,P), percentile_cont(Y,P) and
74 ** percentile_disc(Y,P) can be used as window functions.
75 **
76 ** Differences from standard SQL:
77 **
78 ** * The percentile_cont(X,P) function is equivalent to the following in
79 ** standard SQL:
80 **
81 ** (percentile_cont(P) WITHIN GROUP (ORDER BY X))
82 **
83 ** The SQLite syntax is much more compact. The standard SQL syntax
84 ** is also supported if SQLite is compiled with the
85 ** -DSQLITE_ENABLE_ORDERED_SET_AGGREGATES option.
86 **
87 ** * No median(X) function exists in the SQL standard. App developers
88 ** are expected to write "percentile_cont(0.5)WITHIN GROUP(ORDER BY X)".
89 **
90 ** * No percentile(Y,P) function exists in the SQL standard. Instead of
91 ** percential(Y,P), developers must write this:
92 ** "percentile_cont(P/100.0) WITHIN GROUP (ORDER BY Y)". Note that
93 ** the fraction parameter to percentile() goes from 0 to 100 whereas
94 ** the fraction parameter in SQL standard percentile_cont() goes from
95 ** 0 to 1.
96 **
97 ** Implementation notes as of 2024-08-31:
98 **
99 ** * The regular aggregate-function versions of these routines work
100 ** by accumulating all values in an array of doubles, then sorting
101 ** that array using quicksort before computing the answer. Thus
102 ** the runtime is O(NlogN) where N is the number of rows of input.
103 **
104 ** * For the window-function versions of these routines, the array of
105 ** inputs is sorted as soon as the first value is computed. Thereafter,
106 ** the array is kept in sorted order using an insert-sort. This
107 ** results in O(N*K) performance where K is the size of the window.
108 ** One can imagine alternative implementations that give O(N*logN*logK)
109 ** performance, but they require more complex logic and data structures.
110 ** The developers have elected to keep the asymptotically slower
111 ** algorithm for now, for simplicity, under the theory that window
112 ** functions are seldom used and when they are, the window size K is
113 ** often small. The developers might revisit that decision later,
114 ** should the need arise.
115 */
116 #if defined(SQLITE3_H)
117 /* no-op */
118 #elif defined(SQLITE_STATIC_PERCENTILE)
119 # include "sqlite3.h"
120 #else
121 # include "sqlite3ext.h"
122 SQLITE_EXTENSION_INIT1
123 #endif
124 #include <assert.h>
125 #include <string.h>
126 #include <stdlib.h>
127
128 /* The following object is the group context for a single percentile()
129 ** aggregate. Remember all input Y values until the very end.
130 ** Those values are accumulated in the Percentile.a[] array.
131 */
132 typedef struct Percentile Percentile;
133 struct Percentile {
134 unsigned nAlloc; /* Number of slots allocated for a[] */
135 unsigned nUsed; /* Number of slots actually used in a[] */
136 char bSorted; /* True if a[] is already in sorted order */
137 char bKeepSorted; /* True if advantageous to keep a[] sorted */
138 char bPctValid; /* True if rPct is valid */
139 double rPct; /* Fraction. 0.0 to 1.0 */
140 double *a; /* Array of Y values */
141 };
142
143 /* Details of each function in the percentile family */
144 typedef struct PercentileFunc PercentileFunc;
145 struct PercentileFunc {
146 const char *zName; /* Function name */
147 char nArg; /* Number of arguments */
148 char mxFrac; /* Maximum value of the "fraction" input */
149 char bDiscrete; /* True for percentile_disc() */
150 };
151 static const PercentileFunc aPercentFunc[] = {
152 { "median", 1, 1, 0 },
153 { "percentile", 2, 100, 0 },
154 { "percentile_cont", 2, 1, 0 },
155 { "percentile_disc", 2, 1, 1 },
156 };
157
158 /*
159 ** Return TRUE if the input floating-point number is an infinity.
160 */
161 static int percentIsInfinity(double r){
162 sqlite3_uint64 u;
163 assert( sizeof(u)==sizeof(r) );
164 memcpy(&u, &r, sizeof(u));
165 return ((u>>52)&0x7ff)==0x7ff;
166 }
167
168 /*
169 ** Return TRUE if two doubles differ by 0.001 or less.
170 */
171 static int percentSameValue(double a, double b){
172 a -= b;
173 return a>=-0.001 && a<=0.001;
174 }
175
176 /*
177 ** Search p (which must have p->bSorted) looking for an entry with
178 ** value y. Return the index of that entry.
179 **
180 ** If bExact is true, return -1 if the entry is not found.
181 **
182 ** If bExact is false, return the index at which a new entry with
183 ** value y should be insert in order to keep the values in sorted
184 ** order. The smallest return value in this case will be 0, and
185 ** the largest return value will be p->nUsed.
186 */
187 static int percentBinarySearch(Percentile *p, double y, int bExact){
188 int iFirst = 0; /* First element of search range */
189 int iLast = p->nUsed - 1; /* Last element of search range */
190 while( iLast>=iFirst ){
191 int iMid = (iFirst+iLast)/2;
192 double x = p->a[iMid];
193 if( x<y ){
194 iFirst = iMid + 1;
195 }else if( x>y ){
196 iLast = iMid - 1;
197 }else{
198 return iMid;
199 }
200 }
201 if( bExact ) return -1;
202 return iFirst;
203 }
204
205 /*
206 ** Generate an error for a percentile function.
207 **
208 ** The error format string must have exactly one occurrence of "%%s()"
209 ** (with two '%' characters). That substring will be replaced by the name
210 ** of the function.
211 */
212 static void percentError(sqlite3_context *pCtx, const char *zFormat, ...){
213 PercentileFunc *pFunc = (PercentileFunc*)sqlite3_user_data(pCtx);
214 char *zMsg1;
215 char *zMsg2;
216 va_list ap;
217
218 va_start(ap, zFormat);
219 zMsg1 = sqlite3_vmprintf(zFormat, ap);
220 va_end(ap);
221 zMsg2 = zMsg1 ? sqlite3_mprintf(zMsg1, pFunc->zName) : 0;
222 sqlite3_result_error(pCtx, zMsg2, -1);
223 sqlite3_free(zMsg1);
224 sqlite3_free(zMsg2);
225 }
226
227 /*
228 ** The "step" function for percentile(Y,P) is called once for each
229 ** input row.
230 */
231 static void percentStep(sqlite3_context *pCtx, int argc, sqlite3_value **argv){
232 Percentile *p;
233 double rPct;
234 int eType;
235 double y;
236 assert( argc==2 || argc==1 );
237
238 if( argc==1 ){
239 /* Requirement 13: median(Y) is the same as percentile(Y,50). */
240 rPct = 0.5;
241 }else{
242 /* Requirement 3: P must be a number between 0 and 100 */
243 PercentileFunc *pFunc = (PercentileFunc*)sqlite3_user_data(pCtx);
244 eType = sqlite3_value_numeric_type(argv[1]);
245 rPct = sqlite3_value_double(argv[1])/(double)pFunc->mxFrac;
246 if( (eType!=SQLITE_INTEGER && eType!=SQLITE_FLOAT)
247 || rPct<0.0 || rPct>1.0
248 ){
249 percentError(pCtx, "the fraction argument to %%s()"
250 " is not between 0.0 and %.1f",
251 (double)pFunc->mxFrac);
252 return;
253 }
254 }
255
256 /* Allocate the session context. */
257 p = (Percentile*)sqlite3_aggregate_context(pCtx, sizeof(*p));
258 if( p==0 ) return;
259
260 /* Remember the P value. Throw an error if the P value is different
261 ** from any prior row, per Requirement (2). */
262 if( !p->bPctValid ){
263 p->rPct = rPct;
264 p->bPctValid = 1;
265 }else if( !percentSameValue(p->rPct,rPct) ){
266 percentError(pCtx, "the fraction argument to %%s()"
267 " is not the same for all input rows");
268 return;
269 }
270
271 /* Ignore rows for which Y is NULL */
272 eType = sqlite3_value_type(argv[0]);
273 if( eType==SQLITE_NULL ) return;
274
275 /* If not NULL, then Y must be numeric. Otherwise throw an error.
276 ** Requirement 4 */
277 if( eType!=SQLITE_INTEGER && eType!=SQLITE_FLOAT ){
278 percentError(pCtx, "input to %%s() is not numeric");
279 return;
280 }
281
282 /* Throw an error if the Y value is infinity or NaN */
283 y = sqlite3_value_double(argv[0]);
284 if( percentIsInfinity(y) ){
285 percentError(pCtx, "Inf input to %%s()");
286 return;
287 }
288
289 /* Allocate and store the Y */
290 if( p->nUsed>=p->nAlloc ){
291 unsigned n = p->nAlloc*2 + 250;
292 double *a = sqlite3_realloc64(p->a, sizeof(double)*n);
293 if( a==0 ){
294 sqlite3_free(p->a);
295 memset(p, 0, sizeof(*p));
296 sqlite3_result_error_nomem(pCtx);
297 return;
298 }
299 p->nAlloc = n;
300 p->a = a;
301 }
302 if( p->nUsed==0 ){
303 p->a[p->nUsed++] = y;
304 p->bSorted = 1;
305 }else if( !p->bSorted || y>=p->a[p->nUsed-1] ){
306 p->a[p->nUsed++] = y;
307 }else if( p->bKeepSorted ){
308 int i;
309 i = percentBinarySearch(p, y, 0);
310 if( i<(int)p->nUsed ){
311 memmove(&p->a[i+1], &p->a[i], (p->nUsed-i)*sizeof(p->a[0]));
312 }
313 p->a[i] = y;
314 p->nUsed++;
315 }else{
316 p->a[p->nUsed++] = y;
317 p->bSorted = 0;
318 }
319 }
320
321 /*
322 ** Interchange two doubles.
323 */
324 #define SWAP_DOUBLE(X,Y) {double ttt=(X);(X)=(Y);(Y)=ttt;}
325
326 /*
327 ** Sort an array of doubles.
328 **
329 ** Algorithm: quicksort
330 **
331 ** This is implemented separately rather than using the qsort() routine
332 ** from the standard library because:
333 **
334 ** (1) To avoid a dependency on qsort()
335 ** (2) To avoid the function call to the comparison routine for each
336 ** comparison.
337 */
338 static void percentSort(double *a, unsigned int n){
339 int iLt; /* Entries before a[iLt] are less than rPivot */
340 int iGt; /* Entries at or after a[iGt] are greater than rPivot */
341 int i; /* Loop counter */
342 double rPivot; /* The pivot value */
343
344 while( n>=2 ){
345 if( a[0]>a[n-1] ){
346 SWAP_DOUBLE(a[0],a[n-1])
347 }
348 if( n==2 ) return;
349 iGt = n-1;
350 i = n/2;
351 if( a[0]>a[i] ){
352 SWAP_DOUBLE(a[0],a[i])
353 }else if( a[i]>a[iGt] ){
354 SWAP_DOUBLE(a[i],a[iGt])
355 }
356 if( n==3 ) return;
357 rPivot = a[i];
358 iLt = i = 1;
359 do{
360 if( a[i]<rPivot ){
361 if( i>iLt ) SWAP_DOUBLE(a[i],a[iLt])
362 iLt++;
363 i++;
364 }else if( a[i]>rPivot ){
365 do{
366 iGt--;
367 }while( iGt>i && a[iGt]>rPivot );
368 SWAP_DOUBLE(a[i],a[iGt])
369 }else{
370 i++;
371 }
372 }while( i<iGt );
373 if( iLt>n/2 ){
374 if( n-iGt>=2 ) percentSort(a+iGt, n-iGt);
375 n = iLt;
376 }else{
377 if( iLt>=2 ) percentSort(a, iLt);
378 a += iGt;
379 n -= iGt;
380 }
381 }
382 }
383
384
385 /*
386 ** The "inverse" function for percentile(Y,P) is called to remove a
387 ** row that was previously inserted by "step".
388 */
389 static void percentInverse(sqlite3_context *pCtx,int argc,sqlite3_value **argv){
390 Percentile *p;
391 int eType;
392 double y;
393 int i;
394 assert( argc==2 || argc==1 );
395
396 /* Allocate the session context. */
397 p = (Percentile*)sqlite3_aggregate_context(pCtx, sizeof(*p));
398 assert( p!=0 );
399
400 /* Ignore rows for which Y is NULL */
401 eType = sqlite3_value_type(argv[0]);
402 if( eType==SQLITE_NULL ) return;
403
404 /* If not NULL, then Y must be numeric. Otherwise throw an error.
405 ** Requirement 4 */
406 if( eType!=SQLITE_INTEGER && eType!=SQLITE_FLOAT ){
407 return;
408 }
409
410 /* Ignore the Y value if it is infinity or NaN */
411 y = sqlite3_value_double(argv[0]);
412 if( percentIsInfinity(y) ){
413 return;
414 }
415 if( p->bSorted==0 ){
416 assert( p->nUsed>1 );
417 percentSort(p->a, p->nUsed);
418 p->bSorted = 1;
419 }
420 p->bKeepSorted = 1;
421
422 /* Find and remove the row */
423 i = percentBinarySearch(p, y, 1);
424 if( i>=0 ){
425 p->nUsed--;
426 if( i<(int)p->nUsed ){
427 memmove(&p->a[i], &p->a[i+1], (p->nUsed - i)*sizeof(p->a[0]));
428 }
429 }
430 }
431
432 /*
433 ** Compute the final output of percentile(). Clean up all allocated
434 ** memory if and only if bIsFinal is true.
435 */
436 static void percentCompute(sqlite3_context *pCtx, int bIsFinal){
437 Percentile *p;
438 PercentileFunc *pFunc = (PercentileFunc*)sqlite3_user_data(pCtx);
439 unsigned i1, i2;
440 double v1, v2;
441 double ix, vx;
442 p = (Percentile*)sqlite3_aggregate_context(pCtx, 0);
443 if( p==0 ) return;
444 if( p->a==0 ) return;
445 if( p->nUsed ){
446 if( p->bSorted==0 ){
447 assert( p->nUsed>1 );
448 percentSort(p->a, p->nUsed);
449 p->bSorted = 1;
450 }
451 ix = p->rPct*(p->nUsed-1);
452 i1 = (unsigned)ix;
453 if( pFunc->bDiscrete ){
454 vx = p->a[i1];
455 }else{
456 i2 = ix==(double)i1 || i1==p->nUsed-1 ? i1 : i1+1;
457 v1 = p->a[i1];
458 v2 = p->a[i2];
459 vx = v1 + (v2-v1)*(ix-i1);
460 }
461 sqlite3_result_double(pCtx, vx);
462 }
463 if( bIsFinal ){
464 sqlite3_free(p->a);
465 memset(p, 0, sizeof(*p));
466 }else{
467 p->bKeepSorted = 1;
468 }
469 }
470 static void percentFinal(sqlite3_context *pCtx){
471 percentCompute(pCtx, 1);
472 }
473 static void percentValue(sqlite3_context *pCtx){
474 percentCompute(pCtx, 0);
475 }
476
477 #if defined(_WIN32) && !defined(SQLITE3_H) && !defined(SQLITE_STATIC_PERCENTILE)
478 __declspec(dllexport)
479 #endif
480 int sqlite3_percentile_init(
481 sqlite3 *db,
482 char **pzErrMsg,
483 const sqlite3_api_routines *pApi
484 ){
485 int rc = SQLITE_OK;
486 unsigned int i;
487 #ifdef SQLITE3EXT_H
488 SQLITE_EXTENSION_INIT2(pApi);
489 #else
490 (void)pApi; /* Unused parameter */
491 #endif
492 (void)pzErrMsg; /* Unused parameter */
493 for(i=0; i<sizeof(aPercentFunc)/sizeof(aPercentFunc[0]); i++){
494 rc = sqlite3_create_window_function(db,
495 aPercentFunc[i].zName,
496 aPercentFunc[i].nArg,
497 SQLITE_UTF8|SQLITE_INNOCUOUS|SQLITE_SELFORDER1,
498 (void*)&aPercentFunc[i],
499 percentStep, percentFinal, percentValue, percentInverse, 0);
500 if( rc ) break;
501 }
502 return rc;
503 }