[postgis-devel] PATCH: New positional operators based on Y position of bounding boxes

[Mark Cave-Ayland]

Hi strk,
 
> -----Original Message-----
> From: strk at refractions.net [mailto:strk at refractions.net] 
> Sent: 11 January 2005 15:17
> To: Mark Cave-Ayland
> Cc: 'PostGIS Development Discussion'
> Subject: Re: [postgis-devel] PATCH: New positional operators 
> based on Y position of bounding boxes

(cut)

> 
> Thanks. I've deleted lwgeom/lwgeom.sql.in from the 
> repository. It is no more maintained nor used since a long 
> time (I'm sorry 
> you lost time modifying it as well).

OK, I wasn't sure if it was some sort of low-level testing script so I
updated it anyway :)

> I'm really sorry about it, but - yes - it's true.
> We should remove all 71 special handling around.

I think it would be good to do this sort of housekeeping as we go along, as
it will help keep the code a bit tidier and more understandable.

> Added SRID checks.

Thanks :)
 
> Sounds hard to me... how can you binary search a space with 
> unknown boundaries ? Anyway, now that you make me think about 
> this I implemented btree index on geometry for use in ORDER 
> BY and GROUP BY. geom1 < geom2 if geom1.bbox.xmin < 
> geom2.bbox.xmax and consequently other geoms too... I think 
> it would be easier that way (but you need to build a btree index).

Well, I've been working on some code that opens the GiST index relation
directly and reads in the root node to calculate the extents of the root
node. Of course this does not reflect the true extents since we do not know
the visibility of each of the index entries without reading the tuples
themselves; however it is a very good starting point. Here is the code that
I have experimenting with (add to the end of lwgeom_gist.c):


mca1=# select index_extent('t1_idx');
 index_extent
--------------
 BOX(0 0,0 2)
(1 row)


// Index extent function

static char
*t2c(text* in) {
        char *out=palloc( VARSIZE(in) );
        memcpy(out, VARDATA(in), VARSIZE(in)-VARHDRSZ);
        out[ VARSIZE(in)-VARHDRSZ ] ='\0';
        return out;
}

/*


index_extent takes one parameter: the name of the GiST index as a string


CREATE OR REPLACE FUNCTION index_extent(text)
        RETURNS box2d
        AS '$libdir/liblwgeom.so.1.0','index_extent'
        LANGUAGE 'C' WITH (isstrict,iscachable);

*/
//

#include "access/genam.h"
#include "storage/lmgr.h"
#include "utils/builtins.h"
#include "catalog/namespace.h"

Datum index_extent(PG_FUNCTION_ARGS);
PG_FUNCTION_INFO_V1(index_extent);
Datum index_extent(PG_FUNCTION_ARGS)
{
	text	*name=PG_GETARG_TEXT_P(0);
	char *relname=t2c(name);
	List       *relname_list;
	RangeVar   *relvar;
	Relation        index;	
	Buffer		buffer;
	Page		page;
	ItemId		iid;
	BOX2DFLOAT4 *item, *extent;
	OffsetNumber i, maxoff;	
	

	// Open the passed index
	relname_list = stringToQualifiedNameList(relname, "postgis");
	relvar = makeRangeVarFromNameList(relname_list);
	index = index_openrv(relvar);
	PG_FREE_IF_COPY(name,0);
	LockRelation(index, AccessExclusiveLock);

	// Read the root node of the GiST index, maxoff is the number of
entries
	// in the root node
	buffer = ReadBuffer(index, GISTP_ROOT);
	page = (Page) BufferGetPage(buffer);
	maxoff = PageGetMaxOffsetNumber(page);

	// Cycle through each of the entries in the root node
	extent = palloc0(sizeof(BOX2DFLOAT4));
	for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
	{
		iid = PageGetItemId(page, i);
		item = (BOX2DFLOAT4 *) PageGetItem(page, iid);
	
		// Store the largest extents to represent the bounding box
of the root node
		if (item->xmin < extent->xmin)
			extent->xmin = item->xmin;
		if (item->xmax > extent->xmax)
			extent->xmax = item->xmax;
		if (item->ymin < extent->ymin)
			extent->ymin = item->ymin;
		if (item->ymax > extent->ymax)
			extent->ymax = item->ymax;
	}

	// Close the passed index
	UnlockRelation(index, AccessExclusiveLock);

	ReleaseBuffer(buffer);
	index_close(index);
	pfree(relname);

	// Return the final extent as a BOX2D
	return PointerGetDatum(extent);
}


I'm not sure whether we can use the btree operator class to quickly return
the extents as at the moment I believe the difference metric is area?
However, this is really just me experimenting to see whether we can maximise
the information from the GiST index to calculate the extent more quickly :)


Kind regards,

Mark.

------------------------
WebBased Ltd
South West Technology Centre
Tamar Science Park
Plymouth
PL6 8BT 

T: +44 (0)1752 791021
F: +44 (0)1752 791023
W: http://www.webbased.co.uk