pg.ddx.io  pgsql-general@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Tom Lane <tgl@sss.pgh.pa.us>
To: David Rowley <dgrowleyml@gmail.com>
Cc: Marc Millas <marc.millas@mokadb.com>
Cc: pgsql-general@lists.postgresql.org <pgsql-general@lists.postgresql.org>
Subject: Re: bug or lacking doc hint
Date: Sun, 25 Jun 2023 17:47:55 -0400
Message-ID: <587381.1687729675@sss.pgh.pa.us> (raw)
In-Reply-To: <CAApHDvo-P9b0jDa+CKkG6_+budNn8QQhy47YF5i_ipwCBr6XrA@mail.gmail.com>
References: <CADX_1abJasPxOFSxDm+XVU3dZSUr5wVBz_xFh7tKcdBDqeozsw@mail.gmail.com>
	<CAApHDvo-P9b0jDa+CKkG6_+budNn8QQhy47YF5i_ipwCBr6XrA@mail.gmail.com>

David Rowley <dgrowleyml@gmail.com> writes:
> The problem is that out of the 3 methods PostgreSQL uses to join
> tables, only 1 of them supports join conditions with an OR clause.
> Merge Join cannot do this because results can only be ordered one way
> at a time.  Hash Join technically could do this, but it would require
> that it built multiple hash tables. Currently, it only builds one
> table.  That leaves Nested Loop as the join method to implement joins
> with OR clauses. Unfortunately, nested loops are quadratic and the
> join condition must be evaluated once per each cartesian product row.

We can do better than that if the OR'd conditions are each amenable
to an index scan on one of the tables: then it can be a nestloop with
a bitmap-OR'd inner index scan.  I thought the upthread advice to
convert the substr() condition into something that could be indexed
was on-point.

> Tom Lane did start some work [1] to allow the planner to convert some
> queries to use UNION instead of evaluating OR clauses, but, if I
> remember correctly, it didn't handle ORs in join conditions, though
> perhaps having it do that would be a natural phase 2. I don't recall
> why the work stopped.

As I recall, I was having difficulty convincing myself that
de-duplication of results (for cases where the same row satisfies
more than one of the OR'd conditions) would work correctly.
You can't just blindly make it a UNION because that might remove
identical rows that *should* appear more than once in the result.

			regards, tom lane





view thread (11+ messages)  latest in thread

Message-ID: <587381.1687729675@sss.pgh.pa.us>
Permalink:  ../587381.1687729675@sss.pgh.pa.us/
Also on:    postgresql.org/message-id/587381.1687729675@sss.pgh.pa.us

 · 

reply

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 from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-general@postgresql.org
  Cc: tgl@sss.pgh.pa.us, dgrowleyml@gmail.com, marc.millas@mokadb.com
  Subject: Re: bug or lacking doc hint
  In-Reply-To: <587381.1687729675@sss.pgh.pa.us>
  References: <CADX_1abJasPxOFSxDm+XVU3dZSUr5wVBz_xFh7tKcdBDqeozsw@mail.gmail.com> <CAApHDvo-P9b0jDa+CKkG6_+budNn8QQhy47YF5i_ipwCBr6XrA@mail.gmail.com> <587381.1687729675@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