| blob | 99098ab2522831815f9b40d805656328bede09a2 |
1 <!-- doc/src/sgml/gist.sgml -->
6 <indexterm>
9 </indexterm>
14 <para>
16 balanced, tree-structured access method, that acts as a base template in
17 which to implement arbitrary indexing schemes. B-trees, R-trees and many
19 </para>
21 <para>
23 of custom data types with the appropriate access methods, by
24 an expert in the domain of the data type, rather than a database expert.
25 </para>
27 <para>
28 Some of the information here is derived from the University of California
29 at Berkeley's GiST Indexing Project
31 Marcel Kornacker's thesis,
32 <ulink url="http://www.sai.msu.su/~megera/postgres/gist/papers/concurrency/access-methods-for-next-generation.pdf.gz">
33 Access Methods for Next-Generation Database Systems</ulink>.
36 maintained by Teodor Sigaev and Oleg Bartunov, and there is more
37 information on their
39 </para>
41 </sect2>
46 <para>
52 </para>
60 <thead>
61 <row>
65 </row>
66 </thead>
67 <tbody>
68 <row>
72 </row>
85 <row>
89 </row>
102 <row>
106 </row>
118 <row>
122 </row>
141 <row>
145 </row>
154 <row>
158 </row>
171 <row>
175 </row>
194 <row>
198 </row>
200 <row>
203 <entry></entry>
204 </row>
205 </tbody>
206 </tgroup>
207 </table>
209 <para>
213 for example
214 <programlisting>
215 CREATE INDEX ON my_table USING GIST (my_inet_column inet_ops);
216 </programlisting>
217 </para>
219 </sect2>
224 <para>
225 Traditionally, implementing a new index access method meant a lot of
226 difficult work. It was necessary to understand the inner workings of the
227 database, such as the lock manager and Write-Ahead Log. The
229 requiring the access method implementer only to implement the semantics of
231 takes care of concurrency, logging and searching the tree structure.
232 </para>
234 <para>
235 This extensibility should not be confused with the extensibility of the
236 other standard search trees in terms of the data they can handle. For
238 and hash indexes. That means that you can use
240 data type you want. But B-trees only support range predicates
242 and hash indexes only support equality queries.
243 </para>
245 <para>
246 So if you index, say, an image collection with a
253 ways to ask domain-specific questions, perhaps <quote>find all images of
255 </para>
257 <para>
259 is to implement several user-defined methods, which define the behavior of
260 keys in the tree. Of course these methods have to be pretty fancy to
261 support fancy queries, but for all the standard queries (B-trees,
262 R-trees, etc.) they're relatively straightforward. In short,
264 reuse, and a clean interface.
265 </para>
267 <para>
268 There are five methods that an index operator class for
270 Correctness of the index is ensured
274 methods.
277 a different type than the data it indexes. The leaves are to be of the
278 indexed data type, while the other tree nodes can be of any C struct (but
284 if the operator class wishes to support ordered scans (nearest-neighbor
286 operator class wishes to support index-only scans, except when the
289 user-specified parameters.
293 translate compare types (from
295 used by the operator class. This lets the core code look up operators for
296 temporal constraint indexes.
297 </para>
299 <variablelist>
300 <varlistentry>
302 <listitem>
303 <para>
305 this function determines whether the index entry is
309 any row represented by the index entry? For a leaf index entry this is
310 equivalent to testing the indexable condition, while for an internal
311 tree node this determines whether it is necessary to scan the subtree
312 of the index represented by the tree node. When the result is
314 This indicates whether the predicate is certainly true or only possibly
318 system will automatically evaluate the
320 if it is really a match. This convention allows
322 structures.
323 </para>
325 <para>
328 <programlisting>
329 CREATE OR REPLACE FUNCTION my_consistent(internal, data_type, smallint, oid, internal)
330 RETURNS bool
331 AS 'MODULE_PATHNAME'
332 LANGUAGE C STRICT;
333 </programlisting>
335 And the matching code in the C module could then follow this skeleton:
337 <programlisting>
338 PG_FUNCTION_INFO_V1(my_consistent);
340 Datum
341 my_consistent(PG_FUNCTION_ARGS)
342 {
343 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
344 data_type *query = PG_GETARG_DATA_TYPE_P(1);
345 StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
346 /* Oid subtype = PG_GETARG_OID(3); */
347 bool *recheck = (bool *) PG_GETARG_POINTER(4);
348 data_type *key = DatumGetDataType(entry->key);
349 bool retval;
351 /*
352 * determine return value as a function of strategy, key and query.
353 *
354 * Use GIST_LEAF(entry) to know where you're called in the index tree,
355 * which comes handy when supporting the = operator for example (you could
356 * check for non empty union() in non-leaf nodes and equality in leaf
357 * nodes).
358 */
360 *recheck = true; /* or false if check is exact */
362 PG_RETURN_BOOL(retval);
363 }
364 </programlisting>
368 parameter indicates which operator of your operator class is being
369 applied — it matches one of the operator numbers in the
371 </para>
373 <para>
374 Depending on which operators you have included in the class, the data
376 be whatever type is on the right-hand side of the operator, which might
377 be different from the indexed data type appearing on the left-hand side.
378 (The above code skeleton assumes that only one type is possible; if
380 on the operator.) It is recommended that the SQL declaration of
383 might be something else depending on the operator.
384 </para>
386 </listitem>
387 </varlistentry>
389 <varlistentry>
391 <listitem>
392 <para>
393 This method consolidates information in the tree. Given a set of
394 entries, this function generates a new index entry that represents
395 all the given entries.
396 </para>
398 <para>
401 <programlisting>
402 CREATE OR REPLACE FUNCTION my_union(internal, internal)
403 RETURNS storage_type
404 AS 'MODULE_PATHNAME'
405 LANGUAGE C STRICT;
406 </programlisting>
408 And the matching code in the C module could then follow this skeleton:
410 <programlisting>
411 PG_FUNCTION_INFO_V1(my_union);
413 Datum
414 my_union(PG_FUNCTION_ARGS)
415 {
416 GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
417 GISTENTRY *ent = entryvec->vector;
418 data_type *out,
419 *tmp,
420 *old;
421 int numranges,
422 i = 0;
424 numranges = entryvec->n;
425 tmp = DatumGetDataType(ent[0].key);
426 out = tmp;
428 if (numranges == 1)
429 {
430 out = data_type_deep_copy(tmp);
432 PG_RETURN_DATA_TYPE_P(out);
433 }
436 {
437 old = out;
438 tmp = DatumGetDataType(ent[i].key);
439 out = my_union_implementation(out, tmp);
440 }
442 PG_RETURN_DATA_TYPE_P(out);
443 }
444 </programlisting>
445 </para>
447 <para>
448 As you can see, in this skeleton we're dealing with a data type
450 enough to support data types where this is not the case, by
451 implementing the proper union algorithm in this
453 </para>
455 <para>
457 index's storage type, whatever that is (it might or might not be
460 memory. You can't just return the input value as-is, even if there is
461 no type change.
462 </para>
464 <para>
468 pointer to an integer variable, which can be ignored. (It used to be
470 result value into that variable, but this is no longer necessary.)
471 </para>
472 </listitem>
473 </varlistentry>
475 <varlistentry>
477 <listitem>
478 <para>
479 Converts a data item into a format suitable for physical storage in
480 an index page.
482 in the index without modification.
483 </para>
485 <para>
488 <programlisting>
489 CREATE OR REPLACE FUNCTION my_compress(internal)
490 RETURNS internal
491 AS 'MODULE_PATHNAME'
492 LANGUAGE C STRICT;
493 </programlisting>
495 And the matching code in the C module could then follow this skeleton:
497 <programlisting>
498 PG_FUNCTION_INFO_V1(my_compress);
500 Datum
501 my_compress(PG_FUNCTION_ARGS)
502 {
503 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
504 GISTENTRY *retval;
506 if (entry->leafkey)
507 {
508 /* replace entry->key with a compressed version */
509 compressed_data_type *compressed_data = palloc(sizeof(compressed_data_type));
511 /* fill *compressed_data from entry->key ... */
513 retval = palloc(sizeof(GISTENTRY));
514 gistentryinit(*retval, PointerGetDatum(compressed_data),
516 }
517 else
518 {
519 /* typically we needn't do anything with non-leaf entries */
520 retval = entry;
521 }
523 PG_RETURN_POINTER(retval);
524 }
525 </programlisting>
526 </para>
528 <para>
530 type you're converting to in order to compress your leaf nodes, of
531 course.
532 </para>
533 </listitem>
534 </varlistentry>
536 <varlistentry>
538 <listitem>
539 <para>
540 Converts the stored representation of a data item into a format that
541 can be manipulated by the other GiST methods in the operator class.
543 the other GiST methods can work directly on the stored data format.
550 require full reconstruction of the data.)
551 </para>
553 <para>
556 <programlisting>
557 CREATE OR REPLACE FUNCTION my_decompress(internal)
558 RETURNS internal
559 AS 'MODULE_PATHNAME'
560 LANGUAGE C STRICT;
561 </programlisting>
563 And the matching code in the C module could then follow this skeleton:
565 <programlisting>
566 PG_FUNCTION_INFO_V1(my_decompress);
568 Datum
569 my_decompress(PG_FUNCTION_ARGS)
570 {
571 PG_RETURN_POINTER(PG_GETARG_POINTER(0));
572 }
573 </programlisting>
575 The above skeleton is suitable for the case where no decompression
576 is needed. (But, of course, omitting the method altogether is even
577 easier, and is recommended in such cases.)
578 </para>
579 </listitem>
580 </varlistentry>
582 <varlistentry>
584 <listitem>
585 <para>
587 entry into a particular branch of the tree. Items will be inserted
590 If a negative value is returned, it will be treated as zero.
591 </para>
593 <para>
596 <programlisting>
597 CREATE OR REPLACE FUNCTION my_penalty(internal, internal, internal)
598 RETURNS internal
599 AS 'MODULE_PATHNAME'
600 LANGUAGE C STRICT; -- in some cases penalty functions need not be strict
601 </programlisting>
603 And the matching code in the C module could then follow this skeleton:
605 <programlisting>
606 PG_FUNCTION_INFO_V1(my_penalty);
608 Datum
609 my_penalty(PG_FUNCTION_ARGS)
610 {
611 GISTENTRY *origentry = (GISTENTRY *) PG_GETARG_POINTER(0);
612 GISTENTRY *newentry = (GISTENTRY *) PG_GETARG_POINTER(1);
613 float *penalty = (float *) PG_GETARG_POINTER(2);
614 data_type *orig = DatumGetDataType(origentry->key);
615 data_type *new = DatumGetDataType(newentry->key);
617 *penalty = my_penalty_implementation(orig, new);
618 PG_RETURN_POINTER(penalty);
619 }
620 </programlisting>
624 at the location indicated by the third argument. The return
625 value per se is ignored, though it's conventional to pass back the
626 address of that argument.
627 </para>
629 <para>
631 the index. It'll get used at insertion time to determine which branch
632 to follow when choosing where to add the new entry in the tree. At
633 query time, the more balanced the index, the quicker the lookup.
634 </para>
635 </listitem>
636 </varlistentry>
638 <varlistentry>
640 <listitem>
641 <para>
642 When an index page split is necessary, this function decides which
643 entries on the page are to stay on the old page, and which are to move
644 to the new page.
645 </para>
647 <para>
650 <programlisting>
651 CREATE OR REPLACE FUNCTION my_picksplit(internal, internal)
652 RETURNS internal
653 AS 'MODULE_PATHNAME'
654 LANGUAGE C STRICT;
655 </programlisting>
657 And the matching code in the C module could then follow this skeleton:
659 <programlisting>
660 PG_FUNCTION_INFO_V1(my_picksplit);
662 Datum
663 my_picksplit(PG_FUNCTION_ARGS)
664 {
665 GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
666 GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
668 GISTENTRY *ent = entryvec->vector;
669 int i,
670 nbytes;
671 OffsetNumber *left,
672 *right;
673 data_type *tmp_union;
674 data_type *unionL;
675 data_type *unionR;
676 GISTENTRY **raw_entryvec;
679 nbytes = (maxoff + 1) * sizeof(OffsetNumber);
681 v->spl_left = (OffsetNumber *) palloc(nbytes);
682 left = v->spl_left;
685 v->spl_right = (OffsetNumber *) palloc(nbytes);
686 right = v->spl_right;
689 unionL = NULL;
690 unionR = NULL;
692 /* Initialize the raw entry vector. */
693 raw_entryvec = (GISTENTRY **) malloc(entryvec->n * sizeof(void *));
694 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
697 for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
698 {
699 int real_index = raw_entryvec[i] - entryvec->vector;
701 tmp_union = DatumGetDataType(entryvec->vector[real_index].key);
702 Assert(tmp_union != NULL);
704 /*
705 * Choose where to put the index entries and update unionL and unionR
706 * accordingly. Append the entries to either v->spl_left or
707 * v->spl_right, and care about the counters.
708 */
710 if (my_choice_is_left(unionL, curl, unionR, curr))
711 {
712 if (unionL == NULL)
713 unionL = tmp_union;
714 else
715 unionL = my_union_implementation(unionL, tmp_union);
717 *left = real_index;
718 ++left;
719 ++(v->spl_nleft);
720 }
721 else
722 {
723 /*
724 * Same on the right
725 */
726 }
727 }
729 v->spl_ldatum = DataTypeGetDatum(unionL);
730 v->spl_rdatum = DataTypeGetDatum(unionR);
731 PG_RETURN_POINTER(v);
732 }
733 </programlisting>
737 value per se is ignored, though it's conventional to pass back the
739 </para>
741 <para>
743 is crucial to good performance of the index. Designing suitable
745 is where the challenge of implementing well-performing
747 </para>
748 </listitem>
749 </varlistentry>
751 <varlistentry>
753 <listitem>
754 <para>
755 Returns true if two index entries are identical, false otherwise.
757 not necessarily the original indexed column's type.)
758 </para>
760 <para>
763 <programlisting>
764 CREATE OR REPLACE FUNCTION my_same(storage_type, storage_type, internal)
765 RETURNS internal
766 AS 'MODULE_PATHNAME'
767 LANGUAGE C STRICT;
768 </programlisting>
770 And the matching code in the C module could then follow this skeleton:
772 <programlisting>
773 PG_FUNCTION_INFO_V1(my_same);
775 Datum
776 my_same(PG_FUNCTION_ARGS)
777 {
778 prefix_range *v1 = PG_GETARG_PREFIX_RANGE_P(0);
779 prefix_range *v2 = PG_GETARG_PREFIX_RANGE_P(1);
780 bool *result = (bool *) PG_GETARG_POINTER(2);
782 *result = my_eq(v1, v2);
783 PG_RETURN_POINTER(result);
784 }
785 </programlisting>
788 just return a Boolean result; instead it has to store the flag
789 at the location indicated by the third argument. The return
790 value per se is ignored, though it's conventional to pass back the
791 address of that argument.
792 </para>
793 </listitem>
794 </varlistentry>
796 <varlistentry>
798 <listitem>
799 <para>
801 this function determines the index entry's
803 supplied if the operator class contains any ordering operators.
804 A query using the ordering operator will be implemented by returning
806 so the results must be consistent with the operator's semantics.
807 For a leaf index entry the result just represents the distance to
808 the index entry; for an internal tree node, the result must be the
809 smallest distance that any child entry could have.
810 </para>
812 <para>
815 <programlisting>
816 CREATE OR REPLACE FUNCTION my_distance(internal, data_type, smallint, oid, internal)
817 RETURNS float8
818 AS 'MODULE_PATHNAME'
819 LANGUAGE C STRICT;
820 </programlisting>
822 And the matching code in the C module could then follow this skeleton:
824 <programlisting>
825 PG_FUNCTION_INFO_V1(my_distance);
827 Datum
828 my_distance(PG_FUNCTION_ARGS)
829 {
830 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
831 data_type *query = PG_GETARG_DATA_TYPE_P(1);
832 StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
833 /* Oid subtype = PG_GETARG_OID(3); */
834 /* bool *recheck = (bool *) PG_GETARG_POINTER(4); */
835 data_type *key = DatumGetDataType(entry->key);
836 double retval;
838 /*
839 * determine return value as a function of strategy, key and query.
840 */
842 PG_RETURN_FLOAT8(retval);
843 }
844 </programlisting>
848 </para>
850 <para>
851 Some approximation is allowed when determining the distance, so long
852 as the result is never greater than the entry's actual distance. Thus,
853 for example, distance to a bounding box is usually sufficient in
854 geometric applications. For an internal tree node, the distance
855 returned must not be greater than the distance to any of the child
856 nodes. If the returned distance is not exact, the function must set
858 nodes; for them, the calculation is always assumed to be inexact.) In
859 this case the executor will calculate the accurate distance after
860 fetching the tuple from the heap, and reorder the tuples if necessary.
861 </para>
863 <para>
865 leaf node, the original ordering operator's return type must
867 result values must be comparable to those of the original ordering
868 operator, since the executor will sort using both distance function
869 results and recalculated ordering-operator results. Otherwise, the
871 values, so long as the relative order of the result values matches the
872 order returned by the ordering operator. (Infinity and minus infinity
873 are used internally to handle cases such as nulls, so it is not
875 </para>
877 </listitem>
878 </varlistentry>
880 <varlistentry>
882 <listitem>
883 <para>
884 Converts the compressed index representation of a data item into the
885 original data type, for index-only scans. The returned data must be an
886 exact, non-lossy copy of the originally indexed value.
887 </para>
889 <para>
892 <programlisting>
893 CREATE OR REPLACE FUNCTION my_fetch(internal)
894 RETURNS internal
895 AS 'MODULE_PATHNAME'
896 LANGUAGE C STRICT;
897 </programlisting>
903 original, uncompressed form. If the opclass's compress function does
905 argument as-is. Or, if the opclass does not have a compress function,
907 necessarily be a no-op.
908 </para>
910 <para>
911 The matching code in the C module could then follow this skeleton:
913 <programlisting>
914 PG_FUNCTION_INFO_V1(my_fetch);
916 Datum
917 my_fetch(PG_FUNCTION_ARGS)
918 {
919 GISTENTRY *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
920 input_data_type *in = DatumGetPointer(entry->key);
921 fetched_data_type *fetched_data;
922 GISTENTRY *retval;
924 retval = palloc(sizeof(GISTENTRY));
925 fetched_data = palloc(sizeof(fetched_data_type));
927 /*
928 * Convert 'fetched_data' into the a Datum of the original datatype.
929 */
931 /* fill *retval from fetched_data. */
932 gistentryinit(*retval, PointerGetDatum(converted_datum),
935 PG_RETURN_POINTER(retval);
936 }
937 </programlisting>
938 </para>
940 <para>
941 If the compress method is lossy for leaf entries, the operator class
942 cannot support index-only scans, and must not define
944 </para>
946 </listitem>
947 </varlistentry>
949 <varlistentry>
951 <listitem>
952 <para>
953 Allows definition of user-visible parameters that control operator
954 class behavior.
955 </para>
957 <para>
960 <programlisting>
961 CREATE OR REPLACE FUNCTION my_options(internal)
962 RETURNS void
963 AS 'MODULE_PATHNAME'
964 LANGUAGE C STRICT;
965 </programlisting>
966 </para>
968 <para>
970 struct, which needs to be filled with a set of operator class
971 specific options. The options can be accessed from other support
974 </para>
976 <para>
977 An example implementation of my_options() and parameters use
978 from other support functions are given below:
980 <programlisting>
981 typedef enum MyEnumType
982 {
983 MY_ENUM_ON,
984 MY_ENUM_OFF,
985 MY_ENUM_AUTO
986 } MyEnumType;
988 typedef struct
989 {
990 int32 vl_len_; /* varlena header (do not touch directly!) */
991 int int_param; /* integer parameter */
992 double real_param; /* real parameter */
993 MyEnumType enum_param; /* enum parameter */
994 int str_param; /* string parameter */
995 } MyOptionsStruct;
997 /* String representation of enum values */
998 static relopt_enum_elt_def myEnumValues[] =
999 {
1000 {"on", MY_ENUM_ON},
1001 {"off", MY_ENUM_OFF},
1002 {"auto", MY_ENUM_AUTO},
1003 {(const char *) NULL} /* list terminator */
1004 };
1006 static char *str_param_default = "default";
1008 /*
1009 * Sample validator: checks that string is not longer than 8 bytes.
1010 */
1011 static void
1012 validate_my_string_relopt(const char *value)
1013 {
1015 ereport(ERROR,
1016 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
1017 errmsg("str_param must be at most 8 bytes")));
1018 }
1020 /*
1021 * Sample filler: switches characters to lower case.
1022 */
1023 static Size
1024 fill_my_string_relopt(const char *value, void *ptr)
1025 {
1026 char *tmp = str_tolower(value, strlen(value), DEFAULT_COLLATION_OID);
1027 int len = strlen(tmp);
1029 if (ptr)
1030 strcpy((char *) ptr, tmp);
1032 pfree(tmp);
1033 return len + 1;
1034 }
1036 PG_FUNCTION_INFO_V1(my_options);
1038 Datum
1039 my_options(PG_FUNCTION_ARGS)
1040 {
1041 local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
1043 init_local_reloptions(relopts, sizeof(MyOptionsStruct));
1046 offsetof(MyOptionsStruct, int_param));
1049 offsetof(MyOptionsStruct, real_param));
1051 myEnumValues, MY_ENUM_ON,
1053 offsetof(MyOptionsStruct, enum_param));
1055 str_param_default,
1056 &validate_my_string_relopt,
1057 &fill_my_string_relopt,
1058 offsetof(MyOptionsStruct, str_param));
1060 PG_RETURN_VOID();
1061 }
1063 PG_FUNCTION_INFO_V1(my_compress);
1065 Datum
1066 my_compress(PG_FUNCTION_ARGS)
1067 {
1068 int int_param = 100;
1069 double real_param = 1.0;
1070 MyEnumType enum_param = MY_ENUM_ON;
1071 char *str_param = str_param_default;
1073 /*
1074 * Normally, when opclass contains 'options' method, then options are always
1075 * passed to support functions. However, if you add 'options' method to
1076 * existing opclass, previously defined indexes have no options, so the
1077 * check is required.
1078 */
1079 if (PG_HAS_OPCLASS_OPTIONS())
1080 {
1081 MyOptionsStruct *options = (MyOptionsStruct *) PG_GET_OPCLASS_OPTIONS();
1083 int_param = options->int_param;
1084 real_param = options->real_param;
1085 enum_param = options->enum_param;
1086 str_param = GET_STRING_RELOPTION(options, str_param);
1087 }
1089 /* the rest implementation of support function */
1090 }
1092 </programlisting>
1093 </para>
1095 <para>
1097 flexible, it may depend on user-specified parameters. For instance,
1098 the length of key signature may be specified. See
1100 </para>
1101 </listitem>
1102 </varlistentry>
1104 <varlistentry>
1106 <listitem>
1107 <para>
1108 Returns a comparator function to sort data in a way that preserves
1111 depends on how well the sort order determined by the comparator function
1112 preserves locality of the inputs.
1113 </para>
1114 <para>
1119 </para>
1121 <para>
1123 this:
1125 <programlisting>
1126 CREATE OR REPLACE FUNCTION my_sortsupport(internal)
1127 RETURNS void
1128 AS 'MODULE_PATHNAME'
1129 LANGUAGE C STRICT;
1130 </programlisting>
1133 struct. At a minimum, the function must fill in its comparator field.
1134 The comparator takes three arguments: two Datums to compare, and
1136 Datums are the two indexed values in the format that they are stored
1137 in the index; that is, in the format returned by the
1140 </para>
1142 <para>
1143 The matching code in the C module could then follow this skeleton:
1145 <programlisting>
1146 PG_FUNCTION_INFO_V1(my_sortsupport);
1148 static int
1149 my_fastcmp(Datum x, Datum y, SortSupport ssup)
1150 {
1151 /* establish order between x and y by computing some sorting value z */
1153 int z1 = ComputeSpatialCode(x);
1154 int z2 = ComputeSpatialCode(y);
1157 }
1159 Datum
1160 my_sortsupport(PG_FUNCTION_ARGS)
1161 {
1162 SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
1164 ssup->comparator = my_fastcmp;
1165 PG_RETURN_VOID();
1166 }
1167 </programlisting>
1168 </para>
1169 </listitem>
1170 </varlistentry>
1172 <varlistentry>
1174 <listitem>
1175 <para>
1178 number used by this operator class for matching functionality. The
1180 operator class has no matching strategy.
1181 </para>
1183 <para>
1184 This is used for temporal index constraints (i.e., <literal>PRIMARY
1186 provides this function and it returns results for
1189 </para>
1191 <para>
1193 this:
1195 <programlisting>
1196 CREATE OR REPLACE FUNCTION my_stratnum(integer)
1197 RETURNS smallint
1198 AS 'MODULE_PATHNAME'
1199 LANGUAGE C STRICT;
1200 </programlisting>
1201 </para>
1203 <para>
1204 The matching code in the C module could then follow this skeleton:
1206 <programlisting>
1207 PG_FUNCTION_INFO_V1(my_stratnum);
1209 Datum
1210 my_stratnum(PG_FUNCTION_ARGS)
1211 {
1212 CompareType cmptype = PG_GETARG_INT32(0);
1213 StrategyNumber ret = InvalidStrategy;
1215 switch (cmptype)
1216 {
1217 case COMPARE_EQ:
1218 ret = BTEqualStrategyNumber;
1219 }
1221 PG_RETURN_UINT16(ret);
1222 }
1223 </programlisting>
1224 </para>
1226 <para>
1227 One translation function is provided by
1232 extension defines a second translation function,
1235 </para>
1236 </listitem>
1237 </varlistentry>
1238 </variablelist>
1240 <para>
1241 All the GiST support methods are normally called in short-lived memory
1243 each tuple is processed. It is therefore not very important to worry about
1244 pfree'ing everything you palloc. However, in some cases it's useful for a
1245 support method to cache data across repeated calls. To do that, allocate
1248 data will survive for the life of the index operation (e.g., a single GiST
1249 index scan, index build, or index tuple insertion). Be careful to pfree
1251 will accumulate for the duration of the operation.
1252 </para>
1254 </sect2>
1262 <para>
1263 The simplest way to build a GiST index is just to insert all the entries,
1264 one by one. This tends to be slow for large indexes, because if the
1265 index tuples are scattered across the index and the index is large enough
1266 to not fit in cache, a lot of random I/O will be
1270 </para>
1272 <para>
1273 The sorted method is only available if each of the opclasses used by the
1276 usually the best, so it is used by default.
1277 </para>
1279 <para>
1280 The buffered method works by not inserting tuples directly into the index
1281 right away. It can dramatically reduce the amount of random I/O needed
1282 for non-ordered data sets. For well-ordered data sets the benefit is
1283 smaller or non-existent, because only a small number of pages receive new
1284 tuples at a time, and those pages fit in cache even if the index as a
1285 whole does not.
1286 </para>
1288 <para>
1290 function more often than the simple method does, which consumes some
1291 extra CPU resources. Also, the buffers need temporary disk space, up to
1292 the size of the resulting index. Buffering can also influence the quality
1293 of the resulting index, in both positive and negative directions. That
1294 influence depends on various factors, like the distribution of the input
1295 data and the operator class implementation.
1296 </para>
1298 <para>
1299 If sorting is not possible, then by default a GiST index build switches
1300 to the buffering method when the index size reaches
1303 CREATE INDEX command. The default behavior is good for most cases, but
1304 turning buffering off might speed up the build somewhat if the input data
1305 is ordered.
1306 </para>
1308 </sect3>
1309 </sect2>
1314 <para>
1316 several examples of index methods implemented using
1319 R-Tree equivalent functionality for some of the built-in geometric data types
1322 operator classes:
1324 <variablelist>
1325 <varlistentry>
1327 <listitem>
1329 </listitem>
1330 </varlistentry>
1332 <varlistentry>
1334 <listitem>
1336 </listitem>
1337 </varlistentry>
1339 <varlistentry>
1341 <listitem>
1343 </listitem>
1344 </varlistentry>
1346 <varlistentry>
1348 <listitem>
1350 </listitem>
1351 </varlistentry>
1353 <varlistentry>
1355 <listitem>
1357 </listitem>
1358 </varlistentry>
1360 <varlistentry>
1362 <listitem>
1364 </listitem>
1365 </varlistentry>
1367 <varlistentry>
1369 <listitem>
1371 </listitem>
1372 </varlistentry>
1373 </variablelist>
1374 </para>
1376 </sect2>
1378 </sect1>