PostgreSQL源码解读+-+HASH表算法解析（杭州博学-吕海波）

———深度剖析PostgreSQL源码—深度剖析Oracle/MySQL/PostgreSQL源码数据库源码研究方法论学习致用的研究方法论：PG篇BufferAlloc函数解读（一）：1、数据结构分析：（1）、参数：SMgrRelationsmgr2、代码结构：（1）、初始化newTag（2）、根据newTag，计算HASH值（3）、根据HASH值，得到BufferParationLock（4）、加共享模式BufferParationLock（5）、调用BufTableLookup学习致用的研究方法论：PG篇BufTableLookup函数解读：全局变量：SharedBufHash结构，定义在src/backend/utils/hash/dynahash.c：208行208structHTAB209{210HASHHDR*hctl;/*=>sharedcontrolinformation*/在后面的研究中，逐渐填补这些域的意义211HASHSEGMENT*dir;/*directoryofsegmentstarts*/212HashValueFunchash;/*hashfunction*/213HashCompareFuncmatch;/*keycomparisonfunction*/214HashCopyFunckeycopy;/*keycopyingfunction*/215HashAllocFuncalloc;/*memoryallocator*/216MemoryContexthcxt;/*memorycontextifdefaultallocatorused*/217char*tabname;/*tablename(forerrormessages)*/218boolisshared;/*trueiftableisinsharedmemory*/219boolisfixed;/*iftrue,don'tenlarge*/220221/*freezingasharedtableisn'tallowed,sowecankeepstatehere*/222boolfrozen;/*true=nomoreinsertsallowed*/223224/*Wekeeplocalcopiesofthesefixedvaluestoreducecontention*/225Sizekeysize;/*hashkeylengthinbytes*/226longssize;/*segmentsize---mustbepowerof2*/227intsshift;/*segmentshift=log2(ssize)*/228};学习致用的研究方法论：PG篇BufTableLookup函数解读：参数：newTag：newHash还记得“逻辑读行为预期吗”（参见第7页）学习致用的研究方法论：PG篇BufTableLookup函数解读：全局变量：SharedBufHash结构，定义在src/backend/utils/hash/dynahash.c：208行208structHTAB209{210HASHHDR*hctl;/*=>sharedcontrolinformation*/在后面的研究中，逐渐填补这些域的意义211HASHSEGMENT*dir;/*directoryofsegmentstarts*/212HashValueFunchash;/*hashfunction*/213HashCompareFuncmatch;/*keycomparisonfunction*/214HashCopyFunckeycopy;/*keycopyingfunction*/215HashAllocFuncalloc;/*memoryallocator*/216MemoryContexthcxt;/*memorycontextifdefaultallocatorused*/217char*tabname;/*tablename(forerrormessages)*/218boolisshared;/*trueiftableisinsharedmemory*/219boolisfixed;/*iftrue,don'tenlarge*/220221/*freezingasharedtableisn'tallowed,sowecankeepstatehere*/222boolfrozen;/*true=nomoreinsertsallowed*/223224/*Wekeeplocalcopiesofthesefixedvaluestoreducecontention*/225Sizekeysize;/*hashkeylengthinbytes*/226longssize;/*segmentsize---mustbepowerof2*/227intsshift;/*segmentshift=log2(ssize)*/228};学习致用的研究方法论：PG篇hash_search_with_hash_value函数解读：1、FREELIST_IDX的猜测2、expand_table()3、calc_bucket()4、ELEMENTKEY的使用：230/*231*Key(alsoentry)partofaHASHELEMENT232*/233#defineELEMENTKEY(helem)(((char*)(helem))+MAXALIGN(sizeof(HASHELEMENT)))学习致用的研究方法论：PG篇hash_search_with_hash_value函数解读：学习致用的研究方法论：PG篇hash_search_with_hash_value函数解读：ELEMENTKEY的使用：#defineELEMENTKEY(helem)(((char*)(helem))+MAXALIGN(sizeof(HASHELEMENT)))意义为：helem+16currBucketlinkhashvaluetagPtrkeyrnodeforkNumblockNumid16字节20字节学习致用的研究方法论：PG篇SharedBuffer常用全局结构总结：学习致用的研究方法论：PG篇BufferAlloc函数解读（二）：1、数据结构分析：（1）、参数：SMgrRelationsmgr2、代码结构：（1）、初始化newTag（2）、根据newTag，计算HASH值（3）、根据HASH值，得到BufferParationLock（4）、加共享模式BufferParationLock（5）、调用BufTableLookup（6）、GetBufferDescriptor(buf_id)：全局数据结构BufferDescriptors，它是shared_buffer的描述符。（7）、PinBuffer:主要工作：LockFree方式将buf-state加1，步骤如下：

原子读buf->state到old_buf_state old_buf_state+=1

将old_buf_state原子写回到buf->statePinBuffer竞争测试：Pin成功后，不会影响同页的Select和Update

学习致用的研究方法论：PG篇BufferDesc中的状态：dIdLtOtO引用yIyC次数-----N---K|--|----------------------------100100111001010000000000000000002475950080100000110001010000000000000000001000001100010100000000000000000110000011000101000000000000000001学习致用的研究方法论：PG篇BufferAlloc函数解读（三）：3、竞争分析脚本：lock_time1.stp，观察持有bufferpartitionlock的时间。持有锁的时间学习致用的研究方法论：PG篇ReadBuffer_common的上层函数：1、ReadBufferExtended、ReadBuffer、ReleaseAndReadBuffer2、heapam_index_fetch_tuple：也有一个锁操作：阻塞分析，写一个脚本，分析一段时间内