Line data    Source code

       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * hashsort.c
       4             :  *      Sort tuples for insertion into a new hash index.
       5             :  *
       6             :  * When building a very large hash index, we pre-sort the tuples by bucket
       7             :  * number to improve locality of access to the index, and thereby avoid
       8             :  * thrashing.  We use tuplesort.c to sort the given index tuples into order.
       9             :  *
      10             :  * Note: if the number of rows in the table has been underestimated,
      11             :  * bucket splits may occur during the index build.  In that case we'd
      12             :  * be inserting into two or more buckets for each possible masked-off
      13             :  * hash code value.  That's no big problem though, since we'll still have
      14             :  * plenty of locality of access.
      15             :  *
      16             :  *
      17             :  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
      18             :  * Portions Copyright (c) 1994, Regents of the University of California
      19             :  *
      20             :  * IDENTIFICATION
      21             :  *    src/backend/access/hash/hashsort.c
      22             :  *
      23             :  *-------------------------------------------------------------------------
      24             :  */
      25             : 
      26             : #include "postgres.h"
      27             : 
      28             : #include "access/hash.h"
      29             : #include "miscadmin.h"
      30             : #include "utils/tuplesort.h"
      31             : 
      32             : 
      33             : /*
      34             :  * Status record for spooling/sorting phase.
      35             :  */
      36             : struct HSpool
      37             : {
      38             :     Tuplesortstate *sortstate;  /* state data for tuplesort.c */
      39             :     Relation    index;
      40             : 
      41             :     /*
      42             :      * We sort the hash keys based on the buckets they belong to. Below masks
      43             :      * are used in _hash_hashkey2bucket to determine the bucket of given hash
      44             :      * key.
      45             :      */
      46             :     uint32      high_mask;
      47             :     uint32      low_mask;
      48             :     uint32      max_buckets;
      49             : };
      50             : 
      51             : 
      52             : /*
      53             :  * create and initialize a spool structure
      54             :  */
      55             : HSpool *
      56           1 : _h_spoolinit(Relation heap, Relation index, uint32 num_buckets)
      57             : {
      58           1 :     HSpool     *hspool = (HSpool *) palloc0(sizeof(HSpool));
      59             : 
      60           1 :     hspool->index = index;
      61             : 
      62             :     /*
      63             :      * Determine the bitmask for hash code values.  Since there are currently
      64             :      * num_buckets buckets in the index, the appropriate mask can be computed
      65             :      * as follows.
      66             :      *
      67             :      * NOTE : This hash mask calculation should be in sync with similar
      68             :      * calculation in _hash_init_metabuffer.
      69             :      */
      70           1 :     hspool->high_mask = (((uint32) 1) << _hash_log2(num_buckets + 1)) - 1;
      71           1 :     hspool->low_mask = (hspool->high_mask >> 1);
      72           1 :     hspool->max_buckets = num_buckets - 1;
      73             : 
      74             :     /*
      75             :      * We size the sort area as maintenance_work_mem rather than work_mem to
      76             :      * speed index creation.  This should be OK since a single backend can't
      77             :      * run multiple index creations in parallel.
      78             :      */
      79           1 :     hspool->sortstate = tuplesort_begin_index_hash(heap,
      80             :                                                    index,
      81             :                                                    hspool->high_mask,
      82             :                                                    hspool->low_mask,
      83             :                                                    hspool->max_buckets,
      84             :                                                    maintenance_work_mem,
      85             :                                                    false);
      86             : 
      87           1 :     return hspool;
      88             : }
      89             : 
      90             : /*
      91             :  * clean up a spool structure and its substructures.
      92             :  */
      93             : void
      94           1 : _h_spooldestroy(HSpool *hspool)
      95             : {
      96           1 :     tuplesort_end(hspool->sortstate);
      97           1 :     pfree(hspool);
      98           1 : }
      99             : 
     100             : /*
     101             :  * spool an index entry into the sort file.
     102             :  */
     103             : void
     104       10000 : _h_spool(HSpool *hspool, ItemPointer self, Datum *values, bool *isnull)
     105             : {
     106       10000 :     tuplesort_putindextuplevalues(hspool->sortstate, hspool->index,
     107             :                                   self, values, isnull);
     108       10000 : }
     109             : 
     110             : /*
     111             :  * given a spool loaded by successive calls to _h_spool,
     112             :  * create an entire index.
     113             :  */
     114             : void
     115           1 : _h_indexbuild(HSpool *hspool, Relation heapRel)
     116             : {
     117             :     IndexTuple  itup;
     118             : #ifdef USE_ASSERT_CHECKING
     119           1 :     uint32      hashkey = 0;
     120             : #endif
     121             : 
     122           1 :     tuplesort_performsort(hspool->sortstate);
     123             : 
     124       10002 :     while ((itup = tuplesort_getindextuple(hspool->sortstate, true)) != NULL)
     125             :     {
     126             :         /*
     127             :          * Technically, it isn't critical that hash keys be found in sorted
     128             :          * order, since this sorting is only used to increase locality of
     129             :          * access as a performance optimization.  It still seems like a good
     130             :          * idea to test tuplesort.c's handling of hash index tuple sorts
     131             :          * through an assertion, though.
     132             :          */
     133             : #ifdef USE_ASSERT_CHECKING
     134       10000 :         uint32      lasthashkey = hashkey;
     135             : 
     136       10000 :         hashkey = _hash_hashkey2bucket(_hash_get_indextuple_hashkey(itup),
     137             :                                        hspool->max_buckets, hspool->high_mask,
     138             :                                        hspool->low_mask);
     139       10000 :         Assert(hashkey >= lasthashkey);
     140             : #endif
     141             : 
     142       10000 :         _hash_doinsert(hspool->index, itup, heapRel);
     143             :     }
     144           1 : }