��������� ���������� ��� 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.

����� ���������:

  1. �� ���� �� ������������ ������� �� ����� ����� ������� NULL
  2. ���� ��������, ����� penalty(�� ��������), ������� �� ���������� NULL ��� GISTENTRY � ��������� key NULL.

������������ �������

��� ��������� �������� � ����������� ������� ������������ ���������������, �������� ����������� ������ ��������������� �������� �����������. � ����������� ������ ��������������� ������ ���������� R-tree.

  1. GISTENTRY * compress( GISTENTRY * in )
    GISTENTRY * decompress( GISTENTRY * in )

    ��� ������� �������� �� ����������/������������ ������. ���� ������� ������ �������� ����� (key), ��:

    1. ��� ������ ���������� ������ palloc'������� �������� ��� ���������, ��� � �����( ���� ���� ����������� �� ������, pass-by-reference).
    2. ����������� � ����� ��������� �������� rel, page, offset, leafkey.
    3. ��������� ���������� bytes.
    4. �� ������ ������ ��������� (in), � �� ������ pfree �� in, �� in->key

    ��� ������ compress in->leafkey=TRUE, ���� �������� � key ����� �� �������, � �� �� �������. � ���� ������, ���� ��� ������� ������������, ���� ���� �� �������� ����, ���� ����������� ���������� in->bytes � ���������� in->leafkey=FALSE.

    ���� ��������� ������������ �������� ����� ���������� ������ ����� ��������� ����� ������� decompress.

  2. bool equal( Datum a, Datum b)

    ���������� TRUE ������ � ������ a==b.

  3. float * penalty( GISTENTRY *origentry, GISTENTRY *newentry, float *result)

    ��������� ���� ���������� origentry->key ��� ��� ����������� � newentry->key. ����������� �������� ������ ��������� � *result � ������� ��������� �� ����.

    ���� ��� ������� �� �������� ��� isstrict, �� key ����� ���� NULL. � ��������� ������, ������� �� ���������� � ���������, ��� ���� ���������� ����� 0, ���� ���� �� ���� �� ���������� ����� �������� NULL.

  4. Datum union(GistEntryVector *entryvec, int *size)

    ��������� ����������� (union) ������. ���������� ������������ ���� (�� GISTENTRY!). � *size �������� ������ ��������������� ����� � ������. ��������� GistEntryVector:

    typedef struct
    {  
            int32           n;          /* ���������� ��������� � ���� vector*/
            GISTENTRY       vector[1];
    } GistEntryVector;
    

    ������ ������� �� �������� NULL ���������.

  5. 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 �/��� �������� ���� ������������ �� ���������� ��������� ������.

  6. 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 �������):
  1. �������� ������ ���� ������ (���� ���������)
    • ��������� ������� �������������� ���� � 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
      );
      
  2. �������� ����� ���������� (���� ���������)
    • �������� ������� (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 = '<'
      );
      
  3. ����������� ������������ ������� 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-�.
������ ������ ����� ���������� � ltree.sql �� ������ ltree, ������� ��������� � ������������� 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-� ������� � �������� ���� � ���� ��� �����������, �� ����������� �������� � ������ ����� ��������� ��� �� �����, ��� ������ ����������� ���������� ������������� ����� � ����������� ������� � ������������������.

MBR of Greece cities (fragment)

R-tree ��� ��� ������� � �������� ������. ������ ����� � rtreeportal.org

�� ������� ��������� �������� ������ (������ ������), ������������ � ������� ������ rtree_gistgevel - ������������ ������, ���������������� ��� ������������� ���������� � �������������� GiST. ��������� ������� �������� MBR (minimum bounding rectangles) ������� � �������� ������. ���������� ������ �� �������� ����� (��������� ��������������) � �� 1-� ������ (������� ��������������). ��������� ����� ��������� �����.
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" (�������� ������) � ��� ��������, ��� ��� ������, ������� �� ������ ��� ������, ���������� ���������, �.�., �������� � �������� ���������, ���������� � �������.

compress
Datum
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.