��������� ���������� ��� PostgreSQL � �������������� GiST
���������� ������� �������� ����������� ���������� ������ (GiST), ��� ���������� � ORDBMS PostgreSQL, ������ ��������� ���������������� ���������� � �������������� GiST.
��������
��� ���������� ����������� �������������� ������ ���������� ������ ������������� ��������������� ������, ��������� � ���������, �������� � ������� ����������. �������� ����������� ���������� � ������������������, ���������� � ������������ ����� ������, ����� ������ ������� ������������� ���������� ������� ���������� � ������������������ �������� ������ (abstract data type, ADT).����������� ������ � ������ �������� ����� �� ��������� ������� ���� ������. �� ������������� ������� ���� ������, ������� �� ���������� � ����������� ������. ��� ����� �� ������������� ������� � ������ ������������, � ��������, ����������� ��������� � �����, ������� �������� ������� ���� �������� ����������� ���� ���������. ������, ��� ����������� �������������� �������, ������� ������������ ����� ��������������� ��������� ������, ��������������� ��� ��������� ��������� ������ ��������������� ������������ ��������� ���������. ������ ��������� ��������� ���������� �������� �������� ����������� ��� ���������� ������ � �����. ������, ������ ������������ ����� ���� �� �����, �, ���� ���� ���� ���������� ����� �������, �� ����� ������������� �������������� ������ ��� ��������� ������ ������ �������. �������� ������� (access methods,AM), ������, �������� ����������� (���������) ���������� ����� � ������ ������ � ���. � ������������ ����������� ���� ��� ������ � ����������� �������, ������ ��� ������, �����, ������������ B+-tree � ���, ��� ������� ����������� ����� ����������� ��������� ������. ������, ����������� ����������, ����� ��� ��� (GIS), �������������� �������, CAD, �������� ����������, ������� ��-���� ���������� ����������� ������, ������� ������, ����� ����������� AM. ��������, � ��� ��������� ������ ������ �������� �����, �����, ��������. �� ��������� ���� ���� ����������� ������� (����� 70) ��������� ������������������ AM, ������ �� ���������� � ��������� ���� ������� � �������� ��������� ��-�� ���������� ���������������� AM � ����������� ���������������� ������ ����������, ��������������, ��������������� ���� ��� ������� AM. ������� ��������, ��� ��� ����� ��������� ������ ����� ����������������� �������������, �������� � ����� ����, � �����, ���������� � ��������������� ������������.
������ ��������� ����� AM ��� ������� ������ ���� ������, ����� ������������ [Sto86] ��������� ������������ ������������, ������ ��������� ���������, ����� ��� B+-tree � R-tree. ��� ���� ����� ���������� � ���� Postgres, ����������� � ������ � 80-� ����� (��. ������ � [B05]). ���� ������������� ����������� � ��������� ������� ���������� �������� ������� � ���������� �������, ������� � ���������� ��. ���, ��������, ���������� ���������� ��������� ���������, ����� ������������ B+-tree AM. �� ������� ���� ������ box ������������ �������, ��� B+-tree ����� ������������ ��� �������� AE (���������), AL (������) � AG (������). ������, ����� ������, �������� �� ���� �����������, ������ ���������, ��� ��� �������� �� ��� ������, ������� �������� � B+-tree, ������ ������������ ������� ����� ���, ������� ������������� B+tree. ������� �������, ���� ������ ����������� ������������� �����, �� �� �������� � ������� �������.
��� ����, ����� ���������� ��� �����������, Hellerstein et al. [HNP95] ���������� ��������� �������, ���������� GiST ( Generalized Search Tree, ���������� ��������� ������), ������� �������� ���������� �������������� R-tree � ������������� ����������� ������ ��������� �� ������ � ��� ���������� (����������� � �������� �����). ���� ��������, ��� ����� ������ AM ����� ����������� ��� �������� ����������, � ������� ������ �������� ����������� ��� ���� ������, ������������ � �������� ���� ��������. ����� �������, ����� ��������� ������ ����� ������� �������� ��� ���������� ������ AM, �� ���������� ������������ �����������. ��������, � B+-tree ������ �� ���������� ����� ������������ ���������, ������� ������ ����������� �� ����� � �������� ����� ���������������� ���������. GiST ������������� ��������� ������ � ����� ����� ������ � ������������ ����������� ����� ��������. ��� ��������� ������������� ���������� ��������� � ������� ������, �� ������ ����������-�������������� ���� ����. ����� �����, ��� ����� ADT ������������� ��������� ������������ ������ � �������������� ����� ����� (concurrency and recovery), ���������� ������� � ����, �������� ����� ������� �������, ��������������� ����� GiST.
������� ��������, ��� ������ ������� �������� ��� ���������� � ���� Postgres ��. ������������� � �. ���� [GBK] � ������������ ��� ������������ ���� (IDS/UDO Virtual Index Interface, DB2 UDB table functions, Oracle Extensible Indexing Interface) ��� ��� ���� ������� ���������� ���� � ���������� ���� ����������������� ����. ������, � ����� Postgres (PostgreSQL), GiST �� 2000 ���� ����������� �� ���������� � �� �������������. ����� ����, ��� ���������� �� ������������ ������������� ������� � �������������� ����� ����� �������, ��� ������ ��� ������������� � ������������ ��������.
������ ���� ������, ��� ������ ��� �������� "�������", ������ ������������ GiST � �������� ������������ ������ � ��� ����������. ���, ������ �������� ��������� ������ ���������� �����, ����������� ������ (multi-key), �������������� �������� ������� (������������� ������ ������������). ����� ����, ��� ������ 8.1 ������ �������� ��������� ������������� ������� � GiST �������� � �������������� ����� ����� �������, ��������� ���������������� ��������� �� ������ ��������� � ��. [KMH97], ��� ������������ ����� ��� �����������, �������� ������������� ��� � ������ ����������� �������� � ������ � ������������ �������. �������, ��� ������� ���������� �������, ���������� �� ���� GiST, ������������� "���������" ��� ��� �������������� ���� ��� ������-���� ��������� !
GiST ������������ ����� ���������������� (�� ������) ������, �������� ���� (������) �������� �������� ���� (key, rid), ��� key - ����, � rid - ��������� �� ��������������� ������ �� �������� ������. ���������� ���� �������� ���� (p,ptr), ��� p - ��� ����� �������� (������������ ��� ��������� ����), ������������� ��� *����* ��������� �����, � ptr - ��������� �� ������ ���� � ������. ��� ����� ������ ���������� ������� ������ SEARCH, INSERT, DELETE, � ��������� ��� ��������� ���������������� �������, �������� ����� ��������� ������� ���� (�������) �������.
����� SEARCH ����������� �������� Consistent, ������������ 'true', ���� ���� ������������� ���������, ����� INSERT - ��������� penalty, picksplit � union, ������� ��������� ������� ��������� �������� ������� � ����, ��������� ���� ��� ������������ � ����������� ������ ��� �������������, ����� DELETE ������� ���� ������, ���������� ����, ������� ���� (key, rid) �, ���� �����, � ������� ������� union ������������� ������������ ����.
����������� ��������� GiST
��� ����������� ������������ ������� ������������ � ���������� ������������� ���������������� ������� ��� PostgreSQL �� ����� C, ������� ��������� � ����������.
GiST ������������� ������������� ����� ����� ������ �������� ������ ��� ������ � ����: SEARCH, INSERT, DELETE. ��������� ����� �������� ����� � ������� 7 ������������ �������, ������� ����������� ������ ���������������.
����������� ������� ���������� �������� � �������, ������������� � ��������� ���������:
typedef struct GISTENTRY
{
Datum key; /* ���������� ���� */
Relation rel; /* ������ */
Page page; /* �������� ������� */
OffsetNumber offset; /* ��������� � ������� */
int bytes; /* ����� ����� � ������, ����� ���� ������ -1 */
bool leafkey; /* �������, �����������, ��� � key ��������� ��
����, � �������� �� ������� */
} GISTENTRY;
��� �������, ��� ������� ���������� ������������ ������� ���� key � leafkey.
����� ���������:
- �� ���� �� ������������ ������� �� ����� ����� ������� NULL
- ���� ��������, ����� penalty(�� ��������), ������� �� ���������� NULL ��� GISTENTRY � ��������� key NULL.
������������ �������
��� ��������� �������� � ����������� ������� ������������ ���������������, �������� ����������� ������ ��������������� �������� �����������. � ����������� ������ ��������������� ������ ���������� R-tree.
GISTENTRY * compress( GISTENTRY * in )
GISTENTRY * decompress( GISTENTRY * in )��� ������� �������� �� ����������/������������ ������. ���� ������� ������ �������� ����� (key), ��:
- ��� ������ ���������� ������ palloc'������� �������� ��� ���������, ��� � �����( ���� ���� ����������� �� ������, pass-by-reference).
- ����������� � ����� ��������� �������� rel, page, offset, leafkey.
- ��������� ���������� bytes.
- �� ������ ������ ��������� (in), � �� ������ pfree �� in, �� in->key
��� ������ compress in->leafkey=TRUE, ���� �������� � key ����� �� �������, � �� �� �������. � ���� ������, ���� ��� ������� ������������, ���� ���� �� �������� ����, ���� ����������� ���������� in->bytes � ���������� in->leafkey=FALSE.
���� ��������� ������������ �������� ����� ���������� ������ ����� ��������� ����� ������� decompress.
bool equal( Datum a, Datum b)
���������� TRUE ������ � ������ a==b.
-
float * penalty( GISTENTRY *origentry, GISTENTRY *newentry, float *result)
��������� ���� ���������� origentry->key ��� ��� ����������� � newentry->key. ����������� �������� ������ ��������� � *result � ������� ��������� �� ����.
���� ��� ������� �� �������� ��� isstrict, �� key ����� ���� NULL. � ��������� ������, ������� �� ���������� � ���������, ��� ���� ���������� ����� 0, ���� ���� �� ���� �� ���������� ����� �������� NULL.
-
Datum union(GistEntryVector *entryvec, int *size)
��������� ����������� (union) ������. ���������� ������������ ���� (�� GISTENTRY!). � *size �������� ������ ��������������� ����� � ������. ��������� GistEntryVector:
typedef struct { int32 n; /* ���������� ��������� � ���� vector*/ GISTENTRY vector[1]; } GistEntryVector;������ ������� �� �������� NULL ���������.
-
bool consistent( GISTENTRY *entry, Datum query, StrategyNumber strategy )��������� ���� (entry->key) �� ������������ ������� (query) � ������� �������� � ������� strategy � ���������� TRUE � ������ ������������, ��� FALSE � ���������.
���� ���� ��������� �� ���������� �������� ������, ������� ������ ���������� TRUE, ���� entry->key ����� ��������������� query � FALSE, ���� entry->key ����� �� ������������� query.
���� ���� ��������� �� �������� �������� (leaf page), �� ��������� ������������ ���������� RECHECK ��� ���������� �������� (��. CREATE OPERATOR CLASS). ���� ����� �������� RECHECK, �� ��� ��������, ��� ������ �������� �������� ("lossy"), �.�. ��������� ������ ��������� ��������� �� ������������ ������� (��������� consistent ���������� ��������� �� ���������� ��������� � ���� ������), � ��������� ������ ��������� ������� ������ �����.
������ GIST_LEAF(entry) ���������� TRUE, ���� ���� ��������� �� leaf ��������.
������, ����� �������� ����� strategy ������������� ����� � ������� ���������� SQL( �� ������� box_ops, ��������� ������ ������ "����������� ������������ �������" ):
select pg_amop.amopstrategy, pg_operator.oprname, pg_amop.amopreqcheck from pg_type, pg_operator, pg_opclass, pg_am, pg_amop where pg_type.typname = 'box' and pg_am.amname = 'gist' and pg_opclass.opcname = 'box_ops' and pg_am.oid=pg_opclass.opcamid and pg_opclass.oid = pg_amop.amopclaid and pg_opclass.opcintype = pg_type.oid and pg_amop.amopopr = pg_operator.oid;��������������, ��� �������� ������ opclass �/��� �������� ���� ������������ �� ���������� ��������� ������.
-
GIST_SPLITVEC * split(GistEntryVector *entryvec, GIST_SPLITVEC *v)��������� ������ ������ entryvec �� ���. ������ entryvec �� ����� ��������� NULL ��������.
��������� GIST_SPLITVEC:typedef struct GIST_SPLITVEC { OffsetNumber *spl_left; /* array of entries that go left */ int spl_nleft; /* size of this array */ Datum spl_ldatum; /* Union of keys in spl_left */ OffsetNumber *spl_right; /* array of entries that go right */ int spl_nright; /* size of the array */ Datum spl_rdatum; /* Union of keys in spl_right */ ... } GIST_SPLITVEC;��������� �������� ������� ���������� �����, ��� ������� �����, �� ��������� ���� �� ������ �� ���������.
v->spl_left � v->spl_right ������ ��������������(palloc) ��������������, ��� �������� ��� ������ ��������� ������ ��������� ������� entryvec. ��� ����, ���� ����� �� ����� ����������� � spl_left � spl_right ������������.
��������:
- �������� � ������� entryvec ���������� � 1, � �� � 0
- ������� ������� ���������� spl_ldatum � spl_rdatum - ������������ �����, ��������������, ��� ������ � ������� �������.
����������� ������������ �������
��������� ����������� ���������� � �� ������� �� ���������� ������ (���������� ������ SQL �������):- �������� ������ ���� ������ (���� ���������)
- ��������� ������� �������������� ���� � C-������ � �������:
_in,_out. ��������:CREATE FUNCTION ltree_in(cstring) RETURNS ltree AS '$libdir/ltree' LANGUAGE 'C' WITH (isstrict);
- �������� ���� � ������� CREATE TYPE.
CREATE TYPE ltree ( INTERNALLENGTH = -1, INPUT = ltree_in, OUTPUT = ltree_out, STORAGE = extended );
- ��������� ������� �������������� ���� � C-������ � �������:
- �������� ����� ���������� (���� ���������)
- �������� �������
(CREATE FUNCTION)
��� ������ ����������, ��������, ������� ��������� �����
��� ���������� ���������. ��������,
CREATE FUNCTION ltree_eq(ltree,ltree) RETURNS bool AS '$libdir/ltree' LANGUAGE 'C' WITH (isstrict,iscachable);
-
�������� ���������� � ������� CREATE OPERATOR.
��� ���� �������� ������������ ������ ����������, ������������ � SQL,
� ����������� ���������.
CREATE OPERATOR = ( LEFTARG = ltree, RIGHTARG = ltree, PROCEDURE = ltree_eq, COMMUTATOR = '=', NEGATOR = '<>', RESTRICT = eqsel, JOIN = eqjoinsel, SORT1 = '<', SORT2 = '<' );
- �������� �������
(CREATE FUNCTION)
��� ������ ����������, ��������, ������� ��������� �����
��� ���������� ���������. ��������,
- ����������� ������������ ������� GiST
- ������� ����� ��� ��� �������� � GiST, ���� ����������
(��� ����� ������������� ���� ��� ����� �������� � ������ ����������
�� ��������� ���� ������, ��������, � ������ tsearch2 �������
����� ��������
tsvector, � ��� �������� ������������ ���gtsvector, �������������� ��������� ���������. � ���� ������, ��� ������� � ������� ������ gevel ���������� �������� �������_out. - ������� ������������ ������� GiST.
��������, ��� ������
consistent:CREATE FUNCTION ltree_consistent(internal,internal,int2) RETURNS bool as '$libdir/ltree' language 'C';
- ������� ����� �������� ����� (opclass), ��.
CREATE OPERATOR CLASS,
��������, ��� ���� ������
box:CREATE OPERATOR CLASS gist_box_ops DEFAULT FOR TYPE box USING gist AS OPERATOR 1 << , OPERATOR 2 &< , OPERATOR 3 && , OPERATOR 4 &> , OPERATOR 5 >> , OPERATOR 6 ~= , OPERATOR 7 ~ , OPERATOR 8 @ , FUNCTION 1 gbox_consistent (internal, box, int4), FUNCTION 2 gbox_union (internal, internal), FUNCTION 3 gbox_compress (internal), FUNCTION 4 rtree_decompress (internal), FUNCTION 5 gbox_penalty (internal, internal, internal), FUNCTION 6 gbox_picksplit (internal, internal), FUNCTION 7 gbox_same (box, box, internal);�����, ����� FUNCTION ������������ � core GiST ��� ������������� ������������ �������. ����� OPERATOR ������ ��������� � ������� strategy � ������ consistent, ������� ������������ ��� ����������� ���� ��������. ������� �������, ��������� - ��� ���������� ����� ��������� ��� ������� opclass-�.
- ������� ����� ��� ��� �������� � GiST, ���� ����������
(��� ����� ������������� ���� ��� ����� �������� � ������ ����������
�� ��������� ���� ������, ��������, � ������ tsearch2 �������
����� ��������
contrib � ������������
PostgreSQL.
�����, ������ ������ ������������ Interfacing Extensions To Indexes.
������: R-Tree GiST ��� ���������������
��� �������� ������� �������� ����� ���������� ����� ������� ������, ���������������� ������� �����, ������� ���������� ���, ��� ��������� �������� � ���� ��� �������. ����� ������ �������� bounding volume � �� ������� ����� ������������ ��� �������� �� ��������� �������, ��������, �� ����������� ���� ��������. � �������� bounding volume ����� ���������� �����, ������� ��� ���. �� ����� ������������� ���, ������� �������� bounding box,��� BB.R-Tree - ��� ��������� ������, ������� ������������ ��� �������������� ����������� ������. ��� ���� ���������� ��������� [Gut84] ��� ���������� B-tree �� ����������� ������������, ������� ����������� �� ������������ ��������� � �������� ��������������� BB (�������������� ��� ���������� ������, � ������ 3-� ��������� - ������), ������ ���� R-Tree ����� ��������� ���������� ���������� �������, �� �� ������ ������� ������������� ���������. ������ ������ �� ���������� ����� �������� ������ �� �������� ���� � BB, ������� �������� ��� ������ ����� ��������� ����. ������ ������ ��������� ���� (leaf node) �������� ������ �� ������ � BB ���� ������. ��� ������� ����� ������ �������������, ����� ������� ������ ������ "������", � ����� �������� ����, � ���������, ��� ����������� � ������� ������� ����������� ���������� BB ����� ���� ����� �������. ��� ������ ������������ BB-� ������� � �������� ���� � ���� ��� �����������, �� ����������� �������� � ������ ����� ��������� ��� �� �����, ��� ������ ����������� ���������� ������������� ����� � ����������� ������� � ������������������.
R-tree ��� ��� ������� � �������� ������. ������ ����� � rtreeportal.org
compress, decompress- ������� ����������, ������ ���������� ��, ��� ��������.
Datum gist_box_compress(PG_FUNCTION_ARGS) { PG_RETURN_POINTER(PG_GETARG_POINTER(0)); } Datum gist_box_decompress(PG_FUNCTION_ARGS) { PG_RETURN_POINTER(PG_GETARG_POINTER(0)); } equal- ���������� ��� �������������� � ���������� true ���� ��� ����� ��� ��� ����� NULL
Datum gist_box_same(PG_FUNCTION_ARGS) { BOX *b1 = PG_GETARG_BOX_P(0); BOX *b2 = PG_GETARG_BOX_P(1); bool *result = (bool *) PG_GETARG_POINTER(2); if (b1 && b2) *result = DatumGetBool(DirectFunctionCall2(box_same, PointerGetDatum(b1), PointerGetDatum(b2))); else *result = (b1 == NULL && b2 == NULL) ? TRUE : FALSE; PG_RETURN_POINTER(result); }������, ��� ������������ ����� ���������� � PostgreSQL ������� box_same. ������� ����� �������� �������� �� ������ � ���������� result: ��� ������������ ������� �������� ����������� �� ������ � ������� ������ �������� �������� ������ ���������. �� ��� �� �������� ���� ������ ����������. penalty- ������� ���������� ��������� (����������) ������� �������������� ����� ����������� ����� (��������� bounding box) ��� ���� ���������.
static double size_box(Datum dbox) { /* ���������� ������� �������������� */ BOX *box = DatumGetBoxP(dbox); if (box == NULL || box->high.x <= box->low.x || box->high.y <= box->low.y) return 0.0; return (box->high.x - box->low.x) * (box->high.y - box->low.y); } Datum gist_box_penalty(PG_FUNCTION_ARGS) { /* �������� ������������� */ GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0); /* ����������� ������������� */ GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1); float *result = (float *) PG_GETARG_POINTER(2); Datum ud; /* �������� ������������ ������������� */ ud = DirectFunctionCall2(rt_box_union, origentry->key, newentry->key); /* �������� ������� ��������� �� ����������� �������������� */ *result = (float) (size_box(ud) - size_box(origentry->key)); PG_RETURN_POINTER(result); } union- ������� ���������� ������������ ������������� ��� ���� ��������
���������������
Datum gist_box_union(PG_FUNCTION_ARGS) { GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); int *sizep = (int *) PG_GETARG_POINTER(1); int numranges, i; BOX *cur, *pageunion; numranges = entryvec->n; /* ������������ �������� ������ ���� palloc'�������! */ pageunion = (BOX *) palloc(sizeof(BOX)); /* ��������� ������������� �������������� ������ ��������������� */ cur = DatumGetBoxP(entryvec->vector[0].key); memcpy((void *) pageunion, (void *) cur, sizeof(BOX)); for (i = 1; i < numranges; i++) { cur = DatumGetBoxP(entryvec->vector[i].key); if (pageunion->high.x < cur->high.x) pageunion->high.x = cur->high.x; if (pageunion->low.x > cur->low.x) pageunion->low.x = cur->low.x; if (pageunion->high.y < cur->high.y) pageunion->high.y = cur->high.y; if (pageunion->low.y > cur->low.y) pageunion->low.y = cur->low.y; } /* ������ ������������� �������� � ������ */ *sizep = sizeof(BOX); PG_RETURN_POINTER(pageunion); } consistent-
Datum gist_box_consistent(PG_FUNCTION_ARGS) { GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); BOX *query = PG_GETARG_BOX_P(1); StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); if (DatumGetBoxP(entry->key) == NULL || query == NULL) PG_RETURN_BOOL(FALSE); /* ���� �������� ��������� �� �������� ��������, �� ����������� ������ ���������, �� ���������� �� ������ ������� true ���� �������� �� ����������� ��������� (�����) ����� ������������� ������� */ if (GIST_LEAF(entry)) PG_RETURN_BOOL(gist_box_leaf_consistent(DatumGetBoxP(entry->key), query, strategy)); else PG_RETURN_BOOL(rtree_internal_consistent(DatumGetBoxP(entry->key), query, strategy)); }�������� ������� gist_box_leaf_consistent � rtree_internal_consistent �������� �������, ����������� �� ���������� ������ ��� ������ �� ����������.static bool gist_box_leaf_consistent(BOX *key, BOX *query, StrategyNumber strategy) { bool retval = FALSE; switch (strategy) { case RTSameStrategyNumber: retval = DatumGetBool(DirectFunctionCall2(box_same, PointerGetDatum(key), PointerGetDatum(query))); break; default: elog(NOTICE,"Unsupported StrategyNumber %d", strategy); } return retval; } static bool rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy) { bool retval=FALSE; switch (strategy) { case RTSameStrategyNumber: retval = DatumGetBool(DirectFunctionCall2(box_contain, PointerGetDatum(key), PointerGetDatum(query))); break; default: elog(NOTICE,"Unsupported StrategyNumber %d", strategy); } return retval; }�������� ��������, ��� � ������� gist_box_leaf_consistent ��������� ������������� ����������� �� ������ ���������� � ���������� ���������, � � rtree_internal_consistent ��������� ������������� ������ ��������� ����������� � ���������� ��������. ��������, ��� ���� ��������� ������������� �� ����������, �� ����������� � ��� ��������������� � ��������-����������� ������ �� ����� ����. picksplit- ������ ����� ������� ������� � ���������� GiST. ������ ������ ����� �����
� ���������� PostgreSQL, ���� ./src/backend/access/gist/gistproc.c ����� ������������ �������
������������� (������������) �������� ([Gut84]). ��� ������� �� �����
������������ ������� (�������������) ��������, ������� ��������
������ �������� � "�����" ������, � �������� - � "������".
Datum gist_box_picksplit(PG_FUNCTION_ARGS) { GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0); GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1); OffsetNumber i, maxoff = entryvec->n - 1; int nbytes; nbytes = (maxoff + 2) * sizeof(OffsetNumber); v->spl_left = (OffsetNumber *) palloc(nbytes); v->spl_right = (OffsetNumber *) palloc(nbytes); v->spl_ldatum = PointerGetDatum( palloc( sizeof(BOX) ) ); v->spl_rdatum = PointerGetDatum( palloc( sizeof(BOX) ) ); v->spl_nleft = 0; v->spl_nright = 0; for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) { BOX *pageunion; /* ��������� �� ������������ ������������� ��� �������� */ if ( i%2 == 0 ) { v->spl_left[ v->spl_nleft ] = i; v->spl_nleft++; pageunion = DatumGetBoxP( v->spl_ldatum ); } else { v->spl_right[ v->spl_nright ] = i; v->spl_nright++; pageunion = DatumGetBoxP( v->spl_rdatum ); } if ( i<=OffsetNumberNext( FirstOffsetNumber ) ) { /* �������������� ������������� ������������� �������������� */ memcpy( pageunion, DatumGetBoxP(entryvec->vector[i].key), sizeof(BOX) ); } else { BOX *curbox = DatumGetBoxP(entryvec->vector[i].key); if (pageunion->high.x < curbox->high.x) pageunion->high.x = curbox->high.x; if (pageunion->low.x > curbox->low.x) pageunion->low.x = curbox->low.x; if (pageunion->high.y < curbox->high.y) pageunion->high.y = curbox->high.y; if (pageunion->low.y > curbox->low.y) pageunion->low.y = curbox->low.y; } } PG_RETURN_POINTER(v); }
������: R-Tree GiST ��� ���������
��������� ������� ��� ��������� �������� ����� ��������������, ����������� ��������. ����� �������, ��� ������� �� �������� R-Tree ��� ��������������� ����������� ����� � ���� ��������. ����� ������ �������� "with lossy compression" (�������� ������) � ��� ��������, ��� ��� ������, ������� �� ������ ��� ������, ���������� ���������, �.�., �������� � �������� ���������, ���������� � �������.
compressDatum gist_poly_compress(PG_FUNCTION_ARGS) { GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); GISTENTRY *retval; if (entry->leafkey) { /* �������� entry->key �������� �������, �.�. ��� ����� �������� ��� ������� � ������ */ retval = palloc(sizeof(GISTENTRY)); if (DatumGetPointer(entry->key) != NULL) { POLYGON *in = DatumGetPolygonP(entry->key); BOX *r; r = (BOX *) palloc(sizeof(BOX)); memcpy((void *) r, (void *) &(in->boundbox), sizeof(BOX)); gistentryinit(*retval, PointerGetDatum(r), entry->rel, entry->page, entry->offset, sizeof(BOX), FALSE); } else { gistentryinit(*retval, (Datum) 0, entry->rel, entry->page, entry->offset, 0, FALSE); } } else retval = entry; PG_RETURN_POINTER(retval); }consistent- �������� ��������, ��� ������ ���������� rtree_internal_consistent, ���� ��� �������� �������. �.�. ������� ���������� TRUE ����� ���������, ������ ��������� ����� ���� �������.
Datum gist_poly_consistent(PG_FUNCTION_ARGS) { GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0); POLYGON *query = PG_GETARG_POLYGON_P(1); StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2); bool result; if (DatumGetBoxP(entry->key) == NULL || query == NULL) PG_RETURN_BOOL(FALSE); result = rtree_internal_consistent(DatumGetBoxP(entry->key), &(query->boundbox), strategy); PG_FREE_IF_COPY(query, 1); PG_RETURN_BOOL(result); }
������� ������������� GiST
��� ����, ����� ������������ ������ � ����� ��, ���������� ���������� ������, ��������� ���������� � ���� ��. ��������� ������ ������ ����������� � ������������������ ������ (�� ������� tsearch2):
cd contrib/tsearch2 make && make install && make installcheck���� ��� ������ ��������� (��� ����� ������), �� ����� ��������� ���������� � ���� ��, ��������:
psql foodb < /usr/local/pgsql/share/contrib/tsearch2.sql����� ����� �� ������ ������������ ����� ���� ������, ��������������� �������, ��������, ��������� � CREATE OPERATOR CLASS � �������. ��������, ��� ������ tsearch2:
create table fts ( id integer, title text, body text, ftsindex tsvector); create index fts_idx on fts using gist(ftsindex);����� ������� ftsindex � ������� fts ����� ��� tsvector, ������� � ��� ������������ ������� tsearch2. �������� �������� �� �������� ������ (gist), ������� ������������ ��� ���������� �������. ������, ����� ������� �������� opclass ��� ������, ���� ��������� ������������ �������� �������� �� ��������� ��� ������� ���� �������. ��������, ��� ������ contrib/intarray ����� ������� opclass gist__intbig_ops ��� ����������� ������ � �������� ���������, � �� ����� ��� �� ��������� ������������ gist__int_ops, ����������� ��� ������ � ���������� ���������. ������� ����� gist__intbig_ops � gist__int_ops ����������� � ���, ��� ������ opclass ���������� ����������� ������������� ������� ������� ���������� ( superimposed signature ) ������ 4096 ��� � ������� ������ �������� "lossy", � �� ����� ��� �� ������ ������ ������ �������� ������ � �� ������� �������� ��������� ������� �� ������������ �������.
-- default opclass, could be omitted CREATE INDEX message_rdtree_idx on message using gist ( sections gist__int_ops); -- opclass for large arrays CREATE INDEX message_rdtree_idx on message using gist ( sections gist__intbig_ops);����� �������� ��. ������������ CREATE INDEX
��������� GiST, �������� ���� ����������� ��� ���������� ����������, ������� ������ � ����������� PostgreSQL. ��� ������ ��������� ���� ������, ���������������� ��� ���������� ������, ���������, ��������� ������ � ���� � ������������������ �������. ���� ���������� ����� ������� ����� ������������� ���� ����������. ���������� �������� ���������� � ������������ � ������, � ������� ������������� ����� ����� � ������� ������� �������� PostgreSQL � c ������� ��������� ������ www.pgsql.ru.
- tsearch2 - ���������� ��������������� ������
-
���� ������ ������������ ��� ����������� ��������������� ������ � ��. ��� ������������� ������������ �������� online-������ � ������ ���������� � ��, ��� ���� ����������� ��������� �������������� ����� � ������������� �� ���������. ��������, ������ �� ����������, � ����������� �� ������ ������� ������� � ���� ����������. Tsearch2 ������������ ������������� ��������, ������������� API ��� �� ��������. ��������� �������� ���������� �������� ispell (��� ���������� ���� � �� ���������� �����) � ��������� �� ������ snowball ��������� ������������ tsearch2 �� ������� �������. �������� ��������� tsearch2, ������������ �������� �������� � ���� ������ � �������� � ������� ����������� ������ SQL, ��������� ������������� ��������� ������ ��������������� �� ������ ������. ������ ������������� ��� ���� ����������� �������, ������������ ������������ ����������, � ������� ����� ������������ ��� ���������� ����������� ������ �� �� ������������� �������.
� ������� tsearch2 �������������� ����� ���������� ������� � �������� �������. ������ ������ ����������, ������� �������� ����� '������', '��', '����':
SELECT mid, title from messages where ftsindex @@ to_tsquery('������ & �� & ����');����������, �� ������ 10 ����� ����������� ������� ����������:SELECT mid, title, rank(ftsindex,to_tsquery('������ & �� & ����')) as rank from messages where ftsindex @@ to_tsquery('������ & �� & ����') ORDER BY rank DESC LIMIT 10;������ ������������ ������������� ���������, �.�. ������ �� ������ ������ ��������� (����� ����� ������������ 4 �����) ����� �������� ������ ����. ���, ��������, ��� �����, ��������� � �������� ���������, ����� ���������, �� ��������� � ������� �������. �����, ����� ������������ ����� �� ��������� ������ ����������, ��������� ���� � ��� �� ������. � ������� ����, ���� ftsindex �������� ���� title � ���� ���������.
UPDATE messages SET ftsindex=setweight( to_tsvector(title), 'A' ) || to_tsvector(body);
����� �������� ������ �� ��������� ����������:SELECT mid, title FROM messages WHERE ftsindex @@ to_tsquery('������:a & �� & ����');��� ������������ ����������� ������ ������ ������������� ������� headline, ������� ������ ����������� ����� ��������� � ���������� ���� �� �������.
SELECT mid, headline(body, to_tsquery('������ & �� & ����')), rank(fts_index,to_tsquery('������ & �� & ����')) AS rank FROM messages WHERE ftsindex @@ to_tsquery('������ & �� & ����') ORDER BY rank DESC LIMIT 10;�������, ��� � ���� �������, ������� headline ���������� ��� ������� ���������� ���������, ��� ����� ����������� ������ �� ����� ���������� �������. ��� ������� � ��� ��� � PostgreSQL ���������� LIMIT. ���������������� ������ � �������������� ���������� (subselect) �������� ��������� �������:SELECT mid, headline(body, to_tsquery('������ & �� & ����')) FROM (SELECT mid, body, rank(fts_index,to_tsquery('������ & �� & ����')) AS rank FROM messages WHERE ftsindex @@ to_tsquery('������ & �� & ����') ORDER BY rank DESC LIMIT 10) AS foo;����� ������� headline ���������� ������ ������ (�������� 10) ���������� ���. - ltree - ��������� ������ � ����������� ����������
-
����������� ������ ������ � �������������� �������, ��������, � ����������, ����������� � ������������� ������ ������ (parent_id,child_id), ��� �������� ,��� ��� �����, � ������������� ������������� ����������� ��������. ���� ������ ltree ������� � ���, ����� ������� �������� ������ � ����������� ���� ������
ltree� ������������� ��������� ��������� ��� �������� ��������. ��������, ��� ������ ������������ �� �������TOP / | \ Science Hobbies Collections / | \ Astronomy Amateurs_Astronomy Pictures / \ | Astrophysics Cosmology Astronomy / | \ Galaxies Stars Astronauts������ �� ������ ���� ��������, ��������, ���� 'Top.Science' ��������:SELECT path FROM test WHERE path <@ 'Top.Science'; path ------------------------------------ Top.Science Top.Science.Astronomy Top.Science.Astronomy.Astrophysics Top.Science.Astronomy.Cosmology����� ������ �� �������, ltree ������������� ����������� ������ � �������������� ���������� ��������� � �������������. ��������, ������Top.*{0,2}.sport*@.!football|tennis.Russ*|Spain a) b) c) d) e)��������, ��� ���� ������:- a) - ���������� � ���� � ������ 'Top'
- b) - ������ ����� ���� ������ �� 2-� ����� � ������������ ������
- c) - ����� ���� ���� ���� � ������ ������������ �� 'sport' (��������� � ������� ����� �� �����������)
- d) - ����� ���� ����, ��� �������� �� ������ ��������� 'footbal' ��� 'tennis'
- e) - � ��������� �� ����, ������������ 'Russ' ��� 'Spain' (��������� � ������� ����� ����������)
SELECT path FROM test WHERE path ~ '*.!pictures@.*.Astronomy.*'; path ------------------------------------ Top.Science.Astronomy Top.Science.Astronomy.Astrophysics Top.Science.Astronomy.Cosmology�����, ����� ������������ ����� �� ��������� �����, ��������, ����� ��� ����, ������� ��������� ����� 'Europe', �����, ������������ � 'Russia' (case insensitive), � �� ���������� ����� 'Transportation':'Europe & Russia*@ & !Transportation'
������:SELECT path FROM test WHERE path @ 'Astro*% & !pictures@'; path ------------------------------------ Top.Science.Astronomy Top.Science.Astronomy.Astrophysics Top.Science.Astronomy.Cosmology Top.Hobbies.Amateurs_Astronomy�������� ������������� ����� ������ � ������� ���������� �������� ������� ������ ltree ����� �������� ��� ������� �������� ���������� �����. - intarray - ��������� ��������� ������������� ��������
-
���� ������ ����� ������������ � ��� �������, ����� ��������� ��������������� �� ��� ��������� ������������������. ��������, �������� ������ ������ ���������� �� ���������� ��������. ������������ ��������������� ����� ��������������� ������������� ���� ������ - messages, sections � message_section_map. �������� ����� ������������ ���������� �������, ��� ��� ������� message_section_map �������� ����� ������-��-������. ��� ����, ����� ���� ���������� �� ������ 1,2 ����� ��������� ������ (join) ���� ������ messages � message_section_map, ��� ������ �� ������������������ � � ��������� ������� ������ �����������. �������������� �������� � ����, ��� � ������� messages ����������� ���� sections ������� �������� �������� ����� ����� - ��������������� ������, � ������� ����������� ������ ��������. ������, �������� �� ��, ��� ������ �� ��������� ������ �������, ����� ����� ��� ����� ��������� ��-�� ����, ��� �������� ����� � ������� �� ���������� ������. ��� ������ intarray ��� ��� � ������ ��� �������� - �� ������������ ��������� ��������� ��� �������� ��� �������������� ���������.
CREATE TABLE message (mid int not null,sections int[]); -- select some messages with section in 1 OR 2 - OVERLAP operator SELECT message.mid FROM messages WHERE messages.sections && '{1,2}'; -- select messages contains in sections 1 AND 2 - CONTAINS operator SELECT message.mid FROM messages WHERE messages.sections @ '{1,2}'; -- the same, CONTAINED operator SELECT message.mid FROM messages WHERE '{1,2}' ~ messages.sections;������ ���������� ������ ������������� �������� - ��� ���������� ���������������� ������� ��� ������ � ����������� ����������, �.�. ��� ������� ���� ������� ���� �� ���� �� ����� ������ (������ ������� Achilleus Mantzios).CREATE TABLE tree( id integer PRIMARY KEY, name text not null, parents integer[] ) CREATE INDEX tree_parents on tree using gist (parents gist__int_ops); INSERT INTO tree VALUES (1,'root',null); INSERT INTO tree VALUES (2,'kid1',intset(1)); INSERT INTO tree VALUES (3,'kid2',intset(1)); INSERT INTO tree VALUES (4,'kid1.1',intset(2)+'{1}'::int4[]); INSERT INTO tree VALUES (5,'kid1.2',intset(2)+'{1}'::int4[]);����� ������� intset ����������� integer � ������� �������, � �������� '+' ��������� ��� �������. ������ �� ����� ������ ���������� ����:(1,root,null) / \ / \ / \ (2,kid1,'{1}') (3,kid2,'{1}') / \ / \ / \ (4,kid1.1,'{2,1}') (5,kid1.2,'{2,1}')������ �� ����� ����� ������ �������� ���� id=1 (root)SELECT * FROM tree WHERE intset(1) ~ parents and icount(parents)=1;
������� icount ���� ���������� ��������� � ������� ��� "�������" ���� � ����� �������. ����� ����� ���� �������� ���� id:SELECT * FROM tree WHERE intset(
) ~ parents; - pg_trgm - ����� ������� ����� �� ������ �������
-
���� ������ �� ������ ��������� ������ �������� ������� ������, �� ���
� �� ������� �� �����, ��� ��� ���������� ������ ���������� ������������
��������. ��������� - ��� ������������������ �� ���� �������� ����.
��������, ����� '������' �������� ��������� '���', '���', '���', '���'.
��������� pg_trgm, ����� ����� ��� �����, ������������� �� ��������� ����� '������':
CREATE INDEX trgm_idx ON foo USING gist (word gist_trgm_ops); SELECT word, similarity(word, '������') AS sml FROM foo WHERE word % '������' ORDER BY sml DESC, word;��� ����, ����� �������������� ������trgm_idx, ����������� �� ���� word, ��� ������������ ������� ������������������ ���� ��� �������� ���������� ����.���� ������ ����� ������������ ������ � tsearch2 ��� ��������������� ������ � ���������� ������ �����.
- rtree_gist - ���������� R-tree � �������������� GiST
-
���� ������ ��������� ���������� �������� � ������� � ����������������� ����������. ������� � 8.1 ���� ������ ������������ � ���� PostgreSQL.
- btree_gist - ���������� B-tree � �������������� GiST
-
������ ������������ ������������ ��� �������� ���� ������, ������������ � PostgreSQL � ��������������� �������� �� �����, ��� ��� ���������� btree ������� �����. btree_gist ����������� ��� �������� ����������� ��������, ��� ��� PostgreSQL �� ������������ ����������� �������, ��������� � ������� AM, ��������, gist � btree. �������� �������� ������������� �������� �������� ������� �� (ftsindex, ts), ��� ftsindex - ������� ���� tsvector, � ts - timestamp. ����� ������ ����� ������������ �� ������ ��� �������� ��������������� ������, �� � ��� ��� ��������� ������ � ������������ ��������� ���������.
CREATE INDEX fts_ts_idx ON foo USING gist(ftsindex,ts);
�����, �� ���� ts ����� ������������� �������������� ������ ������ btree_gist, � �� btree. - gevel - ����� ������� ��� �������� GiST �������
-
���� ������ ������������ � ������ ������� ��� ������������� ���������� � �������������� GiST. �� ����� ������������ ������ rtree_gist � ������, ������� �������������� ��� ��������� ���� ��������. � ����:
create table cities (id int4, b box); \copy cities from 'cities_mbr.copy' with delimiter as '|' rtree=# \d bix Index "public.bix" Column | Type --------+------ b | box gist, for table "public.cities"
�������� ���������� �� �������:rtree=# select gist_stat('bix'); Number of levels: 2 Number of pages: 64 Number of leaf pages: 63 Number of tuples: 6782 Number of leaf tuples: 6719 Total size of tuples: 298408 bytes Total size of leaf tuples: 295636 bytes Total size of index: 524288 bytes������� ���������� � ������, ������ �� ������ MAXLEVEL -gist_tree(INDEXNAME,MAXLEVEL)regression=# select gist_tree('pix',0); 0(l:0) blk: 0 numTuple: 29 free: 6888b(15.63%)����� (����� �������):- 0 - page number
- (l:0) - tree level
- blk: 0 - block number
- numTuple: 29 - the number of tuples
- free: 6888b - free space in bytes
- (15.63%) - occupied space in percents
gist_print(INDEXNAME). ��������, ��� ������������ ��������� �� ������ 1, �� ���������� ����� � ����:\pset tuples_only \o cities-l-1.leaf -- ��� ������ PostgreSQL < 8.1 SELECT * FROM gist_print('bix') AS t(level int, a box) WHERE level = 1; -- ��� ������ PostgreSQL ������� � 8.1 SELECT * FROM gist_print('bix') AS t(level int, valid bool, a box) WHERE level =1;�������� �������� �� ������� � �������� ! ����������, ����� �������� ������ ��� �������� ����� (������� 2). ���������� ������ �������������� ��� ��������� ������� ������.��������: �������
gist_print(INDEXNAME)����� ������������ ������ ��� �������� � �������, ������� ����� ��������� �������������. ��� ����� ���������� �������� ������� type_out��� ���������������� ���� �������, ��������, tsvector_out ��� ��������������� ����tsvector�� ������ tsearch2. �������box_out���������� �./backend/utils/adt/geo_ops.c� ��� ������� �������� �� �����:/* box_out - convert a box to external form */ Datum box_out(PG_FUNCTION_ARGS) { BOX *box = PG_GETARG_BOX_P(0); PG_RETURN_CSTRING(path_encode(-1, 2, &(box->high))); }
������ ������ ���������� � ������������ ����� ��������� �� ��������
������������� GiST.
����������� � TODO
�������� �� ������������ �������� � �������� GiST, ���������� ���������
����������� � ������� ���������� (� ��������, �� �����������),
������� �� ��������� � ������� �����.
- �������� NULL - ����������� ������ ��� ������������� ������.
������������ ��������� GiST ��������� ������������� NULL, ��� ��� ����
���������, ����� ������� ���������� �������� ��� ��������.
- ��������� ���������� ��������
- ��������� ������������� ������ (ordered domains) - ������������� ������
� ������� ��� ����������� �������� ������ � ��������� ������������������.
����� ����, ������������ ��������� GiST [HNP95] �������
�����������, ��. ������ �������� [Kor99] � ���� [Aok98], ����������� ���
��� ��������� ����� �������� ������ ������ � ��������, ��� � ��� ���������
������������������ ���������� ������. ��������, ������������ �������� ������
� GiST
���������� ��������� ������ � ������� (depth-first), ��� ������ ������������
������������� �������� ���� "��������", "������������", �� �� ������������
������� ���� "�������", ��� �������� ���� [Aok98], ������� � ���������
���������� GiST ��� ��������� ���������������� ��������� ������,
��������, ������ � ������ (breadth-first) ��� SS-tree (similarity tree),
������� ������������ � ������� ������������� ������.
������� ��������
SP-GiST - ����������
GiST ���������� ��� ��������� ������������ ���� ��������, ������������ �
GIS, CAD/CAM, �������� �������� (tries).
Mohamed Eltabakh
�������� ��� ����������� SP-GiST � ���� ������ ��� PostgreSQL.
�������� �� ��, ��� ��������� ���������� GiST �������� "�������" ���������,
���������� ������� ��� �������� � �������� �����������
������������ ���������, ������� �������� � ����� ������� ��������
"�������������" � ������������������ GiST, � � ������ - ��������� ��������
���������� ���������� ([Kor99], ��������, ���������� ������������ 11 ������������
�������, � [Aok98] - 13, ������ 7).
��� ��������� ��������� ����� ���������� �� ��������� �������� ���������
������ � core GiST, ������� ����� ������������ �� ���������:
picksplit, ����������� ������������� ��������. �������� ��������,
��� �� ������ ������� ���� �������� ���������� ������������������ ����������.
-
R-tree ��������� ��� GiST ����� ���� ������� ��� �������� ��������
opclass'�� �������� 2-D R-tree: ������� ��� n-��������� ��������, ���������
���� �������������� �������� (��. ����������).
����������
����������� ���������� ���������������� ����������, ������� ��������������
��� ���������� ������, �������� ������������ ������������ ����� �����������
ORDBMS.
���������� ��������� ������ (GiST), ������� ������ � ���� PostgreSQL,
���� ����������� ������������ � ���������� ������� ������ ���������
������������������ ���� ������ � ������������ ��������� ������ � ��� �� ������
���������� � ������� ��� ������. ��� ����, ���������������� ����������
����� �������� ���� ����������� ������������ ������, ������������� ��
ORDMBS, � ������������ ������������ ������ � ������.
�������������
������ ���������� ���������� ���� ��������������� ������������
(����) �� ��������� ������� 03-07-90187-�,
05-07-90225-� � �������� ������-����
�� ����������� ��������� ����� ����� �� PostgreSQL.
������
- www.postgresql.org - ������ ������� PostgreSQL
- [B05] ���� ��������, ��� ����� PostgreSQL? - �������� ������ (�� �������) � PostgreSQL
- www.pgsql.ru - ����� �� PostgreSQL ��������
- [GBK] The GiST Indexing Project at Berkeley
- PostgreSQL GiST development page
- [Sto86] Michael Stonebraker. "Inclusion of new types in relational database systems.",
In Proceedings of the 4th IEEE International Conference on Data Engineering, pp. 262-269,
Washington, D.C., 1986
- [HNP95] J. M. Hellerstein, J. F. Naughton, and Avi Pfeffer.
"Generalized search trees for database systems."
In Proceedings of the 21st International Conference on Very Large Data Bases, Zurich, Switzerland, 1995.
-
[Gut84] Antonin Guttman. "R-trees: a dynamic index structure for spatial searching."
In ACM SIGMOD International Conference on Management of Data, pp. 47-54, 1984.
- [Aok98] P.Aoki."Generalized 'Search' in Generalized Search Trees."
In Proc. of the 14th Int. Conf. on Data Engineering, Orlando, USA, pp.380-389,1998.
- [KMH97] Marcel Kornacker, C. Mohan, Joseph M. Hellerstein.
"Concurrency and Recovery in Generalized Search Trees."
SIGMOD Conference 1997, pp. 62-72.
- [Kor99] Marcel Kornacker. "High-Performance Extensible Indexing."
VLDB 1999, pp. 699-708.
������
���� �������� � ����� ������
�������� ������� PostgreSQL Global Development Group (���������
� �������� GiST � PostgreSQL) � �������� �������������-��������� ������� ��
PostgreSQL ��������.
��� �������� �������� ������ ����
���������� ���������� PostgreSQL, � ��� �����, ������ ��������������� ������
tsearch2, ��������� ������������� ����� ������ ltree,
������ � �������������� ��������� intarray. ����� ��������� ����������
�������� �� �������� PostgreSQL GiST development.
����� ��������� �� ���������������� �� � ��� PostgreSQL
��� ��������� �������� �� �������� ����������� ��������� ����������������
������� �� ����� C ��� PostgreSQL, ������ �������� ����� ����� � �������
C-Language Functions
������������.
������� ������ ������������ ��������� ������ 1, ������ 0 deprecated, ���� ���� � ��������������.
- �� ������ � PostgreSQL ��������� � �������� ������ ������
��� SQL-������ � ������������� �-���� Datum.
Datum ����� ������, ������ ������� ��������� �� ������ �����������
(PostgreSQL �� ������������ ����������� � ����������, ������� 32 ���). SQL-���� � PostgreSQL ������� ��
������������ �� �������� � �� ���������.
������������ �� �������� ���� �� ������ ��������� ������ 32 ����.
������������ �� ��������� ���� �������������� �� ���� � ������������� ������ � ����������.
��� ����� � ���������� ������ ������ ����� ������ ������ ���� ����� �������� int4
(� ������, � ������ ������� ���� �����).
��� �������������� Datum � ��� � ������� ���������� ����� ��������,
��.,��������, ����� postgres.h, fmgr.h:
-
int32 i = DatumGetInt32(datum);
-
Datum datum = BoolGetDatum( true );
-
text *sometext = DatumGetTextP( datum );
- ��� ������������ ����, ������������� �� ���������, ����� ������������
�������������� � ���������:
-
SOMETYPE *ptr = (SOMETYPE*)DatumGetPointer(datum);
-
Datum datum = PointerGetDatum( ptr );
- ������� �������� ����� � ���������� ������ ����� "���������", �� ���� ����������
���������� ��������� (TOAST - The Oversized Attribute Storage Technique,
���������).
������� ��� ���������� ����� ��������� ��� �����������, ��� user-defined ��� ������ ����������� ���������������:
SOMETYPE *ptr = (SOMETYPE*)PG_DETOAST_DATUM( DatumGetPointer(datum) );
- ��� ������ � ������ ���������� ����� ���� �������������� �������:
VARSIZE( ptr ) - ������ � ������
VARDATA( ptr ) - ���������� ��������� �� ������ ����� ���� �����.
�.�., ���� ��� ���� ���������� ���������:
typedef struct {
int32 length;
char data[1];
} FOO;
FOO *foo = f();
�� f->length == VARSIZE(f) � f->data == (char*)VARDATA(f) ������. �������,
��� ����� ���� �� ����� ��������� 1Gb. ��� ���� � ���� ����� ������������ PostgreSQL � ����� �����.
- ������� ������ ���������� ��� Datum � ����������� ���:
PG_FUNCTION_INFO_V1(function);
Datum function(PG_FUNCTION_ARGS);
- �������� ���������� ���������� ������� � ������������ ��������
����������� ����������� ��������. ���������� ����� ��������� ��������
���������� �������.
Datum
function(PG_FUNCTION_ARGS) {
/* ����� �����, ���������� �� �������� */
int32 i = PG_GETARG_INT32(0);
/* ��������� �� ������������� */
BOX *b = PG_GETARG_BOX_P(1);
/* ��������� �� ����� */
text *t = PG_GETARG_TEXT_P(2);
/* ���������������� ��� � ���������� ������ */
FOO *f = (FOO*)DatumGetPointer(PG_DETOAST_DATUM(PG_GETARG_DATUM(3));
....
/*
* ����� ����, ��� ������ �����������, �� ����� �� �������� ������
* "�����������" ��������, ���������:
* ������ - ��� ����������-��������� �������,
* ������ - ���������� �����
*/
PG_FREE_IF_COPY(t,2);
PG_FREE_IF_COPY(f,3);
PG_RETURN_INT32( i );
}
- �������� ��������� ������ �������� ����� ����������.
��� ������� �� ��������� � ��������� ����������� ��������, �������� � �������� penalty, equal, union � picksplit ���������� � GiST.
- ��� ���������� ������������ ������� ������ �������������� PostgreSQL-��������� palloc/repalloc/pfree.
�� �������������, ��� �������, ������������ �� ������ ������, �������, � ��������� �������
(���� PostgreSQL ��������� � ������� --enable-debug � --enable-cassert)
- ������ ��� �����, ������������ �� ��������� � ��������������� ������-���� SQL-����, ������ ���� ��������������� ������� palloc.