11. INTERFACING EXTENSIONS TO INDICES

Look back at Figure 3. The right half shows the catalogs that we must modify in order to tell POSTGRES how to use a user-defined type and/or user-defined operators with an index (i.e., pg_am, pg_amop, pg_amproc and pg_opclass). Unfortunately, there is no simple command to do this. We will demonstrate how to modify these catalogs through a running example: a new operator class for the B-tree access method that sorts integers in ascending absolute value order.

The pg_am class contains one instance for every user defined access method. Support for the heap access method is built into POSTGRES, but every other access method is described here. The schema is

The object ID of the instance in pg_am is used as a foreign key in lots of other classes. You don't need to add a new instance to this class; all you're interested in is the object ID of the access method instance you want to extend:

         SELECT oid FROM pg_am WHERE amname = 'btree'

         +----+
         |oid |
         +----+
         |403 |
         +----+

Defining a new set of strategies is beyond the scope of this discussion, but we'll explain how B-tree strategies work because you'll need to know that to add a new operator class. In the pg_am class, the amstrategies attribute is the number of strategies defined for this access method. For B-trees, this number is 5. These strategies correspond to

The idea is that you'll need to add procedures corresponding to the comparisons above to the pg_amop relation (see below). The access method code can use these strategy numbers, regardless of data type, to figure out how to partition the B-tree, compute selectivity, and so on. Don't worry about the details of adding procedures yet; just understand that there must be a set of these procedures for int2, int4, oid, and every other data type on which a B-tree can operate.

Sometimes, strategies aren't enough information for the system to figure out how to use an index. Some access methods require other support routines in order to work. For example, the B-tree access method must be able to compare two keys and determine whether one is greater than, equal to, or less than the other. Similarly, the R-tree access method must be able to compute intersections, unions, and sizes of rectangles. These operations do not correspond to user qualifications in SQL queries; they are administrative routines used by the access methods, internally.

In order to manage diverse support routines consistently across all POSTGRES access methods, pg_am includes an attribute called amsupport. This attribute records the number of support routines used by an access method. For B-trees, this number is one -- the routine to take two keys and return -1, 0, or +1, depending on whether the first key is less than, equal to, or greater than the second.[8]

The amstrategies entry in pg_am is just the number of strategies defined for the access method in question. The procedures for less than, less equal, and so on don't appear in pg_am. Similarly, amsupport is just the number of support routines required by the access method. The actual routines are listed elsewhere.

The next class of interest is pg_opclass. This class exists only to associate a name with an oid. In pg_amop, every B-tree operator class has a set of procedures, one through five, above. Some existing opclasses are int2_ops, int4_ops, and oid_ops. You need to add an instance with your opclass name (for example, complex_abs_ops) to pg_opclass. The oid of this instance is a foreign key in other classes.

         INSERT INTO pg_opclass (opcname) VALUES ('complex_abs_ops');

         SELECT oid, opcname
           FROM pg_opclass
           WHERE opcname = 'complex_abs_ops';

         +------+--------------+
         |oid   | opcname      |
         +------+--------------+
         |17314 | int4_abs_ops |
         +------+--------------+

So now we have an access method and an operator class. We still need a set of operators; the procedure for defining operators was discussed earlier in this manual. For the complex_abs_ops operator class on Btrees, the operators we require are:

         absolute value less-than
         absolute value less-than-or-equal
         absolute value equal
         absolute value greater-than-or-equal
         absolute value greater-than

         /usr/local/postgres95/src/tutorial/complex.c

         #define Mag(c) ((c)->x*(c)->x + (c)->y*(c)->y)

         bool
         complex_abs_eq(Complex *a, Complex *b)
         {
             double amag = Mag(a), bmag = Mag(b);
             return (amag==bmag);
         }

First, note that operators for less-than, less-than-or equal, equal, greater-than-or-equal, and greater-than for int4 are being defined. All of these operators are already defined for int4 under the names <, <=, =, >=, and >. The new operators behave differently, of course. In order to guarantee that POSTGRES uses these new operators rather than the old ones, they need to be named differently from the old ones. This is a key point: you can overload operators in POSTGRES, but only if the operator isn't already defined for the argument types. That is, if you have < defined for (int4, int4), you can't define it again. POSTGRES does not check this when you define your operator, so be careful. To avoid this problem, odd names will be used for the operators. If you get this wrong, the access methods are likely to crash when you try to do scans.

The other important point is that all the operator functions return Boolean values. The access methods rely on this fact. (On the other hand, the support function returns whatever the particular access method expects -- in this case, a signed integer.) The final routine in the file is the "support routine" mentioned when we discussed the amsupport attribute of the pg_am class. We will use this later on. For now, ignore it.

         CREATE FUNCTION complex_abs_eq(complex, complex)
              RETURNS bool
              AS '/usr/local/postgres95/tutorial/obj/complex.so'
              LANGUAGE 'c';

         /*
          * this query uses the regular expression operator (~)
          * to find three-character operator names that end in
          * the character &
          */
         SELECT *
         FROM pg_operator
         WHERE oprname ~ '^..&$'::text;

         CREATE OPERATOR = (
            leftarg = complex, rightarg = complex, procedure = complex_abs_eq,
            restrict = eqsel, join = eqjoinsel
         )

We're just about finished. the last thing we need to do is to update the pg_amop relation. To do this, we need the following attributes:

The cost functions are used by the query optimizer to decide whether or not to use a given index in a scan. Fortunately, these already exist. The two functions we'll use are btreesel, which estimates the selectivity of the B-tree, and btreenpage, which estimates the number of pages a search will touch in the tree.

So we need the oids of the operators we just defined. We'll look up the names of all the operators that take two int4s, and pick ours out:

         SELECT o.oid AS opoid, o.oprname
         INTO TABLE complex_ops_tmp
         FROM pg_operator o, pg_type t
         WHERE o.oprleft = t.oid and o.oprright = t.oid
              and t.typname = 'complex';

     which returns:

         +------+---------+
         |oid   | oprname |
         +------+---------+
         |17321 | <       |
         +------+---------+
         |17322 | <=      |
         +------+---------+
         |17323 |  =      |
         +------+---------+
         |17324 | >=      |
         +------+---------+
         |17325 | >       |
         +------+---------+

Now we're ready to update pg_amop with our new operator class. The most important thing in this entire discussion is that the operators are ordered, from less equal through greater equal, in pg_amop. We add the instances we need:

          INSERT INTO pg_amop (amopid, amopclaid, amopopr, amopstrategy,
                              amopselect, amopnpages)
              SELECT am.oid, opcl.oid, c.opoid, 3,
                 'btreesel'::regproc, 'btreenpage'::regproc
              FROM pg_am am, pg_opclass opcl, complex_ops_tmp c
              WHERE amname = 'btree' and opcname = 'complex_abs_ops'
                 and c.oprname = '=';

The last step (finally!) is registration of the "support routine" previously described in our discussion of pg_am. The oid of this support routine is stored in the pg_amproc class, keyed by the access method oid and the operator class oid. First, we need to register the function in POSTGRES (recall that we put the C code that implements this routine in the bottom of the file in which we implemented the operator routines):

         CREATE FUNCTION int4_abs_cmp(int4, int4)
               RETURNS int4
               AS '/usr/local/postgres95/tutorial/obj/complex.so'
               LANGUAGE 'c';

         SELECT oid, proname FROM pg_proc WHERE prname = 'int4_abs_cmp';

         +------+--------------+
         |oid   | proname      |
         +------+--------------+
         |17328 | int4_abs_cmp |
         +------+--------------+

         INSERT INTO pg_amproc (amid, amopclaid, amproc, amprocnum)
              VALUES ('403'::oid,        -- btree oid
                      '17314'::oid,      --  pg_opclass tuple
                      '17328'::oid,      -- new pg_proc oid
                      '1'::int2);