On Sun, Jul 4, 2021 at 12:27 AM Thomas Munro <thomas.mu...@gmail.com> wrote: > > Since you are experimenting with tuplesort and likely thinking similar > thoughts, here's a patch I've been using to explore that area. I've > seen it get, for example, ~1.18x speedup for simple index builds in > favourable winds (YMMV, early hacking results only). Currently, it > kicks in when the leading column is of type int4, int8, timestamp, > timestamptz, date or text + friends (when abbreviatable, currently > that means "C" and ICU collations only), while increasing the > executable by only 8.5kB (Clang, amd64, -O2, no debug). > > These types are handled with just three specialisations. Their custom > "fast" comparators all boiled down to comparisons of datum bits, > varying only in signedness and width, so I tried throwing them away > and using 3 new common routines. Then I extended > tuplesort_sort_memtuples()'s pre-existing specialisation dispatch to > recognise qualifying users of those and select 3 corresponding sort > specialisations.
I got around to getting a benchmark together to serve as a starting point. I based it off something I got from the archives, but don't remember where (I seem to remember Tomas Vondra wrote the original, but not sure). To start I just used types that were there already -- int, text, numeric. The latter two won't be helped by this patch, but I wanted to keep something like that so we can see what kind of noise variation there is. I'll probably cut text out in the future and just keep numeric for that purpose. I've attached both the script and a crude spreadsheet. I'll try to figure out something nicer for future tests, and maybe some graphs. The "comparison" sheet has the results side by side (min of five). There are 6 distributions of values: - random - sorted - "almost sorted" - reversed - organ pipe (first half ascending, second half descending) - rotated (sorted but then put the smallest at the end) - random 0s/1s I included both "select a" and "select *" to make sure we have the recent datum sort optimization represented. The results look pretty good for ints -- about the same speed up master gets going from tuple sorts to datum sorts, and those got faster in turn also. Next I think I'll run microbenchmarks on int64s with the test harness you attached earlier, and experiment with the qsort parameters a bit. I'm also attaching your tuplesort patch so others can see what exactly I'm comparing. -- John Naylor EDB: http://www.enterprisedb.com
set -e
ROWS=$1
WORK_MEM=$2
function log {
echo `date +%s` [`date +'%Y-%m-%d %H:%M:%S'`] $1
}
function create_tables {
./inst/bin/psql > /dev/null <<EOF
-- tables for source data
DROP TABLE IF EXISTS data_int;
CREATE TABLE data_int (a INT);
INSERT INTO data_int SELECT i FROM generate_series(1, $ROWS) s(i);
DROP TABLE IF EXISTS data_flt;
CREATE TABLE data_flt (a FLOAT);
INSERT INTO data_flt SELECT 100000 * random() FROM generate_series(1, $ROWS) s(i);
-- tables used for the actual testing
CREATE TABLE IF NOT EXISTS int_test (a INT, b TEXT);
CREATE TABLE IF NOT EXISTS txt_test (a TEXT, b TEXT);
CREATE TABLE IF NOT EXISTS num_test (a NUMERIC, b TEXT);
EOF
}
function truncate_tables {
log "truncating tables"
./inst/bin/psql > /dev/null <<EOF
TRUNCATE TABLE int_test;
TRUNCATE TABLE txt_test;
TRUNCATE TABLE num_test;
EOF
}
function vacuum_analyze {
log "analyzing"
./inst/bin/psql > /dev/null <<EOF
VACUUM ANALYZE;
CHECKPOINT;
EOF
}
function prewarm {
log "prewarming buffers"
./inst/bin/psql > /dev/null <<EOF
SELECT pg_prewarm(oid) FROM pg_class WHERE oid > 16384 AND relkind = 'r';
EOF
}
################# load test tables
function load_random {
truncate_tables
log "loading random"
./inst/bin/psql > /dev/null <<EOF
SET work_mem = '$WORK_MEM';
-- this needs randomization
INSERT INTO int_test SELECT a, md5(a::text) FROM data_int ORDER BY random();
-- these already are random
INSERT INTO txt_test SELECT md5(a::text), md5((a+1)::text) FROM data_int;
INSERT INTO num_test SELECT a, md5(a::text) FROM data_flt;
EOF
prewarm
vacuum_analyze
}
function load_sorted {
truncate_tables
log "loading sorted"
./inst/bin/psql > /dev/null <<EOF
SET work_mem = '$WORK_MEM';
INSERT INTO int_test SELECT a, md5(a::text) FROM data_int ORDER BY 1;
INSERT INTO txt_test SELECT md5(a::text), md5((a+1)::text) FROM data_int ORDER BY 1;
INSERT INTO num_test SELECT a, md5(a::text) FROM data_flt ORDER BY 1;
EOF
prewarm
vacuum_analyze
}
function load_almost_sorted {
truncate_tables
log "loading almost sorted"
./inst/bin/psql > /dev/null <<EOF
SET work_mem = '$WORK_MEM';
INSERT INTO int_test SELECT a, b FROM (
SELECT a, md5(a::text) AS b, rank() OVER (ORDER BY a) AS r FROM data_int
) foo ORDER BY r + (100 * random());
INSERT INTO txt_test SELECT a, b FROM (
SELECT md5(a::text) AS a, md5(((a+1))::text) AS b, rank() OVER (ORDER BY md5(a::text)) AS r FROM data_int
) foo ORDER BY r + (100 * random());
INSERT INTO num_test SELECT a, b FROM (
SELECT a, md5(a::text) AS b, rank() OVER (ORDER BY a) AS r FROM data_flt
) foo ORDER BY r + (100 * random());
EOF
prewarm
vacuum_analyze
}
function load_reversed {
truncate_tables
log "loading reversed"
./inst/bin/psql > /dev/null <<EOF
SET work_mem = '$WORK_MEM';
INSERT INTO int_test SELECT a, md5(a::text) FROM data_int ORDER BY 1 DESC;
INSERT INTO txt_test SELECT md5(a::text), md5((a+1)::text) FROM data_int ORDER BY 1 DESC;
INSERT INTO num_test SELECT a, md5(a::text) FROM data_flt ORDER BY 1 DESC;
EOF
prewarm
vacuum_analyze
}
function load_organ_pipe {
truncate_tables
log "loading organ pipe"
./inst/bin/psql > /dev/null <<EOF
SET work_mem = '$WORK_MEM';
WITH c AS (SELECT count(*)/2 AS half from data_int)
INSERT INTO int_test
(SELECT a, md5(a::text) FROM data_int ORDER BY 1 ASC LIMIT (SELECT half from c))
UNION ALL
(SELECT a, md5(a::text) FROM data_int ORDER BY 1 DESC LIMIT (SELECT half from c));
WITH c AS (SELECT count(*)/2 AS half from data_int)
INSERT INTO txt_test
(SELECT md5(a::text), md5((a+1)::text) FROM data_int ORDER BY 1 ASC LIMIT (SELECT half from c))
UNION ALL
(SELECT md5(a::text), md5((a+1)::text) FROM data_int ORDER BY 1 DESC LIMIT (SELECT half from c));
WITH c AS (SELECT count(*)/2 AS half from num_test)
INSERT INTO num_test
(SELECT a, md5(a::text) FROM data_int ORDER BY 1 ASC LIMIT (SELECT half from c))
UNION ALL
(SELECT a, md5(a::text) FROM data_int ORDER BY 1 DESC LIMIT (SELECT half from c));
EOF
prewarm
vacuum_analyze
}
function load_rotated {
truncate_tables
log "loading rotated"
./inst/bin/psql > /dev/null <<EOF
SET work_mem = '$WORK_MEM';
INSERT INTO int_test SELECT a, md5(a::text) FROM data_int;
INSERT INTO int_test VALUES (0, 'b');
INSERT INTO txt_test SELECT md5(a::text), md5((a+1)::text) FROM data_int ORDER BY 1;
INSERT INTO txt_test VALUES ('a', 'b');
INSERT INTO num_test SELECT a + 1.0 FROM data_flt ORDER BY 1;
INSERT INTO num_test VALUES (0.0, 'b');
EOF
prewarm
vacuum_analyze
}
function load_0_1 {
truncate_tables
log "loading 0 1"
./inst/bin/psql > /dev/null <<EOF
SET work_mem = '$WORK_MEM';
INSERT INTO int_test SELECT round(a), md5(a::text) FROM data_int;
INSERT INTO txt_test SELECT
case when a > 0.5
then 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'
else 'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb'
end
FROM data_int;
INSERT INTO num_test SELECT round(a), md5(a::text) FROM data_int;
EOF
prewarm
vacuum_analyze
}
################# run
function run_query {
times=""
group=$1
wmem=$2
workers=$3
query=$4
echo "--" `date` [`date +%s`] >> explains.log
echo "-- $group rows=$ROWS work_mem=$wmem workers=$workers" >> explains.log
./inst/bin/psql >> explains.log 2>&1 <<EOF
SET trace_sort=on;
SET work_mem='$wmem';
SET max_parallel_workers_per_gather=$workers;
explain $query
EOF
s=`date +%s`
for i in `seq 1 5`; do
/usr/bin/time -f '%e' -o 'query.time' ./inst/bin/psql > /dev/null <<EOF
\pset pager off
\o /dev/null
SET trace_sort=on;
SET work_mem='$wmem';
SET max_parallel_workers_per_gather=$workers;
COPY ($query) TO '/dev/null'
EOF
x=`cat query.time`
times="$times\t$x"
done
e=`date +%s`
echo -e "$group\t$ROWS\t$wmem\t$workers\t$s\t$e\t$query\t$times" >> results.csv
}
function run_index {
times=""
group=$1
wmem=$2
workers=$3
query=$4
times=""
s=`date +%s`
for i in `seq 1 5`; do
/usr/bin/time -f '%e' -o 'query.time' ./inst/bin/psql > /dev/null <<EOF
\pset pager off
\o /dev/null
SET maintenance_work_mem='$wmem';
$query
EOF
x=`cat query.time`
times="$times\t$x"
done
e=`date +%s`
echo -e "$group\t$ROWS\t$wmem\t$workers\t$s\t$e\t$query\t$times" >> results.csv
}
function run_queries {
# for wm in '1MB' '8MB' '32MB' '128MB' '512MB' '1GB'; do
for wm in $WORK_MEM; do
log "running queries work_mem=$wm noparallel"
run_query $1 $wm 0 'SELECT a FROM int_test ORDER BY 1 OFFSET '$ROWS''
run_query $1 $wm 0 'SELECT * FROM int_test ORDER BY 1 OFFSET '$ROWS''
# run_query $1 $wm 0 'SELECT a FROM int_test ORDER BY 1 DESC OFFSET '$ROWS''
# run_query $1 $wm 0 'SELECT * FROM int_test ORDER BY 1 DESC OFFSET '$ROWS''
run_index $1 $wm 0 'CREATE INDEX x ON int_test (a); DROP INDEX x'
run_query $1 $wm 0 'SELECT a FROM txt_test ORDER BY 1 OFFSET '$ROWS''
run_query $1 $wm 0 'SELECT * FROM txt_test ORDER BY 1 OFFSET '$ROWS''
# run_query $1 $wm 0 'SELECT a FROM txt_test ORDER BY 1 DESC OFFSET '$ROWS''
# run_query $1 $wm 0 'SELECT * FROM txt_test ORDER BY 1 DESC OFFSET '$ROWS''
run_index $1 $wm 0 'CREATE INDEX x ON txt_test (a); DROP INDEX x'
run_query $1 $wm 0 'SELECT * FROM num_test ORDER BY 1 OFFSET '$ROWS''
# run_query $1 $wm 0 'SELECT * FROM num_test ORDER BY 1 DESC OFFSET '$ROWS''
run_index $1 $wm 0 'CREATE INDEX x ON num_test (a); DROP INDEX x'
done
}
create_tables
log "sort benchmark $ROWS"
load_random
run_queries "random"
load_sorted
run_queries "sorted"
load_almost_sorted
run_queries "almost_sorted"
load_reversed
run_queries "reversed"
load_organ_pipe
run_queries "organ_pipe"
load_rotated
run_queries "rotated"
load_0_1
run_queries "0_1"
test-acc-tuplesort-20210729.ods
Description: application/vnd.oasis.opendocument.spreadsheet
0001-WIP-Accelerate-tuple-sorting-for-common-types.patch
Description: Binary data
