PG10 Crash-safe and replicable Hash Indexes and UNIQUE

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

PG10 Crash-safe and replicable Hash Indexes and UNIQUE

Chapman Flack
Hi,

The item on hash indexes reminded me of an old comment from years
ago that I put in the code of the first custom PG datatype I ever
built at $work:

COMMENT ON OPERATOR CLASS puid_ops USING btree IS
'As puids are only identifiers, there is no obvious reason to define
ordering operators or support btree indexing. But for some curious
reason PostgreSQL 8.4 does not allow a hash index to support UNIQUE
constraints (this may be because, per the manual, hash index "operations
are not presently WAL-logged" so it could be risky to base constraints
on them). Therefore, the whole set of ordering operators must be
implemented to provide an operator class for the btree index method.';

Was my guess about the reason right? Does this PG10 announcement
also mean it will be possible to use UNIQUE constraints with some
pure-identifier, no-natural-ordering type that supports only hashing?

-Chap


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: PG10 Crash-safe and replicable Hash Indexes and UNIQUE

Tom Lane-2
Chapman Flack <[hidden email]> writes:
> Was my guess about the reason right? Does this PG10 announcement
> also mean it will be possible to use UNIQUE constraints with some
> pure-identifier, no-natural-ordering type that supports only hashing?

No, nobody's done anything about allowing hash indexes to support
uniqueness AFAIK.  I don't have a clear picture of how much work
it would be, but it would likely be more than trivial effort;
there's definitely extra code in btree that supports that.

(You might be right about the big picture, in that no one wanted to
bother with working on that as long as hash indexes weren't crash
safe.  But there's not a technical connection.)

                        regards, tom lane


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: PG10 Crash-safe and replicable Hash Indexes and UNIQUE

Chapman Flack
On 05/19/17 11:41, Tom Lane wrote:

> No, nobody's done anything about allowing hash indexes to support
> uniqueness AFAIK.  I don't have a clear picture of how much work
> it would be, but it would likely be more than trivial effort;

I see what you mean. Because of the way hash values are ordered
(to allow binary search) within a page, but not between pages of
a bucket, insertion as it stands now is able to stop as soon as
it finds any page with room for the entry, but a unique-insertion
will have to check every page of the bucket for matching hashes,
and then (because only the hash and tid are in the index) chase
any of those to the heap to compare the value.

Maybe both hash collisions and overflow pages are rare enough
in practice with reasonable data that the performance impact
of that would be small, but still the possibility has to be
accounted for, the locking may get hairier (do you now keep
the lock you have on the page where room was found for the entry,
and use another lock to walk the remaining pages until sure
there's no duplicate?).

At least I see that interest in UNIQUE for hash indexes has been
shown on -hackers several times over the years, and is on the TODO.
Neil Conway seems to have had an idea [1] for making the locking work,
14 years ago (however relevant that might be to today's code).

... and one inquiry last year [2] did seem to get tabled because of the
lack of WAL logging, which is now a non-blocker.

I haven't seen much discussion of /why/ one would want hash-based UNIQUE.
I know my own reasons, but I'm not sure how persuasive they are in light
of the implementation realities, so maybe that makes such a discussion
worthwhile. I can start; these are the two reasons I had:

1. To a naive intuition (especially one raised more on in-memory data
   structures than the guts of databases), it just seems natural:
   hashing seems like the canonical approach to uniqueness testing
   where there's no need for ordering, intuition suggests a performance
   advantage, and so the least-astonishment principle suffers upon finding
   it isn't supported.

2. When developing a custom data type, it feels like tedious
   busy-work to have to bang out a full set of ordering operators
   for a btree operator class if there is no meaningful order for
   the type.

Maybe the intuitions behind (1) are just misinformed, the performance
ones at least, in light of Craig Ringer's low opinion of whether "hash
indexes are better than btree for anything" [3], and André Barbosa's
more recent performance comparison [4] (which does show some advantages
for hash in some circumstances, but mostly not large. The only large
advantage was in initial creation; would that be hashsort.c at work?).

But then, both [3] and [4] predate the recent projects on hash indexes
that have "made them crash safe and are on the way to making them
performant" [5], so maybe an updated comparison would be timely, or some
addition to the docs to better characterize the circumstances where hash
could be good. (Every index method newer than btree and hash has its own
part VII Internals chapter; for completeness, might it make sense to have
those for btree and hash also, even if only to broadly discuss
the conditions under which they perform especially well or poorly?)

For all sorts of indexes, would there be any use for some CREATE INDEX
syntax for a multicolumn index to say that some of its rightmost columns
aren't there to participate in the indexing scheme, but only to benefit
index-only scans? Applied to a hash index, that might offer another useful
kind of multicolumn support, which otherwise seems limited to queries
where you have the exact values of all indexed columns.

Anyway, even if my performance assumption behind (1) was too optimistic,
the astonishment when a new user finds a hash can't support uniqueness
still seems real. A related astonishment is that a hash opclass can't
support DISTINCT, and that seems like something that could be changed
with much less work than making hash indexes amcanunique. Apparently,
array comparison already looks for a btree opclass but can fall back to
a hash one, if present, for equality comparisons. Would it be difficult
to do the same for DISTINCT?

As for my reason (2), the tedium of having to bang out btree operators
for a new type with no meaningful order (which, as I've just remembered,
is necessary not just for UNIQUE constraints but even just to make
SELECT DISTINCT work), maybe there's a solution that simply reduces
the tedium. After all, if a new type has no meaningful notion of order,
an arbitrary one imposed by copy/paste of some existing opclass
for a type with the same internallength might often be good enough.
Could there be some syntactic sugar for that, say,

CREATE OPERATOR CLASS btree_foo_ops
FOR TYPE foo USING btree LIKE int4_ops;

? A transformOpclassLike function could verify that foo and the opcintype
of int4_ops have the same typlen and typbyval, and that the operators and
support procs are backed by C functions, and return a list of
CREATE OPERATOR reusing the same functions, followed by the rewritten
CREATE OPERATOR CLASS.

Would it be helpful to link any part of these notes to the hash index
section of the TODO page?

-Chap


[1]: https://www.postgresql.org/message-id/1063758747.24276.29.camel%40tokyo
[2]: https://www.postgresql.org/message-id/23242.1454609521%40sss.pgh.pa.us
[3]: http://stackoverflow.com/questions/24568157   in a comment
[4]: http://blog.andrebarbosa.co/hash-indexes-on-postgres/
[5]:
https://www.postgresql.org/message-id/CA%2BTgmoZTMWkGdv8302RmvMNTdqhL9LkNzEXcswseUmhZ%3DO8wgA%40mail.gmail.com


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: PG10 Crash-safe and replicable Hash Indexes and UNIQUE

akapila
On Mon, May 22, 2017 at 8:31 AM, Chapman Flack <[hidden email]> wrote:

> On 05/19/17 11:41, Tom Lane wrote:
>
>> No, nobody's done anything about allowing hash indexes to support
>> uniqueness AFAIK.  I don't have a clear picture of how much work
>> it would be, but it would likely be more than trivial effort;
>
> I see what you mean. Because of the way hash values are ordered
> (to allow binary search) within a page, but not between pages of
> a bucket, insertion as it stands now is able to stop as soon as
> it finds any page with room for the entry, but a unique-insertion
> will have to check every page of the bucket for matching hashes,
> and then (because only the hash and tid are in the index) chase
> any of those to the heap to compare the value.
>
> Maybe both hash collisions and overflow pages are rare enough
> in practice with reasonable data that the performance impact
> of that would be small, but still the possibility has to be
> accounted for, the locking may get hairier (do you now keep
> the lock you have on the page where room was found for the entry,
> and use another lock to walk the remaining pages until sure
> there's no duplicate?).
>
> At least I see that interest in UNIQUE for hash indexes has been
> shown on -hackers several times over the years, and is on the TODO.
> Neil Conway seems to have had an idea [1] for making the locking work,
> 14 years ago (however relevant that might be to today's code).
>

I think that won't be directly applicable now as we have changed the
locking mechanism such that instead of acquiring heavy-weight locks it
uses LWLocks and for inserts and we don't hold it for more than one
bucket page at a time for inserts.  I think to make unique check work,
there are a couple of options like (a) unique insertions can always
acquire a cleanup lock on bucket page, this will work because scans
(to find duplicate values in overflow pages will hold a pin on bucket
page).  The drawback will be that unique insertions need to wait even
when there is some unrelated scan is in progress.  (b) unique
insertions can hold locks on bucket pages while traversing the bucket
chain.  It is bad to retain locks on multiple buckets for concurrency,
but in practise, unqiue indexes won't have many overflow pages. (c)
keep a flag in bucket page to indicate unique index insertion is in
progress and if such a flag is set, other insertions need to wait.  I
think this is not a preferable way because we need to take care of
clearing such a flag not only after the operation but also after crash
recovery.

Any better ideas?

> ... and one inquiry last year [2] did seem to get tabled because of the
> lack of WAL logging, which is now a non-blocker.
>
> I haven't seen much discussion of /why/ one would want hash-based UNIQUE.
> I know my own reasons, but I'm not sure how persuasive they are in light
> of the implementation realities, so maybe that makes such a discussion
> worthwhile. I can start; these are the two reasons I had:
>
> 1. To a naive intuition (especially one raised more on in-memory data
>    structures than the guts of databases), it just seems natural:
>    hashing seems like the canonical approach to uniqueness testing
>    where there's no need for ordering, intuition suggests a performance
>    advantage, and so the least-astonishment principle suffers upon finding
>    it isn't supported.
>
> 2. When developing a custom data type, it feels like tedious
>    busy-work to have to bang out a full set of ordering operators
>    for a btree operator class if there is no meaningful order for
>    the type.
>
> Maybe the intuitions behind (1) are just misinformed, the performance
> ones at least, in light of Craig Ringer's low opinion of whether "hash
> indexes are better than btree for anything" [3], and André Barbosa's
> more recent performance comparison [4] (which does show some advantages
> for hash in some circumstances, but mostly not large. The only large
> advantage was in initial creation; would that be hashsort.c at work?).
>
> But then, both [3] and [4] predate the recent projects on hash indexes
> that have "made them crash safe and are on the way to making them
> performant" [5], so maybe an updated comparison would be timely, or some
> addition to the docs to better characterize the circumstances where hash
> could be good.
>

I think the performance characteristics of hash indexes have changed
especially for read-only cases after recent work.  We have done many
tests which indicate that hash indexes perform better than btree when
the column value is unique.  You might want to try that based on your
usecase.

> (Every index method newer than btree and hash has its own
> part VII Internals chapter; for completeness, might it make sense to have
> those for btree and hash also, even if only to broadly discuss
> the conditions under which they perform especially well or poorly?)
>
> For all sorts of indexes, would there be any use for some CREATE INDEX
> syntax for a multicolumn index to say that some of its rightmost columns
> aren't there to participate in the indexing scheme, but only to benefit
> index-only scans? Applied to a hash index, that might offer another useful
> kind of multicolumn support, which otherwise seems limited to queries
> where you have the exact values of all indexed columns.
>

Agreed, but even if we have any such syntax, making it work for hash
indexes is tricky, because we currently store the hash code in the
index, not the original hash index key.

--
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: PG10 Crash-safe and replicable Hash Indexes and UNIQUE

Chapman Flack
On 05/22/2017 05:16 AM, Amit Kapila wrote:
> Agreed, but even if we have any such syntax, making it work for hash
> indexes is tricky, because we currently store the hash code in the
> index, not the original hash index key.

That was what gave me the idea in the first place, which then
I realized could be more generally useful. If I could say
something like

CREATE INDEX ON foo USING btree ( bar, baz ALSO quux );

so that only bar and baz are compared in insertion and search,
but quux is along for the ride and available to index-only scans,
then the (admittedly weird) syntax

CREATE INDEX ON foo USING hash ( bar ALSO bar );

could be taken to mean that the value of bar as well as its hash
is wanted in the index. I was first thinking of that to save
unique-insert from running to the heap to check hash collisions,
though on second thought if collisions are common enough for that
to be a win, maybe the hash function's just wrong. It could still
be useful for index-only scans.

-Chap



--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: PG10 Crash-safe and replicable Hash Indexes and UNIQUE

Alvaro Herrera-9
Chapman Flack wrote:

> That was what gave me the idea in the first place, which then
> I realized could be more generally useful. If I could say
> something like
>
> CREATE INDEX ON foo USING btree ( bar, baz ALSO quux );
>
> so that only bar and baz are compared in insertion and search,
> but quux is along for the ride and available to index-only scans,

INCLUDING:
https://www.postgresql.org/message-id/56168952.4010101@...

--
Álvaro Herrera                https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: PG10 Crash-safe and replicable Hash Indexes and UNIQUE

Chapman Flack
On 05/22/17 18:39, Alvaro Herrera wrote:
> Chapman Flack wrote:
>> CREATE INDEX ON foo USING btree ( bar, baz ALSO quux );
>
> INCLUDING:
> https://www.postgresql.org/message-id/56168952.4010101@...

I'd buy that.

-Chap


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Reply | Threaded
Open this post in threaded view
|

Re: PG10 Crash-safe and replicable Hash Indexes and UNIQUE

Bruce Momjian
In reply to this post by Chapman Flack
On Sun, May 21, 2017 at 11:01:57PM -0400, Chapman Flack wrote:
> ? A transformOpclassLike function could verify that foo and the opcintype
> of int4_ops have the same typlen and typbyval, and that the operators and
> support procs are backed by C functions, and return a list of
> CREATE OPERATOR reusing the same functions, followed by the rewritten
> CREATE OPERATOR CLASS.
>
> Would it be helpful to link any part of these notes to the hash index
> section of the TODO page?

I added a link to this excellent summary email based on the first
paragraph alone:

        Add UNIQUE capability to hash indexes

then when I got to your suggestion at the bottom, it was already done.
:-)

--
  Bruce Momjian  <[hidden email]>        http://momjian.us
  EnterpriseDB                             http://enterprisedb.com

+ As you are, so once was I.  As I am, so you will be. +
+                      Ancient Roman grave inscription +


--
Sent via pgsql-hackers mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Previous Thread Next Thread