public inbox for [email protected]
help / color / mirror / Atom feed[PATCH v3 3/5] pg_rewind: Replace the hybrid list+array data structure with simplehash.
8+ messages / 5 participants
[nested] [flat]
* [PATCH v3 3/5] pg_rewind: Replace the hybrid list+array data structure with simplehash.
@ 2020-08-19 12:34 Heikki Linnakangas <[email protected]>
0 siblings, 0 replies; 8+ messages in thread
From: Heikki Linnakangas @ 2020-08-19 12:34 UTC (permalink / raw)
Now that simplehash can be use in frontend code, let's make use of it.
---
src/bin/pg_rewind/copy_fetch.c | 4 +-
src/bin/pg_rewind/fetch.c | 2 +-
src/bin/pg_rewind/fetch.h | 2 +-
src/bin/pg_rewind/filemap.c | 286 ++++++++++++++------------------
src/bin/pg_rewind/filemap.h | 67 +++-----
src/bin/pg_rewind/libpq_fetch.c | 4 +-
src/bin/pg_rewind/pg_rewind.c | 12 +-
7 files changed, 168 insertions(+), 209 deletions(-)
diff --git a/src/bin/pg_rewind/copy_fetch.c b/src/bin/pg_rewind/copy_fetch.c
index 18fad32600..61aed8018b 100644
--- a/src/bin/pg_rewind/copy_fetch.c
+++ b/src/bin/pg_rewind/copy_fetch.c
@@ -207,9 +207,9 @@ copy_executeFileMap(filemap_t *map)
file_entry_t *entry;
int i;
- for (i = 0; i < map->narray; i++)
+ for (i = 0; i < map->nactions; i++)
{
- entry = map->array[i];
+ entry = map->actions[i];
execute_pagemap(&entry->target_modified_pages, entry->path);
switch (entry->action)
diff --git a/src/bin/pg_rewind/fetch.c b/src/bin/pg_rewind/fetch.c
index f18fe5386e..f41d0f295e 100644
--- a/src/bin/pg_rewind/fetch.c
+++ b/src/bin/pg_rewind/fetch.c
@@ -37,7 +37,7 @@ fetchSourceFileList(void)
* Fetch all relation data files that are marked in the given data page map.
*/
void
-executeFileMap(void)
+execute_file_actions(filemap_t *filemap)
{
if (datadir_source)
copy_executeFileMap(filemap);
diff --git a/src/bin/pg_rewind/fetch.h b/src/bin/pg_rewind/fetch.h
index 7cf8b6ea09..b20df8b153 100644
--- a/src/bin/pg_rewind/fetch.h
+++ b/src/bin/pg_rewind/fetch.h
@@ -25,7 +25,7 @@
*/
extern void fetchSourceFileList(void);
extern char *fetchFile(const char *filename, size_t *filesize);
-extern void executeFileMap(void);
+extern void execute_file_actions(filemap_t *filemap);
/* in libpq_fetch.c */
extern void libpqProcessFileList(void);
diff --git a/src/bin/pg_rewind/filemap.c b/src/bin/pg_rewind/filemap.c
index 6d19d2be61..e6e037d1cd 100644
--- a/src/bin/pg_rewind/filemap.c
+++ b/src/bin/pg_rewind/filemap.c
@@ -3,6 +3,19 @@
* filemap.c
* A data structure for keeping track of files that have changed.
*
+ * This source file contains the logic to decide what to do with different
+ * kinds of files, and the data structure to support it. Before modifying
+ * anything, pg_rewind collects information about all the files and their
+ * attributes in the target and source data directories. It also scans the
+ * WAL log in the target, and collects information about data blocks that
+ * were changed. All this information is stored in a hash table, using the
+ * file path, relative to the root of the data directory, as the key.
+ *
+ * After collecting all the information required, the filemap_finalize()
+ * function scans the hash table and decides what action needs to be taken
+ * for each file. Finally, it sorts the array to the final order that the
+ * actions should be executed in.
+ *
* Copyright (c) 2013-2020, PostgreSQL Global Development Group
*
*-------------------------------------------------------------------------
@@ -14,22 +27,39 @@
#include <unistd.h>
#include "catalog/pg_tablespace_d.h"
+#include "common/hashfn.h"
#include "common/string.h"
#include "datapagemap.h"
#include "filemap.h"
#include "pg_rewind.h"
#include "storage/fd.h"
-filemap_t *filemap = NULL;
+/*
+ * Define a hash table which we can use to store information about the files
+ * mentioned in the backup manifest.
+ */
+static uint32 hash_string_pointer(const char *s);
+#define SH_PREFIX filehash
+#define SH_ELEMENT_TYPE file_entry_t
+#define SH_KEY_TYPE const char *
+#define SH_KEY path
+#define SH_HASH_KEY(tb, key) hash_string_pointer(key)
+#define SH_EQUAL(tb, a, b) (strcmp(a, b) == 0)
+#define SH_SCOPE static inline
+#define SH_RAW_ALLOCATOR pg_malloc0
+#define SH_DECLARE
+#define SH_DEFINE
+#include "lib/simplehash.h"
+
+static filehash_hash *filehash;
static bool isRelDataFile(const char *path);
static char *datasegpath(RelFileNode rnode, ForkNumber forknum,
BlockNumber segno);
-static int path_cmp(const void *a, const void *b);
-static file_entry_t *get_filemap_entry(const char *path, bool create);
+static file_entry_t *insert_filehash_entry(const char *path);
+static file_entry_t *lookup_filehash_entry(const char *path);
static int final_filemap_cmp(const void *a, const void *b);
-static void filemap_list_to_array(filemap_t *map);
static bool check_file_excluded(const char *path, bool is_source);
/*
@@ -131,54 +161,26 @@ static const struct exclude_list_item excludeFiles[] =
};
/*
- * Create a new file map (stored in the global pointer "filemap").
+ * Initialize the hash table for the file map.
*/
void
-filemap_create(void)
+filemap_init(void)
{
- filemap_t *map;
-
- map = pg_malloc(sizeof(filemap_t));
- map->first = map->last = NULL;
- map->nlist = 0;
- map->array = NULL;
- map->narray = 0;
-
- Assert(filemap == NULL);
- filemap = map;
+ filehash = filehash_create(1000, NULL);
}
-/* Look up or create entry for 'path' */
+/* Look up entry for 'path', creating new one if it doesn't exists */
static file_entry_t *
-get_filemap_entry(const char *path, bool create)
+insert_filehash_entry(const char *path)
{
- filemap_t *map = filemap;
file_entry_t *entry;
- file_entry_t **e;
- file_entry_t key;
- file_entry_t *key_ptr;
+ bool found;
- if (map->array)
+ entry = filehash_insert(filehash, path, &found);
+ if (!found)
{
- key.path = (char *) path;
- key_ptr = &key;
- e = bsearch(&key_ptr, map->array, map->narray, sizeof(file_entry_t *),
- path_cmp);
- }
- else
- e = NULL;
-
- if (e)
- entry = *e;
- else if (!create)
- entry = NULL;
- else
- {
- /* Create a new entry for this file */
- entry = pg_malloc(sizeof(file_entry_t));
entry->path = pg_strdup(path);
entry->isrelfile = isRelDataFile(path);
- entry->action = FILE_ACTION_UNDECIDED;
entry->target_exists = false;
entry->target_type = FILE_TYPE_UNDEFINED;
@@ -192,21 +194,18 @@ get_filemap_entry(const char *path, bool create)
entry->source_size = 0;
entry->source_link_target = NULL;
- entry->next = NULL;
-
- if (map->last)
- {
- map->last->next = entry;
- map->last = entry;
- }
- else
- map->first = map->last = entry;
- map->nlist++;
+ entry->action = FILE_ACTION_UNDECIDED;
}
return entry;
}
+static file_entry_t *
+lookup_filehash_entry(const char *path)
+{
+ return filehash_lookup(filehash, path);
+}
+
/*
* Callback for processing source file list.
*
@@ -220,8 +219,6 @@ process_source_file(const char *path, file_type_t type, size_t size,
{
file_entry_t *entry;
- Assert(filemap->array == NULL);
-
/*
* Pretend that pg_wal is a directory, even if it's really a symlink. We
* don't want to mess with the symlink itself, nor complain if it's a
@@ -238,7 +235,9 @@ process_source_file(const char *path, file_type_t type, size_t size,
pg_fatal("data file \"%s\" in source is not a regular file", path);
/* Remember this source file */
- entry = get_filemap_entry(path, true);
+ entry = insert_filehash_entry(path);
+ if (entry->source_exists)
+ pg_fatal("duplicate source file \"%s\"", path);
entry->source_exists = true;
entry->source_type = type;
entry->source_size = size;
@@ -256,7 +255,6 @@ void
process_target_file(const char *path, file_type_t type, size_t size,
const char *link_target)
{
- filemap_t *map = filemap;
file_entry_t *entry;
/*
@@ -265,22 +263,6 @@ process_target_file(const char *path, file_type_t type, size_t size,
* the source data folder when processing the source files.
*/
- if (map->array == NULL)
- {
- /* on first call, initialize lookup array */
- if (map->nlist == 0)
- {
- /* should not happen */
- pg_fatal("source file list is empty");
- }
-
- filemap_list_to_array(map);
-
- Assert(map->array != NULL);
-
- qsort(map->array, map->narray, sizeof(file_entry_t *), path_cmp);
- }
-
/*
* Like in process_source_file, pretend that pg_wal is always a directory.
*/
@@ -288,7 +270,9 @@ process_target_file(const char *path, file_type_t type, size_t size,
type = FILE_TYPE_DIRECTORY;
/* Remember this target file */
- entry = get_filemap_entry(path, true);
+ entry = insert_filehash_entry(path);
+ if (entry->target_exists)
+ pg_fatal("duplicate source file \"%s\"", path);
entry->target_exists = true;
entry->target_type = type;
entry->target_size = size;
@@ -301,7 +285,7 @@ process_target_file(const char *path, file_type_t type, size_t size,
* changed blocks in the pagemap of the file.
*
* NOTE: All the files on both systems must have already been added to the
- * file map!
+ * hash table!
*/
void
process_target_wal_block_change(ForkNumber forknum, RelFileNode rnode,
@@ -312,47 +296,45 @@ process_target_wal_block_change(ForkNumber forknum, RelFileNode rnode,
BlockNumber blkno_inseg;
int segno;
- Assert(filemap->array);
-
segno = blkno / RELSEG_SIZE;
blkno_inseg = blkno % RELSEG_SIZE;
path = datasegpath(rnode, forknum, segno);
- entry = get_filemap_entry(path, false);
+ entry = lookup_filehash_entry(path);
pfree(path);
+ /*
+ * If the block still exists in both systems, remember it. Otherwise we
+ * can safely ignore it.
+ *
+ * If the block is beyond the EOF in the source system, or the file doesn't
+ * doesn'exist in the source at all, we're going to truncate/remove it away
+ * from the target anyway. Likewise, if it doesn't exist in the target
+ * anymore, we will copy it over with the "tail" from the source system,
+ * anyway.
+ *
+ * It is possible to find WAL for a file that doesn't exist on either
+ * system anymore. It means that the relation was dropped later in the
+ * target system, and independently on the source system too, or that
+ * it was created and dropped in the target system and it never existed
+ * in the source. Either way, we can safely ignore it.
+ */
if (entry)
{
- int64 end_offset;
-
Assert(entry->isrelfile);
if (entry->target_type != FILE_TYPE_REGULAR)
pg_fatal("unexpected page modification for directory or symbolic link \"%s\"",
entry->path);
- /*
- * If the block beyond the EOF in the source system, no need to
- * remember it now, because we're going to truncate it away from the
- * target anyway. Also no need to remember the block if it's beyond
- * the current EOF in the target system; we will copy it over with the
- * "tail" from the source system, anyway.
- */
- end_offset = (blkno_inseg + 1) * BLCKSZ;
- if (end_offset <= entry->source_size &&
- end_offset <= entry->target_size)
- datapagemap_add(&entry->target_modified_pages, blkno_inseg);
- }
- else
- {
- /*
- * If we don't have any record of this file in the file map, it means
- * that it's a relation that doesn't exist in the source system. It
- * could exist in the target system; we haven't moved the target-only
- * entries from the linked list to the array yet! But in any case, if
- * it doesn't exist in the source it will be removed from the target
- * too, and we can safely ignore it.
- */
+ if (entry->target_exists && entry->source_exists)
+ {
+ off_t end_offset;
+
+ end_offset = (blkno_inseg + 1) * BLCKSZ;
+ if (end_offset <= entry->source_size && end_offset <= entry->target_size)
+ datapagemap_add(&entry->target_modified_pages, blkno_inseg);
+ }
}
}
@@ -414,34 +396,6 @@ check_file_excluded(const char *path, bool is_source)
return false;
}
-/*
- * Convert the linked list of entries in map->first/last to the array,
- * map->array.
- */
-static void
-filemap_list_to_array(filemap_t *map)
-{
- int narray;
- file_entry_t *entry,
- *next;
-
- map->array = (file_entry_t **)
- pg_realloc(map->array,
- (map->nlist + map->narray) * sizeof(file_entry_t *));
-
- narray = map->narray;
- for (entry = map->first; entry != NULL; entry = next)
- {
- map->array[narray++] = entry;
- next = entry->next;
- entry->next = NULL;
- }
- Assert(narray == map->nlist + map->narray);
- map->narray = narray;
- map->nlist = 0;
- map->first = map->last = NULL;
-}
-
static const char *
action_to_str(file_action_t action)
{
@@ -469,32 +423,31 @@ action_to_str(file_action_t action)
* Calculate the totals needed for progress reports.
*/
void
-calculate_totals(void)
+calculate_totals(filemap_t *filemap)
{
file_entry_t *entry;
int i;
- filemap_t *map = filemap;
- map->total_size = 0;
- map->fetch_size = 0;
+ filemap->total_size = 0;
+ filemap->fetch_size = 0;
- for (i = 0; i < map->narray; i++)
+ for (i = 0; i < filemap->nactions; i++)
{
- entry = map->array[i];
+ entry = filemap->actions[i];
if (entry->source_type != FILE_TYPE_REGULAR)
continue;
- map->total_size += entry->source_size;
+ filemap->total_size += entry->source_size;
if (entry->action == FILE_ACTION_COPY)
{
- map->fetch_size += entry->source_size;
+ filemap->fetch_size += entry->source_size;
continue;
}
if (entry->action == FILE_ACTION_COPY_TAIL)
- map->fetch_size += (entry->source_size - entry->target_size);
+ filemap->fetch_size += (entry->source_size - entry->target_size);
if (entry->target_modified_pages.bitmapsize > 0)
{
@@ -503,7 +456,7 @@ calculate_totals(void)
iter = datapagemap_iterate(&entry->target_modified_pages);
while (datapagemap_next(iter, &blk))
- map->fetch_size += BLCKSZ;
+ filemap->fetch_size += BLCKSZ;
pg_free(iter);
}
@@ -511,15 +464,14 @@ calculate_totals(void)
}
void
-print_filemap(void)
+print_filemap(filemap_t *filemap)
{
- filemap_t *map = filemap;
file_entry_t *entry;
int i;
- for (i = 0; i < map->narray; i++)
+ for (i = 0; i < filemap->nactions; i++)
{
- entry = map->array[i];
+ entry = filemap->actions[i];
if (entry->action != FILE_ACTION_NONE ||
entry->target_modified_pages.bitmapsize > 0)
{
@@ -641,15 +593,6 @@ datasegpath(RelFileNode rnode, ForkNumber forknum, BlockNumber segno)
return path;
}
-static int
-path_cmp(const void *a, const void *b)
-{
- file_entry_t *fa = *((file_entry_t **) a);
- file_entry_t *fb = *((file_entry_t **) b);
-
- return strcmp(fa->path, fb->path);
-}
-
/*
* In the final stage, the filemap is sorted so that removals come last.
* From disk space usage point of view, it would be better to do removals
@@ -835,21 +778,48 @@ decide_file_action(file_entry_t *entry)
/*
* Decide what to do with each file.
*/
-void
+filemap_t *
filemap_finalize()
{
int i;
+ filehash_iterator it;
+ file_entry_t *entry;
+ filemap_t *filemap;
- filemap_list_to_array(filemap);
-
- for (i = 0; i < filemap->narray; i++)
+ filehash_start_iterate(filehash, &it);
+ while ((entry = filehash_iterate(filehash, &it)) != NULL)
{
- file_entry_t *entry = filemap->array[i];
-
entry->action = decide_file_action(entry);
}
- /* Sort the actions to the order that they should be performed */
- qsort(filemap->array, filemap->narray, sizeof(file_entry_t *),
+ /*
+ * Turn the hash table into an array, sorted in the order that the actions
+ * should be performed.
+ */
+ filemap = pg_malloc(offsetof(filemap_t, actions) +
+ filehash->members * sizeof(file_entry_t *));
+ filemap->nactions = filehash->members;
+ filehash_start_iterate(filehash, &it);
+ i = 0;
+ while ((entry = filehash_iterate(filehash, &it)) != NULL)
+ {
+ filemap->actions[i++] = entry;
+ }
+
+ qsort(&filemap->actions, filemap->nactions, sizeof(file_entry_t *),
final_filemap_cmp);
+
+ return filemap;
+}
+
+
+/*
+ * Helper function for filemap hash table.
+ */
+static uint32
+hash_string_pointer(const char *s)
+{
+ unsigned char *ss = (unsigned char *) s;
+
+ return hash_bytes(ss, strlen(s));
}
diff --git a/src/bin/pg_rewind/filemap.h b/src/bin/pg_rewind/filemap.h
index a5e8df57f4..3660ffe099 100644
--- a/src/bin/pg_rewind/filemap.h
+++ b/src/bin/pg_rewind/filemap.h
@@ -12,15 +12,6 @@
#include "storage/block.h"
#include "storage/relfilenode.h"
-/*
- * For every file found in the local or remote system, we have a file entry
- * that contains information about the file on both systems. For relation
- * files, there is also a page map that marks pages in the file that were
- * changed in the target after the last common checkpoint. Each entry also
- * contains an 'action' field, which says what we are going to do with the
- * file.
- */
-
/* these enum values are sorted in the order we want actions to be processed */
typedef enum
{
@@ -44,9 +35,21 @@ typedef enum
FILE_TYPE_SYMLINK
} file_type_t;
+/*
+ * For every file found in the local or remote system, we have a file entry
+ * that contains information about the file on both systems. For relation
+ * files, there is also a page map that marks pages in the file that were
+ * changed in the target after the last common checkpoint.
+ *
+ * When gathering information, these are kept in a hash table, private to
+ * filemap.c. filemap_finalize() fills in the 'action' field, sorts all the
+ * entries, and returns them in an array, ready for executing the actions.
+ */
typedef struct file_entry_t
{
- char *path;
+ uint32 status; /* hash status */
+
+ const char *path;
bool isrelfile; /* is it a relation data file? */
/*
@@ -71,44 +74,25 @@ typedef struct file_entry_t
* What will we do to the file?
*/
file_action_t action;
-
- struct file_entry_t *next;
} file_entry_t;
+/*
+ * This represents the final decisions on what to do with each file.
+ * 'actions' array contains an entry for each file, sorted in the order
+ * that their actions should executed.
+ */
typedef struct filemap_t
{
- /*
- * New entries are accumulated to a linked list, in process_source_file
- * and process_target_file.
- */
- file_entry_t *first;
- file_entry_t *last;
- int nlist; /* number of entries currently in list */
-
- /*
- * After processing all the remote files, the entries in the linked list
- * are moved to this array. After processing local files, too, all the
- * local entries are added to the array by filemap_finalize, and sorted in
- * the final order. After filemap_finalize, all the entries are in the
- * array, and the linked list is empty.
- */
- file_entry_t **array;
- int narray; /* current length of array */
-
- /*
- * Summary information.
- */
+ /* Summary information, filled by calculate_totals() */
uint64 total_size; /* total size of the source cluster */
uint64 fetch_size; /* number of bytes that needs to be copied */
+
+ int nactions; /* size of 'actions' array */
+ file_entry_t *actions[FLEXIBLE_ARRAY_MEMBER];
} filemap_t;
-extern filemap_t *filemap;
-
-extern void filemap_create(void);
-extern void calculate_totals(void);
-extern void print_filemap(void);
-
/* Functions for populating the filemap */
+extern void filemap_init(void);
extern void process_source_file(const char *path, file_type_t type,
size_t size, const char *link_target);
extern void process_target_file(const char *path, file_type_t type,
@@ -116,6 +100,9 @@ extern void process_target_file(const char *path, file_type_t type,
extern void process_target_wal_block_change(ForkNumber forknum,
RelFileNode rnode,
BlockNumber blkno);
-extern void filemap_finalize(void);
+
+extern filemap_t *filemap_finalize(void);
+extern void calculate_totals(filemap_t *filemap);
+extern void print_filemap(filemap_t *filemap);
#endif /* FILEMAP_H */
diff --git a/src/bin/pg_rewind/libpq_fetch.c b/src/bin/pg_rewind/libpq_fetch.c
index 7fc9161b8c..9c541bb73d 100644
--- a/src/bin/pg_rewind/libpq_fetch.c
+++ b/src/bin/pg_rewind/libpq_fetch.c
@@ -460,9 +460,9 @@ libpq_executeFileMap(filemap_t *map)
PQresultErrorMessage(res));
PQclear(res);
- for (i = 0; i < map->narray; i++)
+ for (i = 0; i < map->nactions; i++)
{
- entry = map->array[i];
+ entry = map->actions[i];
/* If this is a relation file, copy the modified blocks */
execute_pagemap(&entry->target_modified_pages, entry->path);
diff --git a/src/bin/pg_rewind/pg_rewind.c b/src/bin/pg_rewind/pg_rewind.c
index e0ed1759cb..13b4eab52b 100644
--- a/src/bin/pg_rewind/pg_rewind.c
+++ b/src/bin/pg_rewind/pg_rewind.c
@@ -129,6 +129,7 @@ main(int argc, char **argv)
TimeLineID endtli;
ControlFileData ControlFile_new;
bool writerecoveryconf = false;
+ filemap_t *filemap;
pg_logging_init(argv[0]);
set_pglocale_pgservice(argv[0], PG_TEXTDOMAIN("pg_rewind"));
@@ -371,10 +372,11 @@ main(int argc, char **argv)
/*
* Collect information about all files in the target and source systems.
*/
- filemap_create();
if (showprogress)
pg_log_info("reading source file list");
+ filemap_init();
fetchSourceFileList();
+
if (showprogress)
pg_log_info("reading target file list");
traverse_datadir(datadir_target, &process_target_file);
@@ -395,13 +397,13 @@ main(int argc, char **argv)
* We have collected all information we need from both systems. Decide
* what to do with each file.
*/
- filemap_finalize();
+ filemap = filemap_finalize();
if (showprogress)
- calculate_totals();
+ calculate_totals(filemap);
/* this is too verbose even for verbose mode */
if (debug)
- print_filemap();
+ print_filemap(filemap);
/*
* Ok, we're ready to start copying things over.
@@ -421,7 +423,7 @@ main(int argc, char **argv)
* modified the target directory and there is no turning back!
*/
- executeFileMap();
+ execute_file_actions(filemap);
progress_report(true);
--
2.18.4
----Next_Part(Fri_Sep_18_16_41_50_2020_369)--
Content-Type: Text/X-Patch; charset=us-ascii
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="v2_5-0004-pg_rewind-Refactor-the-abstraction-to-fetch-from-.patch"
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
@ 2023-06-24 00:08 Tom Lane <[email protected]>
2023-06-24 11:23 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tomas Vondra <[email protected]>
0 siblings, 1 reply; 8+ messages in thread
From: Tom Lane @ 2023-06-24 00:08 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: PostgreSQL Hackers <[email protected]>
Tomas Vondra <[email protected]> writes:
> The problem is that the selectivity for "IS NULL" is estimated using the
> table-level statistics. But the LEFT JOIN entirely breaks the idea that
> the null_frac has anything to do with NULLs in the join result.
Right.
> I wonder how to improve this, say by adjusting the IS NULL selectivity
> when we know to operate on the outer side of the join. We're able to
> do this for antijoins, so maybe we could do that here, somehow?
This mess is part of the long-term plan around the work I've been doing
on outer-join-aware Vars. We now have infrastructure that can let
the estimator routines see "oh, this Var isn't directly from a scan
of its table, it's been passed through a potentially-nulling outer
join --- and I can see which one". I don't have more than vague ideas
about what happens next, but that is clearly an essential step on the
road to doing better.
regards, tom lane
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
2023-06-24 00:08 Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tom Lane <[email protected]>
@ 2023-06-24 11:23 ` Tomas Vondra <[email protected]>
2023-06-26 09:22 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Andrey Lepikhov <[email protected]>
0 siblings, 1 reply; 8+ messages in thread
From: Tomas Vondra @ 2023-06-24 11:23 UTC (permalink / raw)
To: Tom Lane <[email protected]>; +Cc: PostgreSQL Hackers <[email protected]>
On 6/24/23 02:08, Tom Lane wrote:
> Tomas Vondra <[email protected]> writes:
>> The problem is that the selectivity for "IS NULL" is estimated using the
>> table-level statistics. But the LEFT JOIN entirely breaks the idea that
>> the null_frac has anything to do with NULLs in the join result.
>
> Right.
>
>> I wonder how to improve this, say by adjusting the IS NULL selectivity
>> when we know to operate on the outer side of the join. We're able to
>> do this for antijoins, so maybe we could do that here, somehow?
>
> This mess is part of the long-term plan around the work I've been doing
> on outer-join-aware Vars. We now have infrastructure that can let
> the estimator routines see "oh, this Var isn't directly from a scan
> of its table, it's been passed through a potentially-nulling outer
> join --- and I can see which one". I don't have more than vague ideas
> about what happens next, but that is clearly an essential step on the
> road to doing better.
>
I was wondering if that work on outer-join-aware Vars could help with
this, but I wasn't following it very closely. I agree the ability to
check if the Var could be NULL due to an outer join seems useful, as it
says whether applying raw attribute statistics makes sense or not.
I was thinking about what to do for the case when that's not possible,
i.e. when the Var refers to nullable side of the join. Knowing that this
is happening is clearly not enough - we need to know how many new NULLs
are "injected" into the join result, and "communicate" that to the
estimation routines.
Attached is a very ugly experimental patch doing that, and with it the
estimate changes to this:
QUERY PLAN
----------------------------------------------------------------------
Hash Left Join (cost=3.25..18179.88 rows=999900 width=16)
(actual time=0.528..596.151 rows=999900 loops=1)
Hash Cond: (large.id = small.id)
Filter: ((small.id IS NULL) OR
(large.a = ANY ('{1000,2000,3000,4000,5000}'::integer[])))
Rows Removed by Filter: 100
-> Seq Scan on large (cost=0.00..14425.00 rows=1000000 width=8)
(actual time=0.069..176.138 rows=1000000 loops=1)
-> Hash (cost=2.00..2.00 rows=100 width=8)
(actual time=0.371..0.373 rows=100 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 12kB
-> Seq Scan on small (cost=0.00..2.00 rows=100 width=8)
(actual time=0.032..0.146 rows=100 loops=1)
Planning Time: 3.845 ms
Execution Time: 712.405 ms
(10 rows)
Seems nice, but. The patch is pretty ugly, I don't claim it works for
other queries or that this is exactly what we should do. It calculates
"unmatched frequency" next to eqjoinsel_inner, stashes that info into
sjinfo and the estimator (nulltestsel) then uses that to adjust the
nullfrac it gets from the statistics.
The good thing is this helps even for IS NULL checks on non-join-key
columns (where we don't switch to an antijoin), but there's a couple
things that I dislike ...
1) It's not restricted to outer joins or anything like that (this is
mostly just my laziness / interest in one particular query, but also
something the outer-join-aware patch might help with).
2) We probably don't want to pass this kind of information through
sjinfo. That was the simplest thing for an experimental patch, but I
suspect it's not the only piece of information we may need to pass to
the lower levels of estimation code.
3) I kinda doubt we actually want to move this responsibility (to
consider fraction of unmatched rows) to the low-level estimation
routines (e.g. nulltestsel and various others). AFAICS this just
"introduces NULLs" into the relation, so maybe we could "adjust" the
attribute statistics (in examine_variable?) by inflating null_frac and
modifying the other frequencies in MCV/histogram.
4) But I'm not sure we actually want to do that in these low-level
selectivity functions. The outer join essentially produces output with
two subsets - one with matches on the outer side, one without them. But
the side without matches has NULLs in all columns. In a way, we know
exactly how are these columns correlated - if we do the usual estimation
(even with the null_frac adjusted), we just throw this information away.
And when there's a lot of rows without a match, that seems bad.
So maybe we should split the join estimate into two parts, one for each
subset of the join result. One for the rows with a match (and then we
can just do what we do now, with the attribute stats we already have).
And one for the "unmatched part" where we know the values on the outer
side are NULL (and then we can easily "fake" stats with null_frac=1.0).
I really hope what I just wrote makes at least a little bit of sense.
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
Attachments:
[text/x-patch] left-join-estimates.patch (6.1K, ../../[email protected]/2-left-join-estimates.patch)
download | inline diff:
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index c4fcd0076e..a035e213a0 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -154,6 +154,13 @@ static double eqjoinsel_inner(Oid opfuncoid, Oid collation,
AttStatsSlot *sslot1, AttStatsSlot *sslot2,
Form_pg_statistic stats1, Form_pg_statistic stats2,
bool have_mcvs1, bool have_mcvs2);
+static double eqjoinsel_unmatch_left(Oid opfuncoid, Oid collation,
+ VariableStatData *vardata1, VariableStatData *vardata2,
+ double nd1, double nd2,
+ bool isdefault1, bool isdefault2,
+ AttStatsSlot *sslot1, AttStatsSlot *sslot2,
+ Form_pg_statistic stats1, Form_pg_statistic stats2,
+ bool have_mcvs1, bool have_mcvs2);
static double eqjoinsel_semi(Oid opfuncoid, Oid collation,
VariableStatData *vardata1, VariableStatData *vardata2,
double nd1, double nd2,
@@ -1710,6 +1717,9 @@ nulltestsel(PlannerInfo *root, NullTestType nulltesttype, Node *arg,
stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
freq_null = stats->stanullfrac;
+ if (sjinfo)
+ freq_null = freq_null + sjinfo->unmatched_frac - freq_null * sjinfo->unmatched_frac;
+
switch (nulltesttype)
{
case IS_NULL:
@@ -2249,6 +2259,7 @@ eqjoinsel(PG_FUNCTION_ARGS)
Oid collation = PG_GET_COLLATION();
double selec;
double selec_inner;
+ double unmatched_frac;
VariableStatData vardata1;
VariableStatData vardata2;
double nd1;
@@ -2321,6 +2332,26 @@ eqjoinsel(PG_FUNCTION_ARGS)
stats1, stats2,
have_mcvs1, have_mcvs2);
+ /*
+ * calculate fraction of right without of matching row on left
+ *
+ * FIXME Should be restricted to JOIN_LEFT, we should have similar logic
+ * for JOIN_FULL.
+ *
+ * XXX Probably should calculate unmatched as fraction of the join result,
+ * not of the relation on the right (because the matched part can have more
+ * matches per row and thus grow). Not sure. Depends on how it's used later.
+ */
+ unmatched_frac = eqjoinsel_unmatch_left(opfuncoid, collation,
+ &vardata1, &vardata2,
+ nd1, nd2,
+ isdefault1, isdefault2,
+ &sslot1, &sslot2,
+ stats1, stats2,
+ have_mcvs1, have_mcvs2);
+
+ sjinfo->unmatched_frac = unmatched_frac;
+
switch (sjinfo->jointype)
{
case JOIN_INNER:
@@ -2590,6 +2621,117 @@ eqjoinsel_inner(Oid opfuncoid, Oid collation,
return selec;
}
+/*
+ * eqjoinsel_unmatch_left
+ *
+ * XXX Mostly copy paste of eqjoinsel_inner, but calculates unmatched fraction
+ * of the relation on the left. See eqjoinsel_inner for more comments.
+ *
+ * XXX Maybe we could/should integrate this into eqjoinsel_inner, so that we
+ * don't have to walk the MCV lists twice?
+ */
+static double
+eqjoinsel_unmatch_left(Oid opfuncoid, Oid collation,
+ VariableStatData *vardata1, VariableStatData *vardata2,
+ double nd1, double nd2,
+ bool isdefault1, bool isdefault2,
+ AttStatsSlot *sslot1, AttStatsSlot *sslot2,
+ Form_pg_statistic stats1, Form_pg_statistic stats2,
+ bool have_mcvs1, bool have_mcvs2)
+{
+ double unmatchfreq;
+
+ if (have_mcvs1 && have_mcvs2)
+ {
+ LOCAL_FCINFO(fcinfo, 2);
+ FmgrInfo eqproc;
+ bool *hasmatch1;
+ bool *hasmatch2;
+ double matchprodfreq,
+ matchfreq1,
+ unmatchfreq1;
+ int i,
+ nmatches;
+
+ fmgr_info(opfuncoid, &eqproc);
+
+ /*
+ * Save a few cycles by setting up the fcinfo struct just once. Using
+ * FunctionCallInvoke directly also avoids failure if the eqproc
+ * returns NULL, though really equality functions should never do
+ * that.
+ */
+ InitFunctionCallInfoData(*fcinfo, &eqproc, 2, collation,
+ NULL, NULL);
+ fcinfo->args[0].isnull = false;
+ fcinfo->args[1].isnull = false;
+
+ hasmatch1 = (bool *) palloc0(sslot1->nvalues * sizeof(bool));
+ hasmatch2 = (bool *) palloc0(sslot2->nvalues * sizeof(bool));
+
+ /*
+ * Note we assume that each MCV will match at most one member of the
+ * other MCV list. If the operator isn't really equality, there could
+ * be multiple matches --- but we don't look for them, both for speed
+ * and because the math wouldn't add up...
+ */
+ matchprodfreq = 0.0;
+ nmatches = 0;
+ for (i = 0; i < sslot1->nvalues; i++)
+ {
+ int j;
+
+ fcinfo->args[0].value = sslot1->values[i];
+
+ for (j = 0; j < sslot2->nvalues; j++)
+ {
+ Datum fresult;
+
+ if (hasmatch2[j])
+ continue;
+ fcinfo->args[1].value = sslot2->values[j];
+ fcinfo->isnull = false;
+ fresult = FunctionCallInvoke(fcinfo);
+ if (!fcinfo->isnull && DatumGetBool(fresult))
+ {
+ hasmatch1[i] = hasmatch2[j] = true;
+ matchprodfreq += sslot1->numbers[i] * sslot2->numbers[j];
+ nmatches++;
+ break;
+ }
+ }
+ }
+ CLAMP_PROBABILITY(matchprodfreq);
+ /* Sum up frequencies of matched and unmatched MCVs */
+ matchfreq1 = unmatchfreq1 = 0.0;
+ for (i = 0; i < sslot1->nvalues; i++)
+ {
+ if (hasmatch1[i])
+ matchfreq1 += sslot1->numbers[i];
+ else
+ unmatchfreq1 += sslot1->numbers[i];
+ }
+ CLAMP_PROBABILITY(matchfreq1);
+ CLAMP_PROBABILITY(unmatchfreq1);
+
+ unmatchfreq = unmatchfreq1;
+ }
+ else
+ {
+ /*
+ * XXX Should this look at nullfrac on either side? Probably depends on
+ * if we're calculating fraction of NULLs or fraction of unmatched rows.
+ */
+ // unmatchfreq = (1.0 - nullfrac1) * (1.0 - nullfrac2);
+ if (nd1 > nd2)
+ unmatchfreq = (nd1 - nd2) * 1.0 / nd1;
+ else
+ unmatchfreq = 0.0;
+ }
+
+ return unmatchfreq;
+}
+
/*
* eqjoinsel_semi --- eqjoinsel for semi join
*
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index c17b53f7ad..6bc63e648e 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -2853,6 +2853,9 @@ struct SpecialJoinInfo
bool semi_can_hash; /* true if semi_operators are all hash */
List *semi_operators; /* OIDs of equality join operators */
List *semi_rhs_exprs; /* righthand-side expressions of these ops */
+
+ /* For outer join, fraction of rows without a match. */
+ Selectivity unmatched_frac;
};
/*
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
2023-06-24 00:08 Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tom Lane <[email protected]>
2023-06-24 11:23 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tomas Vondra <[email protected]>
@ 2023-06-26 09:22 ` Andrey Lepikhov <[email protected]>
2023-06-26 18:15 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Alena Rybakina <[email protected]>
0 siblings, 1 reply; 8+ messages in thread
From: Andrey Lepikhov @ 2023-06-26 09:22 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; Tom Lane <[email protected]>; +Cc: PostgreSQL Hackers <[email protected]>
On 24/6/2023 17:23, Tomas Vondra wrote:
> I really hope what I just wrote makes at least a little bit of sense.
Throw in one more example:
SELECT i AS id INTO l FROM generate_series(1,100000) i;
CREATE TABLE r (id int8, v text);
INSERT INTO r (id, v) VALUES (1, 't'), (-1, 'f');
ANALYZE l,r;
EXPLAIN ANALYZE
SELECT * FROM l LEFT OUTER JOIN r ON (r.id = l.id) WHERE r.v IS NULL;
Here you can see the same kind of underestimation:
Hash Left Join (... rows=500 width=14) (... rows=99999 ...)
So the eqjoinsel_unmatch_left() function should be modified for the case
where nd1<nd2.
--
regards,
Andrey Lepikhov
Postgres Professional
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
2023-06-24 00:08 Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tom Lane <[email protected]>
2023-06-24 11:23 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tomas Vondra <[email protected]>
2023-06-26 09:22 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Andrey Lepikhov <[email protected]>
@ 2023-06-26 18:15 ` Alena Rybakina <[email protected]>
2023-06-28 21:53 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tomas Vondra <[email protected]>
0 siblings, 1 reply; 8+ messages in thread
From: Alena Rybakina @ 2023-06-26 18:15 UTC (permalink / raw)
To: Andrey Lepikhov <[email protected]>; Tomas Vondra <[email protected]>; Tom Lane <[email protected]>; +Cc: PostgreSQL Hackers <[email protected]>
Hi, all!
On 24.06.2023 14:23, Tomas Vondra wrote:
> On 6/24/23 02:08, Tom Lane wrote:
>> Tomas Vondra<[email protected]> writes:
>>> The problem is that the selectivity for "IS NULL" is estimated using the
>>> table-level statistics. But the LEFT JOIN entirely breaks the idea that
>>> the null_frac has anything to do with NULLs in the join result.
>> Right.
>>
>>> I wonder how to improve this, say by adjusting the IS NULL selectivity
>>> when we know to operate on the outer side of the join. We're able to
>>> do this for antijoins, so maybe we could do that here, somehow?
>> This mess is part of the long-term plan around the work I've been doing
>> on outer-join-aware Vars. We now have infrastructure that can let
>> the estimator routines see "oh, this Var isn't directly from a scan
>> of its table, it's been passed through a potentially-nulling outer
>> join --- and I can see which one". I don't have more than vague ideas
>> about what happens next, but that is clearly an essential step on the
>> road to doing better.
>>
> I was wondering if that work on outer-join-aware Vars could help with
> this, but I wasn't following it very closely. I agree the ability to
> check if the Var could be NULL due to an outer join seems useful, as it
> says whether applying raw attribute statistics makes sense or not.
>
> I was thinking about what to do for the case when that's not possible,
> i.e. when the Var refers to nullable side of the join. Knowing that this
> is happening is clearly not enough - we need to know how many new NULLs
> are "injected" into the join result, and "communicate" that to the
> estimation routines.
>
> Attached is a very ugly experimental patch doing that, and with it the
> estimate changes to this:
>
> QUERY PLAN
> ----------------------------------------------------------------------
> Hash Left Join (cost=3.25..18179.88 rows=999900 width=16)
> (actual time=0.528..596.151 rows=999900 loops=1)
> Hash Cond: (large.id = small.id)
> Filter: ((small.id IS NULL) OR
> (large.a = ANY ('{1000,2000,3000,4000,5000}'::integer[])))
> Rows Removed by Filter: 100
> -> Seq Scan on large (cost=0.00..14425.00 rows=1000000 width=8)
> (actual time=0.069..176.138 rows=1000000 loops=1)
> -> Hash (cost=2.00..2.00 rows=100 width=8)
> (actual time=0.371..0.373 rows=100 loops=1)
> Buckets: 1024 Batches: 1 Memory Usage: 12kB
> -> Seq Scan on small (cost=0.00..2.00 rows=100 width=8)
> (actual time=0.032..0.146 rows=100 loops=1)
> Planning Time: 3.845 ms
> Execution Time: 712.405 ms
> (10 rows)
>
> Seems nice, but. The patch is pretty ugly, I don't claim it works for
> other queries or that this is exactly what we should do. It calculates
> "unmatched frequency" next to eqjoinsel_inner, stashes that info into
> sjinfo and the estimator (nulltestsel) then uses that to adjust the
> nullfrac it gets from the statistics.
>
> The good thing is this helps even for IS NULL checks on non-join-key
> columns (where we don't switch to an antijoin), but there's a couple
> things that I dislike ...
>
> 1) It's not restricted to outer joins or anything like that (this is
> mostly just my laziness / interest in one particular query, but also
> something the outer-join-aware patch might help with).
>
> 2) We probably don't want to pass this kind of information through
> sjinfo. That was the simplest thing for an experimental patch, but I
> suspect it's not the only piece of information we may need to pass to
> the lower levels of estimation code.
>
> 3) I kinda doubt we actually want to move this responsibility (to
> consider fraction of unmatched rows) to the low-level estimation
> routines (e.g. nulltestsel and various others). AFAICS this just
> "introduces NULLs" into the relation, so maybe we could "adjust" the
> attribute statistics (in examine_variable?) by inflating null_frac and
> modifying the other frequencies in MCV/histogram.
>
> 4) But I'm not sure we actually want to do that in these low-level
> selectivity functions. The outer join essentially produces output with
> two subsets - one with matches on the outer side, one without them. But
> the side without matches has NULLs in all columns. In a way, we know
> exactly how are these columns correlated - if we do the usual estimation
> (even with the null_frac adjusted), we just throw this information away.
> And when there's a lot of rows without a match, that seems bad.
>
> So maybe we should split the join estimate into two parts, one for each
> subset of the join result. One for the rows with a match (and then we
> can just do what we do now, with the attribute stats we already have).
> And one for the "unmatched part" where we know the values on the outer
> side are NULL (and then we can easily "fake" stats with null_frac=1.0).
>
>
> I really hope what I just wrote makes at least a little bit of sense.
>
>
> regards
>
I am also interested in this problem.
I did some refactoring of the source code in the patch, moved the
calculation of unmatched_fraction to eqjoinsel_inner.
I wrote myself in this commit as a co-author, if you don't mind, and I'm
going to continue working.
On 26.06.2023 12:22, Andrey Lepikhov wrote:
> On 24/6/2023 17:23, Tomas Vondra wrote:
>> I really hope what I just wrote makes at least a little bit of sense.
> Throw in one more example:
>
> SELECT i AS id INTO l FROM generate_series(1,100000) i;
> CREATE TABLE r (id int8, v text);
> INSERT INTO r (id, v) VALUES (1, 't'), (-1, 'f');
> ANALYZE l,r;
> EXPLAIN ANALYZE
> SELECT * FROM l LEFT OUTER JOIN r ON (r.id = l.id) WHERE r.v IS NULL;
>
> Here you can see the same kind of underestimation:
> Hash Left Join (... rows=500 width=14) (... rows=99999 ...)
>
> So the eqjoinsel_unmatch_left() function should be modified for the
> case where nd1<nd2.
>
Unfortunately, this patch could not fix the cardinality calculation in
this request, I'll try to look and figure out what is missing here.
*postgres=# SELECT i AS id INTO l FROM generate_series(1,100000) i;
CREATE TABLE r (id int8, v text);
INSERT INTO r (id, v) VALUES (1, 't'), (-1, 'f');
ANALYZE l,r;
EXPLAIN ANALYZE
SELECT * FROM l LEFT OUTER JOIN r ON (r.id = l.id) WHERE r.v IS NULL;
SELECT 100000
CREATE TABLE
INSERT 0 2
ANALYZE
QUERY PLAN
---------------------------------------------------------------------------------------------------------------
Hash Left Join (cost=1.04..1819.07 rows=1 width=14) (actual
time=0.143..114.792 rows=99999 loops=1)
Hash Cond: (l.id = r.id)
Filter: (r.v IS NULL)
Rows Removed by Filter: 1
-> Seq Scan on l (cost=0.00..1443.00 rows=100000 width=4) (actual
time=0.027..35.278 rows=100000 loops=1)
-> Hash (cost=1.02..1.02 rows=2 width=10) (actual
time=0.014..0.017 rows=2 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 9kB
-> Seq Scan on r (cost=0.00..1.02 rows=2 width=10) (actual
time=0.005..0.007 rows=2 loops=1)
Planning Time: 0.900 ms
Execution Time: 126.180 ms
(10 rows)*
As in the previous query, even with applied the patch, the cardinality
is calculated poorly here, I would even say that it has become worse:
EXPLAIN ANALYZE
SELECT * FROM large FULL JOIN small ON (large.id = small.id)
WHERE (large.a IS NULL);
MASTER:
*QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------
Merge Full Join (cost=127921.69..299941.59 rows=56503 width=16)
(actual time=795.092..795.094 rows=0 loops=1)
Merge Cond: (small.id = large.id)
Filter: (large.a IS NULL)
Rows Removed by Filter: 1000000
-> Sort (cost=158.51..164.16 rows=2260 width=8) (actual
time=0.038..0.046 rows=100 loops=1)
Sort Key: small.id
Sort Method: quicksort Memory: 29kB
-> Seq Scan on small (cost=0.00..32.60 rows=2260 width=8)
(actual time=0.013..0.022 rows=100 loops=1)
-> Materialize (cost=127763.19..132763.44 rows=1000050 width=8)
(actual time=363.016..649.103 rows=1000000 loops=1)
-> Sort (cost=127763.19..130263.31 rows=1000050 width=8)
(actual time=363.012..481.480 rows=1000000 loops=1)
Sort Key: large.id
Sort Method: external merge Disk: 17664kB
-> Seq Scan on large (cost=0.00..14425.50 rows=1000050
width=8) (actual time=0.009..111.166 rows=1000000 loops=1)
Planning Time: 0.124 ms
Execution Time: 797.139 ms
(15 rows)*
With patch:
*QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Hash Full Join (cost=3.25..18179.25 rows=999900 width=16) (actual
time=261.480..261.482 rows=0 loops=1)
Hash Cond: (large.id = small.id)
Filter: (large.a IS NULL)
Rows Removed by Filter: 1000000
-> Seq Scan on large (cost=0.00..14425.00 rows=1000000 width=8)
(actual time=0.006..92.827 rows=1000000 loops=1)
-> Hash (cost=2.00..2.00 rows=100 width=8) (actual
time=0.032..0.034 rows=100 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 12kB
-> Seq Scan on small (cost=0.00..2.00 rows=100 width=8)
(actual time=0.008..0.015 rows=100 loops=1)
Planning Time: 0.151 ms
Execution Time: 261.529 ms
(10 rows)
*
In addition, I found a few more queries, where the estimation of
cardinality with the patch has become better:
EXPLAIN ANALYZE
SELECT * FROM small LEFT JOIN large ON (large.id = small.id)
WHERE (small.b IS NULL);
MASTER:
*QUERY PLAN
-------------------------------------------------------------------------------------------------------------
Hash Right Join (cost=32.74..18758.45 rows=55003 width=16) (actual
time=0.100..0.104 rows=0 loops=1)
Hash Cond: (large.id = small.id)
-> Seq Scan on large (cost=0.00..14425.50 rows=1000050 width=8)
(never executed)
-> Hash (cost=32.60..32.60 rows=11 width=8) (actual
time=0.089..0.091 rows=0 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 8kB
-> Seq Scan on small (cost=0.00..32.60 rows=11 width=8)
(actual time=0.088..0.088 rows=0 loops=1)
Filter: (b IS NULL)
Rows Removed by Filter: 100
Planning Time: 0.312 ms
Execution Time: 0.192 ms
(10 rows)*
With patch:
*QUERY PLAN
-----------------------------------------------------------------------------------------------------------
Hash Right Join (cost=2.01..18177.02 rows=1 width=16) (actual
time=0.127..0.132 rows=0 loops=1)
Hash Cond: (large.id = small.id)
-> Seq Scan on large (cost=0.00..14425.00 rows=1000000 width=8)
(never executed)
-> Hash (cost=2.00..2.00 rows=1 width=8) (actual time=0.112..0.114
rows=0 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 8kB
-> Seq Scan on small (cost=0.00..2.00 rows=1 width=8)
(actual time=0.111..0.111 rows=0 loops=1)
Filter: (b IS NULL)
Rows Removed by Filter: 100
Planning Time: 0.984 ms
Execution Time: 0.237 ms
(10 rows)*
EXPLAIN ANALYZE
SELECT * FROM large FULL JOIN small ON (large.id = small.id)
WHERE (small.b IS NULL);
MASTER:
*QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------
Merge Full Join (cost=127921.69..299941.59 rows=56503 width=16)
(actual time=339.478..819.232 rows=999900 loops=1)
Merge Cond: (small.id = large.id)
Filter: (small.b IS NULL)
Rows Removed by Filter: 100
-> Sort (cost=158.51..164.16 rows=2260 width=8) (actual
time=0.129..0.136 rows=100 loops=1)
Sort Key: small.id
Sort Method: quicksort Memory: 29kB
-> Seq Scan on small (cost=0.00..32.60 rows=2260 width=8)
(actual time=0.044..0.075 rows=100 loops=1)
-> Materialize (cost=127763.19..132763.44 rows=1000050 width=8)
(actual time=339.260..605.444 rows=1000000 loops=1)
-> Sort (cost=127763.19..130263.31 rows=1000050 width=8)
(actual time=339.254..449.930 rows=1000000 loops=1)
Sort Key: large.id
Sort Method: external merge Disk: 17664kB
-> Seq Scan on large (cost=0.00..14425.50 rows=1000050
width=8) (actual time=0.032..104.484 rows=1000000 loops=1)
Planning Time: 0.324 ms
Execution Time: 859.705 ms
(15 rows)
*
With patch:
*QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Hash Full Join (cost=3.25..18179.25 rows=999900 width=16) (actual
time=0.162..349.683 rows=999900 loops=1)
Hash Cond: (large.id = small.id)
Filter: (small.b IS NULL)
Rows Removed by Filter: 100
-> Seq Scan on large (cost=0.00..14425.00 rows=1000000 width=8)
(actual time=0.021..95.972 rows=1000000 loops=1)
-> Hash (cost=2.00..2.00 rows=100 width=8) (actual
time=0.125..0.127 rows=100 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 12kB
-> Seq Scan on small (cost=0.00..2.00 rows=100 width=8)
(actual time=0.030..0.059 rows=100 loops=1)
Planning Time: 0.218 ms
Execution Time: 385.819 ms
(10 rows)
*
**
EXPLAIN ANALYZE
SELECT * FROM large RIGHT JOIN small ON (large.id = small.id)
WHERE (large.a IS NULL);
MASTER:
*QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------
Merge Left Join (cost=127921.69..299941.59 rows=56503 width=16)
(actual time=345.403..345.404 rows=0 loops=1)
Merge Cond: (small.id = large.id)
Filter: (large.a IS NULL)
Rows Removed by Filter: 100
-> Sort (cost=158.51..164.16 rows=2260 width=8) (actual
time=0.033..0.039 rows=100 loops=1)
Sort Key: small.id
Sort Method: quicksort Memory: 29kB
-> Seq Scan on small (cost=0.00..32.60 rows=2260 width=8)
(actual time=0.012..0.020 rows=100 loops=1)
-> Materialize (cost=127763.19..132763.44 rows=1000050 width=8)
(actual time=345.287..345.315 rows=101 loops=1)
-> Sort (cost=127763.19..130263.31 rows=1000050 width=8)
(actual time=345.283..345.295 rows=101 loops=1)
Sort Key: large.id
Sort Method: external merge Disk: 17664kB
-> Seq Scan on large (cost=0.00..14425.50 rows=1000050
width=8) (actual time=0.009..104.648 rows=1000000 loops=1)
Planning Time: 0.098 ms
Execution Time: 347.807 ms
(15 rows)*
With patch:
*QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Hash Right Join (cost=3.25..18179.25 rows=100 width=16) (actual
time=209.838..209.842 rows=0 loops=1)
Hash Cond: (large.id = small.id)
Filter: (large.a IS NULL)
Rows Removed by Filter: 100
-> Seq Scan on large (cost=0.00..14425.00 rows=1000000 width=8)
(actual time=0.006..91.571 rows=1000000 loops=1)
-> Hash (cost=2.00..2.00 rows=100 width=8) (actual
time=0.034..0.036 rows=100 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 12kB
-> Seq Scan on small (cost=0.00..2.00 rows=100 width=8)
(actual time=0.008..0.016 rows=100 loops=1)
Planning Time: 0.168 ms
Execution Time: 209.883 ms
(10 rows)*
Attachments:
[text/x-patch] 0001-Fixed-the-case-of-calculating-underestimated-cardina.patch (4.4K, ../../[email protected]/3-0001-Fixed-the-case-of-calculating-underestimated-cardina.patch)
download | inline diff:
From e8653477fbe7321325122a2d5032798cd6a95a8b Mon Sep 17 00:00:00 2001
From: Tomas Vondra <[email protected]>
Date: Mon, 26 Jun 2023 15:39:11 +0300
Subject: [PATCH] Fixed the case of calculating underestimated cardinality for
an LEFT JOIN with the restriction "IS NULL" in the clause. This error is
caused by an incorrect calculation of selectivity in the "IS NULL" clause,
since it took into account only table-level statistics without zero values in
the results of the join operation. This patch fixes this by calculating the
fraction of zero values on the right side of the join without of matching row
on left.
Co-authored-by: Alena Rybakina <[email protected]>
---
src/backend/utils/adt/selfuncs.c | 35 +++++++++++++++++++++++++++++---
src/include/nodes/pathnodes.h | 3 +++
2 files changed, 35 insertions(+), 3 deletions(-)
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index c4fcd0076ea..8e18aa1dd2b 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -153,7 +153,7 @@ static double eqjoinsel_inner(Oid opfuncoid, Oid collation,
bool isdefault1, bool isdefault2,
AttStatsSlot *sslot1, AttStatsSlot *sslot2,
Form_pg_statistic stats1, Form_pg_statistic stats2,
- bool have_mcvs1, bool have_mcvs2);
+ bool have_mcvs1, bool have_mcvs2, double *unmatched_frac);
static double eqjoinsel_semi(Oid opfuncoid, Oid collation,
VariableStatData *vardata1, VariableStatData *vardata2,
double nd1, double nd2,
@@ -1710,6 +1710,9 @@ nulltestsel(PlannerInfo *root, NullTestType nulltesttype, Node *arg,
stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
freq_null = stats->stanullfrac;
+ if (sjinfo)
+ freq_null = freq_null + sjinfo->unmatched_frac - freq_null * sjinfo->unmatched_frac;
+
switch (nulltesttype)
{
case IS_NULL:
@@ -2313,13 +2316,24 @@ eqjoinsel(PG_FUNCTION_ARGS)
}
/* We need to compute the inner-join selectivity in all cases */
+ /*
+ * calculate fraction of right without of matching row on left
+ *
+ * FIXME Should be restricted to JOIN_LEFT, we should have similar logic
+ * for JOIN_FULL.
+ *
+ * XXX Probably should calculate unmatched as fraction of the join result,
+ * not of the relation on the right (because the matched part can have more
+ * matches per row and thus grow). Not sure. Depends on how it's used later.
+ */
selec_inner = eqjoinsel_inner(opfuncoid, collation,
&vardata1, &vardata2,
nd1, nd2,
isdefault1, isdefault2,
&sslot1, &sslot2,
stats1, stats2,
- have_mcvs1, have_mcvs2);
+ have_mcvs1, have_mcvs2,
+ &sjinfo->unmatched_frac);
switch (sjinfo->jointype)
{
@@ -2407,7 +2421,7 @@ eqjoinsel_inner(Oid opfuncoid, Oid collation,
bool isdefault1, bool isdefault2,
AttStatsSlot *sslot1, AttStatsSlot *sslot2,
Form_pg_statistic stats1, Form_pg_statistic stats2,
- bool have_mcvs1, bool have_mcvs2)
+ bool have_mcvs1, bool have_mcvs2, double *unmatched_frac)
{
double selec;
@@ -2503,7 +2517,10 @@ eqjoinsel_inner(Oid opfuncoid, Oid collation,
}
CLAMP_PROBABILITY(matchfreq1);
CLAMP_PROBABILITY(unmatchfreq1);
+
+ *unmatched_frac = unmatchfreq1;
matchfreq2 = unmatchfreq2 = 0.0;
+
for (i = 0; i < sslot2->nvalues; i++)
{
if (hasmatch2[i])
@@ -2581,10 +2598,22 @@ eqjoinsel_inner(Oid opfuncoid, Oid collation,
double nullfrac2 = stats2 ? stats2->stanullfrac : 0.0;
selec = (1.0 - nullfrac1) * (1.0 - nullfrac2);
+
+ /*
+ * XXX Should this look at nullfrac on either side? Probably depends on
+ * if we're calculating fraction of NULLs or fraction of unmatched rows.
+ */
+ // unmatchfreq = (1.0 - nullfrac1) * (1.0 - nullfrac2);
if (nd1 > nd2)
+ {
selec /= nd1;
+ *unmatched_frac = (nd1 - nd2) * 1.0 / nd1;
+ }
else
+ {
selec /= nd2;
+ *unmatched_frac = 0.0;
+ }
}
return selec;
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index c17b53f7adb..6bc63e648e6 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -2853,6 +2853,9 @@ struct SpecialJoinInfo
bool semi_can_hash; /* true if semi_operators are all hash */
List *semi_operators; /* OIDs of equality join operators */
List *semi_rhs_exprs; /* righthand-side expressions of these ops */
+
+ /* For outer join, fraction of rows without a match. */
+ Selectivity unmatched_frac;
};
/*
--
2.34.1
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
2023-06-24 00:08 Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tom Lane <[email protected]>
2023-06-24 11:23 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tomas Vondra <[email protected]>
2023-06-26 09:22 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Andrey Lepikhov <[email protected]>
2023-06-26 18:15 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Alena Rybakina <[email protected]>
@ 2023-06-28 21:53 ` Tomas Vondra <[email protected]>
2023-07-06 13:51 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Alena Rybakina <[email protected]>
0 siblings, 1 reply; 8+ messages in thread
From: Tomas Vondra @ 2023-06-28 21:53 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; Andrey Lepikhov <[email protected]>; Tom Lane <[email protected]>; +Cc: PostgreSQL Hackers <[email protected]>
On 6/26/23 20:15, Alena Rybakina wrote:
> Hi, all!
>
> On 24.06.2023 14:23, Tomas Vondra wrote:
>> On 6/24/23 02:08, Tom Lane wrote:
>>> Tomas Vondra <[email protected]> writes:
>>>> The problem is that the selectivity for "IS NULL" is estimated using the
>>>> table-level statistics. But the LEFT JOIN entirely breaks the idea that
>>>> the null_frac has anything to do with NULLs in the join result.
>>> Right.
>>>
>>>> I wonder how to improve this, say by adjusting the IS NULL selectivity
>>>> when we know to operate on the outer side of the join. We're able to
>>>> do this for antijoins, so maybe we could do that here, somehow?
>>> This mess is part of the long-term plan around the work I've been doing
>>> on outer-join-aware Vars. We now have infrastructure that can let
>>> the estimator routines see "oh, this Var isn't directly from a scan
>>> of its table, it's been passed through a potentially-nulling outer
>>> join --- and I can see which one". I don't have more than vague ideas
>>> about what happens next, but that is clearly an essential step on the
>>> road to doing better.
>>>
>> I was wondering if that work on outer-join-aware Vars could help with
>> this, but I wasn't following it very closely. I agree the ability to
>> check if the Var could be NULL due to an outer join seems useful, as it
>> says whether applying raw attribute statistics makes sense or not.
>>
>> I was thinking about what to do for the case when that's not possible,
>> i.e. when the Var refers to nullable side of the join. Knowing that this
>> is happening is clearly not enough - we need to know how many new NULLs
>> are "injected" into the join result, and "communicate" that to the
>> estimation routines.
>>
>> Attached is a very ugly experimental patch doing that, and with it the
>> estimate changes to this:
>>
>> QUERY PLAN
>> ----------------------------------------------------------------------
>> Hash Left Join (cost=3.25..18179.88 rows=999900 width=16)
>> (actual time=0.528..596.151 rows=999900 loops=1)
>> Hash Cond: (large.id = small.id)
>> Filter: ((small.id IS NULL) OR
>> (large.a = ANY ('{1000,2000,3000,4000,5000}'::integer[])))
>> Rows Removed by Filter: 100
>> -> Seq Scan on large (cost=0.00..14425.00 rows=1000000 width=8)
>> (actual time=0.069..176.138 rows=1000000 loops=1)
>> -> Hash (cost=2.00..2.00 rows=100 width=8)
>> (actual time=0.371..0.373 rows=100 loops=1)
>> Buckets: 1024 Batches: 1 Memory Usage: 12kB
>> -> Seq Scan on small (cost=0.00..2.00 rows=100 width=8)
>> (actual time=0.032..0.146 rows=100 loops=1)
>> Planning Time: 3.845 ms
>> Execution Time: 712.405 ms
>> (10 rows)
>>
>> Seems nice, but. The patch is pretty ugly, I don't claim it works for
>> other queries or that this is exactly what we should do. It calculates
>> "unmatched frequency" next to eqjoinsel_inner, stashes that info into
>> sjinfo and the estimator (nulltestsel) then uses that to adjust the
>> nullfrac it gets from the statistics.
>>
>> The good thing is this helps even for IS NULL checks on non-join-key
>> columns (where we don't switch to an antijoin), but there's a couple
>> things that I dislike ...
>>
>> 1) It's not restricted to outer joins or anything like that (this is
>> mostly just my laziness / interest in one particular query, but also
>> something the outer-join-aware patch might help with).
>>
>> 2) We probably don't want to pass this kind of information through
>> sjinfo. That was the simplest thing for an experimental patch, but I
>> suspect it's not the only piece of information we may need to pass to
>> the lower levels of estimation code.
>>
>> 3) I kinda doubt we actually want to move this responsibility (to
>> consider fraction of unmatched rows) to the low-level estimation
>> routines (e.g. nulltestsel and various others). AFAICS this just
>> "introduces NULLs" into the relation, so maybe we could "adjust" the
>> attribute statistics (in examine_variable?) by inflating null_frac and
>> modifying the other frequencies in MCV/histogram.
>>
>> 4) But I'm not sure we actually want to do that in these low-level
>> selectivity functions. The outer join essentially produces output with
>> two subsets - one with matches on the outer side, one without them. But
>> the side without matches has NULLs in all columns. In a way, we know
>> exactly how are these columns correlated - if we do the usual estimation
>> (even with the null_frac adjusted), we just throw this information away.
>> And when there's a lot of rows without a match, that seems bad.
>>
>> So maybe we should split the join estimate into two parts, one for each
>> subset of the join result. One for the rows with a match (and then we
>> can just do what we do now, with the attribute stats we already have).
>> And one for the "unmatched part" where we know the values on the outer
>> side are NULL (and then we can easily "fake" stats with null_frac=1.0).
>>
>>
>> I really hope what I just wrote makes at least a little bit of sense.
>>
>>
>> regards
>>
> I am also interested in this problem.
>
> I did some refactoring of the source code in the patch, moved the
> calculation of unmatched_fraction to eqjoinsel_inner.
> I wrote myself in this commit as a co-author, if you don't mind, and I'm
> going to continue working.
>
Sure, if you want to take over the patch and continue working on it,
that's perfectly fine with me. I'm happy to cooperate on it, doing
reviews etc.
>
> On 26.06.2023 12:22, Andrey Lepikhov wrote:
>> On 24/6/2023 17:23, Tomas Vondra wrote:
>>> I really hope what I just wrote makes at least a little bit of sense.
>> Throw in one more example:
>>
>> SELECT i AS id INTO l FROM generate_series(1,100000) i;
>> CREATE TABLE r (id int8, v text);
>> INSERT INTO r (id, v) VALUES (1, 't'), (-1, 'f');
>> ANALYZE l,r;
>> EXPLAIN ANALYZE
>> SELECT * FROM l LEFT OUTER JOIN r ON (r.id = l.id) WHERE r.v IS NULL;
>>
>> Here you can see the same kind of underestimation:
>> Hash Left Join (... rows=500 width=14) (... rows=99999 ...)
>>
>> So the eqjoinsel_unmatch_left() function should be modified for the
>> case where nd1<nd2.
>>
> Unfortunately, this patch could not fix the cardinality calculation in
> this request, I'll try to look and figure out what is missing here.
>
> *postgres=# SELECT i AS id INTO l FROM generate_series(1,100000) i;
> CREATE TABLE r (id int8, v text);
> INSERT INTO r (id, v) VALUES (1, 't'), (-1, 'f');
> ANALYZE l,r;
> EXPLAIN ANALYZE
> SELECT * FROM l LEFT OUTER JOIN r ON (r.id = l.id) WHERE r.v IS NULL;
> SELECT 100000
> CREATE TABLE
> INSERT 0 2
> ANALYZE
> QUERY
> PLAN
> ---------------------------------------------------------------------------------------------------------------
> Hash Left Join (cost=1.04..1819.07 rows=1 width=14) (actual
> time=0.143..114.792 rows=99999 loops=1)
> Hash Cond: (l.id = r.id)
> Filter: (r.v IS NULL)
> Rows Removed by Filter: 1
> -> Seq Scan on l (cost=0.00..1443.00 rows=100000 width=4) (actual
> time=0.027..35.278 rows=100000 loops=1)
> -> Hash (cost=1.02..1.02 rows=2 width=10) (actual time=0.014..0.017
> rows=2 loops=1)
> Buckets: 1024 Batches: 1 Memory Usage: 9kB
> -> Seq Scan on r (cost=0.00..1.02 rows=2 width=10) (actual
> time=0.005..0.007 rows=2 loops=1)
> Planning Time: 0.900 ms
> Execution Time: 126.180 ms
> (10 rows)*
>
>
> As in the previous query, even with applied the patch, the cardinality
> is calculated poorly here, I would even say that it has become worse:
>
> EXPLAIN ANALYZE
> SELECT * FROM large FULL JOIN small ON (large.id = small.id)
> WHERE (large.a IS NULL);
>
> MASTER:
>
> * QUERY
> PLAN
> -----------------------------------------------------------------------------------------------------------------------------------
> Merge Full Join (cost=127921.69..299941.59 rows=56503 width=16)
> (actual time=795.092..795.094 rows=0 loops=1)
> Merge Cond: (small.id = large.id)
> Filter: (large.a IS NULL)
> Rows Removed by Filter: 1000000
> -> Sort (cost=158.51..164.16 rows=2260 width=8) (actual
> time=0.038..0.046 rows=100 loops=1)
> Sort Key: small.id
> Sort Method: quicksort Memory: 29kB
> -> Seq Scan on small (cost=0.00..32.60 rows=2260 width=8)
> (actual time=0.013..0.022 rows=100 loops=1)
> -> Materialize (cost=127763.19..132763.44 rows=1000050 width=8)
> (actual time=363.016..649.103 rows=1000000 loops=1)
> -> Sort (cost=127763.19..130263.31 rows=1000050 width=8)
> (actual time=363.012..481.480 rows=1000000 loops=1)
> Sort Key: large.id
> Sort Method: external merge Disk: 17664kB
> -> Seq Scan on large (cost=0.00..14425.50 rows=1000050
> width=8) (actual time=0.009..111.166 rows=1000000 loops=1)
> Planning Time: 0.124 ms
> Execution Time: 797.139 ms
> (15 rows)*
>
> With patch:
>
> * QUERY
> PLAN
> ----------------------------------------------------------------------------------------------------------------------
> Hash Full Join (cost=3.25..18179.25 rows=999900 width=16) (actual
> time=261.480..261.482 rows=0 loops=1)
> Hash Cond: (large.id = small.id)
> Filter: (large.a IS NULL)
> Rows Removed by Filter: 1000000
> -> Seq Scan on large (cost=0.00..14425.00 rows=1000000 width=8)
> (actual time=0.006..92.827 rows=1000000 loops=1)
> -> Hash (cost=2.00..2.00 rows=100 width=8) (actual
> time=0.032..0.034 rows=100 loops=1)
> Buckets: 1024 Batches: 1 Memory Usage: 12kB
> -> Seq Scan on small (cost=0.00..2.00 rows=100 width=8)
> (actual time=0.008..0.015 rows=100 loops=1)
> Planning Time: 0.151 ms
> Execution Time: 261.529 ms
> (10 rows)
> *
>
> In addition, I found a few more queries, where the estimation of
> cardinality with the patch has become better:
>
>
Yes, this does not surprise me at all - the patch was very early /
experimental code, and I only really aimed it at that single example
query. So don't hesitate to rethink what/how the patch works.
I do think collecting / constructing a wider set of queries with joins
of different types is going to be an important step in working on this
patch and making sure it doesn't break something.
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
2023-06-24 00:08 Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tom Lane <[email protected]>
2023-06-24 11:23 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tomas Vondra <[email protected]>
2023-06-26 09:22 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Andrey Lepikhov <[email protected]>
2023-06-26 18:15 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Alena Rybakina <[email protected]>
2023-06-28 21:53 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tomas Vondra <[email protected]>
@ 2023-07-06 13:51 ` Alena Rybakina <[email protected]>
2023-07-06 15:38 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tomas Vondra <[email protected]>
0 siblings, 1 reply; 8+ messages in thread
From: Alena Rybakina @ 2023-07-06 13:51 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: PostgreSQL Hackers <[email protected]>; Andrey Lepikhov <[email protected]>; Tom Lane <[email protected]>
Hi, all!
On 26.06.2023 12:22, Andrey Lepikhov wrote:
> On 24/6/2023 17:23, Tomas Vondra wrote:
>> I really hope what I just wrote makes at least a little bit of sense.
> Throw in one more example:
>
> SELECT i AS id INTO l FROM generate_series(1,100000) i;
> CREATE TABLE r (id int8, v text);
> INSERT INTO r (id, v) VALUES (1, 't'), (-1, 'f');
> ANALYZE l,r;
> EXPLAIN ANALYZE
> SELECT * FROM l LEFT OUTER JOIN r ON (r.id = l.id) WHERE r.v IS NULL;
>
> Here you can see the same kind of underestimation:
> Hash Left Join (... rows=500 width=14) (... rows=99999 ...)
>
> So the eqjoinsel_unmatch_left() function should be modified for the
> case where nd1<nd2.
>
>
> Unfortunately, this patch could not fix the cardinality calculation in
> this request, I'll try to look and figure out what is missing here.
I tried to fix the cardinality score in the query above by changing:
diff --git a/src/backend/utils/adt/selfuncs.c
b/src/backend/utils/adt/selfuncs.c
index 8e18aa1dd2b..40901836146 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -2604,11 +2604,16 @@ eqjoinsel_inner(Oid opfuncoid, Oid collation,
* if we're calculating fraction of NULLs or fraction
of unmatched rows.
*/
// unmatchfreq = (1.0 - nullfrac1) * (1.0 - nullfrac2);
- if (nd1 > nd2)
+ if (nd1 != nd2)
{
- selec /= nd1;
- *unmatched_frac = (nd1 - nd2) * 1.0 / nd1;
+ selec /= Max(nd1, nd2);
+ *unmatched_frac = abs(nd1 - nd2) * 1.0 /
Max(nd1, nd2);
}
+ /*if (nd1 > nd2)
+ {
+ selec /= nd1;
+ *unmatched_frac = nd1 - nd2 * 1.0 / nd1;
+ }*/
else
{
selec /= nd2;
and it worked:
SELECT i AS id INTO l FROM generate_series(1,100000) i;
CREATE TABLE r (id int8, v text);
INSERT INTO r (id, v) VALUES (1, 't'), (-1, 'f');
ANALYZE l,r;
EXPLAIN ANALYZE
SELECT * FROM l LEFT OUTER JOIN r ON (r.id = l.id) WHERE r.v IS NULL;
ERROR: relation "l" already exists
ERROR: relation "r" already exists
INSERT 0 2
ANALYZE
QUERY PLAN
---------------------------------------------------------------------------------------------------------------
Hash Left Join (cost=1.09..1944.13 rows=99998 width=14) (actual
time=0.152..84.184 rows=99999 loops=1)
Hash Cond: (l.id = r.id)
Filter: (r.v IS NULL)
Rows Removed by Filter: 2
-> Seq Scan on l (cost=0.00..1443.00 rows=100000 width=4) (actual
time=0.040..27.635 rows=100000 loops=1)
-> Hash (cost=1.04..1.04 rows=4 width=10) (actual
time=0.020..0.022 rows=4 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 9kB
-> Seq Scan on r (cost=0.00..1.04 rows=4 width=10) (actual
time=0.009..0.011 rows=4 loops=1)
Planning Time: 0.954 ms
Execution Time: 92.309 ms
(10 rows)
It looks too simple and I suspect that I might have missed something
somewhere, but so far I haven't found any examples of queries where it
doesn't work.
I didn't see it breaking anything in the examples from my previous
letter [1].
1.
https://www.postgresql.org/message-id/7af1464e-2e24-cfb1-b6d4-1544757f8cfa%40yandex.ru
Unfortunately, I can't understand your idea from point 4, please explain it?
The good thing is this helps even for IS NULL checks on non-join-key
columns (where we don't switch to an antijoin), but there's a couple
things that I dislike ...
1) It's not restricted to outer joins or anything like that (this is
mostly just my laziness / interest in one particular query, but also
something the outer-join-aware patch might help with).
2) We probably don't want to pass this kind of information through
sjinfo. That was the simplest thing for an experimental patch, but I
suspect it's not the only piece of information we may need to pass to
the lower levels of estimation code.
3) I kinda doubt we actually want to move this responsibility (to
consider fraction of unmatched rows) to the low-level estimation
routines (e.g. nulltestsel and various others). AFAICS this just
"introduces NULLs" into the relation, so maybe we could "adjust" the
attribute statistics (in examine_variable?) by inflating null_frac and
modifying the other frequencies in MCV/histogram.
4) But I'm not sure we actually want to do that in these low-level
selectivity functions. The outer join essentially produces output with
two subsets - one with matches on the outer side, one without them. But
the side without matches has NULLs in all columns. In a way, we know
exactly how are these columns correlated - if we do the usual estimation
(even with the null_frac adjusted), we just throw this information away.
And when there's a lot of rows without a match, that seems bad.
--
Regards,
Alena Rybakina
Postgres Professional
Attachments:
[text/x-patch] 0001-Fixed-the-case-of-calculating-underestimated-cardina.patch (4.5K, ../../[email protected]/3-0001-Fixed-the-case-of-calculating-underestimated-cardina.patch)
download | inline diff:
From 54a24390f1137a77c9755a875774a75ae8cf2424 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <[email protected]>
Date: Mon, 26 Jun 2023 15:39:11 +0300
Subject: [PATCH] Fixed the case of calculating underestimated cardinality for
an LEFT JOIN with the restriction "IS NULL" in the clause. This error is
caused by an incorrect calculation of selectivity in the "IS NULL" clause,
since it took into account only table-level statistics without zero values in
the results of the join operation. This patch fixes this by calculating the
fraction of zero values on the right side of the join without of matching row
on left.
Co-authored-by: Alena Rybakina <[email protected]>
---
src/backend/utils/adt/selfuncs.c | 39 ++++++++++++++++++++++++++++----
src/include/nodes/pathnodes.h | 3 +++
2 files changed, 37 insertions(+), 5 deletions(-)
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index c4fcd0076ea..a0e3834453b 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -153,7 +153,7 @@ static double eqjoinsel_inner(Oid opfuncoid, Oid collation,
bool isdefault1, bool isdefault2,
AttStatsSlot *sslot1, AttStatsSlot *sslot2,
Form_pg_statistic stats1, Form_pg_statistic stats2,
- bool have_mcvs1, bool have_mcvs2);
+ bool have_mcvs1, bool have_mcvs2, double *unmatched_frac);
static double eqjoinsel_semi(Oid opfuncoid, Oid collation,
VariableStatData *vardata1, VariableStatData *vardata2,
double nd1, double nd2,
@@ -1710,6 +1710,9 @@ nulltestsel(PlannerInfo *root, NullTestType nulltesttype, Node *arg,
stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
freq_null = stats->stanullfrac;
+ if (sjinfo)
+ freq_null = freq_null + sjinfo->unmatched_frac - freq_null * sjinfo->unmatched_frac;
+
switch (nulltesttype)
{
case IS_NULL:
@@ -2313,13 +2316,24 @@ eqjoinsel(PG_FUNCTION_ARGS)
}
/* We need to compute the inner-join selectivity in all cases */
+ /*
+ * calculate fraction of right without of matching row on left
+ *
+ * FIXME Should be restricted to JOIN_LEFT, we should have similar logic
+ * for JOIN_FULL.
+ *
+ * XXX Probably should calculate unmatched as fraction of the join result,
+ * not of the relation on the right (because the matched part can have more
+ * matches per row and thus grow). Not sure. Depends on how it's used later.
+ */
selec_inner = eqjoinsel_inner(opfuncoid, collation,
&vardata1, &vardata2,
nd1, nd2,
isdefault1, isdefault2,
&sslot1, &sslot2,
stats1, stats2,
- have_mcvs1, have_mcvs2);
+ have_mcvs1, have_mcvs2,
+ &sjinfo->unmatched_frac);
switch (sjinfo->jointype)
{
@@ -2407,7 +2421,7 @@ eqjoinsel_inner(Oid opfuncoid, Oid collation,
bool isdefault1, bool isdefault2,
AttStatsSlot *sslot1, AttStatsSlot *sslot2,
Form_pg_statistic stats1, Form_pg_statistic stats2,
- bool have_mcvs1, bool have_mcvs2)
+ bool have_mcvs1, bool have_mcvs2, double *unmatched_frac)
{
double selec;
@@ -2503,7 +2517,10 @@ eqjoinsel_inner(Oid opfuncoid, Oid collation,
}
CLAMP_PROBABILITY(matchfreq1);
CLAMP_PROBABILITY(unmatchfreq1);
+
+ *unmatched_frac = unmatchfreq1;
matchfreq2 = unmatchfreq2 = 0.0;
+
for (i = 0; i < sslot2->nvalues; i++)
{
if (hasmatch2[i])
@@ -2581,10 +2598,22 @@ eqjoinsel_inner(Oid opfuncoid, Oid collation,
double nullfrac2 = stats2 ? stats2->stanullfrac : 0.0;
selec = (1.0 - nullfrac1) * (1.0 - nullfrac2);
- if (nd1 > nd2)
- selec /= nd1;
+
+ /*
+ * XXX Should this look at nullfrac on either side? Probably depends on
+ * if we're calculating fraction of NULLs or fraction of unmatched rows.
+ */
+ // unmatchfreq = (1.0 - nullfrac1) * (1.0 - nullfrac2);
+ if (nd1 != nd2)
+ {
+ selec /= Max(nd1, nd2);
+ *unmatched_frac = abs(nd1 - nd2) * 1.0 / Max(nd1, nd2);
+ }
else
+ {
selec /= nd2;
+ *unmatched_frac = 0.0;
+ }
}
return selec;
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index c17b53f7adb..6bc63e648e6 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -2853,6 +2853,9 @@ struct SpecialJoinInfo
bool semi_can_hash; /* true if semi_operators are all hash */
List *semi_operators; /* OIDs of equality join operators */
List *semi_rhs_exprs; /* righthand-side expressions of these ops */
+
+ /* For outer join, fraction of rows without a match. */
+ Selectivity unmatched_frac;
};
/*
--
2.34.1
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs
2023-06-24 00:08 Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tom Lane <[email protected]>
2023-06-24 11:23 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tomas Vondra <[email protected]>
2023-06-26 09:22 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Andrey Lepikhov <[email protected]>
2023-06-26 18:15 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Alena Rybakina <[email protected]>
2023-06-28 21:53 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tomas Vondra <[email protected]>
2023-07-06 13:51 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Alena Rybakina <[email protected]>
@ 2023-07-06 15:38 ` Tomas Vondra <[email protected]>
0 siblings, 0 replies; 8+ messages in thread
From: Tomas Vondra @ 2023-07-06 15:38 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: PostgreSQL Hackers <[email protected]>; Andrey Lepikhov <[email protected]>; Tom Lane <[email protected]>
On 7/6/23 15:51, Alena Rybakina wrote:
> Hi, all!
>
> On 26.06.2023 12:22, Andrey Lepikhov wrote:
>> On 24/6/2023 17:23, Tomas Vondra wrote:
>>> I really hope what I just wrote makes at least a little bit of sense.
>> Throw in one more example:
>>
>> SELECT i AS id INTO l FROM generate_series(1,100000) i;
>> CREATE TABLE r (id int8, v text);
>> INSERT INTO r (id, v) VALUES (1, 't'), (-1, 'f');
>> ANALYZE l,r;
>> EXPLAIN ANALYZE
>> SELECT * FROM l LEFT OUTER JOIN r ON (r.id = l.id) WHERE r.v IS NULL;
>>
>> Here you can see the same kind of underestimation:
>> Hash Left Join (... rows=500 width=14) (... rows=99999 ...)
>>
>> So the eqjoinsel_unmatch_left() function should be modified for the
>> case where nd1<nd2.
>>
>>
>> Unfortunately, this patch could not fix the cardinality calculation in
>> this request, I'll try to look and figure out what is missing here.
>
> I tried to fix the cardinality score in the query above by changing:
>
> diff --git a/src/backend/utils/adt/selfuncs.c
> b/src/backend/utils/adt/selfuncs.c
> index 8e18aa1dd2b..40901836146 100644
> --- a/src/backend/utils/adt/selfuncs.c
> +++ b/src/backend/utils/adt/selfuncs.c
> @@ -2604,11 +2604,16 @@ eqjoinsel_inner(Oid opfuncoid, Oid collation,
> * if we're calculating fraction of NULLs or fraction of
> unmatched rows.
> */
> // unmatchfreq = (1.0 - nullfrac1) * (1.0 - nullfrac2);
> - if (nd1 > nd2)
> + if (nd1 != nd2)
> {
> - selec /= nd1;
> - *unmatched_frac = (nd1 - nd2) * 1.0 / nd1;
> + selec /= Max(nd1, nd2);
> + *unmatched_frac = abs(nd1 - nd2) * 1.0 /
> Max(nd1, nd2);
> }
> + /*if (nd1 > nd2)
> + {
> + selec /= nd1;
> + *unmatched_frac = nd1 - nd2 * 1.0 / nd1;
> + }*/
> else
> {
> selec /= nd2;
>
> and it worked:
>
> SELECT i AS id INTO l FROM generate_series(1,100000) i;
> CREATE TABLE r (id int8, v text);
> INSERT INTO r (id, v) VALUES (1, 't'), (-1, 'f');
> ANALYZE l,r;
> EXPLAIN ANALYZE
> SELECT * FROM l LEFT OUTER JOIN r ON (r.id = l.id) WHERE r.v IS NULL;
> ERROR: relation "l" already exists
> ERROR: relation "r" already exists
> INSERT 0 2
> ANALYZE
> QUERY
> PLAN
> ---------------------------------------------------------------------------------------------------------------
> Hash Left Join (cost=1.09..1944.13 rows=99998 width=14) (actual
> time=0.152..84.184 rows=99999 loops=1)
> Hash Cond: (l.id = r.id)
> Filter: (r.v IS NULL)
> Rows Removed by Filter: 2
> -> Seq Scan on l (cost=0.00..1443.00 rows=100000 width=4) (actual
> time=0.040..27.635 rows=100000 loops=1)
> -> Hash (cost=1.04..1.04 rows=4 width=10) (actual time=0.020..0.022
> rows=4 loops=1)
> Buckets: 1024 Batches: 1 Memory Usage: 9kB
> -> Seq Scan on r (cost=0.00..1.04 rows=4 width=10) (actual
> time=0.009..0.011 rows=4 loops=1)
> Planning Time: 0.954 ms
> Execution Time: 92.309 ms
> (10 rows)
>
> It looks too simple and I suspect that I might have missed something
> somewhere, but so far I haven't found any examples of queries where it
> doesn't work.
>
> I didn't see it breaking anything in the examples from my previous
> letter [1].
>
I think it's correct. Or at least it doesn't break anything my patch
didn't already break. My patch was simply written for one specific
query, so it didn't consider the option that the nd1 and nd2 values
might be in the opposite direction ...
> 1.
> https://www.postgresql.org/message-id/7af1464e-2e24-cfb1-b6d4-1544757f8cfa%40yandex.ru
>
>
> Unfortunately, I can't understand your idea from point 4, please explain it?
>
> The good thing is this helps even for IS NULL checks on non-join-key
> columns (where we don't switch to an antijoin), but there's a couple
> things that I dislike ...
>
> 1) It's not restricted to outer joins or anything like that (this is
> mostly just my laziness / interest in one particular query, but also
> something the outer-join-aware patch might help with).
>
> 2) We probably don't want to pass this kind of information through
> sjinfo. That was the simplest thing for an experimental patch, but I
> suspect it's not the only piece of information we may need to pass to
> the lower levels of estimation code.
>
> 3) I kinda doubt we actually want to move this responsibility (to
> consider fraction of unmatched rows) to the low-level estimation
> routines (e.g. nulltestsel and various others). AFAICS this just
> "introduces NULLs" into the relation, so maybe we could "adjust" the
> attribute statistics (in examine_variable?) by inflating null_frac and
> modifying the other frequencies in MCV/histogram.
>
> 4) But I'm not sure we actually want to do that in these low-level
> selectivity functions. The outer join essentially produces output with
> two subsets - one with matches on the outer side, one without them. But
> the side without matches has NULLs in all columns. In a way, we know
> exactly how are these columns correlated - if we do the usual estimation
> (even with the null_frac adjusted), we just throw this information away.
> And when there's a lot of rows without a match, that seems bad.
>
Well, one option would be to modify all selectivity functions to do
something like the patch does for nulltestsel(). That seems a bit
cumbersome because why should those places care about maybe running on
the outer side of a join, or what? For code in extensions this would be
particularly problematic, I think.
So what I was thinking about doing this in a way that'd make this
automatic, without having to modify the selectivity functions.
Option (3) is very simple - examine_variable would simply adjust the
statistics by tweaking the null_frac field, when looking at variables on
the outer side of the join. But it has issues when estimating multiple
conditions.
Imagine t1 has 1M rows, and we want to estimate
SELECT * FROM t1 LEFT JOIN t2 ON (t1.id = t2.id)
WHERE ((t2.a=1) AND (t2.b=1))
but only 50% of the t1 rows has a match in t2. Assume each of the t2
conditions matches 100% rows in the table. With the correction, this
means 50% selectivity for each condition. And if we combine them the
usual way, it's 0.5 * 0.5 = 0.25.
But we know all the rows in the "matching" part match the condition, so
the correct selectivity should be 0.5.
In a way, this is just another case of estimation issues due to the
assumption of independence.
But (4) was suggesting we could improve this essentially by treating the
join as two distinct sets of rows
- the inner join result
- rows without match on the outer side
For the inner part, we would do estimates as now (using the regular
per-column statistics). If we knew the conditions match 100% rows, we'd
still get 100% when the conditions are combined.
For the second part of the join we know the outer side is just NULLs in
all columns, and that'd make the estimation much simpler for most
clauses. We'd just need to have "fake" statistics with null_frac=1.0 and
that's it.
And then we'd just combine these two selectivities. If we know the inner
side is 50% and all rows match the conditions, and no rows in the other
50% match, the selectivity is 50%.
inner_part * inner_sel + outer_part * outer_sel = 0.5 * 1.0 + 0.0 = 0.5
Now, we still have issues with independence assumption in each of these
parts separately. But that's OK, I think.
I think (4) could be implemented by doing the current estimation for the
inner part, and by tweaking examine_variable in the "outer" part in a
way similar to (3). Except that it just sets null_frac=1.0 everywhere.
FWIW, I used "AND" in the example for simplicity, but that'd probably be
pushed to the baserel level. There'd need to be OR to keep it at the
join level, but the overall issue is the same, I think.
Also, this entirely ignores extended statistics - I have no idea how we
might tweak those in (3). For (4) we don't need to tweak those at all,
because for inner part we can just apply them as is, and for outer part
it's irrelevant because everything is NULL.
I hope this makes more sense. If not, let me know and I'll try to
explain it better.
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
^ permalink raw reply [nested|flat] 8+ messages in thread
end of thread, other threads:[~2023-07-06 15:38 UTC | newest]
Thread overview: 8+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2020-08-19 12:34 [PATCH v3 3/5] pg_rewind: Replace the hybrid list+array data structure with simplehash. Heikki Linnakangas <[email protected]>
2023-06-24 00:08 Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tom Lane <[email protected]>
2023-06-24 11:23 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tomas Vondra <[email protected]>
2023-06-26 09:22 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Andrey Lepikhov <[email protected]>
2023-06-26 18:15 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Alena Rybakina <[email protected]>
2023-06-28 21:53 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tomas Vondra <[email protected]>
2023-07-06 13:51 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Alena Rybakina <[email protected]>
2023-07-06 15:38 ` Re: Problems with estimating OR conditions, IS NULL on LEFT JOINs Tomas Vondra <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox