Add a greedy join search algorithm to handle large join problems
Hi hackers,
This patch implements GOO (Greedy Operator Ordering), a greedy
join-order search method for large join problems, based on Fegaras (DEXA
’98) [1]Leonidas Fegaras, “A New Heuristic for Optimizing Large Queries”, DEXA ’98. ACM Digital Library: https://dl.acm.org/doi/10.5555/648311.754892 A publicly accessible PostScript version is available from the author's page: https://lambda.uta.edu/order.ps. The algorithm repeatedly selects, among all legal joins, the
join pair with the lowest estimated total cost, merges them, and
continues until a single join remains. Patch attached.
To get an initial sense of performance, I reused the star join /
snowflake examples and the testing script from the thread in [2]Star/snowflake join thread and benchmarks: /messages/by-id/a22ec6e0-92ae-43e7-85c1-587df2a65f51@vondra.me. The
star-join GUC in that SQL workload was replaced with
`enable_goo_join_search`, so the same tests can run under DP (standard
dynamic programming) / GEQO(Genetic Query Optimizer) / GOO. For these
tests, geqo_threshold was set to 15 for DP, and to 5 for both GEQO and
GOO. Other planner settings, including join_collapse_limit, remained at
their defaults.
On my local machine, a single-client pgbench run produces the following
throughput (tps):
| DP | GEQO | GOO
--------------------+----------+----------+-----------
starjoin (inner) | 1762.52 | 192.13 | 6168.89
starjoin (outer) | 1683.92 | 173.90 | 5626.56
snowflake (inner) | 1829.04 | 133.40 | 3929.57
snowflake (outer) | 1397.93 | 99.65 | 3040.52
Open questions:
* The paper ranks joins by estimated result size, while this prototype
reuses the existing planner total_cost. This makes the implementation
straightforward, but it may be worth exploring row-based rule.
* The prototype allocates through multiple memory contexts, aiming to
reduce memory usage during candidate evaluation. Suggestions on
simplification are welcome.
* Planning performance vs GEQO: On the star/snowflake benchmarks above,
GOO reduces planning time significantly compared to GEQO. Broader
evaluation on more representative workloads (e.g., TPC-H / TPC-DS /
JOB) is TODO, covering both planning speed and plan quality.
* There is no tuning knob like `geqo_seed` for GEQO if GOO produces a
poor ordering.
* The long-term integration is open:
* fully replace GEQO,
* keep GEQO available and optionally try both,
* or use GOO as a starting point for GEQO.
Comments and review would be appreciated.
References:
[1]: Leonidas Fegaras, “A New Heuristic for Optimizing Large Queries”, DEXA ’98. ACM Digital Library: https://dl.acm.org/doi/10.5555/648311.754892 A publicly accessible PostScript version is available from the author's page: https://lambda.uta.edu/order.ps
DEXA ’98. ACM Digital Library:
https://dl.acm.org/doi/10.5555/648311.754892 A publicly accessible
PostScript version is available from the author's page:
https://lambda.uta.edu/order.ps
[2]: Star/snowflake join thread and benchmarks: /messages/by-id/a22ec6e0-92ae-43e7-85c1-587df2a65f51@vondra.me
/messages/by-id/a22ec6e0-92ae-43e7-85c1-587df2a65f51@vondra.me
--
Best regards,
Chengpeng Yan
Attachments:
v1-0001-Add-GOO-Greedy-Operator-Ordering-join-search-as-a.patchapplication/octet-stream; name=v1-0001-Add-GOO-Greedy-Operator-Ordering-join-search-as-a.patchDownload
From cf539f322c91bbea79f444c746303bf49d6b4d70 Mon Sep 17 00:00:00 2001
From: Chengpeng Yan <chengpeng_yan@outlook.com>
Date: Sun, 30 Nov 2025 14:05:10 +0800
Subject: [PATCH v1] Add GOO (Greedy Operator Ordering) join search as an
alternative to GEQO
Introduce a greedy join search algorithm (GOO) to handle
large join problems. GOO builds join relations iteratively, maintaining
a list of clumps (join components) and committing to the cheapest
legal join at each step until only one clump remains.
Signed-off-by: Chengpeng Yan <chengpeng_yan@outlook.com>
---
src/backend/optimizer/path/Makefile | 1 +
src/backend/optimizer/path/allpaths.c | 4 +
src/backend/optimizer/path/goo.c | 601 +++++++++++++++++
src/backend/optimizer/path/meson.build | 1 +
src/backend/utils/misc/guc_parameters.dat | 9 +
src/backend/utils/misc/postgresql.conf.sample | 1 +
src/include/optimizer/goo.h | 23 +
src/include/optimizer/paths.h | 1 +
src/test/regress/expected/goo.out | 634 ++++++++++++++++++
src/test/regress/expected/sysviews.out | 3 +-
src/test/regress/parallel_schedule | 9 +-
src/test/regress/sql/goo.sql | 329 +++++++++
12 files changed, 1612 insertions(+), 4 deletions(-)
create mode 100644 src/backend/optimizer/path/goo.c
create mode 100644 src/include/optimizer/goo.h
create mode 100644 src/test/regress/expected/goo.out
create mode 100644 src/test/regress/sql/goo.sql
diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile
index 1e199ff66f7..3bc825cd845 100644
--- a/src/backend/optimizer/path/Makefile
+++ b/src/backend/optimizer/path/Makefile
@@ -17,6 +17,7 @@ OBJS = \
clausesel.o \
costsize.o \
equivclass.o \
+ goo.o \
indxpath.o \
joinpath.o \
joinrels.o \
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 4c43fd0b19b..4574b1f44cc 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -35,6 +35,7 @@
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/geqo.h"
+#include "optimizer/goo.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
@@ -3845,6 +3846,9 @@ make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
if (join_search_hook)
return (*join_search_hook) (root, levels_needed, initial_rels);
+ /* WIP: for now use geqo_threshold for testing */
+ else if (enable_goo_join_search && levels_needed >= geqo_threshold)
+ return goo_join_search(root, levels_needed, initial_rels);
else if (enable_geqo && levels_needed >= geqo_threshold)
return geqo(root, levels_needed, initial_rels);
else
diff --git a/src/backend/optimizer/path/goo.c b/src/backend/optimizer/path/goo.c
new file mode 100644
index 00000000000..c6dc69e8432
--- /dev/null
+++ b/src/backend/optimizer/path/goo.c
@@ -0,0 +1,601 @@
+/*-------------------------------------------------------------------------
+ *
+ * goo.c
+ * Greedy operator ordering (GOO) join search for large join problems
+ *
+ * GOO is a deterministic greedy operator ordering algorithm that constructs
+ * join relations iteratively, always committing to the cheapest legal join at
+ * each step. The algorithm maintains a list of "clumps" (join components),
+ * initially one per base relation. At each iteration, it evaluates all legal
+ * pairs of clumps, selects the pair that produces the cheapest join according
+ * to the planner's cost model, and replaces those two clumps with the
+ * resulting joinrel. This continues until only one clump remains.
+ *
+ * ALGORITHM COMPLEXITY:
+ *
+ * Time Complexity: O(n^3) where n is the number of base relations.
+ * - The algorithm performs (n - 1) iterations, merging two clumps each time.
+ * - At iteration i, there are (n - i + 1) remaining clumps, requiring
+ * O((n-i)^2) pair evaluations to find the cheapest join.
+ * - Total: Sum of (n-i)^2 for i=1 to n-1 ≈ O(n^3)
+ *
+ * REFERENCES:
+ *
+ * This implementation is based on the algorithm described in:
+ *
+ * Leonidas Fegaras, "A New Heuristic for Optimizing Large Queries",
+ * Proceedings of the 9th International Conference on Database and Expert
+ * Systems Applications (DEXA '98), August 1998, Pages 726-735.
+ * https://dl.acm.org/doi/10.5555/648311.754892
+ *
+ *
+ * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * IDENTIFICATION
+ * src/backend/optimizer/path/goo.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include "miscadmin.h"
+#include "nodes/bitmapset.h"
+#include "nodes/pathnodes.h"
+#include "optimizer/geqo.h"
+#include "optimizer/goo.h"
+#include "optimizer/joininfo.h"
+#include "optimizer/pathnode.h"
+#include "optimizer/paths.h"
+#include "utils/hsearch.h"
+#include "utils/memutils.h"
+
+/*
+ * Configuration defaults. These are exposed as GUCs in guc_tables.c.
+ */
+bool enable_goo_join_search = false;
+
+/*
+ * Working state for a single GOO search invocation.
+ *
+ * This structure holds all the state needed during a greedy join order search.
+ * It manages three memory contexts with different lifetimes to avoid memory
+ * bloat during large join searches.
+ *
+ * TODO: Consider using the extension_state mechanism in PlannerInfo (similar
+ * to GEQO's approach) instead of passing GooState separately.
+ */
+typedef struct GooState
+{
+ PlannerInfo *root; /* global planner state */
+ MemoryContext goo_cxt; /* long-lived (per-search) allocations */
+ MemoryContext cand_cxt; /* per-iteration candidate storage */
+ MemoryContext scratch_cxt; /* per-candidate speculative evaluation */
+ List *clumps; /* remaining join components (RelOptInfo *) */
+
+ /*
+ * "clumps" are similar to GEQO's concept (see geqo_eval.c): join
+ * components that haven't been merged yet. Initially one per base
+ * relation, gradually merged until one remains.
+ */
+ bool clause_pair_present; /* any clause-connected pair exists? */
+} GooState;
+
+/*
+ * Candidate join between two clumps.
+ *
+ * This structure holds the cost metrics extracted from a speculative joinrel
+ * evaluation. We create this lightweight structure in cand_cxt after discarding
+ * the actual joinrel from scratch_cxt, allowing us to compare many candidates
+ * without exhausting memory.
+ */
+typedef struct GooCandidate
+{
+ RelOptInfo *left; /* left input clump */
+ RelOptInfo *right; /* right input clump */
+ Cost total_cost; /* total cost of cheapest path */
+} GooCandidate;
+
+static GooState * goo_init_state(PlannerInfo *root, List *initial_rels);
+static void goo_destroy_state(GooState * state);
+static RelOptInfo *goo_search_internal(GooState * state);
+static void goo_reset_probe_state(GooState * state, int saved_rel_len,
+ struct HTAB *saved_hash);
+static GooCandidate * goo_build_candidate(GooState * state, RelOptInfo *left,
+ RelOptInfo *right);
+static RelOptInfo *goo_commit_join(GooState * state, GooCandidate * cand);
+static bool goo_candidate_better(GooCandidate * a, GooCandidate * b);
+static bool goo_candidate_prunable(GooState * state, RelOptInfo *left,
+ RelOptInfo *right);
+
+/*
+ * goo_join_search
+ * Entry point for Greedy Operator Ordering join search algorithm.
+ *
+ * This function is called from make_rel_from_joinlist() when
+ * enable_goo_join_search is true and the number of relations meets or
+ * exceeds geqo_threshold.
+ *
+ * Returns the final RelOptInfo representing the join of all base relations,
+ * or errors out if no valid join order can be found.
+ */
+RelOptInfo *
+goo_join_search(PlannerInfo *root, int levels_needed,
+ List *initial_rels)
+{
+ GooState *state;
+ RelOptInfo *result;
+ int base_rel_count;
+ struct HTAB *base_hash;
+
+ /* Initialize search state and memory contexts */
+ state = goo_init_state(root, initial_rels);
+
+ /*
+ * Save initial state of join_rel_list and join_rel_hash so we can restore
+ * them if the search fails.
+ */
+ base_rel_count = list_length(root->join_rel_list);
+ base_hash = root->join_rel_hash;
+
+ /* Run the main greedy search loop */
+ result = goo_search_internal(state);
+
+ if (result == NULL)
+ {
+ /* Restore planner state before reporting error */
+ root->join_rel_list = list_truncate(root->join_rel_list, base_rel_count);
+ root->join_rel_hash = base_hash;
+ elog(ERROR, "GOO join search failed to find a valid join order");
+ }
+
+ goo_destroy_state(state);
+ return result;
+}
+
+/*
+ * goo_init_state
+ * Initialize per-search state and memory contexts.
+ *
+ * Creates the GooState structure and three memory contexts with different
+ * lifetimes:
+ *
+ * - goo_cxt: Lives for the entire search, holds the clumps list and state.
+ * - cand_cxt: Reset after each iteration, holds candidate structures during
+ * the comparison phase.
+ * - scratch_cxt: Reset after each candidate evaluation, holds speculative
+ * joinrels that are discarded before committing to a choice.
+ *
+ * The three-context design prevents memory bloat during large join searches
+ * where we may evaluate hundreds or thousands of candidate joins.
+ */
+static GooState * goo_init_state(PlannerInfo *root, List *initial_rels)
+{
+ MemoryContext oldcxt;
+ GooState *state;
+
+ oldcxt = MemoryContextSwitchTo(root->planner_cxt);
+
+ state = palloc(sizeof(GooState));
+ state->root = root;
+ state->clumps = NIL;
+ state->clause_pair_present = false;
+
+ /* Create the three-level memory context hierarchy */
+ state->goo_cxt = AllocSetContextCreate(root->planner_cxt, "GOOStateContext",
+ ALLOCSET_DEFAULT_SIZES);
+ state->cand_cxt = AllocSetContextCreate(state->goo_cxt, "GOOCandidateContext",
+ ALLOCSET_SMALL_SIZES);
+ state->scratch_cxt = AllocSetContextCreate(
+ state->goo_cxt, "GOOScratchContext", ALLOCSET_SMALL_SIZES);
+
+ /*
+ * Copy the initial_rels list into goo_cxt. This becomes our working
+ * clumps list that we'll modify throughout the search.
+ */
+ MemoryContextSwitchTo(state->goo_cxt);
+ state->clumps = list_copy(initial_rels);
+
+ MemoryContextSwitchTo(oldcxt);
+
+ return state;
+}
+
+/*
+ * goo_destroy_state
+ * Free all memory allocated for the GOO search.
+ *
+ * Deletes the goo_cxt memory context (which recursively deletes cand_cxt
+ * and scratch_cxt as children) and then frees the state structure itself.
+ * This is called after the search completes successfully or fails.
+ */
+static void
+goo_destroy_state(GooState * state)
+{
+ MemoryContextDelete(state->goo_cxt);
+ pfree(state);
+}
+
+/*
+ * goo_search_internal
+ * Main greedy search loop.
+ *
+ * Implements a two-pass algorithm at each iteration:
+ *
+ * Pass 1: Scan all clump pairs to detect whether any clause-connected pairs
+ * exist. This sets the clause_pair_present flag.
+ *
+ * Pass 2: Evaluate all viable candidate pairs, keeping track of the best one
+ * according to our comparison criteria. If clause_pair_present is true,
+ * we skip Cartesian products entirely to avoid expensive cross joins.
+ *
+ * After selecting the best candidate, we permanently create its joinrel in
+ * planner_cxt and replace the two input clumps with this new joinrel. This
+ * continues until only one clump remains.
+ *
+ * The function runs primarily in goo_cxt, temporarily switching to planner_cxt
+ * when creating permanent joinrels and to scratch_cxt when evaluating
+ * speculative candidates.
+ *
+ * Returns the final joinrel spanning all base relations, or NULL on failure.
+ */
+static RelOptInfo *
+goo_search_internal(GooState * state)
+{
+ PlannerInfo *root = state->root;
+ RelOptInfo *final_rel = NULL;
+ MemoryContext oldcxt;
+
+ /*
+ * Switch to goo_cxt for the entire search process. This ensures that all
+ * operations on state->clumps and related structures happen in the
+ * correct memory context.
+ */
+ oldcxt = MemoryContextSwitchTo(state->goo_cxt);
+
+ while (list_length(state->clumps) > 1)
+ {
+ ListCell *lc1;
+ int i;
+ GooCandidate *best_candidate = NULL;
+
+ /* Allow query cancellation during long join searches */
+ CHECK_FOR_INTERRUPTS();
+
+ /* Reset candidate context for this iteration */
+ MemoryContextReset(state->cand_cxt);
+ state->clause_pair_present = false;
+
+ /*
+ * Pass 1: Scan all pairs to detect clause-connected joins.
+ *
+ * We need to know whether ANY clause-connected pairs exist before we
+ * can decide whether to skip Cartesian products. This quick scan
+ * allows us to prefer well-connected joins without completely
+ * forbidding Cartesian products (which may be necessary for
+ * disconnected query graphs).
+ */
+ for (i = 0, lc1 = list_head(state->clumps); lc1 != NULL;
+ lc1 = lnext(state->clumps, lc1), i++)
+ {
+ RelOptInfo *left = lfirst_node(RelOptInfo, lc1);
+ ListCell *lc2 = lnext(state->clumps, lc1);
+
+ for (; lc2 != NULL; lc2 = lnext(state->clumps, lc2))
+ {
+ RelOptInfo *right = lfirst_node(RelOptInfo, lc2);
+
+ /* Check if this pair has a join clause or order restriction */
+ if (have_relevant_joinclause(root, left, right) ||
+ have_join_order_restriction(root, left, right))
+ {
+ /* Found at least one clause-connected pair */
+ state->clause_pair_present = true;
+ break;
+ }
+ }
+
+ if (state->clause_pair_present)
+ break;
+ }
+
+ /*
+ * Pass 2: Evaluate all viable candidate pairs and select the best.
+ *
+ * For each pair that passes the pruning check, we do a full
+ * speculative evaluation using make_join_rel() to get accurate costs.
+ * The candidate with the best cost (according to
+ * goo_candidate_better) is remembered and will be committed after
+ * this pass.
+ *
+ * TODO: It might be worth caching cost estimates if the same join
+ * pair appears in multiple iterations.
+ */
+ for (lc1 = list_head(state->clumps); lc1 != NULL;
+ lc1 = lnext(state->clumps, lc1))
+ {
+ RelOptInfo *left = lfirst_node(RelOptInfo, lc1);
+ ListCell *lc2 = lnext(state->clumps, lc1);
+
+ for (; lc2 != NULL; lc2 = lnext(state->clumps, lc2))
+ {
+ RelOptInfo *right = lfirst_node(RelOptInfo, lc2);
+ GooCandidate *cand;
+
+ cand = goo_build_candidate(state, left, right);
+ if (cand == NULL)
+ continue;
+
+ /* Track the best candidate seen so far */
+ if (best_candidate == NULL ||
+ goo_candidate_better(cand, best_candidate))
+ best_candidate = cand;
+ }
+ }
+
+ /* We must have at least one valid join candidate */
+ if (best_candidate == NULL)
+ elog(ERROR, "GOO join search failed to find any valid join candidates");
+
+ /*
+ * Commit the best candidate: create the joinrel permanently and
+ * update the clumps list.
+ */
+ final_rel = goo_commit_join(state, best_candidate);
+
+ if (final_rel == NULL)
+ elog(ERROR, "GOO join search failed to commit join");
+ }
+
+ /* Switch back to the original context before returning */
+ MemoryContextSwitchTo(oldcxt);
+
+ return final_rel;
+}
+
+/*
+ * goo_candidate_prunable
+ * Determine whether a candidate pair should be skipped.
+ *
+ * We use a two-level pruning strategy:
+ *
+ * 1. Pairs with join clauses or join-order restrictions are never prunable.
+ * These represent natural joins or required join orders (e.g., from outer
+ * joins or LATERAL references).
+ *
+ * 2. If clause_pair_present is true (meaning at least one clause-connected
+ * pair exists in this iteration), we prune Cartesian products to avoid
+ * evaluating expensive cross joins when better options are available.
+ *
+ * However, if NO clause-connected pairs exist in an iteration, we allow
+ * Cartesian products to be considered. This ensures we can always make
+ * progress even with disconnected query graphs.
+ *
+ * Returns true if the pair should be pruned (skipped), false otherwise.
+ */
+static bool
+goo_candidate_prunable(GooState * state, RelOptInfo *left,
+ RelOptInfo *right)
+{
+ PlannerInfo *root = state->root;
+ bool has_clause = have_relevant_joinclause(root, left, right);
+ bool has_restriction = have_join_order_restriction(root, left, right);
+
+ if (has_clause || has_restriction)
+ return false; /* never prune clause-connected joins */
+
+ return state->clause_pair_present;
+}
+
+/*
+ * goo_build_candidate
+ * Evaluate a potential join between two clumps and return a
+ *candidate.
+ *
+ * This function performs a speculative join evaluation to extract cost metrics
+ * without permanently creating the joinrel. The process is:
+ *
+ * 1. Check basic viability (pruning, overlapping relids).
+ * 2. Switch to scratch_cxt and create the joinrel using make_join_rel().
+ * 3. Generate paths (including partitionwise and parallel variants).
+ * 4. Extract cost metrics from the cheapest path.
+ * 5. Discard the joinrel by calling goo_reset_probe_state().
+ * 6. Create a lightweight GooCandidate in cand_cxt with the extracted metrics.
+ *
+ * This evaluate-and-discard pattern prevents memory bloat when evaluating
+ * many candidates. The winning candidate will be rebuilt permanently later
+ * by goo_commit_join().
+ *
+ * Returns a GooCandidate structure, or NULL if the join is illegal or
+ * overlapping. Assumes the caller is in goo_cxt.
+ */
+static GooCandidate * goo_build_candidate(GooState * state, RelOptInfo *left,
+ RelOptInfo *right)
+{
+ PlannerInfo *root = state->root;
+ MemoryContext oldcxt;
+ int saved_rel_len;
+ struct HTAB *saved_hash;
+ RelOptInfo *joinrel;
+ Path *best_path;
+ Cost total_cost;
+ GooCandidate *cand;
+
+ /* Skip if this pair should be pruned */
+ if (goo_candidate_prunable(state, left, right))
+ return NULL;
+
+ /* Sanity check: ensure the clumps don't overlap */
+ if (bms_overlap(left->relids, right->relids))
+ return NULL;
+
+ /*
+ * Save state before speculative join evaluation. We'll create the joinrel
+ * in scratch_cxt and then discard it.
+ */
+ saved_rel_len = list_length(root->join_rel_list);
+ saved_hash = root->join_rel_hash;
+
+ /* Switch to scratch_cxt for speculative joinrel creation */
+ oldcxt = MemoryContextSwitchTo(state->scratch_cxt);
+
+ /*
+ * Temporarily disable join_rel_hash so make_join_rel() doesn't find or
+ * cache this speculative joinrel.
+ */
+ root->join_rel_hash = NULL;
+
+ /*
+ * Create the joinrel and generate all its paths.
+ *
+ * TODO: This is the most expensive part of GOO. Each candidate evaluation
+ * performs full path generation via make_join_rel(). We might improve
+ * performance by deferring expensive path variants (partitionwise,
+ * parallel) until the commit phase.
+ */
+ joinrel = make_join_rel(root, left, right);
+
+ if (joinrel)
+ {
+ /* Generate additional path variants */
+ generate_partitionwise_join_paths(root, joinrel);
+ if (!bms_equal(joinrel->relids, root->all_query_rels))
+ generate_useful_gather_paths(root, joinrel, false);
+ set_cheapest(joinrel);
+ }
+
+ best_path = joinrel ? joinrel->cheapest_total_path : NULL;
+ if (best_path == NULL)
+ {
+ /* Invalid or uninteresting join, clean up and return NULL */
+ MemoryContextSwitchTo(oldcxt);
+ goo_reset_probe_state(state, saved_rel_len, saved_hash);
+ return NULL;
+ }
+
+ /*
+ * Extract the metrics we need from the speculative joinrel. After this,
+ * we'll discard the entire joinrel and all its paths.
+ */
+ total_cost = best_path->total_cost;
+
+ /*
+ * Switch back to goo_cxt and discard the speculative joinrel.
+ * goo_reset_probe_state() will clean up join_rel_list, join_rel_hash, and
+ * reset scratch_cxt to free all the joinrel's memory.
+ */
+ MemoryContextSwitchTo(oldcxt);
+ goo_reset_probe_state(state, saved_rel_len, saved_hash);
+
+ /*
+ * Now create the candidate structure in cand_cxt. This will survive until
+ * the end of this iteration (when cand_cxt is reset).
+ */
+ oldcxt = MemoryContextSwitchTo(state->cand_cxt);
+ cand = palloc(sizeof(GooCandidate));
+ cand->left = left;
+ cand->right = right;
+ cand->total_cost = total_cost;
+ MemoryContextSwitchTo(oldcxt);
+
+ return cand;
+}
+
+/*
+ * goo_reset_probe_state
+ * Clean up after a speculative joinrel evaluation.
+ *
+ * Reverts the planner's join_rel_list and join_rel_hash to their saved state,
+ * removing any joinrels that were created during speculative evaluation.
+ * Also resets scratch_cxt to free all memory used by the discarded joinrel
+ * and its paths.
+ *
+ * This function is called after extracting cost metrics from a speculative
+ * joinrel that we don't want to keep.
+ */
+static void
+goo_reset_probe_state(GooState * state, int saved_rel_len,
+ struct HTAB *saved_hash)
+{
+ PlannerInfo *root = state->root;
+
+ /* Remove speculative joinrels from the planner's lists */
+ root->join_rel_list = list_truncate(root->join_rel_list, saved_rel_len);
+ root->join_rel_hash = saved_hash;
+
+ /* Free all memory used during speculative evaluation */
+ MemoryContextReset(state->scratch_cxt);
+}
+
+/*
+ * goo_commit_join
+ * Permanently create the chosen join and update the clumps list.
+ *
+ * After selecting the best candidate in an iteration, we need to permanently
+ * create its joinrel (with all paths) and integrate it into the planner state.
+ * This function:
+ *
+ * 1. Switches to planner_cxt and creates the joinrel using make_join_rel().
+ * Unlike the speculative evaluation, this joinrel is kept permanently.
+ * 2. Generates partitionwise and parallel path variants.
+ * 3. Determines the cheapest paths.
+ * 4. Updates state->clumps by removing the two input clumps and adding the
+ * new joinrel as a single clump.
+ *
+ * The next iteration will treat this joinrel as an atomic unit that can be
+ * joined with other remaining clumps.
+ *
+ * Returns the newly created joinrel. Assumes the caller is in goo_cxt.
+ */
+static RelOptInfo *
+goo_commit_join(GooState * state, GooCandidate * cand)
+{
+ MemoryContext oldcxt;
+ PlannerInfo *root = state->root;
+ RelOptInfo *joinrel;
+
+ /*
+ * Create the joinrel permanently in planner_cxt. Unlike the speculative
+ * evaluation in goo_build_candidate(), this joinrel will be kept and
+ * added to root->join_rel_list for use by the rest of the planner.
+ */
+ oldcxt = MemoryContextSwitchTo(root->planner_cxt);
+
+ joinrel = make_join_rel(root, cand->left, cand->right);
+ if (joinrel == NULL)
+ {
+ MemoryContextSwitchTo(oldcxt);
+ elog(ERROR, "GOO join search failed to create join relation");
+ }
+
+ /* Generate additional path variants, just like standard_join_search() */
+ generate_partitionwise_join_paths(root, joinrel);
+ if (!bms_equal(joinrel->relids, root->all_query_rels))
+ generate_useful_gather_paths(root, joinrel, false);
+ set_cheapest(joinrel);
+
+ /*
+ * Switch back to goo_cxt and update the clumps list. Remove the two input
+ * clumps and add the new joinrel as a single clump.
+ */
+ MemoryContextSwitchTo(oldcxt);
+
+ state->clumps = list_delete_ptr(state->clumps, cand->left);
+ state->clumps = list_delete_ptr(state->clumps, cand->right);
+ state->clumps = lappend(state->clumps, joinrel);
+
+ return joinrel;
+}
+
+/*
+ * goo_candidate_better
+ * Compare two join candidates and determine which is better.
+ *
+ * Returns true if candidate 'a' should be preferred over candidate 'b'.
+ */
+static bool
+goo_candidate_better(GooCandidate * a, GooCandidate * b)
+{
+ return (a->total_cost < b->total_cost);
+}
diff --git a/src/backend/optimizer/path/meson.build b/src/backend/optimizer/path/meson.build
index 12f36d85cb6..e5046365a37 100644
--- a/src/backend/optimizer/path/meson.build
+++ b/src/backend/optimizer/path/meson.build
@@ -5,6 +5,7 @@ backend_sources += files(
'clausesel.c',
'costsize.c',
'equivclass.c',
+ 'goo.c',
'indxpath.c',
'joinpath.c',
'joinrels.c',
diff --git a/src/backend/utils/misc/guc_parameters.dat b/src/backend/utils/misc/guc_parameters.dat
index 3b9d8349078..a8ce31ab8a7 100644
--- a/src/backend/utils/misc/guc_parameters.dat
+++ b/src/backend/utils/misc/guc_parameters.dat
@@ -840,6 +840,15 @@
boot_val => 'true',
},
+/* WIP: for now keep this in QUERY_TUNING_GEQO group for testing convenience */
+{ name => 'enable_goo_join_search', type => 'bool', context => 'PGC_USERSET', group => 'QUERY_TUNING_GEQO',
+ short_desc => 'Enables the planner\'s use of GOO join search for large join problems.',
+ long_desc => 'Greedy Operator Ordering (GOO) is a deterministic join search algorithm for queries with many relations.',
+ flags => 'GUC_EXPLAIN',
+ variable => 'enable_goo_join_search',
+ boot_val => 'false',
+},
+
{ name => 'enable_group_by_reordering', type => 'bool', context => 'PGC_USERSET', group => 'QUERY_TUNING_METHOD',
short_desc => 'Enables reordering of GROUP BY keys.',
flags => 'GUC_EXPLAIN',
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index dc9e2255f8a..8284e8b1da7 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -456,6 +456,7 @@
# - Genetic Query Optimizer -
#geqo = on
+#enable_goo_join_search = off
#geqo_threshold = 12
#geqo_effort = 5 # range 1-10
#geqo_pool_size = 0 # selects default based on effort
diff --git a/src/include/optimizer/goo.h b/src/include/optimizer/goo.h
new file mode 100644
index 00000000000..0080dfa2ac8
--- /dev/null
+++ b/src/include/optimizer/goo.h
@@ -0,0 +1,23 @@
+/*-------------------------------------------------------------------------
+ *
+ * goo.h
+ * prototype for the greedy operator ordering join search
+ *
+ * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * IDENTIFICATION
+ * src/include/optimizer/goo.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef GOO_H
+#define GOO_H
+
+#include "nodes/pathnodes.h"
+#include "nodes/pg_list.h"
+
+extern RelOptInfo *goo_join_search(PlannerInfo *root, int levels_needed,
+ List *initial_rels);
+
+#endif /* GOO_H */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index f6a62df0b43..5b3ebe5f1d2 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -21,6 +21,7 @@
* allpaths.c
*/
extern PGDLLIMPORT bool enable_geqo;
+extern PGDLLIMPORT bool enable_goo_join_search;
extern PGDLLIMPORT bool enable_eager_aggregate;
extern PGDLLIMPORT int geqo_threshold;
extern PGDLLIMPORT double min_eager_agg_group_size;
diff --git a/src/test/regress/expected/goo.out b/src/test/regress/expected/goo.out
new file mode 100644
index 00000000000..88996f57508
--- /dev/null
+++ b/src/test/regress/expected/goo.out
@@ -0,0 +1,634 @@
+--
+-- GOO (Greedy Operator Ordering) Join Search Tests
+--
+-- This test suite validates the GOO join ordering algorithm and verifies
+-- correct behavior for various query patterns.
+--
+-- Create test tables with various sizes and join patterns
+CREATE TEMP TABLE t1 (a int, b int);
+CREATE TEMP TABLE t2 (a int, c int);
+CREATE TEMP TABLE t3 (b int, d int);
+CREATE TEMP TABLE t4 (c int, e int);
+CREATE TEMP TABLE t5 (d int, f int);
+CREATE TEMP TABLE t6 (e int, g int);
+CREATE TEMP TABLE t7 (f int, h int);
+CREATE TEMP TABLE t8 (g int, i int);
+CREATE TEMP TABLE t9 (h int, j int);
+CREATE TEMP TABLE t10 (i int, k int);
+CREATE TEMP TABLE t11 (j int, l int);
+CREATE TEMP TABLE t12 (k int, m int);
+CREATE TEMP TABLE t13 (l int, n int);
+CREATE TEMP TABLE t14 (m int, o int);
+CREATE TEMP TABLE t15 (n int, p int);
+CREATE TEMP TABLE t16 (o int, q int);
+CREATE TEMP TABLE t17 (p int, r int);
+CREATE TEMP TABLE t18 (q int, s int);
+-- Populate with small amount of data
+INSERT INTO t1 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t2 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t3 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t4 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t5 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t6 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t7 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t8 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t9 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t10 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t11 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t12 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t13 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t14 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t15 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t16 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t17 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t18 SELECT i, i FROM generate_series(1,10) i;
+ANALYZE;
+--
+-- Basic 3-way join (sanity check)
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 2;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM (VALUES (1),(2)) AS a(x)
+JOIN (VALUES (1),(2)) AS b(x) USING (x)
+JOIN (VALUES (1),(3)) AS c(x) USING (x);
+ QUERY PLAN
+----------------------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: ("*VALUES*".column1 = "*VALUES*_2".column1)
+ -> Hash Join
+ Hash Cond: ("*VALUES*".column1 = "*VALUES*_1".column1)
+ -> Values Scan on "*VALUES*"
+ -> Hash
+ -> Values Scan on "*VALUES*_1"
+ -> Hash
+ -> Values Scan on "*VALUES*_2"
+(10 rows)
+
+SELECT count(*)
+FROM (VALUES (1),(2)) AS a(x)
+JOIN (VALUES (1),(2)) AS b(x) USING (x)
+JOIN (VALUES (1),(3)) AS c(x) USING (x);
+ count
+-------
+ 1
+(1 row)
+
+--
+-- Disconnected graph (Cartesian products required)
+--
+-- This tests GOO's ability to handle queries where some relations
+-- have no join clauses connecting them. GOO should allow Cartesian
+-- products when no clause-connected joins are available.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2, t5
+WHERE t1.a = 1 AND t2.c = 2 AND t5.f = 3;
+ QUERY PLAN
+-------------------------------------
+ Aggregate
+ -> Nested Loop
+ -> Seq Scan on t5
+ Filter: (f = 3)
+ -> Nested Loop
+ -> Seq Scan on t1
+ Filter: (a = 1)
+ -> Seq Scan on t2
+ Filter: (c = 2)
+(9 rows)
+
+SELECT count(*)
+FROM t1, t2, t5
+WHERE t1.a = 1 AND t2.c = 2 AND t5.f = 3;
+ count
+-------
+ 1
+(1 row)
+
+--
+-- Star schema (fact table with multiple dimension tables)
+--
+-- Test GOO with a typical star schema join pattern.
+--
+CREATE TEMP TABLE fact (id int, dim1_id int, dim2_id int, dim3_id int, dim4_id int, value int);
+CREATE TEMP TABLE dim1 (id int, name text);
+CREATE TEMP TABLE dim2 (id int, name text);
+CREATE TEMP TABLE dim3 (id int, name text);
+CREATE TEMP TABLE dim4 (id int, name text);
+INSERT INTO fact SELECT i, i, i, i, i, i FROM generate_series(1,100) i;
+INSERT INTO dim1 SELECT i, 'dim1_'||i FROM generate_series(1,10) i;
+INSERT INTO dim2 SELECT i, 'dim2_'||i FROM generate_series(1,10) i;
+INSERT INTO dim3 SELECT i, 'dim3_'||i FROM generate_series(1,10) i;
+INSERT INTO dim4 SELECT i, 'dim4_'||i FROM generate_series(1,10) i;
+ANALYZE;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM fact
+JOIN dim1 ON fact.dim1_id = dim1.id
+JOIN dim2 ON fact.dim2_id = dim2.id
+JOIN dim3 ON fact.dim3_id = dim3.id
+JOIN dim4 ON fact.dim4_id = dim4.id
+WHERE dim1.id < 5;
+ QUERY PLAN
+---------------------------------------------------------------------------
+ Aggregate
+ -> Nested Loop
+ Join Filter: (fact.dim4_id = dim4.id)
+ -> Hash Join
+ Hash Cond: (dim3.id = fact.dim3_id)
+ -> Seq Scan on dim3
+ -> Hash
+ -> Hash Join
+ Hash Cond: (dim2.id = fact.dim2_id)
+ -> Seq Scan on dim2
+ -> Hash
+ -> Hash Join
+ Hash Cond: (fact.dim1_id = dim1.id)
+ -> Seq Scan on fact
+ -> Hash
+ -> Seq Scan on dim1
+ Filter: (id < 5)
+ -> Seq Scan on dim4
+(18 rows)
+
+--
+-- Long join chain
+--
+-- Tests GOO with a large join involving 15 relations.
+--
+SET geqo_threshold = 8;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n;
+ QUERY PLAN
+----------------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (t7.h = t9.h)
+ -> Hash Join
+ Hash Cond: (t8.i = t10.i)
+ -> Hash Join
+ Hash Cond: (t2.c = t4.c)
+ -> Hash Join
+ Hash Cond: (t3.b = t1.b)
+ -> Hash Join
+ Hash Cond: (t5.f = t7.f)
+ -> Hash Join
+ Hash Cond: (t3.d = t5.d)
+ -> Seq Scan on t3
+ -> Hash
+ -> Seq Scan on t5
+ -> Hash
+ -> Seq Scan on t7
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t6.g = t8.g)
+ -> Hash Join
+ Hash Cond: (t4.e = t6.e)
+ -> Seq Scan on t4
+ -> Hash
+ -> Seq Scan on t6
+ -> Hash
+ -> Seq Scan on t8
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t12.m = t14.m)
+ -> Hash Join
+ Hash Cond: (t10.k = t12.k)
+ -> Seq Scan on t10
+ -> Hash
+ -> Seq Scan on t12
+ -> Hash
+ -> Seq Scan on t14
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t11.l = t13.l)
+ -> Hash Join
+ Hash Cond: (t9.j = t11.j)
+ -> Seq Scan on t9
+ -> Hash
+ -> Seq Scan on t11
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t13.n = t15.n)
+ -> Seq Scan on t13
+ -> Hash
+ -> Seq Scan on t15
+(58 rows)
+
+-- Execute to verify correctness
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n;
+ count
+-------
+ 10
+(1 row)
+
+--
+-- Bushy tree support
+--
+-- Verify that GOO can produce bushy join trees, not just left-deep or right-deep.
+-- With appropriate cost model, GOO should join (t1,t2) and (t3,t4) first,
+-- then join those results (bushy tree).
+--
+SET geqo_threshold = 4;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2, t3, t4
+WHERE t1.a = t2.a
+ AND t3.b = t4.c
+ AND t1.a = t3.b;
+ QUERY PLAN
+----------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (t1.a = t3.b)
+ -> Hash Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t3.b = t4.c)
+ -> Seq Scan on t3
+ -> Hash
+ -> Seq Scan on t4
+(14 rows)
+
+--
+-- Compare GOO vs standard join search
+--
+-- Run the same query with GOO and standard join search to verify both
+-- produce valid plans. Results should be identical even if plans differ.
+--
+SET enable_goo_join_search = on;
+PREPARE goo_plan AS
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e;
+EXECUTE goo_plan;
+ count
+-------
+ 10
+(1 row)
+
+SET enable_goo_join_search = off;
+SET geqo_threshold = default;
+PREPARE standard_plan AS
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e;
+EXECUTE standard_plan;
+ count
+-------
+ 10
+(1 row)
+
+-- Results should match
+EXECUTE goo_plan;
+ count
+-------
+ 10
+(1 row)
+
+EXECUTE standard_plan;
+ count
+-------
+ 10
+(1 row)
+
+--
+-- Large join (18 relations)
+--
+-- Test GOO with a large number of relations.
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 10;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n
+JOIN t16 ON t14.o = t16.o
+JOIN t17 ON t15.p = t17.p
+JOIN t18 ON t16.q = t18.q;
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (t16.q = t18.q)
+ -> Hash Join
+ Hash Cond: (t15.p = t17.p)
+ -> Hash Join
+ Hash Cond: (t14.o = t16.o)
+ -> Hash Join
+ Hash Cond: (t13.n = t15.n)
+ -> Hash Join
+ Hash Cond: (t12.m = t14.m)
+ -> Hash Join
+ Hash Cond: (t11.l = t13.l)
+ -> Hash Join
+ Hash Cond: (t10.k = t12.k)
+ -> Hash Join
+ Hash Cond: (t9.j = t11.j)
+ -> Hash Join
+ Hash Cond: (t8.i = t10.i)
+ -> Hash Join
+ Hash Cond: (t7.h = t9.h)
+ -> Hash Join
+ Hash Cond: (t6.g = t8.g)
+ -> Hash Join
+ Hash Cond: (t5.f = t7.f)
+ -> Hash Join
+ Hash Cond: (t4.e = t6.e)
+ -> Hash Join
+ Hash Cond: (t3.d = t5.d)
+ -> Hash Join
+ Hash Cond: (t2.c = t4.c)
+ -> Hash Join
+ Hash Cond: (t1.b = t3.b)
+ -> Hash Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Seq Scan on t3
+ -> Hash
+ -> Seq Scan on t4
+ -> Hash
+ -> Seq Scan on t5
+ -> Hash
+ -> Seq Scan on t6
+ -> Hash
+ -> Seq Scan on t7
+ -> Hash
+ -> Seq Scan on t8
+ -> Hash
+ -> Seq Scan on t9
+ -> Hash
+ -> Seq Scan on t10
+ -> Hash
+ -> Seq Scan on t11
+ -> Hash
+ -> Seq Scan on t12
+ -> Hash
+ -> Seq Scan on t13
+ -> Hash
+ -> Seq Scan on t14
+ -> Hash
+ -> Seq Scan on t15
+ -> Hash
+ -> Seq Scan on t16
+ -> Hash
+ -> Seq Scan on t17
+ -> Hash
+ -> Seq Scan on t18
+(70 rows)
+
+--
+-- Mixed connected and disconnected components
+--
+-- Query with two connected components that need a Cartesian product between them.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a,
+ t5 JOIN t6 ON t5.f = t6.e
+WHERE t1.a < 5 AND t5.d < 3;
+ QUERY PLAN
+-------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (t2.a = t1.a)
+ -> Seq Scan on t2
+ -> Hash
+ -> Nested Loop
+ -> Hash Join
+ Hash Cond: (t6.e = t5.f)
+ -> Seq Scan on t6
+ -> Hash
+ -> Seq Scan on t5
+ Filter: (d < 3)
+ -> Seq Scan on t1
+ Filter: (a < 5)
+(14 rows)
+
+--
+-- Outer joins
+--
+-- Verify GOO handles outer joins correctly (respects join order restrictions)
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+LEFT JOIN t2 ON t1.a = t2.a
+LEFT JOIN t3 ON t2.a = t3.b
+LEFT JOIN t4 ON t3.d = t4.c;
+ QUERY PLAN
+----------------------------------------------
+ Aggregate
+ -> Hash Left Join
+ Hash Cond: (t3.d = t4.c)
+ -> Hash Left Join
+ Hash Cond: (t2.a = t3.b)
+ -> Hash Left Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Seq Scan on t3
+ -> Hash
+ -> Seq Scan on t4
+(14 rows)
+
+--
+-- Complete Cartesian products (disconnected graphs)
+--
+-- Test GOO's ability to handle queries with no join clauses at all.
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 2;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2;
+ QUERY PLAN
+----------------------------------
+ Aggregate
+ -> Nested Loop
+ -> Seq Scan on t1
+ -> Materialize
+ -> Seq Scan on t2
+(5 rows)
+
+SELECT count(*)
+FROM t1, t2;
+ count
+-------
+ 100
+(1 row)
+
+--
+-- Join order restrictions with FULL OUTER JOIN
+--
+-- FULL OUTER JOIN creates strong ordering constraints that GOO must respect
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+FULL OUTER JOIN t2 ON t1.a = t2.a
+FULL OUTER JOIN t3 ON t2.a = t3.b;
+ QUERY PLAN
+----------------------------------------
+ Aggregate
+ -> Hash Full Join
+ Hash Cond: (t2.a = t3.b)
+ -> Hash Full Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Seq Scan on t3
+(10 rows)
+
+--
+-- Self-join handling
+--
+-- Test GOO with the same table appearing multiple times. GOO must correctly
+-- handle self-joins that were not removed by Self-Join Elimination.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1 a
+JOIN t1 b ON a.a = b.a
+JOIN t2 c ON b.b = c.c;
+ QUERY PLAN
+------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (b.b = c.c)
+ -> Hash Join
+ Hash Cond: (a.a = b.a)
+ -> Seq Scan on t1 a
+ -> Hash
+ -> Seq Scan on t1 b
+ -> Hash
+ -> Seq Scan on t2 c
+(10 rows)
+
+--
+-- Complex bushy tree pattern
+--
+-- Create a query that naturally leads to bushy tree: multiple independent
+-- join chains that need to be combined
+--
+CREATE TEMP TABLE chain1a (id int, val int);
+CREATE TEMP TABLE chain1b (id int, val int);
+CREATE TEMP TABLE chain1c (id int, val int);
+CREATE TEMP TABLE chain2a (id int, val int);
+CREATE TEMP TABLE chain2b (id int, val int);
+CREATE TEMP TABLE chain2c (id int, val int);
+INSERT INTO chain1a SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain1b SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain1c SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2a SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2b SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2c SELECT i, i FROM generate_series(1,100) i;
+ANALYZE;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM chain1a
+JOIN chain1b ON chain1a.id = chain1b.id
+JOIN chain1c ON chain1b.val = chain1c.id
+JOIN chain2a ON chain1a.val = chain2a.id -- Cross-chain join
+JOIN chain2b ON chain2a.val = chain2b.id
+JOIN chain2c ON chain2b.val = chain2c.id;
+ QUERY PLAN
+-----------------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (chain1a.val = chain2a.id)
+ -> Hash Join
+ Hash Cond: (chain1b.val = chain1c.id)
+ -> Hash Join
+ Hash Cond: (chain1a.id = chain1b.id)
+ -> Seq Scan on chain1a
+ -> Hash
+ -> Seq Scan on chain1b
+ -> Hash
+ -> Seq Scan on chain1c
+ -> Hash
+ -> Hash Join
+ Hash Cond: (chain2b.val = chain2c.id)
+ -> Hash Join
+ Hash Cond: (chain2a.val = chain2b.id)
+ -> Seq Scan on chain2a
+ -> Hash
+ -> Seq Scan on chain2b
+ -> Hash
+ -> Seq Scan on chain2c
+(22 rows)
+
+-- Cleanup
+DEALLOCATE goo_plan;
+DEALLOCATE standard_plan;
+RESET geqo_threshold;
+RESET enable_goo_join_search;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index 3b37fafa65b..cb0c84cebff 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -153,6 +153,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_distinct_reordering | on
enable_eager_aggregate | on
enable_gathermerge | on
+ enable_goo_join_search | off
enable_group_by_reordering | on
enable_hashagg | on
enable_hashjoin | on
@@ -173,7 +174,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_seqscan | on
enable_sort | 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.
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index cc6d799bcea..14e3a475906 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -68,6 +68,12 @@ test: select_into select_distinct select_distinct_on select_implicit select_havi
# ----------
test: brin gin gist spgist privileges init_privs security_label collate matview lock replica_identity rowsecurity object_address tablesample groupingsets drop_operator password identity generated_stored join_hash
+# ----------
+# Additional JOIN ORDER tests
+# WIP: need to find an appropriate group for this test
+# ----------
+test: goo
+
# ----------
# Additional BRIN tests
# ----------
@@ -98,9 +104,6 @@ test: maintain_every
# no relation related tests can be put in this group
test: publication subscription
-# ----------
-# Another group of parallel tests
-# select_views depends on create_view
# ----------
test: select_views portals_p2 foreign_key cluster dependency guc bitmapops combocid tsearch tsdicts foreign_data window xmlmap functional_deps advisory_lock indirect_toast equivclass stats_rewrite
diff --git a/src/test/regress/sql/goo.sql b/src/test/regress/sql/goo.sql
new file mode 100644
index 00000000000..c4d9cae48a4
--- /dev/null
+++ b/src/test/regress/sql/goo.sql
@@ -0,0 +1,329 @@
+--
+-- GOO (Greedy Operator Ordering) Join Search Tests
+--
+-- This test suite validates the GOO join ordering algorithm and verifies
+-- correct behavior for various query patterns.
+--
+
+-- Create test tables with various sizes and join patterns
+CREATE TEMP TABLE t1 (a int, b int);
+CREATE TEMP TABLE t2 (a int, c int);
+CREATE TEMP TABLE t3 (b int, d int);
+CREATE TEMP TABLE t4 (c int, e int);
+CREATE TEMP TABLE t5 (d int, f int);
+CREATE TEMP TABLE t6 (e int, g int);
+CREATE TEMP TABLE t7 (f int, h int);
+CREATE TEMP TABLE t8 (g int, i int);
+CREATE TEMP TABLE t9 (h int, j int);
+CREATE TEMP TABLE t10 (i int, k int);
+CREATE TEMP TABLE t11 (j int, l int);
+CREATE TEMP TABLE t12 (k int, m int);
+CREATE TEMP TABLE t13 (l int, n int);
+CREATE TEMP TABLE t14 (m int, o int);
+CREATE TEMP TABLE t15 (n int, p int);
+CREATE TEMP TABLE t16 (o int, q int);
+CREATE TEMP TABLE t17 (p int, r int);
+CREATE TEMP TABLE t18 (q int, s int);
+
+-- Populate with small amount of data
+INSERT INTO t1 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t2 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t3 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t4 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t5 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t6 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t7 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t8 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t9 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t10 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t11 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t12 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t13 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t14 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t15 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t16 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t17 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t18 SELECT i, i FROM generate_series(1,10) i;
+
+ANALYZE;
+
+--
+-- Basic 3-way join (sanity check)
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 2;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM (VALUES (1),(2)) AS a(x)
+JOIN (VALUES (1),(2)) AS b(x) USING (x)
+JOIN (VALUES (1),(3)) AS c(x) USING (x);
+
+SELECT count(*)
+FROM (VALUES (1),(2)) AS a(x)
+JOIN (VALUES (1),(2)) AS b(x) USING (x)
+JOIN (VALUES (1),(3)) AS c(x) USING (x);
+
+--
+-- Disconnected graph (Cartesian products required)
+--
+-- This tests GOO's ability to handle queries where some relations
+-- have no join clauses connecting them. GOO should allow Cartesian
+-- products when no clause-connected joins are available.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2, t5
+WHERE t1.a = 1 AND t2.c = 2 AND t5.f = 3;
+
+SELECT count(*)
+FROM t1, t2, t5
+WHERE t1.a = 1 AND t2.c = 2 AND t5.f = 3;
+
+--
+-- Star schema (fact table with multiple dimension tables)
+--
+-- Test GOO with a typical star schema join pattern.
+--
+CREATE TEMP TABLE fact (id int, dim1_id int, dim2_id int, dim3_id int, dim4_id int, value int);
+CREATE TEMP TABLE dim1 (id int, name text);
+CREATE TEMP TABLE dim2 (id int, name text);
+CREATE TEMP TABLE dim3 (id int, name text);
+CREATE TEMP TABLE dim4 (id int, name text);
+
+INSERT INTO fact SELECT i, i, i, i, i, i FROM generate_series(1,100) i;
+INSERT INTO dim1 SELECT i, 'dim1_'||i FROM generate_series(1,10) i;
+INSERT INTO dim2 SELECT i, 'dim2_'||i FROM generate_series(1,10) i;
+INSERT INTO dim3 SELECT i, 'dim3_'||i FROM generate_series(1,10) i;
+INSERT INTO dim4 SELECT i, 'dim4_'||i FROM generate_series(1,10) i;
+
+ANALYZE;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM fact
+JOIN dim1 ON fact.dim1_id = dim1.id
+JOIN dim2 ON fact.dim2_id = dim2.id
+JOIN dim3 ON fact.dim3_id = dim3.id
+JOIN dim4 ON fact.dim4_id = dim4.id
+WHERE dim1.id < 5;
+
+--
+-- Long join chain
+--
+-- Tests GOO with a large join involving 15 relations.
+--
+SET geqo_threshold = 8;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n;
+
+-- Execute to verify correctness
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n;
+
+--
+-- Bushy tree support
+--
+-- Verify that GOO can produce bushy join trees, not just left-deep or right-deep.
+-- With appropriate cost model, GOO should join (t1,t2) and (t3,t4) first,
+-- then join those results (bushy tree).
+--
+SET geqo_threshold = 4;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2, t3, t4
+WHERE t1.a = t2.a
+ AND t3.b = t4.c
+ AND t1.a = t3.b;
+
+--
+-- Compare GOO vs standard join search
+--
+-- Run the same query with GOO and standard join search to verify both
+-- produce valid plans. Results should be identical even if plans differ.
+--
+SET enable_goo_join_search = on;
+PREPARE goo_plan AS
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e;
+
+EXECUTE goo_plan;
+
+SET enable_goo_join_search = off;
+SET geqo_threshold = default;
+PREPARE standard_plan AS
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e;
+
+EXECUTE standard_plan;
+
+-- Results should match
+EXECUTE goo_plan;
+EXECUTE standard_plan;
+
+--
+-- Large join (18 relations)
+--
+-- Test GOO with a large number of relations.
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 10;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n
+JOIN t16 ON t14.o = t16.o
+JOIN t17 ON t15.p = t17.p
+JOIN t18 ON t16.q = t18.q;
+
+--
+-- Mixed connected and disconnected components
+--
+-- Query with two connected components that need a Cartesian product between them.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a,
+ t5 JOIN t6 ON t5.f = t6.e
+WHERE t1.a < 5 AND t5.d < 3;
+
+--
+-- Outer joins
+--
+-- Verify GOO handles outer joins correctly (respects join order restrictions)
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+LEFT JOIN t2 ON t1.a = t2.a
+LEFT JOIN t3 ON t2.a = t3.b
+LEFT JOIN t4 ON t3.d = t4.c;
+
+--
+-- Complete Cartesian products (disconnected graphs)
+--
+-- Test GOO's ability to handle queries with no join clauses at all.
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 2;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2;
+
+SELECT count(*)
+FROM t1, t2;
+
+--
+-- Join order restrictions with FULL OUTER JOIN
+--
+-- FULL OUTER JOIN creates strong ordering constraints that GOO must respect
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+FULL OUTER JOIN t2 ON t1.a = t2.a
+FULL OUTER JOIN t3 ON t2.a = t3.b;
+
+--
+-- Self-join handling
+--
+-- Test GOO with the same table appearing multiple times. GOO must correctly
+-- handle self-joins that were not removed by Self-Join Elimination.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1 a
+JOIN t1 b ON a.a = b.a
+JOIN t2 c ON b.b = c.c;
+
+--
+-- Complex bushy tree pattern
+--
+-- Create a query that naturally leads to bushy tree: multiple independent
+-- join chains that need to be combined
+--
+CREATE TEMP TABLE chain1a (id int, val int);
+CREATE TEMP TABLE chain1b (id int, val int);
+CREATE TEMP TABLE chain1c (id int, val int);
+CREATE TEMP TABLE chain2a (id int, val int);
+CREATE TEMP TABLE chain2b (id int, val int);
+CREATE TEMP TABLE chain2c (id int, val int);
+
+INSERT INTO chain1a SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain1b SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain1c SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2a SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2b SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2c SELECT i, i FROM generate_series(1,100) i;
+
+ANALYZE;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM chain1a
+JOIN chain1b ON chain1a.id = chain1b.id
+JOIN chain1c ON chain1b.val = chain1c.id
+JOIN chain2a ON chain1a.val = chain2a.id -- Cross-chain join
+JOIN chain2b ON chain2a.val = chain2b.id
+JOIN chain2c ON chain2b.val = chain2c.id;
+
+-- Cleanup
+DEALLOCATE goo_plan;
+DEALLOCATE standard_plan;
+
+RESET geqo_threshold;
+RESET enable_goo_join_search;
--
2.39.3 (Apple Git-146)
On Tue, Dec 2, 2025 at 9:18 AM Chengpeng Yan <chengpeng_yan@outlook.com> wrote:
Hi hackers,
This patch implements GOO (Greedy Operator Ordering), a greedy
join-order search method for large join problems, based on Fegaras (DEXA
’98) [1]. The algorithm repeatedly selects, among all legal joins, the
join pair with the lowest estimated total cost, merges them, and
continues until a single join remains. Patch attached.
Interesting.
To get an initial sense of performance, I reused the star join /
snowflake examples and the testing script from the thread in [2]. The
star-join GUC in that SQL workload was replaced with
`enable_goo_join_search`, so the same tests can run under DP (standard
dynamic programming) / GEQO(Genetic Query Optimizer) / GOO. For these
tests, geqo_threshold was set to 15 for DP, and to 5 for both GEQO and
GOO. Other planner settings, including join_collapse_limit, remained at
their defaults.On my local machine, a single-client pgbench run produces the following
throughput (tps):| DP | GEQO | GOO
--------------------+----------+----------+-----------
starjoin (inner) | 1762.52 | 192.13 | 6168.89
starjoin (outer) | 1683.92 | 173.90 | 5626.56
snowflake (inner) | 1829.04 | 133.40 | 3929.57
snowflake (outer) | 1397.93 | 99.65 | 3040.52
Is pgbench the right workload to test this, I mean what are we trying
to compare here the planning time taken by DP vs GEQO vs GOO or the
quality of the plans generated by different join ordering algorithms
or both? All pgbench queries are single table scans and there is no
involvement of the join search, so I am not sure how we can justify
these gains?
--
Regards,
Dilip Kumar
Google
Hi,
Thanks for taking a look.
On Dec 2, 2025, at 13:36, Dilip Kumar <dilipbalaut@gmail.com> wrote:
Is pgbench the right workload to test this, I mean what are we trying
to compare here the planning time taken by DP vs GEQO vs GOO or the
quality of the plans generated by different join ordering algorithms
or both? All pgbench queries are single table scans and there is no
involvement of the join search, so I am not sure how we can justify
these gains?
Just to clarify: as noted in the cover mail, the numbers are not from
default pgbench queries, but from the star-join / snowflake workloads in
thread [1]Star/snowflake join thread and benchmarks: /messages/by-id/a22ec6e0-92ae-43e7-85c1-587df2a65f51@vondra.me, using the benchmark included in the v5-0001 patch. These
workloads contain multi-table joins and do trigger join search; you can
reproduce them by configuring the GUCs as described in the cover mail.
The benchmark tables contain no data, so execution time is negligible;
the results mainly reflect planning time of the different join-ordering
methods, which is intentional for this microbenchmark.
A broader evaluation on TPC-H / TPC-DS / JOB is TODO, covering both
planning time and plan quality. That should provide a more
representative picture of GOO, beyond this synthetic setup.
References:
[1]: Star/snowflake join thread and benchmarks: /messages/by-id/a22ec6e0-92ae-43e7-85c1-587df2a65f51@vondra.me
/messages/by-id/a22ec6e0-92ae-43e7-85c1-587df2a65f51@vondra.me
--
Best regards,
Chengpeng Yan
On 12/2/25 04:48, Chengpeng Yan wrote:
Hi hackers,
This patch implements GOO (Greedy Operator Ordering), a greedy
join-order search method for large join problems, based on Fegaras (DEXA
’98) [1]. The algorithm repeatedly selects, among all legal joins, the
join pair with the lowest estimated total cost, merges them, and
continues until a single join remains. Patch attached.To get an initial sense of performance, I reused the star join /
snowflake examples and the testing script from the thread in [2]. The
star-join GUC in that SQL workload was replaced with
`enable_goo_join_search`, so the same tests can run under DP (standard
dynamic programming) / GEQO(Genetic Query Optimizer) / GOO. For these
tests, geqo_threshold was set to 15 for DP, and to 5 for both GEQO and
GOO. Other planner settings, including join_collapse_limit, remained at
their defaults.On my local machine, a single-client pgbench run produces the following
throughput (tps):| DP | GEQO | GOO
--------------------+----------+----------+-----------
starjoin (inner) | 1762.52 | 192.13 | 6168.89
starjoin (outer) | 1683.92 | 173.90 | 5626.56
snowflake (inner) | 1829.04 | 133.40 | 3929.57
snowflake (outer) | 1397.93 | 99.65 | 3040.52
Seems interesting, and also much more ambitious than what I intended to
do in the starjoin thread (which is meant to be just a simplistic
heuristics on top of the regular join order planning).
I think a much broader evaluation will be needed, comparing not just the
planning time, but also the quality of the final plan. Which for the
starjoin tests does not really matter, as the plans are all equal in
this regard.
regards
--
Tomas Vondra
Hi,
On Dec 2, 2025, at 18:56, Tomas Vondra <tomas@vondra.me> wrote:
I think a much broader evaluation will be needed, comparing not just the
planning time, but also the quality of the final plan. Which for the
starjoin tests does not really matter, as the plans are all equal in
this regard.
Many thanks for your feedback.
You are absolutely right — plan quality is also very important. In my
initial email I only showed the improvements in planning time, but did
not provide results regarding plan quality. I will run tests on more
complex join scenarios, evaluating both planning time and plan quality.
Thanks again!
--
Best regards,
Chengpeng Yan
On 12/2/25 14:04, Chengpeng Yan wrote:
Hi,
On Dec 2, 2025, at 18:56, Tomas Vondra <tomas@vondra.me> wrote:
I think a much broader evaluation will be needed, comparing not just the
planning time, but also the quality of the final plan. Which for the
starjoin tests does not really matter, as the plans are all equal in
this regard.Many thanks for your feedback.
You are absolutely right — plan quality is also very important. In my
initial email I only showed the improvements in planning time, but did
not provide results regarding plan quality. I will run tests on more
complex join scenarios, evaluating both planning time and plan quality.
I was trying to do some simple experiments by comparing plans for TPC-DS
queries, but unfortunately I get a lot of crashes with the patch. All
the backtraces look very similar - see the attached example. The root
cause seems to be that sort_inner_and_outer() sees
inner_path = NULL
I haven't investigated this very much, but I suppose the GOO code should
be calling set_cheapest() from somewhere.
regards
--
Tomas Vondra
Attachments:
On 12/9/25 20:20, Tomas Vondra wrote:
On 12/2/25 14:04, Chengpeng Yan wrote:
Hi,
On Dec 2, 2025, at 18:56, Tomas Vondra <tomas@vondra.me> wrote:
I think a much broader evaluation will be needed, comparing not just the
planning time, but also the quality of the final plan. Which for the
starjoin tests does not really matter, as the plans are all equal in
this regard.Many thanks for your feedback.
You are absolutely right — plan quality is also very important. In my
initial email I only showed the improvements in planning time, but did
not provide results regarding plan quality. I will run tests on more
complex join scenarios, evaluating both planning time and plan quality.I was trying to do some simple experiments by comparing plans for TPC-DS
queries, but unfortunately I get a lot of crashes with the patch. All
the backtraces look very similar - see the attached example. The root
cause seems to be that sort_inner_and_outer() seesinner_path = NULL
I haven't investigated this very much, but I suppose the GOO code should
be calling set_cheapest() from somewhere.
FWIW after looking at the failing queries for a bit, and a bit of
tweaking, it seems the issue is about aggregates in the select list. For
example this TPC-DS query fails (Q7):
select i_item_id,
avg(ss_quantity) agg1,
avg(ss_list_price) agg2,
avg(ss_coupon_amt) agg3,
avg(ss_sales_price) agg4
from store_sales, customer_demographics, date_dim, item, promotion
where ss_sold_date_sk = d_date_sk and
ss_item_sk = i_item_sk and
ss_cdemo_sk = cd_demo_sk and
ss_promo_sk = p_promo_sk and
cd_gender = 'F' and
cd_marital_status = 'W' and
cd_education_status = 'Primary' and
(p_channel_email = 'N' or p_channel_event = 'N') and
d_year = 1998
group by i_item_id
order by i_item_id
LIMIT 100;
but if I remove the aggregates, it plans just fine:
select i_item_id
from store_sales, customer_demographics, date_dim, item, promotion
where ss_sold_date_sk = d_date_sk and
ss_item_sk = i_item_sk and
ss_cdemo_sk = cd_demo_sk and
ss_promo_sk = p_promo_sk and
cd_gender = 'F' and
cd_marital_status = 'W' and
cd_education_status = 'Primary' and
(p_channel_email = 'N' or p_channel_event = 'N') and
d_year = 1998
group by i_item_id
order by i_item_id
LIMIT 100;
The backtrace matches the one I already posted, I'm not going to post
that again.
I looked at a couple more failing queries, and removing the aggregates
fixes them too. Maybe there are other issues/crashes, of course.
regards
--
Tomas Vondra
Hi,
On Dec 10, 2025, at 07:30, Tomas Vondra <tomas@vondra.me> wrote:
I looked at a couple more failing queries, and removing the aggregates
fixes them too. Maybe there are other issues/crashes, of course.
Thanks a lot for pointing this out. I also noticed the same issue when
testing TPC-H Q5. The root cause was that in the goo algorithm I forgot
to handle the case of eager aggregation. This has been fixed in the v2
patch (after the fix, the v2 version works correctly for all TPC-H
queries). I will continue testing it on TPC-DS as well.
Sorry that I didn’t push the related changes earlier. I was running more
experiments on the greedy strategy, and I still needed some time to
organize and analyze the results. During this process, I found that the
current greedy strategy may lead to suboptimal plan quality in some
cases. Because of that, I plan to first evaluate a few basic greedy
heuristics on TPC-H to understand their behavior and limitations. If
there are meaningful results or conclusions, I will share them for
discussion.
Based on some preliminary testing, I’m leaning toward keeping the greedy
strategy simple and explainable, and focusing on the following
indicators together with the planner’s cost estimates:
* join cardinality (number of output rows)
* selectivity (join_size / (left_size * right_size))
* estimated result size in bytes(joinrel->reltarget->width * joinrel->rows)
* cheapest total path cost (cheapest_total_path->total_cost)
At the moment, I’m inclined to prioritize join cardinality with input
size as a secondary factor, but I’d like to validate this step by step:
first by testing these simple heuristics on TPC-H (as a relatively
simple workload) and summarizing some initial conclusions there. After
that, I plan to run more comprehensive experiments on more complex
benchmarks such as JOB and TPC-DS and report the results.
Do you have any thoughts or suggestions on this direction?
Thanks again for your feedback and help.
--
Best regards,
Chengpeng Yan
Attachments:
v2-0001-Add-GOO-Greedy-Operator-Ordering-join-search-as-a.patchapplication/octet-stream; name=v2-0001-Add-GOO-Greedy-Operator-Ordering-join-search-as-a.patchDownload
From 79c4d3fa7d83a24b3937ed2e4d5568bcb949e820 Mon Sep 17 00:00:00 2001
From: Chengpeng Yan <chengpeng_yan@outlook.com>
Date: Wed, 10 Dec 2025 12:52:17 +0800
Subject: [PATCH v2] Add GOO (Greedy Operator Ordering) join search as an
alternative to GEQO
Introduce a greedy join search algorithm (GOO) to handle
large join problems. GOO builds join relations iteratively, maintaining
a list of clumps (join components) and committing to the cheapest
legal join at each step until only one clump remains.
Signed-off-by: Chengpeng Yan <chengpeng_yan@outlook.com>
---
src/backend/optimizer/path/Makefile | 1 +
src/backend/optimizer/path/allpaths.c | 4 +
src/backend/optimizer/path/goo.c | 612 +++++++++++++++
src/backend/optimizer/path/meson.build | 1 +
src/backend/utils/misc/guc_parameters.dat | 9 +
src/backend/utils/misc/postgresql.conf.sample | 1 +
src/include/optimizer/goo.h | 23 +
src/include/optimizer/paths.h | 1 +
src/test/regress/expected/goo.out | 700 ++++++++++++++++++
src/test/regress/expected/sysviews.out | 3 +-
src/test/regress/parallel_schedule | 9 +-
src/test/regress/sql/goo.sql | 364 +++++++++
12 files changed, 1724 insertions(+), 4 deletions(-)
create mode 100644 src/backend/optimizer/path/goo.c
create mode 100644 src/include/optimizer/goo.h
create mode 100644 src/test/regress/expected/goo.out
create mode 100644 src/test/regress/sql/goo.sql
diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile
index 1e199ff66f7..3bc825cd845 100644
--- a/src/backend/optimizer/path/Makefile
+++ b/src/backend/optimizer/path/Makefile
@@ -17,6 +17,7 @@ OBJS = \
clausesel.o \
costsize.o \
equivclass.o \
+ goo.o \
indxpath.o \
joinpath.o \
joinrels.o \
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 4c43fd0b19b..4574b1f44cc 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -35,6 +35,7 @@
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/geqo.h"
+#include "optimizer/goo.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
@@ -3845,6 +3846,9 @@ make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
if (join_search_hook)
return (*join_search_hook) (root, levels_needed, initial_rels);
+ /* WIP: for now use geqo_threshold for testing */
+ else if (enable_goo_join_search && levels_needed >= geqo_threshold)
+ return goo_join_search(root, levels_needed, initial_rels);
else if (enable_geqo && levels_needed >= geqo_threshold)
return geqo(root, levels_needed, initial_rels);
else
diff --git a/src/backend/optimizer/path/goo.c b/src/backend/optimizer/path/goo.c
new file mode 100644
index 00000000000..247dbb5f921
--- /dev/null
+++ b/src/backend/optimizer/path/goo.c
@@ -0,0 +1,612 @@
+/*-------------------------------------------------------------------------
+ *
+ * goo.c
+ * Greedy operator ordering (GOO) join search for large join problems
+ *
+ * GOO is a deterministic greedy operator ordering algorithm that constructs
+ * join relations iteratively, always committing to the cheapest legal join at
+ * each step. The algorithm maintains a list of "clumps" (join components),
+ * initially one per base relation. At each iteration, it evaluates all legal
+ * pairs of clumps, selects the pair that produces the cheapest join according
+ * to the planner's cost model, and replaces those two clumps with the
+ * resulting joinrel. This continues until only one clump remains.
+ *
+ * ALGORITHM COMPLEXITY:
+ *
+ * Time Complexity: O(n^3) where n is the number of base relations.
+ * - The algorithm performs (n - 1) iterations, merging two clumps each time.
+ * - At iteration i, there are (n - i + 1) remaining clumps, requiring
+ * O((n-i)^2) pair evaluations to find the cheapest join.
+ * - Total: Sum of (n-i)^2 for i=1 to n-1 ≈ O(n^3)
+ *
+ * REFERENCES:
+ *
+ * This implementation is based on the algorithm described in:
+ *
+ * Leonidas Fegaras, "A New Heuristic for Optimizing Large Queries",
+ * Proceedings of the 9th International Conference on Database and Expert
+ * Systems Applications (DEXA '98), August 1998, Pages 726-735.
+ * https://dl.acm.org/doi/10.5555/648311.754892
+ *
+ *
+ * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * IDENTIFICATION
+ * src/backend/optimizer/path/goo.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include "miscadmin.h"
+#include "nodes/bitmapset.h"
+#include "nodes/pathnodes.h"
+#include "optimizer/geqo.h"
+#include "optimizer/goo.h"
+#include "optimizer/joininfo.h"
+#include "optimizer/pathnode.h"
+#include "optimizer/paths.h"
+#include "utils/hsearch.h"
+#include "utils/memutils.h"
+
+/*
+ * Configuration defaults. These are exposed as GUCs in guc_tables.c.
+ */
+bool enable_goo_join_search = false;
+
+/*
+ * Working state for a single GOO search invocation.
+ *
+ * This structure holds all the state needed during a greedy join order search.
+ * It manages three memory contexts with different lifetimes to avoid memory
+ * bloat during large join searches.
+ *
+ * TODO: Consider using the extension_state mechanism in PlannerInfo (similar
+ * to GEQO's approach) instead of passing GooState separately.
+ */
+typedef struct GooState
+{
+ PlannerInfo *root; /* global planner state */
+ MemoryContext goo_cxt; /* long-lived (per-search) allocations */
+ MemoryContext cand_cxt; /* per-iteration candidate storage */
+ MemoryContext scratch_cxt; /* per-candidate speculative evaluation */
+ List *clumps; /* remaining join components (RelOptInfo *) */
+
+ /*
+ * "clumps" are similar to GEQO's concept (see geqo_eval.c): join
+ * components that haven't been merged yet. Initially one per base
+ * relation, gradually merged until one remains.
+ */
+ bool clause_pair_present; /* any clause-connected pair exists? */
+} GooState;
+
+/*
+ * Candidate join between two clumps.
+ *
+ * This structure holds the greedy metrics from a speculative joinrel
+ * evaluation. We create this lightweight structure in cand_cxt after discarding
+ * the actual joinrel from scratch_cxt, allowing us to compare many candidates
+ * without exhausting memory.
+ */
+typedef struct GooCandidate
+{
+ RelOptInfo *left; /* left input clump */
+ RelOptInfo *right; /* right input clump */
+ Cost total_cost; /* total cost of cheapest path */
+} GooCandidate;
+
+static GooState * goo_init_state(PlannerInfo *root, List *initial_rels);
+static void goo_destroy_state(GooState * state);
+static RelOptInfo *goo_search_internal(GooState * state);
+static void goo_reset_probe_state(GooState * state, int saved_rel_len,
+ struct HTAB *saved_hash);
+static GooCandidate * goo_build_candidate(GooState * state, RelOptInfo *left,
+ RelOptInfo *right);
+static RelOptInfo *goo_commit_join(GooState * state, GooCandidate * cand);
+static bool goo_candidate_better(GooCandidate * a, GooCandidate * b);
+static bool goo_candidate_prunable(GooState * state, RelOptInfo *left,
+ RelOptInfo *right);
+
+/*
+ * goo_join_search
+ * Entry point for Greedy Operator Ordering join search algorithm.
+ *
+ * This function is called from make_rel_from_joinlist() when
+ * enable_goo_join_search is true and the number of relations meets or
+ * exceeds geqo_threshold.
+ *
+ * Returns the final RelOptInfo representing the join of all base relations,
+ * or errors out if no valid join order can be found.
+ */
+RelOptInfo *
+goo_join_search(PlannerInfo *root, int levels_needed,
+ List *initial_rels)
+{
+ GooState *state;
+ RelOptInfo *result;
+ int base_rel_count;
+ struct HTAB *base_hash;
+
+ /* Initialize search state and memory contexts */
+ state = goo_init_state(root, initial_rels);
+
+ /*
+ * Save initial state of join_rel_list and join_rel_hash so we can restore
+ * them if the search fails.
+ */
+ base_rel_count = list_length(root->join_rel_list);
+ base_hash = root->join_rel_hash;
+
+ /* Run the main greedy search loop */
+ result = goo_search_internal(state);
+
+ if (result == NULL)
+ {
+ /* Restore planner state before reporting error */
+ root->join_rel_list = list_truncate(root->join_rel_list, base_rel_count);
+ root->join_rel_hash = base_hash;
+ elog(ERROR, "GOO join search failed to find a valid join order");
+ }
+
+ goo_destroy_state(state);
+ return result;
+}
+
+/*
+ * goo_init_state
+ * Initialize per-search state and memory contexts.
+ *
+ * Creates the GooState structure and three memory contexts with different
+ * lifetimes:
+ *
+ * - goo_cxt: Lives for the entire search, holds the clumps list and state.
+ * - cand_cxt: Reset after each iteration, holds candidate structures during
+ * the comparison phase.
+ * - scratch_cxt: Reset after each candidate evaluation, holds speculative
+ * joinrels that are discarded before committing to a choice.
+ *
+ * The three-context design prevents memory bloat during large join searches
+ * where we may evaluate hundreds or thousands of candidate joins.
+ */
+static GooState * goo_init_state(PlannerInfo *root, List *initial_rels)
+{
+ MemoryContext oldcxt;
+ GooState *state;
+
+ oldcxt = MemoryContextSwitchTo(root->planner_cxt);
+
+ state = palloc(sizeof(GooState));
+ state->root = root;
+ state->clumps = NIL;
+ state->clause_pair_present = false;
+
+ /* Create the three-level memory context hierarchy */
+ state->goo_cxt = AllocSetContextCreate(root->planner_cxt, "GOOStateContext",
+ ALLOCSET_DEFAULT_SIZES);
+ state->cand_cxt = AllocSetContextCreate(state->goo_cxt, "GOOCandidateContext",
+ ALLOCSET_SMALL_SIZES);
+ state->scratch_cxt = AllocSetContextCreate(
+ state->goo_cxt, "GOOScratchContext", ALLOCSET_SMALL_SIZES);
+
+ /*
+ * Copy the initial_rels list into goo_cxt. This becomes our working
+ * clumps list that we'll modify throughout the search.
+ */
+ MemoryContextSwitchTo(state->goo_cxt);
+ state->clumps = list_copy(initial_rels);
+
+ MemoryContextSwitchTo(oldcxt);
+
+ return state;
+}
+
+/*
+ * goo_destroy_state
+ * Free all memory allocated for the GOO search.
+ *
+ * Deletes the goo_cxt memory context (which recursively deletes cand_cxt
+ * and scratch_cxt as children) and then frees the state structure itself.
+ * This is called after the search completes successfully or fails.
+ */
+static void
+goo_destroy_state(GooState * state)
+{
+ MemoryContextDelete(state->goo_cxt);
+ pfree(state);
+}
+
+/*
+ * goo_search_internal
+ * Main greedy search loop.
+ *
+ * Implements a two-pass algorithm at each iteration:
+ *
+ * Pass 1: Scan all clump pairs to detect whether any clause-connected pairs
+ * exist. This sets the clause_pair_present flag.
+ *
+ * Pass 2: Evaluate all viable candidate pairs, keeping track of the best one
+ * according to our comparison criteria. If clause_pair_present is true,
+ * we skip Cartesian products entirely to avoid expensive cross joins.
+ *
+ * After selecting the best candidate, we permanently create its joinrel in
+ * planner_cxt and replace the two input clumps with this new joinrel. This
+ * continues until only one clump remains.
+ *
+ * The function runs primarily in goo_cxt, temporarily switching to planner_cxt
+ * when creating permanent joinrels and to scratch_cxt when evaluating
+ * speculative candidates.
+ *
+ * Returns the final joinrel spanning all base relations, or NULL on failure.
+ */
+static RelOptInfo *
+goo_search_internal(GooState * state)
+{
+ PlannerInfo *root = state->root;
+ RelOptInfo *final_rel = NULL;
+ MemoryContext oldcxt;
+
+ /*
+ * Switch to goo_cxt for the entire search process. This ensures that all
+ * operations on state->clumps and related structures happen in the
+ * correct memory context.
+ */
+ oldcxt = MemoryContextSwitchTo(state->goo_cxt);
+
+ while (list_length(state->clumps) > 1)
+ {
+ ListCell *lc1;
+ int i;
+ GooCandidate *best_candidate = NULL;
+
+ /* Allow query cancellation during long join searches */
+ CHECK_FOR_INTERRUPTS();
+
+ /* Reset candidate context for this iteration */
+ MemoryContextReset(state->cand_cxt);
+ state->clause_pair_present = false;
+
+ /*
+ * Pass 1: Scan all pairs to detect clause-connected joins.
+ *
+ * We need to know whether ANY clause-connected pairs exist before we
+ * can decide whether to skip Cartesian products. This quick scan
+ * allows us to prefer well-connected joins without completely
+ * forbidding Cartesian products (which may be necessary for
+ * disconnected query graphs).
+ */
+ for (i = 0, lc1 = list_head(state->clumps); lc1 != NULL;
+ lc1 = lnext(state->clumps, lc1), i++)
+ {
+ RelOptInfo *left = lfirst_node(RelOptInfo, lc1);
+ ListCell *lc2 = lnext(state->clumps, lc1);
+
+ for (; lc2 != NULL; lc2 = lnext(state->clumps, lc2))
+ {
+ RelOptInfo *right = lfirst_node(RelOptInfo, lc2);
+
+ /* Check if this pair has a join clause or order restriction */
+ if (have_relevant_joinclause(root, left, right) ||
+ have_join_order_restriction(root, left, right))
+ {
+ /* Found at least one clause-connected pair */
+ state->clause_pair_present = true;
+ break;
+ }
+ }
+
+ if (state->clause_pair_present)
+ break;
+ }
+
+ /*
+ * Pass 2: Evaluate all viable candidate pairs and select the best.
+ *
+ * For each pair that passes the pruning check, we do a full
+ * speculative evaluation using make_join_rel() to get accurate costs.
+ * The candidate with the best cost (according to
+ * goo_candidate_better) is remembered and will be committed after
+ * this pass.
+ *
+ * TODO: It might be worth caching cost estimates if the same join
+ * pair appears in multiple iterations.
+ */
+ for (lc1 = list_head(state->clumps); lc1 != NULL;
+ lc1 = lnext(state->clumps, lc1))
+ {
+ RelOptInfo *left = lfirst_node(RelOptInfo, lc1);
+ ListCell *lc2 = lnext(state->clumps, lc1);
+
+ for (; lc2 != NULL; lc2 = lnext(state->clumps, lc2))
+ {
+ RelOptInfo *right = lfirst_node(RelOptInfo, lc2);
+ GooCandidate *cand;
+
+ cand = goo_build_candidate(state, left, right);
+ if (cand == NULL)
+ continue;
+
+ /* Track the best candidate seen so far */
+ if (best_candidate == NULL ||
+ goo_candidate_better(cand, best_candidate))
+ best_candidate = cand;
+ }
+ }
+
+ /* We must have at least one valid join candidate */
+ if (best_candidate == NULL)
+ elog(ERROR, "GOO join search failed to find any valid join candidates");
+
+ /*
+ * Commit the best candidate: create the joinrel permanently and
+ * update the clumps list.
+ */
+ final_rel = goo_commit_join(state, best_candidate);
+
+ if (final_rel == NULL)
+ elog(ERROR, "GOO join search failed to commit join");
+ }
+
+ /* Switch back to the original context before returning */
+ MemoryContextSwitchTo(oldcxt);
+
+ return final_rel;
+}
+
+/*
+ * goo_candidate_prunable
+ * Determine whether a candidate pair should be skipped.
+ *
+ * We use a two-level pruning strategy:
+ *
+ * 1. Pairs with join clauses or join-order restrictions are never prunable.
+ * These represent natural joins or required join orders (e.g., from outer
+ * joins or LATERAL references).
+ *
+ * 2. If clause_pair_present is true (meaning at least one clause-connected
+ * pair exists in this iteration), we prune Cartesian products to avoid
+ * evaluating expensive cross joins when better options are available.
+ *
+ * However, if NO clause-connected pairs exist in an iteration, we allow
+ * Cartesian products to be considered. This ensures we can always make
+ * progress even with disconnected query graphs.
+ *
+ * Returns true if the pair should be pruned (skipped), false otherwise.
+ */
+static bool
+goo_candidate_prunable(GooState * state, RelOptInfo *left,
+ RelOptInfo *right)
+{
+ PlannerInfo *root = state->root;
+ bool has_clause = have_relevant_joinclause(root, left, right);
+ bool has_restriction = have_join_order_restriction(root, left, right);
+
+ if (has_clause || has_restriction)
+ return false; /* never prune clause-connected joins */
+
+ return state->clause_pair_present;
+}
+
+/*
+ * goo_build_candidate
+ * Evaluate a potential join between two clumps and return a candidate.
+ *
+ * This function performs a speculative join evaluation to extract greedy metrics
+ * without permanently creating the joinrel. The process is:
+ *
+ * 1. Check basic viability (pruning, overlapping relids).
+ * 2. Switch to scratch_cxt and create the joinrel using make_join_rel().
+ * 3. Generate paths (including partitionwise and parallel variants).
+ * 4. Extract the greedy metrics from the cheapest path.
+ * 5. Discard the joinrel by calling goo_reset_probe_state().
+ * 6. Create a lightweight GooCandidate in cand_cxt with the extracted metrics.
+ *
+ * This evaluate-and-discard pattern prevents memory bloat when evaluating
+ * many candidates. The winning candidate will be rebuilt permanently later
+ * by goo_commit_join().
+ *
+ * Returns a GooCandidate structure, or NULL if the join is illegal or
+ * overlapping. Assumes the caller is in goo_cxt.
+ */
+static GooCandidate * goo_build_candidate(GooState * state, RelOptInfo *left,
+ RelOptInfo *right)
+{
+ PlannerInfo *root = state->root;
+ MemoryContext oldcxt;
+ int saved_rel_len;
+ struct HTAB *saved_hash;
+ RelOptInfo *joinrel;
+ Cost total_cost;
+ GooCandidate *cand;
+
+ /* Skip if this pair should be pruned */
+ if (goo_candidate_prunable(state, left, right))
+ return NULL;
+
+ /* Sanity check: ensure the clumps don't overlap */
+ if (bms_overlap(left->relids, right->relids))
+ return NULL;
+
+ /*
+ * Save state before speculative join evaluation. We'll create the joinrel
+ * in scratch_cxt and then discard it.
+ */
+ saved_rel_len = list_length(root->join_rel_list);
+ saved_hash = root->join_rel_hash;
+
+ /* Switch to scratch_cxt for speculative joinrel creation */
+ oldcxt = MemoryContextSwitchTo(state->scratch_cxt);
+
+ /*
+ * Temporarily disable join_rel_hash so make_join_rel() doesn't find or
+ * cache this speculative joinrel.
+ */
+ root->join_rel_hash = NULL;
+
+ /*
+ * Create the joinrel and generate all its paths.
+ *
+ * TODO: This is the most expensive part of GOO. Each candidate evaluation
+ * performs full path generation via make_join_rel().
+ */
+ joinrel = make_join_rel(root, left, right);
+
+ if (joinrel == NULL)
+ {
+ /* Invalid or illegal join, clean up and return NULL */
+ MemoryContextSwitchTo(oldcxt);
+ goo_reset_probe_state(state, saved_rel_len, saved_hash);
+ return NULL;
+ }
+
+ bool is_top_rel = bms_equal(joinrel->relids, root->all_query_rels);
+
+ generate_partitionwise_join_paths(root, joinrel);
+ if (!is_top_rel)
+ generate_useful_gather_paths(root, joinrel, false);
+ set_cheapest(joinrel);
+
+ if (joinrel->grouped_rel != NULL && !is_top_rel)
+ {
+ RelOptInfo *grouped_rel = joinrel->grouped_rel;
+
+ Assert(IS_GROUPED_REL(grouped_rel));
+
+ generate_grouped_paths(root, grouped_rel, joinrel);
+ set_cheapest(grouped_rel);
+ }
+
+ total_cost = joinrel->cheapest_total_path->total_cost;
+
+ /*
+ * Switch back to goo_cxt and discard the speculative joinrel.
+ * goo_reset_probe_state() will clean up join_rel_list, join_rel_hash, and
+ * reset scratch_cxt to free all the joinrel's memory.
+ */
+ MemoryContextSwitchTo(oldcxt);
+ goo_reset_probe_state(state, saved_rel_len, saved_hash);
+
+ /*
+ * Now create the candidate structure in cand_cxt. This will survive until
+ * the end of this iteration (when cand_cxt is reset).
+ */
+ oldcxt = MemoryContextSwitchTo(state->cand_cxt);
+ cand = palloc(sizeof(GooCandidate));
+ cand->left = left;
+ cand->right = right;
+ cand->total_cost = total_cost;
+ MemoryContextSwitchTo(oldcxt);
+
+ return cand;
+}
+
+/*
+ * goo_reset_probe_state
+ * Clean up after a speculative joinrel evaluation.
+ *
+ * Reverts the planner's join_rel_list and join_rel_hash to their saved state,
+ * removing any joinrels that were created during speculative evaluation.
+ * Also resets scratch_cxt to free all memory used by the discarded joinrel
+ * and its paths.
+ *
+ * This function is called after extracting cost metrics from a speculative
+ * joinrel that we don't want to keep.
+ */
+static void
+goo_reset_probe_state(GooState * state, int saved_rel_len,
+ struct HTAB *saved_hash)
+{
+ PlannerInfo *root = state->root;
+
+ /* Remove speculative joinrels from the planner's lists */
+ root->join_rel_list = list_truncate(root->join_rel_list, saved_rel_len);
+ root->join_rel_hash = saved_hash;
+
+ /* Free all memory used during speculative evaluation */
+ MemoryContextReset(state->scratch_cxt);
+}
+
+/*
+ * goo_commit_join
+ * Permanently create the chosen join and update the clumps list.
+ *
+ * After selecting the best candidate in an iteration, we need to permanently
+ * create its joinrel (with all paths) and integrate it into the planner state.
+ * This function:
+ *
+ * 1. Switches to planner_cxt and creates the joinrel using make_join_rel().
+ * Unlike the speculative evaluation, this joinrel is kept permanently.
+ * 2. Generates partitionwise and parallel path variants.
+ * 3. Determines the cheapest paths.
+ * 4. Updates state->clumps by removing the two input clumps and adding the
+ * new joinrel as a single clump.
+ *
+ * The next iteration will treat this joinrel as an atomic unit that can be
+ * joined with other remaining clumps.
+ *
+ * Returns the newly created joinrel. Assumes the caller is in goo_cxt.
+ */
+static RelOptInfo *
+goo_commit_join(GooState * state, GooCandidate * cand)
+{
+ MemoryContext oldcxt;
+ PlannerInfo *root = state->root;
+ RelOptInfo *joinrel;
+
+ /*
+ * Create the joinrel permanently in planner_cxt. Unlike the speculative
+ * evaluation in goo_build_candidate(), this joinrel will be kept and
+ * added to root->join_rel_list for use by the rest of the planner.
+ */
+ oldcxt = MemoryContextSwitchTo(root->planner_cxt);
+
+ joinrel = make_join_rel(root, cand->left, cand->right);
+ if (joinrel == NULL)
+ {
+ MemoryContextSwitchTo(oldcxt);
+ elog(ERROR, "GOO join search failed to create join relation");
+ }
+
+ /* Generate additional path variants, just like standard_join_search() */
+ bool is_top_rel = bms_equal(joinrel->relids, root->all_query_rels);
+
+ generate_partitionwise_join_paths(root, joinrel);
+ if (!is_top_rel)
+ generate_useful_gather_paths(root, joinrel, false);
+ set_cheapest(joinrel);
+
+ if (joinrel->grouped_rel != NULL && !is_top_rel)
+ {
+ RelOptInfo *grouped_rel = joinrel->grouped_rel;
+
+ Assert(IS_GROUPED_REL(grouped_rel));
+
+ generate_grouped_paths(root, grouped_rel, joinrel);
+ set_cheapest(grouped_rel);
+ }
+
+ /*
+ * Switch back to goo_cxt and update the clumps list. Remove the two input
+ * clumps and add the new joinrel as a single clump.
+ */
+ MemoryContextSwitchTo(oldcxt);
+
+ state->clumps = list_delete_ptr(state->clumps, cand->left);
+ state->clumps = list_delete_ptr(state->clumps, cand->right);
+ state->clumps = lappend(state->clumps, joinrel);
+
+ return joinrel;
+}
+
+/*
+ * goo_candidate_better
+ * Compare two join candidates and determine which is better.
+ *
+ * Returns true if candidate 'a' should be preferred over candidate 'b'.
+ */
+static bool
+goo_candidate_better(GooCandidate * a, GooCandidate * b)
+{
+ return (a->total_cost < b->total_cost);
+}
diff --git a/src/backend/optimizer/path/meson.build b/src/backend/optimizer/path/meson.build
index 12f36d85cb6..e5046365a37 100644
--- a/src/backend/optimizer/path/meson.build
+++ b/src/backend/optimizer/path/meson.build
@@ -5,6 +5,7 @@ backend_sources += files(
'clausesel.c',
'costsize.c',
'equivclass.c',
+ 'goo.c',
'indxpath.c',
'joinpath.c',
'joinrels.c',
diff --git a/src/backend/utils/misc/guc_parameters.dat b/src/backend/utils/misc/guc_parameters.dat
index 3b9d8349078..a8ce31ab8a7 100644
--- a/src/backend/utils/misc/guc_parameters.dat
+++ b/src/backend/utils/misc/guc_parameters.dat
@@ -840,6 +840,15 @@
boot_val => 'true',
},
+/* WIP: for now keep this in QUERY_TUNING_GEQO group for testing convenience */
+{ name => 'enable_goo_join_search', type => 'bool', context => 'PGC_USERSET', group => 'QUERY_TUNING_GEQO',
+ short_desc => 'Enables the planner\'s use of GOO join search for large join problems.',
+ long_desc => 'Greedy Operator Ordering (GOO) is a deterministic join search algorithm for queries with many relations.',
+ flags => 'GUC_EXPLAIN',
+ variable => 'enable_goo_join_search',
+ boot_val => 'false',
+},
+
{ name => 'enable_group_by_reordering', type => 'bool', context => 'PGC_USERSET', group => 'QUERY_TUNING_METHOD',
short_desc => 'Enables reordering of GROUP BY keys.',
flags => 'GUC_EXPLAIN',
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index dc9e2255f8a..8284e8b1da7 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -456,6 +456,7 @@
# - Genetic Query Optimizer -
#geqo = on
+#enable_goo_join_search = off
#geqo_threshold = 12
#geqo_effort = 5 # range 1-10
#geqo_pool_size = 0 # selects default based on effort
diff --git a/src/include/optimizer/goo.h b/src/include/optimizer/goo.h
new file mode 100644
index 00000000000..0080dfa2ac8
--- /dev/null
+++ b/src/include/optimizer/goo.h
@@ -0,0 +1,23 @@
+/*-------------------------------------------------------------------------
+ *
+ * goo.h
+ * prototype for the greedy operator ordering join search
+ *
+ * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * IDENTIFICATION
+ * src/include/optimizer/goo.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef GOO_H
+#define GOO_H
+
+#include "nodes/pathnodes.h"
+#include "nodes/pg_list.h"
+
+extern RelOptInfo *goo_join_search(PlannerInfo *root, int levels_needed,
+ List *initial_rels);
+
+#endif /* GOO_H */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index f6a62df0b43..5b3ebe5f1d2 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -21,6 +21,7 @@
* allpaths.c
*/
extern PGDLLIMPORT bool enable_geqo;
+extern PGDLLIMPORT bool enable_goo_join_search;
extern PGDLLIMPORT bool enable_eager_aggregate;
extern PGDLLIMPORT int geqo_threshold;
extern PGDLLIMPORT double min_eager_agg_group_size;
diff --git a/src/test/regress/expected/goo.out b/src/test/regress/expected/goo.out
new file mode 100644
index 00000000000..0b41634c968
--- /dev/null
+++ b/src/test/regress/expected/goo.out
@@ -0,0 +1,700 @@
+--
+-- GOO (Greedy Operator Ordering) Join Search Tests
+--
+-- This test suite validates the GOO join ordering algorithm and verifies
+-- correct behavior for various query patterns.
+--
+-- Create test tables with various sizes and join patterns
+CREATE TEMP TABLE t1 (a int, b int);
+CREATE TEMP TABLE t2 (a int, c int);
+CREATE TEMP TABLE t3 (b int, d int);
+CREATE TEMP TABLE t4 (c int, e int);
+CREATE TEMP TABLE t5 (d int, f int);
+CREATE TEMP TABLE t6 (e int, g int);
+CREATE TEMP TABLE t7 (f int, h int);
+CREATE TEMP TABLE t8 (g int, i int);
+CREATE TEMP TABLE t9 (h int, j int);
+CREATE TEMP TABLE t10 (i int, k int);
+CREATE TEMP TABLE t11 (j int, l int);
+CREATE TEMP TABLE t12 (k int, m int);
+CREATE TEMP TABLE t13 (l int, n int);
+CREATE TEMP TABLE t14 (m int, o int);
+CREATE TEMP TABLE t15 (n int, p int);
+CREATE TEMP TABLE t16 (o int, q int);
+CREATE TEMP TABLE t17 (p int, r int);
+CREATE TEMP TABLE t18 (q int, s int);
+-- Populate with small amount of data
+INSERT INTO t1 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t2 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t3 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t4 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t5 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t6 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t7 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t8 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t9 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t10 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t11 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t12 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t13 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t14 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t15 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t16 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t17 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t18 SELECT i, i FROM generate_series(1,10) i;
+ANALYZE;
+--
+-- Basic 3-way join (sanity check)
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 2;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM (VALUES (1),(2)) AS a(x)
+JOIN (VALUES (1),(2)) AS b(x) USING (x)
+JOIN (VALUES (1),(3)) AS c(x) USING (x);
+ QUERY PLAN
+----------------------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: ("*VALUES*".column1 = "*VALUES*_2".column1)
+ -> Hash Join
+ Hash Cond: ("*VALUES*".column1 = "*VALUES*_1".column1)
+ -> Values Scan on "*VALUES*"
+ -> Hash
+ -> Values Scan on "*VALUES*_1"
+ -> Hash
+ -> Values Scan on "*VALUES*_2"
+(10 rows)
+
+SELECT count(*)
+FROM (VALUES (1),(2)) AS a(x)
+JOIN (VALUES (1),(2)) AS b(x) USING (x)
+JOIN (VALUES (1),(3)) AS c(x) USING (x);
+ count
+-------
+ 1
+(1 row)
+
+--
+-- Disconnected graph (Cartesian products required)
+--
+-- This tests GOO's ability to handle queries where some relations
+-- have no join clauses connecting them. GOO should allow Cartesian
+-- products when no clause-connected joins are available.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2, t5
+WHERE t1.a = 1 AND t2.c = 2 AND t5.f = 3;
+ QUERY PLAN
+-------------------------------------
+ Aggregate
+ -> Nested Loop
+ -> Seq Scan on t5
+ Filter: (f = 3)
+ -> Nested Loop
+ -> Seq Scan on t1
+ Filter: (a = 1)
+ -> Seq Scan on t2
+ Filter: (c = 2)
+(9 rows)
+
+SELECT count(*)
+FROM t1, t2, t5
+WHERE t1.a = 1 AND t2.c = 2 AND t5.f = 3;
+ count
+-------
+ 1
+(1 row)
+
+--
+-- Star schema (fact table with multiple dimension tables)
+--
+-- Test GOO with a typical star schema join pattern.
+--
+CREATE TEMP TABLE fact (id int, dim1_id int, dim2_id int, dim3_id int, dim4_id int, value int);
+CREATE TEMP TABLE dim1 (id int, name text);
+CREATE TEMP TABLE dim2 (id int, name text);
+CREATE TEMP TABLE dim3 (id int, name text);
+CREATE TEMP TABLE dim4 (id int, name text);
+INSERT INTO fact SELECT i, i, i, i, i, i FROM generate_series(1,100) i;
+INSERT INTO dim1 SELECT i, 'dim1_'||i FROM generate_series(1,10) i;
+INSERT INTO dim2 SELECT i, 'dim2_'||i FROM generate_series(1,10) i;
+INSERT INTO dim3 SELECT i, 'dim3_'||i FROM generate_series(1,10) i;
+INSERT INTO dim4 SELECT i, 'dim4_'||i FROM generate_series(1,10) i;
+ANALYZE;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM fact
+JOIN dim1 ON fact.dim1_id = dim1.id
+JOIN dim2 ON fact.dim2_id = dim2.id
+JOIN dim3 ON fact.dim3_id = dim3.id
+JOIN dim4 ON fact.dim4_id = dim4.id
+WHERE dim1.id < 5;
+ QUERY PLAN
+---------------------------------------------------------------------------
+ Aggregate
+ -> Nested Loop
+ Join Filter: (fact.dim4_id = dim4.id)
+ -> Hash Join
+ Hash Cond: (dim3.id = fact.dim3_id)
+ -> Seq Scan on dim3
+ -> Hash
+ -> Hash Join
+ Hash Cond: (dim2.id = fact.dim2_id)
+ -> Seq Scan on dim2
+ -> Hash
+ -> Hash Join
+ Hash Cond: (fact.dim1_id = dim1.id)
+ -> Seq Scan on fact
+ -> Hash
+ -> Seq Scan on dim1
+ Filter: (id < 5)
+ -> Seq Scan on dim4
+(18 rows)
+
+--
+-- Long join chain
+--
+-- Tests GOO with a large join involving 15 relations.
+--
+SET geqo_threshold = 8;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n;
+ QUERY PLAN
+----------------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (t7.h = t9.h)
+ -> Hash Join
+ Hash Cond: (t8.i = t10.i)
+ -> Hash Join
+ Hash Cond: (t2.c = t4.c)
+ -> Hash Join
+ Hash Cond: (t3.b = t1.b)
+ -> Hash Join
+ Hash Cond: (t5.f = t7.f)
+ -> Hash Join
+ Hash Cond: (t3.d = t5.d)
+ -> Seq Scan on t3
+ -> Hash
+ -> Seq Scan on t5
+ -> Hash
+ -> Seq Scan on t7
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t6.g = t8.g)
+ -> Hash Join
+ Hash Cond: (t4.e = t6.e)
+ -> Seq Scan on t4
+ -> Hash
+ -> Seq Scan on t6
+ -> Hash
+ -> Seq Scan on t8
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t12.m = t14.m)
+ -> Hash Join
+ Hash Cond: (t10.k = t12.k)
+ -> Seq Scan on t10
+ -> Hash
+ -> Seq Scan on t12
+ -> Hash
+ -> Seq Scan on t14
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t11.l = t13.l)
+ -> Hash Join
+ Hash Cond: (t9.j = t11.j)
+ -> Seq Scan on t9
+ -> Hash
+ -> Seq Scan on t11
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t13.n = t15.n)
+ -> Seq Scan on t13
+ -> Hash
+ -> Seq Scan on t15
+(58 rows)
+
+-- Execute to verify correctness
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n;
+ count
+-------
+ 10
+(1 row)
+
+--
+-- Bushy tree support
+--
+-- Verify that GOO can produce bushy join trees, not just left-deep or right-deep.
+-- With appropriate cost model, GOO should join (t1,t2) and (t3,t4) first,
+-- then join those results (bushy tree).
+--
+SET geqo_threshold = 4;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2, t3, t4
+WHERE t1.a = t2.a
+ AND t3.b = t4.c
+ AND t1.a = t3.b;
+ QUERY PLAN
+----------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (t1.a = t3.b)
+ -> Hash Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t3.b = t4.c)
+ -> Seq Scan on t3
+ -> Hash
+ -> Seq Scan on t4
+(14 rows)
+
+--
+-- Compare GOO vs standard join search
+--
+-- Run the same query with GOO and standard join search to verify both
+-- produce valid plans. Results should be identical even if plans differ.
+--
+SET enable_goo_join_search = on;
+PREPARE goo_plan AS
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e;
+EXECUTE goo_plan;
+ count
+-------
+ 10
+(1 row)
+
+SET enable_goo_join_search = off;
+SET geqo_threshold = default;
+PREPARE standard_plan AS
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e;
+EXECUTE standard_plan;
+ count
+-------
+ 10
+(1 row)
+
+-- Results should match
+EXECUTE goo_plan;
+ count
+-------
+ 10
+(1 row)
+
+EXECUTE standard_plan;
+ count
+-------
+ 10
+(1 row)
+
+--
+-- Large join (18 relations)
+--
+-- Test GOO with a large number of relations.
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 10;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n
+JOIN t16 ON t14.o = t16.o
+JOIN t17 ON t15.p = t17.p
+JOIN t18 ON t16.q = t18.q;
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (t16.q = t18.q)
+ -> Hash Join
+ Hash Cond: (t15.p = t17.p)
+ -> Hash Join
+ Hash Cond: (t14.o = t16.o)
+ -> Hash Join
+ Hash Cond: (t13.n = t15.n)
+ -> Hash Join
+ Hash Cond: (t12.m = t14.m)
+ -> Hash Join
+ Hash Cond: (t11.l = t13.l)
+ -> Hash Join
+ Hash Cond: (t10.k = t12.k)
+ -> Hash Join
+ Hash Cond: (t9.j = t11.j)
+ -> Hash Join
+ Hash Cond: (t8.i = t10.i)
+ -> Hash Join
+ Hash Cond: (t7.h = t9.h)
+ -> Hash Join
+ Hash Cond: (t6.g = t8.g)
+ -> Hash Join
+ Hash Cond: (t5.f = t7.f)
+ -> Hash Join
+ Hash Cond: (t4.e = t6.e)
+ -> Hash Join
+ Hash Cond: (t3.d = t5.d)
+ -> Hash Join
+ Hash Cond: (t2.c = t4.c)
+ -> Hash Join
+ Hash Cond: (t1.b = t3.b)
+ -> Hash Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Seq Scan on t3
+ -> Hash
+ -> Seq Scan on t4
+ -> Hash
+ -> Seq Scan on t5
+ -> Hash
+ -> Seq Scan on t6
+ -> Hash
+ -> Seq Scan on t7
+ -> Hash
+ -> Seq Scan on t8
+ -> Hash
+ -> Seq Scan on t9
+ -> Hash
+ -> Seq Scan on t10
+ -> Hash
+ -> Seq Scan on t11
+ -> Hash
+ -> Seq Scan on t12
+ -> Hash
+ -> Seq Scan on t13
+ -> Hash
+ -> Seq Scan on t14
+ -> Hash
+ -> Seq Scan on t15
+ -> Hash
+ -> Seq Scan on t16
+ -> Hash
+ -> Seq Scan on t17
+ -> Hash
+ -> Seq Scan on t18
+(70 rows)
+
+--
+-- Mixed connected and disconnected components
+--
+-- Query with two connected components that need a Cartesian product between them.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a,
+ t5 JOIN t6 ON t5.f = t6.e
+WHERE t1.a < 5 AND t5.d < 3;
+ QUERY PLAN
+-------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (t2.a = t1.a)
+ -> Seq Scan on t2
+ -> Hash
+ -> Nested Loop
+ -> Hash Join
+ Hash Cond: (t6.e = t5.f)
+ -> Seq Scan on t6
+ -> Hash
+ -> Seq Scan on t5
+ Filter: (d < 3)
+ -> Seq Scan on t1
+ Filter: (a < 5)
+(14 rows)
+
+--
+-- Outer joins
+--
+-- Verify GOO handles outer joins correctly (respects join order restrictions)
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+LEFT JOIN t2 ON t1.a = t2.a
+LEFT JOIN t3 ON t2.a = t3.b
+LEFT JOIN t4 ON t3.d = t4.c;
+ QUERY PLAN
+----------------------------------------------
+ Aggregate
+ -> Hash Left Join
+ Hash Cond: (t3.d = t4.c)
+ -> Hash Left Join
+ Hash Cond: (t2.a = t3.b)
+ -> Hash Left Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Seq Scan on t3
+ -> Hash
+ -> Seq Scan on t4
+(14 rows)
+
+--
+-- Complete Cartesian products (disconnected graphs)
+--
+-- Test GOO's ability to handle queries with no join clauses at all.
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 2;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2;
+ QUERY PLAN
+----------------------------------
+ Aggregate
+ -> Nested Loop
+ -> Seq Scan on t1
+ -> Materialize
+ -> Seq Scan on t2
+(5 rows)
+
+SELECT count(*)
+FROM t1, t2;
+ count
+-------
+ 100
+(1 row)
+
+--
+-- Join order restrictions with FULL OUTER JOIN
+--
+-- FULL OUTER JOIN creates strong ordering constraints that GOO must respect
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+FULL OUTER JOIN t2 ON t1.a = t2.a
+FULL OUTER JOIN t3 ON t2.a = t3.b;
+ QUERY PLAN
+----------------------------------------
+ Aggregate
+ -> Hash Full Join
+ Hash Cond: (t2.a = t3.b)
+ -> Hash Full Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Seq Scan on t3
+(10 rows)
+
+--
+-- Self-join handling
+--
+-- Test GOO with the same table appearing multiple times. GOO must correctly
+-- handle self-joins that were not removed by Self-Join Elimination.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1 a
+JOIN t1 b ON a.a = b.a
+JOIN t2 c ON b.b = c.c;
+ QUERY PLAN
+------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (b.b = c.c)
+ -> Hash Join
+ Hash Cond: (a.a = b.a)
+ -> Seq Scan on t1 a
+ -> Hash
+ -> Seq Scan on t1 b
+ -> Hash
+ -> Seq Scan on t2 c
+(10 rows)
+
+--
+-- Complex bushy tree pattern
+--
+-- Create a query that naturally leads to bushy tree: multiple independent
+-- join chains that need to be combined
+--
+CREATE TEMP TABLE chain1a (id int, val int);
+CREATE TEMP TABLE chain1b (id int, val int);
+CREATE TEMP TABLE chain1c (id int, val int);
+CREATE TEMP TABLE chain2a (id int, val int);
+CREATE TEMP TABLE chain2b (id int, val int);
+CREATE TEMP TABLE chain2c (id int, val int);
+INSERT INTO chain1a SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain1b SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain1c SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2a SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2b SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2c SELECT i, i FROM generate_series(1,100) i;
+ANALYZE;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM chain1a
+JOIN chain1b ON chain1a.id = chain1b.id
+JOIN chain1c ON chain1b.val = chain1c.id
+JOIN chain2a ON chain1a.val = chain2a.id -- Cross-chain join
+JOIN chain2b ON chain2a.val = chain2b.id
+JOIN chain2c ON chain2b.val = chain2c.id;
+ QUERY PLAN
+-----------------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (chain1a.val = chain2a.id)
+ -> Hash Join
+ Hash Cond: (chain1b.val = chain1c.id)
+ -> Hash Join
+ Hash Cond: (chain1a.id = chain1b.id)
+ -> Seq Scan on chain1a
+ -> Hash
+ -> Seq Scan on chain1b
+ -> Hash
+ -> Seq Scan on chain1c
+ -> Hash
+ -> Hash Join
+ Hash Cond: (chain2b.val = chain2c.id)
+ -> Hash Join
+ Hash Cond: (chain2a.val = chain2b.id)
+ -> Seq Scan on chain2a
+ -> Hash
+ -> Seq Scan on chain2b
+ -> Hash
+ -> Seq Scan on chain2c
+(22 rows)
+
+--
+-- Eager aggregation with GOO join search
+-- Ensure grouped_rel handling when eager aggregation is enabled.
+--
+SET enable_eager_aggregate = on;
+SET min_eager_agg_group_size = 0;
+CREATE TEMP TABLE center_tbl (id int PRIMARY KEY);
+CREATE TEMP TABLE arm1_tbl (center_id int, payload int);
+CREATE TEMP TABLE arm2_tbl (center_id int, payload int);
+INSERT INTO center_tbl SELECT i FROM generate_series(1, 10) i;
+INSERT INTO arm1_tbl SELECT i%10 + 1, i FROM generate_series(1, 1000) i;
+INSERT INTO arm2_tbl SELECT i%10 + 1, i FROM generate_series(1, 1000) i;
+ANALYZE center_tbl;
+ANALYZE arm1_tbl;
+ANALYZE arm2_tbl;
+EXPLAIN (VERBOSE, COSTS OFF)
+SELECT c.id, count(*)
+FROM center_tbl c
+JOIN arm1_tbl a1 ON c.id = a1.center_id
+JOIN arm2_tbl a2 ON c.id = a2.center_id
+GROUP BY c.id;
+ QUERY PLAN
+----------------------------------------------------------
+ HashAggregate
+ Output: c.id, count(*)
+ Group Key: c.id
+ -> Hash Join
+ Output: c.id
+ Hash Cond: (c.id = a2.center_id)
+ -> Hash Join
+ Output: c.id, a1.center_id
+ Inner Unique: true
+ Hash Cond: (a1.center_id = c.id)
+ -> Seq Scan on pg_temp.arm1_tbl a1
+ Output: a1.center_id, a1.payload
+ -> Hash
+ Output: c.id
+ -> Seq Scan on pg_temp.center_tbl c
+ Output: c.id
+ -> Hash
+ Output: a2.center_id
+ -> Seq Scan on pg_temp.arm2_tbl a2
+ Output: a2.center_id
+(20 rows)
+
+SELECT c.id, count(*)
+FROM center_tbl c
+JOIN arm1_tbl a1 ON c.id = a1.center_id
+JOIN arm2_tbl a2 ON c.id = a2.center_id
+GROUP BY c.id;
+ id | count
+----+-------
+ 8 | 10000
+ 10 | 10000
+ 9 | 10000
+ 7 | 10000
+ 1 | 10000
+ 5 | 10000
+ 4 | 10000
+ 2 | 10000
+ 6 | 10000
+ 3 | 10000
+(10 rows)
+
+RESET min_eager_agg_group_size;
+RESET enable_eager_aggregate;
+-- Cleanup
+DEALLOCATE goo_plan;
+DEALLOCATE standard_plan;
+RESET geqo_threshold;
+RESET enable_goo_join_search;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index 3b37fafa65b..cb0c84cebff 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -153,6 +153,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_distinct_reordering | on
enable_eager_aggregate | on
enable_gathermerge | on
+ enable_goo_join_search | off
enable_group_by_reordering | on
enable_hashagg | on
enable_hashjoin | on
@@ -173,7 +174,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_seqscan | on
enable_sort | 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.
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index cc6d799bcea..14e3a475906 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -68,6 +68,12 @@ test: select_into select_distinct select_distinct_on select_implicit select_havi
# ----------
test: brin gin gist spgist privileges init_privs security_label collate matview lock replica_identity rowsecurity object_address tablesample groupingsets drop_operator password identity generated_stored join_hash
+# ----------
+# Additional JOIN ORDER tests
+# WIP: need to find an appropriate group for this test
+# ----------
+test: goo
+
# ----------
# Additional BRIN tests
# ----------
@@ -98,9 +104,6 @@ test: maintain_every
# no relation related tests can be put in this group
test: publication subscription
-# ----------
-# Another group of parallel tests
-# select_views depends on create_view
# ----------
test: select_views portals_p2 foreign_key cluster dependency guc bitmapops combocid tsearch tsdicts foreign_data window xmlmap functional_deps advisory_lock indirect_toast equivclass stats_rewrite
diff --git a/src/test/regress/sql/goo.sql b/src/test/regress/sql/goo.sql
new file mode 100644
index 00000000000..ab048d8e34e
--- /dev/null
+++ b/src/test/regress/sql/goo.sql
@@ -0,0 +1,364 @@
+--
+-- GOO (Greedy Operator Ordering) Join Search Tests
+--
+-- This test suite validates the GOO join ordering algorithm and verifies
+-- correct behavior for various query patterns.
+--
+
+-- Create test tables with various sizes and join patterns
+CREATE TEMP TABLE t1 (a int, b int);
+CREATE TEMP TABLE t2 (a int, c int);
+CREATE TEMP TABLE t3 (b int, d int);
+CREATE TEMP TABLE t4 (c int, e int);
+CREATE TEMP TABLE t5 (d int, f int);
+CREATE TEMP TABLE t6 (e int, g int);
+CREATE TEMP TABLE t7 (f int, h int);
+CREATE TEMP TABLE t8 (g int, i int);
+CREATE TEMP TABLE t9 (h int, j int);
+CREATE TEMP TABLE t10 (i int, k int);
+CREATE TEMP TABLE t11 (j int, l int);
+CREATE TEMP TABLE t12 (k int, m int);
+CREATE TEMP TABLE t13 (l int, n int);
+CREATE TEMP TABLE t14 (m int, o int);
+CREATE TEMP TABLE t15 (n int, p int);
+CREATE TEMP TABLE t16 (o int, q int);
+CREATE TEMP TABLE t17 (p int, r int);
+CREATE TEMP TABLE t18 (q int, s int);
+
+-- Populate with small amount of data
+INSERT INTO t1 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t2 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t3 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t4 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t5 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t6 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t7 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t8 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t9 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t10 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t11 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t12 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t13 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t14 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t15 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t16 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t17 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t18 SELECT i, i FROM generate_series(1,10) i;
+
+ANALYZE;
+
+--
+-- Basic 3-way join (sanity check)
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 2;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM (VALUES (1),(2)) AS a(x)
+JOIN (VALUES (1),(2)) AS b(x) USING (x)
+JOIN (VALUES (1),(3)) AS c(x) USING (x);
+
+SELECT count(*)
+FROM (VALUES (1),(2)) AS a(x)
+JOIN (VALUES (1),(2)) AS b(x) USING (x)
+JOIN (VALUES (1),(3)) AS c(x) USING (x);
+
+--
+-- Disconnected graph (Cartesian products required)
+--
+-- This tests GOO's ability to handle queries where some relations
+-- have no join clauses connecting them. GOO should allow Cartesian
+-- products when no clause-connected joins are available.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2, t5
+WHERE t1.a = 1 AND t2.c = 2 AND t5.f = 3;
+
+SELECT count(*)
+FROM t1, t2, t5
+WHERE t1.a = 1 AND t2.c = 2 AND t5.f = 3;
+
+--
+-- Star schema (fact table with multiple dimension tables)
+--
+-- Test GOO with a typical star schema join pattern.
+--
+CREATE TEMP TABLE fact (id int, dim1_id int, dim2_id int, dim3_id int, dim4_id int, value int);
+CREATE TEMP TABLE dim1 (id int, name text);
+CREATE TEMP TABLE dim2 (id int, name text);
+CREATE TEMP TABLE dim3 (id int, name text);
+CREATE TEMP TABLE dim4 (id int, name text);
+
+INSERT INTO fact SELECT i, i, i, i, i, i FROM generate_series(1,100) i;
+INSERT INTO dim1 SELECT i, 'dim1_'||i FROM generate_series(1,10) i;
+INSERT INTO dim2 SELECT i, 'dim2_'||i FROM generate_series(1,10) i;
+INSERT INTO dim3 SELECT i, 'dim3_'||i FROM generate_series(1,10) i;
+INSERT INTO dim4 SELECT i, 'dim4_'||i FROM generate_series(1,10) i;
+
+ANALYZE;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM fact
+JOIN dim1 ON fact.dim1_id = dim1.id
+JOIN dim2 ON fact.dim2_id = dim2.id
+JOIN dim3 ON fact.dim3_id = dim3.id
+JOIN dim4 ON fact.dim4_id = dim4.id
+WHERE dim1.id < 5;
+
+--
+-- Long join chain
+--
+-- Tests GOO with a large join involving 15 relations.
+--
+SET geqo_threshold = 8;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n;
+
+-- Execute to verify correctness
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n;
+
+--
+-- Bushy tree support
+--
+-- Verify that GOO can produce bushy join trees, not just left-deep or right-deep.
+-- With appropriate cost model, GOO should join (t1,t2) and (t3,t4) first,
+-- then join those results (bushy tree).
+--
+SET geqo_threshold = 4;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2, t3, t4
+WHERE t1.a = t2.a
+ AND t3.b = t4.c
+ AND t1.a = t3.b;
+
+--
+-- Compare GOO vs standard join search
+--
+-- Run the same query with GOO and standard join search to verify both
+-- produce valid plans. Results should be identical even if plans differ.
+--
+SET enable_goo_join_search = on;
+PREPARE goo_plan AS
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e;
+
+EXECUTE goo_plan;
+
+SET enable_goo_join_search = off;
+SET geqo_threshold = default;
+PREPARE standard_plan AS
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e;
+
+EXECUTE standard_plan;
+
+-- Results should match
+EXECUTE goo_plan;
+EXECUTE standard_plan;
+
+--
+-- Large join (18 relations)
+--
+-- Test GOO with a large number of relations.
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 10;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n
+JOIN t16 ON t14.o = t16.o
+JOIN t17 ON t15.p = t17.p
+JOIN t18 ON t16.q = t18.q;
+
+--
+-- Mixed connected and disconnected components
+--
+-- Query with two connected components that need a Cartesian product between them.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a,
+ t5 JOIN t6 ON t5.f = t6.e
+WHERE t1.a < 5 AND t5.d < 3;
+
+--
+-- Outer joins
+--
+-- Verify GOO handles outer joins correctly (respects join order restrictions)
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+LEFT JOIN t2 ON t1.a = t2.a
+LEFT JOIN t3 ON t2.a = t3.b
+LEFT JOIN t4 ON t3.d = t4.c;
+
+--
+-- Complete Cartesian products (disconnected graphs)
+--
+-- Test GOO's ability to handle queries with no join clauses at all.
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 2;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2;
+
+SELECT count(*)
+FROM t1, t2;
+
+--
+-- Join order restrictions with FULL OUTER JOIN
+--
+-- FULL OUTER JOIN creates strong ordering constraints that GOO must respect
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+FULL OUTER JOIN t2 ON t1.a = t2.a
+FULL OUTER JOIN t3 ON t2.a = t3.b;
+
+--
+-- Self-join handling
+--
+-- Test GOO with the same table appearing multiple times. GOO must correctly
+-- handle self-joins that were not removed by Self-Join Elimination.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1 a
+JOIN t1 b ON a.a = b.a
+JOIN t2 c ON b.b = c.c;
+
+--
+-- Complex bushy tree pattern
+--
+-- Create a query that naturally leads to bushy tree: multiple independent
+-- join chains that need to be combined
+--
+CREATE TEMP TABLE chain1a (id int, val int);
+CREATE TEMP TABLE chain1b (id int, val int);
+CREATE TEMP TABLE chain1c (id int, val int);
+CREATE TEMP TABLE chain2a (id int, val int);
+CREATE TEMP TABLE chain2b (id int, val int);
+CREATE TEMP TABLE chain2c (id int, val int);
+
+INSERT INTO chain1a SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain1b SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain1c SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2a SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2b SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2c SELECT i, i FROM generate_series(1,100) i;
+
+ANALYZE;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM chain1a
+JOIN chain1b ON chain1a.id = chain1b.id
+JOIN chain1c ON chain1b.val = chain1c.id
+JOIN chain2a ON chain1a.val = chain2a.id -- Cross-chain join
+JOIN chain2b ON chain2a.val = chain2b.id
+JOIN chain2c ON chain2b.val = chain2c.id;
+
+--
+-- Eager aggregation with GOO join search
+-- Ensure grouped_rel handling when eager aggregation is enabled.
+--
+SET enable_eager_aggregate = on;
+SET min_eager_agg_group_size = 0;
+
+CREATE TEMP TABLE center_tbl (id int PRIMARY KEY);
+CREATE TEMP TABLE arm1_tbl (center_id int, payload int);
+CREATE TEMP TABLE arm2_tbl (center_id int, payload int);
+
+INSERT INTO center_tbl SELECT i FROM generate_series(1, 10) i;
+INSERT INTO arm1_tbl SELECT i%10 + 1, i FROM generate_series(1, 1000) i;
+INSERT INTO arm2_tbl SELECT i%10 + 1, i FROM generate_series(1, 1000) i;
+
+ANALYZE center_tbl;
+ANALYZE arm1_tbl;
+ANALYZE arm2_tbl;
+
+EXPLAIN (VERBOSE, COSTS OFF)
+SELECT c.id, count(*)
+FROM center_tbl c
+JOIN arm1_tbl a1 ON c.id = a1.center_id
+JOIN arm2_tbl a2 ON c.id = a2.center_id
+GROUP BY c.id;
+
+SELECT c.id, count(*)
+FROM center_tbl c
+JOIN arm1_tbl a1 ON c.id = a1.center_id
+JOIN arm2_tbl a2 ON c.id = a2.center_id
+GROUP BY c.id;
+
+RESET min_eager_agg_group_size;
+RESET enable_eager_aggregate;
+
+-- Cleanup
+DEALLOCATE goo_plan;
+DEALLOCATE standard_plan;
+
+RESET geqo_threshold;
+RESET enable_goo_join_search;
--
2.39.3 (Apple Git-146)
On 12/10/25 06:20, Chengpeng Yan wrote:
Hi,
On Dec 10, 2025, at 07:30, Tomas Vondra <tomas@vondra.me> wrote:
I looked at a couple more failing queries, and removing the aggregates
fixes them too. Maybe there are other issues/crashes, of course.Thanks a lot for pointing this out. I also noticed the same issue when
testing TPC-H Q5. The root cause was that in the goo algorithm I forgot
to handle the case of eager aggregation. This has been fixed in the v2
patch (after the fix, the v2 version works correctly for all TPC-H
queries). I will continue testing it on TPC-DS as well.
I can confirm v2 makes it work for planning all 99 TPC-DS queries, i.e.
there are no more crashes during EXPLAIN.
Comparing the plans from master/geqo and master/goo, I see about 80% of
them changed. I haven't done any evaluation of how good the plans are,
really. I'll see if I can get some numbers next, but it'll take a while.
It's also tricky as plan choices depend on GUCs like random_page_cost,
and if those values are not good enough, the optimizer may still end up
with a bad plan. I'm not sure what's the best approach.
I did however notice an interesting thing - running EXPLAIN on the 99
queries (for 3 scales and 0/4 workers, so 6x 99) took this much time:
master: 8s
master/geqo: 20s
master/goo: 5s
Where master/geqo means
geqo_threshold=2
and master/goo means
geqo_threshold=2
enable_goo_join_search = on
It's nice that "goo" seems to be faster than "geqo" - assuming the plans
are comparable or better. But it surprised me switching to geqo makes it
slower than master. That goes against my intuition that geqo is meant to
be cheaper/faster join order planning. But maybe I'm missing something.
Sorry that I didn’t push the related changes earlier. I was running more
experiments on the greedy strategy, and I still needed some time to
organize and analyze the results. During this process, I found that the
current greedy strategy may lead to suboptimal plan quality in some
cases. Because of that, I plan to first evaluate a few basic greedy
heuristics on TPC-H to understand their behavior and limitations. If
there are meaningful results or conclusions, I will share them for
discussion.Based on some preliminary testing, I’m leaning toward keeping the greedy
strategy simple and explainable, and focusing on the following
indicators together with the planner’s cost estimates:
* join cardinality (number of output rows)
* selectivity (join_size / (left_size * right_size))
* estimated result size in bytes(joinrel->reltarget->width * joinrel->rows)
* cheapest total path cost (cheapest_total_path->total_cost)At the moment, I’m inclined to prioritize join cardinality with input
size as a secondary factor, but I’d like to validate this step by step:
first by testing these simple heuristics on TPC-H (as a relatively
simple workload) and summarizing some initial conclusions there. After
that, I plan to run more comprehensive experiments on more complex
benchmarks such as JOB and TPC-DS and report the results.Do you have any thoughts or suggestions on this direction?
Thanks again for your feedback and help.
No opinion.
IIUC it's a simplified heuristics, replacing the "full" join planning
algorithm. So inevitably there will be cases when it produces plans that
are "worse" than the actual join order planning. I don't have a great
intuition what's the right trade off yet. Or am I missing something?
regards
--
Tomas Vondra
On Wed, Dec 10, 2025 at 5:20 PM Tomas Vondra <tomas@vondra.me> wrote:
I did however notice an interesting thing - running EXPLAIN on the 99
queries (for 3 scales and 0/4 workers, so 6x 99) took this much time:master: 8s
master/geqo: 20s
master/goo: 5s
It's nice that "goo" seems to be faster than "geqo" - assuming the plans
are comparable or better. But it surprised me switching to geqo makes it
slower than master. That goes against my intuition that geqo is meant to
be cheaper/faster join order planning. But maybe I'm missing something.
Yeah, that was surprising. It seems that geqo has a large overhead, so
it takes a larger join problem for the asymptotic behavior to win over
exhaustive search.
--
John Naylor
Amazon Web Services
čt 11. 12. 2025 v 3:53 odesílatel John Naylor <johncnaylorls@gmail.com>
napsal:
On Wed, Dec 10, 2025 at 5:20 PM Tomas Vondra <tomas@vondra.me> wrote:
I did however notice an interesting thing - running EXPLAIN on the 99
queries (for 3 scales and 0/4 workers, so 6x 99) took this much time:master: 8s
master/geqo: 20s
master/goo: 5sIt's nice that "goo" seems to be faster than "geqo" - assuming the plans
are comparable or better. But it surprised me switching to geqo makes it
slower than master. That goes against my intuition that geqo is meant to
be cheaper/faster join order planning. But maybe I'm missing something.Yeah, that was surprising. It seems that geqo has a large overhead, so
it takes a larger join problem for the asymptotic behavior to win over
exhaustive search.
If I understand correctly to design - geqo should be slower for any queries
with smaller complexity. The question is how many queries in the tested
model are really complex.
Show quoted text
--
John Naylor
Amazon Web Services
On 12/11/25 07:12, Pavel Stehule wrote:
čt 11. 12. 2025 v 3:53 odesílatel John Naylor <johncnaylorls@gmail.com
<mailto:johncnaylorls@gmail.com>> napsal:On Wed, Dec 10, 2025 at 5:20 PM Tomas Vondra <tomas@vondra.me
<mailto:tomas@vondra.me>> wrote:I did however notice an interesting thing - running EXPLAIN on the 99
queries (for 3 scales and 0/4 workers, so 6x 99) took this much time:master: 8s
master/geqo: 20s
master/goo: 5sIt's nice that "goo" seems to be faster than "geqo" - assuming the
plans
are comparable or better. But it surprised me switching to geqo
makes it
slower than master. That goes against my intuition that geqo is
meant to
be cheaper/faster join order planning. But maybe I'm missing
something.
Yeah, that was surprising. It seems that geqo has a large overhead, so
it takes a larger join problem for the asymptotic behavior to win over
exhaustive search.If I understand correctly to design - geqo should be slower for any
queries with smaller complexity. The question is how many queries in the
tested model are really complex.
Depends on what you mean by "really complex". TPC-DS queries are not
trivial, but the complexity may not be in the number of joins.
Of course, setting geqo_threshold to 2 may be too aggressive. Not sure.
regards
--
Tomas Vondra
Hi,
Here's a more complete set of results from a TPC-DS run. See the
run-queries-2.sh script for more details. There are also .sql files with
DDL to create the database, etc. It does not include the parts to
generate the data etc. (you'll need to the generator from TPC site).
The attached CSV has results for scales 1 and 10, with 0 and 4 parallel
workers. It runs three configurations:
- master (geqo=off, threshold=12)
- master-geqo (goo=off, threshold=2)
- master-goo (goo=on, threshold=2)
There's a couple more fields, e.g. whether it's cold/cached run, etc.
A very simple summary of the results is the total duration of the run,
for all 99 queries combined:
scale workers caching master master-geqo master-goo
===================================================================
1 0 cold 816 399 1124
warm 784 369 1097
4 cold 797 384 1085
warm 774 366 1069
-------------------------------------------------------------------
10 0 cold 2760 2653 2340
warm 2580 2470 2177
4 cold 2563 2423 1969
warm 2439 2325 1859
This is interesting, and also a bit funny.
The funny part is that geqo seems to do better than master - on scale 1
it's pretty clear, on scale 10 the difference is much smaller.
The interesting part is that "goo" is doing worse than master (or geqo)
on scale 1, and better on scale 10. I wonder how would it do on larger
scales, but I don't have such results.
There's a PDF with per-query results too.
This may be a little bit misleading because the statement timeout was
set to 300s, and there's a couple queries that did not complete before
this timeout. Maybe it'd be better to not include these queries. I
haven't tried, though.
It might be interesting to look at some of the queries that got worse,
and check why. Maybe that'd help you with picking the heuristics?
FWIW I still think no heuristics can be perfect, so getting slower plans
for some queries should not be treated as "hard failure". The other
thing is the quality of plans depends on GUCs like random_page_cost, and
I kept them at default values.
Anyway, I hope this is helpful input.
regards
--
Tomas Vondra
Attachments:
tpcds.pdfapplication/pdf; name=tpcds.pdfDownload
%PDF-1.4
% ����
3
0
obj
<<
/Type
/Catalog
/Names
<<
>>
/PageLabels
<<
/Nums
[
0
<<
/S
/D
/St
1
>>
]
>>
/Outlines
2
0
R
/Pages
1
0
R
>>
endobj
4
0
obj
<<
/Creator
(�� G o o g l e S h e e t s)
/Title
(�� t p c - d s)
>>
endobj
5
0
obj
<<
/Type
/Page
/Parent
1
0
R
/MediaBox
[
0
0
595
842
]
/Contents
6
0
R
/Resources
7
0
R
/Annots
9
0
R
/Group
<<
/S
/Transparency
/CS
/DeviceRGB
>>
>>
endobj
6
0
obj
<<
/Filter
/FlateDecode
/Length
8
0
R
>>
stream
x���_��8v��cp���?�|��a��D��c�dlL�8�t� ���a�ub'@�~��\{�����%�4f�~��K�:�"�D���o��������#��������-�P���������7����������iI������������=���[[��7����w�F��{��������}���{�=^���^t��y_�h�����u�<j����S�G��o9e/�p;�4��h2�������T\�����?�vJ�U�gy�����S���Jh�T�7��E���8��}��&�C����;�3�V8WN������G: ?
�8J�0�A3���c����*o�V��G�S�����do&@�7��e����x��������y���H^�D�F�] /�DZI�v
��Nea|��Ne��f��0���G[��Jg0<]�'P�}U�}��������}���w~���Hj�����r���z����8�������vJ����8����0��"�-������,7��.�=�s?��x�\6�4~,�Ir%)�H�i�������Of��9���������t�Nv��� )���0S��x����}o��������8�y�;�W3��q,����4�\9����w|��'��D9�c+�������������I�c�c>��>Z*���l��q����n��L�U*�V�|ZG�Q-���7.�~Z�X8���5�GK%=��.s���8�`���T���g]����s��-|0���,����q��w�O�����l�d��x�^w����s�l������-��`m��Spq��y_w���#w �@�;��h5\2n_����8N�t���Jr����X�'tZ�G����~��|"Ju����[_�tN��v�j<���4���� ��-<�)��g
|*�P� �����1��t���x�������Y���Riy7������3�x��dg���h���
4�~w��p<�B�T��U���1��~��+��vv;��Uh�<V?��;o�zj���y�����m =V�����������X��6P������������q��3a�������`�0f���C��V;���A��Wh��c���x|������k��j<�C��D'���l��K�3�dg�y4�49]T�8�I��%l}OO>�����YC';�"�}�,9�`�����
H7G��e�5@bP���R�T�0E��������R������,����(���p<Y������P<(��*�O�� C'���x����_8��08
�-@��T����.@������O :�)�<e�d����C���r��p&<��W�7J?k���<��d��y�h�Y��|�<�I?��'PdK�������R�g�Mt�3+<������x����l�Y��sa|�%t�O|�� P�����x�^�g Pt�� ���������iB'K6O�������)��T0�$@��oKV����������%������<�tV�+�����g�@T���@�`>��U�����Nvf;��2�O�����PHny�Pv�!�C}Y�Z�>���~*|b�T�e�0_Qx�����&�Ty6HfV�����wt&�%�<3)��"��y}Y�-��(��}�&7&���|`������OJ��>;�*MnR4�����"Jh�s��8N��'u� ������������s�@���~��@��� ��I���n< ������W7�t2��g���A�'�\w�t����T �.1����`����7�y���j��'=O��OC~.��<}�d��x����n��i�4�O��������p.W�:�}��gJh��n-�`8�S�"��`S�:��Q�1ZdH�8�X���e��p0|n�?�g��`���}*:
n
�����R��B��3��q��� G��A� �d.���#v'������-���x�F���G�@E�j���q��%����~r<Rw� ��c�Z��~���Tx�n�Gg�p0��t������ K���Nm�a:PZ�m:���Q�V��O��qr���)�<h���t���@�WM|6�Q5(��h�YB�!t��(<P�/����p<Gh�b��)���������s�@e��}��0��<9h�F������/�������N��#��~E�}w���g�;~f���
�'���p�r� �@?�Un�GL� L�N����M�' ����>�!��r>{���t�K�v<;�C�pOrJ�w3��l�irn����EN&`�����m7P�3��|����<; ���H���I���r�����l;�9�$��V9��zD_������v�;!��9��3�eYx2�V�eG�����b4�G�G.��X[���|�>-�L�G���u��/�&Kv;L��Q�og���69�Mv�-�._f��3��[A�����M-�����#|�8���l�[l�[g��r;��"{�:�![��
X�-�?}�V��m2j���������v2J����Y]��\�n��A����&�r���+�w�I�NI��u��:"pn�u�1����!W�M�hu���e��e���mt�A9��3SF�2�v�2vF�e(�t�m���������������dd����'���$N�$CgG?�U�����M�qk�����c�{v@;9�U���IG��KK�������Ye##�?����@��-g9�������������[��8b�������w��pv>28oEF��z���,��,�uG?�C��E��l��-�54���3,�����[����h�����?�~��]�������V}[�� ��}�r#'�t�3\e1=�9z��h'%���� "�����Xf���L "�<C�~����GFo����Td����"��d
d]���}d�2t�������e����v<;!�2�*s��t�|���������������H��m��2�������k���0���h������H�G����v���:�VT�Q4�b��
�u��h<�I�����GK{<3���x�(�z��=���H�U��Pc��xe��O�${��7��+�����M�GEzc�rx��P9�j��>����L���`�G{����,K���,��3xp�7��6�)����QY�-
�{�?&��^=*YF�����������������G{����6
�{�o��h��;�Fas�=������mv�P�5��^=*�F�������o�?����@c�P^�!l��]��R`u�a���g���{(��x�F{c���<�}��-��X ��=�C����{�@r�+<������7X�C{�����w����=�x}c]o,P�C�aw�o\�f��p�m|�U�6
�=T6x�|?To,����P�oI�
G�����3���w������f�X������X�4�P]�!�(�2�R`q�
�����l����C���;=zc��=T+<�
0���7�����!�0��}�f��=t,�6p���1E`X�CG���i������=tx��Fxo,P�C�a��g~48�PK�n����^)��Cm��p������{�ex���~eo,��C��C�s�w{c��j<�������yS;hF��M�p'2�=�Q��hZ�V���_�I�:
����d���z��J{���Xy]��-\�T*o��7x��h����^���G����������l��M������&��n3o��H�����f�K��7�$��G�R�)��l��?yh<��BK#�����z��v�+-��u3�!�N��b�!����b�CN�<�J�\��:�����^����-���&�F�R"�m���e� l(���-��&O�F�R&�m�\�(.y�3
�
�n;�u����$c�&���K��K�:$�\)���j�CL�|�?
�Vr]��:d!�U*�,��P_~�W��O�����.��r����X�0�$1��e�*KF��$Fx����J�2��0��: b�eJ�8��N*H�;�(Y����uF�0(�T�4m+���aP�\�d���3��A���J�T�mc��F�o�*�<�����.��&�U�m���!��T�Lm���-U6n�]}����t�7PU3#�`���^�������p�����3�&�����6�3�&����@��Y ��4vp��~Fr���?v��g(������~F�2t�V�3R&�)rAV�|m��\���WF�RQ?#qa���^��������~F�2t���i��dvp�U��l��t
;8PV?#�a2�������0� ���J���-��$�3��BI��L��tvvp�M�����t*;8�e=h�~.U&MfJ5�3�L4��O�T�m��ua?#:J��������@��9��Tvp�]�����t;8PU?#Cb���V�4 m����~F������~F��d:�(���61���d����������W*y
����������RR?#�b2������R1�Na��gdVL�s���3,&��"��^��,k-S��d�$ZS�F#�t�,s��kb{�=�XMRpOA�."f���m�����Y�U����Q�1k�^���m"p����El�#�1T�������UY)F�������5Y.F�a��4M����a�����5��.���A,�z �6A������� ��!��XB@
'hb��Fu@������-I@��)� $t�.������� �X�G�� �t�C,���,O����!�P�T��k��� ��X�z r>A�b��k�H�]���#Z��>Lr��������\z\9�?���J,�
W��^��R�����F#��plT%`��h�Ib�z���]Y1��?&�Yw�Q��m��ToP.\�d��V����R�R��?�=Xg�z���+�,�C��:#���U*y��%�]b�M��d���}7�/�Q������1�Ne���m��H�5vo��fF��$~�R��?�e?#����-�g�L����m�g�L�S���v�3�?&�i��@U�������`%��p�c?�����o�(��g�L�S���������L�����h�~���_�T��m��{b?#�:JI�����t2;8��~F��d:�(����1���T�����lM�`%�����\��Fc��~F��d:;;8��~F��d:�hW?#�c2�&�%���V&�����W*y����������
�E�����tvvp�M�����t*;8��~F��d:������1��na+y�����ca?#���PhQ?#�c2��������L�`*�g�L�A��+�<�C[�sK�g$~CG)����1�NfZ�����L���e�3�?&�9��������{�a
/�����)tJ2�F���)L��� �X��s���=���D�&��� V����E��%��U����@~�:�����n�p�D,���-��&F~���E#�?A��R����#�?Ak�\�X������!���S��?k.=`]� ��X�%� ��.���#n� �t�C,����O��������Ys�����X>b
= ����e�|�5� ��.V��s���]��G,� �41~:=�����$�� 0���O���X>�z �?A+b����m�����W?�Wci�]$��#�#@}^�D����p%��u(+U X�7n$1������6�|������ ��o����YD��1�������h[Xg�z�r�J%������H����J�����:#�t\�d��6�����R��?-���lb\%���V������J�M-����t*7��>F��d:����?�e7#�����W*y����g�z�6vp�E�����tvvp�M�����t*;8��~F��d:������1�������z�������
�U�����t�\��r�$�&�3�Q�T���������W*y�����=����
��~F��d:�hU?#�c2��������L�`*�g�L6�&v���h�~.������PR?#�c2��hS?#�c2�������1�N�Y�RU?#�c��^��������~F�7t��3�?&�����6�3�?&����@�����4vp��~F��d3�������������SC�E�����t
;8PV?#�c2�������1A�_�T��m��H����@I�����t2;8��~F��d:�(����1���T�����l���SxA����L�S�94?hLa��O�����#�-��I��$b5Iu�=���X]D�-R�.A��"���������Ys��Ez�m����Y�,b�,��:����]��J1�V���]��r1b
�G��&��kOE������u���b���� ��.������O���|�z �?AC�7�z�g�� ��b��)� ��.���-�����,= ������ ��!��XB@�'hb�t(z�g�5AI��A,`
= ����e�|�5� ��.V��-�{<���X��[~��_=���L��+t#�_�G�L����-������1��=6n�~� ��F���q���H?���b��H�� ��Oh��X'f�0��9�*"c=I`e��irK�:��$���g���f=��H�7�|��XFXY��D,����G���@dSO�:V2*2�Q����\�FnE�7��a=�{ ��7�"�c=����c���@�XO�:��X�v�,9�������n�"�z���c����@�X������3!�-���u��Xdu�,9�������E�����Z�����V������n P���[���|n�"�z��1�c���@�X��:r,��Q��a[���Xn�"�z��G�D�E&7�@�X����I�E ��S���glwr,��Q��[�J�E7��c=]��x2�d��M�?�H��H�X��:n�X$p�,9�C��;9��(D��D�c%�"{e����ul�Xo�,9���>oZ��H���*9���1E#�"r��M�o��h9y�(D����A�E�6��c=?{ ��"�c=<���c���@�XO�:fr,2�Q���Y�B�E�6��c=3�x�c����@�X���;�D���y.�Y���g��P�'��
���r����;+)%\+�$�V��lp[X�-Rqe�&V����d����L���mc�m�����6]����0yiD^�y,6��
J#�*�3����i�P��j�u�_Aa��bD���a�7�8�3�Fd�{6xg�#7���"�NM���q�f(����3�n���C��'`�W�8�2�Fd�{�58�����4"{�����=�����|
>��H�P�=��Wg�a&�"J����E�L^�=�y���G8�����v�,��E-��;>������ �U����j��H�+��9���Jl��h���H�:���,|
7��Z�c�*��F�L#[�����)Y��;� ]��,�d9����\�R��8���32�A�r���qh{����W*Y ���uF��5�T�LFKb��:�WiQ�c�����Y�M-�msL�S���v�1��1�Nc��jfl�c���^�������
����,�C[�3��A;;8��~��9&����@�����L���U�3��1�������z������
�U��msL�S�����%��5�����J��~��9&� w��J���-�����(���m��t2;8�exh�~�3���T��gl�c2������m����V�0m��%����a4J�gl�c2��hS?c���Tvp�]��msL��d��T�<��D������J%�����\�3��������m��tvvp K����\w�3��Q�����m��t;8PU?c����v��G}h�~>�3r:L
��3��1�Na��gl�c2������m� :�z���~h�~n����n�(%�3��1�NfZ���6�d:���?�e?��~Fx7*������l���SxA���L�S�94�;hLa�ms�.�e�qmAlO"�'�I��)��E��"bm���u bm��>�,oT�X����-�n��\� �e�����b��� ��"f���u����ZsY:.U����P���#�� ��=�==%����Ez �=�\B��9A������mN���|�z �� �b�Q�Ck.=`K���A,`
= ��],��#��`�����|�z �� ��!��h��5����$�O=@����$�� 0��ms�.������mN���X>�%��q�w��i�K��������>/T"`��h����:���,�
7��^�c�*��F�L#�����`te�,"���Lf�YF)��3�?&���+�,�C��:#�T*W*Y�����To�qp���h�Xg�z�[�J%��`�$�K���q�,�C[����E�7*�6�0�?&��l�@�����4vo��fF��$~�R��?�e?#����-�g�L����Y����g�z�*;8��~F��d:������1�������z�������
�U�����t�\��r�$�&�3�Q�T���������W*y�����=����
��~F��d:�hU?#�c2��d������~F�7*�����
��������Kb?#��h,������Lgg������L�����g�L��d��T�<��D������J%�����\�3��������1��������1�Ne��m��������J��~F��d3�������������SC�E�����t
;8PV?#�c2�������1A�_�T��m��-����
��~F��d:�hU?#�c2��������L�`��m�����3?L�=���2�NI����0�i4�?A�2w��� �'����$����"bu��Hu�����Xc�[�7�z�g�����M�.[���m�`D����[X4"�t�*+����j1�^wlE�Z�g�e��4� ���T����KX�� p = �����b��[���]��G,� �41~�:���\z��� ��X�z �?A�b��k���]���#���� ��!��XB@�'hb�t(z�g�5AI��A,`
= ����e�|�5� ��.V��-������e ~z�!������3gn��]������M@c
Y���a# �����Kc�X�D�!���ww�HA_��*����w�Xg�+.MB�u,��HmYg�+~�B�u,�<V�LV�`K��U&�Uj�s���H-*-�t<�<V�LVhaK���`$}�2������m��oTb'{z7�������@lgO�:� [&TFb?{z7xc?#�������
���H�Fe ���w�+�I���~��npc?#����������~F��K���~��npf?#�������
.rE.r$��~���LV����]g<|���H�gO���g$}�2���������oTb?{z7�������@�gO��g$}�2����1"&�3��1tb?{z���������~��n��~F�7*��=�\��H�Fe ���w��L3�L-�L����h.*#��=��������@�gO���g$}�2���������oTb?{z7�������@�gO���la?#���@�gO�0d?#���P(��=�\��H�Fe ���w��3��Q����]g<����H�gO���g$}�2���������oTb?{z7�������@�gO��g$}�2���;���L���a-Q������Uf���PQ&������D,7��'�S�I�j������%��E��"�Wkjt{�W���!���;��m"�mR1��ewxc�"�g��(�F���F��#�>TG���gwx���Q�#�������UlD�����Mz �>TG������ ����b����8� �CuD����7����U�C�����Uz �>TG��������:�� ���F�����xv�7���PQz�gw�
<�+��ID�PR�x X��#J��od���PQz@���1`A���� �x�Sw��i������p��H���P��m
W� a��R�����F#!�plT%`A�h�Ib$���2%��t'����e�,JD��:# �W*Y����uF@8�T�T�(m�����J%�������F�J%�hIl�Xg�*-�{ld2�]<�������t*7��>�F@&�i��@U����L�A�+�<JD[�3�A;8��~�F@&�����6�362�Ne�����d:���D�e?# �����Q"�z������U����L�S�����%��5����J��~�F@&� ��J%�-�yO�gD�CG)�����t2;8��~�F@&�)��@Y����L�s���362� ���J%�-��$�3"@��BI����L����m�gld2��������t��2�j�g4�h4�3"�^��Q"�����~F8t��362���������t*;8��~�F@&�i��@U����L6�[��J%�-��X��� 15Z����d:�(�����tvp��~�F@&� ��J%�-��%�3"��������d:�hU?c# ��vp��~�F@&�9������l�� SxA�5[��A�z�V�t�U��im"�e�qmAlO"�'�I��)��E��"bm���u bm��>��oT�0����-n��\� �e�d������h�F@A��R����#6
�X��b����(hb����T�0��KX���q�G�0��KX7���l��������.v��#���P�������&Zs�[���bS��(�bY,q
= ]���#���P���|�z 6
��?�&Zs����X>b
= ],��#Z�h���,= ���D�&������W?�Wci�z\9�?���J,�
W��^��R�����F#��plT%`��h�Ib�z��5����E����;�(Y����uF�7(�T��m+��ToP�\�d���3R�A���J���mc����o�*�<�����.��&�U��m������T������L��q��c�L��������t���J%������To�������1��������1�Ne������L���U�3�?&�����<��U���W�3��������1�N��R��"���~F�7*����t���J%������'�3���������L'����g�L�S����������@E�������V��m��H�0��Y��!��\6�3�Q������1�Ne������L��,C��yF��Fc?#���J���-��.�g$~CGiQ?#�c2��hS?#�c2�������1�Nc��g�L6�[��J���-���kp���Y��� ����g$~�R)����1���T���������W*y��������H���RR?#�c2�������1�Na��g�L�s���3�?&��"��^��?k-ShDz�U��S�F#�t���:��h�'����$����"bu��Hu�����Xc�[�7�z�g�����M�.[���m�`D����[X4"�t�*+��{X9"�t�&���5,�� �?�==�����Ez ?�\B@�'�b�X>��h^��Ez ?T,� �41~�:���\z��� ��X�z �?A�b��k���]���#���� ��!��XB@�'hb�t(z�g�5AI��A,`
= ����e�|�5� ��.V��-����8&����Uo����u�)��������M@��T�H���:n���,42IXzWq��4YeF�I�����
�#��H�u,��HmY'���*�Xz7x�2��2��:��
�L&��X�P��A`&TZ�xz7x�2��2��:��
�����2#��=�\����2#��=������2#��=�����P����������*3�����;�y�Uf$���w�+�y�Uf$���w��y�Uf$���w������2��gO�g�s��������E�����$��~���LV����]g<���H�gO����]V������
���]V������
.��]V������
>����2#��=�#bb?{��&�~��0����2��~��n��~.�<��~��npe?YRFb?{z7��4CV��d����x� ������
���U�������
���U�������
���*+�H�gO�7�s�Ec$���wcz���Y/Fb?{z�� ����b��~��npa?e�vb?{z7�`?�@��~���3fBe$���w�W�s�ea$���w�3����0��������d1���������d�������
MI_����=������.��L�=�����.#�I���j��$��X]�X[D�-Rq��F������)���&b�� �0����xX��#����;�Qe��Q_���=��MV���)V��n���}Qz�gwxc��Q_��� ����.=���6�"=��;�qH���MQz�gw�
<,h��Pz�gwxc��Q_��� ���F��Q_��� ���F��Q_��� ����!=���6E����7� ��G&�xv�7V���)J��od���)J���=,H9�b�������������oo����G��������_���?������o/�C�����J�;�������������}�7?����z��������������<>���G���e�a�����������������?�������|����������n�������>���������^R_�/`���?�o>������~��K�[�{����������/I�~0�����g��.�������i��~{��?���������w/�>����L�e�����~�5��m+��������'U�:������}���^�M�����A���J;��D���~�/~�m��y��>w�-�?���M�W�u��P��������?��5��#�V��Eew�^g�_���������L���w��k�8���'��{�G���k��'�#��D�W���+��wW���+���^E������~�����X�,q�.�S�3���)v�M�u���Z��������k��~��^�C��������r����>�_-��_�>����T�����XnK����]��b1W����]-�������^�u�\�a����y�h�6���s����c�<��+�3�_��d��h���9wL��?��O's�_�����(���|��1U���;~M���5c*���9��|f-r��-�1���������~��h�Wo?���En_��Sx���E�����kK��S�������,2����|�/L��1������<S>������6�5W\-l��Z�'�O��������7R��R~[�}~�;��'��c���W����S��O(��I�~mO�8��\�?����\��7'������;3��i�\���D�<���^��O>�������������W/��~��X���/���z��G�x��jVB�8���t������O�_��/.&_L����zq���bK���$�o�=�������L���k��r��K���t\
>V�/-����8}_����� Ye�gkgs��������\���e���7|E�5�~=�'_�����d�}1�}���/.v_<>y��7|����o��������3���x*|�N�s����\���x}�|�8��1�� ����h����h���i_L�_���/�(����2 �F�s���>>�^-�q��7���(t�����E���ig}1�� ��Z�}q���b�{����������<D{1
u_Lu����������S�+�����~}�����B��OG��tO��{.|�O�_���/������'��X��6��>��u�=��ja��S�W}�y�\��������5�����,����7��d/E.�����t_�����5���~���_�L?���d�9��q6���^�X�X���L��f�'�gv��]]����_����(��g�����w.�u{\�k������^.L�8��#���S�v�^����
g��>��l�(_���Q�6�^���S�_���v����b]����������5�q6���^p�x�{rz���E�T�������?K��s:���~{�#��uG<�=�Sg*|���'�����Rf�8�u>�=�H}�{�I�'���TC�L�����������O��O��Qg_���s*{�������Z]��L��t�.3�+����#N?�>�}���?�~��?�~��=�>�=w�l�?&����G]'A�7�������.�u{\�k�����3{�W����
{��@���q�T��;Qn�ku����=f�W<�~�09�N��oN'�S�+��ku��t_]�G�d/q�\�����m��}s:���^��t��uG\�kw�&��]��W��>��.��q,����� �T��;f��=.�����K���y��M��oN'�S�6�\���x�{n��^�y?���E��O��� �T��M��#��5G�dOEYp�3�����NR�oO'�S����;�Z]w�������;|�
���u�IB���hs*{AR�T��S"^s�L��>x���<b&}�<�-�������T�G<�=���u�����+���
�O���m�����i�T��G�.�uG\�k���^������yD+�$����T�
G\���x�{n������0jL���`M;&I�����������ku�3�K�W�#��&����]�T��'��w1>>i���gw]���l������|��� [�:���=�;���?NN&�V�Lr�����'�������'K��X���i�\��_�z�0��Za�x�����w�2��L���Ng�s�&W�/����L����2���Dd��N6��'~����Za����|��)_s��V�|��IL���|s�{�8�T�����Ol����/>|�����5�X'q�w�S����B�&_\+����^2�\���������Y�\��������g���G��������$���,����,u�����ES�KLr�0��Za�x�t���3��fPi�4���!�\������ja��������%a�����u��t��OB����������]+��l�{�/.Wf_l� �����T��Z����#b��L���vG����#�>���;~Nu�3.&_\+����^4��j_�����I�����s�����������^/f�W�b�}���M������S��Z�|q���b�{�E�g��\��0c[&��������������/��Wl�|���Z�m�}>���^~^,L��V�}1��$�|�|���m�df��?��W�S/&_\+L7�������_<Q~����/�Ib����s�{���Za��3����)��{w��5�.n'��4 ��?~Nu/�|����ba���3�s�
���3�+~����I�����s���;v.&_<>}��*����s���.Tr��g��?��W���X�|q��_/f���G���L��<l��2�M������%�x&|v�1���0���W'�J\>����Y1W���?�
�X�
endstream
endobj
8
0
obj
15679
endobj
9
0
obj
[
]
endobj
12
0
obj
<<
/Type
/Page
/Parent
1
0
R
/MediaBox
[
0
0
595
842
]
/Contents
13
0
R
/Resources
14
0
R
/Annots
16
0
R
/Group
<<
/S
/Transparency
/CS
/DeviceRGB
>>
>>
endobj
13
0
obj
<<
/Filter
/FlateDecode
/Length
15
0
R
>>
stream
x���_���u��c�<��K���_��q��K�K��Sv���Jf���c�U�������B���(���A�s�k�����~y����������������.�k��_���yy_J��_\6B���5���������_�e[�#���|������������?����?�^�u|���������_���_�}�����o���{x�)�^��V1��~{9��-.����1S�G�����z����}<^}����uY����^�W��>8�2a�}�%�J���_��q�������o��ix��5�� �8���>��c�w����W���J���_��e�)�����$�||��z����n���n��c������W�}&���F��������ox ��o�w���_���?.����z��_���?-��������F��o����\W� e_���������������_���/F�6�������m��C��Z_?�&����?|���_�����x��?z����?���t��n��/�~�������������������w�������^~����������^���}�����t���\��/o��^��*��v���j����_^���������m{�����7���G����#.�����
��i��������.��^�����\e�o%��'����J{���v ��"JdC�\H/W�e8�u�)k��7y�>�/1�z6;*�q��~1XK|�����AE��<���>MJvB�w�o�K��v��
�wx�A�~��������������&[>
��X�2� �W�����#>��dgw��������;�dgT������s^]���.�����A����8�8`|��E;���r������|}������/�l�?}��%�T�},��l)��^_����q[h��2�0�a<(A>�aWx����:~�;���c�} ��pp1]N�%���G����y���<|����JG�w�����v9i��n?�XCN�u��{���c�c��J0�a��u!�>��������������c�E�2����7�emK�� ��s��/�����H9���?):�b�`�����>�H�j���������8������������:}��9F�X�>s�O������&:�����4����{�7�������y��~�O�r8�-�Any<�����1?��#�$�{r8��;;�<!��`A����1���W�2��~x��� ��c�L?J{�e<6��8N����,��q�J��7:�>xr1�7W�Hz0o��u��]qm:���pr��i�����T��/��]Xe?������b[���=~�1�+�Xv���MQ1�3?�J�t�\,�u{;���w��h����L����]���v�
?����>���a���Rm��&@5��&��(�q:�-�F�^7���q6�����;�`�a��;�'j����~l�f:���!w~|6u�7L� �te�������0N��C,4��f!���`�Q�{�4 ����C��8~�����F3��h&��zV�1������@P��}��dO�=-���;�Q�k(.�\ ���l�2�I����pl���=�\x�����h���`���b(��}2���m��@�h��8�r~1h�f;��f(&�u�����F3M9�=�d�N���� H+4i�8O��h������0XpP{�5�q�h���4�����t������x��� ����4���
���p�G������h^�E��(�4Kx���K;*��l�f"��!������H3���2MA#�Hl�34?GGiF `�)�"�����[����~��f"��� ��L���K;,��l��"��.�rm�*MJv���h�Xi�0��~e���$� n4 Q�w�����m�Iv��i�q"h��G����7��@����}="��
?�K�8W������Np}{,b
�L������`������vg�S��r�ORp���>�\��r�C��`�+�O��K;�J�W7:��K{��������.��A��4_�w���8���������5�e������-�tl�|<U�������mtxa��c�]�P�`�{�Ot��L�R0��v���8u�`
t<���l%��Mc&i����'�t8%��L�����x.��>���JG�V:���i�?�}����"�_�����S�/_1X�<�
�����F�����@�����a�=��m�%
_���L���"+ �qt���&D��HG�� Q�8R���I�t$m���\,��?t:�8���Gh������-�s��M{��
u�����W�v�LG2a���b�������[u�D�x��f[� Z�Pg�;��j���>�1��kG?�B3,�T�{�\.j{���9W(4�R�=�%�h��kG?�F3-���������Wh4�R�]����v�=��&Z���1]>�K������~��9�B���c���?���c��2�#j��P�4�Q���Kk.�4 ��&A1��G1�)���I"3��#M���x\����iB3M�b��b��I��X��=���D���@���L8�}�taG?����������/;�<��f��}}��7�<�h��V�-bp���������=����pp�'��{��y�o��L+M+v�c�4�P\���g�����xhJ�,}�3\�S�����~����V)�|bG?�L���|�>i�,c8�H
� -��3�=��B�2M(v�c�4�P��]���[v�i��������B�wh?C_M�n�u<�J��� 7�?(V�N��[r���%�F��a?|�Ke7;���@�A�����/����m�I4:f~�E�w���`^i��W���D���������p��=�4c�0�E�����.*4u����\E1-�C��kz�v8�D3h MY�10�U�Y��~T��)��s��uB�=����Jn4=Q,4[�������)��h���TYhZ"�����U��RY�3\��
D:��&'���ys���bYh���b���B��7�,�?;"���@�����j�RL�����K������s�A��n<�@�� ����P����eI4]�����D1�t%����i�u��x���+��{�������KMMv��i4Q,��&����viG@���y�otJ����v�u��� �(�5��@�#v���~hq��i����Gi^�����������J�4%Q\h���l��}����~B;��a��d��U�p�������Ke���7���O0���f�)��������g���Xi��L��=���D�V��(N�tw����fC;�1m4�Q�4G�*}z>�!�c�4+�p�i�"���N�hv��d[i:$��?��V����Gm��������j+��v���4R\���|��}�a���E�)����i��I���b�Y�]�|:[n�]�����YP��������e�
���Xi���iu��p=C�v��ys�i���h�,o�3�< ��ki�4?�����H����>g����dG� �(l,�����,ih���l�v847�V���{��V�����_�����B�������/�������� �����������Lk�c��8<������ �����r�^�d��/���������^�d��/x����������� ���V��������Lk�c�������C������Yyhl�g�zS���f]���g/`������ux
j�jz9�2t����'��������u�s<���^^�>JC���|��{y�L�]�?���_���P�^��a����������r�e���Y�O�r/Oc� �����>�����}&���k��
,���0����f]���������6t��Z�a�����{9�:t�����|�����)]�e�:,�^|�o/`�C�m����_K����u�f]���/����g$��>]g�y_����2��j��Zy�cS�CynV����60�6�����f��60U���d����A �>3�e��j��oPK�X���<+O��K�R�K�����80�8��d�
]gK��&��'�w}��{y�Nh�.�:,�Z|N/`
C��d]��J�/n�Li��P���h��*���]�u��,�d/`
m���Z�a����-z9�:t]��uX���Z�^������+>_+����u�Z�a5������:t]����Za�o����
]�V�:�X���^��]��u�o_�{�^���K���f/�5h/`�C��j]�o����0����f]�/b�"o/`J��u9X������#��La������U���I��4t].�u��n�o}zS�.7�:|+��w*{SnC�����;-��E/gZ��+����,��@/`
C��d]�/N�{S���:|)�x�����u�Y��+�����������b]�|}����3-C���a���<�}&�������{y�L(]W�u"����^�T����uR��S����nC����q��1Q/gZ��k�����L/`�C��l]��j�X�0���Z��C
�xn����um��C��\S�����-��9���
��������XO::"������0�!� �@b����Hb=�H�����Db=�D�����Lb=!n��-N����z^�aJ��p���Q� 0V����7�Y
07����_]�nT-h1�7r r��az���26�����-���� d0�D-��m]�P�+&q "Bk���E�@�����jA�vl89 �
0P�+.� �=�.����8 ���jy�$@D�b�Z^����^-��
'lv��1R�+Z\d��[$ ,B�` @"t�J-�����]l��W�� �K������������� � �E�b%�XI,W��U�r#��H�6��M��Fbu#�m�j�������V���\+��Y~��R��EW6<�X
$VU� b%�X�$�"U�(b-�X`�V����������8 ���%jy� @F�b�Z^1���X��W,� d�&�h�WzT��+9 �� e\��],S�+Z�f��1���Z0����F-�X���M[�������J@�1�U����2��b �#t�J-�����]l��W�� �u�&���Wzl����9 ���8 A��jyE��l89 r =Tq B>BC���=��������ALp $t�D-��� ]�P�+&q �ABk���E������jA
m89�.� D�\�� ],S�+Fq BEB����/�pr@�� ����� ��&���Wz�h��m% x���*@I�b�Z^1�M�X��W�� ��.�Q�+Vq bKBC`��=���F���
7�:C0m�Jb=�����Wz�i��(�L� Z�i�#��L�#UZ�i���LXUZ�i�3��L�e�� ����dG$��Z�L^G1d��XIL�L�H�g����Z0J�"�$t��Q������$;"����`�pr 2I`��W\�0 ],Q�+Z�i���$��Z^1�`�X��W,� ��&���Wz�i���$��Z^q �$t�D-��0 ]�P�+&q LBk���E� ����X�jA0m89`[�H,!&��`�X��W� ����L@b�j�,@�I�b��b �$�?#��-/8�6|t�e��XHLp-"+��Jb�R�`�"���Fb�Q������O�|�1��8��Fo�n��>+�Qh�(����}�� �;CJ�bi�j���X
$f��K�jA�Bmx$�I�E�,Q�Z"�6z���^-�Q�
�d�&0����PBKd� ^BJ�b�����K�B ]��yK�F����Wz��+9 �� d�\��B ],S�+Fq �PB������pr@�� d���� D��&���Wzj��i% ����*@J�b�Z^1���X��W�� D��.�Q�+Vq �PBC���=
��@����b�A�(���
��b
%t�F-�hQ�
'�F@���=
�������}BLp
%t�D-���B ]�P�+&q �PBk���E�(����}�jA�Bm89�.� d�\��B ],S�+Fq �PB����Y�(���6jyE�Bm89�n� d��Z��PNh+9 �'�Wq �PB����Q�(���*��b
%t��Z^������^-�Qh���,
%�h��-
��+��t�#��^-�Q�
��M`$&hQ�
�$��M`�T-hQ�
O$��M`MT-hQ�
�$��M���Z��P^H����}�jA�Bmx��nc%1A�Bmx#��ns�j�(M�(����F���bx# �����Wzj��H7��Z^q
%t�D-���B ]�P�+Zj��H7��Z^������^-�Q�
' �jy�E�(�����b
%t�B-����B ]�Q�+q �PBC���=
����m% ����*@J�b�Z^1���X��W�(����J@��j�*@J1�>�j�!
���,��Bb�k�XI,V���c��H,7���s���X�Hl��Z��,�$41$��ZqYD,�$VK+U�U�R �H��LA�J$1;���"UZ�i�����X�jA0m�� �$�����`�X��W� ��.V���8 &��5jy�"@�IhbH,{������J@b 1�U� ���2��b �$t�J-���0 ]l��W� ����F@b��=��������XBLp �$t�L-��0 ]�R�+fq LB����8 &��!����`bx �@@b 1� @�I�b�Z^1�`�X��W,� ��&���Wz�i��e! ����"@�I�b�Z^1�`�X��WL� ��.����8 &��!����`�pr@]�H,!&��`�X��W�� ��.V���8 &��m���U� ����X�jA0m89��� $�\�0 ],S�+Fq LB����Y� ���6jy�*@�IhbH,{����oLJeX� ���uX1����]�H^���J]���-�HVz�0(yn��������qT���s���K�_i��e�~�;��*���������w$/U,��e�;�~�;��p��CP��������mT����������������=�<��m�q�'w����3{���p�s{I&J��d�s{1&J��X�s{&J��L�s{���<���H������^���=�id�0�8�K�*�=�Qd�4�8rK�*�=�9d�2�8BK�*��`�6�8K�
��V�rg�������c�{��9�=����c�{��9�=����c�{����=����c�{��y{%J����/D\��|�������������J�P���;n<l�����+�*��������Q�6*U��F��3�i1"�$����C,�9��RZ�T1�J)�R �R T�G�Y��Q�E*U����;�/��d���G������
Q�8v�������
Q�8v�������HQ�8v�'������Q�8���;�Ol�d���/{���q�q�(U{����y�q��(U{�S��u�qD�(U{�#������Q�8���};�O�d�{����q�q$�(U{����y�q��(U{�c��u�qd�(U{�3�����Q�8��;����d����e=����G�R���=��\�G�R���=����G�R���=��Kk$+=�����uc�#�C�����uNc�#�C������u.c�#�C�����unc�#�C���������64��p�;������T�~���w�����P�8���w����H�P�8��'w������Tq�q��v��F�J8��gv�����P�8��v����H�P�8���u������P�8��Gu�������Tq�q��z����J8��f3�fw�d����L3�����$�����z���~6<�bH��1���E6<�X��9R���6<�X���5Q���6<�X���[�jA� mx!���uDv��=��uC����- ����z����-�����X7��� ,Y$41�x�Z�#AN@�����8 K ],Q�+q �,�X��WL� ,Y$t�F-�X�X�Hhb��z��'�6�����q �,�X��W� ,Y$t�B-���X�H�b�Z^���d������jAm89`[�� &���d���2��b`�"��Ujy�,��EB����8 K !f��^-8��6|t����XHLp-"+��Jb�R�`�"���Fb�Q�`n"V7��mUVv�-Y$41���ZqYD,�$VK+U�U�R �H��LA�J$�I�E�,Q�Z"�6:���^-�!�
`�#0�-�������Q-�X�H�b�Z^1��d�����b`�"��!h����Yb�J�+9 Y#�Wq �,�X��W�� ,Y$t�J-���X�H�b��b`�"��!w���a�pr@�����Z^�RLNH�����Q�%��.V���8 K ]l��W�� ,Y$41���Z�M���H"!&�X�H�b�Z^1��d�����b`�"��!�����n�pr 2K`��W\�X�H�b�Z^�2NN(��l��I�%��.����8 K M e�������B@H 1�E�%��.����8 K ]�R�+fq �,��F-�X�X�Hhb,{��g�6��Vr 2K� �� ,Y$t�L-�h �
'�L@r�j�,��EB����8 K M�e��(����-�$�h��-���+��L�#�^-��
�2I`$&h�
�$�3I`�T-h�
O$�3I`MT-h�
�$�3I���Z�L^H�g��X�jA0mx��Ic%1A0mx#��Is�j�(M� ����F��`bx# �����Wz�i���$��Z^q �$t�D-��0 ]�P�+&q LBk���E� ����X�jA0m89 �$0P�+Z�i���$��Z^1�`�X��WL� ��.����8 &��!����`�pr����XBLp �$t�L-��0 ]�R�+fq LB����8 &!�,���� ����L� Z�i�+��Jb�R�`�"���Fb�Q�`n"V7��mUVv���&���W+.������Jbi�j���X
$���@��)�X�$V"��H��%�XK$�FXb��=����,�r��"@�I�b�Z^�LN�����I� �����b �$41$��Z�L_�q% ����*@�I�b�Z^1�`�X��W�� ��.�Q�+Vq LBCb��=��������XBLp �$t�L-�h�
'�L@b�j�,@�I�b��b �$41$��Z�L���H,!&�0 ]�P�+&q LBk���E� ����X�jA0m89�,� $�\�0 ],Q�+q LB+���`�pr@)� $��,� ��&���Wz�i��u! ����"@�I�b�Z^1�`�X��W�� ��.�Q�+Vq LBCb��=��������XBLp �$t�L-��0 ]�R�+Z�i�����X�Z��`��^-�f�p��k����&v����iD�w��^�����}�&���Q�Ll�w��^�I�Ll�w��^��H�Ll�w��^��I�Ll�w��^�XH���ObZ��(�&6�;aB�Vl$�i�<6�W+n$f&6Tr �NT6r��}��&���<���@@��jEr������;Q�H�
9 y'��`bC# �D�"9���iZ��`bC �D�"9�LlH� ���V$x��
������ 0����w�Zp#x��7��mB�> 9�Ll�� ���V$x��
������ 0����w�Z��&6l� ���V$x��o�G� Q}��C��
��X,T�XI,V���r�j�Fb��Xm$VU+n$V��87�Upl�!s����XZ�Z1�X
"V��@����J�I�E�VL$��i��nB�>���C��
��%��i=s��DM�������9bC��ED�jEjZ���Q�"�D�"5�g�}��&�j�u<m�#6Dr "JT+�<s��L@D�jEr�g��P��(Q�H��6r "JT+�<s���7�U���#6Dr "JT+�<s��L@D�jEr�g��P��(Q�H��6r "JT+�<s��8�U+r�g�����(Q�H��
9 %���9bC# �D�"9�3����Z���9bC �D�"9�3GlH� D��V$x��
������ ����Q�Z���c��G� ���� ��!�Q�Z0�<s��L@D�jEr�g��P��(Q�H��6r "JT+�<s���8�U���#6Dr "JT+�<s��L@D�jEr�g��P��(Q�H��6r "JT+�4s�� ���� ����b+0 ?n�:C0m�Jb=�����Wz�i��(�L� Z�i�#��L�#UZ�i���LXUZ�i�3��L�e�� ����dGd��Z�L^G1d��XIL�L�H�g����Z�L��X�$�u�j�,�
LBC���=���� d��@-���������b`&��jy�$�
LBk���E���&���Wz�i���$��Z^q`&��%jy� �
LB+���`�pr 2I`��W,� ��$41d��Z�LN�Vr 2G� �� ��$t�L-��X�I�b�Z^1�����6jy�*�
LB�Y��W�
`�$0\���Jb��X�T-���Fbv���6�� ��o$V7�6��� [�Ihb0{����XXI,�$�V����@b)�X T-����Hb%�X�T-X���Dbmt���Z��P>:�N` (.� ��$t�D-��X�I�b�Z^1����������6�9 f��4�Wr@\�0!&������2��b`&��Ujy�,�
LB����8 +0 Mf��4����J@� 1�U���.����8 +0 ]�R�+fq V`��F-�hi�
'��� �Wz����9 &��8 +0 ]�P�+&q V`�X��W,� ��$41��Z��PN(9 &�q V`�X��W� ��$t�B-���X�I�b�Z^������`�jAOCm89�.� �\�X�I�b�Z^1�����*��b`&��m���U���&� �Wzj��m% ����*�
LB����Q���.V���8 +0 ]l��W�� ��$41��Z������`~4��m�`����z&��e�� ���Q�$0� ��G��$0G�� ��'��$�&�� ��g��$p�T-h�
/$�3��H,{���6��b�$������6��X�$��Q�`��E�I�bu�jA01���IvDb��=���� d��@-���`�X��W� ��.V���8 &��5jy�"@�IhbH,{���6��L��q LBK���A� ���
��b �$t�F-�h&�o�����X�jA0m89`[�H,!&��`�X��W�� ��.V���8 &��m���U� �b�X���C�i�GX& ����"b��X�$�+U�*b��Xn$VU�&bu#1;���mT-hf� ����X�j�e���XXI,�T-VK��R ��Z0+��J$��Z�Dk���� K,{���6|t�e��@P\�0 ],Q�+q LB+���I� �����b �$41$��Z�L_�q% ����*@�I�b�Z^1�`�X��W�� ��.�Q�+Vq LBCb��=��������XBLp �$t�L-��0 ]�R�+fq LB����8 &��!����`bx �@@b 1� @�I�b�Z^1�`�X��W,� ��&���Wz�i��e! ����"@�I�b�Z^1�`�X��WL� ��.����8 &��!����`�pr 2I`��W\�0 ],S�+Fq LB����Y� ���6jy�*@�IhbH,{���6��Vr K� �� ��.����8 &��Ujy�,@�I�b��b �$41$��Z���/��#��;`�*�:���;aB�V\I�����Z��(�&6�;aB�V�$f&6�;aB�VL$f&6�;aB�V�$f&6�;aB�V,$ff��G� ���u� ��0�W+6���x����7� *9����9�����Z��`bC T�>"9�LlH��Jw�G$x��
�P�N��� 0���*� ��f��G� ���� 0�!�� ��&6$r@�;�#�<���Bht'|Dr����������<���9�U��&6Dr�Fw�G$x��
������`bC%lt'|Dr�����6�>"9��}�=BNh���Ll����N����,���\I����H,7����N���Uv�=BNh��v��!�$�7�$����@b|�z�Hb%�X�$�7�L$��i�rB�>���C��
��6����i=s��DM�������9bC��
|�z@jZ���Q��y= 5�g�}!'�j�u<m�#6Dr@����<s��L�|�z@r�g��P��o^H��6r@����<s��9�U���#6Dr@����<s��LH|�z@r�g��P��o^H��6r@����<s��9�U+r�g����QnS$x��
���6Er�g����QnS$x��7�rB�> 9�3Gl� �(�)�<s��D��r�"9�3Gl(� �(�)�<s��F��r�"9�3����Z���9bC xD��0�<s��L��r�"9�3Gl�� �(�)�<s�����6Er�g�}!'���<s��H��r�"9�3Gl�� �(�)�<s��J��r�"9�3Gl��QnS$h�h��Z����o_�zm��x]^y���^os��z��Z^s�p���q���^�0�a��
�?u����y�a�e�w���o�N~����������_������z�������?���[~��,�"xyy����>����y�����|�G�~���~�n�\ ��B������|�����qU>]�\n&~�Z���S��w��^��C��2�����;�����A��/���&}��������'{_�,\/'����*w����8Yy��Pg}���}1����)�l_����?v��b&��"��G�|qG���/O����}���/�z�/f�W�=�qC_�+<������b���)����w_����LX&}����������rG���?W�����LD����w������ok���?����t�������{�G�~V����(}B�l��G�������g\S���
�5e�{�5e�}�\����/s��S�3�)'{_�,l}1�}w;=�S��.?���"�Y_<v��b�{����}q����
_����6��kk�����k��N������_T�o��~�^��&�q�$�>�$3����1��I���\a?y�u����?�|F_\x��]`�����rQ9Wx��{��M��I�T������}1�}w�+O��m�}�|:�=#�:Yx��s��|1�}�����O���N��o�B��_=~�j}q����]��&��S����&�S�SnNj�Di�>�Nu���8Wx��{�����N��I������jl�<M��NE��gL6N��\a?y�t�:y���9y�I�������3���8����C_�~4 ���QXO_?q��&���^�y�I�2 ��}>���q�8Y���dao���Op����gV �M&)���g�S�3�����&�'��f�{�f���)}�&����g�S�w�}q����
1�T���8_���)���L��o��E���N�m9Yx��s��|1�=!���|���M��o��E���\G���\��|1S>�|1�=�|�-��O��S�3&�'{_�,<������u=w�O�9��4X{:�����
}q��]G��WW?�5�]�3�i��}�|,:�=#�8Yx��s��/f������������wB���
���b��� _��,<�����3�����?���m�}�|:�=�|q����
{_�t�� =>�H���z��e�.1|6 ���������n�K��TX?�����>q���;����e�r ���2q����\t�{���la;��-���\����|��/�-[�E�O��D��E>wu�>Mq��x���OOMO;�������T����d��#N����D��/O�����v>,[� ?��S���q��x���'t�T��I���������?��������c��]�BuY�\�������T����=�h�X����]z����<�l�N@����E�w�~�~��X��&hS�3�(�����\���3~�[���S!�����M���'�3=Yw��Sum
�DWoH�8a����wJs�v~�����s�(������o��'��p�O����D������D������N�f�g�c��N����b"{J�qO��~a9����p�D���������|��'�s��OB�3�s��J?����i=���=O�D��p��}r��]������>�u��9��OI�~(����Dl&z�u�\��N��~����������'���$j{�&����~8Uw��Su�y���=#;WxHH�r��=�(p*�����t��%=W�^p�zKz��[�nH��n��>/�]�}�cO��3�����������,2�i�L��[���;m����k;������j�i�=�l�dOX�s��p�8U�&�O���������X���������)�Su��8Uw<GL��{"�j?���m��=hW���������������~�wn�~v��]����e��=g�d��z�����{��=�v��=%��Is�mH�����5~3�/���<'�q��p�� ��M����x���g���Q�L��s���CG��������� 1���sD��mO��3�3����}�#N}��9b"����9�?�/��M�,�{:����o��;t��G�9p��~�_=?�� yN.��c���q�L��6��zG��k1�=���L��=�#�,{�������su��8Uw�j��O�Y�d�=������5��g�3�w'<�v�������������G�����Q����g�3�'Vo{G��;t��'���dOY^uO��4;o���>�<�=eq�����zGLd�]Z���U1��� �&%��}}�|f9�=cqO��s�=��~��T�zr�7�L�����_xJ:�__>�Y�d���<Ww��;�O^5f���k������F)�����3����/��:�����/�^c&|���L����8G�c������L��?X9t���CG������� �gQ�Y��tf9�=cq��w�=�'�>g��-�]����?�j8F__=�Y�d����=Yw��;�O�9>��1�=i}DM�����3����w��t�Y�3�s�����b"}��=�����9�����MN�k9f`_=]�d��%��N����G��~���7&o�����������3�3�!?Wwh�Su��1�=��t.�����;�-�����1g�g�6��������`3�S�?� ��a�=��'����8Uw��Su�#&���#� �0�ly����1�=c����CG��}�#&��|�5������@���s�����su��8U���G�����M��7g|��c:�����L�� ��su��8U�OS��:[x��m=�c_=j�d�XRs��w�L���/!��{�%d.L���.������
endstream
endobj
15
0
obj
15976
endobj
16
0
obj
[
]
endobj
18
0
obj
<<
/Type
/Page
/Parent
1
0
R
/MediaBox
[
0
0
595
842
]
/Contents
19
0
R
/Resources
20
0
R
/Annots
22
0
R
/Group
<<
/S
/Transparency
/CS
/DeviceRGB
>>
>>
endobj
19
0
obj
<<
/Filter
/FlateDecode
/Length
21
0
R
>>
stream
x���_�,�u���1O6�K�� =�*+�V>Z�(��,����z0,PaW�d�����8'#*g�r������������]���/���r���{����??���K����_��������q��m������>�-l/[�C}��������������4x���}������o�����6������<�=��/�P��������x�G�����m��!��!f*�(����_�9<��������pT�G%^�0^��q�����B�x��x5�Y&�����?�����/�QM �,��}�����M Y�����J��a���,SM����d?� ~xi�z���}�{��n����j�iM���}F:�Y�����#i~����8t��o^~�������������
���o�6���p�����X� p�������'T������t���������?��?�����n�O��w����|��l[{�t4���{����������g���^���o��=~qk������������n��W�R�O���G���������|�zz�o�����x���_���{���������_����]��I����/o���������0�������G{���z&���g&�)�Wv�y`��;���W-~l-��_������e�'���o8}����~�ShN��'�
}�Dz��}z���TS�x���6��nvRq��s�q�L/m�B2���@�I�N�����q������8��%-����.�(�z��_W�A�4�4�~ T�@��>�^C�s�_��u�qo�����`�Y��`'����}��c�=������r���m�z��p����4��N����G�CJ���:M�nt����;�}�����4��'�(i��D?�������Vn[�U����i*�c���R�[}">v������<��G�R��]`�����������m�]
!M�����{{�i��9�>���'&?F��m��6��3MM0�y��!�4���4GS�}`�`x����1��b� �B3����'x����=�N����;��O4�����C�e��4��ir9��j���L�3����M�1�6�n����ivc,�_=��!�O-4������|�xw������m�<��G�@���]`� �q�M���qS�4������>�J�?B;�J!7��<�v?]���>�-�y:�tb����������N�����3���W%��0y�O�i>q���@�|����w�]�iv%�t�}}��-1w�^�4���|���mT�4��iBm��������+���y:-�tZ���H�/�h�1���n?�%n���(��w���h�=��y���iZ��[��FS�����61x�6�t4�4���;-:��1XPv��L;hZt�3L��P�h�a��f�����i� `�%���+�����h��?b��b������GJ�^M�K������C���E��-Cb�eHl��P���Z-b_6Z�@���r���(-F�YuZ}(�r��������d��E�1X��"d���);-A������|�<{k��V%��6Z��?�D�6Z����%)�BD������F������M��*)��Dq���,�S�E��>�J��t^���q��M�)���D1�"��wg_���>���$�e^C�w�R�K���cA��B�� wZ�(N���B�i�r�M/Z�b�[g�GC�s�i���9�
Ep��bn'[�@K�}n��&���`D�P�'��Qr�E�b�E�g���H��}r��%��V)XV���tb���
T��V&������iir�O��ZD1�J���k�8����ii
`���b>E#o��s���>��� �5���4(��\hY������T.�wZ�h�)����y;BZ�@c �0�;�ojZ$��>�h1r�O.��C1����l���"� FZ|(������g�#�D� fZz(�����o�������7��&Ek��i��8�rm��i�q�O��rC1�+��q��3��I�f�i `�%�"�o���y"+�� ���tZt(�������GL���tZs(�����c��9�fW7Zsb�1��X������������M�!u�U� ����s������n�9�g�h�������`|?���C��Gj��"�pZ����~�k~���t9���8~M�K]L�r�'��s�D��V<����{�����H��Zh���~j�S�~��4Z�(��V?�w;FZ�@�h��X������v��9���i����)�{��49�~�m��� ��(�e��UI�+��@���m�u��>�D���5���/;tZ��D��i_t��/%������ ��
-:�A������}�SN)$�g3�H+��P���9W�����@��N����'6'��F�����Zb�����<��@K ������=�z�@�U��b�H���w���B��=��_�����X�������`�� �#-�L+ �H����D�_�gs����i������l�tn�3���J'c�L��������:=��N��fD'����X1���4��vZ}����{����� Z���z���mZ�t
�N�g���m�4����mn=��Y����NH�SS;XZ@b v0��~����� �#����n;DZ� h�m���ys&�� �L2��ke�#��X��&CK��im�8�o������l*-��<�Fb�=�����WZ(.��V��+�R@�;-+o�6g�KKh ;E��C���O��Z�wZ��)���KA|ZA����������c� ��3>F������>�in�dqz�0u;�@3I�f"�����.Mo��$m4������S3I�$m4����-2�X�^Mw��!F�O�4��i���Kr;�H�)���2M@�����r��H���D���& �^�;tZ^���4��h�-�{�9 ��7F���&�i�}^[��j���"#����l�r�����������������[�|�����d����yS�����Wv��`��>�\b;�IU�c���'�v���[y�}�F�j�f#X(���Qo*;�<�|n�1�'cE��
�=������b�=~�iz�Iv:;�HggA^|���g��GL���9F:?�{\�]�tF����xH�#'������D��>��c���"����������q.������<�������������P��~� ��h�6Z���[u�����[!���~s�D���$����������@��Nk����}���]�G�-[�N�E��_���>=�a�M��m�)�:E������q����D��h�"8��'��[1-W��EZ�(�s�3=�]�lh�����0�������?���.4�Xh���-����9��c��T�v��V������2-��yUZ)�W�
;*Z� Xi!�8�������X�����`��=}l���/��:��PSy��|<�9=�7
��6����w{�����
���}L��#�<�(g
i*����z��L1O��X�x".��U���\��Z�|<r�i�Q�T�T�7+Oxz�(`�����;��<U��sF9S�����<v+�}.`�}*/��K�������Yy���osS����������Q��a��ux�$�S��i�\w<����<���3�4��x��Gy���gBer��p����(��������>����7�L��1�\�����o=����u)��p+z�{�GS�\���w|�]x0��ui7��n����Li�\���7,��u�3��u9��pgp�LGS�\�������s0��u���p�k��&GS�\�wsn#
~_�Q����u���?���<�>
��J4���������8��dsn:~��(`���J3��.������6��tsn�~��Q�T������p�Z��F9�6��Eb/��2�L(M���������>*��j3�����7���6��vs�
~'�Q�T������p[N��<F9�6��%s�� ~��(`J��Z1��N���H��2����:�<�>��������`��M�?��Lar��u�"�'���)N����w�tz0��u{5��3����:�n��u�|<�'�G��O�;>y��_�q��P�\������,q0��u=����j�O�FS�\����f�(l0��u����ya�����u�d��?�u�a\�}F9��M�)Zy�oI�g,��)���$+/��[��J��[������������+�p���GS���������(Ou.g��T����f���L�M�e���[y����O��[y�V��\���u#���__15�R�\��.�W_Z�7
���:|Q��<���3�<��D5%�S�4
��������M�Q���u)���M��(g
��R4�!b�r�Q�'��l�Cz�HAf� �=��C�w�"��.�hA��0���*}U���"6|#��{ ���-$����F
r�E$G�����4�Y&���-@����FB���-N����F^���-\����Fz�+UZ�b���,e ��Q-���
�g1$+������06��X�$�;U�.b%�X $�U� bm#���X��Z�I�S �����p� �3�D�W����X!�+&� �;�.����E: a��u��b�@�Chb}F���@6�: )0��7� �B�.V���I: !���dy�*������jA�l8u@��� &�'�X&�+F� �K�.V���Y: Q���dy�*�����9�jA��l8u@ �� &�J�X&�+F� DT�.V���Y: ���u��b�@|Ehb�F��Y6�:�n��� &�I �"t�B�WL��]����t b/B�dy�&�����jA��l8u@���ALp�@@F�b�,�����X#�+� �g�&��lTz�f����#Y^1H X#t�L�W����]����t B7B����U: ��!|����p����AL0H �#t�L�W���]����t �;B����U: A!�,�;��H���`�0m$&h�
�$�"��H��)�XI$V��D��%�X�$�2��L��-�X/$��� pTz0h�����*� nU�R#��H�4���p�������x��*;���e��I�u�����O�X��ys� ������25����6�z)f�%�����K2 ]l��Q��K�5 M�������S/�@��xb�Az �'��ej�(�� ���*5��E���!!
%�?���s��$E�B1|D��.VUZj�7�&p��Z��PIl��Z�yTNQ�
O������HL��P�Il�����Z��P^Hl���Z�Z��P^Il����R��E�6���H7"������}C� �;� Zj�;��Nb�S�`�"V��@b-P�` "�6k�����&b=�X�@�9�=
���H7��,��I
%t�B�WL��B ]����t �PB�dy�&�(����}�jA�Bm8u �M`"�+n��B ]����t �PB����U: Q(��!�����p� ���H�W�(��S�H����Q: Q(��U��b�@J�b;Y^�J
%41d��Z��PNPu �O� � D��.����Q: Q(��U��b�@J�b�,�������Q-�Q�
���.`"�+Zj��j�@��j�$�(���Y^�H
%t�N�Wl��B M����(��S��: �'�7� D��.V���I: Q(��5��b�@Jhb�>G��G�6�: �&0���t �PB�dyE�Bm8u����}�Z0K
%t��,�X�����Q-�Q�
���: �'��t �PB�dy�(�(���*Y^1K
%t��,�X��B����Zp�Bm���n�Fb��&b)����X"UZj���Db-Q�`I"�2��Lb=S�`�"����,�������,��Jb�[��H,5+��S���X�I��T-Xvk��Z'���Z�qX�Ihb���� �t LB�dy�(� ���*Y^�LN+u KTV� ��&��rTz�i��R�@b 1� � ���2Y^1J �$t�J�W� s�Uv���7��X����h&�� ���j�jA0m�Fb#��UZ�i�#��L�@K,�j�)���i�L� Z�i�3��L�3UZ�i���LXUZ�i�+��L�W�� ��7��@$��Z�L��b�$�q'1A0mx'��I,w��]�J �H��,A��Fbm#��Q�`�D�G��H,G���6�: �$0��-�����$��,���`�X#�+� ��.����M: &��!���`�p� d��D�W��`�X!�+&� ��.����t LBCb9�=�����$��,��`�X&�+Z�i��r�@b�j�,� ���v��b�@�IhbH,G���6�:�� $��0 ],���t LB�dy�,� ���:Y^�I �$41$��Z�LNP7� $���`�X!�+Z�i��j�@b�j�"� ���:Y^�I �$41$��Z�LN�6� $���`�X!�+&� ��.����E: &��!���`�p��=P ���`�@�I�b�,��`�X%�+Z�i���J����U: &��!���`�p����XBL0H �$t�L�W��0 ]����t LB����U: &!�,�<�� ���`�$0m$&�m"�"��Hb%R�`�"V�����-Q���6<�X�$�3U�,b��X�;��Q-��
�;�2I`�$&�UK��R#���Z05+;�����N��e��I�u���w���&��rT+� ��.����Q: &��U��b�@�I�b;Y^�LNw� $��Z�LN�u K� � ��.����Q: &��U�����{�c������V�8��<����U�L^*8��1�����x&/U�f%�-�����T1�JZ�����L(=cr�)�<�|g�R��_<�<.{g�R���_<�<�yg�R��{`<�<.xg�R��+a<�<xW�3Y� ���78��R��Tq���'�>+�N��%�J%�R�RT���J�L����7*U��Rg��m�82�Qz����IN��`�Tq������q��(U�=�i��6{�%Jg�{9��Gn�R����C��d?���p�����q$�(U�=� ��2{q%J�oY������qd�(U�=�����#�3Y� g�{�88�GJ�R����:���Q�Tq��G����q��(U�=�y��}�8�I�*����`���������=ig�#�D���
����$Q�8{�3��u�8I�
�w�z�8��G�R����.�?l;���p��G����q��(U�=����2{!$Jg�{�8��G�R����(���?�Tq�����o��d�'�=�Y��4{�#J���8��G��R����"n��9�T��A�#���W$g�����pp�=������=<�g�#iD���qO���;���3���p�>{#Jg�{fx0���LVz�������.�Tq�������qD�(U\[��:{�"Jg�{N8x�=�P���}�>��V�L�gGN8y|J�mVJ�*�Y)EV*qV*�J��T+�4+�D��yVj��z��z�R�2+u������������Hpp��R�T��f%}���Y�4*U\7���g����q�1����qv&�>�*����np�������3=�\gg"�C���L����3��Tqv�v����d�'���i��8;�JggzT78��D��R�������G"/U�����^b�nY$��0�
-���q�"���@��������F��7�����G������S�g��$f�0&I��-��.�3UZh���dXUZh�+��p�W��$��7��@$x�Z��@��b���q'1���X�$;��N����X $V��@��%�X�H�m$�7�l���Hb�: ����l��S �&���&�[ ]����t nY$t�F�W����S �v��b��-��&�|oTzTh�� Y^q��-��.V���I: �,��N�W���e������jA�
m8u@��� &�p�"��e��b��-��.V���Y: �,��N�W���S��: ������S�@��b�A: �,�X&�+F� ��H�b�,���p�"��u��b��-��&�$pTz�h���F�0b��t nY$t�B�WL��e���Y^�H��EB�dyEm8u@��G��g�6�:�m��!&�I��EB+dy�$�[ ]����t nY$41���Z��FN�� ����e���2Y^1J��EB�dy�,�[ ]l'�+V� ��Hhb�G����6�:�� ����e���2Y^1J��EB�dy�,�[ ]l'�+V� ��H1��j�)���sX�L� n���Hb)�X�T-����Db%�XKT-X���Lb-�X�T-����Bb�.�@$��Z��I>w�E��TILp�"���Fb�Q�`j"Vv+;�����.b��X�$�;U6� �e���U�j� �[ ],���t nY$t�J�W���e���v��b��-��&��rTzj���k#Y^1H��EB�dy�(�[ ]���-
��S���?&`Y��>LB���-�����L�oT-h�
�$62�-�<�� ���I�2I`L$&h�
�$62I`�T-h�
/$62I`-T-h�
�$62I�^�Z�L�Hld��X�jA0m�>�!����-�����b'���Z0v+��J ��Z�k�����F��m�I�S ���`�p� d��D�W��`�X!�+&� ��.����E: &��u����6�: ��@$��Z�LN�L�����t LB+dy�$� ���v��b�@�IhbH,G���6�: � $��0 ],���t LB�dy�,� ���v��b�@�IhbH,G���6�:�� $��0 ],���t LB�dy�,� ���:Y^�I �$41$��Z�LNP7� $���`�X!�+&� ��.����E: &��u��b�@�IhbH,G���6�:�m�H,!&�I �$t�B�WL�0 ]����t LBCb9�=����{�@b 1� � ���2Y^1J �$t�J�W��0 ]l'�+V� ��&��rTz�i���I#Y^1H �$t�L�W��0 ]����t LB����U: &!�,�<�� ���`�$0m$&�m"�"��Hb%R�`�"V��Db-Q�`I"�2��Lb=S�`�"����,���`���,��Jb�`��Fb��XiT-�������Nbm�j���X�$�:��N���;�LBCb9��t LB�dy�(� ���*Y^1K �$t��,�X�`��Q-��
�@& �dy� � ���2Y^�LN�2u KTZ������ xi�3�f���LlW��^-��Y��
�J���7� ��0�W+F� ��``���i�LlW��^��I�LlW��^�XH�LlW��^�XI�LlW��^��Hlg�����V}�}� �Nbq�j�Nb��X�$�;U�@b%�X$�U+n$�6�����#�u� <�Mh�'�� u �NT+Rx��
�: y'��<���F�����`bC�@��jE� 0�<�Mh�'�� u �NT+Rx��
�: y'�+u����S �D�"u��c��&��Rx��
�: y'��<���L�����`bC�@��jE� 0�a�@��jE� 0�<�Mh�'�� "u �NT+Rx��
�: y'��<���J�����:�Ll���;Q�H������ ����`bC�@��jE� 0��P �D�"u������w�Z�:�Ll���;Q�H������ ����`bC�@��jE� 0��P �D�"u������w�Zp�� sl�#��V}B� 0�!R �D�"u������w�Z�:�Ll���;Q�H�&6���;Q�H����'� ����`bC�@��jE� 0�!S �D�"u���P��w�Z�:�Ll���w�Z�Sx�yl�� Q}��� �Fbi�j�Hb)�X�$V"U+&+I�Z"���Z1�����3��L����:w�=Nh�'�;`
0�!UK����&b��XiT���X�E�w���c�M;e�����(Q�H���2�%����9bC%�"�D�"��3Gl����(Q�H���ql�s��V}B2�g�����(Q�H���2�%����9���^�H��G��G�cw`�`��m�`b�����j�jA0m�Fb#��UZ�i�#��L�@��j�)���i�L� Z�i�3��L�3UZ�i���LXUZ�i�+��L�W�� ��7��@d��Z�L��b�$�q'1A0mx'��I,w��]�J �H��,A��Fbm#��Q�`�D�G���G���6�: �$0��7� ��I�b�,���p&��5��b����.����M: w`�2�Q-��
�@& LdyE0m8u@J��Q-��p&���dy�*�;0 M���� ��S�@��b�A: w`�X&�+F� ��I�b�,���p&���dy�*�;0 M���� ��S �F��b����.����`�p�����9�Z0K�LB�dy�&�;0 M���� ��S��: �#�7� ��I�b�,���p&��5��b����.����M: w`�2�Q-��
�hu 2G� n�����
Y^�LN�
u 2GT� ��Ihb�G���6�:`��!&�p&��e��b����.V���Y: w`��N�W�������9�jA0m8u@��!&�p&��e��b����.V���`�p��^��9�Z�J�LB�Y�xTN�
�;�2I`�HLp�D,EK��J�j�E�$+��Z�j��D�ek��z�j��E��sX�8�=���sX& L���*b��Xj$VU�&be'1{�?��T-h�
�$�:��N���;���$41��Z1H�LB�dy�(�;0 ]����t ��$t��,�X�p&��!������p���`BL0H�LB�dy�(�;0 ]���-
���80 0L�}�`b�0 ]��� ��o$62I��Q���6<���$�����L�&1�$�1����6<���$�9S���6����$��P���6����$�{�jA0mx#��IDb9�=����,�Lw���Nb��X�T-h&��@b%�XT-X������Fb}�j���X�$���X�jA0m8u 2I`"�+n�0 ]����t LBkdy�"� ���:Y^�I �$41$��Z�LN�L�����t LB+dyE01�R�J����U: &��!���`�p����XBL0H �$t�L�W��0 ]����t LB����U: &��!���`�p����XBL0H �$t�L�W��0 ]���-���FPu KT6� ��&��rTz�i���F��b��t LB+dy�$� ���Y^�H �$t�N�Wl�0 M���� ��S��: �%�7� ��.V���I: &��5�����S��: ���� ��S��: �%��t LB�dy�(� ���*Y^1K �$t��,�X�`��Q-��
���: �%��t LB�dy�(� ���*Y^1K �$t��,�h&�w���������L>w�e��������X�$�"��H��)�XI$V��D��%�X�$�2��L��-�X/$����rTz�i���L�*� nU�R#��H�4�LM��Nbe'��S�`�E�u�w�{�jA0�p��&��rT+� ��.����Q: &��U��b�@�I�b;Y^�J �$41$��Z�LN�u K� � ��.����Q: &��U�����qE`��B���Kmp�q%L���9����0�� �Zq#10�a\ z�b$10�
�9���N�&�)���q%L�����,���q%L�����,���q%L�����,���q%L�����v6�=BNh�'�g10�!�$�W�'�$���Nb|%�X�� b-�_ �p#���X�H���OI�K�rB�>!u�����"_ ��:�Ll(����OH�&64���W�'�� :u@�+�Rx�96�rB�>!u�����_ ��:�Ll(����+u����S$�>!u��c!'��Rx��
�: ��� �<���L��J���`bC��|%|B� 0�a��|%|B� 0�<BNh�'�� "u@�+�Rx��
�:���� �<���JP�JX�Qx��
�:�����<��9�U��:�LlH�����H�&6��JW�g�� u@�+�3Rx��
�:�����<��9�U��:�LlH�����H�&6��FW�g�� u@�+���`�
x����OH�&6D������H�&6d������H�&6T������H�&6��;] ��:�����Z� �<���H��J���`bC��t%|F� 0��Rx���H�&6���w�v� 0�
�9�]��p��)�����X�,����R�I�Pt�Db%�XK$�(:a&��E�g�����X��G� ���sL&6�Jb���6� J#1�;�w+���Nb�S5c�i��"��#��D2�g�����Q�%�i=s��J����/�L��#6�dZ�(����9�
x����OH���"��#��D2�g�����Q�%�i5s�G� �Z�L������W/�������_���/�7�?���
/w�p���z��m��2��w<��y��I���N��o���c'���/���������~�O�����#��������y��t;��B�G��c���������^~���}���|���?�����=~���8Y����x�p���.|�n���w��n�N�lk�/n�_|�w��o^�{�u-�����)<;���#�x���O��gq����Ku�����-�����_>�����'�>�M�xE�}<9���uG,d����~������w��wDoG��iG,d����q����Ku��k�#^��iG�p[���{O:b){� ��j���u����F+/����p�R����]����x��sv�B�������#.��{�R��_�;b)��%��a����v�B����Ku'G\���X�>������me_)��]�^Q��Z���o_>��){����<m�������M�=.������������}�
��qRV{|}�=����Y{�d/�.}U�Y{\{�f���%����gG��p�wO;b!{�
�Z�����#��_��O;��+����WO��K����u'G\������;�YW����wz����/�H��9#���hs)��w��'{\�;��R]�X�^s
�Xxv�~N��z:�\�^r
yE�� ���uG,d����=�\J��s�����WOG�K�+q��;�Z]s�J�����qrV�s��W\��x��z>�\�^���Vw����n���3���BV�_>���������s���%��Twr����������*���h�$���s���%��Ku'G\���X�^r]������}�|�������Z�����#�������XxrD����W���+�+����#��5G�d���o���XI_qOE��g����������N��T���}.�pG,��{����rN��~>�\��������N��T���}����m��������0W���5.��q��;b!���<�G,����Z#�s����J��;�.��q��;b!���'�����U�]W����}�|�����R�Z]����f���%��k�\x�tN��~>�\�^���Vwr�������E����wW�Br9'a_?`�d/q����#^�}�����5��_p)��s����J��E����#.�uG,d/��^��%�����0W�_^p�������t�|�X�^r��k��5J<�`_?`�d�x��Vwr�+�O����}�s��-��?m6;"�s���0W��8�R������wg��npp{,�n�n�)��}�|�������ku'{������J�����wW��e?�b�<�f�d�x�Z����N����yfp��O�����}�|����b�������+��#V��}�a�XK_������}�|����bQ�������;�G��������{?����9�7�
0�����X��_�������~�}���mi����[K�q�?����y��c)�tt����"��s*���a�J��~_2�_\�;�_\��g���E����5k�~N��y>�\�^�����#.�uG,d/���j��m;�b�<f�d����V�q��9b%{�#^��J��s*���a�J����ku'G\���X�^o�&|�#�9���0s%{�u����#^�}:�X ���=w�B�~z�:��s�����J�������#.������%�_-<;��n�{:�\����;�_�}�Z���uG,d�YG�"|�#���}�|~������ku����#V���8���~���H����r%{�#.��q��;b!{����r%}���~}��
�+�Kq����Ku��{���'�����7i_�������g�+�K���� �����X�~q�b��#��<���9�����r%{�������ku�+������/���e������3���\}^�;9�R�)�X _���������z>�_�>�Y�d�=�>�����/R�q���G,d/��|M�����z=�_�>�Y�d/9k\�;9�R]w�B����5�V�}_���tf������ku'G\���X�>w���#����S����n�{6�\�^p�q��9�b]8b){���yG���{>��!��I���r){�{����#.�uG,d�8k\.<;"���g3���%���N��T������?��C]={�lf����=�R�����#��}[������W�����+�O�1���{o��?�����>��p����t���:1���3����$o�9���8s){�������q��d�����}^~�����U��l�����f��u'G\�k'���7�].<;���W��8s){Axu����Ku��kn��wAT���-����K�Kq����Ku��+����~;���G���]���7���������O����:�w�l������_���"�#joH��]o��7���i�?�����O���/�����g��V�W��]���i���V���{^�����=��D�������p���a!�\�f�+�'n��PZ�}~������=$<�9V��=��������=]5����aW�O]#M�h�?>��{�B���Z����R���KR����S��}�����1W�?���t��N�����
_c���y�1��B���4��w���Hq�����+��h�b]��V��+�+ByU���F���G���B�������.����[��g(_=��|����u��=m���\�^�;��R]�X�^�Y�k��~u���1f
endstream
endobj
21
0
obj
15760
endobj
22
0
obj
[
]
endobj
23
0
obj
<<
/Type
/Page
/Parent
1
0
R
/MediaBox
[
0
0
595
842
]
/Contents
24
0
R
/Resources
25
0
R
/Annots
27
0
R
/Group
<<
/S
/Transparency
/CS
/DeviceRGB
>>
>>
endobj
24
0
obj
<<
/Filter
/FlateDecode
/Length
26
0
R
>>
stream
x���_���u���q������ ��F�B���(m�&5����0��`�P�}}w7*��LT��^� ��:��{O�l����,o����z��R����|x������������m)mc{q���?�T��%,/K���=��}���������_�����V���}>�������1<��������/�;�����~(��������x�GE����m��[��x�1S9F�����������1���Wm���QCl�x���j�c/��s
k�����U��2���x����}�^�I�j�g�����Wm79$�����*��}{��^�����7���v���>� �w�����v�W�����-T���3h�c���������T����x����������~�_������
����)���u����1�|��{����C��P��U����w��������_����������~�G���%��)/K}yw����_���������x�����������_��i���7V�_o~�����o�����*�������]���~�_����/^��>�o�����|����WI�G{�������������J;?����o���_������^���h�����^�����z&���f&�)��v�y`x�v�i��j|[k!�������eoo%��3��>�Z�[?�6�)4o���N�L6��������8����=~���c���G���1��;���j��^���"d�����>s]b�F�T=�u���:��L�j��vM��)i�/���n�����5��x��n?���O>
�n���{Lq�qO����j��}���j;~��y�!N�)-������������f����.�`A��~�&�_���}n�}�K�f�Z�aJ����B3�Z���r��p����,�W%�-���C��i �0XPz���m�����������hj9�\�����@�X���a�����=~P��n&y����fRWz��m�Gf����/4�&��������%��|zB5��j� ��f X����+��fi�m,��Q~��W������K�' �����m��Z�����.mk?!��
�]�l&��~��0x��Z^R?�}�k�Y
���.�*�c��q5}k�X�Ib�6�D�l��`�n��>X�5���Ls��&#���c���4��l��`A����;
���9�d.4����s�������K��Y��>:�������Th�u�) ��>�C�wM��}�;�k}�u�5���C-�������?���j{�?�a�6)Z#�bW���iW��V��-��S����( &:�+.���G��$Z�3)t�WL~������4t�K�>����@�w��l����~t��Yk�����"�@��F��B�q[��~�%]7�B�H 7Z'(����g�q��m~�o�'����@�`
�J�`�D�>=~m���^������A,���?��h�p�O*�RA1���}������U�ia�6Z8`,��q�����|-
c�Fx��l[� EZ$@�hU�(������gh��V���@1=;ut��]��h��}`� �2���m����<����b�Z,��V����dk{��:-h�?�-�F��n�>���������J��j?vV���qZ�@n���j��v,�3/��T<"�|�Pu�Qk��� �@F�������;�y�����2B��g�"�?� �rg[i}����s� [���>�L+���!��d1��1<y��"-� ���Q�=�3+����&��i-t�O���G1�������[���J��9�Rh���Q�����$�A��--������Q����?8��;����@�N+E���D����8�����7�<���|O�BK��g����P\�%������v�����~ �=�dh ����P\��%}��!��6-K�9fZ�(��F�l�;���f����%�]y�������=�j�@�\���b�o�4��9Zx� Xi���i��Z��N������Si�����P��������5-=��i���;�d|go�� b�9,��C����]&c�6�~]b�8��9��!�n
�*��O0��������m�6�����Op9-�0���IS[w�ZYh.���S��V��K�f�ire��v�����Vhr%���H�,;Y����f�9�@s�"MB���!���B3���A^B�P���vij��9�K�G,���V�v�����>#i�s���((#i+U��Vs���~�b��h�����������W�_�4!��+�����]��V�b�4'A��'d���1%�c)4)����*�C�R���!��S�"{���X2Mq�4'������2��.��E�k�[y��l�Z%��/N1gU_�>�]m�6�~�b{h�e������JC�`���b���G��l_6Z��HK�n_����<.c�E��>�L���,9�����I�2%fZ�(���L���)��*�K-S�m#��=}�a{�d�Rb�e�"�qx�:���Z�@��N��>����;���{�`�';�?�h��t3�i�r��p]h�"������C{��b�F�u�%�`���9v�-V��+k�������{s�4A0��Zq9(���k���>�Jgh�|�K���{�I��z��:�����M:C�s����X��x(>{{���Y{��:B����O�W����}�M2-t����|-�����n���s���
��i���`����L����;-t�N+����d���X�m:t�N+��i�]b^�;.�$����6���9:a+���{=��P�qP|D����)�t�����Zq}�`�XZ�S����>������|���`�����6:c+f:�����3x��~�M.:eb��S �����::?�������H'�}B�����?a�����I���|��mRt����������<��Bi����9Q�������
��O �mNt&��RE�#n��3���n��B�}��"����/v*�ns<]`6!Jr���b����hr��E��>��V%��sn�8���j*@�T�#,�4/���V@+�mB%��D�qCD���~C���}�Py�����h�
v����M�^n'��~���xL�����'%��D1����w���7�[
{�9��DZ�(v{����vD��EZ��D���/j[������X�us��<�0�zD����?��U���@�\���bzU��]�theR*-Ey��m��=-LJ����>��V"��_,|�{��
-O�N��n��J�i�p�����6X���;7���m�b�gt`{:
�������N��/ "���#��G�+�����U��'���iy�=l<���eu����>�L���V��)���&@k��i���~�Q�L��}�;����{%>z(�.mR��� ����Ey��*8������~jUPwZh?.<�b��#�l�/�<;��O������ �>��{�4������;���L���/�x��(`��G����y���/gZBW�.V�����X+`Z��<G+o���0�������sk��~jLu���d������L��10��_r��3-�+_���'��?�
�����j���������\��j]�s�?=�
�j�u��5���mL�(?Z��/�����P���xV���<�K�gB����i���(��>*]��:|���r�:0a���@�:<T�F�V���;����/�����P����?���<�K�gB���Z��pz���[S���n�u��;�M�GS��������(�}� �������<�s�gBk�u[���}����lL����Z�����r���u��[��^��wKL��u��X��f��w"�r����}������o�kLk�u{������o�kL����Z����7����u��[��������/����xD��ms���j�L����`�)Xy }S
]yY��,V�-}SY��-Z����[s���y��{�>���<�}9SX����<&+O�/`��+O��S��������R��+�J_�TJW�U+��uv�Q��l�u�����(�}� ���b�����?EoL������p�A���[S��.V�:|���V�T����u>%���Q�������A�_�}� -]���u��Z����V��v]�f�:|l�#�V����[�u>�
��^+`�]���u>
���Q���]�����/�h��3-]��������0�]��b]�����
�J�ui����O�?�8
���u]�u��'�'��)t]��u>G ����u]N�u��"x��
�R�u�X��#���r+`*]����I{���(`�[�u%X�!����r��u]��u������)v]W�ur���^+`J]��j]��3xd�
�j�ue��C�<�:
���u]]����Z9��u�_�^���3��������F�QZS���V�:=�s�V�T����u��pOA�>c�v���%��7��a������Z��1H��X�[4B�bk 1AIl�Bb-���-2����Z&���-@��+�����T-hq�
O$����SZ���+6<�bHO�k&1A�Zlx!��� s�j�U�����J����pr r�N-�X�fM�L����#9�Dr � Fq BB+�����pr ��F-�X�tMQN��h����� #��b �!t�D-���~]�P�+&q � B����8 ���!j���pr���� &���],S�+�� H�.V��-J������$�Z��.�b�V-�1�
'�9 !�q �'B�����8 1��Ujy�,@(E�b;��b �"���SG�`V����F����]�R �H��LA��Bbv�?p[�Z�b-Il�`�V�������W���Db1�XJT-���Lb)�X�T-����Bb���V�Z��*�m�,k��������#9@1���X��W�� Di�.V���8 ���������pr@���Z��n6��.� �m\���],S�+�� r�.V���8 �������U�������jA��l89 -� �v\��],S�+�� �z�.�Q�+q B>BC���=������� &� ],Q�+Fq �@B+���I�p���6jy�"@THhb [����6�P9 �!��8 1"��%jy�(@�H�b�Z^1�1��N-�X� MQc�������B@�1�E�0���2���*@4I�b�Z^1�T��N-�X��- M�e�� ��[5`�7���-���;��L�!�V-�&�� ����@b�`����Z& �UZ�i�#��LX#UZ�i�Wk�$p_�Z�L�H�e�
�X�jA0mx���I�Lb�`��Bb-��B���4-LB���-���� d���Z^��`��V-�&�Gr@�� $��� ��.V���8 &��m���`�pr 2��H,[���6��L���8 &��%jy�(@�I�b�Z^1�`��F-�X�0 M�e�� ����@@b 1� @�I�b�Z^q �$t�J-���0 ]l��W� ��������Uz�i���B@b 1�E� ���2���*@�I�b�Z^1�`��N-�X�0 !f��Q-��6�w�e��u'1�e�H,+��S���XYHl[�Z�,"�E����X�jA0mx� �$�q%1���XL$��D��1�X�$�2��L��)�X)$V
�m��K�����;��V-��
�`�$0��8 &��%jy�(@�I�b�Z^1�`��N-�X�0 M�e�� �������b��8 &��ejy�U� ���*��b �$t��Z^��`��V-��
'����b��8 &��ejy�U� ���6jy�"@�IhbH,[���6��L���8 &��%jy�(@�I�b�Z^1�`��F-�X�0 M�e�� ���J ���` �$t�D-��0 ]�P�+&q LB����8 &��!�l��`�pr@����+����6�PWr KT�� ��.V���8 &������U� ����X�jA0�?�m&�{�
Gh�
�I�e�
�X�jA01���.�� ��/$�2I`^�Z�LI�e���Z�L��X�$��J��`��Db-�l���Uz�i�s/�L�f� ��k�$0�\�i`�X�T-h�
' �����U� ����X�jA01<�J$ ���` �$t�B-���0 ]l��W,� ��&���Uz�i���$��Z^1�`�X��W�� ��.V���8 &��m���E� ����X�jA0m89`� $�� ��.���Wq LB����Y� ���vjy�*@�IhbH,[���6��/� $�\�0 ],S�+�� ��.V���8 &������U� �b�X��]�i�{X& \w\vK��R ��Z0+��������"b[$��w�%��Z�L�;�2I`\IL�L�H,&K��c��I,e+��S�RH��
U�"b[%��w�%��Z�L�;�2I`$(q LBK���Q� ���*��b �$t��Z^��`��V-��
'�v�?p��W� ����������8 &��Ujy�,@�I�b;��b �$41$��Z�LNH9 �%�q LB�����8 &��m���E� ����X�jA0m89 �$0R�+q LBK���`�pr@N� $��L� ��.�Q�+q LBCb��=������H,!&�0 ],Q�+Fq LB+���I� ���vjy�*@�IhbH,[���6�Pr K� .� ��.���-�������H,Q-��0 ]l��W�� ��&���Uz�y|Y��.�{z���u� ������q�
��K��������.�{�R��T���[6n��=y���+Yh��]������W���q����K�^�������'/U�������s����JO�S����oO^��i������nO^�8������q��(U�{����{��3Q���������q$��T1�=��d���8bL�*�=��d���82L�*�=��d���q�(U�{�����������qO#���]�T��q�"����[�T��q�!���Z�Tq��������X�T��qO �_��JO������c���*Q*H_���c���8�J�*�=��c���8RJ�*�=��c���qD�(U�{�#����{���=�yc���q��(U�{������q$�(U�{������q��(Ua���qd�(U�{�3���t��p{B���N������J�N�����v�b�z��Tq��,Zl�-���P�b��6�q��=Y� ��B��q���J���W.y��8�^)%*U��}����%�J%S�b�EL�%6�J��*U����+�=Y� �/��q�{�#J���q�{y#J���������q��(U�{����{��HQ����'��O��d�'�{�c��k���Q����g��s��Q������k��HQ����������-�Tq���O��d�'�{�s��k��Q�������s��HQ*H_8� a���q��(U�{�������z���=��`���8�D�*�=��`���8RD�*�=��`���8"D�*�=��`���q��(U�{�����~z������q�{�!J��$�q�{�!J���q�{�!J��m=l��=����}�{ x0�JOVz���=�k��=����}�{��8�=����}�{����=����}�{��x�{ !J���������}�o�g(���������
7`���6|'�
6D���=A��v�#�����-D����h�����Gk� �F��(���$�B��R����6<�X�"l��(����!&���-S����ZR���-V����ZX����8 7?��N-�X������
�jA�1<����b��GB+���I�� ]l��W,� ��Hhb[��g�6�����8 7?�X��W������#��b��GB����8 7?���V-���
'l���b�A�� ],S�+�� ��H�b�Z^1�p�#������U�� M�a��$������b��8 7?�X��W�<����L@��j�,����.�S�+Vq n~$����G�`L���7����]�R �H��LA��Bbe!�m�j����Il�`�b��������W���Db1�XJT-���Lbv�?�d�����+���B�����VIl�`Ac�������$��A�� ],Q�+Fq n~$t�J-��������vjy�*����&���Uz�i���B@�1�E�� ],S�+�� ��H�b�Z^��LNX+9 $��8 7?�b�V-���
'���$b��8 7?�X��W\������6jy�"����&�H�Uz�i��9��JBL0�p�#��%jy�(����.V���8 7?��F-�hI�
'�����Uz�i��%�RBL0�p�#��%jy�(����.V���8 7?��N-�X������X�jA�>m89�.� d�\������2���*����.V���8 7?��N-�h9�
'�����UzzX�L���0��L��X�$"�l��`bx0 ]l
$&h�
_H�e���P���6<�X�$�5R���6|%��I���-�����Z&��e�� ���^�$p�$&h�
/$�2I`.T-�J�"�$t�Z�Z�LN@& ����8 &��!�l��`bx$ �&jy�(@�I�b�Z^1�`��F-�X�0 M�e�� ����I#��b �$t�D-��0 ]�P�+Z�i���$���b �$41$��Z�LN�9 �%��8 &��ejy�U� ���*��b �$t��Z^��`��V-��
'�9 �%�q LB�����8 &��UjyE0m89`�� $���� �������L�;�2I�������X
$���@��)�XYH�,$�-T-X�"�m�,�l��`����I�Jb�a��H,&K��c��I,e+��S�RH���n��-��������X�jA0mx� �$����0 ],Q�+Fq LB����Y� ���vjy�*@�IhbH,[���6��.� $�\�0 ],S�+�� ��.V���8 &������`�pr����X�jA0m89 -� $�\�0 ],S�+�� ��.�Q�+q LBCb��=������H,!&�0 ],Q�+Fq LB+���I� ���6jy�"@�Ihb�?�Z�LN(���b�A� �����b �$t�B-���0 ]l��W�� ��&���Uz�i��u! ����"@�I�b�Z^q �$t�J-���0 ]l��W�� ��&���Uz������6���z��O���S�.��� �Zq'10�<�Mh��K��<���v%L����Y��
�J���#�Y��
�J���W� ��0�W+&� �m�3��V}���y��
�J�������x����+�Y��
������ 0�a' �D�"9����xZ�b$x��
������ 0����w�Z��&6l� ���V$x��6�qoB�>!9�Ll�� ���V$x��
������ 0����w�Z��&6l� ���V$x��6��oB�>!9�Ll�� ���\�`bC& �D�"9�Ll�� ���V$x��
;9 y'��`�
x���OH� Vr �NT+�<���L@��jEr���P��;Q�H� vr �NT+�<�<6�����>c��.���u'�u�j�H,+��J�j����"b�Bb�B����6v�='Nh�'����W�+U+&� R"���Z1�X�"V2��L����J����V�Z������� ����� "9 y'��`bC" �D�`&x��
������ 0�a' �D�"9���O�Z� �`b�J@��jEr������;Q�H� *9 y'��`b�N@��jEr��m*'���<��������� 0�!��w�Z��<��������� 0�<`Nh�'$x��
������ 0�!��w�Z��&6r �NT+�<��������� 0��#���h�'$x��
������ 0�!��w�Z��&6r �NTVr������w�Z��f���� ���� 0�a% �D�"9�Ll�� ���V$x��
������ 0�a' �D�"9@L{���OH�����R�������#�4���$���0[�����n�$t�5�����6|!�p�B������Hb-��H��������Z� �W��4��'kgC��Z��P�{1��5�����6��X8��P����6��X8��R�`�vNB���-
��� �
`�jAOC1<�p��b�vNB+���I��9 ]l��W,� ��Ihb0[����6������8 �s�X��W�� ��I�b�Z^1�p;'��m���E��9 Mf��4����@@� 1� ����.���Wq n�$t�J-��������vjy�*����&� �Uzj���B@� 1�E��9 ],S�+�� ��I�b�Z^1�p;'������U��9 !f�Q-���6�w���u'1�e�H,+��S���XYHl[�Z�,"�E�zX���=
���,�����*b1�XL$�U�$b)�X�$V2U�,b��X)$��,E��Jb[� 0[����6�w���HP�4���b$ �D�`�vNB����Y��9 ]l��W�� ��Ihb0[����6��.� �\������2���*����.V���8 �s��N-�X������`�jAOCm89 �Q���Z^��PNH+9 &�Wq n�$t��Z^��p;'��!�l�����pr@� �� ��I�b�Z^1�p;'��jy�$����.�Q�+q n�$41��Z��PN@� ����A��9 ],Q�+Zj��%�`�Z0�p;'������U��9 Mf��4����B@� 1�E��9 ],S�+�� ��I�b�Z^1�p;'������U��9 Mf��4t\,Z�I��pn#� ���$�2��H,[����LB[� Z�i�k�$0/T-h�
�$�2I`�T-h�
_I�e��}�jA0mx"��I6Db��=����C& \3� Z�i���L�U���0 ]�V�� ����Iwjy�*@�IhbH,[�����$��Z^1�`�X��WL� ��.�Q�+q LBCb��=���� d��H-��0 ],Q�+Fq LB+���I� ���6jy�"@�Ihb[��� ����I#�������������8 &��Ujy�,@�I�b;��b �$41$��Z�LN�r K� .� ��.���Wq LB����Y� ���vjy�*@�I1K,�j�.����,��;� Z���)�X
$VU� be!�����P�`YDl�$�����Uz�i�{X& �+� �U�b"��H,%��I�R&��I�d�LY�J!�RHl+T-X��m�����X�jA0mx� �$����0 ],Q�+Z����39 �%��8 &������U� ����X�jA0m89`]�H,!&��`�X��W\�0 ]�R�+fq LB����8 &��!�l��`�pr@Z�H,!&��`�X��W� �9 r KTq LBCb��=������H,!&�0 ],Q�+Fq LB+���I� ���6jy�"@�IhbH,[���6�P9 �%��8 &��%jy�(@�I�b�Z^�L���R�H,Q-X�0 M�e�� ����B@b 1�E� ���2���*@�I�b�Z^1�`��N-�X�0 M�e�� ���ytB�8���6x�v%L���;�Y��6�ytB�V\B/�&6�+aB�V\H�LlhW��^�I�LlhW��^��������� �Z1���m�G'���^�LlhW��^�XHl������^�XI�Ll����W�'$x��
;9 ����`�
x���#9�LlH��BW�g$x��
�P�J��� 0�a#�>#9�����Z� �`bC$T�>#9�LlH��JW�g$x��
�P�J��� 0�a#T�>#9���a� �;�!�<���H��J��+9�Ll�������H� *9`�+�3�<���������`�
x���OH� Vr�NW�g$x��
������`bC%�t%|Fr�����v�>#9��c�=�Nh����LlXw�+a�H,+���J����E�����J����6v�=�Nh�'����W�+�&�I�R"1�>a&��E�d�+�+E��Bb|%|�Jb`�
x���O�;�0�!�"_ ���&6$r@�+a�L� *9 ��� �`b�N�|%|Br��m�G'���<�������� �`bC&�|%|Br���P�+_ ���&6������OH� �m����V}Br�����<���H� 29���}���&6l� �;�!�<�l�<:�U���&6Dr�����`bC"x����&6r�����`b�F��s"9�����Z� �`bC$x����&6$r�����`bC!x�����<�����y�>Dr��m�G'���<�����y�>Dr������w�C$x��
��y�>Dr�����<���H� ��G'����y����������������~��H����)�������_��������[<������h��o�������������/�����-/�����<����������9������6������_������������/���������q�������U���v�~q���U�eK�z�������Wo�~�^%���#�������m���i����uq�g�����?<z�����m���o����-n���H���W���3������1~����3�X�bt��~��b${���Z��su�X1W���������C���Z��:�u��#�S:b�n�Su�mUY����������q�/&t�m�r�~�i���������W;�����v����1��~q����x"<�#�m ��3s��/^�������u���-��#�?�������Pz�:"������]�������w�\]��g�?\���O�JG,�fBG�a�j�;b({�1����G��#����#le9��vB�|� ?�#�2����r}Ge�����#��v1U��C� +�g���������w�@v���3����g��M�����RF��p� ���#��W�_�?�����>�������>�G���Ds$;�O��v}2U���9����]G�e��2����������su�#�Y�x�������� }��c�����#�k�g�WW�su��1�����8��'��
E����������Xv��c�n�Ot_�:b ;%�z&<!��64�@�rGd��K��v�D�b�5���'\�����f���}u=��~��u~����������e#�+���1|�S>'��9(��z�9��qO�\]��g����#��W��m]�6R�u�qy���k����}u=��~1�=��v�1U��c ;eQ�Lx�j-�����a�HvJGL��:b��w�@vJd1[���m��];G�3>��XT<{��#�o���rG���3.<�p����k�d��pc�3������c�Hv�"��'�[<'a__�5G�_���'��;��o��?�]����q=:��$l�v�q�b$���{�};c���s@���\s$���y�(Su�C�T]������e#�f,/�r����k�dg��5W���'���,1��t����P��W�[��������s����\s�n�Su�#�Wn���x"<�����:�;�r�9��r�]zsu�#��ZG�e'���'�5�xN����k�dg�5��v1U�;b {�a�����f\�����}}=���XY���:b��w�@����������3�{=gb__�2G�_L��b�n�Su�#�s����������������?]�:b�n�Su�(s$���O��
{G���2��Q�Pv���d]����8Fe��#��s:b=�l�\�2��_\?FL��:b��#��������������������Pv�1b�n�Su�1���q�S��W�9�s�����r(;�#��v1U�;b ;�#&�����o.g�C����]GL��:b�n���"�;b ;��,�������Pv�1b��w�\];F�d�����P2��a�1bY���7�3�����r�n�Su�#��:b����cD9G_�\�,�����]GL���#�y����e^�s�����r(;c1W�����}G��t��I�����7�3����u�\]����v����cf(=��9���zf9�������u�T]�����u�3���G����:y�#�32���]GL���#� W�#�Yg�r����Y�d��5��v1U���k ��5�3�
�q;�_�^�,G�3V�su�����#�W��F���5���o�g�#������su�1���P��5f�G�7_�,G�3V�su�����1��q��S� ��5���o�g�#� w�L��:b��w�PvFG<��u����3�����'�v1U�;b ;�����}G��������Hv�:���������1��t�1����L�������Hv���\]��g�W�^�Px�=T#�w��������g�#��?��u�T��#����{�v�|��w�Pz��F��������Hv���u�����1����� 1��v�:����q9���XG���:b��w�@v���O�'|���s�����r$;e1U������:b <��������������g�#�w�����x�{��s$;�/����qw~^���w�3����<b�n�Su�c�H��1�}��@���3��p&�|N���`�dgD��t�.*����1�����3��K��9 ��z�9���}v�u����������H����EE �����Hv�1b��w�3��#�I����_���}G�s��� s$;���
ug|�5W�;b(���K����&|u@.���}=�������u���g���� s$��)g�r����`�d�t�T��#��zGdg|M�S��������#��'D��t��#�1������^���=�/E��z):�B��s(���,s$;#�����1W��c$;�������E��H��Yf��we�z���W2jy[�->y����{�����W�;�b���r�=�����gM�������HvF�9W�;^L����@v�E�Hz����2J�.G�#�)g���]GL����Ny�����3�>����������x�{5���~�#�s:�������s"���(s$;�������t��������G�i�YY/A��/����� ��
endstream
endobj
26
0
obj
15727
endobj
27
0
obj
[
]
endobj
28
0
obj
<<
/Type
/Page
/Parent
1
0
R
/MediaBox
[
0
0
595
842
]
/Contents
29
0
R
/Resources
30
0
R
/Annots
32
0
R
/Group
<<
/S
/Transparency
/CS
/DeviceRGB
>>
>>
endobj
29
0
obj
<<
/Filter
/FlateDecode
/Length
31
0
R
>>
stream
x���[�$�u���8O6�3�!�HjE�=-H�@[�H�$C��5 �%����:��/keT�ae�9���^�Q�wF���:���}/�����E���������^��V��J_���������h��s��C������!�0���_?����w|����g���y���/c�&�p��1�z6����^�e�{����|W������]��*n��b��m��)��S�OLU�V���_��1����O��l����G�g���4_�����`}��f���4_����$U�~?���}v�?��{4 ���2��W����M �a����Hy�i����������D����O/����u�C����O�������GJ�,io<��P��og���H<�~����_~qO�����o���������)��jf�/�\�� �a����]��*v^���_[�����??����������B~M����+����|��l[{����_�����}��w�����?|����?����n�n����~��o���wq���}J=�sj��z�?{�����w�x�����=�������y��?>%�������������{�J��������w?�����_>�K�'��z���}�{���G������)�:��1|�Cf��W-~h-��_�������S)m���L��o��M�e
m��:q"i����7w�(���t.u/������8��\�v��]�2��6Z(�����s������>V�����?�����(���z����
�Qg�)��z�;���u��z�0F
������|�B��b����}�}���M�?)��������_�J������.�d���~��"8�����e�1�{7i�����cj0��`�e��S{���[.���w�?������g��0a=�;ko��p������CX��������n]��7���t[0B������s->�6`�m���W���xv���_/����n��~��?���(���������re#�[��6� #�FF8��/����� 0���4&��� ^����B��~��g���^��s�A�K�m�n�����'Xo����H������4&���r������r�}^�9��P"��f
��fn�}0xU��t�#���"�p� � i^{M�����+7��`h5��z�������Rr�t��}�0�j�Kc������a\=�q���6>�_��R����j����]�eyu�����D�26��0�]��@K���_BL�75wxS #��Ze��u�r�q���+�/w!v�fV��Q���s�!�c"�o�����.7]0B��#����nt���j��� �!�f�/��vc�0�`P���7��m�0���u��z�Q�����k�V��^0��W�?�������[�_>L���##�t��D���RAS��n�8��U��i��������pK�'m0��` �i[����sz��1m0��`P���7��o�FW"��ea���t����
j�r�u�P����#��D]�0B�������J^��w���%aK0�Q`H�-}��f� Wj���
�%`K0�Q`D���%��u�!X@�yw:J�/���0�k����m�^�o���M�
�&�r�q����>0�PG+��7�m��������dGZ�Uc�5��Vz����%��:�����9=oX��h�l�a,��
W
����DD�F�G�����
�&;�S���4~���+���,E����������6�Bi�����%��8IV#��/���?�vw� �������5o��F�v�1a|d8,{��s����O����q���a)�:������C�0Q� �a)�����*r=EX��h����b��U��.���V`����1��o�v�f���g�mxV^�|W�vI9���:L4;,��CW��i�HOb;�s���4~�%E����L�gcB��[��r��v{���������FK�a��*GwCO�d� �fG[ax�������6�K.�xX}���/=uX|e�4�
�_�����3��v�+���_��|b9,�r��P���@���.#����zHD;,����z��?r��P��*�s�����s��U87�"�X6Xf��M��Z�X � +��`������/Z���'���$X1�.��]L�;�z�� c�Sw�����v�M^�����@)0s�h�`������4�o����4Q�=Q��
L��!�`�f,���2�4��w��
���������� ��D����n����e0_��c�L���x�p�iB���qC0k�����4M�=�/��}Aw_~mn�u�Y{Gb�i�q��S��v�2K�:$����m����/��4K�
1�\��
������My����� ��Z`g���>D�
� �k�0Uv�6��K��6�H�:(XATu�
�����i�bG��5c� ��������`!�V����|r�0��Sy��Z ���'���T���g��7����O�>����k@{�Tn�w���U�N��]�[ wW%���YI�:$��[�[o��������U��w��u��+��*���Y��t��W��*���"�a�f�.h���7��;� {�)�P����~S��a��v�WL�Q{0����uO0��h��0�3�n�M{{�G��=�$��=��V>=o��w�Af��c~f��u�0�3���Y]����3��;�+L���w���?����4���8^�{���W�Oe{�4&�0�����}��t���Cw�-��1�4��ue�t��0���D�R[H]��#�0���D����;��*�-an"�s`G`���1�q���/,$\0�
?������m���EpF��c�u��>=�OFa�2
��3���7
,Rv��4X�0p�m���Y����5�h�(a,��-���r4X��hC�:al�rx�r�R���1`u���\�a����
�Lia��Bm<��jb��*d����U�h��=�� �C+�/���D�Ze�
1"�v��`�����5��c#<������gU�0�Ra���j���z����q[a�����R��R���`��"v����d�v�����h����a����w�UN�0���-#t���;8h��A�6�`��?��D�����_��lL�{�e��SwS7
�&�hC��F�=�(�%�\��Auc0F���yl��-
\0���h�q����K����n0B���i����]�0��s�z�e�v��
0�aT������7�
���"���W����AUw%�� ���/T6&����i��?��F��a������>=�K�+�a�����}��#,v��eX0�����K����aU�x����v�%��6�
k��==^�HO:X.��4&t==��}��=��&�'��9���r��g R�.�
��3���f R.�
�O��� $i���>���^��s��G
��Q��#o������I��ce�������Y��3[����T��E���Q����{�f��
�����=%3��Bu��ixl��@�������kx�>