Incremental aggregate/rollup strategy advice

[Morris de Oryx]

I'm researching strategies for incrementally updating aggregate/rollup
tables. The problem is how to do so without double-counting changes, and
not skipping changes. I know enough about concurrency issues to ask the
question, but do *not* know enough about the features and details of
Postgres' concurrency management to figure out a 100% reliable solution
without some help. And, with concurrency-related stuff, you're either 100%
right or you're buggy.

And *thanks in advance* to anyone who can help out. I'm not good at writing
short :( I've tried to put in enough detail to get to the point, which is
"how do I find unprocessed records without missing any."

Okay, the setup is that we've got a lot of tables where we would like to do
incremental aggregates. To simplify things, mostly these are INSERT-only
tables, sometimes UPDATE, not worrying about DELETE yet. A couple of
strategies I'd like to avoid:

* Full queries will take too long, and will scale poorly. So, MATERIALIZED
VIEW is unappealing. So, rollup tables as it's possible to update them
incrementally.

* We may have multiple aggregates off the same base data, and may change
them over time. So, putting some kind of flag field in the source table
doesn't really fit.

* I was thinking about a posting/diff/delta/audit-like table, but that's a
pretty "heavy" solution. You need some kind of ON AFTER INSERT/UPDATE
selection-based trigger to push over the data that's needed to update the
aggregates. Which, again, means the source table needs to know what
aggregations are going to take place. Plus, it's just a ton of churn and
extra data...when all of necessary data exists in the source table already.

* I saw one strategy that looks good from the folks at CitusData:
https://www.citusdata.com/blog/2018/06/14/scalable-incremental-data-aggregation/

Briefly, they use a bigserial counter which, I guess, is not
transaction-bound so that record insertions have a chronological stamp. 1,
2, 3, etc. This is a design familiar to me from other environments and is
sometimes called a "concurrency ID." In our case, we need to support UPDATE
as well, so I don't think the sequence idea will work (?) To make this more
concrete, here's a simplified table with source data:

CREATE TABLE "error_report" (
"id" uuid NOT NULL DEFAULT extensions.gen_random_uuid(), -- We've got
distributed sources, so UUIDs for IDs.
"error_name" text NOT NULL DEFAULT false,-- Something we'll
summarize by.
"facility_id" uuid NOT NULL DEFAULT NULL,-- Something we'll
summarize by.
"error_dts" timestamptz NOT NULL DEFAULT NULL,   -- Set on the
source machine in UTC
"last_updated_dts" timestamptz NOT NULL DEFAULT NULL);   -- Set on Postgres
after INSERT or UPDATE.

The idea is that you have a stable number line as a number or a timestamp.
We use timestamptz and store everything in UTC. Otherwise, it's the same
basic idea as what the CitusData folks said: You have an ever-increasing
number line so that you can mark where you've processed to. This way, you
can fetch unprocessed rows without missing any, without a flag field the
source table, and without an audit table/change queue of any kind. I've
simplified the timestamps below for legibility to spell this out, as it's
the crux of my question about Postgres specifics. And, just pretend that
these rows are all on page 0...I've faked ctid values to make the rows
easier to keep track of.

ctid   last_updated_dts
(0,1)  2018-09-25 05:53:00
(0,2)  2018-09-25 05:54:00
(0,3)  2018-09-25 05:55:00
(0,3)  2018-09-25 05:55:00
(0,4)  2018-09-26 02:23:00
(0,5)  2018-09-26 03:14:00
(0,6)  2018-09-26 03:15:00
(0,7)  2018-09-28 05:10:00
(0,8)  2018-09-28 05:14:00
(0,9)  2018-09-28 05:15:00
(0,10) 2018-09-28 05:15:00

You need a small utility table to hold details about which records you've
aggregated or processed.

CREATE TABLE "rollup_status" (
"id" uuid NOT NULL DEFAULT extensions.gen_random_uuid(), -- We use UUIDs,
not necessary here, but it's what we use.
"rollup_name" text NOT NULL DEFAULT false,
"last_processed_dts" timestamptz NOT NULL DEFAULT NULL); -- Marks the last
timestamp processed.

Now imagine that I've got a rollup_status record

rollup_name last_processed_dts
error_name_counts   2018-09-26 02:23:00

If I search for rows that were modified after the "processed until", I get
these:

ctid   last_updated_dts
(0,5)  2018-09-26 03:14:00
(0,6)  2018-09-26 03:15:00
(0,7)  2018-09-28 05:10:00
(0,8)  2018-09-28 05:14:00
(0,9)  2018-09-28 05:15:00
(0,10) 2018-09-28 05:15:00

And update the max(last_updated_dts) in the rollup_detail record:

rollup_name last_processed_dts
error_name_counts   2018-09-28 05:15:00

So, I got a chunk of the timeline, recorded how far I went, and processed
those records. The beauty part of this technique, if I can get it
implemented correctly, is that this doesn't have to block new records.
While I'm processing those 5 (or 5K), new records can be added onto the end
of error_report and,

Re: Incremental aggregate/rollup strategy advice

[Morris de Oryx]

Tatsuo,

Thank you for your response, I have followed the discussion on Hackers with
interest. I hope that your efforts are a great success! In my case, I need
to find a solution available in shipping versions of Postgres. But, since
you've joined in, I'm curious: What is the advantage of a materialized view
over a real table? It seems like the update semantics and mechanics are
more straightforward with a table.

Re: Incremental aggregate/rollup strategy advice

[Morris de Oryx]

Thanks Steven, nice suggestions. I should have mentioned that the
deployment setup is on RDS on PG 11.x, which rules out those extensions.
I've looked at TimescaleDB several times, and it looks pretty great.

I've now read through some of the archives from years back when
pg_xact_commit_timestamp was still in development, and I'm thinking it
might be the right solution. I'm still not clear how long timestamps are
held, or what the overhead is. It sounds like commit timestamps might be
exactly the same, but that's fine for me. So long as they're never in the
past, it doesn't matter how many timestamps are the same.

Re: Aggregate functions on groups

[Morris de Oryx]

Your tributaries and fish master tables make sense. If I read your code
right, you're grouping by too many columns. I flattened the data into a
survey table for this simple example:

select tributary,
   common_name,
   scientific_name,
   sum(count_value) as fish_seen,
   count(count_value) as observations_made

   from survey

   group by 1,2,3 -- The GROUP BY clause can use positions on the select
list, if you feel like typing less.


tributary  common_name scientific_name
   fish_seen  observations_made
Anderson Creek trib to Nehalem River   Black crappie   Pomoxis
nigromaculatus 3  2
Anderson Creek trib to Nehalem River   Brook trout Salvelinus
fontinalis  3  2
Anderson Creek trib to Nehalem River   BluegillLepomis macrochirus
   3  2
Anderson Creek trib to Nehalem River   Brown bullhead  Ameiurus nebulosus
  3  2

But this is not why I'm answering. I'm responding as I wanted to make sure
that you're aware of the pg-similarity extension:

https://salsa.debian.org/postgresql/pg-similarity

This tool implements a *lot* of similarity measures for fuzzy cmparisons.
Some are sting-oriented algorithms (Jaro-Winkler, Soundex, Levenshtein,
etc.), and others derive from and/or apply to field population comparisons,
like the Jaccard and Dice Coefficients. There's a lot of great stuff in the
package.

On Sat, Aug 31, 2019 at 3:14 AM Rich Shepard 
wrote:

> Tables hold data on fish counts by stream name, species, and (unreported)
> collection dates. I'm trying to write a query that returns the total number
> of each species in each stream.
>
> The latest attempt is (lines wrapped by alpine; submitted as one line):
>
> \copy (select f.stream_tribs, f.count_value, sum(f.count_value),
> i.common_name, i.sci_name  from fish_counts as f, itis as i where
> f.stream_tribs like '%Nehalem River%' group by f.stream_tribs,
> i.common_name, i.sci_name, f.count_value  order by f.stream_tribs,
> i.common_name, i.sci_name, f.count_value) to
> '/home/rshepard/projects/oregon/mohler_sand/data/fish/fishes.dat';
>
> The returned set starts this way:
>
> Anderson Creek trib to Nehalem River0   0   Black crappie
>  Pomoxis nigromaculatus
> Anderson Creek trib to Nehalem River3   3   Black crappie
>  Pomoxis nigromaculatus
> Anderson Creek trib to Nehalem River0   0   Bluegill
> Lepomis macrochirus
> Anderson Creek trib to Nehalem River3   3   Bluegill
> Lepomis macrochirus
> Anderson Creek trib to Nehalem River0   0   Brook trout
>  Salvelinus fontinalis
> Anderson Creek trib to Nehalem River3   3   Brook trout
>  Salvelinus fontinalis
> Anderson Creek trib to Nehalem River0   0   Brown bullhead
> Ameiurus nebulosus
> Anderson Creek trib to Nehalem River3   3   Brown bullhead
> Ameiurus nebulosus
>
> What I want returned would look like this:
>
> Anderson Creek trib to Nehalem River  Black crappie  Pomoxis
> nigromaculatus 3
> Anderson Creek trib to Nehalem River  Bluegill   Lepomis macrochirus
>   3
> Anderson Creek trib to Nehalem River  Brook troutSalvelinus
> fontinalis  3
> Anderson Creek trib to Nehalem River  Brown bullhead Ameiurus nebulosus
>  3
>
> I've read the manual yet must have not seen the section explaining how to
> apply aggregate functions to groups.
>
> Thanks in advance,
>
> Rich
>
>
>

Re: FW: Re: FW: Re: Shouldn;t this trigger be called?

[Morris de Oryx]

I see that you've already been pointed at citext, but I don't think a CHECK
constraint has been mentioned. In case it hasn't, what about something like
this?

   ADD CONSTRAINT check_activity_status
CHECK (activity_status = 'ACTIVE' OR activity_status = 'INACTIVE');

I'm kind of allergic to ENUM...maybe that's just me. But since you're
considering it, maybe it's the perfect time to consider all of your
options. Such as a linked lookup table of defined allowed values (feels
silly with two values), a domain (not entirely fit to purpose), or the
CHECK constraint above. And, yeah, if it's only ever ACTIVE or INACTIVE,
I'd normally make a Boolean named something like active, as Adrian Klaver
mentioned. That's easy to reason about, and it makes it unambiguous that
there are two and only two possible states..

Re: FW: Re: FW: Re: Shouldn;t this trigger be called?

[Morris de Oryx]

citext is an extension, so you have to install it:

CREATE EXTENSION citext;

That's the simplest form. you can install it into a specific schema, test
for existence, etc. Check out the CREATE EXTENSION docs here:

https://www.postgresql.org/docs/current/sql-createextension.html

Re: citext, actually probably using extensions

[Morris de Oryx]

Not sure about best practices, but what I'm going is like this:

* Create a schema named extensions.

* Install extensions in this special schema only. I don't put anything else
in there.

* Put the extensions schema early (left) in the search_path for each role.

* Grant execute access permissively on the functions in that schema.

If there's something deeply flawed about this strategy, I'd be keen to hear
about it. On the positive side, I find it simple to understand, maintain,
and explain to other people. YMMV

Re: Phone number type extension

[Morris de Oryx]

For clarification, what do you mean by "phone number"? I'm not being dense,
I'm wondering if you're looking for a type that handles only numbers from
one country, or that can deal with the rules for a variety of countries.

Re: Redis 16 times faster than Postgres?

[Morris de Oryx]

Sigh. I despair of "16x faster" and "20x faster" headlines that ignore the
raw numbers. *The worst numbers in there are far below the threshold of
user perception*. Unless these results are compounded by running in a loop,
they are meaningless. Not immeasurable, just meaningless.

https://www.nngroup.com/articles/response-times-3-important-limits/

That piece is from 1993, but the human nervous system hasn't changed since
then.

Re: Redis 16 times faster than Postgres?

[Morris de Oryx]

> Back-end web servers don't have human nervous systems. Faster response
time means that a give bit of hardware can support
>  a much higher load, saving you money

Fair point, I can't argue against it as stated. Although I have no way of
know if this person's site is *ever* overloaded or has any chance of saving
money. Other sites do for sure. Not knocking using in-memory caches, they
can be a life-saver.

Like everyone else here, I've been to a *lot* of meetings down the year
that came down to arguing about optimizations that could not pay for
themselves before the heat death of the universe. As such, I've developed
an allergy to context-free performance comparisons.

On Mon, Sep 30, 2019 at 10:25 AM Ron  wrote:

> On 9/29/19 7:01 PM, Morris de Oryx wrote:
>
> Sigh. I despair of "16x faster" and "20x faster" headlines that ignore the
> raw numbers. *The worst numbers in there are far below the threshold of
> user perception*. Unless these results are compounded by running in a
> loop, they are meaningless. Not immeasurable, just meaningless.
>
> https://www.nngroup.com/articles/response-times-3-important-limits/
>
> That piece is from 1993, but the human nervous system hasn't changed since
> then.
>
>
> Back-end web servers don't have human nervous systems. Faster response
> time means that a give bit of hardware can support a much higher load,
> saving you money
>
> --
> Angular momentum makes the world go 'round.
>

Re: Case Insensitive Comparison with Postgres 12

[Morris de Oryx]

As I understand it, custom collation are not applied globally. Meaning, you
have to associate a collation with a column or en expression with COLLATE.

Has there been any discussion of custom dictionaries being defined in the database?

[Morris de Oryx]

I've been experimenting with the FTS features in Postgres over the past few
days. Mind blow.

We're deployed on RDS, which does not give you any file system to access.
I'd love to be able to create a custom thesaurus dictionary for our
situation, which seems like it is impossible in a setup like ours.

Has there been any discussion of making dictionary configuration files
accessible via a dictionary table instead of a physical, structured disk
file? Or, alternatively, something that could be accessed
remotely/externally as a URL or FDW?

Thanks for any comments.

Re: Has there been any discussion of custom dictionaries being defined in the database?

[Morris de Oryx]

Fair.

Given that Amazon is bragging this week about turning off Oracle, it seems
like they could kick some resources towards contributing something to the
Postgres project. With that in mind, is the idea of defining dictionaries
within a table somehow meritless, or unexpectedly difficult?

Re: Has there been any discussion of custom dictionaries being defined in the database?

[Morris de Oryx]

Nope, no custom C installs. RDS is super convenient in many ways, but also
limited. You can't, for example, run TimeScale, install RUM indexes (if
those still work), or any novel plugins. And you can't do anything at all
requiring a file reference. The backup features are outstanding. But, yeah,
sometimes frustrating.

ERROR: could not find tuple for statistics object - is there a way to clean this up?

[Morris de Oryx]

I've been experimenting with CREATE STATISTICS to declare some functionally
dependent columns. Right now, I'm working with a local copy of Postgres
running on this version:

PostgreSQL 12.5 on x86_64-apple-darwin16.7.0, compiled by Apple LLVM
version 8.1.0 (clang-802.0.42), 64-bit

We deploy on RDS, also in the 12.x line.

Here's an example of the DROP:
DROP TABLE data.samples CASCADE;And

And here's the error that I get back:

ERROR:  could not find tuple for statistics object 147574.

I'm out of my depth here. pg_statistic_ext does not have any row with an
oid or stxrelid of 147574. I've hunted around some in pg_class and
pg_statitic, but can't find any column with a reference to this value.

I tried upgrading (I was on 12.3), shutting down and restarting the server
a few times, and running ANALYZE to see if anything would change. It hasn't.

Any idea how this problem can be created, avoided, or resolved? Many thanks.

For those of you familiar with the source, I've Googled for this error, and
have not seen it discussed. It comes up on pg-hackers about 12 years ago,
and it's located in the source at:

https://doxygen.postgresql.org/objectaddress_8h.html

Here's a snippet where the error is thrown, when HeapTupleIsValid returns
false.

case OCLASS_STATISTIC_EXT:

 {
HeapTuple   stxTup;
Form_pg_statistic_ext stxForm;
char   *nspname;

stxTup = SearchSysCache1(STATEXTOID,
 ObjectIdGetDatum(object->objectId));
if (!HeapTupleIsValid(stxTup))
{
if (!missing_ok)
elog(ERROR, "could not find tuple for statistics object %u",
 object->objectId);
break;
}

stxForm = (Form_pg_statistic_ext) GETSTRUCT(stxTup);

/* Qualify the name if not visible in search path */
if (StatisticsObjIsVisible(object->objectId))
nspname = NULL;
else
nspname = get_namespace_name(stxForm->stxnamespace);

appendStringInfo(&buffer, _("statistics object %s"),
 quote_qualified_identifier(nspname,
NameStr(stxForm->stxname)));

ReleaseSysCache(stxTup);
break;
 }

Re: ERROR: could not find tuple for statistics object - is there a way to clean this up?

[Morris de Oryx]

After posting, I realized that this is likely a Stupid User Error. I was
mucking around, and did something along the lines of

delete from pg_statistic_ext;

or
delete from pg_stats_ext;

...instead of DROP STATISTICS calls. Would this likely explain what I'm
seeing? If so, bug is in front of keyboard...my understanding is that you
shouldn't mess with the catalog data directly.

On Sun, Nov 15, 2020 at 6:08 PM Tom Lane  wrote:

> Morris de Oryx  writes:
> > And here's the error that I get back:
> > ERROR:  could not find tuple for statistics object 147574.
>
> Can you give a self-contained recipe for triggering this?
>
> regards, tom lane
>

Re: ERROR: could not find tuple for statistics object - is there a way to clean this up?

[Morris de Oryx]

Thanks, it's my local copy, which I drop and rebuild constantly as part of
my testing cycle. On our deployed servers, my patch and test procedures are
very strict. Locally, I like to experiment and blow things up. Well,
mission accomplished there ;-)

Thanks for taking the time to answer.

On Mon, Nov 16, 2020 at 3:34 AM Tom Lane  wrote:

> Morris de Oryx  writes:
> > After posting, I realized that this is likely a Stupid User Error. I was
> > mucking around, and did something along the lines of
> > delete from pg_statistic_ext;
> > or
> > delete from pg_stats_ext;
>
> > ...instead of DROP STATISTICS calls. Would this likely explain what I'm
> > seeing?
>
> Ah, yeah, it likely would.
>
> If this isn't a throwaway database, what you'd have to do to clear the
> errors is to find and remove the now-dangling links to the deleted objects
> in pg_depend.
>
> regards, tom lane
>

Re: crosstab function

[Morris de Oryx]

Professor Mueller! I believe that we met, long ago. I graduated from your
department in 1984 where I worked closely with the wonderful, late Prof.
Dipple.

Postgres.app is a very easy way to work with Postgres, and it does include
support for tablefunc. If you ever want to check which extensions are
installed, run this line:

select * from pg_available_extensions order by name;

Your code looks correct on the face of it:

CREATE EXTENSION IF NOT EXISTS tablefunc;

Or, if you have set up schemas other than the default "public", you can
install into a specific schema:

CREATE EXTENSION IF NOT EXISTS tablefunc WITH SCHEMA extensions;

If you aren't already using custom schemas...I'll leave it alone for now.

As noted, you're installing into a specific database, so make sure that
you've connected where you expect and are in the database you mean. It's
fairly easy for a tool to default to something other than your custom
database. If it's not clear from the UI, or you just feel like testing by
hand, run this line:

SELECT current_database();

It's worth knowing that a Postgres extension is a packaging system. An
extension may include C code, setup scripts, straight SQL, a variety of
resources. Sometimes, you can open one up and harvest little bits of SQL
you want. For details:

https://www.postgresql.org/docs/10/extend-extensions.html

After a quick googling, it looks like you may be interested in textual
analysis. If so, Postgres has a *lot* of tools that can be of assistance.
Within Postgres.app, I can see at least the following:

citext
If you haven't noticed, and care, Postgres' default varchar/text field type
is case-sensitive. Ugh. The citext extension is searchable
case-insensitively out of the box. I use this for alpha/text fields when I
don't care about case-sensitive searches. For where that is, read
"everywhere".

fuzzystrmatch
https://www.postgresql.org/docs/10/fuzzystrmatch.html

Basic, name/word-matching fuzzy algorithms. The "phonetic" ones are not so
great, but Levenshtein is quite good, if a bit expensive to run.

Full Text Search
Huge subject, lots of options, modern versions of Postgres are quite strong
here.

unaccent
The description reads, "text search dictionary that removes accents." I
haven't needed it, and wonder if specifying a collation might not work
better?

pg_pgtrgm
https://www.postgresql.org/docs/10/pgtrgm.html

*N*-grams of length 3. This is a fantastic tool. N-grams have proven
themselves down the years for fuzzy string matching in multiple domains.
I've mostly used it historically on name data, but it works well on larger
text blocks as well. This holds up with many languages other than English.
It's pretty easy to use this extension.

There's another appealing extension named pg_similarity that includes a
huge range of text comparison and fuzzy ranking tools, but I do not know
how to compile it for macOS or get it to run with Postgres.app. If you are
interested in a specific algorithm, many are easily implemented in a SQL
statement or stored function. For example, Jaccard (and similar) ranking
metrics are produced arithmetically, so they're easy to reimplement.

Re: Camel case identifiers and folding

[Morris de Oryx]

The original question has already been answered really well, but it reminds
me to mention that *Postgres text/varchar values are case-sensitive*.
Here's a list of the times when I would like a case-sensitive text field:

   Never

Now here's the list of times I would like a case-blind text field:

   Everywhere else.

If this is how you feel too, there are several alternatives. The one that
I've chosen is to use the citext extension instead of text fields.This
takes care of the problem without having to add extra function calls to
your queries, do anything special with indexes, etc.

 If you have JSON, which has case-sensitive element names, use JSONB.

Your requirements may differ than mine! Other people have good reason to
want case-sensitive searches. I just never do. (30+ years in programming
and I can't remember a time I wanted user data to be treated
case-sensitively...but you never know...one day...maybe.) There's also an
extension for stripping accents, which I've not needed.

I've idly wondered if using a different collation on a text field might be
a better answer than using citext everywhere? If anyone wants to set me
straight on this, I'd be grateful.

Re: Camel case identifiers and folding

[Morris de Oryx]

We definitely *store* data case-sensitively, we just never want to *search*
on it case-sensitively. That's what citext gives us.  Many databases
perform this way as a default. Postgres does not, but it offers
alternatives. The OP is coming from MySQL which, if I remember correctly,
treated non-binary-like text containers as case-insensitive in searches.
That's why I mentioned the Postgres behavior, it's a gotcha if you're
assuming something else will happen.

More to the point, users never want case-sensitive searches, it's just
confusing for them.

There are places where we've got data where byte-level/code page
differences are significant. But a lot of that is binary-like data. These
are rare, and I'm willing to do a bit of extra work for them. I can't even
think of such a case off the top of my head.

UUIDs as a type are an interesting case in Postgres. They're stored as a
large numeric for efficiency (good!), but are presented by default in the
36-byte format with the dashes. However, you can also search using the
dashes 32-character formatand it all works. Case-insensitively.
Postgres converses 36/32 char strings of any case combination back into the
relevant number and then searches. Anything else would be pointlessly hard
to deal with.

There are also cases where case-sensitivity is not optional. For example,
we save and generate JSON (like everyone else) for various tasks. JSON
element names are case-sensitive. Not our call, just the way it is.
Personally, I think that case-sensitive language element names are one of
the stupidest design choices in history...but no one asked me. There are
solid arguments in favor of the idea (Dijkstra himself argued in their
favor), and it's an unchangeable fact of life. So in those cases, yeah,
case-sensitivity matters. Namely, if the data itself *is *case-sensitive. The
truth is, I rarely have a reason to use a 0NF packed field type like
JSONso the issue doesn't come up in our Postgres searches. But if I did
plan to store JSON, say API response logs, I'd want those searches to be
case-sensitive and would use JSONB and the necessary operators.

Re: Camel case identifiers and folding

[Morris de Oryx]

Sounds like I may have touched a nerve with some. If so, no offense
intended!

There are cases where case-sensitivity is required or desirable, it would
be silly to argue otherwise. Where you have such cases, then case-sensitive
queries are great. Some RDBMS systems default to case-sensitive searches,
others default to case-blind searches. I'll take that to mean that either
choice has merit, and it's not foolish to prefer either. I need case-blind
searches vanishingly close to 100% of the time, but other people have
different conditions and may find that they almost never need case-blind
searches. I find this extreme hard to imagine, but find it easy to imagine
people who need case-sensitive searches quite often.

What I've been thinking about most are user-driven searches on
user-oriented data. Users, at least any user I've ever had, don't want
case-sensitive searches. They also don't care about diacritical characters,
at least in English. I worked for a French company for many years.
Diacritical searches were not always preferred, but sometimes were. It
depends on your user community and their requirements and norms. Sometimes
it comes down to an individual user. Options are good! I was really just
trying to warn someone coming from a base-blind default about Postgres
behavior because, well, it hurts if you aren't expecting it. That doesn't
make Postgres wrong (it's not that kind of a choice), but it is important
to know about.

I'm new to Postgres (only about a year in), and it's great. But I'm used to
a case-blind search as a default. And, honestly, I can *never* remember a
case when a user asked for a case-sensitive search. Ever. In 30+ years.
Maybe it's just me. Just kidding, it's not just me. If you're presenting
users with a search interface, you can find out by asking them. Or you can
AB test a search UI where there is the option of case-sensitive/blind
searching, but you randomly flip which is the default. For users,
case-sensitive searches are assumed. That's what Google does. Seriously,
Google === Search. It's not a hard test to run. If you find that with a
case-blind search, 30% of user tick the box to make it case-sensitive, then
you've got users that often do care about case-sensitive search.

And since it seems to be unclear at a few places in the discussion above: *It
absolutely makes sense to store data in its original form* and to allow for
case-sensitive searches, when required. It would be very weird to store

* Call me back Ishmael, I've gotta go...*

and get back anything else, be that


* call me back ishmael, i've gotta go...*

or

* CALL ME BACK ISHMAEL, I'VE GOTTA GO...*

As far as I understand it in Postgres, you can:

* Use something like UPPER or LOWER in Every. Single. Search.

* Fold text to one case consistently in an index to make searches
case-blind.

* Use citext.

* Teach and convince every user to enter and search for data
case-sensitively correctly Every. Single. Time.

On that last point, good luck. Here's an example, I'm keen on birds. Do you
write it:

Black-shouldered Kite
Black-Shouldered Kite


On Sun, Mar 17, 2019 at 8:46 AM Peter J. Holzer  wrote:

> On 2019-03-16 14:00:34 -0600, Rob Sargent wrote:
> > What sort of content is in your field of type text?  Certainly,
> in
> > English
> > prose, “rob” is different than “Rob”
> >
> >
> > I disagree. While the grammar for written English has rules when to
> > write "rob" and when to write "Rob", that distinction usually
> carries no
> > semantic difference. Consider:
> [...]
> > I don’t think it’s solely about the semantics.  One might be
> contractually
> > obligated to always spell a name in some exact way including it
> capitalization.
> > For instance if referring to "Rob Sargent” as a quote or accreditation,
> then
> > it’s not okay to let a typo “rob Sargent” go through.
>
> 1) Such contracts might exist, but they are only binding to the signing
> parties, they don't affect what is commonly understood as "the English
> language". Everybody else will see it as an obvious typo and won't
> assume that this refers to some "rob Sargent" who is a different person
> than "Rob Sargent".
>
> 2) I don't think the OP was talking about spell-checking. And in any
> case spell-checking is more complicated than simply comparing strings
> byte by byte.
>
> hp
>
>
> --
>_  | Peter J. Holzer| we build much bigger, better disasters now
> |_|_) || because we have much more sophisticated
> | |   | h...@hjp.at | management tools.
> __/   | http://www.hjp.at/ | -- Ross Anderson 
> -BEGIN PGP SIGNATURE-
>
> iQIzBAABCAAdFiEETtJbRjyPwVTYGJ5k8g5IURL+KF0FAlyNbrwACgkQ8g5IURL+
> KF2mKhAAq8b9RLFBihsO+dQf3pxjLt3bWoD9mhgMEy8GvxADuxAF4dLo1SqfX2S0
> aIZFEyQgMoNKWOaiylj7TYPiBRilfVSCxggisPsirUKLKpXr4Bw9oIGiPBiE+21m
> ajlaONOZNiaM9D+BFthFkPM0TcjR2FHTaXOch0HbFnPnDWMgEPwY9yyDeN8ZPCOn
> 7G002EB3wxHcnhoFm8jGO2E8SL9l0NLU6+CVlCPAen

Re: Camel case identifiers and folding

[Morris de Oryx]

...hit send by accident

..or BLACK SHOULDERED KITE

You'll see all three regularly, depending on context and writer. It's
always the same bird. A natural search turns up all matches, regardless of
capitalization differences. The hyphens are hardI'm a huge, huge, huge
fan of fuzzy string matching and n-grams, but that's an unrelated topic.


On Mon, Mar 18, 2019 at 10:18 PM Morris de Oryx 
wrote:

> Sounds like I may have touched a nerve with some. If so, no offense
> intended!
>
> There are cases where case-sensitivity is required or desirable, it would
> be silly to argue otherwise. Where you have such cases, then case-sensitive
> queries are great. Some RDBMS systems default to case-sensitive searches,
> others default to case-blind searches. I'll take that to mean that either
> choice has merit, and it's not foolish to prefer either. I need case-blind
> searches vanishingly close to 100% of the time, but other people have
> different conditions and may find that they almost never need case-blind
> searches. I find this extreme hard to imagine, but find it easy to imagine
> people who need case-sensitive searches quite often.
>
> What I've been thinking about most are user-driven searches on
> user-oriented data. Users, at least any user I've ever had, don't want
> case-sensitive searches. They also don't care about diacritical characters,
> at least in English. I worked for a French company for many years.
> Diacritical searches were not always preferred, but sometimes were. It
> depends on your user community and their requirements and norms. Sometimes
> it comes down to an individual user. Options are good! I was really just
> trying to warn someone coming from a base-blind default about Postgres
> behavior because, well, it hurts if you aren't expecting it. That doesn't
> make Postgres wrong (it's not that kind of a choice), but it is important
> to know about.
>
> I'm new to Postgres (only about a year in), and it's great. But I'm used
> to a case-blind search as a default. And, honestly, I can *never* remember
> a case when a user asked for a case-sensitive search. Ever. In 30+ years.
> Maybe it's just me. Just kidding, it's not just me. If you're presenting
> users with a search interface, you can find out by asking them. Or you can
> AB test a search UI where there is the option of case-sensitive/blind
> searching, but you randomly flip which is the default. For users,
> case-sensitive searches are assumed. That's what Google does. Seriously,
> Google === Search. It's not a hard test to run. If you find that with a
> case-blind search, 30% of user tick the box to make it case-sensitive, then
> you've got users that often do care about case-sensitive search.
>
> And since it seems to be unclear at a few places in the discussion above: *It
> absolutely makes sense to store data in its original form* and to allow
> for case-sensitive searches, when required. It would be very weird to store
>
> * Call me back Ishmael, I've gotta go...*
>
> and get back anything else, be that
>
>
> * call me back ishmael, i've gotta go...*
>
> or
>
> * CALL ME BACK ISHMAEL, I'VE GOTTA GO...*
>
> As far as I understand it in Postgres, you can:
>
> * Use something like UPPER or LOWER in Every. Single. Search.
>
> * Fold text to one case consistently in an index to make searches
> case-blind.
>
> * Use citext.
>
> * Teach and convince every user to enter and search for data
> case-sensitively correctly Every. Single. Time.
>
> On that last point, good luck. Here's an example, I'm keen on birds. Do
> you write it:
>
> Black-shouldered Kite
> Black-Shouldered Kite
>
>
> On Sun, Mar 17, 2019 at 8:46 AM Peter J. Holzer  wrote:
>
>> On 2019-03-16 14:00:34 -0600, Rob Sargent wrote:
>> > What sort of content is in your field of type text?  Certainly,
>> in
>> > English
>> > prose, “rob” is different than “Rob”
>> >
>> >
>> > I disagree. While the grammar for written English has rules when to
>> > write "rob" and when to write "Rob", that distinction usually
>> carries no
>> > semantic difference. Consider:
>> [...]
>> > I don’t think it’s solely about the semantics.  One might be
>> contractually
>> > obligated to always spell a name in some exact way including it
>> capitalization.
>> > For instance if referring to "Rob Sargent” as a quote or accreditation,
>> then
>> > it’s not okay to let a typo “rob Sargent” go through.
>>
>> 1) Such cont

Re: Where to store Blobs?

[Morris de Oryx]

Good question, and there are some excellent thoughts and cautionary tales
in the thread already. I've faced this question several times down the
years and, as others have said, the best answer depends. Roughly speaking,
I can think of three obvious places to store documents:

* A database.

* A file system.

* A commodity file-system-like cloud service, such as S3, B2 Cloud, Azure,
or Google Cloud.

There are pros and cons to each, and circumstances that will make one
option or another untenable. It also depends a lot on your overall
architecture, if documents can change, how your searches work, your
security/regulatory requirements, the overall workflow, etc.

But given all of that, I *hate* bloating a database with BLOBs that aren't
themselves searchable. That's what file systems are for. This past week,
I've been coding against the B2 Cloud API and it's quite nice...simpler
than S3, and much cheaper. In this setup, we keep a document catalog in the
database that ties together a source record and an external document. The
"cloud_doc" record contains identifiers and information from both parts of
this story. So, descriptors, tags and IDs needed when you're looking for
something. In our case, that's large XML log files. These logs are either
of zero value or great value. We need to keep them, but 99.9% of the
time they're pure bloat. We've got a record about the event the log
details. The cloud_doc record includes a reference back to the original,
and to the storage location of the full log. So, the service type, bucket
ID, document ID, etc. So the catalog record links our real data with the
remote document, same as you would storing file paths to a local file tree.

Storing the data externally has some risks and limitations that make it
unsuitable in some situations. For example, you can't include the file or
cloud system in a transaction in any normal sense. Also, depending on
platform, there may be an unacceptable lag between pushing a file up and it
becoming visible to other systems. But for common cases, external (file or
cloud) storage can be pretty great.

Likewise, it's kind of scary to have the files someplace else where Bad
Things Might Happen and your database and file tree are out of sync. That's
genuinely worrisome. It's likely overkill, but I like to store references
back into the database in the meta-data for the document up on the cloud.
On S3 and B2, you store meta-data as "tags". I haven't used the document
storage systems on Azure or Google, but they likely have similar
functionality. A "tag" up on the cloud repository is a name-value-pair that
you can add custom data to. So, for example, I'll store the ID of our cloud
document catalog record in the meta-data (tags) for the document on the
cloud service. I also stash the ID of the source record that the log
relates to. If all goes well, we'll never need these tags but if worst came
to worst, they provide a way of calculating the parents of each external
document.

That last paragraph about tags points out something important: Cloud
document storage can be preferable to a standard file system for reasons
other than simplified provisioning and cost. Many file systems don't allow
your readily add and search meta-data like this, whereas it's a quite
accessible feature of cloud storage systems.

Going in another direction entirely, there may be times when what you need
is a local file storage system for documents. File systems are...scary, but
what about SQLite? You have a single file with a modern SQL syntax where
you can stuff BLOBs. You don't bloat your Postgres data file, but still
have a database for the documents instead of a file system. SQLite only
looks to solve problems in a pretty specific set of cases but, as it turns
out, those cases are also quite common. Combining it with a Postgres setup
seems pretty exotic, but there might be a time. It depends on your setup.

On Sat, Apr 20, 2019 at 10:59 AM Jamesie Pic  wrote:

> I forgot to mention that my deployments include automated migrations as
> often as possible, sometimes destructive for refactoring purpose, as such,
> to maintain PostgreSQL on a basic linux box I am:
>
> - for having an automated backup prior in the automated deployment script
> that may play destructive migrations,
> - against the needless overhead of coupling both binary and relational
> data in operations that slows the whole thing down or makes it less reliable
>
> Also got supposedly many new points against, mixed with more detail on the
> points briefly exposed in my previous email, going deeper in detail, about
> how it fits in the big picture of my personal practice ... and how this has
> destabilized my prod for months:
>
> https://blog.yourlabs.org/post/184290880553/storing-hd-photos-in-a-relational-database-recipe
>
> tl;dr
> If you store media files in PostgreSQL on a production server, then do
> take disk space alarms seriously even if they happen only during backups.
> Otherwise I fail to see how

Re: Questions about btree_gin vs btree_gist for low cardinality columns

[Morris de Oryx]

Jeremy's question is *great*, and really well presented. I can't answer his
questions, but I am keenly interested in this subject as well. The links he
provides lead to some really interesting and well-though-out pieces, well
worth reading.

I'm going to try restating things in my own way in hopes of getting some
good feedback and a basic question:

*What are the best ways to index low cardinality values in Postgres?*

For an example, imagine an address table with 100M US street addresses with
two character state abbreviations. So, say there are around 60 values in
there (the USPS is the mail system for a variety of US territories,
possessions and friends in the Pacific.) Okay, so what's the best index
type for state abbreviation? For the sake of argument, assume a normal
distribution so something like FM (Federated States of Micronesia) is on a
tail end and CA or NY are a whole lot more common.

A *B-tree* is obviously a pretty *bad match* for this sort of situation. It
works, but B-trees are ideal for *unique* values, and super large for
repeated values. Not getting into the details or Postgres specifics of
various kinds of traditional B-trees. (I think B*?) Doesn't matter. You
have a huge index because the index size is closely related to the number
of *rows*, not the number of *distinct values*.

Alternatively, you could set up *partial indexes* for the distinct values,
like so:

Running 10 Million PostgreSQL Indexes In Production (And Counting)
https://heap.io/blog/engineering/running-10-million-postgresql-indexes-in-production

Like Jeremy, I've wondered about *GIN indexes* for low-cardinality columns.
Has anyone tried this out in PG 10 or 11? It sounds like a good idea. As I
understand it, GIN indexes are something like a B-tree of unique values
that link to another data structure, like a tree, bitmap, etc. So, in my
imaginary example, there are 60 nodes for the state codes [internally there
would be more for padding free nodes, evenly sized pages, etcjust
pretend there are 60] and then linked to that, 60 data structures with the
actual row references. Somehow.

It can imagine things going quite well with a GIN or btree_gin. I can also
imagine that the secondary data structure could get bloaty, slow, and
horrible. I've worked with a system which uses bitmaps as the secondary
structure (at least some of the time), and it can work quite well...not
sure how it's implemented in Postgres.

So, does anyone have any links or results about efficiently (space and/or
time) indexing Boolean and other low-cardinality columns in Postgres? I'm
on PG 11, but figure many are on 9.x or 10.x.

References and results much appreciated.

Thanks!

Re: Questions about btree_gin vs btree_gist for low cardinality columns

[Morris de Oryx]

tests. I was hoping that the GIN would do well, but it didn't.
Here are some explain dumps.

B-tree (partial, just on this one value)
Aggregate  (cost=389.43..389.44 rows=1 width=8)
  ->  Index Only Scan using abbr_btree on state_test  (cost=0.42..346.68
rows=17100 width=0)
Index Cond: (abbr = 'MA'::text)

B-tree on whole table
Aggregate  (cost=389.43..389.44 rows=1 width=8)
  ->  Index Only Scan using abbr_btree on state_test  (cost=0.42..346.68
rows=17100 width=0)
Index Cond: (abbr = 'MA'::text)

GIN (btree_gin, hopefully - I created the extension)
Aggregate  (cost=4867.03..4867.04 rows=1 width=8)
  ->  Bitmap Heap Scan on state_test  (cost=140.53..4824.28 rows=17100
width=0)
Recheck Cond: (abbr = 'MA'::text)
->  Bitmap Index Scan on abbr_gin  (cost=0.00..136.25 rows=17100
width=0)
  Index Cond: (abbr = 'MA'::text)

Hash index
Aggregate  (cost=4915.00..4915.01 rows=1 width=8)
  ->  Index Scan using abbr_hash on state_test  (cost=0.00..4872.25
rows=17100 width=0)
Index Cond: (abbr = 'MA'::text)

No index
Finalize Aggregate  (cost=10696.37..10696.38 rows=1 width=8)
  ->  Gather  (cost=10696.15..10696.36 rows=2 width=8)
Workers Planned: 2
->  Partial Aggregate  (cost=9696.15..9696.16 rows=1 width=8)
  ->  Parallel Seq Scan on state_test  (cost=0.00..9678.34
rows=7125 width=0)
Filter: (abbr = 'MA'::text)


On Sat, Jun 1, 2019 at 12:52 PM Morris de Oryx 
wrote:

> Jeremy's question is *great*, and really well presented. I can't answer
> his questions, but I am keenly interested in this subject as well. The
> links he provides lead to some really interesting and well-though-out
> pieces, well worth reading.
>
> I'm going to try restating things in my own way in hopes of getting some
> good feedback and a basic question:
>
> *What are the best ways to index low cardinality values in Postgres?*
>
> For an example, imagine an address table with 100M US street addresses
> with two character state abbreviations. So, say there are around 60 values
> in there (the USPS is the mail system for a variety of US territories,
> possessions and friends in the Pacific.) Okay, so what's the best index
> type for state abbreviation? For the sake of argument, assume a normal
> distribution so something like FM (Federated States of Micronesia) is on a
> tail end and CA or NY are a whole lot more common.
>
> A *B-tree* is obviously a pretty *bad match* for this sort of situation.
> It works, but B-trees are ideal for *unique* values, and super large for
> repeated values. Not getting into the details or Postgres specifics of
> various kinds of traditional B-trees. (I think B*?) Doesn't matter. You
> have a huge index because the index size is closely related to the number
> of *rows*, not the number of *distinct values*.
>
> Alternatively, you could set up *partial indexes* for the distinct
> values, like so:
>
> Running 10 Million PostgreSQL Indexes In Production (And Counting)
>
> https://heap.io/blog/engineering/running-10-million-postgresql-indexes-in-production
>
> Like Jeremy, I've wondered about *GIN indexes* for low-cardinality
> columns. Has anyone tried this out in PG 10 or 11? It sounds like a good
> idea. As I understand it, GIN indexes are something like a B-tree of unique
> values that link to another data structure, like a tree, bitmap, etc. So,
> in my imaginary example, there are 60 nodes for the state codes [internally
> there would be more for padding free nodes, evenly sized pages, etcjust
> pretend there are 60] and then linked to that, 60 data structures with the
> actual row references. Somehow.
>
> It can imagine things going quite well with a GIN or btree_gin. I can also
> imagine that the secondary data structure could get bloaty, slow, and
> horrible. I've worked with a system which uses bitmaps as the secondary
> structure (at least some of the time), and it can work quite well...not
> sure how it's implemented in Postgres.
>
> So, does anyone have any links or results about efficiently (space and/or
> time) indexing Boolean and other low-cardinality columns in Postgres? I'm
> on PG 11, but figure many are on 9.x or 10.x.
>
> References and results much appreciated.
>
> Thanks!
>
>

Re: Questions about btree_gin vs btree_gist for low cardinality columns

[Morris de Oryx]

On Sat, Jun 1, 2019 at 6:24 PM Gavin Flower 
wrote:

> On 01/06/2019 14:52, Morris de Oryx wrote:
>
> I'd expect the distribution of values to be closer to a power law than
> the Normal distribution -- at very least a few states would have the
> most lookups.  But this is my gut feel, not based on any scientific
> analysis!


G'day and thanks! (I'm in the country to the left of you) Yeah, and my
mocked data divides things up fairly evenly :(

I meant to mention that when I did my tests that I only had one index on at
a time to prevent confusion. I also ran the speed tests several times so
each was on a warm cache.

Re: Questions about btree_gin vs btree_gist for low cardinality columns

[Morris de Oryx]

Peter, thanks a lot for picking up on what I started, improving it, and
reporting back. I *thought *I was providing timing estimates from the
EXPLAIN cost dumps. Seems not. Well, there's another thing that I've
learned.

Your explanation of why the hash index bloats out makes complete sense, I
ought to have thought that.

Can you tell me how you get timing results into state_test_times? I know
how to turn on time display in psql, but I much prefer to use straight SQL.
The reason for that is my production code is always run through a SQL
session, not typing things into psql.

On Sat, Jun 1, 2019 at 11:53 PM Peter J. Holzer  wrote:

> On 2019-06-01 17:44:00 +1000, Morris de Oryx wrote:
> > Since I've been wondering about this subject, I figured I'd take a bit
> of time
> > and try to do some tests. I'm not new to databases or coding, but have
> been
> > using Postgres for less than two years. I haven't tried to generate large
> > blocks of test data directly in Postgres before, so I'm sure that there
> are
> > better ways to do what I've done here. No worries, this gave me a chance
> to
> > work through at least some of the questions/problems in setting up and
> running
> > tests.
> >
> > Anyway, I populated a table with 1M rows of data with very little in
> them, just
> > a two-character state abbreviation. There are only 59 values, and the
> > distribution is fairly even as I used random() without any tricks to
> shape the
> > distribution. So, each value is roughly 1/60th of the total row count.
> Not
> > realistic, but what I've got.
> >
> > For this table, I built four different kind of index and tried each one
> out
> > with a count(*) query on a single exact match. I also checked out the
> size of
> > each index.
> >
> > Headline results:
> >
> > Partial index: Smaller (as expeced), fast.
> > B-tree index: Big, fast.
> > GIN: Small, slow.
> > Hash: Large, slow. ("Large" may be exaggerated in comparison with a
> B-tree
> > because of my test data.)
>
> You didn't post any times (or the queries you timed), so I don't know
> what "fast" and "slow" mean.
>
> I used your setup to time
> select sum(num) from state_test where abbr = 'MA';
> on my laptop (i5-7Y54, 16GB RAM, SSD, Pgsql 10.8) and here are the
> results:
>
> hjp=> select method, count(*),
> min(time_ms),
> avg(time_ms),
> percentile_cont(0.5) within group (order by time_ms) as median,
> max(time_ms)
> from state_test_times
> group by method
> order by 5;
>
>  method  | count |  min   |   avg   | median |  max
> -+---++-++
>  Partial | 5 |   9.05 |  9.7724 |  9.185 | 12.151
>  B tree  | 5 |  9.971 | 12.8036 | 10.226 |   21.6
>  GIN | 5 |  9.542 | 10.3644 | 10.536 | 10.815
>  Hash| 5 | 10.801 | 11.7448 | 11.047 | 14.875
>
> All the times are pretty much the same. GIN is third by median, but the
> difference is tiny, and it is secondy by minium and average and even
> first by maximum.
>
> In this case all the queries do a bitmap scan, so the times are probably
> dominated by reading the heap, not the index.
>
> > methodpg_table_sizekb
> > Partial   401408392 Kb
> > B tree2248704021960 Kb
> > GIN   19169281872 Kb
> > Hash  4925030448096 Kb
>
> I get the same sizes.
>
>
> > Okay, so the partial index is smaller, basically proportional to the
> fraction
> > of the file it's indexing. So that makes sense, and is good to know.
>
> Yeah. But to cover all values you would need 59 partial indexes, which
> gets you back to the size of the full btree index. My test shows that it
> might be faster, though, which might make the hassle of having to
> maintain a large number of indexes worthwhile.
>
> > The hash index size is...harder to explain...very big. Maybe my tiny
> > strings? Not sure what size Postgres hashes to. A hash of a two
> > character string is likely about worst-case.
>
> I think that a hash index is generally a poor fit for low cardinality
> indexes: You get a lot of equal values, which are basically hash
> collisions. Unless the index is specifically designed to handle this
> (e.g. by storing the key only once and then a tuple list per key, like a
> GIN index does) it will balloon out trying to reduce the number of
> collisions.
>
> hp
>
> --
>_  | Peter J. Holzer| we build much bigger, better disasters now
> |_|_) || because we have much more sophisticated
> | |   | h...@hjp.at | management tools.
> __/   | http://www.hjp.at/ | -- Ross Anderson <https://www.edge.org/>
>

Re: Questions about btree_gin vs btree_gist for low cardinality columns

[Morris de Oryx]

>From what Peter showed, the answer to (part of) the original questions
seems to be that *yes*, a B-tree GIN can be quite appealing. The test times
aren't too worrisome, and the index size is about 1/12th of a B-tree. I
added on the sizes, and divided each index size by a full B-tree:

Method  Count  Min   Avg Median Max  KB
KB/B-Tree
Partial 5  9.0509.77249.185 12.151  392 0.018
B-tree  5  9.971   12.8036   10.226 21.600   21,960 1.000
GIN 5  9.542   10.3644   10.536 10.8151,872 0.085
Hash5 10.801   11.7448   11.047 14.875   48,096 2.190

I'm not great at ASCII tables, I'm attaching a picture...don't know if that
works here.

[image: results_table.jpeg]

I guess I'd say at this point:

* The test case I set up is kind of silly and definitely not representative
of a variety of data distributions.

* Hash index is not well-matched to low-cardinality (=== "high collision")
values.

* Partial B-trees aren't going to save space if you need one for each
distinct value. And there's an overhead to index maintenance, so there's
that. (But partial indexes in Postgres are fantastic in the right
situationsthis probably isn't one.)

* A B-tree GIN index performs well and is space-efficient.

Might be overriding a bit here from an artificial/toy test, but I find the
results Peter offered pretty encouraging. It *really *feels wrong to use a
standard B-tree for low-cardinality columns. It's just a badly matched data
structure. Hash toothere you see the results quite dramatically, but
it's a closely related problem. A GIN index *seems* like it's well-matched
to low-cardinality indexing.

Now that this is all in my head a bit, I'm hoping for more feedback and
real-world observations. Any commentary appreciated.

On Sun, Jun 2, 2019 at 9:10 AM Morris de Oryx 
wrote:

> Peter, thanks a lot for picking up on what I started, improving it, and
> reporting back. I *thought *I was providing timing estimates from the
> EXPLAIN cost dumps. Seems not. Well, there's another thing that I've
> learned.
>
> Your explanation of why the hash index bloats out makes complete sense, I
> ought to have thought that.
>
> Can you tell me how you get timing results into state_test_times? I know
> how to turn on time display in psql, but I much prefer to use straight SQL.
> The reason for that is my production code is always run through a SQL
> session, not typing things into psql.
>
> On Sat, Jun 1, 2019 at 11:53 PM Peter J. Holzer  wrote:
>
>> On 2019-06-01 17:44:00 +1000, Morris de Oryx wrote:
>> > Since I've been wondering about this subject, I figured I'd take a bit
>> of time
>> > and try to do some tests. I'm not new to databases or coding, but have
>> been
>> > using Postgres for less than two years. I haven't tried to generate
>> large
>> > blocks of test data directly in Postgres before, so I'm sure that there
>> are
>> > better ways to do what I've done here. No worries, this gave me a
>> chance to
>> > work through at least some of the questions/problems in setting up and
>> running
>> > tests.
>> >
>> > Anyway, I populated a table with 1M rows of data with very little in
>> them, just
>> > a two-character state abbreviation. There are only 59 values, and the
>> > distribution is fairly even as I used random() without any tricks to
>> shape the
>> > distribution. So, each value is roughly 1/60th of the total row count.
>> Not
>> > realistic, but what I've got.
>> >
>> > For this table, I built four different kind of index and tried each one
>> out
>> > with a count(*) query on a single exact match. I also checked out the
>> size of
>> > each index.
>> >
>> > Headline results:
>> >
>> > Partial index: Smaller (as expeced), fast.
>> > B-tree index: Big, fast.
>> > GIN: Small, slow.
>> > Hash: Large, slow. ("Large" may be exaggerated in comparison with a
>> B-tree
>> > because of my test data.)
>>
>> You didn't post any times (or the queries you timed), so I don't know
>> what "fast" and "slow" mean.
>>
>> I used your setup to time
>> select sum(num) from state_test where abbr = 'MA';
>> on my laptop (i5-7Y54, 16GB RAM, SSD, Pgsql 10.8) and here are the
>> results:
>>
>> hjp=> select method, count(*),
>> min(time_ms),
>> avg(time_ms),
>> percentile_cont(0.5) within group (order by time_ms) as median

Re: Questions about btree_gin vs btree_gist for low cardinality columns

[Morris de Oryx]

Peter,

Thanks a lot for the remedial help on EXPLAIN and timing results.

Re: Questions about btree_gin vs btree_gist for low cardinality columns

[Morris de Oryx]

Thanks to Tom Lane and Jeff Janes for chiming in with the level of detail
they're able to provide.

As an outsider-who-now-loves-Postgres, I don't know the history or deep
details of all of the various index types. (Obviously.) As a long-time
database programmer, I can say that low-cardinality fields are *very*
common cases. So whatever Postgres can offer to make for optimal searches
and aggregates on such columns would be of immediate, ongoing, and
widespread value.

As an example, we're dealing with millions of rows where we often want to
find or summarize by a category value. So, maybe 6-10 categories that are
used in various queries. It's not realistic for us to anticipate every
field combination the category field is going to be involved in to lay down
multi-column indexes everywhere.

I've used a system that handled this situation with a B-tree for the
distinct values, and a subordinate data structure for the associated key
(TIDs in PG, I guess.) They either stored a packed list of addresses, or a
compressed bitmap on the whole table, depending on the number of associated
entries.  Seemed to work pretty well for queries. That also sounds very
like a btree_gin index in Postgres. (Without the compressed, on-disk bitmap
option.)

Getting back to the day-to-day, what would you recommend using for a
single-column index on a low-cardinality column (really low)? And, yes,
we'll happily use blocking queries up front to reduce the number of rows
under inspection, but that's 1) not always possible and 2) definitely not
always predictable in advance. So I'm looking for the best case for stupid
searches ;-)

Re: Questions about btree_gin vs btree_gist for low cardinality columns

[Morris de Oryx]

I didn't notice Bloom filters in the conversation so far, and have been
waiting for *years* for a good excuse to use a Bloom filter. I ran into
them years back in Splunk, which is a distributed log store. There's an
obvious benefit to a probabalistic tool like a Bloom filter there since
remote lookup (and/or retrieval from cold storage) is quite expensive,
relative to a local, hashed lookup. I haven't tried them in Postgres.

In the case of a single column with a small set of distinct values over a
large set of rows, how would a Bloom filter be preferable to, say, a GIN
index on an integer value?

I have to say, this is actually a good reminder in my case. We've got a lot
of small-distinct-values-big-rows columns. For example, "server_id",
"company_id", "facility_id", and so on. Only a handful of parent keys with
many millions of related rows. Perhaps it would be conceivable to use a
Bloom index to do quick lookups on combinations of such values within the
same table. I haven't tried Bloom indexes in Postgres, this might be worth
some experimenting.

Is there any thought in the Postgres world of adding something like
Oracle's bitmap indexes?

Is there a way to translate pg_amop.amopstrategy into a description?

[Morris de Oryx]

I'm digging into GiST indexes again, and ran into a helpful script here:

https://medium.com/postgres-professional/indexes-in-postgresql-5-gist-86e19781b5db

(This piece has shown up in many places in various versions.) I've adapted
the search a little, as I'd like to make it easier to explore available
index ops:

 SELECT amop.amopopr::regoperator   AS operator,
iif(amop.amoppurpose = 's', 'search','order')   AS purpose,
amop.amopstrategy   AS
stratgey_number -- I'd like to translate this into a description

   FROM pg_opclass opc,
pg_opfamily opf,
pg_am am,
pg_amop amop

  WHERE opc.opcname= 'gist_trgm_ops'
AND am.amname  = 'gist'
AND opf.oid= opc.opcfamily
AND am.oid = opf.opfmethod
AND amop.amopfamily= opc.opcfamily
AND amop.amoplefttype  = opc.opcintype;


+--+-+-+
| operator | purpose | stratgey_number |
+--+-+-+
| %(text,text) | search  | 1   |
| <->(text,text)   | order   | 2   |
| ~~(text,text)| search  | 3   |
| ~~*(text,text)   | search  | 4   |
| ~(text,text) | search  | 5   |
| ~*(text,text)| search  | 6   |
| %>(text,text)| search  | 7   |
| <->>(text,text)  | order   | 8   |
| %>>(text,text)   | search  | 9   |
| <->>>(text,text) | order   | 10  |
| =(text,text) | search  | 11  |
+--+-+-+

What I'm hoping for is a function like
get_opt_class_strategy_description(optclass, straregy_number)  I've
looked at the source a bit, and it seems that there is no such
function, and that it might well be difficult to implement. The
strategy numbers are, as far as I can see, local to the specific
opt_class, which has no requirement to label them in any particular
way.

Does anyone know if I'm missing something?

Along the way, I did find that you can often look things up by hand in
the source for specific tools, or review a lot of the strategies in
one place:

https://github.com/postgres/postgres/blob/edcb71258504ed22abba8cc7181d2bab3762e757/src/include/catalog/pg_amop.dat#L82

It's easier to use the docs at that point.

No lives hang in the balance here, but I'm hoping to learn something.

Thanks for any help or clarification.

Re: Is there a way to translate pg_amop.amopstrategy into a description?

[Morris de Oryx]

Thanks for the confirmation. And, I'd say that this feature would go under
"nice to have" rather than anything more important. Although, it *would *be
nice.

On Thu, Aug 22, 2024 at 5:42 PM Tom Lane  wrote:

> Morris de Oryx  writes:
> > What I'm hoping for is a function like
> > get_opt_class_strategy_description(optclass, straregy_number)  I've
> > looked at the source a bit, and it seems that there is no such
> > function, and that it might well be difficult to implement. The
> > strategy numbers are, as far as I can see, local to the specific
> > opt_class, which has no requirement to label them in any particular
> > way.
>
> That's correct.  For btree and hash, the meanings of the strategy
> numbers are determined by the index AM; but for (IIRC) all of our
> other index AMs they're determined by the individual opclass.  So
> anything like this would have to be implemented by dedicated code
> in each opclass.  Perhaps that's worth doing, but it'd be a fair
> amount of work.
>
> regards, tom lane
>

Remedial C: Does an ltree GiST index *ever* set recheck to true?

[Morris de Oryx]

I'm trying to determine if an ltree GiST index search *ever *needs to load
a row out of heap for a recheck, of if the index entry itself includes
enough information for a definitive answer. I believe that this is
controlled by the recheck flag in the consistency function.

>From what I've seen in the wild, and can sort out from the source, I think
that ltree does *not* need to load rows from heap.

https://github.com/postgres/postgres/blob/master/contrib/ltree/ltree_gist.c

I wonder because an ltree GiST index is "lossy" and this behavior is more
like a lossless strategy. I think that's either because I've misunderstood
what "lossy" means in this case, or it's because ltree GiST index *pages *are
based on a signature (lossy), while ltree GiST index *leaf entries* contain
the full tree/path (lossless.)

Can anyone confirm or deny for me? I'd be grateful for the certainty.

Re: Remedial C: Does an ltree GiST index *ever* set recheck to true?

[Morris de Oryx]

As always, thanks very much for the confirmation.

On Fri, Aug 30, 2024 at 12:18 PM Tom Lane  wrote:

> Morris de Oryx  writes:
> > From what I've seen in the wild, and can sort out from the source, I
> think
> > that ltree does *not* need to load rows from heap.
>
> The comment in ltree_consistent is pretty definitive:
>
> /* All cases served by this function are exact */
> *recheck = false;
>
> > I wonder because an ltree GiST index is "lossy" and this behavior is more
> > like a lossless strategy. I think that's either because I've
> misunderstood
> > what "lossy" means in this case, or it's because ltree GiST index *pages
> *are
> > based on a signature (lossy), while ltree GiST index *leaf entries*
> contain
> > the full tree/path (lossless.)
>
> Yeah, the code is not terribly well commented but this bit in ltree.h
> appears to be saying that leaf entries contain the original ltree:
>
>  * type of index key for ltree. Tree are combined B-Tree and R-Tree
>  * Storage:
>  *Leaf pages
>  *(len)(flag)(ltree)
>  *Non-Leaf
>  * (len)(flag)(sign)(left_ltree)(right_ltree)
>  *ALLTRUE: (len)(flag)(left_ltree)(right_ltree)
>
> and that seems consistent with the fact that ltree_consistent
> does different things at leaf and non-leaf levels.
>
> regards, tom lane
>