public inbox for [email protected]
help / color / mirror / Atom feed[PATCH v4 09/19] Execute freezing in heap_page_prune()
20+ messages / 6 participants
[nested] [flat]
* [PATCH v4 09/19] Execute freezing in heap_page_prune()
@ 2024-03-08 21:45 Melanie Plageman <[email protected]>
0 siblings, 0 replies; 20+ messages in thread
From: Melanie Plageman @ 2024-03-08 21:45 UTC (permalink / raw)
As a step toward combining the prune and freeze WAL records, execute
freezing in heap_page_prune(). The logic to determine whether or not to
execute freeze plans was moved from lazy_scan_prune() over to
heap_page_prune() with little modification.
---
src/backend/access/heap/heapam_handler.c | 2 +-
src/backend/access/heap/pruneheap.c | 155 ++++++++++++++++++-----
src/backend/access/heap/vacuumlazy.c | 134 +++++---------------
src/backend/storage/ipc/procarray.c | 6 +-
src/include/access/heapam.h | 39 +++---
src/tools/pgindent/typedefs.list | 2 +-
6 files changed, 182 insertions(+), 156 deletions(-)
diff --git a/src/backend/access/heap/heapam_handler.c b/src/backend/access/heap/heapam_handler.c
index 680a50bf8b1..5e522f5b0ba 100644
--- a/src/backend/access/heap/heapam_handler.c
+++ b/src/backend/access/heap/heapam_handler.c
@@ -1046,7 +1046,7 @@ heapam_scan_analyze_next_tuple(TableScanDesc scan, TransactionId OldestXmin,
* We ignore unused and redirect line pointers. DEAD line pointers
* should be counted as dead, because we need vacuum to run to get rid
* of them. Note that this rule agrees with the way that
- * heap_page_prune() counts things.
+ * heap_page_prune_and_freeze() counts things.
*/
if (!ItemIdIsNormal(itemid))
{
diff --git a/src/backend/access/heap/pruneheap.c b/src/backend/access/heap/pruneheap.c
index afc5ea5e0e7..20907ba5408 100644
--- a/src/backend/access/heap/pruneheap.c
+++ b/src/backend/access/heap/pruneheap.c
@@ -17,16 +17,19 @@
#include "access/heapam.h"
#include "access/heapam_xlog.h"
#include "access/htup_details.h"
+#include "access/multixact.h"
#include "access/transam.h"
#include "access/xlog.h"
+#include "commands/vacuum.h"
#include "access/xloginsert.h"
+#include "executor/instrument.h"
#include "miscadmin.h"
#include "pgstat.h"
#include "storage/bufmgr.h"
#include "utils/rel.h"
#include "utils/snapmgr.h"
-/* Working data for heap_page_prune and subroutines */
+/* Working data for heap_page_prune_and_freeze() and subroutines */
typedef struct
{
/* tuple visibility test, initialized for the relation */
@@ -51,6 +54,11 @@ typedef struct
* 1. Otherwise every access would need to subtract 1.
*/
bool marked[MaxHeapTuplesPerPage + 1];
+
+ /*
+ * One entry for every tuple that we may freeze.
+ */
+ HeapTupleFreeze frozen[MaxHeapTuplesPerPage];
} PruneState;
/* Local functions */
@@ -59,14 +67,15 @@ static HTSV_Result heap_prune_satisfies_vacuum(PruneState *prstate,
Buffer buffer);
static int heap_prune_chain(Buffer buffer,
OffsetNumber rootoffnum,
- PruneState *prstate, PruneResult *presult);
+ PruneState *prstate, PruneFreezeResult *presult);
+
static void heap_prune_record_prunable(PruneState *prstate, TransactionId xid);
static void heap_prune_record_redirect(PruneState *prstate,
OffsetNumber offnum, OffsetNumber rdoffnum);
static void heap_prune_record_dead(PruneState *prstate, OffsetNumber offnum,
- PruneResult *presult);
+ PruneFreezeResult *presult);
static void heap_prune_record_dead_or_unused(PruneState *prstate, OffsetNumber offnum,
- PruneResult *presult);
+ PruneFreezeResult *presult);
static void heap_prune_record_unused(PruneState *prstate, OffsetNumber offnum);
static void page_verify_redirects(Page page);
@@ -146,15 +155,15 @@ heap_page_prune_opt(Relation relation, Buffer buffer)
*/
if (PageIsFull(page) || PageGetHeapFreeSpace(page) < minfree)
{
- PruneResult presult;
+ PruneFreezeResult presult;
/*
* For now, pass mark_unused_now as false regardless of whether or
* not the relation has indexes, since we cannot safely determine
* that during on-access pruning with the current implementation.
*/
- heap_page_prune(relation, buffer, vistest, false, NULL,
- &presult, NULL);
+ heap_page_prune_and_freeze(relation, buffer, vistest, false, NULL,
+ &presult, NULL);
/*
* Report the number of tuples reclaimed to pgstats. This is
@@ -188,7 +197,12 @@ heap_page_prune_opt(Relation relation, Buffer buffer)
/*
- * Prune and repair fragmentation in the specified page.
+ * Prune and repair fragmentation and potentially freeze tuples on the
+ * specified page.
+ *
+ * If the page can be marked all-frozen in the visibility map, we may
+ * opportunistically freeze tuples on the page if either its tuples are old
+ * enough or freezing will be cheap enough.
*
* Caller must have pin and buffer cleanup lock on the page. Note that we
* don't update the FSM information for page on caller's behalf. Caller might
@@ -206,23 +220,24 @@ heap_page_prune_opt(Relation relation, Buffer buffer)
* mark_unused_now indicates whether or not dead items can be set LP_UNUSED
* during pruning.
*
- * pagefrz contains both input and output parameters used if the caller is
- * interested in potentially freezing tuples on the page.
+ * pagefrz is an input parameter containing visibility cutoff information and
+ * the current relfrozenxid and relminmxids used if the caller is interested in
+ * freezing tuples on the page.
*
* presult contains output parameters needed by callers such as the number of
* tuples removed and the number of line pointers newly marked LP_DEAD.
- * heap_page_prune() is responsible for initializing it.
+ * heap_page_prune_and_freeze() is responsible for initializing it.
*
* off_loc is the offset location required by the caller to use in error
* callback.
*/
void
-heap_page_prune(Relation relation, Buffer buffer,
- GlobalVisState *vistest,
- bool mark_unused_now,
- HeapPageFreeze *pagefrz,
- PruneResult *presult,
- OffsetNumber *off_loc)
+heap_page_prune_and_freeze(Relation relation, Buffer buffer,
+ GlobalVisState *vistest,
+ bool mark_unused_now,
+ HeapPageFreeze *pagefrz,
+ PruneFreezeResult *presult,
+ OffsetNumber *off_loc)
{
Page page = BufferGetPage(buffer);
BlockNumber blockno = BufferGetBlockNumber(buffer);
@@ -230,6 +245,8 @@ heap_page_prune(Relation relation, Buffer buffer,
maxoff;
PruneState prstate;
HeapTupleData tup;
+ bool do_freeze;
+ int64 fpi_before = pgWalUsage.wal_fpi;
/*
* First, initialize the new pd_prune_xid value to zero (indicating no
@@ -265,6 +282,10 @@ heap_page_prune(Relation relation, Buffer buffer,
/* for recovery conflicts */
presult->frz_conflict_horizon = InvalidTransactionId;
+ /* For advancing relfrozenxid and relminmxid */
+ presult->new_relfrozenxid = InvalidTransactionId;
+ presult->new_relminmxid = InvalidMultiXactId;
+
maxoff = PageGetMaxOffsetNumber(page);
tup.t_tableOid = RelationGetRelid(relation);
@@ -400,11 +421,11 @@ heap_page_prune(Relation relation, Buffer buffer,
/* Tuple with storage -- consider need to freeze */
if ((heap_prepare_freeze_tuple(htup, pagefrz,
- &presult->frozen[presult->nfrozen],
+ &prstate.frozen[presult->nfrozen],
&totally_frozen)))
{
/* Save prepared freeze plan for later */
- presult->frozen[presult->nfrozen++].offset = offnum;
+ prstate.frozen[presult->nfrozen++].offset = offnum;
}
/*
@@ -557,6 +578,72 @@ heap_page_prune(Relation relation, Buffer buffer,
/* Record number of newly-set-LP_DEAD items for caller */
presult->nnewlpdead = prstate.ndead;
+
+ /*
+ * Freeze the page when heap_prepare_freeze_tuple indicates that at least
+ * one XID/MXID from before FreezeLimit/MultiXactCutoff is present. Also
+ * freeze when pruning generated an FPI, if doing so means that we set the
+ * page all-frozen afterwards (might not happen until final heap pass).
+ */
+ if (pagefrz)
+ do_freeze = pagefrz->freeze_required ||
+ (presult->all_visible_except_removable && presult->all_frozen &&
+ presult->nfrozen > 0 &&
+ fpi_before != pgWalUsage.wal_fpi);
+ else
+ do_freeze = false;
+
+ if (do_freeze)
+ {
+ /*
+ * We can use frz_conflict_horizon as our cutoff for conflicts when
+ * the whole page is eligible to become all-frozen in the VM once
+ * we're done with it. Otherwise we generate a conservative cutoff by
+ * stepping back from OldestXmin.
+ */
+ if (!(presult->all_visible_except_removable && presult->all_frozen))
+ {
+ /* Avoids false conflicts when hot_standby_feedback in use */
+ presult->frz_conflict_horizon = pagefrz->cutoffs->OldestXmin;
+ TransactionIdRetreat(presult->frz_conflict_horizon);
+ }
+
+ /* Execute all freeze plans for page as a single atomic action */
+ heap_freeze_execute_prepared(relation, buffer,
+ presult->frz_conflict_horizon,
+ prstate.frozen, presult->nfrozen);
+ }
+ else if (!pagefrz || !presult->all_frozen || presult->nfrozen > 0)
+ {
+ /*
+ * If we will neither freeze tuples on the page nor set the page all
+ * frozen in the visibility map, the page is not all frozen and there
+ * will be no newly frozen tuples.
+ */
+ presult->all_frozen = false;
+ presult->nfrozen = 0; /* avoid miscounts in instrumentation */
+ }
+
+ /* Caller won't update new_relfrozenxid and new_relminmxid */
+ if (!pagefrz)
+ return;
+
+ /*
+ * If we will freeze tuples on the page or, even if we don't freeze tuples
+ * on the page, if we will set the page all-frozen in the visibility map,
+ * we can advance relfrozenxid and relminmxid to the values in
+ * pagefrz->FreezePageRelfrozenXid and pagefrz->FreezePageRelminMxid.
+ */
+ if (presult->all_frozen || presult->nfrozen > 0)
+ {
+ presult->new_relfrozenxid = pagefrz->FreezePageRelfrozenXid;
+ presult->new_relminmxid = pagefrz->FreezePageRelminMxid;
+ }
+ else
+ {
+ presult->new_relfrozenxid = pagefrz->NoFreezePageRelfrozenXid;
+ presult->new_relminmxid = pagefrz->NoFreezePageRelminMxid;
+ }
}
@@ -614,7 +701,7 @@ heap_prune_satisfies_vacuum(PruneState *prstate, HeapTuple tup, Buffer buffer)
*/
static int
heap_prune_chain(Buffer buffer, OffsetNumber rootoffnum,
- PruneState *prstate, PruneResult *presult)
+ PruneState *prstate, PruneFreezeResult *presult)
{
int ndeleted = 0;
Page dp = (Page) BufferGetPage(buffer);
@@ -879,10 +966,10 @@ heap_prune_chain(Buffer buffer, OffsetNumber rootoffnum,
{
/*
* We found a redirect item that doesn't point to a valid follow-on
- * item. This can happen if the loop in heap_page_prune caused us to
- * visit the dead successor of a redirect item before visiting the
- * redirect item. We can clean up by setting the redirect item to
- * DEAD state or LP_UNUSED if the caller indicated.
+ * item. This can happen if the loop in heap_page_prune_and_freeze()
+ * caused us to visit the dead successor of a redirect item before
+ * visiting the redirect item. We can clean up by setting the
+ * redirect item to DEAD state or LP_UNUSED if the caller indicated.
*/
heap_prune_record_dead_or_unused(prstate, rootoffnum, presult);
}
@@ -922,7 +1009,7 @@ heap_prune_record_redirect(PruneState *prstate,
/* Record line pointer to be marked dead */
static void
heap_prune_record_dead(PruneState *prstate, OffsetNumber offnum,
- PruneResult *presult)
+ PruneFreezeResult *presult)
{
Assert(prstate->ndead < MaxHeapTuplesPerPage);
prstate->nowdead[prstate->ndead] = offnum;
@@ -945,7 +1032,7 @@ heap_prune_record_dead(PruneState *prstate, OffsetNumber offnum,
*/
static void
heap_prune_record_dead_or_unused(PruneState *prstate, OffsetNumber offnum,
- PruneResult *presult)
+ PruneFreezeResult *presult)
{
/*
* If the caller set mark_unused_now to true, we can remove dead tuples
@@ -972,9 +1059,9 @@ heap_prune_record_unused(PruneState *prstate, OffsetNumber offnum)
/*
- * Perform the actual page changes needed by heap_page_prune.
- * It is expected that the caller has a full cleanup lock on the
- * buffer.
+ * Perform the actual page pruning modifications needed by
+ * heap_page_prune_and_freeze(). It is expected that the caller has a full
+ * cleanup lock on the buffer.
*/
void
heap_page_prune_execute(Buffer buffer,
@@ -1088,11 +1175,11 @@ heap_page_prune_execute(Buffer buffer,
#ifdef USE_ASSERT_CHECKING
/*
- * When heap_page_prune() was called, mark_unused_now may have been
- * passed as true, which allows would-be LP_DEAD items to be made
- * LP_UNUSED instead. This is only possible if the relation has no
- * indexes. If there are any dead items, then mark_unused_now was not
- * true and every item being marked LP_UNUSED must refer to a
+ * When heap_page_prune_and_freeze() was called, mark_unused_now may
+ * have been passed as true, which allows would-be LP_DEAD items to be
+ * made LP_UNUSED instead. This is only possible if the relation has
+ * no indexes. If there are any dead items, then mark_unused_now was
+ * not true and every item being marked LP_UNUSED must refer to a
* heap-only tuple.
*/
if (ndead > 0)
diff --git a/src/backend/access/heap/vacuumlazy.c b/src/backend/access/heap/vacuumlazy.c
index 74ebab25a95..c4553a4159c 100644
--- a/src/backend/access/heap/vacuumlazy.c
+++ b/src/backend/access/heap/vacuumlazy.c
@@ -430,12 +430,12 @@ heap_vacuum_rel(Relation rel, VacuumParams *params,
* as an upper bound on the XIDs stored in the pages we'll actually scan
* (NewRelfrozenXid tracking must never be allowed to miss unfrozen XIDs).
*
- * Next acquire vistest, a related cutoff that's used in heap_page_prune.
- * We expect vistest will always make heap_page_prune remove any deleted
- * tuple whose xmax is < OldestXmin. lazy_scan_prune must never become
- * confused about whether a tuple should be frozen or removed. (In the
- * future we might want to teach lazy_scan_prune to recompute vistest from
- * time to time, to increase the number of dead tuples it can prune away.)
+ * Next acquire vistest, a related cutoff that's used in
+ * heap_page_prune_and_freeze(). We expect vistest will always make
+ * heap_page_prune_and_freeze() remove any deleted tuple whose xmax is <
+ * OldestXmin. (In the future we might want to teach lazy_scan_prune to
+ * recompute vistest from time to time, to increase the number of dead
+ * tuples it can prune away.)
*/
vacrel->aggressive = vacuum_get_cutoffs(rel, params, &vacrel->cutoffs);
vacrel->rel_pages = orig_rel_pages = RelationGetNumberOfBlocks(rel);
@@ -1378,21 +1378,21 @@ lazy_scan_new_or_empty(LVRelState *vacrel, Buffer buf, BlockNumber blkno,
*
* Caller must hold pin and buffer cleanup lock on the buffer.
*
- * Prior to PostgreSQL 14 there were very rare cases where heap_page_prune()
- * was allowed to disagree with our HeapTupleSatisfiesVacuum() call about
- * whether or not a tuple should be considered DEAD. This happened when an
- * inserting transaction concurrently aborted (after our heap_page_prune()
- * call, before our HeapTupleSatisfiesVacuum() call). There was rather a lot
- * of complexity just so we could deal with tuples that were DEAD to VACUUM,
- * but nevertheless were left with storage after pruning.
+ * Prior to PostgreSQL 14 there were very rare cases where
+ * heap_page_prune_and_freeze() was allowed to disagree with our
+ * HeapTupleSatisfiesVacuum() call about whether or not a tuple should be
+ * considered DEAD. This happened when an inserting transaction concurrently
+ * aborted (after our heap_page_prune_and_freeze() call, before our
+ * HeapTupleSatisfiesVacuum() call). There was rather a lot of complexity just
+ * so we could deal with tuples that were DEAD to VACUUM, but nevertheless were
+ * left with storage after pruning.
*
* As of Postgres 17, we circumvent this problem altogether by reusing the
- * result of heap_page_prune()'s visibility check. Without the second call to
- * HeapTupleSatisfiesVacuum(), there is no new HTSV_Result and there can be no
- * disagreement. We'll just handle such tuples as if they had become fully dead
- * right after this operation completes instead of in the middle of it. Note that
- * any tuple that becomes dead after the call to heap_page_prune() can't need to
- * be frozen, because it was visible to another session when vacuum started.
+ * result of heap_page_prune_and_freeze()'s visibility check. Without the
+ * second call to HeapTupleSatisfiesVacuum(), there is no new HTSV_Result and
+ * there can be no disagreement. We'll just handle such tuples as if they had
+ * become fully dead right after this operation completes instead of in the
+ * middle of it.
*
* vmbuffer is the buffer containing the VM block with visibility information
* for the heap block, blkno. all_visible_according_to_vm is the saved
@@ -1415,26 +1415,24 @@ lazy_scan_prune(LVRelState *vacrel,
OffsetNumber offnum,
maxoff;
ItemId itemid;
- PruneResult presult;
+ PruneFreezeResult presult;
int lpdead_items,
live_tuples,
recently_dead_tuples;
HeapPageFreeze pagefrz;
bool hastup = false;
- bool do_freeze;
- int64 fpi_before = pgWalUsage.wal_fpi;
OffsetNumber deadoffsets[MaxHeapTuplesPerPage];
Assert(BufferGetBlockNumber(buf) == blkno);
/*
* maxoff might be reduced following line pointer array truncation in
- * heap_page_prune. That's safe for us to ignore, since the reclaimed
- * space will continue to look like LP_UNUSED items below.
+ * heap_page_prune_and_freeze(). That's safe for us to ignore, since the
+ * reclaimed space will continue to look like LP_UNUSED items below.
*/
maxoff = PageGetMaxOffsetNumber(page);
- /* Initialize (or reset) page-level state */
+ /* Initialize pagefrz */
pagefrz.freeze_required = false;
pagefrz.FreezePageRelfrozenXid = vacrel->NewRelfrozenXid;
pagefrz.FreezePageRelminMxid = vacrel->NewRelminMxid;
@@ -1446,7 +1444,7 @@ lazy_scan_prune(LVRelState *vacrel,
recently_dead_tuples = 0;
/*
- * Prune all HOT-update chains in this page.
+ * Prune all HOT-update chains and potentially freeze tuples on this page.
*
* We count the number of tuples removed from the page by the pruning step
* in presult.ndeleted. It should not be confused with lpdead_items;
@@ -1457,8 +1455,8 @@ lazy_scan_prune(LVRelState *vacrel,
* items LP_UNUSED, so mark_unused_now should be true if no indexes and
* false otherwise.
*/
- heap_page_prune(rel, buf, vacrel->vistest, vacrel->nindexes == 0,
- &pagefrz, &presult, &vacrel->offnum);
+ heap_page_prune_and_freeze(rel, buf, vacrel->vistest, vacrel->nindexes == 0,
+ &pagefrz, &presult, &vacrel->offnum);
/*
* Now scan the page to collect LP_DEAD items and check for tuples
@@ -1575,85 +1573,23 @@ lazy_scan_prune(LVRelState *vacrel,
vacrel->offnum = InvalidOffsetNumber;
- /*
- * Freeze the page when heap_prepare_freeze_tuple indicates that at least
- * one XID/MXID from before FreezeLimit/MultiXactCutoff is present. Also
- * freeze when pruning generated an FPI, if doing so means that we set the
- * page all-frozen afterwards (might not happen until final heap pass).
- */
- do_freeze = pagefrz.freeze_required ||
- (presult.all_visible_except_removable && presult.all_frozen &&
- presult.nfrozen > 0 &&
- fpi_before != pgWalUsage.wal_fpi);
+ Assert(MultiXactIdIsValid(presult.new_relminmxid));
+ vacrel->NewRelfrozenXid = presult.new_relfrozenxid;
+ Assert(TransactionIdIsValid(presult.new_relfrozenxid));
+ vacrel->NewRelminMxid = presult.new_relminmxid;
- if (do_freeze)
+ if (presult.nfrozen > 0)
{
- TransactionId snapshotConflictHorizon;
-
/*
- * We're freezing the page. Our final NewRelfrozenXid doesn't need to
- * be affected by the XIDs that are just about to be frozen anyway.
+ * We never increment the frozen_pages instrumentation counter when
+ * nfrozen == 0, since it only counts pages with newly frozen tuples
+ * (don't confuse that with pages newly set all-frozen in VM).
*/
- vacrel->NewRelfrozenXid = pagefrz.FreezePageRelfrozenXid;
- vacrel->NewRelminMxid = pagefrz.FreezePageRelminMxid;
-
vacrel->frozen_pages++;
- /*
- * We can use frz_conflict_horizon as our cutoff for conflicts when
- * the whole page is eligible to become all-frozen in the VM once
- * we're done with it. Otherwise we generate a conservative cutoff by
- * stepping back from OldestXmin.
- */
- if (presult.all_visible_except_removable && presult.all_frozen)
- snapshotConflictHorizon = presult.frz_conflict_horizon;
- else
- {
- /* Avoids false conflicts when hot_standby_feedback in use */
- snapshotConflictHorizon = pagefrz.cutoffs->OldestXmin;
- TransactionIdRetreat(snapshotConflictHorizon);
- }
-
/* Using same cutoff when setting VM is now unnecessary */
- if (presult.all_visible_except_removable && presult.all_frozen)
+ if (presult.all_frozen)
presult.frz_conflict_horizon = InvalidTransactionId;
-
- /* Execute all freeze plans for page as a single atomic action */
- heap_freeze_execute_prepared(vacrel->rel, buf,
- snapshotConflictHorizon,
- presult.frozen, presult.nfrozen);
- }
- else if (presult.all_frozen && presult.nfrozen == 0)
- {
- /* Page should be all visible except to-be-removed tuples */
- Assert(presult.all_visible_except_removable);
-
- /*
- * We have no freeze plans to execute, so there's no added cost from
- * following the freeze path. That's why it was chosen. This is
- * important in the case where the page only contains totally frozen
- * tuples at this point (perhaps only following pruning). Such pages
- * can be marked all-frozen in the VM by our caller, even though none
- * of its tuples were newly frozen here (note that the "no freeze"
- * path never sets pages all-frozen).
- *
- * We never increment the frozen_pages instrumentation counter here,
- * since it only counts pages with newly frozen tuples (don't confuse
- * that with pages newly set all-frozen in VM).
- */
- vacrel->NewRelfrozenXid = pagefrz.FreezePageRelfrozenXid;
- vacrel->NewRelminMxid = pagefrz.FreezePageRelminMxid;
- }
- else
- {
- /*
- * Page requires "no freeze" processing. It might be set all-visible
- * in the visibility map, but it can never be set all-frozen.
- */
- vacrel->NewRelfrozenXid = pagefrz.NoFreezePageRelfrozenXid;
- vacrel->NewRelminMxid = pagefrz.NoFreezePageRelminMxid;
- presult.all_frozen = false;
- presult.nfrozen = 0; /* avoid miscounts in instrumentation */
}
/*
diff --git a/src/backend/storage/ipc/procarray.c b/src/backend/storage/ipc/procarray.c
index b3cd248fb64..88a6d504dff 100644
--- a/src/backend/storage/ipc/procarray.c
+++ b/src/backend/storage/ipc/procarray.c
@@ -1715,9 +1715,9 @@ TransactionIdIsActive(TransactionId xid)
* Note: the approximate horizons (see definition of GlobalVisState) are
* updated by the computations done here. That's currently required for
* correctness and a small optimization. Without doing so it's possible that
- * heap vacuum's call to heap_page_prune() uses a more conservative horizon
- * than later when deciding which tuples can be removed - which the code
- * doesn't expect (breaking HOT).
+ * heap vacuum's call to heap_page_prune_and_freeze() uses a more conservative
+ * horizon than later when deciding which tuples can be removed - which the
+ * code doesn't expect (breaking HOT).
*/
static void
ComputeXidHorizons(ComputeXidHorizonsResult *h)
diff --git a/src/include/access/heapam.h b/src/include/access/heapam.h
index 2339abfd28a..b2a4caeb33a 100644
--- a/src/include/access/heapam.h
+++ b/src/include/access/heapam.h
@@ -195,7 +195,7 @@ typedef struct HeapPageFreeze
/*
* Per-page state returned from pruning
*/
-typedef struct PruneResult
+typedef struct PruneFreezeResult
{
int ndeleted; /* Number of tuples deleted from the page */
int nnewlpdead; /* Number of newly LP_DEAD items */
@@ -210,9 +210,10 @@ typedef struct PruneResult
/*
* Tuple visibility is only computed once for each tuple, for correctness
- * and efficiency reasons; see comment in heap_page_prune() for details.
- * This is of type int8[], instead of HTSV_Result[], so we can use -1 to
- * indicate no visibility has been computed, e.g. for LP_DEAD items.
+ * and efficiency reasons; see comment in heap_page_prune_and_freeze() for
+ * details. This is of type int8[], instead of HTSV_Result[], so we can
+ * use -1 to indicate no visibility has been computed, e.g. for LP_DEAD
+ * items.
*
* This needs to be MaxHeapTuplesPerPage + 1 long as FirstOffsetNumber is
* 1. Otherwise every access would need to subtract 1.
@@ -220,17 +221,18 @@ typedef struct PruneResult
int8 htsv[MaxHeapTuplesPerPage + 1];
- /*
- * One entry for every tuple that we may freeze.
- */
- HeapTupleFreeze frozen[MaxHeapTuplesPerPage];
-} PruneResult;
+ /* New value of relfrozenxid found by heap_page_prune_and_freeze() */
+ TransactionId new_relfrozenxid;
+
+ /* New value of relminmxid found by heap_page_prune_and_freeze() */
+ MultiXactId new_relminmxid;
+} PruneFreezeResult;
/*
* Pruning calculates tuple visibility once and saves the results in an array
- * of int8. See PruneResult.htsv for details. This helper function is meant to
- * guard against examining visibility status array members which have not yet
- * been computed.
+ * of int8. See PruneFreezeResult.htsv for details. This helper function is
+ * meant to guard against examining visibility status array members which have
+ * not yet been computed.
*/
static inline HTSV_Result
htsv_get_valid_status(int status)
@@ -306,6 +308,7 @@ extern TM_Result heap_lock_tuple(Relation relation, HeapTuple tuple,
Buffer *buffer, struct TM_FailureData *tmfd);
extern void heap_inplace_update(Relation relation, HeapTuple tuple);
+
extern bool heap_prepare_freeze_tuple(HeapTupleHeader tuple,
HeapPageFreeze *pagefrz,
HeapTupleFreeze *frz, bool *totally_frozen);
@@ -332,12 +335,12 @@ extern TransactionId heap_index_delete_tuples(Relation rel,
/* in heap/pruneheap.c */
struct GlobalVisState;
extern void heap_page_prune_opt(Relation relation, Buffer buffer);
-extern void heap_page_prune(Relation relation, Buffer buffer,
- struct GlobalVisState *vistest,
- bool mark_unused_now,
- HeapPageFreeze *pagefrz,
- PruneResult *presult,
- OffsetNumber *off_loc);
+extern void heap_page_prune_and_freeze(Relation relation, Buffer buffer,
+ struct GlobalVisState *vistest,
+ bool mark_unused_now,
+ HeapPageFreeze *pagefrz,
+ PruneFreezeResult *presult,
+ OffsetNumber *off_loc);
extern void heap_page_prune_execute(Buffer buffer,
OffsetNumber *redirected, int nredirected,
OffsetNumber *nowdead, int ndead,
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 042d04c8de2..b2ddc1e2549 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -2179,7 +2179,7 @@ ProjectionPath
PromptInterruptContext
ProtocolVersion
PrsStorage
-PruneResult
+PruneFreezeResult
PruneState
PruneStepResult
PsqlScanCallbacks
--
2.40.1
--tez7m2a73jtztiij
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment;
filename="v4-0010-Make-opp-freeze-heuristic-compatible-with-prune-f.patch"
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
@ 2025-02-07 20:09 Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-10 21:36 ` Re: should we have a fast-path planning for OLTP starjoins? Robert Haas <[email protected]>
0 siblings, 2 replies; 20+ messages in thread
From: Tomas Vondra @ 2025-02-07 20:09 UTC (permalink / raw)
To: James Hunter <[email protected]>; +Cc: Richard Guo <[email protected]>; Tom Lane <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
On 2/7/25 20:11, James Hunter wrote:
> On Wed, Feb 5, 2025 at 4:23 AM Tomas Vondra <[email protected]> wrote:
>>
>> If the requirement is that all "dimensions" only join to the fact table
>> (which in this example would be "A" I think) through a FK, then why
>> would these joins be illegal?
>>
>> ...
>> Essentially, this defines a "dimension" as a relation that is joined
>> through a PK, without any other restrictions, both of which seems fairly
>> simple to check, and it's a "local" feature. And we'd simply mark those
>> as "join at the very end, in arbitrary order". Easy enough, I guess.
>
> As I understand your proposal, you want to detect queries that join a
> large number, N, of tables -- which means doing an exhaustive search
> of all possible join orders is expensive -- where N - 1 of the tables
> do not join to each other, but join only to the Nth table.
>
Yes. Essentially, it reduces the size of the problem by ignoring joins
for which we know the optimal order. We know the dimensions can be
joined last, and it does not matter in which exact order we join them.
The starjoins are a bit of the "worst case" for our heuristics, because
there are no dependencies between the dimensions, and we end up
exploring the n! possible join orders, more or less. For other joins we
quickly prune the space.
> PostgreSQL already falls back on geqo when it hits some heuristic that
> says exhaustive search is too expensive, but you're proposing an
> additional, better heuristic.
True, but most people will never actually hit the GEQO, because the
default threshold are set like this:
join_collapse_limit = 8
geqo_threshold = 12
So the planner will not "create" join search problems with more than 8
relations, but geqo only kicks in at 12. Most systems run with the
default values for these GUCs, so they don't really use GEQO.
FWIW I don't know a lot about the GEQO internals, but I heard it doesn't
work all that well for the join order problem anyway. Not sure.
> Say we have F JOIN D1 JOIN D2 ... JOIN D(N-1). In the example you
> gave, the single-table predicate on F makes it small enough, I think,
> that F will be the "build" side of any Hash Join, right? You're
> assuming, I think, that the cardinality |F| = 1, after applying the
> filter to F. And so, |F JOIN Dk| will be approximately 1, for any 1 <=
> k < N. So then the join order does not matter. I think this is what
> you mean by "OLTP star join."
>
I don't think it matters very much on which side of the join the F will
end up (or if it's a hash join, it can easily be NL). It will definitely
be in the first join, though, because all other dimensions join to it
(assuming this is just a starjoin, with only fact + dimensions).
It also doesn't really matter what's the exact cardinality of |F|. The
example used a PK lookup, so that would be 1 row, but the point is that
this is (much) cheaper than the planning. E.g. the planning might take
3ms while the execution only takes 1ms, etc. In the OLAP cases this is
usually not the case, because the queries are processing a lot of data
from the fact table, and the planning is negligible.
> For *OLAP* star joins, Oracle's Star Transformation [1] works
> reasonably well, where Oracle scans D1, ..., D(N-1) first, constructs
> Bloom filters, etc., and then "pushes" the N-1 joins down into the Seq
> Scan on F.
>
I don't care about OLAP star joins, at least no in this patch. It's a
completely different / separate use case, and it affects very different
parts of the planner (and also the executor, which this patch does not
need to touch at all).
> So, I suggest:
> 1. Add an *OLTP* optimization similar to what you described, but
> instead of classifying the largest table as fact F, look for the "hub"
> of the star and classify it as F. And then enable your optimization if
> and only if the estimated nrows for F is very small.
>
Right. I believe this is mostly what looking for FKs (as suggested by
Tom) would end up doing. It doesn't need to consider the cardinality of
F at all.
> 2. For an *OLAP* optimization, do something like Oracle's Star
> Transformation.
>
I consider that well outside the scope of this patch.
> Re "OLTP" vs. "OLAP": the join order does not matter for *OLTP* star
> queries, because the fact table F is *small* (post-filtering). And
> because F is small, it doesn't matter so much in what order you join
> the dimension tables, because the result is "likely" to be small as
> well.
>
I don't think that's quite true. The order of dimension joins does not
matter because the joins do not affect the join size at all. The size of
|F| has nothing to do with that, I think. We'll do the same number of
lookups against the dimensions no matter in what order we join them. And
we know it's best to join them as late as possible, after all the joins
that reduce the size (and before joins that "add" rows, I think).
> Tom correctly points out that you really need foreign key constraints
> to ensure the previous sentence's "likely," but since your
> optimization is just intended to avoid considering unnecessary join
> orders, you may be able to get away with asking the optimizer what it
> thinks the cardinality |(... (F JOIN D1) ... JOIN Dk)| would be, and
> just fall back on the existing join-search logic when the optimizer
> thinks that Dk will create lots of rows (and so the join order
> matters...).
>
Possibly, but TBH the join cardinality estimates can be quite dubious
pretty easily. The FK is a much more reliable (definitive) information.
> So much for the OLTP case. For completeness, some discussion about the
> OLAP case; fwiw, let me start by plugging my "credentials" [2].
>
Thanks ;-)
> The OLAP case is more complicated than the OLTP case, in that the bad
> thing about *OLAP* star joins is that joins are pairwise. With OLAP
> star joins, you assume that |F| is always much larger than |Dk|, and
> by extension |(... (F JOIN D1) ... JOIN Dk)| is generally larger than
> |D(k+1)|. And the problem for OLAP is that while every Dk potentially
> filters rows out from F, you have to join to the Dk's one at a time,
> so you never get as much filtering as you'd like.
>
> For OLAP, you can take the Cartesian product of D1, ..., DN , and then
> scan F to aggregate into the resulting cube; see [3] . (Link [2] is
> related to transformation.)
>
> Or, you can scan D1, ..., DN first, without joining anything,
> constructing Hash tables and Bloom filters from your scans; then push
> the Bloom filters down to the scan of F; and finally join the
> (Bloom-filtered) F back to D1, ..., DN. This is what link [1]
> describes. Note that [1] came out before [3].
>
> However... for OLAP, you see from the above discussion that it's not
> compilation that takes too long, but rather execution. So the
> optimizations require significant changes to the SQL executor.
>
Agreed. I'm not against improving the OLAP case too, but it's not what
this thread was about. It seems it'll need changes in very different
places, etc.
> What you're proposing, IIUC, is a nice optimization to compilation
> times, which is why (I think) you're focused on the OLTP use case. In
> that case, I suggest focusing on an OLTP-specific solution, maybe a
> straw man like:
> 1. I see a query where N-1 relations join to the Nth relation, but not
> to each other (except transitively, of course).
> 2. Estimated cardinality for F, after pushing down single table
> predicates, is very small.
> 3. OK, let's start joining tables D1, ..., D(N-1) in order, since
> we're assuming (thanks to (1) and (2)) that the join order won't
> matter.
> 4. Continue joining tables in this fixed (arbitrary) order, unless we
> come to a Dk where the optimizer thinks joining to Dk will generate a
> significant number of rows.
> 5. Either we join all tables in order (fast compilation!); or we hit
> the case in (4), so we just fall back on the existing join logic.
>
Yes, I think that's pretty much the idea. Except that I don't think we
need to look at the |F| at all - it will have more impact for small |F|,
of course, but it doesn't hurt for large |F|.
I think it'll probably need to consider which joins increase/decrease
the cardinality, and "inject" the dimension joins in between those.
regards
--
Tomas Vondra
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
@ 2025-02-07 22:43 ` James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
1 sibling, 1 reply; 20+ messages in thread
From: James Hunter @ 2025-02-07 22:43 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: Richard Guo <[email protected]>; Tom Lane <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
On Fri, Feb 7, 2025 at 12:09 PM Tomas Vondra <[email protected]> wrote:
> ...
> Yes, I think that's pretty much the idea. Except that I don't think we
> need to look at the |F| at all - it will have more impact for small |F|,
> of course, but it doesn't hurt for large |F|.
>
> I think it'll probably need to consider which joins increase/decrease
> the cardinality, and "inject" the dimension joins in between those.
YMMV, but I suspect you may find it much easier to look at |F|, |F
JOIN D1|, |(F JOIN D1) JOIN D2|, etc., than to consider |F JOIN D1| /
|F|, etc. (In other words, I suspect that considering absolute
cardinalities will end up easier/cleaner than considering ratios of
increases/decreases in cardinalities.) But I have not thought about
this much, so I am not putting too much weight on my suspicions.
James
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
@ 2025-02-07 23:29 ` Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
0 siblings, 1 reply; 20+ messages in thread
From: Tomas Vondra @ 2025-02-07 23:29 UTC (permalink / raw)
To: James Hunter <[email protected]>; +Cc: Richard Guo <[email protected]>; Tom Lane <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
On 2/7/25 23:43, James Hunter wrote:
> On Fri, Feb 7, 2025 at 12:09 PM Tomas Vondra <[email protected]> wrote:
>> ...
>> Yes, I think that's pretty much the idea. Except that I don't think we
>> need to look at the |F| at all - it will have more impact for small |F|,
>> of course, but it doesn't hurt for large |F|.
>>
>> I think it'll probably need to consider which joins increase/decrease
>> the cardinality, and "inject" the dimension joins in between those.
>
> YMMV, but I suspect you may find it much easier to look at |F|, |F
> JOIN D1|, |(F JOIN D1) JOIN D2|, etc., than to consider |F JOIN D1| /
> |F|, etc. (In other words, I suspect that considering absolute
> cardinalities will end up easier/cleaner than considering ratios of
> increases/decreases in cardinalities.) But I have not thought about
> this much, so I am not putting too much weight on my suspicions.
>
That's not what I meant when I mentioned joins that increase/decrease
cardinality. That wasn't referring to the "dimension" joins, which we
expect to have FK and thus should not affect the cardinality at all.
Instead, I was thinking about the "other" joins (if there are any), that
may add or remove rows. AFAIK we want to join the dimensions at the
place with the lowest cardinality - the discussion mostly assumed the
joins would only reduce the cardinality, in which case we'd just leave
the dimensions until the very end.
But ISTM that may not be necessarily true. Let's say there's a join that
"multiplies" each row. It'll probably be done at the end, and the
dimension joins should probably happen right before it ... not sure.
cheers
--
Tomas Vondra
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
@ 2025-02-08 00:23 ` Tom Lane <[email protected]>
2025-02-08 01:49 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
0 siblings, 1 reply; 20+ messages in thread
From: Tom Lane @ 2025-02-08 00:23 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: James Hunter <[email protected]>; Richard Guo <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
Tomas Vondra <[email protected]> writes:
> Instead, I was thinking about the "other" joins (if there are any), that
> may add or remove rows. AFAIK we want to join the dimensions at the
> place with the lowest cardinality - the discussion mostly assumed the
> joins would only reduce the cardinality, in which case we'd just leave
> the dimensions until the very end.
> But ISTM that may not be necessarily true. Let's say there's a join that
> "multiplies" each row. It'll probably be done at the end, and the
> dimension joins should probably happen right before it ... not sure.
I thought the idea here was to get rid of as much join order searching
as we could. Insisting that we get the best possible plan anyway
seems counterproductive, not to mention very messy to implement.
So I'd just push all these joins to the end and be done with it.
regards, tom lane
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
@ 2025-02-08 01:49 ` Tomas Vondra <[email protected]>
2025-07-28 19:44 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
0 siblings, 1 reply; 20+ messages in thread
From: Tomas Vondra @ 2025-02-08 01:49 UTC (permalink / raw)
To: Tom Lane <[email protected]>; +Cc: James Hunter <[email protected]>; Richard Guo <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
On 2/8/25 01:23, Tom Lane wrote:
> Tomas Vondra <[email protected]> writes:
>> Instead, I was thinking about the "other" joins (if there are any), that
>> may add or remove rows. AFAIK we want to join the dimensions at the
>> place with the lowest cardinality - the discussion mostly assumed the
>> joins would only reduce the cardinality, in which case we'd just leave
>> the dimensions until the very end.
>
>> But ISTM that may not be necessarily true. Let's say there's a join that
>> "multiplies" each row. It'll probably be done at the end, and the
>> dimension joins should probably happen right before it ... not sure.
>
> I thought the idea here was to get rid of as much join order searching
> as we could. Insisting that we get the best possible plan anyway
> seems counterproductive, not to mention very messy to implement.
> So I'd just push all these joins to the end and be done with it.
>
Right, cutting down on the join order searching is the point. But most
of the savings comes (I think) from not considering different ordering
of the dimensions, because those are all essentially the same.
Consider a join with 16 relations, 10 of which are dimensions. There are
10! possible orders of the dimensions, but all of them behave pretty
much exactly the same. In a way, this behaves almost like a join with 7
relations, one of which represents all the 10 dimensions.
I think this "join group" abstraction (a relation representing a bunch
of relations in a particular order) would make this reasonably clean to
implement. I haven't tried yet, though.
Yes, this means we'd explore more orderings, compared to just pushing
all the dimensions to the end. In the example above, that'd be 7!/6!, so
up to ~7x orderings.
I don't know if this is worth the extra complexity, of course.
thanks
--
Tomas Vondra
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-02-08 01:49 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
@ 2025-07-28 19:44 ` Tomas Vondra <[email protected]>
2025-09-23 19:46 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
0 siblings, 1 reply; 20+ messages in thread
From: Tomas Vondra @ 2025-07-28 19:44 UTC (permalink / raw)
To: Tom Lane <[email protected]>; +Cc: James Hunter <[email protected]>; Richard Guo <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
On 2/4/25 22:55, Tom Lane wrote:
> Tomas Vondra <[email protected]> writes:
>>> The interesting thing about this is we pretty much have all the
>>> infrastructure for detecting such FK-related join conditions
>>> already. Possibly the join order forcing could be done with
>>> existing infrastructure too (by manipulating the joinlist).
>
>> Maybe, interesting. I've ruled out relying on the FKeys early in the
>> coding, but I'm sure there's infrastructure the patch could use.
>
> It would be very sad to do that work twice in a patch that purports
> to reduce planning time. If it's done too late to suit you now,
> could we move it to happen earlier?
>
>> What kind of "manipulation" of the joinlist you have in mind?
>
> Right now, if we have four tables to join, we have a joinlist
> (A B C D). (Really they're integer relids, but let's use names here.)
> If we decide to force C to be joined last, it should be sufficient to
> convert this to ((A B D) C). If C and D both look like candidates for
> this treatment, we can make it be (((A B) C) D) or (((A B) D) C).
> This is pretty much the same thing that happens if you set
> join_collapse_limit to 1 and use JOIN syntax to force a join order.
> In fact, IIRC we start out with nested joinlists and there is some
> code that normally flattens them until it decides it'd be creating
> too large a sub-problem. I'm suggesting selectively reversing the
> flattening.
>
> regards, tom lane
Here's a patch trying to do it more like this - by manipulating the
lists describing the join problems, before it's passed the the actual
join search algorithm (which is where the PoC patch did this).
I wonder if this is roughly the place where you imagined this would be
done, or if you envision some other issue with this approach. The patch
is definitely incomplete, there's plenty of XXX comments about places
missing some code, etc.
I initially tried to manipulate the joinlist much earlier - pretty much
right at the end of deconstruct_jointree. But that turned out to be way
too early. To identify dimensions etc. we need to check stuff about
foreign keys, join clauses, ... and that's not available that early.
So I think this needs to happen much later in query_planner(), and the
patch does it right before the make_one_rel() call. Maybe that's too
late, but it needs to happen after match_foreign_keys_to_quals(), as it
relies on some of the FK info built by that call. Maybe we could call
match_foreign_keys_to_quals() earlier, but I don't quite see any
benefits of doing that ...
On 2/8/25 02:49, Tomas Vondra wrote:
> On 2/8/25 01:23, Tom Lane wrote:
>> Tomas Vondra <[email protected]> writes:
>>> Instead, I was thinking about the "other" joins (if there are any), that
>>> may add or remove rows. AFAIK we want to join the dimensions at the
>>> place with the lowest cardinality - the discussion mostly assumed the
>>> joins would only reduce the cardinality, in which case we'd just leave
>>> the dimensions until the very end.
>>
>>> But ISTM that may not be necessarily true. Let's say there's a join that
>>> "multiplies" each row. It'll probably be done at the end, and the
>>> dimension joins should probably happen right before it ... not sure.
>>
>> I thought the idea here was to get rid of as much join order searching
>> as we could. Insisting that we get the best possible plan anyway
>> seems counterproductive, not to mention very messy to implement.
>> So I'd just push all these joins to the end and be done with it.
>>
>
> Right, cutting down on the join order searching is the point. But most
> of the savings comes (I think) from not considering different ordering
> of the dimensions, because those are all essentially the same.
>
> Consider a join with 16 relations, 10 of which are dimensions. There are
> 10! possible orders of the dimensions, but all of them behave pretty
> much exactly the same. In a way, this behaves almost like a join with 7
> relations, one of which represents all the 10 dimensions.
>
> I think this "join group" abstraction (a relation representing a bunch
> of relations in a particular order) would make this reasonably clean to
> implement. I haven't tried yet, though.
>
> Yes, this means we'd explore more orderings, compared to just pushing
> all the dimensions to the end. In the example above, that'd be 7!/6!, so
> up to ~7x orderings.
>
> I don't know if this is worth the extra complexity, of course.
>
I'm still concerned about regressions when happen to postpone some
expensive dimension joins after a join that increases the cardinality.
And the "join group" would address that. But It probably is not a very
common query pattern, and it'd require changes to join_search_one_level.
I'm not sure what could / should count as 'dimension'. The patch doesn't
implement this yet, but I think it can mostly copy how we match the FK
to the join in get_foreign_key_join_selectivity. There's probably more
to think about, though. For example, don't we need to check NOT NULL /
nullfrac on the referencing side? Also, it probably interacts with
LEFT/OUTER joins. I plan to start strict and then relax and handle some
additional cases.
I'm however struggling with the concept of join order restrictions a
bit. I suspect we need to worry about that when walking the relation
list and figuring out what can be a dimension, but I've never worked
with this, so my mental model of how this works is not great.
Another question is if this planning shortcut (which for the dimensions
mostly picks a random join order) could have some unexpected impact on
the rest of the planning. For example, could we "miss" some join
producing tuples in an interesting order? Or could we fail to consider a
partition-wise join?
Could this "shortcut" restrict the rest of the plan in some undesirable
way? For example, if some of the tables are partitioned, could this mean
we no longer can do partition-wise joins with the (mostly arbitrary)
join order we picked?
There's also a "patch" directory, with some SQL scripts creating two
simple examples of schemas/queries that would benefit from this. The
"create-1/select-1" examples are the simple starjoins, this thread
focuses on. It might be modified to do "snowflake" join, which is
fundamentally a variant of this query type.
The second example (create-2/select-2) is quite different, in that it's
nor a starjoin schema. It still joins one "main" table with multiple
"dimensions", but the FKs go in the other direction (to a single column
in the main table). But it has a very similar bottleneck - the order of
the joins is expensive, but it often does not matter very much, because
the query matches just one row anyway. And even if it returns more rows,
isn't the join order determined just by the selectivity of each join?
Maybe the starjoin optimization could be made to work for this type too?
regards
--
Tomas Vondra
Attachments:
[text/x-patch] v2-0001-Simplify-planning-of-starjoin-queries.patch (23.5K, ../../[email protected]/2-v2-0001-Simplify-planning-of-starjoin-queries.patch)
download | inline diff:
From a821bf2382cd08829b36cd67cfb424340d9f6408 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <[email protected]>
Date: Thu, 26 Jun 2025 17:49:29 +0200
Subject: [PATCH v2] Simplify planning of starjoin queries
---
patch/create-1.sql | 18 +
patch/create-2.sql | 11 +
patch/select-1.sql | 9 +
patch/select-2.sql | 9 +
src/backend/optimizer/plan/analyzejoins.c | 425 ++++++++++++++++++++++
src/backend/optimizer/plan/planmain.c | 10 +
src/backend/utils/misc/guc_tables.c | 10 +
src/include/optimizer/planmain.h | 2 +
8 files changed, 494 insertions(+)
create mode 100644 patch/create-1.sql
create mode 100644 patch/create-2.sql
create mode 100644 patch/select-1.sql
create mode 100644 patch/select-2.sql
diff --git a/patch/create-1.sql b/patch/create-1.sql
new file mode 100644
index 00000000000..8df04fd0677
--- /dev/null
+++ b/patch/create-1.sql
@@ -0,0 +1,18 @@
+create table dim1 (id int primary key, val1 text);
+create table dim2 (id int primary key, val2 text);
+create table dim3 (id int primary key, val3 text);
+create table dim4 (id int primary key, val4 text);
+create table dim5 (id int primary key, val5 text);
+create table dim6 (id int primary key, val6 text);
+create table dim7 (id int primary key, val7 text);
+
+create table t (id serial primary key,
+ id1 int references dim1(id),
+ id2 int references dim2(id),
+ id3 int references dim3(id),
+ id4 int references dim4(id),
+ id5 int references dim5(id),
+ id6 int references dim6(id),
+ id7 int references dim7(id));
+
+vacuum analyze;
diff --git a/patch/create-2.sql b/patch/create-2.sql
new file mode 100644
index 00000000000..cdf612dde8f
--- /dev/null
+++ b/patch/create-2.sql
@@ -0,0 +1,11 @@
+create table t (id serial primary key, a text);
+
+create table dim1 (id1 int primary key references t(id), val1 text);
+create table dim2 (id2 int primary key references t(id), val2 text);
+create table dim3 (id3 int primary key references t(id), val3 text);
+create table dim4 (id4 int primary key references t(id), val4 text);
+create table dim5 (id5 int primary key references t(id), val5 text);
+create table dim6 (id6 int primary key references t(id), val6 text);
+create table dim7 (id7 int primary key references t(id), val7 text);
+
+vacuum analyze;
diff --git a/patch/select-1.sql b/patch/select-1.sql
new file mode 100644
index 00000000000..1535ddcdc8f
--- /dev/null
+++ b/patch/select-1.sql
@@ -0,0 +1,9 @@
+--set join_collapse_limit = 1;
+select * from t
+ join dim1 on (dim1.id = id1)
+ join dim2 on (dim2.id = id2)
+ join dim3 on (dim3.id = id3)
+ join dim4 on (dim4.id = id4)
+ join dim5 on (dim5.id = id5)
+ join dim6 on (dim6.id = id6)
+ join dim7 on (dim7.id = id7);
diff --git a/patch/select-2.sql b/patch/select-2.sql
new file mode 100644
index 00000000000..4e1d2a7b0e7
--- /dev/null
+++ b/patch/select-2.sql
@@ -0,0 +1,9 @@
+-- set join_collapse_limit = 1;
+select * from t
+ left join dim1 on (id = id1)
+ left join dim2 on (id = id2)
+ left join dim3 on (id = id3)
+ left join dim4 on (id = id4)
+ left join dim5 on (id = id5)
+ left join dim6 on (id = id6)
+ left join dim7 on (id = id7);
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 4d55c2ea591..c57c3db94ef 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -51,6 +51,7 @@ typedef struct
} SelfJoinCandidate;
bool enable_self_join_elimination;
+bool enable_starjoin_join_search;
/* local functions */
static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
@@ -2512,3 +2513,427 @@ remove_useless_self_joins(PlannerInfo *root, List *joinlist)
return joinlist;
}
+
+/*
+ * starjoin_match_to_foreign_key
+ * Try to match a join to a FK constraint.
+ *
+ * For a relation to be a dimension (for the starjoin heuristics), it needs
+ * to be joined through a FK constraint. The dimension is expected to be
+ * on the PK side of the join. The relation must not have any additional
+ * join clauses, beyond those matching the foreign key.
+ *
+ * We already have a list of relevant foreign keys, and we use that info
+ * for selectivity estimation in get_foreign_key_join_selectivity(). And
+ * we're actually doing something quite similar here.
+ *
+ * XXX Do we need to worry about the join type, e.g. inner/outer joins,
+ * semi/anti? get_foreign_key_join_selectivity() does care about it, and
+ * ignores some of those cases. Maybe we should too?
+ *
+ * XXX Check there are no other join clauses, beyond those matching the
+ * foreign key. But do we already have the joininfo at this point? Some
+ * of this stuff gets build only during the join order search later.
+ * The match_foreign_keys_to_quals() probably needs to be aware of all
+ * this, so how does it do that?
+ */
+static bool
+starjoin_match_to_foreign_key(PlannerInfo *root, RelOptInfo *rel)
+{
+ ListCell *lc;
+
+ /* Consider each FK constraint that is known to match the query */
+ foreach(lc, root->fkey_list)
+ {
+ ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+ int nmatches = 0;
+
+ /* rel is not the referenced table of the FK */
+ if (fkinfo->ref_relid != rel->relid)
+ continue;
+
+ /*
+ * Do we have a match for each key of the FK?
+ *
+ * XXX get_foreign_key_join_selectivity checks EquivalenceClasses,
+ * we should probably (definitely) do that here too.
+ *
+ * XXX We should check that all the clauses have the same relation
+ * on the other side (for multi-column keys). And that there are
+ * no other join clauses other than those matching the FK.
+ *
+ * XXX Do we need to check that the FK side of the join (i.e. the fact
+ * table) has the columns referenced as NOT NULL? Otherwise we could
+ * have a FK join that reduces the cardinality, which is one of
+ * the arguments why it's fine to move the join (that it doesn't
+ * change the cardinality). But if the join is LEFT JOIN, this
+ * should be fine too - but do we get here with LEFT JOINs?
+ *
+ * XXX Do we need to check if the other side of the FK is in the
+ * current join list? Maybe it's in some later one?
+ */
+ for (int i = 0; i < fkinfo->nkeys; i++)
+ {
+ bool has_matching_clause = false;
+
+ /*
+ * Is there a clause matching this FK key?
+ *
+ * XXX We need to make sure it's a valid match, e.g. that the
+ * same referencing table matches all keys in a composite FK,
+ * and so on.
+ *
+ * XXX Do we need to check some relationship to other rels in
+ * the same jointree item? E.g. the referencing table should
+ * not be a dimensions we already removed.
+ */
+ if ((fkinfo->rinfos[i] != NULL) || (fkinfo->eclass[i] != NULL))
+ {
+ has_matching_clause = true;
+ nmatches++;
+ continue;
+ }
+
+ /* found a FK key without a matching join clause, ignore the FK */
+ if (has_matching_clause)
+ break;
+ }
+
+ /* matched all FK keys */
+ if (nmatches == fkinfo->nkeys)
+ {
+ return true;
+ }
+ }
+
+ return false;
+}
+
+
+/*
+ * starjoin_is_dimension
+ * Determine if a range table entry is a dimension in a starjoin.
+ *
+ * To be considered a dimension for the simplified join order search, the
+ * join must not affect the cardinality of the join. We ensure that by
+ * requiring a couple things:
+ *
+ * 1) the join clause has to match a FK (that is, the fact does have at
+ * most one matching row in the dimension)
+ *
+ * 2) the FK side (the fact table) should be marked as NOT NULL, so that
+ * we know there's exactly one dimension row for each fact table row
+ *
+ * 3) there must be no additional restrictions on the relation (that
+ * might eliminate some of the rows, reducing the cardinality)
+ *
+ * XXX The Implementation is incomplete. It probably needs more thought,
+ * considering some join types would allow relaxing some of the checks
+ * (e.g. outer joins may not require checking (2) or possibly even (3),
+ * depending on where the condition is, what varnullingrels it has).
+ *
+ * XXX I wonder if we could handle (3) by ordering the dimensions by the
+ * selectivity of the restriction. There are no join clauses between the
+ * dimensions (ignoring the snowflake joins, but even there the clauses
+ * don't go between branches), so the selectivity could be treated as
+ * a measure of how much it shrinks the join result. So we could just
+ * sort the dimensions by this, starting with the lowest selectivity
+ * (close to 0.0), and ending with dimensions without restrictions (in
+ * which case the selectivity is 1.0).
+ *
+ * XXX If the join in INNER, and the fact side has NULL values in the
+ * join key, we might consider nullfrac as restriction.
+ *
+ * XXX I'm not sure how careful this needs to be about join order
+ * restrictions. Maybe it should call have_relevant_joinclause and
+ * have_join_order_restriction, to ensure the join order is OK?
+ *
+ * The optimizer/README is not very clear about this, but maybe it's
+ * a too specific question. It seems to say the relations in those
+ * lists can be joined in any order (lines 94 and 106). Maybe that's
+ * not what it means, or I'm misunderstanding it.
+ *
+ * It however seems has_join_restrictions() in join_search_one_level()
+ * forces the code to look only at "earlier" rels in the list
+ *
+ * first_rel = foreach_current_index(r) + 1
+ *
+ * So maybe we just need to stop once we find a rel with a restriction,
+ * as determined byhas_join_restrictions()?
+ *
+ * But there's also join_is_legal() to check legality of joins, with
+ * LEFT/RIGHT joins, and IN/EXISTS clauses. See README line 188. And it
+ * also looks-up the SpecialJoinInfo for the join. So maybe we should
+ * lookup RelOptInfo for both sides of the join, and call join_is_legal
+ * on that? Might be too expensive, though. Maybe do that only when
+ * has_join_restrictions already says yes?
+ *
+ * Maybe we should use has_join_restrictions(), but in a different way.
+ * We could still treat rels with restrictions as dimensions, and move
+ * that to the separate list (that doesn't change the join order), but
+ * stop once we hit the first non-dimension with a restriction? Because
+ * if any relation after that was a dimention, we wouldn't be able to
+ * move it to the separate list. It'd change the join order in a way
+ * that might violate the restriction. I believe that's the idea behind
+ * first_rel in join_search_one_level(), but maybe not.
+ *
+ * Perhaps have_join_order_restriction and have_relevant_joinclause are
+ * useful for this, rather than has_join_restrictions? We might look at
+ * actual pairs of relations, and/or check there's no join order
+ * restriction with respect to the relations we skipped/moved to the
+ * list of dimension?
+ *
+ * AFAICS it's just the skipping that can break the order restrictions?
+ * Adding something to the list of dimensions keeps the order (at least
+ * with respect to the rels after it).
+ */
+static bool
+starjoin_is_dimension(PlannerInfo *root, RangeTblRef *rtr)
+{
+ Index rti = rtr->rtindex;
+ RangeTblEntry *rte = root->simple_rte_array[rti];
+ RelOptInfo *rel = root->simple_rel_array[rti];
+
+ /* only plain relations can be dimensions (we need FK/PK join) */
+ if ((rte->rtekind != RTE_RELATION) ||
+ (rel->reloptkind != RELOPT_BASEREL))
+ return false;
+
+ /*
+ * Does it have any conditions/restrictions that may affect the number
+ * of rows matched? If yes, don't treat as dimension.
+ *
+ * Dimensions in a starjoin may have restrictions, but that means it'll
+ * change cardinality of the joins (reduce it), so it may be better to
+ * join it early. We leave it to the regular join order planning. The
+ * expectation is that most dimensions won't have extra restrictions.
+ *
+ * XXX Should we check some other fields, like lateral references, and
+ * so on? Or is that unnecessary? What about eclasses?
+ */
+ if (rel->baserestrictinfo != NIL)
+ return false;
+
+ /*
+ * See if the join clause matches a foreign key. It should match a
+ * single relation on the other side, and the dimension should be on
+ * the PK side.
+ *
+ * XXX loosely inspired by get_foreign_key_join_selectivity()
+ */
+ if (!starjoin_match_to_foreign_key(root, rel))
+ return false;
+
+ /*
+ * XXX Maybe some additional checks here ...
+ */
+
+ return true;
+}
+
+/*
+ * starjoin_adjust_joins
+ * Adjust the jointree for starjoins, to simplify the join order search.
+ *
+ * The join search for starjoin queries is surprisingly expensive, because
+ * there are very few join order restrictions. Consider a starjoin query
+ *
+ * SELECT * FROM f
+ * JOIN d1 ON (f.id1 = d1.id)
+ * JOIN d2 ON (f.id2 = d2.id)
+ * ...
+ * JOIN d9 ON (f.id9 = d9.id)
+ *
+ * There are no clauses between the dimension tables (d#), which means those
+ * tables can be joined in almost arbitrary order. This means the standard
+ * join_order_search() would explore a N! possible join orders. It is not
+ * that bad in practice, because we split the problem by from_collapse_limit
+ * into a sequence of smaller problems, but even for the default limit of
+ * 8 relations it's quite expensive. This can be easily demonstrated by
+ * setting from_collapse_limit=1 for example starjoin queries.
+ *
+ * The idea here is to apply a much simpler join order search for this type
+ * of queries, without too much risk of picking a much worse plans. It is
+ * however a trade off between how expensive we allow this to be, and how
+ * good the decisions will be. This can help only starjoins with multiple
+ * dimension tables, and we don't want to harm planning of other queries,
+ * so the basic "query shape" detection needs to be very cheap. And then
+ * it needs to be cheaper than the regular join order search.
+ *
+ * If a perfect check is impossible or too expensive, it's better to end
+ * up with a cheap false negative (i.e. and not use the optimization),
+ * rather than risk regressions in other cases.
+ *
+ * The simplified join order search relies on the fact that if the joins
+ * to dimensions do not alter the cardinality of the join relation, then
+ * the relative order of those joins does not matter. All the possible
+ * orders are guaranteed to perform the same. So we can simply pick one
+ * of those orders, and "hardcode" it in the join tree later passed to the
+ * join_order_search().
+ *
+ * The query may involve joins to additional (non-dimension) tables, and
+ * those may alter cardinality. Some joins may increase it, other joins
+ * may decrease it. In principle, it'd be best to first perform all the
+ * joins that reduce join size, then join all the dimensions, and finally
+ * perform joins that may increase the join size. But this is not done
+ * now, currently we simply apply all the dimensions at the end, hoping
+ * that the earlier joins did not inflate the join too much.
+ *
+ * The definition of a dimension is a bit vague. For our definition see
+ * the comment at starjoin_is_dimension().
+ *
+ * The optimization works by manipulating the joinlist (originally built
+ * by deconstruct_jointree), which decomposed the original jointree into
+ * smaller "problems" depending on join type and join_collapse_limit. We
+ * inspect those smaller lists, and selectively split them into smaller
+ * problems to force a join order. This may effectively undo some of the
+ * merging done by deconstruct_jointree(), which tries to build problems
+ * with up to join_collapse_limit relations.
+ *
+ * For example, imagine a join problem with 8 rels - one fact table and
+ * then 7 dimensions, which we can represent a joinlist with 8 elements.
+ *
+ * (D7, D6, D5, D4, D3, D2, D1, F)
+ *
+ * Assuming all those joins meet the requirements (have a matching FK,
+ * don't affect the join cardinality, ...), then we can split this into
+ *
+ * (D7, (D6, (D5, (D4, (D3, (D2, (D1, F)))))))
+ *
+ * which is a nested joinlist, with only two elements on each level. That
+ * means there's no need for expensive join order search, there's only
+ * one way to join the relations (two, if we consider the relations may
+ * switch sides).
+ *
+ * The joinlist may already be nested, with multiple smaller subproblems.
+ * We look at each individual join problem independently, i.e. we don't
+ * try to merge problems to build join_collapse_limit problems again.
+ * This is partially to keep it cheap/simple, but also so not change
+ * behavior for cases when people use join_collapse_limit to force some
+ * particular join shape.
+ *
+ * XXX A possible improvement is to allow handling snowflake joins, i.e.
+ * recursive dimensions. That would require a somewhat more complicated
+ * processing, because a dimension would be allowed other rels, as long
+ * as those are dimensions too. And we'd need to be more careful about
+ * the order in which join them to the top of the join.
+ *
+ * XXX One possible risk is that moving the dimension joins at the very
+ * end may move that after joins that increase the cardinality. Which
+ * may cause a regression. Such joins however don't seem very common, at
+ * least in regular starjoin queries. So maybe we could simply check if
+ * there are any such joins and disable this optimization. Is there a
+ * cheap way to identify that a join increases cardinality?
+ *
+ * XXX Ideally, we'd perform the dimension joins at the place with the
+ * lowest cardinality. Imagine a joinlist
+ *
+ * (D1, D2, A, B, F)
+ *
+ * Where A increases join cardinality, while B does not (possibly even
+ * reduces it). Ideally, we'd do the join like this
+ *
+ * (A, (D2, (D1, (B, F))))
+ *
+ * so D1/D2 get joined at the point of "lowest cardinality". We probably
+ * don't want to do all this cardinality estimation work here, it'd copy
+ * what we already do in the join_order_search(). Perhaps we could invent
+ * a "join item" representing a join to all those dimensions, and pass it
+ * to join_order_search()? And let it pick the right place for it? It'd
+ * always join them in the same order, it'd not reorder them. It would
+ * still do the regular cardinality estimations etc. It would be trivial
+ * to disable the optimization if needed - don't collapse the dimensions
+ * into the new type of join item.
+ */
+List *
+starjoin_adjust_joins(PlannerInfo *root, List *joinlist)
+{
+ ListCell *lc;
+ List *newlist = NIL;
+ List *dimensions = NIL;
+
+ /*
+ * Do nothing if starjoin optimization not enabled / not applicable.
+ *
+ * XXX It might seems we can skip this for lists with <= 2 items, but
+ * that does not work, the elements may be nested list, and we need to
+ * descend into those. So do what remove_useless_self_joins() does, and
+ * only bail out for the simplest single-relation case (i.e. no joins).
+ */
+ if (!enable_starjoin_join_search || joinlist == NIL ||
+ (list_length(joinlist) == 1 && !IsA(linitial(joinlist), List)))
+ return joinlist;
+
+ /*
+ * Process the current join problem - split the elements into dimensions
+ * and non-dimensions. If there are dimensions, add them back at the end,
+ * as small single-rel joins.
+ *
+ * The list may contain various types of elements. It may contain a list,
+ * which means it's an independent join search problem and we need to
+ * process it recursively. Or it may be RangeTblRef, in which case we
+ * need to check if it's a dimension. Other types of elements are just
+ * added back to the list as-is.
+ *
+ * XXX I think we need to be careful to keep the order of the list (for
+ * the non-dimension entries). The join_search_one_level() relies on
+ * that when handling join order restrictions.
+ *
+ * XXX It might be better to only create a new list if needed, i.e. once
+ * we find the first dimension. So that non-starjoin queries don't pay
+ * for something they don't need. A mutable iterator might be a way, but
+ * I'm not sure how expensive this really is.
+ */
+ foreach (lc, joinlist)
+ {
+ Node *item = (Node *) lfirst(lc);
+
+ /* a separate join search problem, handle it recursively */
+ if (IsA(item, List))
+ {
+ newlist = lappend(newlist,
+ starjoin_adjust_joins(root, (List *) item));
+ continue;
+ }
+
+ /*
+ * Non-RangeTblRef elements can't be considered a dimension (only
+ * baserels can have FK, etc.), so just add those to the list.
+ */
+ if (!IsA(item, RangeTblRef))
+ {
+ newlist = lappend(newlist, item);
+ continue;
+ }
+
+ /*
+ * An entry representing a baserel. If it's a dimension, save it in
+ * a separate list, and we'll add it at the "top" of the join at the
+ * end. Otherwise add it to the list just like other elements.
+ */
+ if (starjoin_is_dimension(root, (RangeTblRef *) item))
+ {
+ dimensions = lappend(dimensions, item);
+ continue;
+ }
+
+ /* not a dimension, add it to the list directly */
+ newlist = lappend(newlist, item);
+ }
+
+ /*
+ * If we found some dimensions, add them to the join tree one by one.
+ * The exact order does not matter, so we add them in the order we
+ * found them in the original list.
+ *
+ * We need to add them by creating smaller 2-element lists, with the
+ * rest of the list on one side and the dimension on the other. This
+ * is how we force the explicit join order.
+ */
+ foreach (lc, dimensions)
+ {
+ newlist = list_make2(newlist, list_make1(lfirst(lc)));
+ }
+
+ return newlist;
+}
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 5467e094ca7..c75a5203aae 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -282,6 +282,16 @@ query_planner(PlannerInfo *root,
*/
distribute_row_identity_vars(root);
+ /*
+ * Try to simplify the join search problem for starjoin-like joins, with
+ * joins over FK relationships. The dimensions can be joined in almost
+ * any order, so the join search can be close to factorial complexity.
+ * But there's not much difference between such join orders, so we just
+ * leave the dimensions at the end of each group (as determined by the
+ * join_collapse_limit earlier).
+ */
+ joinlist = starjoin_adjust_joins(root, joinlist);
+
/*
* Ready to do the primary planning.
*/
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index d14b1678e7f..4c7642b3102 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -1036,6 +1036,16 @@ struct config_bool ConfigureNamesBool[] =
true,
NULL, NULL, NULL
},
+ {
+ {"enable_starjoin_join_search", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("Enables simplified join order planning for starjoins."),
+ NULL,
+ GUC_EXPLAIN
+ },
+ &enable_starjoin_join_search,
+ false,
+ NULL, NULL, NULL
+ },
{
{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
gettext_noop("Enables genetic query optimization."),
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 9d3debcab28..fee6c695d03 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -21,6 +21,7 @@
#define DEFAULT_CURSOR_TUPLE_FRACTION 0.1
extern PGDLLIMPORT double cursor_tuple_fraction;
extern PGDLLIMPORT bool enable_self_join_elimination;
+extern PGDLLIMPORT bool enable_starjoin_join_search;
/* query_planner callback to compute query_pathkeys */
typedef void (*query_pathkeys_callback) (PlannerInfo *root, void *extra);
@@ -119,6 +120,7 @@ extern bool innerrel_is_unique_ext(PlannerInfo *root, Relids joinrelids,
JoinType jointype, List *restrictlist,
bool force_cache, List **extra_clauses);
extern List *remove_useless_self_joins(PlannerInfo *root, List *joinlist);
+extern List *starjoin_adjust_joins(PlannerInfo *root, List *joinlist);
/*
* prototypes for plan/setrefs.c
--
2.50.1
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-02-08 01:49 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-07-28 19:44 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
@ 2025-09-23 19:46 ` Tom Lane <[email protected]>
2025-11-08 20:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
0 siblings, 1 reply; 20+ messages in thread
From: Tom Lane @ 2025-09-23 19:46 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: James Hunter <[email protected]>; Richard Guo <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
[ sorry for ridiculously slow response to this ]
Tomas Vondra <[email protected]> writes:
> Here's a patch trying to do it more like this - by manipulating the
> lists describing the join problems, before it's passed the the actual
> join search algorithm (which is where the PoC patch did this).
> I wonder if this is roughly the place where you imagined this would be
> done, or if you envision some other issue with this approach.
Cool. This is proof-of-concept that manipulating the joinlist can
do what we need done. So we can move on to what heuristics we need
to use.
> I initially tried to manipulate the joinlist much earlier - pretty much
> right at the end of deconstruct_jointree. But that turned out to be way
> too early. To identify dimensions etc. we need to check stuff about
> foreign keys, join clauses, ... and that's not available that early.
> So I think this needs to happen much later in query_planner(), and the
> patch does it right before the make_one_rel() call. Maybe that's too
> late, but it needs to happen after match_foreign_keys_to_quals(), as it
> relies on some of the FK info built by that call. Maybe we could call
> match_foreign_keys_to_quals() earlier, but I don't quite see any
> benefits of doing that ...
I don't have a problem with doing it where you did it, but the comment
should explain the placement. What you do have in the comment mostly
belongs with the code, too; it's not the business of the caller. So
in planmain.c something like
+ /*
+ * Try to simplify the join search problem for starjoin-like joins.
+ * This step relies on info about FK relationships, so we can't do it
+ * till after match_foreign_keys_to_quals().
+ */
would be more appropriate IMO. I'd be slightly inclined to put the
GUC test there, too:
+ if (enable_starjoin_join_search)
+ joinlist = starjoin_adjust_joins(root, joinlist);
I agree that you need to worry about join order restrictions,
and that it's not immediately clear how to do that. join_is_legal
would work if we could call it, but the problem is that at this
stage we'll only have RelOptInfos for base rels not join rels.
If we have a joinlist (A B C D) and we are considering treating
C as a dimension table, then the questions we have to ask are:
(a) is it okay to build the (A B D) join without C?
(b) is it okay to join (A B D) to C?
In this simple case, I think (b) must be true if (a) is, but
I'm not quite sure that that's so in more complex cases with
multiple candidates for dimension tables. In any case,
join_is_legal won't help us if we don't have join RelOptInfos.
I'm inclined to start by using has_join_restriction: if that
says "false" for a candidate dimension table, it should be safe
to postpone the join to the dimension table. We might be able
to refine that later.
> The second example (create-2/select-2) is quite different, in that it's
> nor a starjoin schema. It still joins one "main" table with multiple
> "dimensions", but the FKs go in the other direction (to a single column
> in the main table). But it has a very similar bottleneck - the order of
> the joins is expensive, but it often does not matter very much, because
> the query matches just one row anyway. And even if it returns more rows,
> isn't the join order determined just by the selectivity of each join?
> Maybe the starjoin optimization could be made to work for this type too?
Yeah, I'm slightly itchy about relying on FKs in this heuristic at
all; it doesn't seem like quite the right thing. I think we do want
one side of the join to be joining to a PK or at least a unique index,
but I'm not sure we need to insist on there being an FK relationship.
A couple of minor coding notes:
* There's no point in doing anything (except recursing) if the joinlist
contains fewer than 3 items, and maybe as a further heuristic
this shouldn't kick in till later yet, like 5 or so items.
When there are just a few items, the possibility of missing the
best plan seems to outweigh the minimal savings in plan time.
* Joinlists never contain anything but RangeTblRefs and sub-lists.
See make_rel_from_joinlist.
* Your reconstructed joinlist is overly complicated. Instead of
+ newlist = list_make2(newlist, list_make1(lfirst(lc)));
you could just do
+ newlist = list_make2(newlist, lfirst(lc));
because a single-element subproblem is useless.
I notice that the patch doesn't apply cleanly anymore because of
the introduction of guc_parameters.dat. So here's a v3 that
rebases over that, and I took the liberty of fixing the joinlist
construction as above, but I didn't do anything else.
regards, tom lane
Attachments:
[text/x-diff] v3-0001-Simplify-planning-of-starjoin-queries.patch (20.4K, ../../[email protected]/2-v3-0001-Simplify-planning-of-starjoin-queries.patch)
download | inline diff:
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 2a3dea88a94..5417c10fbf8 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -51,6 +51,7 @@ typedef struct
} SelfJoinCandidate;
bool enable_self_join_elimination;
+bool enable_starjoin_join_search;
/* local functions */
static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
@@ -2514,3 +2515,427 @@ remove_useless_self_joins(PlannerInfo *root, List *joinlist)
return joinlist;
}
+
+/*
+ * starjoin_match_to_foreign_key
+ * Try to match a join to a FK constraint.
+ *
+ * For a relation to be a dimension (for the starjoin heuristics), it needs
+ * to be joined through a FK constraint. The dimension is expected to be
+ * on the PK side of the join. The relation must not have any additional
+ * join clauses, beyond those matching the foreign key.
+ *
+ * We already have a list of relevant foreign keys, and we use that info
+ * for selectivity estimation in get_foreign_key_join_selectivity(). And
+ * we're actually doing something quite similar here.
+ *
+ * XXX Do we need to worry about the join type, e.g. inner/outer joins,
+ * semi/anti? get_foreign_key_join_selectivity() does care about it, and
+ * ignores some of those cases. Maybe we should too?
+ *
+ * XXX Check there are no other join clauses, beyond those matching the
+ * foreign key. But do we already have the joininfo at this point? Some
+ * of this stuff gets build only during the join order search later.
+ * The match_foreign_keys_to_quals() probably needs to be aware of all
+ * this, so how does it do that?
+ */
+static bool
+starjoin_match_to_foreign_key(PlannerInfo *root, RelOptInfo *rel)
+{
+ ListCell *lc;
+
+ /* Consider each FK constraint that is known to match the query */
+ foreach(lc, root->fkey_list)
+ {
+ ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+ int nmatches = 0;
+
+ /* rel is not the referenced table of the FK */
+ if (fkinfo->ref_relid != rel->relid)
+ continue;
+
+ /*
+ * Do we have a match for each key of the FK?
+ *
+ * XXX get_foreign_key_join_selectivity checks EquivalenceClasses,
+ * we should probably (definitely) do that here too.
+ *
+ * XXX We should check that all the clauses have the same relation
+ * on the other side (for multi-column keys). And that there are
+ * no other join clauses other than those matching the FK.
+ *
+ * XXX Do we need to check that the FK side of the join (i.e. the fact
+ * table) has the columns referenced as NOT NULL? Otherwise we could
+ * have a FK join that reduces the cardinality, which is one of
+ * the arguments why it's fine to move the join (that it doesn't
+ * change the cardinality). But if the join is LEFT JOIN, this
+ * should be fine too - but do we get here with LEFT JOINs?
+ *
+ * XXX Do we need to check if the other side of the FK is in the
+ * current join list? Maybe it's in some later one?
+ */
+ for (int i = 0; i < fkinfo->nkeys; i++)
+ {
+ bool has_matching_clause = false;
+
+ /*
+ * Is there a clause matching this FK key?
+ *
+ * XXX We need to make sure it's a valid match, e.g. that the
+ * same referencing table matches all keys in a composite FK,
+ * and so on.
+ *
+ * XXX Do we need to check some relationship to other rels in
+ * the same jointree item? E.g. the referencing table should
+ * not be a dimensions we already removed.
+ */
+ if ((fkinfo->rinfos[i] != NULL) || (fkinfo->eclass[i] != NULL))
+ {
+ has_matching_clause = true;
+ nmatches++;
+ continue;
+ }
+
+ /* found a FK key without a matching join clause, ignore the FK */
+ if (has_matching_clause)
+ break;
+ }
+
+ /* matched all FK keys */
+ if (nmatches == fkinfo->nkeys)
+ {
+ return true;
+ }
+ }
+
+ return false;
+}
+
+
+/*
+ * starjoin_is_dimension
+ * Determine if a range table entry is a dimension in a starjoin.
+ *
+ * To be considered a dimension for the simplified join order search, the
+ * join must not affect the cardinality of the join. We ensure that by
+ * requiring a couple things:
+ *
+ * 1) the join clause has to match a FK (that is, the fact does have at
+ * most one matching row in the dimension)
+ *
+ * 2) the FK side (the fact table) should be marked as NOT NULL, so that
+ * we know there's exactly one dimension row for each fact table row
+ *
+ * 3) there must be no additional restrictions on the relation (that
+ * might eliminate some of the rows, reducing the cardinality)
+ *
+ * XXX The Implementation is incomplete. It probably needs more thought,
+ * considering some join types would allow relaxing some of the checks
+ * (e.g. outer joins may not require checking (2) or possibly even (3),
+ * depending on where the condition is, what varnullingrels it has).
+ *
+ * XXX I wonder if we could handle (3) by ordering the dimensions by the
+ * selectivity of the restriction. There are no join clauses between the
+ * dimensions (ignoring the snowflake joins, but even there the clauses
+ * don't go between branches), so the selectivity could be treated as
+ * a measure of how much it shrinks the join result. So we could just
+ * sort the dimensions by this, starting with the lowest selectivity
+ * (close to 0.0), and ending with dimensions without restrictions (in
+ * which case the selectivity is 1.0).
+ *
+ * XXX If the join in INNER, and the fact side has NULL values in the
+ * join key, we might consider nullfrac as restriction.
+ *
+ * XXX I'm not sure how careful this needs to be about join order
+ * restrictions. Maybe it should call have_relevant_joinclause and
+ * have_join_order_restriction, to ensure the join order is OK?
+ *
+ * The optimizer/README is not very clear about this, but maybe it's
+ * a too specific question. It seems to say the relations in those
+ * lists can be joined in any order (lines 94 and 106). Maybe that's
+ * not what it means, or I'm misunderstanding it.
+ *
+ * It however seems has_join_restrictions() in join_search_one_level()
+ * forces the code to look only at "earlier" rels in the list
+ *
+ * first_rel = foreach_current_index(r) + 1
+ *
+ * So maybe we just need to stop once we find a rel with a restriction,
+ * as determined byhas_join_restrictions()?
+ *
+ * But there's also join_is_legal() to check legality of joins, with
+ * LEFT/RIGHT joins, and IN/EXISTS clauses. See README line 188. And it
+ * also looks-up the SpecialJoinInfo for the join. So maybe we should
+ * lookup RelOptInfo for both sides of the join, and call join_is_legal
+ * on that? Might be too expensive, though. Maybe do that only when
+ * has_join_restrictions already says yes?
+ *
+ * Maybe we should use has_join_restrictions(), but in a different way.
+ * We could still treat rels with restrictions as dimensions, and move
+ * that to the separate list (that doesn't change the join order), but
+ * stop once we hit the first non-dimension with a restriction? Because
+ * if any relation after that was a dimention, we wouldn't be able to
+ * move it to the separate list. It'd change the join order in a way
+ * that might violate the restriction. I believe that's the idea behind
+ * first_rel in join_search_one_level(), but maybe not.
+ *
+ * Perhaps have_join_order_restriction and have_relevant_joinclause are
+ * useful for this, rather than has_join_restrictions? We might look at
+ * actual pairs of relations, and/or check there's no join order
+ * restriction with respect to the relations we skipped/moved to the
+ * list of dimension?
+ *
+ * AFAICS it's just the skipping that can break the order restrictions?
+ * Adding something to the list of dimensions keeps the order (at least
+ * with respect to the rels after it).
+ */
+static bool
+starjoin_is_dimension(PlannerInfo *root, RangeTblRef *rtr)
+{
+ Index rti = rtr->rtindex;
+ RangeTblEntry *rte = root->simple_rte_array[rti];
+ RelOptInfo *rel = root->simple_rel_array[rti];
+
+ /* only plain relations can be dimensions (we need FK/PK join) */
+ if ((rte->rtekind != RTE_RELATION) ||
+ (rel->reloptkind != RELOPT_BASEREL))
+ return false;
+
+ /*
+ * Does it have any conditions/restrictions that may affect the number
+ * of rows matched? If yes, don't treat as dimension.
+ *
+ * Dimensions in a starjoin may have restrictions, but that means it'll
+ * change cardinality of the joins (reduce it), so it may be better to
+ * join it early. We leave it to the regular join order planning. The
+ * expectation is that most dimensions won't have extra restrictions.
+ *
+ * XXX Should we check some other fields, like lateral references, and
+ * so on? Or is that unnecessary? What about eclasses?
+ */
+ if (rel->baserestrictinfo != NIL)
+ return false;
+
+ /*
+ * See if the join clause matches a foreign key. It should match a
+ * single relation on the other side, and the dimension should be on
+ * the PK side.
+ *
+ * XXX loosely inspired by get_foreign_key_join_selectivity()
+ */
+ if (!starjoin_match_to_foreign_key(root, rel))
+ return false;
+
+ /*
+ * XXX Maybe some additional checks here ...
+ */
+
+ return true;
+}
+
+/*
+ * starjoin_adjust_joins
+ * Adjust the jointree for starjoins, to simplify the join order search.
+ *
+ * The join search for starjoin queries is surprisingly expensive, because
+ * there are very few join order restrictions. Consider a starjoin query
+ *
+ * SELECT * FROM f
+ * JOIN d1 ON (f.id1 = d1.id)
+ * JOIN d2 ON (f.id2 = d2.id)
+ * ...
+ * JOIN d9 ON (f.id9 = d9.id)
+ *
+ * There are no clauses between the dimension tables (d#), which means those
+ * tables can be joined in almost arbitrary order. This means the standard
+ * join_order_search() would explore a N! possible join orders. It is not
+ * that bad in practice, because we split the problem by from_collapse_limit
+ * into a sequence of smaller problems, but even for the default limit of
+ * 8 relations it's quite expensive. This can be easily demonstrated by
+ * setting from_collapse_limit=1 for example starjoin queries.
+ *
+ * The idea here is to apply a much simpler join order search for this type
+ * of queries, without too much risk of picking a much worse plans. It is
+ * however a trade off between how expensive we allow this to be, and how
+ * good the decisions will be. This can help only starjoins with multiple
+ * dimension tables, and we don't want to harm planning of other queries,
+ * so the basic "query shape" detection needs to be very cheap. And then
+ * it needs to be cheaper than the regular join order search.
+ *
+ * If a perfect check is impossible or too expensive, it's better to end
+ * up with a cheap false negative (i.e. and not use the optimization),
+ * rather than risk regressions in other cases.
+ *
+ * The simplified join order search relies on the fact that if the joins
+ * to dimensions do not alter the cardinality of the join relation, then
+ * the relative order of those joins does not matter. All the possible
+ * orders are guaranteed to perform the same. So we can simply pick one
+ * of those orders, and "hardcode" it in the join tree later passed to the
+ * join_order_search().
+ *
+ * The query may involve joins to additional (non-dimension) tables, and
+ * those may alter cardinality. Some joins may increase it, other joins
+ * may decrease it. In principle, it'd be best to first perform all the
+ * joins that reduce join size, then join all the dimensions, and finally
+ * perform joins that may increase the join size. But this is not done
+ * now, currently we simply apply all the dimensions at the end, hoping
+ * that the earlier joins did not inflate the join too much.
+ *
+ * The definition of a dimension is a bit vague. For our definition see
+ * the comment at starjoin_is_dimension().
+ *
+ * The optimization works by manipulating the joinlist (originally built
+ * by deconstruct_jointree), which decomposed the original jointree into
+ * smaller "problems" depending on join type and join_collapse_limit. We
+ * inspect those smaller lists, and selectively split them into smaller
+ * problems to force a join order. This may effectively undo some of the
+ * merging done by deconstruct_jointree(), which tries to build problems
+ * with up to join_collapse_limit relations.
+ *
+ * For example, imagine a join problem with 8 rels - one fact table and
+ * then 7 dimensions, which we can represent a joinlist with 8 elements.
+ *
+ * (D7, D6, D5, D4, D3, D2, D1, F)
+ *
+ * Assuming all those joins meet the requirements (have a matching FK,
+ * don't affect the join cardinality, ...), then we can split this into
+ *
+ * (D7, (D6, (D5, (D4, (D3, (D2, (D1, F)))))))
+ *
+ * which is a nested joinlist, with only two elements on each level. That
+ * means there's no need for expensive join order search, there's only
+ * one way to join the relations (two, if we consider the relations may
+ * switch sides).
+ *
+ * The joinlist may already be nested, with multiple smaller subproblems.
+ * We look at each individual join problem independently, i.e. we don't
+ * try to merge problems to build join_collapse_limit problems again.
+ * This is partially to keep it cheap/simple, but also so not change
+ * behavior for cases when people use join_collapse_limit to force some
+ * particular join shape.
+ *
+ * XXX A possible improvement is to allow handling snowflake joins, i.e.
+ * recursive dimensions. That would require a somewhat more complicated
+ * processing, because a dimension would be allowed other rels, as long
+ * as those are dimensions too. And we'd need to be more careful about
+ * the order in which join them to the top of the join.
+ *
+ * XXX One possible risk is that moving the dimension joins at the very
+ * end may move that after joins that increase the cardinality. Which
+ * may cause a regression. Such joins however don't seem very common, at
+ * least in regular starjoin queries. So maybe we could simply check if
+ * there are any such joins and disable this optimization. Is there a
+ * cheap way to identify that a join increases cardinality?
+ *
+ * XXX Ideally, we'd perform the dimension joins at the place with the
+ * lowest cardinality. Imagine a joinlist
+ *
+ * (D1, D2, A, B, F)
+ *
+ * Where A increases join cardinality, while B does not (possibly even
+ * reduces it). Ideally, we'd do the join like this
+ *
+ * (A, (D2, (D1, (B, F))))
+ *
+ * so D1/D2 get joined at the point of "lowest cardinality". We probably
+ * don't want to do all this cardinality estimation work here, it'd copy
+ * what we already do in the join_order_search(). Perhaps we could invent
+ * a "join item" representing a join to all those dimensions, and pass it
+ * to join_order_search()? And let it pick the right place for it? It'd
+ * always join them in the same order, it'd not reorder them. It would
+ * still do the regular cardinality estimations etc. It would be trivial
+ * to disable the optimization if needed - don't collapse the dimensions
+ * into the new type of join item.
+ */
+List *
+starjoin_adjust_joins(PlannerInfo *root, List *joinlist)
+{
+ ListCell *lc;
+ List *newlist = NIL;
+ List *dimensions = NIL;
+
+ /*
+ * Do nothing if starjoin optimization not enabled / not applicable.
+ *
+ * XXX It might seems we can skip this for lists with <= 2 items, but
+ * that does not work, the elements may be nested list, and we need to
+ * descend into those. So do what remove_useless_self_joins() does, and
+ * only bail out for the simplest single-relation case (i.e. no joins).
+ */
+ if (!enable_starjoin_join_search || joinlist == NIL ||
+ (list_length(joinlist) == 1 && !IsA(linitial(joinlist), List)))
+ return joinlist;
+
+ /*
+ * Process the current join problem - split the elements into dimensions
+ * and non-dimensions. If there are dimensions, add them back at the end,
+ * as small single-rel joins.
+ *
+ * The list may contain various types of elements. It may contain a list,
+ * which means it's an independent join search problem and we need to
+ * process it recursively. Or it may be RangeTblRef, in which case we
+ * need to check if it's a dimension. Other types of elements are just
+ * added back to the list as-is.
+ *
+ * XXX I think we need to be careful to keep the order of the list (for
+ * the non-dimension entries). The join_search_one_level() relies on
+ * that when handling join order restrictions.
+ *
+ * XXX It might be better to only create a new list if needed, i.e. once
+ * we find the first dimension. So that non-starjoin queries don't pay
+ * for something they don't need. A mutable iterator might be a way, but
+ * I'm not sure how expensive this really is.
+ */
+ foreach (lc, joinlist)
+ {
+ Node *item = (Node *) lfirst(lc);
+
+ /* a separate join search problem, handle it recursively */
+ if (IsA(item, List))
+ {
+ newlist = lappend(newlist,
+ starjoin_adjust_joins(root, (List *) item));
+ continue;
+ }
+
+ /*
+ * Non-RangeTblRef elements can't be considered a dimension (only
+ * baserels can have FK, etc.), so just add those to the list.
+ */
+ if (!IsA(item, RangeTblRef))
+ {
+ newlist = lappend(newlist, item);
+ continue;
+ }
+
+ /*
+ * An entry representing a baserel. If it's a dimension, save it in
+ * a separate list, and we'll add it at the "top" of the join at the
+ * end. Otherwise add it to the list just like other elements.
+ */
+ if (starjoin_is_dimension(root, (RangeTblRef *) item))
+ {
+ dimensions = lappend(dimensions, item);
+ continue;
+ }
+
+ /* not a dimension, add it to the list directly */
+ newlist = lappend(newlist, item);
+ }
+
+ /*
+ * If we found some dimensions, add them to the join tree one by one.
+ * The exact order does not matter, so we add them in the order we
+ * found them in the original list.
+ *
+ * We need to add them by creating smaller 2-element lists, with the rest
+ * of the list being a sub-problem and then adding the dimension
+ * table. This is how we force the desired join order.
+ */
+ foreach (lc, dimensions)
+ {
+ newlist = list_make2(newlist, lfirst(lc));
+ }
+
+ return newlist;
+}
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 5467e094ca7..c75a5203aae 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -282,6 +282,16 @@ query_planner(PlannerInfo *root,
*/
distribute_row_identity_vars(root);
+ /*
+ * Try to simplify the join search problem for starjoin-like joins, with
+ * joins over FK relationships. The dimensions can be joined in almost
+ * any order, so the join search can be close to factorial complexity.
+ * But there's not much difference between such join orders, so we just
+ * leave the dimensions at the end of each group (as determined by the
+ * join_collapse_limit earlier).
+ */
+ joinlist = starjoin_adjust_joins(root, joinlist);
+
/*
* Ready to do the primary planning.
*/
diff --git a/src/backend/utils/misc/guc_parameters.dat b/src/backend/utils/misc/guc_parameters.dat
index 6bc6be13d2a..bde4378527e 100644
--- a/src/backend/utils/misc/guc_parameters.dat
+++ b/src/backend/utils/misc/guc_parameters.dat
@@ -203,6 +203,13 @@
boot_val => 'true',
},
+{ name => 'enable_starjoin_join_search', type => 'bool', context => 'PGC_USERSET', group => 'QUERY_TUNING_METHOD',
+ short_desc => 'Enables simplified join order planning for starjoins.',
+ flags => 'GUC_EXPLAIN',
+ variable => 'enable_starjoin_join_search',
+ boot_val => 'false',
+},
+
{ name => 'geqo', type => 'bool', context => 'PGC_USERSET', group => 'QUERY_TUNING_GEQO',
short_desc => 'Enables genetic query optimization.',
long_desc => 'This algorithm attempts to do planning without exhaustive searching.',
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 9d3debcab28..fee6c695d03 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -21,6 +21,7 @@
#define DEFAULT_CURSOR_TUPLE_FRACTION 0.1
extern PGDLLIMPORT double cursor_tuple_fraction;
extern PGDLLIMPORT bool enable_self_join_elimination;
+extern PGDLLIMPORT bool enable_starjoin_join_search;
/* query_planner callback to compute query_pathkeys */
typedef void (*query_pathkeys_callback) (PlannerInfo *root, void *extra);
@@ -119,6 +120,7 @@ extern bool innerrel_is_unique_ext(PlannerInfo *root, Relids joinrelids,
JoinType jointype, List *restrictlist,
bool force_cache, List **extra_clauses);
extern List *remove_useless_self_joins(PlannerInfo *root, List *joinlist);
+extern List *starjoin_adjust_joins(PlannerInfo *root, List *joinlist);
/*
* prototypes for plan/setrefs.c
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-02-08 01:49 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-07-28 19:44 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-09-23 19:46 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
@ 2025-11-08 20:14 ` Tomas Vondra <[email protected]>
2025-11-08 20:36 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
0 siblings, 1 reply; 20+ messages in thread
From: Tomas Vondra @ 2025-11-08 20:14 UTC (permalink / raw)
To: Tom Lane <[email protected]>; +Cc: James Hunter <[email protected]>; Richard Guo <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
On 9/23/25 21:46, Tom Lane wrote:
> [ sorry for ridiculously slow response to this ]
>
> Tomas Vondra <[email protected]> writes:
>> Here's a patch trying to do it more like this - by manipulating the
>> lists describing the join problems, before it's passed the the actual
>> join search algorithm (which is where the PoC patch did this).
>> I wonder if this is roughly the place where you imagined this would be
>> done, or if you envision some other issue with this approach.
>
> Cool. This is proof-of-concept that manipulating the joinlist can
> do what we need done. So we can move on to what heuristics we need
> to use.
>
Thanks. Good to hear this seems like a reasonable place.
>> I initially tried to manipulate the joinlist much earlier - pretty much
>> right at the end of deconstruct_jointree. But that turned out to be way
>> too early. To identify dimensions etc. we need to check stuff about
>> foreign keys, join clauses, ... and that's not available that early.
>
>> So I think this needs to happen much later in query_planner(), and the
>> patch does it right before the make_one_rel() call. Maybe that's too
>> late, but it needs to happen after match_foreign_keys_to_quals(), as it
>> relies on some of the FK info built by that call. Maybe we could call
>> match_foreign_keys_to_quals() earlier, but I don't quite see any
>> benefits of doing that ...
>
> I don't have a problem with doing it where you did it, but the comment
> should explain the placement. What you do have in the comment mostly
> belongs with the code, too; it's not the business of the caller. So
> in planmain.c something like
>
> + /*
> + * Try to simplify the join search problem for starjoin-like joins.
> + * This step relies on info about FK relationships, so we can't do it
> + * till after match_foreign_keys_to_quals().
> + */
>
> would be more appropriate IMO.
I agree. I've adopted your wording, and moved the original comment to
starjoin_adjust_joins (with some changes).
> I'd be slightly inclined to put the GUC test there, too:
>
> + if (enable_starjoin_join_search)
> + joinlist = starjoin_adjust_joins(root, joinlist);
>
I'm not sure I like this very mcuh. No other call in query_planner()
does it like that. Most don't have such GUC, but at least
remove_useless_self_joins does, and it still doesn't check it here.
>
> I agree that you need to worry about join order restrictions,
> and that it's not immediately clear how to do that. join_is_legal
> would work if we could call it, but the problem is that at this
> stage we'll only have RelOptInfos for base rels not join rels.
> If we have a joinlist (A B C D) and we are considering treating
> C as a dimension table, then the questions we have to ask are:
> (a) is it okay to build the (A B D) join without C?
> (b) is it okay to join (A B D) to C?
>
> In this simple case, I think (b) must be true if (a) is, but
> I'm not quite sure that that's so in more complex cases with
> multiple candidates for dimension tables. In any case,
> join_is_legal won't help us if we don't have join RelOptInfos.
>
> I'm inclined to start by using has_join_restriction: if that
> says "false" for a candidate dimension table, it should be safe
> to postpone the join to the dimension table. We might be able
> to refine that later.
>
Thanks. I agree has_join_restriction seems like a good start, I'll give
that a try in the next patch version.
When thinking about this, I realized the has_join_restriction() is only
ever used in join_search_one_level(), i.e. when dealing with each small
join order problem. Doesn't this mean the deconstructed jointree must
already consider the restrictions in some way? I don't see any explicit
mentions of such join order restrictions in deconstruct_recurse. It must
not violate any ordering restrictions by splitting the joins in a
"wrong" way, right? If I set join_collapse_limit=1 it still needs to
satisfy all the rules.
I was wondering if maybe we could piggy-back on that, somehow. But maybe
that's not very practical, and has_join_restriction() is the way to go.
It's been a while since I looked at this patch, so it's possible I
already concluded that wouldn't work, and forgot about it :-/
>> The second example (create-2/select-2) is quite different, in that it's
>> nor a starjoin schema. It still joins one "main" table with multiple
>> "dimensions", but the FKs go in the other direction (to a single column
>> in the main table). But it has a very similar bottleneck - the order of
>> the joins is expensive, but it often does not matter very much, because
>> the query matches just one row anyway. And even if it returns more rows,
>> isn't the join order determined just by the selectivity of each join?
>> Maybe the starjoin optimization could be made to work for this type too?
>
> Yeah, I'm slightly itchy about relying on FKs in this heuristic at
> all; it doesn't seem like quite the right thing. I think we do want
> one side of the join to be joining to a PK or at least a unique index,
> but I'm not sure we need to insist on there being an FK relationship.
>
True, requiring the FK may be unnecessary in this case. We do need to
guarantee the cardinality does not change, but a UNIQUE + LEFT JOIN
seems to be enough for that.
BTW the v3 lost the patch/ directory. I assume that wasn't intentional,
so I added it back into v4.
> A couple of minor coding notes:
>
> * There's no point in doing anything (except recursing) if the joinlist
> contains fewer than 3 items, and maybe as a further heuristic
> this shouldn't kick in till later yet, like 5 or so items.
> When there are just a few items, the possibility of missing the
> best plan seems to outweigh the minimal savings in plan time.
>
> * Joinlists never contain anything but RangeTblRefs and sub-lists.
> See make_rel_from_joinlist.
>
> * Your reconstructed joinlist is overly complicated. Instead of
>
> + newlist = list_make2(newlist, list_make1(lfirst(lc)));
>
> you could just do
>
> + newlist = list_make2(newlist, lfirst(lc));
>
> because a single-element subproblem is useless.
>
> I notice that the patch doesn't apply cleanly anymore because of
> the introduction of guc_parameters.dat. So here's a v3 that
> rebases over that, and I took the liberty of fixing the joinlist
> construction as above, but I didn't do anything else.
>
Thanks. I agree with all of these comments, and updated v4 accordingly.
cfbot started complaining about guc_parameters.dat and a couple more
things, so v4 fixes that too.
regards
--
Tomas Vondra
Attachments:
[text/x-patch] v4-0001-Simplify-planning-of-starjoin-queries.patch (25.7K, ../../[email protected]/2-v4-0001-Simplify-planning-of-starjoin-queries.patch)
download | inline diff:
From b8473cd5c93bf594896d2be40a7f093e90aeca16 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <[email protected]>
Date: Sat, 8 Nov 2025 18:16:30 +0100
Subject: [PATCH v4] Simplify planning of starjoin queries
---
patch/create-1.sql | 18 +
patch/create-2.sql | 11 +
patch/select-1.sql | 9 +
patch/select-2.sql | 9 +
src/backend/optimizer/plan/analyzejoins.c | 443 ++++++++++++++++++
src/backend/optimizer/plan/planmain.c | 7 +
src/backend/utils/misc/guc_parameters.dat | 7 +
src/backend/utils/misc/postgresql.conf.sample | 1 +
src/include/optimizer/planmain.h | 2 +
src/test/regress/expected/sysviews.out | 3 +-
10 files changed, 509 insertions(+), 1 deletion(-)
create mode 100644 patch/create-1.sql
create mode 100644 patch/create-2.sql
create mode 100644 patch/select-1.sql
create mode 100644 patch/select-2.sql
diff --git a/patch/create-1.sql b/patch/create-1.sql
new file mode 100644
index 00000000000..8df04fd0677
--- /dev/null
+++ b/patch/create-1.sql
@@ -0,0 +1,18 @@
+create table dim1 (id int primary key, val1 text);
+create table dim2 (id int primary key, val2 text);
+create table dim3 (id int primary key, val3 text);
+create table dim4 (id int primary key, val4 text);
+create table dim5 (id int primary key, val5 text);
+create table dim6 (id int primary key, val6 text);
+create table dim7 (id int primary key, val7 text);
+
+create table t (id serial primary key,
+ id1 int references dim1(id),
+ id2 int references dim2(id),
+ id3 int references dim3(id),
+ id4 int references dim4(id),
+ id5 int references dim5(id),
+ id6 int references dim6(id),
+ id7 int references dim7(id));
+
+vacuum analyze;
diff --git a/patch/create-2.sql b/patch/create-2.sql
new file mode 100644
index 00000000000..cdf612dde8f
--- /dev/null
+++ b/patch/create-2.sql
@@ -0,0 +1,11 @@
+create table t (id serial primary key, a text);
+
+create table dim1 (id1 int primary key references t(id), val1 text);
+create table dim2 (id2 int primary key references t(id), val2 text);
+create table dim3 (id3 int primary key references t(id), val3 text);
+create table dim4 (id4 int primary key references t(id), val4 text);
+create table dim5 (id5 int primary key references t(id), val5 text);
+create table dim6 (id6 int primary key references t(id), val6 text);
+create table dim7 (id7 int primary key references t(id), val7 text);
+
+vacuum analyze;
diff --git a/patch/select-1.sql b/patch/select-1.sql
new file mode 100644
index 00000000000..1535ddcdc8f
--- /dev/null
+++ b/patch/select-1.sql
@@ -0,0 +1,9 @@
+--set join_collapse_limit = 1;
+select * from t
+ join dim1 on (dim1.id = id1)
+ join dim2 on (dim2.id = id2)
+ join dim3 on (dim3.id = id3)
+ join dim4 on (dim4.id = id4)
+ join dim5 on (dim5.id = id5)
+ join dim6 on (dim6.id = id6)
+ join dim7 on (dim7.id = id7);
diff --git a/patch/select-2.sql b/patch/select-2.sql
new file mode 100644
index 00000000000..4e1d2a7b0e7
--- /dev/null
+++ b/patch/select-2.sql
@@ -0,0 +1,9 @@
+-- set join_collapse_limit = 1;
+select * from t
+ left join dim1 on (id = id1)
+ left join dim2 on (id = id2)
+ left join dim3 on (id = id3)
+ left join dim4 on (id = id4)
+ left join dim5 on (id = id5)
+ left join dim6 on (id = id6)
+ left join dim7 on (id = id7);
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index e592e1ac3d1..66b1c8c540c 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -51,6 +51,7 @@ typedef struct
} SelfJoinCandidate;
bool enable_self_join_elimination;
+bool enable_starjoin_join_search;
/* local functions */
static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
@@ -2511,3 +2512,445 @@ remove_useless_self_joins(PlannerInfo *root, List *joinlist)
return joinlist;
}
+
+/*
+ * starjoin_match_to_foreign_key
+ * Try to match a join to a FK constraint.
+ *
+ * For a relation to be a dimension (for the starjoin heuristics), it needs
+ * to be joined through a FK constraint. The dimension is expected to be
+ * on the PK side of the join. The relation must not have any additional
+ * join clauses, beyond those matching the foreign key.
+ *
+ * We already have a list of relevant foreign keys, and we use that info
+ * for selectivity estimation in get_foreign_key_join_selectivity(). And
+ * we're actually doing something quite similar here.
+ *
+ * XXX Do we need to worry about the join type, e.g. inner/outer joins,
+ * semi/anti? get_foreign_key_join_selectivity() does care about it, and
+ * ignores some of those cases. Maybe we should too?
+ *
+ * XXX Check there are no other join clauses, beyond those matching the
+ * foreign key. But do we already have the joininfo at this point? Some
+ * of this stuff gets build only during the join order search later.
+ * The match_foreign_keys_to_quals() probably needs to be aware of all
+ * this, so how does it do that?
+ */
+static bool
+starjoin_match_to_foreign_key(PlannerInfo *root, RelOptInfo *rel)
+{
+ ListCell *lc;
+
+ /* Consider each FK constraint that is known to match the query */
+ foreach(lc, root->fkey_list)
+ {
+ ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+ int nmatches = 0;
+
+ /* rel is not the referenced table of the FK */
+ if (fkinfo->ref_relid != rel->relid)
+ continue;
+
+ /*
+ * Do we have a match for each key of the FK?
+ *
+ * XXX get_foreign_key_join_selectivity checks EquivalenceClasses,
+ * we should probably (definitely) do that here too.
+ *
+ * XXX We should check that all the clauses have the same relation
+ * on the other side (for multi-column keys). And that there are
+ * no other join clauses other than those matching the FK.
+ *
+ * XXX Do we need to check that the FK side of the join (i.e. the fact
+ * table) has the columns referenced as NOT NULL? Otherwise we could
+ * have a FK join that reduces the cardinality, which is one of
+ * the arguments why it's fine to move the join (that it doesn't
+ * change the cardinality). But if the join is LEFT JOIN, this
+ * should be fine too - but do we get here with LEFT JOINs?
+ *
+ * XXX Do we need to check if the other side of the FK is in the
+ * current join list? Maybe it's in some later one?
+ */
+ for (int i = 0; i < fkinfo->nkeys; i++)
+ {
+ bool has_matching_clause = false;
+
+ /*
+ * Is there a clause matching this FK key?
+ *
+ * XXX We need to make sure it's a valid match, e.g. that the
+ * same referencing table matches all keys in a composite FK,
+ * and so on.
+ *
+ * XXX Do we need to check some relationship to other rels in
+ * the same jointree item? E.g. the referencing table should
+ * not be a dimensions we already removed.
+ */
+ if ((fkinfo->rinfos[i] != NULL) || (fkinfo->eclass[i] != NULL))
+ {
+ has_matching_clause = true;
+ nmatches++;
+ continue;
+ }
+
+ /* found a FK key without a matching join clause, ignore the FK */
+ if (has_matching_clause)
+ break;
+ }
+
+ /* matched all FK keys */
+ if (nmatches == fkinfo->nkeys)
+ {
+ return true;
+ }
+ }
+
+ return false;
+}
+
+
+/*
+ * starjoin_is_dimension
+ * Determine if a range table entry is a dimension in a starjoin.
+ *
+ * To be considered a dimension for the simplified join order search, the
+ * join must not affect the cardinality of the join. We ensure that by
+ * requiring a couple things:
+ *
+ * 1) the join clause has to match a FK (that is, the fact does have at
+ * most one matching row in the dimension)
+ *
+ * 2) the FK side (the fact table) should be marked as NOT NULL, so that
+ * we know there's exactly one dimension row for each fact table row
+ *
+ * 3) there must be no additional restrictions on the relation (that
+ * might eliminate some of the rows, reducing the cardinality)
+ *
+ * XXX The Implementation is incomplete. It probably needs more thought,
+ * considering some join types would allow relaxing some of the checks
+ * (e.g. outer joins may not require checking (2) or possibly even (3),
+ * depending on where the condition is, what varnullingrels it has).
+ *
+ * XXX I wonder if we could handle (3) by ordering the dimensions by the
+ * selectivity of the restriction. There are no join clauses between the
+ * dimensions (ignoring the snowflake joins, but even there the clauses
+ * don't go between branches), so the selectivity could be treated as
+ * a measure of how much it shrinks the join result. So we could just
+ * sort the dimensions by this, starting with the lowest selectivity
+ * (close to 0.0), and ending with dimensions without restrictions (in
+ * which case the selectivity is 1.0).
+ *
+ * XXX If the join in INNER, and the fact side has NULL values in the
+ * join key, we might consider nullfrac as restriction.
+ *
+ * XXX I'm not sure how careful this needs to be about join order
+ * restrictions. Maybe it should call have_relevant_joinclause and
+ * have_join_order_restriction, to ensure the join order is OK?
+ *
+ * The optimizer/README is not very clear about this, but maybe it's
+ * a too specific question. It seems to say the relations in those
+ * lists can be joined in any order (lines 94 and 106). Maybe that's
+ * not what it means, or I'm misunderstanding it.
+ *
+ * It however seems has_join_restrictions() in join_search_one_level()
+ * forces the code to look only at "earlier" rels in the list
+ *
+ * first_rel = foreach_current_index(r) + 1
+ *
+ * So maybe we just need to stop once we find a rel with a restriction,
+ * as determined byhas_join_restrictions()?
+ *
+ * But there's also join_is_legal() to check legality of joins, with
+ * LEFT/RIGHT joins, and IN/EXISTS clauses. See README line 188. And it
+ * also looks-up the SpecialJoinInfo for the join. So maybe we should
+ * lookup RelOptInfo for both sides of the join, and call join_is_legal
+ * on that? Might be too expensive, though. Maybe do that only when
+ * has_join_restrictions already says yes?
+ *
+ * Maybe we should use has_join_restrictions(), but in a different way.
+ * We could still treat rels with restrictions as dimensions, and move
+ * that to the separate list (that doesn't change the join order), but
+ * stop once we hit the first non-dimension with a restriction? Because
+ * if any relation after that was a dimention, we wouldn't be able to
+ * move it to the separate list. It'd change the join order in a way
+ * that might violate the restriction. I believe that's the idea behind
+ * first_rel in join_search_one_level(), but maybe not.
+ *
+ * Perhaps have_join_order_restriction and have_relevant_joinclause are
+ * useful for this, rather than has_join_restrictions? We might look at
+ * actual pairs of relations, and/or check there's no join order
+ * restriction with respect to the relations we skipped/moved to the
+ * list of dimension?
+ *
+ * AFAICS it's just the skipping that can break the order restrictions?
+ * Adding something to the list of dimensions keeps the order (at least
+ * with respect to the rels after it).
+ */
+static bool
+starjoin_is_dimension(PlannerInfo *root, RangeTblRef *rtr)
+{
+ Index rti = rtr->rtindex;
+ RangeTblEntry *rte = root->simple_rte_array[rti];
+ RelOptInfo *rel = root->simple_rel_array[rti];
+
+ /* only plain relations can be dimensions (we need FK/PK join) */
+ if ((rte->rtekind != RTE_RELATION) ||
+ (rel->reloptkind != RELOPT_BASEREL))
+ return false;
+
+ /*
+ * Does it have any conditions/restrictions that may affect the number
+ * of rows matched? If yes, don't treat as dimension.
+ *
+ * Dimensions in a starjoin may have restrictions, but that means it'll
+ * change cardinality of the joins (reduce it), so it may be better to
+ * join it early. We leave it to the regular join order planning. The
+ * expectation is that most dimensions won't have extra restrictions.
+ *
+ * XXX Should we check some other fields, like lateral references, and
+ * so on? Or is that unnecessary? What about eclasses?
+ */
+ if (rel->baserestrictinfo != NIL)
+ return false;
+
+ /*
+ * See if the join clause matches a foreign key. It should match a
+ * single relation on the other side, and the dimension should be on
+ * the PK side.
+ *
+ * XXX loosely inspired by get_foreign_key_join_selectivity()
+ */
+ if (!starjoin_match_to_foreign_key(root, rel))
+ return false;
+
+ /*
+ * XXX Maybe some additional checks here ...
+ */
+
+ return true;
+}
+
+/*
+ * starjoin_adjust_joins
+ * Adjust the jointree for starjoins, to simplify the join order search.
+ *
+ * Try to simplify the join search problem for starjoin-like joins, with
+ * joins over FK relationships. The dimensions can be joined in almost
+ * any order, which is about the worst case for the standard join order
+ * search, and can be close to factorial complexity. But there's not much
+ * difference between such join orders, so we just leave the dimensions at
+ * the end of each group (as determined by the join_collapse_limit earlier).
+ *
+ * The join search for starjoin queries is surprisingly expensive, because
+ * there are very few join order restrictions. Consider a starjoin query
+ *
+ * SELECT * FROM f
+ * JOIN d1 ON (f.id1 = d1.id)
+ * JOIN d2 ON (f.id2 = d2.id)
+ * ...
+ * JOIN d9 ON (f.id9 = d9.id)
+ *
+ * There are no clauses between the dimension tables (d#), which means those
+ * tables can be joined in almost arbitrary order. This means the standard
+ * join_order_search() would explore a N! possible join orders. It is not
+ * that bad in practice, because we split the problem by from_collapse_limit
+ * into a sequence of smaller problems, but even for the default limit of
+ * 8 relations it's quite expensive. This can be easily demonstrated by
+ * setting from_collapse_limit=1 for example starjoin queries.
+ *
+ * The idea here is to apply a much simpler join order search for this type
+ * of queries, without too much risk of picking a much worse plans. It is
+ * however a trade off between how expensive we allow this to be, and how
+ * good the decisions will be. This can help only starjoins with multiple
+ * dimension tables, and we don't want to harm planning of other queries,
+ * so the basic "query shape" detection needs to be very cheap. And then
+ * it needs to be cheaper than the regular join order search.
+ *
+ * If a perfect check is impossible or too expensive, it's better to end
+ * up with a cheap false negative (i.e. and not use the optimization),
+ * rather than risk regressions in other cases.
+ *
+ * The simplified join order search relies on the fact that if the joins
+ * to dimensions do not alter the cardinality of the join relation, then
+ * the relative order of those joins does not matter. All the possible
+ * orders are guaranteed to perform the same. So we can simply pick one
+ * of those orders, and "hardcode" it in the join tree later passed to the
+ * join_order_search().
+ *
+ * The query may involve joins to additional (non-dimension) tables, and
+ * those may alter cardinality. Some joins may increase it, other joins
+ * may decrease it. In principle, it'd be best to first perform all the
+ * joins that reduce join size, then join all the dimensions, and finally
+ * perform joins that may increase the join size. But this is not done
+ * now, currently we simply apply all the dimensions at the end, hoping
+ * that the earlier joins did not inflate the join too much.
+ *
+ * The definition of a dimension is a bit vague. For our definition see
+ * the comment at starjoin_is_dimension().
+ *
+ * The optimization works by manipulating the joinlist (originally built
+ * by deconstruct_jointree), which decomposed the original jointree into
+ * smaller "problems" depending on join type and join_collapse_limit. We
+ * inspect those smaller lists, and selectively split them into smaller
+ * problems to force a join order. This may effectively undo some of the
+ * merging done by deconstruct_jointree(), which tries to build problems
+ * with up to join_collapse_limit relations.
+ *
+ * For example, imagine a join problem with 8 rels - one fact table and
+ * then 7 dimensions, which we can represent a joinlist with 8 elements.
+ *
+ * (D7, D6, D5, D4, D3, D2, D1, F)
+ *
+ * Assuming all those joins meet the requirements (have a matching FK,
+ * don't affect the join cardinality, ...), then we can split this into
+ *
+ * (D7, (D6, (D5, (D4, (D3, (D2, (D1, F)))))))
+ *
+ * which is a nested joinlist, with only two elements on each level. That
+ * means there's no need for expensive join order search, there's only
+ * one way to join the relations (two, if we consider the relations may
+ * switch sides).
+ *
+ * The joinlist may already be nested, with multiple smaller subproblems.
+ * We look at each individual join problem independently, i.e. we don't
+ * try to merge problems to build join_collapse_limit problems again.
+ * This is partially to keep it cheap/simple, but also so not change
+ * behavior for cases when people use join_collapse_limit to force some
+ * particular join shape.
+ *
+ * XXX A possible improvement is to allow handling snowflake joins, i.e.
+ * recursive dimensions. That would require a somewhat more complicated
+ * processing, because a dimension would be allowed other rels, as long
+ * as those are dimensions too. And we'd need to be more careful about
+ * the order in which join them to the top of the join.
+ *
+ * XXX One possible risk is that moving the dimension joins at the very
+ * end may move that after joins that increase the cardinality. Which
+ * may cause a regression. Such joins however don't seem very common, at
+ * least in regular starjoin queries. So maybe we could simply check if
+ * there are any such joins and disable this optimization. Is there a
+ * cheap way to identify that a join increases cardinality?
+ *
+ * XXX Ideally, we'd perform the dimension joins at the place with the
+ * lowest cardinality. Imagine a joinlist
+ *
+ * (D1, D2, A, B, F)
+ *
+ * Where A increases join cardinality, while B does not (possibly even
+ * reduces it). Ideally, we'd do the join like this
+ *
+ * (A, (D2, (D1, (B, F))))
+ *
+ * so D1/D2 get joined at the point of "lowest cardinality". We probably
+ * don't want to do all this cardinality estimation work here, it'd copy
+ * what we already do in the join_order_search(). Perhaps we could invent
+ * a "join item" representing a join to all those dimensions, and pass it
+ * to join_order_search()? And let it pick the right place for it? It'd
+ * always join them in the same order, it'd not reorder them. It would
+ * still do the regular cardinality estimations etc. It would be trivial
+ * to disable the optimization if needed - don't collapse the dimensions
+ * into the new type of join item.
+ */
+List *
+starjoin_adjust_joins(PlannerInfo *root, List *joinlist)
+{
+ ListCell *lc;
+ List *newlist = NIL;
+ List *dimensions = NIL;
+ int nlist = list_length(joinlist);
+
+ /* Do nothing if starjoin optimization not enabled. */
+ if (!enable_starjoin_join_search)
+ return joinlist;
+
+ /*
+ * Do nothing if starjoin optimization not applicable.
+ *
+ * XXX It might seems we can skip this for lists with <= 2 items, but
+ * that does not work, the elements may be nested list, and we need to
+ * descend into those. So do what remove_useless_self_joins() does, and
+ * only bail out for the simplest single-relation case (i.e. no joins).
+ */
+ if (joinlist == NIL ||
+ (nlist == 1 && !IsA(linitial(joinlist), List)))
+ return joinlist;
+
+ /*
+ * Process the current join problem - split the elements into dimensions
+ * and non-dimensions. If there are dimensions, add them back at the end,
+ * as small single-rel joins.
+ *
+ * The list may contain various types of elements. It may contain a list,
+ * which means it's an independent join search problem and we need to
+ * process it recursively. Or it may be RangeTblRef, in which case we
+ * need to check if it's a dimension. Other types of elements are just
+ * added back to the list as-is.
+ *
+ * XXX I think we need to be careful to keep the order of the list (for
+ * the non-dimension entries). The join_search_one_level() relies on
+ * that when handling join order restrictions.
+ *
+ * XXX It might be better to only create a new list if needed, i.e. once
+ * we find the first dimension. So that non-starjoin queries don't pay
+ * for something they don't need. A mutable iterator might be a way, but
+ * I'm not sure how expensive this really is.
+ */
+ foreach (lc, joinlist)
+ {
+ Node *item = (Node *) lfirst(lc);
+
+ /* a separate join search problem, handle it recursively */
+ if (IsA(item, List))
+ {
+ newlist = lappend(newlist,
+ starjoin_adjust_joins(root, (List *) item));
+ continue;
+ }
+
+ /*
+ * If it's not a List, it has to be a RangeTblRef - jinlists can't
+ * contain any other elements (see make_rel_from_joinlist).
+ */
+ Assert(IsA(item, RangeTblRef));
+
+ /*
+ * An entry representing a baserel. If it's a dimension, save it in
+ * a separate list, and we'll add it at the "top" of the join at the
+ * end. Otherwise add it to the list just like other elements.
+ *
+ * We do this only when the joinlist has at least 3 items. For fewer
+ * rels the optimization does not matter, there's only a single join
+ * order anyway. That only skips the optimization on this level - we
+ * still do the recursion, and that might hit a larger join problem.
+ *
+ * XXX We might have a new GUC to customize the cutoff limit, but for
+ * now it seems good enough to do it whenever applicable. If we find
+ * it's not worth it for less than N rels, we can add it later.
+ */
+ if ((nlist >= 3) &&
+ starjoin_is_dimension(root, (RangeTblRef *) item))
+ {
+ dimensions = lappend(dimensions, item);
+ continue;
+ }
+
+ /* not a dimension, add it to the list directly */
+ newlist = lappend(newlist, item);
+ }
+
+ /*
+ * If we found some dimensions, add them to the join tree one by one.
+ * The exact order does not matter, so we add them in the order we
+ * found them in the original list.
+ *
+ * We need to add them by creating smaller 2-element lists, with the rest
+ * of the list being a sub-problem and then adding the dimension
+ * table. This is how we force the desired join order.
+ */
+ foreach (lc, dimensions)
+ {
+ newlist = list_make2(newlist, lfirst(lc));
+ }
+
+ return newlist;
+}
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index eefc486a566..14abbbbd361 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -291,6 +291,13 @@ query_planner(PlannerInfo *root,
*/
distribute_row_identity_vars(root);
+ /*
+ * Try to simplify the join search problem for starjoin-like joins.
+ * This step relies on info about FK relationships, so we can't do it
+ * till after match_foreign_keys_to_quals().
+ */
+ joinlist = starjoin_adjust_joins(root, joinlist);
+
/*
* Ready to do the primary planning.
*/
diff --git a/src/backend/utils/misc/guc_parameters.dat b/src/backend/utils/misc/guc_parameters.dat
index 1128167c025..510241e75be 100644
--- a/src/backend/utils/misc/guc_parameters.dat
+++ b/src/backend/utils/misc/guc_parameters.dat
@@ -968,6 +968,13 @@
boot_val => 'true',
},
+{ name => 'enable_starjoin_join_search', type => 'bool', context => 'PGC_USERSET', group => 'QUERY_TUNING_METHOD',
+ short_desc => 'Enables simplified join order planning for starjoins.',
+ flags => 'GUC_EXPLAIN',
+ variable => 'enable_starjoin_join_search',
+ boot_val => 'false',
+},
+
{ name => 'enable_tidscan', type => 'bool', context => 'PGC_USERSET', group => 'QUERY_TUNING_METHOD',
short_desc => 'Enables the planner\'s use of TID scan plans.',
flags => 'GUC_EXPLAIN',
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index f62b61967ef..4e5542f690c 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -424,6 +424,7 @@
#enable_presorted_aggregate = on
#enable_seqscan = on
#enable_sort = on
+enable_starjoin_join_search = off
#enable_tidscan = on
#enable_group_by_reordering = on
#enable_distinct_reordering = on
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 00addf15992..c30ac3a5754 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -21,6 +21,7 @@
#define DEFAULT_CURSOR_TUPLE_FRACTION 0.1
extern PGDLLIMPORT double cursor_tuple_fraction;
extern PGDLLIMPORT bool enable_self_join_elimination;
+extern PGDLLIMPORT bool enable_starjoin_join_search;
/* query_planner callback to compute query_pathkeys */
typedef void (*query_pathkeys_callback) (PlannerInfo *root, void *extra);
@@ -120,6 +121,7 @@ extern bool innerrel_is_unique_ext(PlannerInfo *root, Relids joinrelids,
JoinType jointype, List *restrictlist,
bool force_cache, List **extra_clauses);
extern List *remove_useless_self_joins(PlannerInfo *root, List *joinlist);
+extern List *starjoin_adjust_joins(PlannerInfo *root, List *joinlist);
/*
* prototypes for plan/setrefs.c
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index 3b37fafa65b..0c3b1eeaba7 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -172,8 +172,9 @@ select name, setting from pg_settings where name like 'enable%';
enable_self_join_elimination | on
enable_seqscan | on
enable_sort | on
+ enable_starjoin_join_search | off
enable_tidscan | on
-(25 rows)
+(26 rows)
-- There are always wait event descriptions for various types. InjectionPoint
-- may be present or absent, depending on history since last postmaster start.
--
2.51.1
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-02-08 01:49 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-07-28 19:44 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-09-23 19:46 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-08 20:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
@ 2025-11-08 20:36 ` Tom Lane <[email protected]>
2025-11-09 18:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
0 siblings, 1 reply; 20+ messages in thread
From: Tom Lane @ 2025-11-08 20:36 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: James Hunter <[email protected]>; Richard Guo <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
[ Don't have time to read the v4 patch right now, but a couple
of quick responses: ]
Tomas Vondra <[email protected]> writes:
> On 9/23/25 21:46, Tom Lane wrote:
>> I'd be slightly inclined to put the GUC test there, too:
>>
>> + if (enable_starjoin_join_search)
>> + joinlist = starjoin_adjust_joins(root, joinlist);
> I'm not sure I like this very mcuh. No other call in query_planner()
> does it like that. Most don't have such GUC, but at least
> remove_useless_self_joins does, and it still doesn't check it here.
Fair enough, it was just a suggestion.
> When thinking about this, I realized the has_join_restriction() is only
> ever used in join_search_one_level(), i.e. when dealing with each small
> join order problem. Doesn't this mean the deconstructed jointree must
> already consider the restrictions in some way? I don't see any explicit
> mentions of such join order restrictions in deconstruct_recurse. It must
> not violate any ordering restrictions by splitting the joins in a
> "wrong" way, right? If I set join_collapse_limit=1 it still needs to
> satisfy all the rules.
Performing outer joins in syntactic order is always OK by definition,
and setting join_collapse_limit to 1 just forces that to happen.
So I guess you could say that the original jointree "considers the
restrictions", and it's only after we flatten an outer join's two
sides into a joinlist (along with other rels) that we have to worry.
Or is that not what you meant?
regards, tom lane
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-02-08 01:49 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-07-28 19:44 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-09-23 19:46 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-08 20:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-08 20:36 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
@ 2025-11-09 18:14 ` Tomas Vondra <[email protected]>
2025-11-09 18:42 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
0 siblings, 1 reply; 20+ messages in thread
From: Tomas Vondra @ 2025-11-09 18:14 UTC (permalink / raw)
To: Tom Lane <[email protected]>; +Cc: James Hunter <[email protected]>; Richard Guo <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
On 11/8/25 21:36, Tom Lane wrote:
> [ Don't have time to read the v4 patch right now, but a couple
> of quick responses: ]
>
> Tomas Vondra <[email protected]> writes:
>> On 9/23/25 21:46, Tom Lane wrote:
>>> I'd be slightly inclined to put the GUC test there, too:
>>>
>>> + if (enable_starjoin_join_search)
>>> + joinlist = starjoin_adjust_joins(root, joinlist);
>
>> I'm not sure I like this very mcuh. No other call in query_planner()
>> does it like that. Most don't have such GUC, but at least
>> remove_useless_self_joins does, and it still doesn't check it here.
>
> Fair enough, it was just a suggestion.
>
>> When thinking about this, I realized the has_join_restriction() is only
>> ever used in join_search_one_level(), i.e. when dealing with each small
>> join order problem. Doesn't this mean the deconstructed jointree must
>> already consider the restrictions in some way? I don't see any explicit
>> mentions of such join order restrictions in deconstruct_recurse. It must
>> not violate any ordering restrictions by splitting the joins in a
>> "wrong" way, right? If I set join_collapse_limit=1 it still needs to
>> satisfy all the rules.
>
> Performing outer joins in syntactic order is always OK by definition,
> and setting join_collapse_limit to 1 just forces that to happen.
> So I guess you could say that the original jointree "considers the
> restrictions", and it's only after we flatten an outer join's two
> sides into a joinlist (along with other rels) that we have to worry.
> Or is that not what you meant?
>
I'm not sure, but I wasn't talking just about outer joins.
AFAICS even queries with inner joins will get the jointree deconstructed
like this. Consider the query from select-1.sql:
select * from t
join dim1 on (dim1.id = id1)
join dim2 on (dim2.id = id2)
join dim3 on (dim3.id = id3)
join dim4 on (dim4.id = id4)
join dim5 on (dim5.id = id5)
join dim6 on (dim6.id = id6)
join dim7 on (dim7.id = id7);
If I set join_collapse_limit=1, then standard_join_search() only sees
problems of size 2, i.e. (list_length(initial_rels) == 2). And we only
look at has_join_restriction() *inside* these small problems, i.e. the
jointree must not be deconstructed in a way that would violate this.
Doesn't that mean deconstruct_jointree() has to somehow "consider" the
join restrictions (even if not explicitly). It that's the case, could we
maybe leverage that, eliminating the need to call has_join_restriction?
It's just a hunch, though. Maybe splitting the jointree like this is
always legal, because deconstruct_jointree() does not try to "reorder"
the elements.
regards
--
Tomas Vondra
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-02-08 01:49 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-07-28 19:44 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-09-23 19:46 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-08 20:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-08 20:36 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-09 18:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
@ 2025-11-09 18:42 ` Tom Lane <[email protected]>
2025-11-10 14:45 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
0 siblings, 1 reply; 20+ messages in thread
From: Tom Lane @ 2025-11-09 18:42 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: James Hunter <[email protected]>; Richard Guo <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
Tomas Vondra <[email protected]> writes:
> If I set join_collapse_limit=1, then standard_join_search() only sees
> problems of size 2, i.e. (list_length(initial_rels) == 2). And we only
> look at has_join_restriction() *inside* these small problems, i.e. the
> jointree must not be deconstructed in a way that would violate this.
> Doesn't that mean deconstruct_jointree() has to somehow "consider" the
> join restrictions (even if not explicitly).
It mustn't build subproblems that don't have any legal solutions, sure.
But that is automatic given that it only folds up within the syntactic
structure --- it doesn't go combining rels from random places within
the jointree.
> It that's the case, could we
> maybe leverage that, eliminating the need to call has_join_restriction?
Don't see how. Once we've folded an outer join into an upper
subproblem, some but (usually) not all of the join orders within that
subproblem will be legal.
It might be that we could make has_join_restriction and friends
faster/simpler with some other representation of the join tree.
I've not really thought hard about alternatives.
regards, tom lane
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-02-08 01:49 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-07-28 19:44 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-09-23 19:46 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-08 20:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-08 20:36 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-09 18:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-09 18:42 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
@ 2025-11-10 14:45 ` Tomas Vondra <[email protected]>
2025-11-12 15:39 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
0 siblings, 1 reply; 20+ messages in thread
From: Tomas Vondra @ 2025-11-10 14:45 UTC (permalink / raw)
To: Tom Lane <[email protected]>; +Cc: James Hunter <[email protected]>; Richard Guo <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
On 11/9/25 19:42, Tom Lane wrote:
> Tomas Vondra <[email protected]> writes:
>> If I set join_collapse_limit=1, then standard_join_search() only sees
>> problems of size 2, i.e. (list_length(initial_rels) == 2). And we only
>> look at has_join_restriction() *inside* these small problems, i.e. the
>> jointree must not be deconstructed in a way that would violate this.
>
>> Doesn't that mean deconstruct_jointree() has to somehow "consider" the
>> join restrictions (even if not explicitly).
>
> It mustn't build subproblems that don't have any legal solutions, sure.
> But that is automatic given that it only folds up within the syntactic
> structure --- it doesn't go combining rels from random places within
> the jointree.
>
Ah, I see. I didn't realize it's driven purely by the syntactic
structure, I got convinced it's aware of more stuff. But yeah, this
means it can't help the patch.
>> It that's the case, could we
>> maybe leverage that, eliminating the need to call has_join_restriction?
>
> Don't see how. Once we've folded an outer join into an upper
> subproblem, some but (usually) not all of the join orders within that
> subproblem will be legal.
>
> It might be that we could make has_join_restriction and friends
> faster/simpler with some other representation of the join tree.
> I've not really thought hard about alternatives.
>
No idea. I'm not familiar enough with this to have good ideas on how to
rework it, and I assume has_join_restriction will be cheap enough for
this patch.
regards
--
Tomas Vondra
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-02-08 01:49 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-07-28 19:44 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-09-23 19:46 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-08 20:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-08 20:36 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-09 18:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-09 18:42 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-10 14:45 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
@ 2025-11-12 15:39 ` Tomas Vondra <[email protected]>
2025-11-14 21:07 ` Re: should we have a fast-path planning for OLTP starjoins? Bruce Momjian <[email protected]>
0 siblings, 1 reply; 20+ messages in thread
From: Tomas Vondra @ 2025-11-12 15:39 UTC (permalink / raw)
To: Tom Lane <[email protected]>; +Cc: James Hunter <[email protected]>; Richard Guo <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
Hi,
Here's a v5, addressing some (but not all) of the things discussed
earlier in this thread.
This does nothing about the "opposite" type of join, with many small
tables linking to a single "central" table. I'm not convinced it makes
sense to handle that together with starjoins. But I haven't tried yet.
The main improvements/changes in v5 are:
1) comment cleanup / clarification
----------------------------------
A lot of comments was stale, or open questions answered since the
comment was written. So clean that up. Rewording and clarification of
various comments - a lot of places talking about the same thing, so I
de-duplicated that (I hope).
2) starjoin_match_to_foreign_key: improved matching FK to join clauses
----------------------------------------------------------------------
The check is split into starjoin_foreign_key_matched_by_clauses and
starjoin_clauses_matched_by_foreign_key, each doing the check in one
direction. It might be possible to do both in a single function, but I
don't think it'd be more efficient and this seemed simpler.
I was a bit surprised it doesn't need to inspect the EC members, it's
enough to check if the FK matches the EC. At least I don't think it's
needed, and it seems to be working without it. Maybe there's some more
complex case where we actually need to look at the members?
The one remaining XXX is about ensuring the referencing table has the FK
columns marked as NOT NULL, to guarantee the join does not reduce
cardinality. But it's related to the question of OUTER joins, which is
discussed later.
3) has_join_restriction(), but allowing some join order restrictions
--------------------------------------------------------------------
starjoin_is_dimension() now calls has_join_restriction(), and for inner
joins this works fine. But as soon as there's an outer join (say, left
join), it disabled the simplified planning. I find that unfortunate, but
I think we can actually do better - IIUC it's OK to treat a relation
with join restrictions as a dimension, as long as we don't reorder
relations with restrictions (the sublist).
Consider a join list with 8 baserels, and an empty list of dimensions.
[F, E1, D2, E3, D4, E5, D6, E7] []
The "F" is the fact, "D" are dimensions, "E" are non-dimension tables.
We can simply move the "D" rels to the dimension list:
[F, E1, E3, E5, E7] [D2, D4, D6]
The v4 patch would have stopped here, but I think we can do better - we
can move the "E" rels to the dimension list, as long as the only reason
preventing that was "has_join_restriction". We move the rels to the
beginning of the dimensions list, to keep the syntactic join order. And
we stop once we find the first rel that can't be moved (due to not
having a matching FK or has WHERE filter).
starjoin_adjust_joins does that by walking the filter repeatedly, and
stopping when it finds no dimension. I now realize it won't actually
need more than two loops (and one to find nothing) but that's a detail.
This is related to the NOT NULL vs. outer join check mentioned in (2),
because the restrictions are usually due to outer joins, and outer joins
don't need the check (and probably even can't have that). But I'm not
sure what's the best way to check if the order restriction is due to
some kind of outer join, or something else. Not sure.
I kept this separated in 0002, for easier review.
snowflake joins
---------------
There's another possible improvement that I'd like to address in the
next version of the patch - handling snowflake schemas. Right now the
leaf dimensions will be handled fine, but the "inner" dimensions won't
because they reference other tables (the leafs). Which gets rejected by
starjoin_clauses_matched_by_foreign_key, because those join clauses are
not matched by the incoming FK.
I plan to modify starjoin_is_dimension() to allow join clauses pointing
to "known" dimensions, so that the next loop can add the "inner" ones.
some experiments
----------------
To verify if this is effective, I ran the two starjoin and snowflake
selects (select-1 and select-3) with inner/outer joins, on master and
with 0001 and 0002. There's a "run.sh" script in "patch/" directory.
The results look like this:
| master | 0001/off 0001/on | 0002/off 0002/on
------------------|---------|-------------------|------------------
starjoin inner | 2299 | 2295 15325 | 2299 15131
starjoin outer | 2270 | 2272 2257 | 2249 14312
snowflake inner | 2718 | 2667 7223 | 2654 7106
snowflake outer | 2282 | 2264 2254 | 2273 6210
This is throughput (tps) from a single pgbench run with a single client.
It's quite stable, but there's a bit of noise.
The master and "off" results are virtually the same (and it gives you a
good idea of how much noise is there). 0001 helps with inner joins, but
not the outer joins (because of the restrictions). 0002 fixes that.
The improvement for snowflake joins is smaller because of the "inner"
dimensions. The current patches identify only the leaf ones.
regards
--
Tomas Vondra
Attachments:
[text/x-patch] v5-0002-Allow-dimensions-with-some-join-restrictions.patch (8.3K, ../../[email protected]/2-v5-0002-Allow-dimensions-with-some-join-restrictions.patch)
download | inline diff:
From 41273bc5db9785ba88038c15b762a1ffd367b762 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <[email protected]>
Date: Tue, 11 Nov 2025 23:12:39 +0100
Subject: [PATCH v5 2/2] Allow dimensions with some join restrictions
---
src/backend/optimizer/plan/analyzejoins.c | 154 +++++++++++++++++-----
1 file changed, 119 insertions(+), 35 deletions(-)
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index 79a7f0c8608..bc19c2b537c 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -2782,7 +2782,8 @@ starjoin_match_to_foreign_key(PlannerInfo *root, RelOptInfo *rel)
* with respect to the rels after it).
*/
static bool
-starjoin_is_dimension(PlannerInfo *root, RangeTblRef *rtr)
+starjoin_is_dimension(PlannerInfo *root, RangeTblRef *rtr,
+ bool allow_restrictions)
{
Index rti = rtr->rtindex;
RangeTblEntry *rte = root->simple_rte_array[rti];
@@ -2815,7 +2816,7 @@ starjoin_is_dimension(PlannerInfo *root, RangeTblRef *rtr)
* XXX This blocks the simplified planning for LEFT (or OUTER) joins,
* because outer joins imply restrictions.
*/
- if (has_join_restriction(root, rel))
+ if (!allow_restrictions && has_join_restriction(root, rel))
return false;
/*
@@ -2953,6 +2954,28 @@ starjoin_is_dimension(PlannerInfo *root, RangeTblRef *rtr)
* to disable the optimization if needed, I think - don't collapse the
* dimensions into the "group" join item. It would require changes to
* the generic join search, to be aware of the new item type.
+ *
+ * The search for dimensions may perform multiple passes over the list, to
+ * allow treating some rels with restrictions as dimensions. Relations
+ * without restrictions can be moved to an arbitrary place in the join
+ * tree. We leverage that by moving it to the list of dimensions, which
+ * may skip over various other relations.
+ *
+ * Relations with join order do not allow these arbitrary moves. But we can
+ * allow treating them dimensions in some cases. A join restriction does not
+ * imply we can't move the relation at all, otherwise we wouldn't be allowed
+ * to move any relations when there's a single relation with a restriction.
+ * It means we can't change the relative order of restricted relations.
+ *
+ * This means we can treat a relation with a restriction as a dimension,
+ * as long as it's the last in the current joinlist (after some relations
+ * were already moved to list of dimensions).
+ *
+ * To do this we walk the joinlist multiple times, and in each iteration
+ * we try to identify as many dimensions as possible. We walk the list in
+ * reverse, and we add dimensions to the beginning of the list. This way
+ * we preserve the original syntactic join order. If we find no dimensions
+ * in a loop, we're done.
*/
List *
starjoin_adjust_joins(PlannerInfo *root, List *joinlist)
@@ -2961,6 +2984,8 @@ starjoin_adjust_joins(PlannerInfo *root, List *joinlist)
List *newlist = NIL;
List *dimensions = NIL;
int nlist = list_length(joinlist);
+ int nitems;
+ Node **items;
/* Do nothing if starjoin optimization not enabled. */
if (!enable_starjoin_join_search)
@@ -2978,6 +3003,15 @@ starjoin_adjust_joins(PlannerInfo *root, List *joinlist)
(nlist == 1 && !IsA(linitial(joinlist), List)))
return joinlist;
+ /* expand the list into an array, to make backwards processing easier */
+ items = palloc_array(Node *, nlist);
+
+ nitems = 0;
+ foreach(lc, joinlist)
+ {
+ items[nitems++] = (Node *) lfirst(lc);
+ }
+
/*
* Process the current join problem - split the elements into dimensions
* and non-dimensions. If there are dimensions, add them back at the end,
@@ -2989,6 +3023,9 @@ starjoin_adjust_joins(PlannerInfo *root, List *joinlist)
* to check if it's a dimension. Other types of elements are just added
* back to the list as-is.
*
+ * Walk the list backwards, to preserve syntactic join order. This allows
+ * tracking "last" relation. If we find no dimension, we're done.
+ *
* XXX I think we need to be careful to keep the order of the list (for
* the non-dimension entries). The join_search_one_level() relies on that
* when handling join order restrictions.
@@ -2998,47 +3035,94 @@ starjoin_adjust_joins(PlannerInfo *root, List *joinlist)
* something they don't need. A mutable iterator might be a way, but I'm
* not sure how expensive this really is.
*/
- foreach(lc, joinlist)
+ for (;;)
{
- Node *item = (Node *) lfirst(lc);
+ bool found = false; /* found at least one dimension */
+ bool last = true; /* is this the current last rel */
- /* a separate join search problem, handle it recursively */
- if (IsA(item, List))
+ for (int i = (nitems - 1); i >= 0; i--)
{
- newlist = lappend(newlist,
- starjoin_adjust_joins(root, (List *) item));
- continue;
+ Node *item = items[i];
+
+ /* skip empty items (already moved to dimensions) */
+ if (item == NULL)
+ continue;
+
+ /* do nothing about join subproblems, leave them in place */
+ if (IsA(item, List))
+ {
+ /* XXX do we need to disable "false" for join subtree? */
+ last = false;
+ continue;
+ }
+
+ /*
+ * If it's not a List, it has to be a RangeTblRef - jinlists can't
+ * contain any other elements (see make_rel_from_joinlist).
+ */
+ Assert(IsA(item, RangeTblRef));
+
+ /*
+ * Is it a dimension?
+ *
+ * An entry representing a baserel. If it's a dimension, save it
+ * in a separate list, and we'll add it at the "top" of the join
+ * at the end. Otherwise add it to the list just like other
+ * elements.
+ *
+ * We do this only when the joinlist has at least 3 items. For
+ * fewer rels the optimization does not matter, there's only a
+ * single join order anyway. That only skips the optimization on
+ * this level - we still do the recursion, and that might hit a
+ * larger join problem.
+ *
+ * XXX If we decide to treat the rel as a dimension, don't update
+ * the "last" flag. The next relation will be the last one.
+ *
+ * XXX We might have a new GUC to customize the cutoff limit, but
+ * for now it seems good enough to do it whenever applicable. If
+ * we find it's not worth it for less than N rels, we can add it
+ * later.
+ */
+ if ((nlist >= 3) &&
+ starjoin_is_dimension(root, (RangeTblRef *) item, last))
+ {
+ /* add it to the beginning of the list */
+ dimensions = lcons(item, dimensions);
+ items[i] = NULL;
+ found = true;
+ continue;
+ }
+
+ /*
+ * Not a dimension. Leave it in the array, but remember the next
+ * item (backwards) is no longer the last one.
+ *
+ * XXX Maybe we don't need to reset "last" if the item does not
+ * have join restrictions?
+ */
+ last = false;
}
- /*
- * If it's not a List, it has to be a RangeTblRef - jinlists can't
- * contain any other elements (see make_rel_from_joinlist).
- */
- Assert(IsA(item, RangeTblRef));
+ /* terminate when a loop finds no dimension */
+ if (!found)
+ break;
+ }
- /*
- * An entry representing a baserel. If it's a dimension, save it in a
- * separate list, and we'll add it at the "top" of the join at the
- * end. Otherwise add it to the list just like other elements.
- *
- * We do this only when the joinlist has at least 3 items. For fewer
- * rels the optimization does not matter, there's only a single join
- * order anyway. That only skips the optimization on this level - we
- * still do the recursion, and that might hit a larger join problem.
- *
- * XXX We might have a new GUC to customize the cutoff limit, but for
- * now it seems good enough to do it whenever applicable. If we find
- * it's not worth it for less than N rels, we can add it later.
- */
- if ((nlist >= 3) &&
- starjoin_is_dimension(root, (RangeTblRef *) item))
- {
- dimensions = lappend(dimensions, item);
+ /*
+ * Add items remaining in the input array to the newlist. We need to do
+ * this every time, even without dimensions, because we need to recurse to
+ * the nested join problems.
+ */
+ for (int i = 0; i < nitems; i++)
+ {
+ if (items[i] == NULL)
continue;
- }
- /* not a dimension, add it to the list directly */
- newlist = lappend(newlist, item);
+ if (IsA(items[i], List))
+ items[i] = (Node *) starjoin_adjust_joins(root, (List *) items[i]);
+
+ newlist = lappend(newlist, items[i]);
}
/*
--
2.51.1
[text/x-patch] v5-0001-Simplify-planning-of-starjoin-queries.patch (34.7K, ../../[email protected]/3-v5-0001-Simplify-planning-of-starjoin-queries.patch)
download | inline diff:
From 162d2e9d876304e9cffa9a0fd73cfea33ca74819 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <[email protected]>
Date: Sat, 8 Nov 2025 18:16:30 +0100
Subject: [PATCH v5 1/2] Simplify planning of starjoin queries
---
patch/create-1.sql | 18 +
patch/create-2.sql | 11 +
patch/create-3.sql | 32 +
patch/run.sh | 23 +
patch/select-1-inner.sql | 10 +
patch/select-1-outer.sql | 10 +
patch/select-2.sql | 9 +
patch/select-3-inner.sql | 15 +
patch/select-3-outer.sql | 15 +
src/backend/optimizer/path/joinrels.c | 3 +-
src/backend/optimizer/plan/analyzejoins.c | 546 ++++++++++++++++++
src/backend/optimizer/plan/planmain.c | 7 +
src/backend/utils/misc/guc_parameters.dat | 7 +
src/backend/utils/misc/postgresql.conf.sample | 1 +
src/include/optimizer/paths.h | 1 +
src/include/optimizer/planmain.h | 2 +
src/test/regress/expected/sysviews.out | 3 +-
17 files changed, 710 insertions(+), 3 deletions(-)
create mode 100644 patch/create-1.sql
create mode 100644 patch/create-2.sql
create mode 100644 patch/create-3.sql
create mode 100644 patch/run.sh
create mode 100644 patch/select-1-inner.sql
create mode 100644 patch/select-1-outer.sql
create mode 100644 patch/select-2.sql
create mode 100644 patch/select-3-inner.sql
create mode 100644 patch/select-3-outer.sql
diff --git a/patch/create-1.sql b/patch/create-1.sql
new file mode 100644
index 00000000000..8df04fd0677
--- /dev/null
+++ b/patch/create-1.sql
@@ -0,0 +1,18 @@
+create table dim1 (id int primary key, val1 text);
+create table dim2 (id int primary key, val2 text);
+create table dim3 (id int primary key, val3 text);
+create table dim4 (id int primary key, val4 text);
+create table dim5 (id int primary key, val5 text);
+create table dim6 (id int primary key, val6 text);
+create table dim7 (id int primary key, val7 text);
+
+create table t (id serial primary key,
+ id1 int references dim1(id),
+ id2 int references dim2(id),
+ id3 int references dim3(id),
+ id4 int references dim4(id),
+ id5 int references dim5(id),
+ id6 int references dim6(id),
+ id7 int references dim7(id));
+
+vacuum analyze;
diff --git a/patch/create-2.sql b/patch/create-2.sql
new file mode 100644
index 00000000000..cdf612dde8f
--- /dev/null
+++ b/patch/create-2.sql
@@ -0,0 +1,11 @@
+create table t (id serial primary key, a text);
+
+create table dim1 (id1 int primary key references t(id), val1 text);
+create table dim2 (id2 int primary key references t(id), val2 text);
+create table dim3 (id3 int primary key references t(id), val3 text);
+create table dim4 (id4 int primary key references t(id), val4 text);
+create table dim5 (id5 int primary key references t(id), val5 text);
+create table dim6 (id6 int primary key references t(id), val6 text);
+create table dim7 (id7 int primary key references t(id), val7 text);
+
+vacuum analyze;
diff --git a/patch/create-3.sql b/patch/create-3.sql
new file mode 100644
index 00000000000..bd086c137ce
--- /dev/null
+++ b/patch/create-3.sql
@@ -0,0 +1,32 @@
+create table dim1_1 (id int primary key, val2 text);
+create table dim1_2 (id int primary key, val3 text);
+create table dim1 (id int primary key,
+ id1_1 int references dim1_1(id),
+ id1_2 int references dim1_2(id),
+ val1 text);
+create table dim2_1 (id int primary key, val5 text);
+create table dim2_2 (id int primary key, val6 text);
+create table dim2 (id int primary key,
+ id2_1 int references dim2_1(id),
+ id2_2 int references dim2_2(id),
+ val4 text);
+create table dim3_1 (id int primary key, val5 text);
+create table dim3_2 (id int primary key, val6 text);
+create table dim3 (id int primary key,
+ id3_1 int references dim3_1(id),
+ id3_2 int references dim3_2(id),
+ val4 text);
+create table dim4_1 (id int primary key, val5 text);
+create table dim4_2 (id int primary key, val6 text);
+create table dim4 (id int primary key,
+ id4_1 int references dim4_1(id),
+ id4_2 int references dim4_2(id),
+ val4 text);
+
+create table t (id serial primary key,
+ id1 int references dim1(id),
+ id2 int references dim2(id),
+ id3 int references dim3(id),
+ id4 int references dim4(id));
+
+vacuum analyze;
diff --git a/patch/run.sh b/patch/run.sh
new file mode 100644
index 00000000000..c67cd848a4a
--- /dev/null
+++ b/patch/run.sh
@@ -0,0 +1,23 @@
+#!/usr/bin/env bash
+
+for t in 1 3; do
+
+ dropdb --if-exists test
+ createdb test
+ psql test < create-$t.sql > /dev/null 2>&1
+
+ for m in inner outer; do
+
+ for o in off on; do
+
+ sed "s/OPT/$o/" select-$t$m.sql > script.sql
+
+ tps=$(pgbench -n -f script.sql -T 10 test | grep 'tps = ' | awk '{print $3}')
+
+ echo $t $m $o $tps
+
+ done
+
+ done
+
+done
diff --git a/patch/select-1-inner.sql b/patch/select-1-inner.sql
new file mode 100644
index 00000000000..d3bd477eea3
--- /dev/null
+++ b/patch/select-1-inner.sql
@@ -0,0 +1,10 @@
+--set join_collapse_limit = 1;
+set enable_starjoin_join_search = OPT;
+select * from t
+ join dim1 on (dim1.id = id1)
+ join dim2 on (dim2.id = id2)
+ join dim3 on (dim3.id = id3)
+ join dim4 on (dim4.id = id4)
+ join dim5 on (dim5.id = id5)
+ join dim6 on (dim6.id = id6)
+ join dim7 on (dim7.id = id7);
diff --git a/patch/select-1-outer.sql b/patch/select-1-outer.sql
new file mode 100644
index 00000000000..249cde4b768
--- /dev/null
+++ b/patch/select-1-outer.sql
@@ -0,0 +1,10 @@
+--set join_collapse_limit = 1;
+set enable_starjoin_join_search = OPT;
+select * from t
+ left join dim1 on (dim1.id = id1)
+ left join dim2 on (dim2.id = id2)
+ left join dim3 on (dim3.id = id3)
+ left join dim4 on (dim4.id = id4)
+ left join dim5 on (dim5.id = id5)
+ left join dim6 on (dim6.id = id6)
+ left join dim7 on (dim7.id = id7);
diff --git a/patch/select-2.sql b/patch/select-2.sql
new file mode 100644
index 00000000000..4e1d2a7b0e7
--- /dev/null
+++ b/patch/select-2.sql
@@ -0,0 +1,9 @@
+-- set join_collapse_limit = 1;
+select * from t
+ left join dim1 on (id = id1)
+ left join dim2 on (id = id2)
+ left join dim3 on (id = id3)
+ left join dim4 on (id = id4)
+ left join dim5 on (id = id5)
+ left join dim6 on (id = id6)
+ left join dim7 on (id = id7);
diff --git a/patch/select-3-inner.sql b/patch/select-3-inner.sql
new file mode 100644
index 00000000000..f661c0c2fb5
--- /dev/null
+++ b/patch/select-3-inner.sql
@@ -0,0 +1,15 @@
+--set join_collapse_limit = 1;
+set enable_starjoin_join_search = OPT;
+select * from t
+ join dim1 on (dim1.id = id1)
+ join dim2 on (dim2.id = id2)
+ join dim3 on (dim3.id = id3)
+ join dim4 on (dim4.id = id4)
+ join dim1_1 on (id1_1 = dim1_1.id)
+ join dim1_2 on (id1_2 = dim1_2.id)
+ join dim2_1 on (id2_1 = dim2_1.id)
+ join dim2_2 on (id2_2 = dim2_2.id)
+ join dim3_1 on (id3_1 = dim3_1.id)
+ join dim3_2 on (id3_2 = dim3_2.id)
+ join dim4_1 on (id4_1 = dim4_1.id)
+ join dim4_2 on (id4_2 = dim4_2.id);
diff --git a/patch/select-3-outer.sql b/patch/select-3-outer.sql
new file mode 100644
index 00000000000..5ca549f02ac
--- /dev/null
+++ b/patch/select-3-outer.sql
@@ -0,0 +1,15 @@
+--set join_collapse_limit = 1;
+set enable_starjoin_join_search = OPT;
+select * from t
+ left join dim1 on (dim1.id = id1)
+ left join dim2 on (dim2.id = id2)
+ left join dim3 on (dim3.id = id3)
+ left join dim4 on (dim4.id = id4)
+ left join dim1_1 on (id1_1 = dim1_1.id)
+ left join dim1_2 on (id1_2 = dim1_2.id)
+ left join dim2_1 on (id2_1 = dim2_1.id)
+ left join dim2_2 on (id2_2 = dim2_2.id)
+ left join dim3_1 on (id3_1 = dim3_1.id)
+ left join dim3_2 on (id3_2 = dim3_2.id)
+ left join dim4_1 on (id4_1 = dim4_1.id)
+ left join dim4_2 on (id4_2 = dim4_2.id);
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 5d1fc3899da..17332350da5 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -32,7 +32,6 @@ static void make_rels_by_clause_joins(PlannerInfo *root,
static void make_rels_by_clauseless_joins(PlannerInfo *root,
RelOptInfo *old_rel,
List *other_rels);
-static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel);
static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel);
static bool restriction_is_constant_false(List *restrictlist,
RelOptInfo *joinrel,
@@ -1363,7 +1362,7 @@ have_join_order_restriction(PlannerInfo *root,
* say "true" incorrectly. (Therefore, we don't bother with the relatively
* expensive has_legal_joinclause test.)
*/
-static bool
+bool
has_join_restriction(PlannerInfo *root, RelOptInfo *rel)
{
ListCell *l;
diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index e592e1ac3d1..79a7f0c8608 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -51,6 +51,7 @@ typedef struct
} SelfJoinCandidate;
bool enable_self_join_elimination;
+bool enable_starjoin_join_search;
/* local functions */
static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
@@ -2511,3 +2512,548 @@ remove_useless_self_joins(PlannerInfo *root, List *joinlist)
return joinlist;
}
+
+/*
+ * starjoin_foreign_key_matched_by_clauses
+ * Determines if the foreign key is matched by join clauses.
+ *
+ * Each foreign key attribute must be matched by a join clause. Either by
+ * a simple RestrictInfo, or by an equivalence class (if the relation has
+ * eclass joins).
+ *
+ * Returns true if the foreign key is matched, false otherwise.
+ *
+ * XXX Do we need to check that the FK side of the join (i.e. the fact table)
+ * has the columns referenced as NOT NULL? Otherwise we could have a FK join
+ * that reduces the cardinality, which is one of the arguments why it's fine
+ * to move the join (that it doesn't change the cardinality). But if the join
+ * is LEFT JOIN, this should be fine too - but do we get here with LEFT JOINs?
+ */
+static bool
+starjoin_foreign_key_matched_by_clauses(PlannerInfo *root, RelOptInfo *rel,
+ ForeignKeyOptInfo *fkinfo)
+{
+ /* make sure each FK attribute has at least one matching clause */
+ for (int i = 0; i < fkinfo->nkeys; i++)
+ {
+ /* matching rinfo clause or equivalance class */
+ if ((fkinfo->rinfos[i] != NULL) || (fkinfo->eclass[i] != NULL))
+ {
+ /*
+ * XXX Do we need to inspect the rinfo/eclass further? I don't
+ * think that's really necessary, we've already inspected it when
+ * building ForeignKeyOptInfo. So existence should be enough.
+ */
+ continue;
+ }
+
+ /* found an attribute without a join clause, ignore this FK */
+ return false;
+ }
+
+ /* all FK attributes had a matching join clause */
+ return true;
+}
+
+/*
+ * starjoin_clauses_matched_by_foreign_key
+ * Are all join clauses (rinfo or eclass) matched by the foreign key?
+ *
+ * Check if all join clauses for the current relation match the foreign key.
+ * Returns true if that's the case, false otherwise.
+ *
+ * XXX Could we do the check in both directions at once? Essentially, merge
+ * this with starjoin_foreign_key_matched_by_clauses, in a way that would
+ * make it cheaper than two separate functions? I don't think so.
+ */
+static bool
+starjoin_clauses_matched_by_foreign_key(PlannerInfo *root, RelOptInfo *rel,
+ ForeignKeyOptInfo *fkinfo)
+{
+ ListCell *lc;
+ int j;
+
+ /* Inspect all simple (RestrictInfo) clauses. */
+ foreach(lc, rel->joininfo)
+ {
+ RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+ bool matched = false; /* matched to the foreign key */
+
+ /* Is there a FK attribute referencing this rinfo? */
+ for (int i = 0; i < fkinfo->nkeys; i++)
+ {
+ if (list_member_ptr(fkinfo->rinfos[i], rinfo))
+ {
+ matched = true;
+ break;
+ }
+ }
+
+ /* found a clause not matched for FK */
+ if (!matched)
+ return false;
+ }
+
+ /* If the rel does not have eclass joins, we're done. */
+ if (!rel->has_eclass_joins)
+ return true;
+
+ /*
+ * There should be joins with clauses in equivalence classes. Walk all the
+ * eclasses, and try to match them to the foreign key.
+ */
+ j = -1;
+ while ((j = bms_next_member(rel->eclass_indexes, j)) >= 0)
+ {
+ EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, j);
+ bool matched = false; /* matched to the foreign key */
+
+ /*
+ * We're interested in joins, and const or single-member EC won't
+ * generate join clauses. So skip them now, before walking the FK.
+ * (The latter test covers the volatile case too.)
+ *
+ * XXX Taken from generate_implied_equalities_for_column().
+ */
+ if (ec->ec_has_const || list_length(ec->ec_members) <= 1)
+ continue;
+
+ /*
+ * A join EC needs to have multiple relids, so ignore cases with only
+ * a single relid.
+ *
+ * XXX Could there be 0 relids? I don't think so. Or do we need to
+ * check if (num != 2) instead?
+ *
+ * XXX If this simple check is not enough and we need to inspect ut we
+ * need to inspect the members, we should probably leave this after
+ * matching to FK attributes, if it doesn't match. The FK check is
+ * likely cheaper
+ */
+ if (bms_num_members(ec->ec_relids) == 1)
+ continue;
+
+ /* Is there a FK attribute referencing this EC? */
+ for (int i = 0; i < fkinfo->nkeys; i++)
+ {
+ if (fkinfo->eclass[i] == ec)
+ {
+ matched = true;
+ break;
+ }
+ }
+
+ /* found a join eclass not matched by the FK */
+ if (!matched)
+ return false;
+ }
+
+ /* all the join clauses seem to match (both rinfo and eclass) */
+ return true;
+}
+
+/*
+ * starjoin_match_to_foreign_key
+ * Determine if the relation is joined through a FK constraint.
+ *
+ * The relation needs to be joined through a FK constraint, with it being on
+ * the PK side of the join. The FK must be matched completely (no columns
+ * missing in join clauses), and there must be no other join clauses.
+ *
+ * We already have a list of relevant foreign keys, and we use that info
+ * for selectivity estimation in get_foreign_key_join_selectivity(). And
+ * we're actually doing something quite similar here.
+ *
+ * XXX Do we need to worry about the join type, e.g. inner/outer joins,
+ * semi/anti? get_foreign_key_join_selectivity() does care about it, and
+ * ignores some of those cases. Maybe we should too?
+ */
+static bool
+starjoin_match_to_foreign_key(PlannerInfo *root, RelOptInfo *rel)
+{
+ ListCell *lc;
+
+ /*
+ * Check if there's a FK matching the join clauses.
+ *
+ * The match needs to be perfect from both sides. All join clauses need to
+ * match the foreign key, and the whole foreign key needs to have a
+ * matching clause. There must not be any extra join clauses.
+ */
+ foreach(lc, root->fkey_list)
+ {
+ ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+
+ /*
+ * The foreign key is not relevant unless it references the rel on the
+ * PK side.
+ *
+ * XXX If we want to support the "inverse" join (with smaller tables
+ * referencing the main table) in the future, we'll probably need to
+ * allow con_relid too.
+ */
+ if (fkinfo->ref_relid != rel->relid)
+ continue;
+
+ /*
+ * First, check that each FK attribute has a matching join clause.
+ */
+ if (!starjoin_foreign_key_matched_by_clauses(root, rel, fkinfo))
+ continue;
+
+ /*
+ * Each FK attribute has a join clause matching it. What about the
+ * opposite direction? Do all join clauses match this FK? We need to
+ * check both joininfo and equivalence classes (if the rel has
+ * has_eclass_joins=true).
+ */
+ if (!starjoin_clauses_matched_by_foreign_key(root, rel, fkinfo))
+ continue;
+
+ /* matched in both directions */
+ return true;
+ }
+
+ return false;
+}
+
+/*
+ * starjoin_is_dimension
+ * Determine if a range table entry is a dimension in a starjoin.
+ *
+ * To be considered a dimension for the simplified join order search, the
+ * relation must be joined in a way that does not affect the cardinality
+ * of the join. And must be possible to postpone the join.
+ *
+ * We ensure that by checking a couple things:
+ *
+ * 1) The join clause(s) match a single FK. There has to be a single FK,
+ * with each key covered by a join clause. There must be no extra join
+ * clauses (which means the rel can be joined to a single other rel).
+ *
+ * 2) The FK side (in the fact table) should be marked as NOT NULL.
+ *
+ * 3) There must be no additional restrictions (WHERE conditions etc.).
+ *
+ * 4) The relation must not have a join order restriction, i.e. it has to
+ * be possible to "postpone" the join.
+ *
+ * These three rules guarantee the join does not alter the cardinality, as
+ * each row in the fact table has exactly one match in the dimension.
+ *
+ * XXX For inner joins this works fine. For outer we may need to be smarter
+ * as outer joins imply ordering restrictions, violating (4) and so don't
+ * allow the simplified planning. I believe it should be possible to still
+ * postpone the join, if we're dealing with the last relation in the list
+ * (because then we're not really changing the order). Or maybe it needs
+ * to check varnullingrels? In any case, we need to keep this cheap,
+ * cheaper than the "full" join planning.
+ *
+ * XXX Could we relax (3) in some way, to allow filters on dimensions? The
+ * joins are independent (there are no clauses between dimensions), so the
+ * per-dimension selectivity could measures how much it "shrinks" the join.
+ * We could order the dimensions so that the most selective (close to 0.0)
+ * are joined first, to reduce the join cardinality soon. This could be
+ * extended with the "cost" of evaluating the join clause, to make the cost
+ * model more correct.
+ *
+ * In snowflake joins this would be more complicated, because dimensions
+ * can join to other (child) dimensions, but even there the clauses don't
+ * go between branches. So even there it should be possible.
+ *
+ * XXX With LEFT joins we could even allow baserestrictinfo on the rel, as
+ * that won't affect the cardinality (if the filter happens before the
+ * join, of course). But such queries are likely rather rare, because why
+ * would you filter before LEFT join?
+ *
+ * XXX Right now this uses has_join_restriction(), but maybe that's a bit
+ * too heavy-handed and have_join_order_restriction would be better? But
+ * that might be too early? Also, have_join_order_restriction is already
+ * exposed in paths.h, not static. Could have_relevant_joinclause help?
+ *
+ * XXX There's also join_is_legal() to check legality of joins, with
+ * LEFT/RIGHT joins, and IN/EXISTS clauses (see "Join Tree Construction"
+ * in README, circa line 188). It also looks-up the SpecialJoinInfo for
+ * the join. But it's probably too early for join_is_legal(), we don't
+ * have RelOptInfos for joins yet, just base relations.
+ *
+ * XXX Is it just the "skipping" that can break the order restrictions?
+ * Adding something to the list of dimensions keeps the order (at least
+ * with respect to the rels after it).
+ */
+static bool
+starjoin_is_dimension(PlannerInfo *root, RangeTblRef *rtr)
+{
+ Index rti = rtr->rtindex;
+ RangeTblEntry *rte = root->simple_rte_array[rti];
+ RelOptInfo *rel = root->simple_rel_array[rti];
+
+ /* only plain relations can be dimensions (we need FK/PK join) */
+ if ((rte->rtekind != RTE_RELATION) ||
+ (rel->reloptkind != RELOPT_BASEREL))
+ return false;
+
+ /*
+ * Does it have any conditions/restrictions that may affect the number of
+ * rows matched? If yes, don't treat as dimension.
+ *
+ * Dimensions in a starjoin may have restrictions, but that means it'll
+ * change cardinality of the joins (reduce it), so it may be better to
+ * join it early. We leave it to the regular join order planning. The
+ * expectation is that most dimensions won't have extra restrictions.
+ *
+ * XXX Should we check some other fields, like lateral references, and so
+ * on? Or is that unnecessary? What about eclasses?
+ */
+ if (rel->baserestrictinfo != NIL)
+ return false;
+
+ /*
+ * Ignore relations with join restrictions. This requires the complete
+ * join order search, this cheap heuristics is not enough.
+ *
+ * XXX This blocks the simplified planning for LEFT (or OUTER) joins,
+ * because outer joins imply restrictions.
+ */
+ if (has_join_restriction(root, rel))
+ return false;
+
+ /*
+ * See if the join clause matches a foreign key. It should match a single
+ * relation on the other side, and the dimension should be on the PK side.
+ */
+ if (!starjoin_match_to_foreign_key(root, rel))
+ return false;
+
+ /*
+ * XXX Maybe some additional checks here ...
+ */
+
+ return true;
+}
+
+/*
+ * starjoin_adjust_joins
+ * Adjust the jointree for starjoins, to simplify the join order search.
+ *
+ * Try to simplify the join search problem for starjoin-like joins, with
+ * joins over FK relationships. The dimensions can be joined in almost any
+ * order, which is about the worst case for the standard join order search,
+ * and can be close to factorial complexity. But all the different orders
+ * are equivalent, so all this work is wasted. So the simplified planning
+ * identifies dimensions, and joins them all at the end of each group (as
+ * determined by the join_collapse_limit earlier).
+ *
+ * Note: The definition of a dimension is a bit vague. See the comment at
+ * starjoin_is_dimension() for our definition.
+ *
+ * The join search for starjoin queries is surprisingly expensive, because
+ * there are very few join order restrictions. Consider a starjoin query
+ *
+ * SELECT * FROM f
+ * JOIN d1 ON (f.id1 = d1.id)
+ * JOIN d2 ON (f.id2 = d2.id)
+ * ...
+ * JOIN d9 ON (f.id9 = d9.id)
+ *
+ * There are no clauses between the dimension tables (d#), which means those
+ * tables can be joined in almost arbitrary order. This means the standard
+ * join_order_search() would explore a N! possible join orders. It is not
+ * that bad in practice, as we split the problem by from_collapse_limit into
+ * a sequence of smaller problems, but even for the default of 8 relations
+ * it's quite expensive. This can be easily demonstrated by setting
+ * join_collapse_limit=1 for starjoin queries.
+ *
+ * We can significantly simplify the join order search for this type of
+ * queries, without too much risk of picking a much worse plans. It is
+ * however a trade off between how expensive we allow this to be, and how
+ * good the decisions will be. This can help only starjoins with multiple
+ * dimension tables, and we don't want to harm planning of other queries,
+ * so the basic "query shape" detection needs to be very cheap.
+ *
+ * If a perfect check is impossible or too expensive, it's better to end
+ * up with a cheap false negative (i.e. and not use the optimization),
+ * rather than risk regressions in other cases. Otherwise we might just
+ * as well use the regular join order search.
+ *
+ * The simplified join order search relies leverages the fact that joins
+ * of dimensions do not change the cardinality of the join, which means
+ * the relative order of those joins does not matter. All orders perform
+ * the same - we can pick an arbitrary of those orders, and "hardcode"
+ * it in the join tree before passing it to join_order_search().
+ *
+ * The join order is "hardcoded" by modifying the jointree, undoing some
+ * of the work performed by deconstruct_jointree earlier. That decomposed
+ * the original jointree into smaller "problems" depending on join type,
+ * join_collapse_limit and other details. We inspect those smaller lists,
+ * and selectively split them into smaller problems to force a join order.
+ * This may effectively undo some of the merging, which tries to construct
+ * problems with up to join_collapse_limit relations.
+ *
+ * For example, imagine a join problem with 8 rels - one fact table and
+ * then 7 dimensions, which we can represent a joinlist with 8 elements.
+ *
+ * (D7, D6, D5, D4, D3, D2, D1, F)
+ *
+ * Assuming all those joins meet the requirements (have a matching FK,
+ * don't affect the join cardinality, ...), then we can split this into
+ *
+ * (D7, (D6, (D5, (D4, (D3, (D2, (D1, F)))))))
+ *
+ * which is a nested joinlist, with only two elements on each level. That
+ * means there's no need for expensive join order search, there's only
+ * one way to join the relations (two, if we consider the relations may
+ * switch sides).
+ *
+ * The joinlist may already be nested, with multiple smaller join problems,
+ * similar to the example. Those are processed independently. We don't try
+ * to merge problems to build join_collapse_limit problems again. This is
+ * partially to keep it cheap/simple, but also so not change behavior for
+ * cases when people use join_collapse_limit to force a particular shape.
+ *
+ * Note: Ne never move relations between the "smaller problems", so this
+ * restricts what fraction of the join space we explore. So reducing the
+ * join_collapse_limit would improve the starjoin planning, but it may
+ * produce worse plans for other queries.
+ *
+ * The query may involve joins to additional (non-dimension) tables, and
+ * those may alter cardinality in either direction. In principle, it'd be
+ * best to first perform all the joins that reduce join size, then join all
+ * the dimensions, and finally perform joins that may increase the join
+ * size. Imagine a joinlist:
+ *
+ * (D1, D2, A, B, F)
+ *
+ * with fact F, dimensions D1 and D2, and non-dimensions A and B. If A
+ * increases cardinality, and B does not (or even reduces it), we could
+ * use this join tree:
+ *
+ * (A, (D2, (D1, (B, F))))
+ *
+ * For now we simply leave the dimension joins at the end, assuming
+ * that the earlier joins did not inflate the join too much.
+ *
+ * XXX Joins with cardinality increase don't seem very common, at least in
+ * regular starjoin queries. But maybe we could simply check if there are
+ * any such joins and disable this optimization? Is there a cheap way to
+ * identify when a join increases cardinality? I suppose we would need to
+ * calculate selectivity for join clauses? That might be too expensive,
+ * which goes against keeping this join search optimization very cheap.
+ *
+ * XXX A possible improvement would be to allow snowflake joins, i.e.
+ * queries with "recursive" dimensions. That would require a more complex
+ * logic, as a dimension would be allowed to join to other rels, as long
+ * as those are dimensions too. We'd need to be careful about preventing
+ * cycles, and about the order in which we join them.
+ *
+ * XXX Maybe we could invent a "join item" representing the dimensions,
+ * and pass it to join_order_search()? It'd expand the item into individual
+ * joins, and do the regular cardinality estimations etc. But it would
+ * only consider a single join order of the dimension. It would be trivial
+ * to disable the optimization if needed, I think - don't collapse the
+ * dimensions into the "group" join item. It would require changes to
+ * the generic join search, to be aware of the new item type.
+ */
+List *
+starjoin_adjust_joins(PlannerInfo *root, List *joinlist)
+{
+ ListCell *lc;
+ List *newlist = NIL;
+ List *dimensions = NIL;
+ int nlist = list_length(joinlist);
+
+ /* Do nothing if starjoin optimization not enabled. */
+ if (!enable_starjoin_join_search)
+ return joinlist;
+
+ /*
+ * Do nothing if starjoin optimization not applicable.
+ *
+ * XXX It might seems we can skip this for lists with <= 2 items, but that
+ * does not work, the elements may be nested list, and we need to descend
+ * into those. So do what remove_useless_self_joins() does, and only bail
+ * out for the simplest single-relation case (i.e. no joins).
+ */
+ if (joinlist == NIL ||
+ (nlist == 1 && !IsA(linitial(joinlist), List)))
+ return joinlist;
+
+ /*
+ * Process the current join problem - split the elements into dimensions
+ * and non-dimensions. If there are dimensions, add them back at the end,
+ * as small single-rel joins.
+ *
+ * The list may contain various types of elements. It may contain a list,
+ * which means it's an independent join search problem and we need to
+ * process it recursively. Or it may be RangeTblRef, in which case we need
+ * to check if it's a dimension. Other types of elements are just added
+ * back to the list as-is.
+ *
+ * XXX I think we need to be careful to keep the order of the list (for
+ * the non-dimension entries). The join_search_one_level() relies on that
+ * when handling join order restrictions.
+ *
+ * XXX It might be better to only create a new list if needed, i.e. once
+ * we find the first dimension. So that non-starjoin queries don't pay for
+ * something they don't need. A mutable iterator might be a way, but I'm
+ * not sure how expensive this really is.
+ */
+ foreach(lc, joinlist)
+ {
+ Node *item = (Node *) lfirst(lc);
+
+ /* a separate join search problem, handle it recursively */
+ if (IsA(item, List))
+ {
+ newlist = lappend(newlist,
+ starjoin_adjust_joins(root, (List *) item));
+ continue;
+ }
+
+ /*
+ * If it's not a List, it has to be a RangeTblRef - jinlists can't
+ * contain any other elements (see make_rel_from_joinlist).
+ */
+ Assert(IsA(item, RangeTblRef));
+
+ /*
+ * An entry representing a baserel. If it's a dimension, save it in a
+ * separate list, and we'll add it at the "top" of the join at the
+ * end. Otherwise add it to the list just like other elements.
+ *
+ * We do this only when the joinlist has at least 3 items. For fewer
+ * rels the optimization does not matter, there's only a single join
+ * order anyway. That only skips the optimization on this level - we
+ * still do the recursion, and that might hit a larger join problem.
+ *
+ * XXX We might have a new GUC to customize the cutoff limit, but for
+ * now it seems good enough to do it whenever applicable. If we find
+ * it's not worth it for less than N rels, we can add it later.
+ */
+ if ((nlist >= 3) &&
+ starjoin_is_dimension(root, (RangeTblRef *) item))
+ {
+ dimensions = lappend(dimensions, item);
+ continue;
+ }
+
+ /* not a dimension, add it to the list directly */
+ newlist = lappend(newlist, item);
+ }
+
+ /*
+ * If we found some dimensions, add them to the join tree one by one. The
+ * exact order does not matter, so we add them in the order we found them
+ * in the original list.
+ *
+ * We need to add them by creating smaller 2-element lists, with the rest
+ * of the list being a sub-problem and then adding the dimension table.
+ * This is how we force the desired join order.
+ */
+ foreach(lc, dimensions)
+ {
+ newlist = list_make2(newlist, lfirst(lc));
+ }
+
+ return newlist;
+}
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index eefc486a566..58278dbc94f 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -291,6 +291,13 @@ query_planner(PlannerInfo *root,
*/
distribute_row_identity_vars(root);
+ /*
+ * Try to simplify the join search problem for starjoin-like joins. This
+ * step relies on info about FK relationships, so we can't do it till
+ * after match_foreign_keys_to_quals().
+ */
+ joinlist = starjoin_adjust_joins(root, joinlist);
+
/*
* Ready to do the primary planning.
*/
diff --git a/src/backend/utils/misc/guc_parameters.dat b/src/backend/utils/misc/guc_parameters.dat
index 1128167c025..d5b976b2e39 100644
--- a/src/backend/utils/misc/guc_parameters.dat
+++ b/src/backend/utils/misc/guc_parameters.dat
@@ -968,6 +968,13 @@
boot_val => 'true',
},
+{ name => 'enable_starjoin_join_search', type => 'bool', context => 'PGC_USERSET', group => 'QUERY_TUNING_METHOD',
+ short_desc => 'Enables simplified join order planning for starjoins.',
+ flags => 'GUC_EXPLAIN',
+ variable => 'enable_starjoin_join_search',
+ boot_val => 'true',
+},
+
{ name => 'enable_tidscan', type => 'bool', context => 'PGC_USERSET', group => 'QUERY_TUNING_METHOD',
short_desc => 'Enables the planner\'s use of TID scan plans.',
flags => 'GUC_EXPLAIN',
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index f62b61967ef..458cd74c262 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -424,6 +424,7 @@
#enable_presorted_aggregate = on
#enable_seqscan = on
#enable_sort = on
+#enable_starjoin_join_search = on
#enable_tidscan = on
#enable_group_by_reordering = on
#enable_distinct_reordering = on
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index f6a62df0b43..8d3c44854cd 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -108,6 +108,7 @@ extern RelOptInfo *make_join_rel(PlannerInfo *root,
extern Relids add_outer_joins_to_relids(PlannerInfo *root, Relids input_relids,
SpecialJoinInfo *sjinfo,
List **pushed_down_joins);
+extern bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel);
extern bool have_join_order_restriction(PlannerInfo *root,
RelOptInfo *rel1, RelOptInfo *rel2);
extern void mark_dummy_rel(RelOptInfo *rel);
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 00addf15992..c30ac3a5754 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -21,6 +21,7 @@
#define DEFAULT_CURSOR_TUPLE_FRACTION 0.1
extern PGDLLIMPORT double cursor_tuple_fraction;
extern PGDLLIMPORT bool enable_self_join_elimination;
+extern PGDLLIMPORT bool enable_starjoin_join_search;
/* query_planner callback to compute query_pathkeys */
typedef void (*query_pathkeys_callback) (PlannerInfo *root, void *extra);
@@ -120,6 +121,7 @@ extern bool innerrel_is_unique_ext(PlannerInfo *root, Relids joinrelids,
JoinType jointype, List *restrictlist,
bool force_cache, List **extra_clauses);
extern List *remove_useless_self_joins(PlannerInfo *root, List *joinlist);
+extern List *starjoin_adjust_joins(PlannerInfo *root, List *joinlist);
/*
* prototypes for plan/setrefs.c
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index 3b37fafa65b..e9762da9937 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -172,8 +172,9 @@ select name, setting from pg_settings where name like 'enable%';
enable_self_join_elimination | on
enable_seqscan | on
enable_sort | on
+ enable_starjoin_join_search | on
enable_tidscan | on
-(25 rows)
+(26 rows)
-- There are always wait event descriptions for various types. InjectionPoint
-- may be present or absent, depending on history since last postmaster start.
--
2.51.1
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-02-08 01:49 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-07-28 19:44 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-09-23 19:46 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-08 20:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-08 20:36 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-09 18:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-09 18:42 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-10 14:45 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-12 15:39 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
@ 2025-11-14 21:07 ` Bruce Momjian <[email protected]>
2025-11-15 00:41 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
0 siblings, 1 reply; 20+ messages in thread
From: Bruce Momjian @ 2025-11-14 21:07 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: Tom Lane <[email protected]>; James Hunter <[email protected]>; Richard Guo <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
On Wed, Nov 12, 2025 at 04:39:50PM +0100, Tomas Vondra wrote:
> Hi,
>
> Here's a v5, addressing some (but not all) of the things discussed
> earlier in this thread.
>
> This does nothing about the "opposite" type of join, with many small
> tables linking to a single "central" table. I'm not convinced it makes
> sense to handle that together with starjoins. But I haven't tried yet.
I read this thread and the patch. I have a few questions which might
have already been answered but they used terminology I might not have
understood. I want to explain what I think is happening and perhaps
someone can tell me if these ideas are new or are already covered.
So, assume a fact table with a primary-key first column, and ten more
columns, each with its own dimension table.
So, a star join would query the fact table with some filter, and then
join each of the ten columns to its own dimension table, e.g.,
fact.col2 joins to dim2.primary_key
fact.col3 joins to dim3.primary_key
...
and the problem is that the dimension tables don't join to each other,
but only to the fact table, and our existing optimizer considers join
orders of:
F to D2
F to D3
...
and then
F to D3
F to D4
...
and there are 10! possible combinations, and Tomas is saying that the
dimension tables are almost all the same in their affect on the row
count, so why bother to consider all 10! join orders. Also, some joins
might increase the row count, so a foreign key guarantees only one row
will be matched in the dimension.
I found this code comment in the recent patch which is helpful:
+ * The query may involve joins to additional (non-dimension) tables, and
+ * those may alter cardinality in either direction. In principle, it'd be
+ * best to first perform all the joins that reduce join size, then join all
+ * the dimensions, and finally perform joins that may increase the join
+ * size. Imagine a joinlist:
+ *
+ * (D1, D2, A, B, F)
+ *
+ * with fact F, dimensions D1 and D2, and non-dimensions A and B. If A
+ * increases cardinality, and B does not (or even reduces it), we could
+ * use this join tree:
+ *
+ * (A, (D2, (D1, (B, F))))
+ *
+ * For now we simply leave the dimension joins at the end, assuming
+ * that the earlier joins did not inflate the join too much.
And then there is the problem of detecting when this happens.
I think my big question is, when we join A->B->C->D, we do a lot of work
in the optimizer to figure out what order to use, but when we do A->B,
A->C, A->D, why are we spending the same amount of optimizer effort?
Could we just order B, C, D in order of which have restrictions, or
based on size? I assume we can't because we don't know if A->C or
another join would increase the number of rows, and this patch is saying
if there is a foreign key relationship, they can't increase the rows so
just short-circuit and order them simply. Is that accurate?
Crazy question, if we have A->B, A->C, and A->D, why can't we just sort
B,C,D based in increasing order of adding rows to the result, and just
use that ordering, without requiring foreign keys?
I am very glad someone is working on this problem.
--
Bruce Momjian <[email protected]> https://momjian.us
EDB https://enterprisedb.com
Do not let urgent matters crowd out time for investment in the future.
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-02-08 01:49 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-07-28 19:44 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-09-23 19:46 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-08 20:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-08 20:36 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-09 18:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-09 18:42 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-10 14:45 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-12 15:39 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-14 21:07 ` Re: should we have a fast-path planning for OLTP starjoins? Bruce Momjian <[email protected]>
@ 2025-11-15 00:41 ` Tomas Vondra <[email protected]>
2025-11-15 02:52 ` Re: should we have a fast-path planning for OLTP starjoins? Bruce Momjian <[email protected]>
0 siblings, 1 reply; 20+ messages in thread
From: Tomas Vondra @ 2025-11-15 00:41 UTC (permalink / raw)
To: Bruce Momjian <[email protected]>; +Cc: Tom Lane <[email protected]>; James Hunter <[email protected]>; Richard Guo <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
On 11/14/25 22:07, Bruce Momjian wrote:
> On Wed, Nov 12, 2025 at 04:39:50PM +0100, Tomas Vondra wrote:
>> Hi,
>>
>> Here's a v5, addressing some (but not all) of the things discussed
>> earlier in this thread.
>>
>> This does nothing about the "opposite" type of join, with many small
>> tables linking to a single "central" table. I'm not convinced it makes
>> sense to handle that together with starjoins. But I haven't tried yet.
>
> I read this thread and the patch. I have a few questions which might
> have already been answered but they used terminology I might not have
> understood. I want to explain what I think is happening and perhaps
> someone can tell me if these ideas are new or are already covered.
>
> So, assume a fact table with a primary-key first column, and ten more
> columns, each with its own dimension table.
>
> So, a star join would query the fact table with some filter, and then
> join each of the ten columns to its own dimension table, e.g.,
>
> fact.col2 joins to dim2.primary_key
> fact.col3 joins to dim3.primary_key
> ...
>
> and the problem is that the dimension tables don't join to each other,
> but only to the fact table, and our existing optimizer considers join
> orders of:
>
> F to D2
> F to D3
> ...
>
> and then
>
> F to D3
> F to D4
> ...
>
> and there are 10! possible combinations, and Tomas is saying that the
> dimension tables are almost all the same in their affect on the row
> count, so why bother to consider all 10! join orders. Also, some joins
> might increase the row count, so a foreign key guarantees only one row
> will be matched in the dimension.
>
Right. A join between F and a "dimension" has the same cardinality as F,
i.e. each row in F has one matching row in the dimension. It's entirely
irrelevant in which order we actually join the dimensions.
And then there may be some other joins that affect the cardinality, and
the question is what to do about these ...
> I found this code comment in the recent patch which is helpful:
>
> + * The query may involve joins to additional (non-dimension) tables, and
> + * those may alter cardinality in either direction. In principle, it'd be
> + * best to first perform all the joins that reduce join size, then join all
> + * the dimensions, and finally perform joins that may increase the join
> + * size. Imagine a joinlist:
> + *
> + * (D1, D2, A, B, F)
> + *
> + * with fact F, dimensions D1 and D2, and non-dimensions A and B. If A
> + * increases cardinality, and B does not (or even reduces it), we could
> + * use this join tree:
> + *
> + * (A, (D2, (D1, (B, F))))
> + *
> + * For now we simply leave the dimension joins at the end, assuming
> + * that the earlier joins did not inflate the join too much.
>
> And then there is the problem of detecting when this happens.
>
> I think my big question is, when we join A->B->C->D, we do a lot of work
> in the optimizer to figure out what order to use, but when we do A->B,
> A->C, A->D, why are we spending the same amount of optimizer effort?
>
I'm sorry, I don't quite understand what's the question here. What does
A->B->C->D mean, exactly?
The standard join algorithm is (intentionally) generic, it handles all
kinds of joins, and it simply doesn't have any special cases for joins
with a particular structure (like a starjoin).
> Could we just order B, C, D in order of which have restrictions, or
> based on size? I assume we can't because we don't know if A->C or
> another join would increase the number of rows, and this patch is saying
> if there is a foreign key relationship, they can't increase the rows so
> just short-circuit and order them simply. Is that accurate?
>
> Crazy question, if we have A->B, A->C, and A->D, why can't we just sort
> B,C,D based in increasing order of adding rows to the result, and just
> use that ordering, without requiring foreign keys?
>
Yeah, that's mostly the idea one of the comments in the patch suggests.
To do the joins that reduce the cardinality first, then the dimensions,
and finally the joins that increase the cardinality.
However, the examples make it look like we're joining pairs of tables,
but that's not necessarily true. The join may be between F and relation
that is really a join itself. And now you need to know how this join
changes the cardinality, which is more expensive than when only looking
at joins of pairs of tables.
So I think we'd need to first identify these "independent join groups"
first. But that seems non-trivial, because we don't know which table to
start from (we don't know what's the "F" table).
I'm sure there's an algorithm to decompose the join tree like this, but
I'm not sure how expensive / invasive it'd be. The premise of this patch
is that it's a cheap optimization, that doesn't need to do this.
It simply "peels off" the dimensions from the join, based on things it
can prove locally, without having to decompose the whole jointree.
In any case, this is my current understanding of the problem. It's
entirely possible I'm missing some obvious solution, described in a
paper somewhere.
regards
--
Tomas Vondra
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-02-08 01:49 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-07-28 19:44 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-09-23 19:46 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-08 20:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-08 20:36 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-09 18:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-09 18:42 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-10 14:45 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-12 15:39 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-14 21:07 ` Re: should we have a fast-path planning for OLTP starjoins? Bruce Momjian <[email protected]>
2025-11-15 00:41 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
@ 2025-11-15 02:52 ` Bruce Momjian <[email protected]>
2025-11-18 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Bruce Momjian <[email protected]>
0 siblings, 1 reply; 20+ messages in thread
From: Bruce Momjian @ 2025-11-15 02:52 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: Tom Lane <[email protected]>; James Hunter <[email protected]>; Richard Guo <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
On Sat, Nov 15, 2025 at 01:41:04AM +0100, Tomas Vondra wrote:
> > And then there is the problem of detecting when this happens.
> >
> > I think my big question is, when we join A->B->C->D, we do a lot of work
> > in the optimizer to figure out what order to use, but when we do A->B,
> > A->C, A->D, why are we spending the same amount of optimizer effort?
> >
>
> I'm sorry, I don't quite understand what's the question here. What does
> A->B->C->D mean, exactly?
It means table A joins B, and B joins C, and C joins D. I can see that
as a much harder problem, and one we have code for in the optimizer,
than A joining to B, C, and D.
> > Could we just order B, C, D in order of which have restrictions, or
> > based on size? I assume we can't because we don't know if A->C or
> > another join would increase the number of rows, and this patch is saying
> > if there is a foreign key relationship, they can't increase the rows so
> > just short-circuit and order them simply. Is that accurate?
> >
> > Crazy question, if we have A->B, A->C, and A->D, why can't we just sort
> > B,C,D based in increasing order of adding rows to the result, and just
> > use that ordering, without requiring foreign keys?
> >
>
> Yeah, that's mostly the idea one of the comments in the patch suggests.
> To do the joins that reduce the cardinality first, then the dimensions,
> and finally the joins that increase the cardinality.
Yes, I saw that.
> However, the examples make it look like we're joining pairs of tables,
> but that's not necessarily true. The join may be between F and relation
> that is really a join itself. And now you need to know how this join
> changes the cardinality, which is more expensive than when only looking
> at joins of pairs of tables.
Yes, if the join is from F to D, and D joins to something else,
especially if it is not a foreign key where we know there is only one
match, I think we have to give up and go back to the normal optimizer
process.
> So I think we'd need to first identify these "independent join groups"
> first. But that seems non-trivial, because we don't know which table to
> start from (we don't know what's the "F" table).
Do we easily know how many relations each relation joins to? Does that
help us?
> I'm sure there's an algorithm to decompose the join tree like this, but
> I'm not sure how expensive / invasive it'd be. The premise of this patch
> is that it's a cheap optimization, that doesn't need to do this.
Yeah, I can see expense being an issue, which explains, as you said, why
many other databases have star join "flags", which ideally we can avoid
since very few people are going to use the flag.
> It simply "peels off" the dimensions from the join, based on things it
> can prove locally, without having to decompose the whole jointree.
I see, and I think understand better now. Thanks.
--
Bruce Momjian <[email protected]> https://momjian.us
EDB https://enterprisedb.com
Do not let urgent matters crowd out time for investment in the future.
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-02-08 01:49 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-07-28 19:44 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-09-23 19:46 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-08 20:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-08 20:36 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-09 18:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-09 18:42 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-10 14:45 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-12 15:39 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-14 21:07 ` Re: should we have a fast-path planning for OLTP starjoins? Bruce Momjian <[email protected]>
2025-11-15 00:41 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-15 02:52 ` Re: should we have a fast-path planning for OLTP starjoins? Bruce Momjian <[email protected]>
@ 2025-11-18 00:23 ` Bruce Momjian <[email protected]>
0 siblings, 0 replies; 20+ messages in thread
From: Bruce Momjian @ 2025-11-18 00:23 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: Tom Lane <[email protected]>; James Hunter <[email protected]>; Richard Guo <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
On Fri, Nov 14, 2025 at 09:52:41PM -0500, Bruce Momjian wrote:
> On Sat, Nov 15, 2025 at 01:41:04AM +0100, Tomas Vondra wrote:
> > > And then there is the problem of detecting when this happens.
> > >
> > > I think my big question is, when we join A->B->C->D, we do a lot of work
> > > in the optimizer to figure out what order to use, but when we do A->B,
> > > A->C, A->D, why are we spending the same amount of optimizer effort?
> > >
> >
> > I'm sorry, I don't quite understand what's the question here. What does
> > A->B->C->D mean, exactly?
>
> It means table A joins B, and B joins C, and C joins D. I can see that
> as a much harder problem, and one we have code for in the optimizer,
> than A joining to B, C, and D.
I guess fundamentally it is the case of splitting a big problem into
smaller ones, e.g., 2 + 3 + 3 = 8, but 2! * 3! * 3! = 72 and 8! = 40320.
--
Bruce Momjian <[email protected]> https://momjian.us
EDB https://enterprisedb.com
Do not let urgent matters crowd out time for investment in the future.
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
@ 2025-02-10 21:36 ` Robert Haas <[email protected]>
2025-02-11 15:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
1 sibling, 1 reply; 20+ messages in thread
From: Robert Haas @ 2025-02-10 21:36 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: James Hunter <[email protected]>; Richard Guo <[email protected]>; Tom Lane <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
On Fri, Feb 7, 2025 at 3:09 PM Tomas Vondra <[email protected]> wrote:
> I don't think that's quite true. The order of dimension joins does not
> matter because the joins do not affect the join size at all. The size of
> |F| has nothing to do with that, I think. We'll do the same number of
> lookups against the dimensions no matter in what order we join them. And
> we know it's best to join them as late as possible, after all the joins
> that reduce the size (and before joins that "add" rows, I think).
This is often not quite true, because there are often restriction
clauses on the fact tables that result in some rows being eliminated.
e.g. SELECT * FROM hackers h JOIN languages l ON h.language_id = l.id
JOIN countries c ON h.country_id = c.id WHERE c.name = 'Czechia';
However, I think that trying to somehow leverage the existence of
either FK or LJ+UNIQUE is still a pretty good idea. In a lot of cases,
many of the joins don't change the row count, so we don't really need
to explore all possible orderings of those joins. We might be able to
define some concept of "join that does't change the row count at all"
or maybe better "join that doesn't change the row count very much".
And then if we have a lot of such joins, we can consider them as a
group. Say we have 2 joins that do change the row count significantly,
and then 10 more than don't. The 10 that don't can be done before,
between, or after the two that do, but it doesn't seem necessary to
consider doing some of them at one point and some at another.
Maybe that's not the right way to think about this problem; I haven't
read the academic literature on star-join optimization. But it has
always felt stupid to me that we spend a bunch of time considering
join orders that are not meaningfully different, and I think what
makes two join orders not meaningfully different is that we're
commuting joins that are not changing the row count.
(Also worth noting: even joins of this general form change the row
count, they can only reduce it.)
--
Robert Haas
EDB: http://www.enterprisedb.com
^ permalink raw reply [nested|flat] 20+ messages in thread
* Re: should we have a fast-path planning for OLTP starjoins?
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-10 21:36 ` Re: should we have a fast-path planning for OLTP starjoins? Robert Haas <[email protected]>
@ 2025-02-11 15:14 ` Tomas Vondra <[email protected]>
0 siblings, 0 replies; 20+ messages in thread
From: Tomas Vondra @ 2025-02-11 15:14 UTC (permalink / raw)
To: Robert Haas <[email protected]>; +Cc: James Hunter <[email protected]>; Richard Guo <[email protected]>; Tom Lane <[email protected]>; Jeff Davis <[email protected]>; pgsql-hackers
On 2/10/25 22:36, Robert Haas wrote:
> On Fri, Feb 7, 2025 at 3:09 PM Tomas Vondra <[email protected]> wrote:
>> I don't think that's quite true. The order of dimension joins does not
>> matter because the joins do not affect the join size at all. The size of
>> |F| has nothing to do with that, I think. We'll do the same number of
>> lookups against the dimensions no matter in what order we join them. And
>> we know it's best to join them as late as possible, after all the joins
>> that reduce the size (and before joins that "add" rows, I think).
>
> This is often not quite true, because there are often restriction
> clauses on the fact tables that result in some rows being eliminated.
>
> e.g. SELECT * FROM hackers h JOIN languages l ON h.language_id = l.id
> JOIN countries c ON h.country_id = c.id WHERE c.name = 'Czechia';
>
True. I think this was discussed earlier in this thread - dimensions
with additional restrictions may affect the row count, and thus would be
exempt from this (and would instead go through the "regular" join order
search algorithm). So I assumed the "dimensions" don't have any such
restrictions in my message, I should have mentioned that.
> However, I think that trying to somehow leverage the existence of
> either FK or LJ+UNIQUE is still a pretty good idea. In a lot of cases,
> many of the joins don't change the row count, so we don't really need
> to explore all possible orderings of those joins. We might be able to
> define some concept of "join that does't change the row count at all"
> or maybe better "join that doesn't change the row count very much".
> And then if we have a lot of such joins, we can consider them as a
> group. Say we have 2 joins that do change the row count significantly,
> and then 10 more than don't. The 10 that don't can be done before,
> between, or after the two that do, but it doesn't seem necessary to
> consider doing some of them at one point and some at another.
>
> Maybe that's not the right way to think about this problem; I haven't
> read the academic literature on star-join optimization. But it has
> always felt stupid to me that we spend a bunch of time considering
> join orders that are not meaningfully different, and I think what
> makes two join orders not meaningfully different is that we're
> commuting joins that are not changing the row count.
>
> (Also worth noting: even joins of this general form change the row
> count, they can only reduce it.)
>
I searched for papers on star-joins, but pretty much everything I found
focuses on the OLAP case. Which is interesting, I think the OLTP
star-join I described seems quite different, and I'm not sure the trade
offs are necessarily the same.
My gut feeling is that in the first "phase" we should focus on the case
with no restrictions - that makes it obvious what the optimal order is,
and it will help a significant fraction of cases.
And then in the next step we can try doing something for cases with
restrictions - be it some sort of greedy algorithm, something that
leverages knowledge of the selectivity to prune join orders early
(instead of actually exploring all N! join orders like today). Or
something else, not sure.
regards
--
Tomas Vondra
^ permalink raw reply [nested|flat] 20+ messages in thread
end of thread, other threads:[~2025-11-18 00:23 UTC | newest]
Thread overview: 20+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2024-03-08 21:45 [PATCH v4 09/19] Execute freezing in heap_page_prune() Melanie Plageman <[email protected]>
2025-02-07 20:09 Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-07 22:43 ` Re: should we have a fast-path planning for OLTP starjoins? James Hunter <[email protected]>
2025-02-07 23:29 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-02-08 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-02-08 01:49 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-07-28 19:44 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-09-23 19:46 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-08 20:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-08 20:36 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-09 18:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-09 18:42 ` Re: should we have a fast-path planning for OLTP starjoins? Tom Lane <[email protected]>
2025-11-10 14:45 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-12 15:39 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-14 21:07 ` Re: should we have a fast-path planning for OLTP starjoins? Bruce Momjian <[email protected]>
2025-11-15 00:41 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
2025-11-15 02:52 ` Re: should we have a fast-path planning for OLTP starjoins? Bruce Momjian <[email protected]>
2025-11-18 00:23 ` Re: should we have a fast-path planning for OLTP starjoins? Bruce Momjian <[email protected]>
2025-02-10 21:36 ` Re: should we have a fast-path planning for OLTP starjoins? Robert Haas <[email protected]>
2025-02-11 15:14 ` Re: should we have a fast-path planning for OLTP starjoins? Tomas Vondra <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox