Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Add the percentile() SQL function as a loadable extension in the ext/misc directory. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
a64d760d9290b1be78cdda7ae66d4f02 |
User & Date: | drh 2013-05-28 20:25:54.766 |
Context
2013-05-29
| ||
14:22 | Add tests for running FTS 'merge' and 'optimize' commands in shared cache mode. (check-in: 09e5a7ad85 user: dan tags: trunk) | |
2013-05-28
| ||
20:25 | Add the percentile() SQL function as a loadable extension in the ext/misc directory. (check-in: a64d760d92 user: drh tags: trunk) | |
17:30 | Finish removing the sqlite3.inTrans field. In the previous check-in, it was merely commented out because I failed to select File->Save on my text editor. (check-in: 2f97e38a66 user: drh tags: trunk) | |
Changes
Changes to Makefile.in.
︙ | ︙ | |||
389 390 391 392 393 394 395 396 397 398 399 400 401 402 | # TESTSRC += \ $(TOP)/ext/misc/amatch.c \ $(TOP)/ext/misc/closure.c \ $(TOP)/ext/misc/fuzzer.c \ $(TOP)/ext/misc/ieee754.c \ $(TOP)/ext/misc/nextchar.c \ $(TOP)/ext/misc/regexp.c \ $(TOP)/ext/misc/spellfix.c \ $(TOP)/ext/misc/wholenumber.c # Source code to the library files needed by the test fixture # TESTSRC2 = \ | > | 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 | # TESTSRC += \ $(TOP)/ext/misc/amatch.c \ $(TOP)/ext/misc/closure.c \ $(TOP)/ext/misc/fuzzer.c \ $(TOP)/ext/misc/ieee754.c \ $(TOP)/ext/misc/nextchar.c \ $(TOP)/ext/misc/percentile.c \ $(TOP)/ext/misc/regexp.c \ $(TOP)/ext/misc/spellfix.c \ $(TOP)/ext/misc/wholenumber.c # Source code to the library files needed by the test fixture # TESTSRC2 = \ |
︙ | ︙ |
Changes to Makefile.msc.
︙ | ︙ | |||
709 710 711 712 713 714 715 716 717 718 719 720 721 722 | # TESTEXT = \ $(TOP)\ext\misc\amatch.c \ $(TOP)\ext\misc\closure.c \ $(TOP)\ext\misc\fuzzer.c \ $(TOP)\ext\misc\ieee754.c \ $(TOP)\ext\misc\nextchar.c \ $(TOP)\ext\misc\regexp.c \ $(TOP)\ext\misc\spellfix.c \ $(TOP)\ext\misc\wholenumber.c # Source code to the library files needed by the test fixture # | > | 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 | # TESTEXT = \ $(TOP)\ext\misc\amatch.c \ $(TOP)\ext\misc\closure.c \ $(TOP)\ext\misc\fuzzer.c \ $(TOP)\ext\misc\ieee754.c \ $(TOP)\ext\misc\nextchar.c \ $(TOP)\ext\misc\percentile.c \ $(TOP)\ext\misc\regexp.c \ $(TOP)\ext\misc\spellfix.c \ $(TOP)\ext\misc\wholenumber.c # Source code to the library files needed by the test fixture # |
︙ | ︙ |
Added ext/misc/percentile.c.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 | /* ** 2013-05-28 ** ** The author disclaims copyright to this source code. In place of ** a legal notice, here is a blessing: ** ** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give. ** ****************************************************************************** ** ** This file contains code to implement the percentile(Y,P) SQL function ** as described below: ** ** (1) The percentile(Y,P) function is an aggregate function taking ** exactly two arguments. ** ** (2) If the P argument to percentile(Y,P) is not the same for every ** row in the aggregate then an error is thrown. The word "same" ** in the previous sentence means that the value differ by less ** than 0.001. ** ** (3) If the P argument to percentile(Y,P) evaluates to anything other ** than a number in the range of 0.0 to 100.0 inclusive then an ** error is thrown. ** ** (4) If any Y argument to percentile(Y,P) evaluates to a value that ** is not NULL and is not numeric then an error is thrown. ** ** (5) If any Y argument to percentile(Y,P) evaluates to plus or minus ** infinity then an error is thrown. (SQLite always interprets NaN ** values as NULL.) ** ** (6) Both Y and P in percentile(Y,P) can be arbitrary expressions, ** including CASE WHEN expressions. ** ** (7) The percentile(Y,P) aggregate is able to handle inputs of at least ** one million (1,000,000) rows. ** ** (8) If there are no non-NULL values for Y, then percentile(Y,P) ** returns NULL. ** ** (9) If there is exactly one non-NULL value for Y, the percentile(Y,P) ** returns the one Y value. ** ** (10) If there N non-NULL values of Y where N is two or more and ** the Y values are ordered from least to greatest and a graph is ** drawn from 0 to N-1 such that the height of the graph at J is ** the J-th Y value and such that straight lines are drawn between ** adjacent Y values, then the percentile(Y,P) function returns ** the height of the graph at P*(N-1)/100. ** ** (11) The percentile(Y,P) function always returns either a floating ** point number or NULL. ** ** (12) The percentile(Y,P) is implemented as a single C99 source-code ** file that compiles into a shared-library or DLL that can be loaded ** into SQLite using the sqlite3_load_extension() interface. */ #include "sqlite3ext.h" SQLITE_EXTENSION_INIT1 #include <assert.h> #include <string.h> #include <stdlib.h> /* The following object is the session context for a single percentile() ** function. We have to remember all input Y values until the very end. ** Those values are accumulated in the Percentile.a[] array. */ typedef struct Percentile Percentile; struct Percentile { unsigned nAlloc; /* Number of slots allocated for a[] */ unsigned nUsed; /* Number of slots actually used in a[] */ double rPct; /* 1.0 more than the value for P */ double *a; /* Array of Y values */ }; /* ** Return TRUE if the input floating-point number is an infinity. */ static int isInfinity(double r){ sqlite3_uint64 u; assert( sizeof(u)==sizeof(r) ); memcpy(&u, &r, sizeof(u)); return ((u>>52)&0x7ff)==0x7ff; } /* ** Return TRUE if two doubles differ by 0.001 or less */ static int sameValue(double a, double b){ a -= b; return a>=-0.001 && a<=0.001; } /* ** The "step" function for percentile(Y,P) is called once for each ** input row. */ static void percentStep(sqlite3_context *pCtx, int argc, sqlite3_value **argv){ Percentile *p; double rPct; int eType; double y; assert( argc==2 ); /* Requirement 3: P must be a number between 0 and 100 */ eType = sqlite3_value_numeric_type(argv[1]); rPct = sqlite3_value_double(argv[1]); if( (eType!=SQLITE_INTEGER && eType!=SQLITE_FLOAT) || ((rPct = sqlite3_value_double(argv[1]))<0.0 || rPct>100.0) ){ sqlite3_result_error(pCtx, "2nd argument to percentile() is not " "a number between 0.0 and 100.0", -1); return; } /* Allocate the session context. */ p = (Percentile*)sqlite3_aggregate_context(pCtx, sizeof(*p)); if( p==0 ) return; /* Remember the P value. Throw an error if the P value is different ** from any prior row, per Requirement (2). */ if( p->rPct==0.0 ){ p->rPct = rPct+1.0; }else if( !sameValue(p->rPct,rPct+1.0) ){ sqlite3_result_error(pCtx, "2nd argument to percentile() is not the " "same for all input rows", -1); return; } /* Ignore rows for which Y is NULL */ eType = sqlite3_value_type(argv[0]); if( eType==SQLITE_NULL ) return; /* If not NULL, then Y must be numeric. Otherwise throw an error. ** Requirement 4 */ if( eType!=SQLITE_INTEGER && eType!=SQLITE_FLOAT ){ sqlite3_result_error(pCtx, "1st argument to percentile() is not " "numeric", -1); return; } /* Throw an error if the Y value is infinity or NaN */ y = sqlite3_value_double(argv[0]); if( isInfinity(y) ){ sqlite3_result_error(pCtx, "Inf input to percentile()", -1); return; } /* Allocate and store the Y */ if( p->nUsed>=p->nAlloc ){ unsigned n = p->nAlloc*2 + 250; double *a = sqlite3_realloc(p->a, sizeof(double)*n); if( a==0 ){ sqlite3_free(p->a); memset(p, 0, sizeof(*p)); sqlite3_result_error_nomem(pCtx); return; } p->nAlloc = n; p->a = a; } p->a[p->nUsed++] = y; } /* ** Compare to doubles for sorting using qsort() */ static int doubleCmp(const void *pA, const void *pB){ double a = *(double*)pA; double b = *(double*)pB; if( a==b ) return 0; if( a<b ) return -1; return +1; } /* ** Called to compute the final output of percentile() and to clean ** up all allocated memory. */ static void percentFinal(sqlite3_context *pCtx){ Percentile *p; unsigned i1, i2; double v1, v2; double ix, vx; p = (Percentile*)sqlite3_aggregate_context(pCtx, 0); if( p==0 ) return; if( p->a==0 ) return; if( p->nUsed ){ qsort(p->a, p->nUsed, sizeof(double), doubleCmp); ix = (p->rPct-1.0)*(p->nUsed-1)*0.01; i1 = ix; i2 = ix==(double)i1 || i1==p->nUsed-1 ? i1 : i1+1; v1 = p->a[i1]; v2 = p->a[i2]; vx = v1 + (v2-v1)*(ix-i1); sqlite3_result_double(pCtx, vx); } sqlite3_free(p->a); memset(p, 0, sizeof(*p)); } #ifdef _WIN32 __declspec(dllexport) #endif int sqlite3_percentile_init( sqlite3 *db, char **pzErrMsg, const sqlite3_api_routines *pApi ){ int rc = SQLITE_OK; SQLITE_EXTENSION_INIT2(pApi); (void)pzErrMsg; /* Unused parameter */ rc = sqlite3_create_function(db, "percentile", 2, SQLITE_UTF8, 0, 0, percentStep, percentFinal); return rc; } |
Changes to main.mk.
︙ | ︙ | |||
271 272 273 274 275 276 277 278 279 280 281 282 283 284 | # TESTSRC += \ $(TOP)/ext/misc/amatch.c \ $(TOP)/ext/misc/closure.c \ $(TOP)/ext/misc/fuzzer.c \ $(TOP)/ext/misc/ieee754.c \ $(TOP)/ext/misc/nextchar.c \ $(TOP)/ext/misc/regexp.c \ $(TOP)/ext/misc/spellfix.c \ $(TOP)/ext/misc/wholenumber.c #TESTSRC += $(TOP)/ext/fts2/fts2_tokenizer.c #TESTSRC += $(TOP)/ext/fts3/fts3_tokenizer.c | > | 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 | # TESTSRC += \ $(TOP)/ext/misc/amatch.c \ $(TOP)/ext/misc/closure.c \ $(TOP)/ext/misc/fuzzer.c \ $(TOP)/ext/misc/ieee754.c \ $(TOP)/ext/misc/nextchar.c \ $(TOP)/ext/misc/percentile.c \ $(TOP)/ext/misc/regexp.c \ $(TOP)/ext/misc/spellfix.c \ $(TOP)/ext/misc/wholenumber.c #TESTSRC += $(TOP)/ext/fts2/fts2_tokenizer.c #TESTSRC += $(TOP)/ext/fts3/fts3_tokenizer.c |
︙ | ︙ |
Changes to src/test1.c.
︙ | ︙ | |||
6008 6009 6010 6011 6012 6013 6014 6015 6016 6017 6018 6019 6020 6021 6022 6023 6024 6025 6026 6027 6028 6029 6030 6031 6032 6033 | Tcl_Obj *CONST objv[] ){ extern int sqlite3_amatch_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_closure_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_fuzzer_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_ieee_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_nextchar_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_regexp_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_spellfix_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_wholenumber_init(sqlite3*,char**,const sqlite3_api_routines*); static const struct { const char *zExtName; int (*pInit)(sqlite3*,char**,const sqlite3_api_routines*); } aExtension[] = { { "amatch", sqlite3_amatch_init }, { "closure", sqlite3_closure_init }, { "fuzzer", sqlite3_fuzzer_init }, { "ieee754", sqlite3_ieee_init }, { "nextchar", sqlite3_nextchar_init }, { "regexp", sqlite3_regexp_init }, { "spellfix", sqlite3_spellfix_init }, { "wholenumber", sqlite3_wholenumber_init }, }; sqlite3 *db; const char *zName; int i, j, rc; | > > | 6008 6009 6010 6011 6012 6013 6014 6015 6016 6017 6018 6019 6020 6021 6022 6023 6024 6025 6026 6027 6028 6029 6030 6031 6032 6033 6034 6035 | Tcl_Obj *CONST objv[] ){ extern int sqlite3_amatch_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_closure_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_fuzzer_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_ieee_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_nextchar_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_percentile_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_regexp_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_spellfix_init(sqlite3*,char**,const sqlite3_api_routines*); extern int sqlite3_wholenumber_init(sqlite3*,char**,const sqlite3_api_routines*); static const struct { const char *zExtName; int (*pInit)(sqlite3*,char**,const sqlite3_api_routines*); } aExtension[] = { { "amatch", sqlite3_amatch_init }, { "closure", sqlite3_closure_init }, { "fuzzer", sqlite3_fuzzer_init }, { "ieee754", sqlite3_ieee_init }, { "nextchar", sqlite3_nextchar_init }, { "percentile", sqlite3_percentile_init }, { "regexp", sqlite3_regexp_init }, { "spellfix", sqlite3_spellfix_init }, { "wholenumber", sqlite3_wholenumber_init }, }; sqlite3 *db; const char *zName; int i, j, rc; |
︙ | ︙ |
Added test/percentile.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 | # 2013-05-28 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is percentile.c extension # set testdir [file dirname $argv0] source $testdir/tester.tcl # Basic test of the percentile() function. # do_test percentile-1.0 { load_static_extension db percentile execsql { CREATE TABLE t1(x); INSERT INTO t1 VALUES(1),(4),(6),(7),(8),(9),(11),(11),(11); } execsql {SELECT percentile(x,0) FROM t1} } {1.0} foreach {in out} { 100 11.0 50 8.0 12.5 4.0 15 4.4 20 5.2 80 11.0 89 11.0 } { do_test percentile-1.1.$in { execsql {SELECT percentile(x,$in) FROM t1} } $out } # Add some NULL values. # do_test percentile-1.2 { execsql {INSERT INTO t1 VALUES(NULL),(NULL);} } {} foreach {in out} { 100 11.0 50 8.0 12.5 4.0 15 4.4 20 5.2 80 11.0 89 11.0 } { do_test percentile-1.3.$in { execsql {SELECT percentile(x,$in) FROM t1} } $out } # The second argument to percentile can change some, but not much. # do_test percentile-1.4 { catchsql {SELECT round(percentile(x, 15+0.000001*rowid),1) FROM t1} } {0 4.4} do_test percentile-1.5 { catchsql {SELECT round(percentile(x, 15+0.1*rowid),1) FROM t1} } {1 {2nd argument to percentile() is not the same for all input rows}} # Input values in a random order # do_test percentile-1.6 { execsql { CREATE TABLE t2(x); INSERT INTO t2 SELECT x+0.0 FROM t1 ORDER BY random(); } } {} foreach {in out} { 100 11.0 50 8.0 12.5 4.0 15 4.4 20 5.2 80 11.0 89 11.0 } { do_test percentile-1.7.$in { execsql {SELECT percentile(x,$in) FROM t2} } $out } # Wrong number of arguments # do_test percentile-1.8 { catchsql {SELECT percentile(x,0,1) FROM t1} } {1 {wrong number of arguments to function percentile()}} do_test percentile-1.9 { catchsql {SELECT percentile(x) FROM t1} } {1 {wrong number of arguments to function percentile()}} # Second argument must be numeric # do_test percentile-1.10 { catchsql {SELECT percentile(x,null) FROM t1} } {1 {2nd argument to percentile() is not a number between 0.0 and 100.0}} do_test percentile-1.11 { catchsql {SELECT percentile(x,'fifty') FROM t1} } {1 {2nd argument to percentile() is not a number between 0.0 and 100.0}} do_test percentile-1.12 { catchsql {SELECT percentile(x,x'3530') FROM t1} } {1 {2nd argument to percentile() is not a number between 0.0 and 100.0}} # Second argument is out of range # do_test percentile-1.13 { catchsql {SELECT percentile(x,-0.0000001) FROM t1} } {1 {2nd argument to percentile() is not a number between 0.0 and 100.0}} do_test percentile-1.14 { catchsql {SELECT percentile(x,100.0000001) FROM t1} } {1 {2nd argument to percentile() is not a number between 0.0 and 100.0}} # First argument is not NULL and is not NUMERIC # do_test percentile-1.15 { catchsql { BEGIN; UPDATE t1 SET x='50' WHERE x IS NULL; SELECT percentile(x, 50) FROM t1; } } {1 {1st argument to percentile() is not numeric}} do_test percentile-1.16 { catchsql { ROLLBACK; BEGIN; UPDATE t1 SET x=x'3530' WHERE x IS NULL; SELECT percentile(x, 50) FROM t1; } } {1 {1st argument to percentile() is not numeric}} do_test percentile-1.17 { catchsql { ROLLBACK; SELECT percentile(x, 50) FROM t1; } } {0 8.0} # No non-NULL entries. # do_test percentile-1.18 { execsql { UPDATE t1 SET x=NULL; SELECT ifnull(percentile(x, 50),'NULL') FROM t1 } } {NULL} # Exactly one non-NULL entry # do_test percentile-1.19 { execsql { UPDATE t1 SET x=12345 WHERE rowid=5; SELECT percentile(x, 0), percentile(x, 50), percentile(x,100) FROM t1 } } {12345.0 12345.0 12345.0} # Infinity as an input # do_test percentile-1.20 { catchsql { DELETE FROM t1; INSERT INTO t1 SELECT x+0.0 FROM t2; UPDATE t1 SET x=1.0e300*1.0e300 WHERE rowid=5; SELECT percentile(x,50) from t1; } } {1 {Inf input to percentile()}} do_test percentile-1.21 { catchsql { UPDATE t1 SET x=-1.0e300*1.0e300 WHERE rowid=5; SELECT percentile(x,50) from t1; } } {1 {Inf input to percentile()}} # Million-row Inputs # do_test percentile-2.0 { load_static_extension db wholenumber execsql { CREATE VIRTUAL TABLE nums USING wholenumber; CREATE TABLE t3(x); INSERT INTO t3 SELECT value-1 FROM nums WHERE value BETWEEN 1 AND 500000; INSERT INTO t3 SELECT value*10 FROM nums WHERE value BETWEEN 500000 AND 999999; SELECT count(*) FROM t3; } } {1000000} foreach {in out} { 0 0.0 100 9999990.0 50 2749999.5 10 99999.9 } { do_test percentile-2.1.$in { execsql { SELECT percentile(x, $in) from t3; } } $out } finish_test |