From: Tom Lane <tgl@sss.pgh.pa.us>
To: Craig James <cjames@emolecules.com>
Cc: Jim Nasby <Jim.Nasby@bluetreble.com>
Cc: Mike Sofen <msofen@runbox.com>
Cc: pgsql-performance@postgresql.org <pgsql-performance@postgresql.org>
Subject: Re: Slow query with big tables
Date: Sat, 27 Aug 2016 12:36:56 -0400
Message-ID: <6955.1472315816@sss.pgh.pa.us> (raw)
In-Reply-To: <CAFwQ8rcGGeVk0Gayz1QEP+VMp8AQi8O-f=OtbtR5T2OXVp8iiQ@mail.gmail.com>
References: <CAOLG3nrKEuAe2NEQK-z65X5H_i22Vg3tDpB=KYJ9ai07dYxNGA@mail.gmail.com>
<CAFwQ8rfgqxg0As4DvK9sku2o-7SKGhMp0hS_YU6h_REHOPdXjg@mail.gmail.com>
<CAOLG3nq-KjLF1S-5Hq3pnE96y6itXi-Sq0_SXJYpeOfxebvLdA@mail.gmail.com>
<00e601d1ffd8$2beb8850$83c298f0$@runbox.com>
<1b6396d4-ca7d-05a1-51c7-3b1d71c6cd55@BlueTreble.com>
<CAFwQ8rcGGeVk0Gayz1QEP+VMp8AQi8O-f=OtbtR5T2OXVp8iiQ@mail.gmail.com>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-performance>
Craig James <cjames@emolecules.com> writes:
> Straight hash-table indexes (which Postgres doesn't use) have O(1) access
> time. The amount of data has no effect on the access time.
This is wishful thinking --- once you have enough data, O(1) goes out the
window. For example, a hash index is certainly not going to continue to
scale linearly once you reach its maximum possible number of buckets
(2^N for N-bit hashes, and remember you can't get very many useful hash
bits out of small objects like integers). But even before that, large
numbers of buckets put enough stress on your storage system that you will
see some not very O(1)-ish behavior, just because too little of the index
fits in whatever cache and RAM you have. Any storage hierarchy is
ultimately going to impose O(log N) access costs, that's the way they're
built.
I think it's fairly pointless to discuss such matters in the abstract.
If you want to make useful engineering tradeoffs you have to talk about
specific data sets and available hardware.
regards, tom lane
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: tgl@sss.pgh.pa.us, cjames@emolecules.com, Jim.Nasby@bluetreble.com, msofen@runbox.com
Subject: Re: Slow query with big tables
In-Reply-To: <6955.1472315816@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox