Operator class group proposal

On Wed, Dec 13, 2006 at 04:27:09PM -0500, Tom Lane wrote:

After further thought about the mergejoinable-operators issue and some
other longstanding planner problems, I have a modest proposal to make:
we should invent the notion of "operator class groups", which identify
sets of compatible operator classes. (I'm not wedded to the name "class
group"; it seems a bit redundant. Anyone have a better idea?) We've
touched on related ideas in past threads but never really put together
a concrete proposal. Here is one.

<snip>

I think it's a good idea, though I would point out that in the examples
given it's the underlying types that are compatable, not the classes.
But I'm unsure if there's a way to use that. These groups seem a
reasonable addition to the existing system.

Other names I can think of:

- type class
- type group
- compatability class
- operator class set

None of which sound any good :(

It's good is that this provides more information about the underlying
types to the system, which improves the possibility of optimisation
(and correctness).

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/

Martijn van Oosterhout <kleptog@svana.org> writes:

On Wed, Dec 13, 2006 at 04:27:09PM -0500, Tom Lane wrote:

we should invent the notion of "operator class groups", which identify
sets of compatible operator classes.

I think it's a good idea, though I would point out that in the examples
given it's the underlying types that are compatable, not the classes.

Well, I didn't try very hard to provide a complete set of examples,
but here is one addressing that point: the string types have one set of
opclasses involving < = > and one set involving ~<~ ~=~ ~>~ (the
"pattern_ops" opclasses). These would need to be distinct class groups
since in fact they have incompatible semantics. Reverse-sort opclasses
would be another example.

Other names I can think of:
- type class
- type group
- compatability class
- operator class set
None of which sound any good :(

Yeah, I'm drawing a blank on good names too. In the absence of any
better idea I'm inclined to re-use some word that's already a keyword,
rather than invent a new one. (GROUP is already a fully reserved word,
I think because it's used in GROUP BY, so it wouldn't pose any parsing
problems.)

regards, tom lane

I wrote:

We further require that any given opclass be a member of at most one class
group (this simplifies matters, and there isn't any application I can see
for one opclass being in more than one group), and that a class group
contain at most one opclass for a given datatype (ditto).

BTW, I forgot to mention one of the motivations for that last
restriction: I'm thinking it would be convenient to allow index
declarations to accept either an opclass name or a class group name.
Thus you could say "pattern_ops" instead of being specific about
"varchar_pattern_ops" or "text_pattern_ops". Not sure whether
there's a need to worry about name collisions ...

regards, tom lane

[ replying to myself again, how tacky :-( ]

I wrote:

BTW, I forgot to mention one of the motivations for that last
restriction: I'm thinking it would be convenient to allow index
declarations to accept either an opclass name or a class group name.
Thus you could say "pattern_ops" instead of being specific about
"varchar_pattern_ops" or "text_pattern_ops".

Some more thought about that yielded what might or might not be a good
idea: why not just collapse all the members of a "class group" into one
opclass? In other words, not make a distinction between groups and
individual opclasses? So for example, int2_ops int4_ops and int8_ops
would all collapse into one big opclass.

In SQL terms this would mean allowing several "FOR TYPE foo" clauses in
a single CREATE OPERATOR CLASS command, and we'd likely have to give up
the shorthand where you can omit argument types for operators (or at
least, it'd only work in the case where you say FOR TYPE just once).

At the system catalog level this'd require some rearrangement of
pg_opclass, and the unique keys for pg_amop and pg_amproc would probably
need another column, but it certainly seems doable.

One rather large objection is that existing pg_dump files may contain
references to specific opclasses such as "varchar_pattern_ops". How
could we deal with converting that to a world where there's only one
"pattern_ops" opclass? In the past we've resorted to hard-wired
substitutions in gram.y, but that got too bletcherous to bear quite
some time ago. I'm thinking about allowing opclasses to have "aliases"
recorded in the system catalogs as a more general solution to the
problem; it'd let us get rid of those old hacks in gram.y, too.

The other thing that'd have to be dealt with is that for GIST and GIN,
the STORAGE clause needs to be associated with a specific indexable
type. I'm thinking the syntax might be like

CREATE OPERATOR CLASS name USING index_method AS
{ [ DEFAULT ] FOR TYPE data_type [ STORAGE storage_type ] [ ALIAS name ]
| OPERATOR strategy_number operator_name [ (op_type, op_type) ] [ RECHECK ]
| FUNCTION support_number funcname (argument_type [, ...])
} [, ... ]

plus a backwards-compatible variant syntax where there's just one FOR TYPE
clause before the USING part.

With either this or the original proposal, or for that matter our
existing releases, there's a bit of an issue with needing to modify
existing opclasses. Consider the situation of someone adding say
"tinyint" as a contrib module, and wanting it to interact reasonably
with the existing datatypes. He has to create some cross-type
operators, which is no big deal, but then he needs to plug them into
already-existing opclasses, and there's no provision for doing that.
I had been thinking that the scheme of adding opclasses to a
pre-existing group would fix that, but it doesn't really: you still need
to add more cross-type operators to the existing group member opclasses.

So this leads me to think that we need to allow
ALTER OPERATOR CLASS foo ADD [ TYPE/OPERATOR/FUNCTION ]
ALTER OPERATOR CLASS foo DROP [ TYPE/OPERATOR/FUNCTION ]
and the process for the would-be tinyint implementor is to add on
entries to an existing "numeric_ops" operator class, instead of
starting his own class.

Among other things this would require finer granularity in the
pg_depends entries, since dropping a type would involve deleting
elements of an opclass but not necessarily the whole thing.
(That may well mean that we still need an object equivalent to the
current per-datatype opclass, as something to be named in pg_depends;
in which case the above restructuring becomes largely syntactic sugar.)

It may be that the separate-GROUP approach is about as clean as this
once all the dust settles, but we'd still need to do something about
allowing additions to an existing operator class.

Thoughts?

regards, tom lane

Some more thought about that yielded what might or might not be a good
idea: why not just collapse all the members of a "class group" into one
opclass? In other words, not make a distinction between groups and
individual opclasses? So for example, int2_ops int4_ops and int8_ops
would all collapse into one big opclass.

IMHO, this is better than groups, but in any case exact opclass will be defined
by pair: (opgroup, opclass) in first case or (opclass, alias) in second. Pair is
needed to find support function(s). For instance, contrib/intarray makes two
GiST opclasses with different storage types.

I don't have any idea whether opclass groups would be useful for GiST or
GIN indexes, but maybe Oleg and Teodor can think of applications.

I'm afraid it isn't useful for GiST/GIN - strategies are not defined at all and
planner can't known about semantic meaning of operation/strategies.

Examples of opclasses which can be joined in one group:
1) geometry opclasses
2) gist__int_ops and gist__intbig_ops for GiST from contrib/intarray (BTW,
gin__int_ops for GIN supports the same operations and the same strategies
as gist__int*_ops)
3) some of opclasses from btree_gist.
4) builtin GIN oplasses for arrays and it possible to add cross-type operations
for arrays ( ie int4[] && int8[] )

BTW, unpleasant behaviour of postgres:
postgres=# CREATE TABLE foo (a varchar);
postgres=# CREATE INDEX fooidx ON foo (a varchar_pattern_ops);
postgres=# ALTER OPERATOR CLASS varchar_pattern_ops USING btree RENAME TO bar;

% pg_dump postgres | psql wow
...
ERROR: operator class "bar" does not exist for access method "btree"
...

May be, it will be useful to forbids altering/renaming of builtin objects...

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

CREATE OPERATOR CLASS name USING index_method AS
{ [ DEFAULT ] FOR TYPE data_type [ STORAGE storage_type ] [
ALIAS name ]
| OPERATOR strategy_number operator_name [ (op_type,
op_type) ] [ RECHECK ]
| FUNCTION support_number funcname (argument_type [, ...])
} [, ... ]

plus a backwards-compatible variant syntax where there's just
one FOR TYPE
clause before the USING part.

With either this or the original proposal, or for that matter our
existing releases, there's a bit of an issue with needing to modify
existing opclasses. Consider the situation of someone adding say
"tinyint" as a contrib module, and wanting it to interact reasonably
with the existing datatypes. He has to create some cross-type
operators, which is no big deal, but then he needs to plug them into
already-existing opclasses, and there's no provision for doing that.
I had been thinking that the scheme of adding opclasses to a
pre-existing group would fix that, but it doesn't really: you
still need
to add more cross-type operators to the existing group member
opclasses.

So this leads me to think that we need to allow
ALTER OPERATOR CLASS foo ADD [ TYPE/OPERATOR/FUNCTION ]
ALTER OPERATOR CLASS foo DROP [ TYPE/OPERATOR/FUNCTION ]
and the process for the would-be tinyint implementor is to add on
entries to an existing "numeric_ops" operator class, instead of
starting his own class.

I think it would be easier to understand if we do not merge the
opclasses
for different types into one statement.

We would add type to the key and thus have:
CREATE OPERATOR CLASS name USING index_method FOR TYPE data_type ...
DROP OPERATOR CLASS name USING index_method FOR TYPE data_type ...

I would then name the opclasses btree_ops (for the default btree
opclass)
with no reference to type, but only to functionality. (maybe we need to
diff text and number)
Classes with the same name and index_method would implicitly be a class
group.

I generally like the idea to simplify this area.

As an aside, Informix decided to name compatible operator functions
identically
and define an opclass as those names:
opclassname owner amid opclassid ops support
btree_ops informix 1 1
lessthan;lessthanorequal;equal;greaterthanorequal;greaterthan; compare;
rtree_ops informix 2 2
overlap;equal;contains;within; union;size;inter;
This is also simple to use and understand.

Andreas

On Wed, Dec 13, 2006 at 07:28:20PM -0500, Tom Lane wrote:

Some more thought about that yielded what might or might not be a good
idea: why not just collapse all the members of a "class group" into one
opclass? In other words, not make a distinction between groups and
individual opclasses? So for example, int2_ops int4_ops and int8_ops
would all collapse into one big opclass.

I think it may be useful to maintain the distinction between groups and
classes for users, because at that level the whole concept is easier to
understand. Dropping and recreating operator classes is easier to
handle than playing strange tricks with ALTER OPERATOR CLASS GROUP. And
probably easier to get right/harder to screw up.

How the backend implements it may be easier as one single large
opclass. Essentially the operater class table becomes merely a
placeholder for the name (maybe also aliases?), which can still be used
in index declarations, but is never used by the backend otherwise.

That would preserve backward compatability while still allowing all the
benefits.

BTW, in some aspects this resembles some of the changes needed for SQL
collate support. There also I tried to merge operator classes into
something larger. However, there the point was that the group becomes a
common pathkey identifier for all the underlying types, which is not in
your proposal.

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/

"Zeugswetter Andreas ADI SD" <ZeugswetterA@spardat.at> writes:

I think it would be easier to understand if we do not merge the
opclasses for different types into one statement.

Agreed, huge CREATE OPERATOR CLASS commands would be no fun, which
is one reason for my recommendation to improve ALTER OPERATOR CLASS.
I think that in practice people would use ALTER to add one type at
a time to an opclass.

Classes with the same name and
index_method would implicitly be a class group.

[ itch... ] I've never cared for the idea that semantics should depend
fundamentally on the mere name of something. I think we want class
groups to be real objects in one form or another, not chance
associations. As a specific objection, under this rule it would never
become possible to allow unprivileged users to create opclasses, because
they could break the behavior of someone else's opclass just by creating
another one of the same name with not-really-compatible behavior.

As an aside, Informix decided to name compatible operator functions
identically and define an opclass as those names:

Interesting. Probably too much water under the bridge now for us to
consider forcing function/operator renames, though.

regards, tom lane

Martijn van Oosterhout <kleptog@svana.org> writes:

I think it may be useful to maintain the distinction between groups and
classes for users, because at that level the whole concept is easier to
understand. Dropping and recreating operator classes is easier to
handle than playing strange tricks with ALTER OPERATOR CLASS GROUP. And
probably easier to get right/harder to screw up.

I'm not sure. The problem that I'm seeing is that currently, cross-type
comparisons go into the opclass associated with their left-hand argument
type. Therefore, if say you want to add "tinyint" to an opclass group,
you not only need to add an opclass for tinyint (containing tinyint vs
tinyint as well as tinyint vs other-type operators), but you also need
to add other-type vs tinyint operators to the *other* members of the
group. So the notion of the classes being separate objects seems a bit
artificial to me. I think that "if I want to make tinyint part of the
numeric_ops index opclass, I just add the type and all these operators to
that opclass" is at least as clear.

regards, tom lane

"Tom Lane" <tgl@sss.pgh.pa.us> writes:

I'm not sure. The problem that I'm seeing is that currently, cross-type
comparisons go into the opclass associated with their left-hand argument
type. Therefore, if say you want to add "tinyint" to an opclass group,
you not only need to add an opclass for tinyint (containing tinyint vs
tinyint as well as tinyint vs other-type operators), but you also need
to add other-type vs tinyint operators to the *other* members of the
group. So the notion of the classes being separate objects seems a bit
artificial to me. I think that "if I want to make tinyint part of the
numeric_ops index opclass, I just add the type and all these operators to
that opclass" is at least as clear.

Hm, would we still need all the cross-data-type btree operators? Could the
planner be taught that as long as the two types belong to the same
opclassclass that it's ok to use a btree operator that requires a cast first
before being used?

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

Gregory Stark <stark@enterprisedb.com> writes:

Hm, would we still need all the cross-data-type btree operators?

Yes, I think so; remember all the pain we had when we didn't have
indexable cross-type operators and spent years looking for a non-broken
way of introducing casts to solve the problem. Those were fundamental
semantic problems and AFAICS we'd be right back into that if we take
cross-type operators out of the opclasses again.

Basically what I'm on about here is that the way we shoehorned
cross-type operators into opclasses was a kluge. Which was not a bad
idea when we weren't yet sure it would solve the problem. But now it's
looking better and better to take the next step and allow opclasses to
support multiple types explicitly.

regards, tom lane

Martijn van Oosterhout <kleptog@svana.org> writes:

I think it may be useful to maintain the distinction between groups and
classes for users, because at that level the whole concept is easier to
understand. Dropping and recreating operator classes is easier to
handle than playing strange tricks with ALTER OPERATOR CLASS GROUP. And
probably easier to get right/harder to screw up.

After further thought I'm beginning to see the merits of this
suggestion. The consideration that drives it is this: what is an index
going to depend on in pg_depends? If we have a massive operator class
handling multiple types, we certainly don't want to have to drop every
index using that opclass if we want to drop just one of the datatypes.
(This would be especially true for things like "numeric_ops" which would
support both user indexes and system catalogs ... after adding "tinyint"
to that, what if you want to back it out again?) So it seems like in a
multi-type-operator-class system there'd still have to be an explicit
notion of an opclass-and-indexed-datatype combination --- which we might
as well keep calling an operator class for old times' sake. So we're
back to calling the larger structure an "operator class group" unless
someone's got a better idea.

However, thinking about the effects of DROP leads me to suggest that an
operator class in this sense should ideally contain only the "core"
stuff that you must have to support an index on a column of its
datatype. In particular, cross-type comparisons are generally not
"core", and could be dropped without breaking indexes that use the
class. So I suggest that cross-type comparison operators could be
declared to be members of an operator class group but not directly
members of any one of its operator classes.

In other words the object hierarchy looks like

Operator class group

Operator class

"core" ops and support functions for class

Operator class

"core" ops and support functions for class

...

Cross-type ops and support functions

The dependencies would be set up so that dropping a "core" operator
forces dropping its operator class and any dependent indexes, same
as today. But dropping a cross-type op doesn't force anything,
and an operator class group per se never goes away unless explicitly
destroyed. (It could validly exist with no contained objects, in
fact that would be its initial state.)

I think the CREATE OPERATOR CLASS GROUP command becomes just

CREATE OPERATOR CLASS GROUP name USING am;

and then you add opclasses to it by creating them with a GROUP
option used in CREATE OPERATOR CLASS, and/or add individual cross-type
ops to it with an ALTER command that would look like

ALTER OPERATOR CLASS GROUP name ADD { OPERATOR ... | FUNCTION ... } ...

As now, there's no ALTER OPERATOR CLASS, you can only drop the whole
thing (with any dependent indexes) and re-create it. This seems a good
idea because we lack any infrastructure for rebuilding dependent indexes
after an opclass redefinition. That doesn't seem like a problem for
fooling with individual cross-type ops in a class group though.

For backwards compatibility, we'd still accept cross-type ops listed in
CREATE OPERATOR CLASS, but this would be deprecated for the reason that
dropping such an op would force dropping the class (as indeed it does
today) and obviously you'd rather not have indexes dependent on non-core
operators. Note that which operators are "core" to an opclass is not
hardwired into this structure, it's the class author's choice.

How the backend implements it may be easier as one single large
opclass. Essentially the operater class table becomes merely a
placeholder for the name (maybe also aliases?), which can still be used
in index declarations, but is never used by the backend otherwise.

To represent this cleanly in the catalogs, we'd probably want nominally
stand-alone opclasses to belong to implicitly created single-member
groups, because the individual entries in pg_amop and pg_amproc are
always going to be shown as belonging to groups --- the membership
hierarchy above is only interesting in pg_depends, not for index
operations. I think that's about the same thing you're saying here.

Comments?

regards, tom lane

On Thu, Dec 14, 2006 at 08:31:59PM -0500, Tom Lane wrote:

How the backend implements it may be easier as one single large
opclass. Essentially the operater class table becomes merely a
placeholder for the name (maybe also aliases?), which can still be used
in index declarations, but is never used by the backend otherwise.

To represent this cleanly in the catalogs, we'd probably want nominally
stand-alone opclasses to belong to implicitly created single-member
groups, because the individual entries in pg_amop and pg_amproc are
always going to be shown as belonging to groups --- the membership
hierarchy above is only interesting in pg_depends, not for index
operations. I think that's about the same thing you're saying here.

I think we're on the same page. I thought of another motivation also:
protections/permissions. We don't currently allow people to mess with
definitions needed by system catalogs, so you don't want to allow users
to mess with the btree(int4) class, but you want to allow them to
modify the group as a whole to add new things and remove things they've
added.

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/

Martijn van Oosterhout <kleptog@svana.org> writes:

I think we're on the same page. I thought of another motivation also:
protections/permissions. We don't currently allow people to mess with
definitions needed by system catalogs, so you don't want to allow users
to mess with the btree(int4) class, but you want to allow them to
modify the group as a whole to add new things and remove things they've
added.

Yeah. We're a long way from letting non-superusers manipulate opclass
definitions, but it'd be good if the structure were not one that would
forbid using permissions in future.

I'm still not real happy with the phrase "operator class group"; it
seems unwieldy, and it's not even technically accurate in this design,
since the structure can contain operators directly not only operator
classes. What do people think about calling it just an "operator
group"? That's sort of reasonable since really what we're doing is
saying that all these operators are compatible. (A lot of the things
the planner wants to do with this info have nothing to do with indexes
anyway.)

The main objection I can think of is that a novice seeing the terms
"operator class" and "operator group" isn't going to have any context
to know which is which, but I'm not sure that we can devise any terms
that would help much.

regards, tom lane

"Tom Lane" <tgl@sss.pgh.pa.us> writes:

The main objection I can think of is that a novice seeing the terms
"operator class" and "operator group" isn't going to have any context
to know which is which, but I'm not sure that we can devise any terms
that would help much.

Operator Superclass ?

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

Gregory Stark <stark@enterprisedb.com> writes:

Operator Superclass ?

Yeah, I thought about that too, but I don't like it much ... can't
entirely put my finger on why not, except that class/superclass usually
implies that the objects you're talking about are all the same kind of
thing, whereas what we have here is a very definite distinction between
two kinds of objects. On the same grounds, I'd object to calling
schemas "directories" or "folders", unless they could be nested.

regards, tom lane

"Tom Lane" <tgl@sss.pgh.pa.us> writes:

Gregory Stark <stark@enterprisedb.com> writes:

Operator Superclass ?

Yeah, I thought about that too, but I don't like it much ... can't
entirely put my finger on why not, except that class/superclass usually
implies that the objects you're talking about are all the same kind of
thing, whereas what we have here is a very definite distinction between
two kinds of objects.

I'm kind of glad to hear that since I had similar discomfort with it myself. I
thought it might be the least worst option though so I figured I would say it
out loud.

Perhaps something like

Operator Class
and
Data Type Class

Data type classes happens to involve operator classes but it sounds like
you're looking for them to specify other behaviours of how data types
inter-relate than just their operator classes anyways.

On the same grounds, I'd object to calling schemas "directories" or
"folders", unless they could be nested.

(Actually that's a bit of an odd case since real-world folders aren't
generally nestable and actually many early operating systems didn't allow them
to be nested either. We're just so used to the computer metaphor that we
forget what it's originally supposed to represent.)

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

Gregory Stark <stark@enterprisedb.com> writes:

Perhaps something like

Operator Class
and
Data Type Class

Data type classes happens to involve operator classes but it sounds like
you're looking for them to specify other behaviours of how data types
inter-relate than just their operator classes anyways.

Well, actually I think of this more as something that tells me how a
bunch of *operators* relate. As an example, "=" and friends over the
string datatypes will be one group, and "~=~" and friends will be
another group over the very same types. So to me "data type class"
would really miss the point.

The alternatives I'd been thinking about were "operator set" and
"operator collection", but I don't really see any advantage over
"operator group" for either ...

On the same grounds, I'd object to calling schemas "directories" or
"folders", unless they could be nested.

(Actually that's a bit of an odd case since real-world folders aren't
generally nestable

True, ya got me ;-)

regards, tom lane

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Fri, Dec 15, 2006 at 06:44:10PM -0500, Tom Lane wrote:

Gregory Stark <stark@enterprisedb.com> writes:

Operator Superclass ?

Yeah, I thought about that too, but I don't like it much ... can't
entirely put my finger on why not [...]

I think I can ;-)

"Operator class group", unwieldy as it is, conveys the meaning that we
are talking about _sets of operator classes_. The nicer terms I have
seen all lose a bit of that ring to me.

Regards
- -- tomás
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFFg4aYBcgs9XrR2kYRAp1mAJ9+ISc7Ex1qCBV2dKgNJSUAOSmR/ACeKt6O
KKp1DI9OkSrlO4VpJbb2xFM=
=KDb3
-----END PGP SIGNATURE-----