Re: [sqlite] patch to allow integer rtree keys
wrote: On Fri, Jul 11, 2008 at 9:23 PM, Steve Friedman wrote: > I've just started using the rtree extension, and have found that > the 32-bit > float for the range keys is not appropriate for me. Please find > attached a > patch for rtree.c (based on v1.5) that allows for int -OR- > unsigned int -OR- > float operation. >> >> What kind of advantages does using int over float have here? >> >> With a little work it might be possible to select int or float at >> runtime. Do other people who know about such things think that this >> would be a good option to have? > > Dan, > > I think the need for integer support is to avoid floating point rounding > errors that might cause you to miss a key otherwise. > > I think this would be a nice feature to have. I think it should be > implemented at runtime because if I ever have an application that need > both say time (int) and spatial rtrees (floats) then it puts me into a > problem of not being able to support both in a single build. > > -Steve I agree with your desire; however, let's not let the perfect become the enemy of the good. My patch satisfies my initial need. Can I have that included in 3.6.0? A subsequent patch, with the more complete implementation to eliminate compile-time restrictions, could be included in a later release. Steve Friedman ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] patch to allow integer rtree keys
On Jul 12, 2008, at 11:08 AM, Dan wrote: > > On Jul 12, 2008, at 2:42 AM, Steve Friedman wrote: > >> >> >> Filip Navara wrote: >>> how about actually attaching the patch? :) >>> >>> - Filip >>> >>> On Fri, Jul 11, 2008 at 9:23 PM, Steve Friedman >>> <[EMAIL PROTECTED]> wrote: I've just started using the rtree extension, and have found that the 32-bit float for the range keys is not appropriate for me. Please find attached a patch for rtree.c (based on v1.5) that allows for int -OR- unsigned int -OR- float operation. > > What kind of advantages does using int over float have here? > > With a little work it might be possible to select int or float at > runtime. Do other people who know about such things think that this > would be a good option to have? > An important class of problems use all 32bits of an integer. Simply don't have enough bits in a 32bit float to cover integer range. Perhaps the implementation just looks at the type supplied on the create table statement. To keep things simple throw an error of they are not all the same type or are of an unsupported type. Unsigned ints should be supported! ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] patch to allow integer rtree keys
Dan wrote:
> On Jul 12, 2008, at 2:42 AM, Steve Friedman wrote:
>
>>
>> Filip Navara wrote:
>>> how about actually attaching the patch? :)
>>>
>>> - Filip
>>>
>>> On Fri, Jul 11, 2008 at 9:23 PM, Steve Friedman
>>> <[EMAIL PROTECTED]> wrote:
I've just started using the rtree extension, and have found that
the 32-bit
float for the range keys is not appropriate for me. Please find
attached a
patch for rtree.c (based on v1.5) that allows for int -OR-
unsigned int -OR-
float operation.
>
> What kind of advantages does using int over float have here?
>
> With a little work it might be possible to select int or float at
> runtime. Do other people who know about such things think that this
> would be a good option to have?
Dan,
I think the need for integer support is to avoid floating point rounding
errors that might cause you to miss a key otherwise.
I think this would be a nice feature to have. I think it should be
implemented at runtime because if I ever have an application that need
both say time (int) and spatial rtrees (floats) then it puts me into a
problem of not being able to support both in a single build.
-Steve
Steve Friedman
>> Not sure where it got deleted (since my inbox shows the attachment).
>> Included inline...
>>
>> --- rtree.c 2008-07-11 15:04:42.0 -0400
>> +++ rtreemod.c 2008-07-11 15:04:31.0 -0400
>> @@ -149,13 +149,36 @@
>> RtreeConstraint *aConstraint; /* Search constraints. */
>> };
>>
>> +#if defined( SQLITE_RTREE_TYPE_INT)
>> +typedef int ConstraintType;
>> +# define sqlite3_result_ConstraintType sqlite3_result_int
>> +# define sqlite3_value_ConstraintType(x) ((int) sqlite3_value_int
>> ((x)))
>> +# define sqlite3_snprintf_ConstraintType( a, b, c) \
>> + sqlite3_snprintf( (a), (b), " %d", (c))
>> +
>> +#elif defined(SQLITE_RTREE_TYPE_UINT)
>> +typedef u32 ConstraintType;
>> +# define sqlite3_result_ConstraintType sqlite3_result_int64
>> +# define sqlite3_value_ConstraintType(x) ((u32)
>> sqlite3_value_int64((x)))
>> +# define sqlite3_snprintf_ConstraintType( a, b, c) \
>> + sqlite3_snprintf( (a), (b), " %u", (c))
>> +
>> +#else
>> +typedef float ConstraintType;
>> +# define sqlite3_result_ConstraintType sqlite3_result_double
>> +# define sqlite3_value_ConstraintType(x) ((float)
>> sqlite3_value_double((x)))
>> +# define sqlite3_snprintf_ConstraintType( a, b, c) \
>> + sqlite3_snprintf( (a), (b), " %f", (double) (c))
>> +#endif
>> +
>> +
>> /*
>> ** A search constraint.
>> */
>> struct RtreeConstraint {
>> int iCoord; /* Index of constrained
>> coordinate */
>> int op; /* Constraining operation */
>> - float rValue; /* Constraint value. */
>> + ConstraintType rValue;/* Constraint value. */
>> };
>>
>> /* Possible values for RtreeConstraint.op */
>> @@ -198,7 +221,7 @@
>> */
>> struct RtreeCell {
>> i64 iRowid;
>> - float aCoord[RTREE_MAX_DIMENSIONS*2];
>> + ConstraintType aCoord[RTREE_MAX_DIMENSIONS*2];
>> };
>>
>> #define MAX(x,y) ((x) < (y) ? (y) : (x))
>> @@ -211,14 +234,14 @@
>> static int readInt16(u8 *p){
>> return (p[0]<<8) + p[1];
>> }
>> -static float readReal32(u8 *p){
>> +static ConstraintType readReal32(u8 *p){
>> u32 i = (
>> (((u32)p[0]) << 24) +
>> (((u32)p[1]) << 16) +
>> (((u32)p[2]) << 8) +
>> (((u32)p[3]) << 0)
>> );
>> - return *(float *)&i;
>> + return *(ConstraintType *)&i;
>> }
>> static i64 readInt64(u8 *p){
>> return (
>> @@ -243,9 +266,9 @@
>> p[1] = (i>> 0)&0xFF;
>> return 2;
>> }
>> -static int writeReal32(u8 *p, float f){
>> +static int writeReal32(u8 *p, ConstraintType f){
>> u32 i;
>> - assert( sizeof(float)==4 );
>> + assert( sizeof(ConstraintType)==4 );
>> assert( sizeof(u32)==4 );
>> i = *(u32 *)&f;
>> p[0] = (i>>24)&0xFF;
>> @@ -543,7 +566,7 @@
>> /*
>> ** Return coordinate iCoord from cell iCell in node pNode.
>> */
>> -static float nodeGetCoord(
>> +static ConstraintType nodeGetCoord(
>> Rtree *pRtree,
>> RtreeNode *pNode,
>> int iCell,
>> @@ -721,8 +744,8 @@
>> for(ii=0; iinConstraint; ii++){
>> RtreeConstraint *p = &pCursor->aConstraint[ii];
>>
>> -float cell_min = cell.aCoord[(p->iCoord>>1)*2];
>> -float cell_max = cell.aCoord[(p->iCoord>>1)*2+1];
>> +ConstraintType cell_min = cell.aCoord[(p->iCoord>>1)*2];
>> +ConstraintType cell_max = cell.aCoord[(p->iCoord>>1)*2+1];
>> assert( cell_min<=cell_max );
>>
>> switch( p->op ){
>> @@ -769,7 +792,7 @@
>> nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
>> for(ii=0; iinConstraint; ii++){
>> RtreeConstraint *p = &pCursor->aConstraint[ii];
>> -float cell_val = cell.aCoord[p->iCoord];
>> +ConstraintType cell_val = cell.aCoord[p->iCoord];
>> int res;
>> switch( p->op ){
>> case RTREE
Re: [sqlite] patch to allow integer rtree keys
On Jul 12, 2008, at 2:42 AM, Steve Friedman wrote:
>
>
> Filip Navara wrote:
>> how about actually attaching the patch? :)
>>
>> - Filip
>>
>> On Fri, Jul 11, 2008 at 9:23 PM, Steve Friedman
>> <[EMAIL PROTECTED]> wrote:
>>> I've just started using the rtree extension, and have found that
>>> the 32-bit
>>> float for the range keys is not appropriate for me. Please find
>>> attached a
>>> patch for rtree.c (based on v1.5) that allows for int -OR-
>>> unsigned int -OR-
>>> float operation.
What kind of advantages does using int over float have here?
With a little work it might be possible to select int or float at
runtime. Do other people who know about such things think that this
would be a good option to have?
Dan.
>>> Steve Friedman
>
> Not sure where it got deleted (since my inbox shows the attachment).
> Included inline...
>
> --- rtree.c 2008-07-11 15:04:42.0 -0400
> +++ rtreemod.c 2008-07-11 15:04:31.0 -0400
> @@ -149,13 +149,36 @@
> RtreeConstraint *aConstraint; /* Search constraints. */
> };
>
> +#if defined( SQLITE_RTREE_TYPE_INT)
> +typedef int ConstraintType;
> +# define sqlite3_result_ConstraintType sqlite3_result_int
> +# define sqlite3_value_ConstraintType(x) ((int) sqlite3_value_int
> ((x)))
> +# define sqlite3_snprintf_ConstraintType( a, b, c) \
> + sqlite3_snprintf( (a), (b), " %d", (c))
> +
> +#elif defined(SQLITE_RTREE_TYPE_UINT)
> +typedef u32 ConstraintType;
> +# define sqlite3_result_ConstraintType sqlite3_result_int64
> +# define sqlite3_value_ConstraintType(x) ((u32)
> sqlite3_value_int64((x)))
> +# define sqlite3_snprintf_ConstraintType( a, b, c) \
> + sqlite3_snprintf( (a), (b), " %u", (c))
> +
> +#else
> +typedef float ConstraintType;
> +# define sqlite3_result_ConstraintType sqlite3_result_double
> +# define sqlite3_value_ConstraintType(x) ((float)
> sqlite3_value_double((x)))
> +# define sqlite3_snprintf_ConstraintType( a, b, c) \
> + sqlite3_snprintf( (a), (b), " %f", (double) (c))
> +#endif
> +
> +
> /*
> ** A search constraint.
> */
> struct RtreeConstraint {
> int iCoord; /* Index of constrained
> coordinate */
> int op; /* Constraining operation */
> - float rValue; /* Constraint value. */
> + ConstraintType rValue;/* Constraint value. */
> };
>
> /* Possible values for RtreeConstraint.op */
> @@ -198,7 +221,7 @@
> */
> struct RtreeCell {
> i64 iRowid;
> - float aCoord[RTREE_MAX_DIMENSIONS*2];
> + ConstraintType aCoord[RTREE_MAX_DIMENSIONS*2];
> };
>
> #define MAX(x,y) ((x) < (y) ? (y) : (x))
> @@ -211,14 +234,14 @@
> static int readInt16(u8 *p){
> return (p[0]<<8) + p[1];
> }
> -static float readReal32(u8 *p){
> +static ConstraintType readReal32(u8 *p){
> u32 i = (
> (((u32)p[0]) << 24) +
> (((u32)p[1]) << 16) +
> (((u32)p[2]) << 8) +
> (((u32)p[3]) << 0)
> );
> - return *(float *)&i;
> + return *(ConstraintType *)&i;
> }
> static i64 readInt64(u8 *p){
> return (
> @@ -243,9 +266,9 @@
> p[1] = (i>> 0)&0xFF;
> return 2;
> }
> -static int writeReal32(u8 *p, float f){
> +static int writeReal32(u8 *p, ConstraintType f){
> u32 i;
> - assert( sizeof(float)==4 );
> + assert( sizeof(ConstraintType)==4 );
> assert( sizeof(u32)==4 );
> i = *(u32 *)&f;
> p[0] = (i>>24)&0xFF;
> @@ -543,7 +566,7 @@
> /*
> ** Return coordinate iCoord from cell iCell in node pNode.
> */
> -static float nodeGetCoord(
> +static ConstraintType nodeGetCoord(
> Rtree *pRtree,
> RtreeNode *pNode,
> int iCell,
> @@ -721,8 +744,8 @@
> for(ii=0; iinConstraint; ii++){
> RtreeConstraint *p = &pCursor->aConstraint[ii];
>
> -float cell_min = cell.aCoord[(p->iCoord>>1)*2];
> -float cell_max = cell.aCoord[(p->iCoord>>1)*2+1];
> +ConstraintType cell_min = cell.aCoord[(p->iCoord>>1)*2];
> +ConstraintType cell_max = cell.aCoord[(p->iCoord>>1)*2+1];
> assert( cell_min<=cell_max );
>
> switch( p->op ){
> @@ -769,7 +792,7 @@
> nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
> for(ii=0; iinConstraint; ii++){
> RtreeConstraint *p = &pCursor->aConstraint[ii];
> -float cell_val = cell.aCoord[p->iCoord];
> +ConstraintType cell_val = cell.aCoord[p->iCoord];
> int res;
> switch( p->op ){
> case RTREE_LE: res = (cell_val<=p->rValue); break;
> @@ -935,8 +958,8 @@
> i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
> sqlite3_result_int64(ctx, iRowid);
> }else{
> -float fCoord = nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell,
> i-1);
> -sqlite3_result_double(ctx, fCoord);
> +ConstraintType fCoord = nodeGetCoord(pRtree, pCsr->pNode,
> pCsr->iCell, i-1);
> +sqlite3_result_ConstraintType(ctx, fCoord);
> }
>
> return SQLITE_OK;
> @@ -1009,7 +1032,7 @@
> RtreeConstraint *p = &pCsr->aConstraint
Re: [sqlite] patch to allow integer rtree keys
Filip Navara wrote:
> how about actually attaching the patch? :)
>
> - Filip
>
> On Fri, Jul 11, 2008 at 9:23 PM, Steve Friedman <[EMAIL PROTECTED]> wrote:
>> I've just started using the rtree extension, and have found that the 32-bit
>> float for the range keys is not appropriate for me. Please find attached a
>> patch for rtree.c (based on v1.5) that allows for int -OR- unsigned int -OR-
>> float operation.
>>
>> Steve Friedman
Not sure where it got deleted (since my inbox shows the attachment).
Included inline...
--- rtree.c 2008-07-11 15:04:42.0 -0400
+++ rtreemod.c 2008-07-11 15:04:31.0 -0400
@@ -149,13 +149,36 @@
RtreeConstraint *aConstraint; /* Search constraints. */
};
+#if defined( SQLITE_RTREE_TYPE_INT)
+typedef int ConstraintType;
+# define sqlite3_result_ConstraintType sqlite3_result_int
+# define sqlite3_value_ConstraintType(x) ((int) sqlite3_value_int((x)))
+# define sqlite3_snprintf_ConstraintType( a, b, c) \
+ sqlite3_snprintf( (a), (b), " %d", (c))
+
+#elif defined(SQLITE_RTREE_TYPE_UINT)
+typedef u32 ConstraintType;
+# define sqlite3_result_ConstraintType sqlite3_result_int64
+# define sqlite3_value_ConstraintType(x) ((u32) sqlite3_value_int64((x)))
+# define sqlite3_snprintf_ConstraintType( a, b, c) \
+ sqlite3_snprintf( (a), (b), " %u", (c))
+
+#else
+typedef float ConstraintType;
+# define sqlite3_result_ConstraintType sqlite3_result_double
+# define sqlite3_value_ConstraintType(x) ((float)
sqlite3_value_double((x)))
+# define sqlite3_snprintf_ConstraintType( a, b, c) \
+ sqlite3_snprintf( (a), (b), " %f", (double) (c))
+#endif
+
+
/*
** A search constraint.
*/
struct RtreeConstraint {
int iCoord; /* Index of constrained coordinate */
int op; /* Constraining operation */
- float rValue; /* Constraint value. */
+ ConstraintType rValue;/* Constraint value. */
};
/* Possible values for RtreeConstraint.op */
@@ -198,7 +221,7 @@
*/
struct RtreeCell {
i64 iRowid;
- float aCoord[RTREE_MAX_DIMENSIONS*2];
+ ConstraintType aCoord[RTREE_MAX_DIMENSIONS*2];
};
#define MAX(x,y) ((x) < (y) ? (y) : (x))
@@ -211,14 +234,14 @@
static int readInt16(u8 *p){
return (p[0]<<8) + p[1];
}
-static float readReal32(u8 *p){
+static ConstraintType readReal32(u8 *p){
u32 i = (
(((u32)p[0]) << 24) +
(((u32)p[1]) << 16) +
(((u32)p[2]) << 8) +
(((u32)p[3]) << 0)
);
- return *(float *)&i;
+ return *(ConstraintType *)&i;
}
static i64 readInt64(u8 *p){
return (
@@ -243,9 +266,9 @@
p[1] = (i>> 0)&0xFF;
return 2;
}
-static int writeReal32(u8 *p, float f){
+static int writeReal32(u8 *p, ConstraintType f){
u32 i;
- assert( sizeof(float)==4 );
+ assert( sizeof(ConstraintType)==4 );
assert( sizeof(u32)==4 );
i = *(u32 *)&f;
p[0] = (i>>24)&0xFF;
@@ -543,7 +566,7 @@
/*
** Return coordinate iCoord from cell iCell in node pNode.
*/
-static float nodeGetCoord(
+static ConstraintType nodeGetCoord(
Rtree *pRtree,
RtreeNode *pNode,
int iCell,
@@ -721,8 +744,8 @@
for(ii=0; iinConstraint; ii++){
RtreeConstraint *p = &pCursor->aConstraint[ii];
-float cell_min = cell.aCoord[(p->iCoord>>1)*2];
-float cell_max = cell.aCoord[(p->iCoord>>1)*2+1];
+ConstraintType cell_min = cell.aCoord[(p->iCoord>>1)*2];
+ConstraintType cell_max = cell.aCoord[(p->iCoord>>1)*2+1];
assert( cell_min<=cell_max );
switch( p->op ){
@@ -769,7 +792,7 @@
nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
for(ii=0; iinConstraint; ii++){
RtreeConstraint *p = &pCursor->aConstraint[ii];
-float cell_val = cell.aCoord[p->iCoord];
+ConstraintType cell_val = cell.aCoord[p->iCoord];
int res;
switch( p->op ){
case RTREE_LE: res = (cell_val<=p->rValue); break;
@@ -935,8 +958,8 @@
i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
sqlite3_result_int64(ctx, iRowid);
}else{
-float fCoord = nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1);
-sqlite3_result_double(ctx, fCoord);
+ConstraintType fCoord = nodeGetCoord(pRtree, pCsr->pNode,
pCsr->iCell, i-1);
+sqlite3_result_ConstraintType(ctx, fCoord);
}
return SQLITE_OK;
@@ -1009,7 +1032,7 @@
RtreeConstraint *p = &pCsr->aConstraint[ii];
p->op = idxStr[ii*2];
p->iCoord = idxStr[ii*2+1]-'a';
- p->rValue = sqlite3_value_double(argv[ii]);
+ p->rValue = sqlite3_value_ConstraintType(argv[ii]);
}
}
}
@@ -1157,8 +1180,8 @@
/*
** Return the N-dimensional volumn of the cell stored in *p.
*/
-static float cellArea(Rtree *pRtree, RtreeCell *p){
- float area = 1.0;
+static ConstraintType cellArea(Rtree *pRtree, RtreeCell *p){
+ ConstraintType area = 1.0;
int ii;
for(ii=0; ii<(pRtree->nDim*2); ii+=2){
area = area * (p->aCoord[ii+
Re: [sqlite] patch to allow integer rtree keys
how about actually attaching the patch? :) - Filip On Fri, Jul 11, 2008 at 9:23 PM, Steve Friedman <[EMAIL PROTECTED]> wrote: > I've just started using the rtree extension, and have found that the 32-bit > float for the range keys is not appropriate for me. Please find attached a > patch for rtree.c (based on v1.5) that allows for int -OR- unsigned int -OR- > float operation. > > Steve Friedman > > ___ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > > ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
[sqlite] patch to allow integer rtree keys
I've just started using the rtree extension, and have found that the 32-bit float for the range keys is not appropriate for me. Please find attached a patch for rtree.c (based on v1.5) that allows for int -OR- unsigned int -OR- float operation. Steve Friedman ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
