ex1/main_4.tex

   1 %ex1.4
   2
   3 \begin{enumerate}[label=(\alph*)]
   4 \item Hash Join in Merge Join.
   5 \begin{verbatim}
   6 EXPLAIN (ANALYZE, COSTS, VERBOSE, BUFFERS)
   7 SELECT a,b,c FROM r NATURAL JOIN s NATURAL JOIN t;
   8 \end{verbatim}
   9
  10 Query plan
  11 \begin{verbatim}
  12 Merge Join (cost=126688.84..189746.85 rows=4812309 width=12)
  13       (actual time=1223.252..3564.720 rows=4790517 loops=1)
  14   Output: r.a, r.b, s.c
  15   Merge Cond: ((t.a = r.a) AND (t.c = s.c))
  16   Buffers: shared hit=138, temp read=1320 written=3593
  17   -> Sort (cost=809.39..834.39 rows=10000 width=8)
  18      (actual time=6.542..9.442 rows=10000 loops=1)
  19     Output: t.a, t.c
  20     Sort Key: t.a, t.c
  21     Sort Method: quicksort Memory: 853kB
  22     Buffers: shared hit=45
  23     -> Seq Scan on public.t (cost=0.00..145.00 rows=10000 width=8)
  24                      (actual time=0.013..1.698 rows=10000 loops=1)
  25         Output: t.a, t.c
  26         Buffers: shared hit=45
  27   -> Materialize (cost=125878.37..130770.59 rows=978445 width=12)
  28             (actual time=1216.698..1848.300 rows=4790518 loops=1)
  29     Output: r.a, r.b, s.c
  30     Buffers: shared hit=93, temp read=1320 written=3593
  31     -> Sort (cost=125878.37..128324.48 rows=978445 width=12)
  32        (actual time=1216.694..1265.485 rows=105629 loops=1)
  33         Output: r.a, r.b, s.c
  34         Sort Key: r.a, s.c
  35         Sort Method: external merge Disk: 21312kB
  36         Buffers: shared hit=93, temp read=1320 written=3593
  37         -> Hash Join (cost=270.00..11799.45 rows=978445 width=12)
  38                 (actual time=5.707..326.759 rows=993774 loops=1)
  39           Output: r.a, r.b, s.c
  40           Hash Cond: (r.b = s.b)
  41           Buffers: shared hit=93
  42           -> Seq Scan on public.r (cost=0.00..145.00 rows=10000 width=8)
  43                            (actual time=0.013..2.200 rows=10000 loops=1)
  44               Output: r.a, r.b
  45               Buffers: shared hit=45
  46           -> Hash  (cost=145.00..145.00 rows=10000 width=8)
  47               (actual time=5.636..5.636 rows=10000 loops=1)
  48               Output: s.c, s.b
  49               Buckets: 16384  Batches: 1 Memory Usage: 519kB
  50               Buffers: shared hit=45
  51               -> Seq Scan on public.s (cost=0.00..145.00 rows=10000 width=8)
  52                                (actual time=0.012..2.656 rows=10000 loops=1)
  53                 Output: s.c, s.b
  54                 Buffers: shared hit=45
  55 Planning time: 0.448 ms
  56 Execution time: 4093.957 ms
  57 \end{verbatim}
  58
  59
  60
  61 \item
  62 \begin{verbatim}
  63 set enable\_hashjoin=1; set enable\_mergejoin=0; set enable\_nestloop=0;
  64 EXPLAIN (ANALYZE, COSTS, VERBOSE, BUFFERS)
  65 SELECT a,b,c FROM r NATURAL JOIN s NATURAL JOIN t;
  66 \end{verbatim}
  67
  68 Results
  69 \begin{verbatim}
  70 Hash Join (cost=565.00..382720.42 rows=4812309 width=12)
  71     (actual time=10.065..2336.284 rows=4790517 loops=1)
  72 Execution time: 2839.835 ms
  73 \end{verbatim}
  74
  75
  76 \begin{verbatim}
  77 set enable\_hashjoin=0; set enable\_mergejoin=1; set enable\_nestloop=0;
  78 EXPLAIN (ANALYZE, COSTS, VERBOSE, BUFFERS)
  79 SELECT a,b,c FROM r NATURAL JOIN s NATURAL JOIN t;
  80 \end{verbatim}
  81
  82 Results
  83 \begin{verbatim}
  84 Merge Join (cost=127309.80..190367.82 rows=4812309 width=12)
  85       (actual time=1400.115..3961.542 rows=4790517 loops=1)
  86 Planning time: 0.374 ms
  87 Execution time: 4215.626 ms
  88 \end{verbatim}
  89
  90
  91 \begin{verbatim}
  92 set enable\_hashjoin=0; set enable\_mergejoin=0; set enable\_nestloop=1;
  93 EXPLAIN (ANALYZE, COSTS, VERBOSE, BUFFERS)
  94 SELECT a,b,c FROM r NATURAL JOIN s NATURAL JOIN t;
  95 \end{verbatim}
  96
  97 Results
  98 \begin{verbatim}
  99 Nested Loop (cost=0.00..172728360.00 rows=4812309 width=12)
 100 Execution time: query-timeout
 101 \end{verbatim}
 102
 103
 104
 105 \item create indices.
 106 \begin{verbatim}
 107 create index i1 on r(a);
 108 create index i2 on r(b);
 109 create index i3 on s(b);
 110 create index i4 on s(c);
 111 create index i5 on t(a);
 112 create index i6 on t(c);
 113 create index ii1 on r(a,b);
 114 create index ii2 on s(b,c);
 115 create index ii3 on t(a,c);
 116 REINDEX DATABASE u00726236; VACUUM ANALYZE;
 117
 118 RESET ALL;
 119 EXPLAIN (ANALYZE, COSTS, VERBOSE, BUFFERS)
 120 SELECT a,b,c FROM r NATURAL JOIN s NATURAL JOIN t;
 121 \end{verbatim}
 122
 123 New query plan for merge join.
 124 \begin{verbatim}
 125 Merge Join (cost=126115.03..189598.35 rows=4812309 width=12)
 126       (actual time=1471.775..3798.577 rows=4790517 loops=1)
 127   Output: r.a, r.b, s.c
 128   Merge Cond: ((t.a = r.a) AND (t.c = s.c))
 129   Buffers: shared hit=7289 read=58, temp read=1325 written=3598
 130   ->  Index Only Scan using ii3 on public.t (cost=0.29..449.50 rows=10000 width=8)
 131                                      (actual time=0.034..8.250 rows=10000 loops=1)
 132     Output: t.a, t.c
 133     Heap Fetches: 10000
 134     Buffers: shared hit=6299 read=29
 135   ->  Materialize (cost=126114.75..131006.97 rows=978445 width=12)
 136              (actual time=1471.732..2093.037 rows=4790518 loops=1)
 137     Output: r.a, r.b, s.c
 138     Buffers: shared hit=990 read=29, temp read=1325 written=3598
 139     ->  Sort (cost=126114.75..128560.86 rows=978445 width=12)
 140         (actual time=1471.727..1519.766 rows=105629 loops=1)
 141         Output: r.a, r.b, s.c
 142         Sort Key: r.a, s.c
 143         Sort Method: external merge  Disk: 21312kB
 144         Buffers: shared hit=990 read=29, temp read=1325 written=3598
 145         ->  Merge Join (cost=809.67..12035.83 rows=978445 width=12)
 146                   (actual time=5.865..568.309 rows=993774 loops=1)
 147           Output: r.a, r.b, s.c
 148           Merge Cond: (r.b = s.b)
 149           Buffers: shared hit=990 read=29
 150           ->  Index Scan using i2 on public.r (cost=0.29..449.80 rows=10000 width=8)
 151                                        (actual time=0.026..7.013 rows=10000 loops=1)
 152               Output: r.a, r.b
 153               Buffers: shared hit=945 read=29
 154           ->  Sort (cost=809.39..834.39 rows=10000 width=8)
 155             (actual time=5.836..189.024 rows=993775 loops=1)
 156               Output: s.c, s.b
 157               Sort Key: s.b
 158               Sort Method: quicksort Memory: 853kB
 159               Buffers: shared hit=45
 160               ->  Seq Scan on public.s (cost=0.00..145.00 rows=10000 width=8)
 161                                 (actual time=0.013..2.654 rows=10000 loops=1)
 162                 Output: s.c, s.b
 163                 Buffers: shared hit=45
 164 Planning time: 1.060 ms
 165 Execution time: 4323.022 ms
 166 \end{verbatim}
 167
 168 It seems like no performance improvement is made: Query planning and execution time is bigger with indices.
 169
 170
 171 Suddenly nested loop joins become feasible.
 172 \begin{verbatim}
 173 Nested Loop (cost=0.57..498778.26 rows=4812309 width=12)
 174      (actual time=0.096..8351.002 rows=4790517 loops=1)
 175   Output: r.a, r.b, s.c
 176   Buffers: shared hit=7476815 read=11
 177   ->  Nested Loop (cost=0.29..30520.00 rows=1007007 width=12)
 178           (actual time=0.076..1017.339 rows=987869 loops=1)
 179         Output: r.a, r.b, t.c
 180         Buffers: shared hit=950972 read=4
 181         ->  Seq Scan on public.t (cost=0.00..145.00 rows=10000 width=8)
 182                           (actual time=0.015..2.720 rows=10000 loops=1)
 183               Output: t.a, t.c
 184               Buffers: shared hit=45
 185         ->  Index Only Scan using ii1 on public.r (cost=0.29..2.05 rows=99 width=8)
 186                                          (actual time=0.007..0.076 rows=99 loops=10000)
 187               Output: r.a, r.b
 188               Index Cond: (r.a = t.a)
 189               Heap Fetches: 987869
 190               Buffers: shared hit=950927 read=4
 191   ->  Index Only Scan using ii2 on public.s (cost=0.29..0.41 rows=5 width=8)
 192                                    (actual time=0.003..0.006 rows=5 loops=987869)
 193         Output: s.b, s.c
 194         Index Cond: ((s.b = r.b) AND (s.c = t.c))
 195         Heap Fetches: 4790517
 196         Buffers: shared hit=6525843 read=7
 197 Planning time: 0.604 ms
 198 Execution time: 8884.429 ms
 199 \end{verbatim}
 200
 201
 202
 203
 204 \newpage
 205 \begin{verbatim}
 206 RESET ALL; EXPLAIN (ANALYZE, COSTS, VERBOSE, BUFFERS)
 207 SELECT a,b,c FROM r NATURAL JOIN t WHERE b IN (SELECT s.b FROM s);
 208 \end{verbatim}
 209
 210 Query plan
 211 \begin{verbatim}
 212 Hash Join (cost=578.59..12368.66 rows=1007007 width=12)
 213     (actual time=25.336..340.303 rows=987869 loops=1)
 214   Output: r.a, r.b, t.c
 215   Hash Cond: (t.a = r.a)
 216   Buffers: shared hit=135
 217   ->  Seq Scan on public.t (cost=0.00..145.00 rows=10000 width=8)
 218                     (actual time=0.035..1.820 rows=10000 loops=1)
 219     Output: t.a, t.c
 220     Buffers: shared hit=45
 221   ->  Hash (cost=453.59..453.59 rows=10000 width=8)
 222     (actual time=25.235..25.235 rows=10000 loops=1)
 223     Output: r.a, r.b
 224     Buckets: 16384 Batches: 1 Memory Usage: 519kB
 225     Buffers: shared hit=90
 226     ->  Hash Join (cost=172.27..453.59 rows=10000 width=8)
 227            (actual time=14.607..22.222 rows=10000 loops=1)
 228         Output: r.a, r.b
 229         Hash Cond: (r.b = s.b)
 230         Buffers: shared hit=90
 231         ->  Seq Scan on public.r (cost=0.00..145.00 rows=10000 width=8)
 232                           (actual time=0.026..1.943 rows=10000 loops=1)
 233           Output: r.a, r.b
 234           Buffers: shared hit=45
 235         ->  Hash (cost=171.01..171.01 rows=101 width=4)
 236           (actual time=14.558..14.559 rows=101 loops=1)
 237           Output: s.b
 238           Buckets: 1024 Batches: 1 Memory Usage: 12kB
 239           Buffers: shared hit=45
 240           ->  HashAggregate (cost=170.00..171.01 rows=101 width=4)
 241                      (actual time=14.423..14.486 rows=101 loops=1)
 242               Output: s.b
 243               Group Key: s.b
 244               Buffers: shared hit=45
 245               ->  Seq Scan on public.s (cost=0.00..145.00 rows=10000 width=4)
 246                                 (actual time=0.028..6.220 rows=10000 loops=1)
 247                 Output: s.b
 248                 Buffers: shared hit=45
 249 Planning time: 0.626 ms
 250 Execution time: 439.179 ms
 251 \end{verbatim}
 252
 253 It now takes only 439.7 ms to execute the query, instead of the previous 4323 ms.
 254
 255
 256 \item This was the case with (d) already.\\
 257 But if we create indexes we get a merge join + hash semi join combination, which is a little bit slower.
 258 \begin{verbatim}
 259 Merge Join (cost=1118.26..12199.68 rows=1007007 width=12)
 260       (actual time=23.151..517.241 rows=987869 loops=1)
 261   Output: r.a, r.b, t.c
 262   Merge Cond: (t.a = r.a)
 263   Buffers: shared hit=585 read=29
 264   ->  Index Scan using i5 on public.t (cost=0.29..448.89 rows=10000 width=8)
 265                                (actual time=0.038..4.266 rows=10000 loops=1)
 266     Output: t.a, t.c
 267     Buffers: shared hit=495 read=29
 268   ->  Sort (cost=1117.98..1142.98 rows=10000 width=8)
 269      (actual time=23.107..186.813 rows=987870 loops=1)
 270     Output: r.a, r.b
 271     Sort Key: r.a
 272     Sort Method: quicksort Memory: 853kB
 273     Buffers: shared hit=90
 274     ->  Hash Join (cost=172.27..453.59 rows=10000 width=8)
 275            (actual time=11.223..19.180 rows=10000 loops=1)
 276         Output: r.a, r.b
 277         Hash Cond: (r.b = s.b)
 278         Buffers: shared hit=90
 279         ->  Seq Scan on public.r (cost=0.00..145.00 rows=10000 width=8)
 280                           (actual time=0.019..2.069 rows=10000 loops=1)
 281           Output: r.a, r.b
 282           Buffers: shared hit=45
 283         ->  Hash (cost=171.01..171.01 rows=101 width=4)
 284           (actual time=11.183..11.183 rows=101 loops=1)
 285           Output: s.b
 286           Buckets: 1024 Batches: 1 Memory Usage: 12kB
 287           Buffers: shared hit=45
 288           ->  HashAggregate (cost=170.00..171.01 rows=101 width=4)
 289                      (actual time=11.079..11.126 rows=101 loops=1)
 290               Output: s.b
 291               Group Key: s.b
 292               Buffers: shared hit=45
 293               ->  Seq Scan on public.s (cost=0.00..145.00 rows=10000 width=4)
 294                                 (actual time=0.019..4.724 rows=10000 loops=1)
 295                 Output: s.b
 296                 Buffers: shared hit=45
 297 Planning time: 1.320 ms
 298 Execution time: 624.356 ms
 299 \end{verbatim}
 300
 301
 302
 303 \item
 304 \begin{verbatim}
 305 RESET ALL; EXPLAIN (ANALYZE, COSTS, VERBOSE, BUFFERS)
 306 SELECT a,b,c FROM r NATURAL JOIN s WHERE a IN (SELECT t.a FROM t);
 307 \end{verbatim}
 308
 309 Without index: hash join + hash semi join
 310 \begin{verbatim}
 311 Hash Join (cost=440.25..1943.04 rows=112490 width=12)
 312     (actual time=20.751..57.164 rows=105628 loops=1)
 313 Planning time: 0.836 ms
 314 Execution time: 67.660 ms
 315 \end{verbatim}
 316
 317 With index: hash join + merge join.
 318 \begin{verbatim}
 319 Hash Join  (cost=440.59..1817.14 rows=112490 width=12)
 320      (actual time=19.917..53.721 rows=105628 loops=1)
 321 Planning time: 1.938 ms
 322 Execution time: 65.131 ms
 323 \end{verbatim}
 324
 325
 326
 327 \begin{verbatim}
 328 RESET ALL; EXPLAIN (ANALYZE, COSTS, VERBOSE, BUFFERS)
 329 SELECT a,b,c FROM s NATURAL JOIN t WHERE a IN (SELECT r.a FROM r);
 330 \end{verbatim}
 331
 332 Without index: hash join + hash semi join
 333 \begin{verbatim}
 334 Hash Join  (cost=442.27..56192.50 rows=4884102 width=12)
 335     (actual time=17.134..1482.398 rows=4884102 loops=1)
 336 Planning time: 0.547 ms
 337 Execution time: 1980.768 ms
 338 \end{verbatim}
 339
 340 With index: hash join + hash join.
 341 \begin{verbatim}
 342 Hash Join (cost=442.27..56192.50 rows=4884102 width=12)
 343    (actual time=17.631..1541.867 rows=4884102 loops=1)
 344 Planning time: 0.978 ms
 345 Execution time: 2040.407 ms
 346 \end{verbatim}
 347
 348 \end{enumerate}