資料庫資料搜尋方法，一直是電腦科學中相當熱門的研究方法之一，然而隨著資訊資料雲端化，資料庫中龐大的資料量，總是需耗費相當多的運算資源，因此如何加速處理大量資料的研究也日漸增多。

隨著一般通用型科學計算圖形處理器（General-purpose computing on graphics processing units, GPGPU, 簡稱GPU）的普及，藉由其平行化架構的高效能計算特性，將資料庫內巨量資料藉由GPU的高速運算架構，分配給不同處理單元中的執行緒，做平行運算及比對，再將結果統一輸出，逐一針對資料表內容做比較，再將結果輸出，能更有效地提高查詢效能。

最久未用演算法（Least Recently Used, LRU）為最常應用於資料快取的演算法，透過在目標資料庫前建立一個快取空間，並設定其優先順序的方式，快速將資料提供給使用者，達到提升資料查詢的目的。然而，LRU演算法中，需透過建立快取表格的方式，對資料進行優先權的比對及排列，相對地耗費系統資源。本論文提出一個藉由平行化技術，將原本需逐一使用排序比對的LRU演算法，透過GPU架構中的多核心高速平行計算特性，同時進行LRU演算法中的比對及排序，如此一來，更能有效取代逐一比對(大量)查詢的機制。

本研究以NVIDIA公司推出的平行運算技術（Compute Unified Device Architecture, CUDA），實現平行化具巨量資料的資料庫表格搜尋，並在進行查詢前，建立一個使用LRU演算法來加速查詢效能的表格，在不考慮時間存取優先情況下，透過圖形運算處理器，模擬實際大型資料庫查詢，及快取技術後，在存取效能所提升的效益。根據實驗結果，當資料量及快取大小逹一定程度，且使用該快取時，使用圖形運算處理器，和未使用圖形運算處理器相比的結果，在搜尋時間上有明顯的查詢加速效益。

The approach of database searching is one of the popular research methods in computer science. However, along with the clouding of information data, the huge data always spends lots of computing resources. Therefore, the research raises for how to accelerate dealing with big data.
According to the popular general-purpose computing on graphics processing units (GPGPU), the characterization of high calculation efficiency which dues to the parallel infrastructure, we arranged the big data in the database to different process units and then computed parallelly and compared using high speed computing structure of GPU. Thereafter, we output the results and raised the efficiency of searching efficiently.
Least Recently Used algorithm, LRU, is used widely in cache technology. It raises the data search efficiency by creating a cache space in target database and setting the priority to supply data to users immediately. However, it spends lots of system resource relatively. In this thesis, we proposed a parallel technology of multi-core fast and parallel computing characterization of GPU structure to replace the traditional individually comparison searching mechanism.
In this research, we realize the parallelized approach to search database with big data by using Compute Unified Device Architecture, CUDA, NVIDIA. It created an table at first to accelerate the search by using LRU algorithm. We simulate the real large database searching and cache technology using GPU without the consideration of the priority of access time. According to the experimental results, the searching time was promoted greatly compared to the non-GPU algorithm when the amount of data and the size of cache reaching some level

摘要 i
Abstract ii
誌謝 v
目錄 vi
圖目錄 viii
表目錄 ix
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 1
1.3 論文主要內容 2
第二章 相關背景探討 3
2.1 資料庫管理系統 3
2.2 資料表欄位索引與存取 4
2.3 SQLite資料庫 6
2.4 SQL語法解析及架構 8
2.5 快取演算法 12
2.6 LRU演算法 14
2.7 GPGPU 16
2.8 CUDA 17
第三章 研究方法 20
3.1 平行化資料表 20
3.2 GPU與LRU演算法 22
3.3 研究方法步驟 24
第四章 實驗結果 24
4.1 實驗環境 24
4.2 實驗結果 26
4.2.1 一般資料表查詢 26
4.2.2 平行化資料表查詢 26
4.2.3 使用LRU演算法 28
4.3 實驗結果總結 29
第五章結論與未來展望 30
參考文獻 32
附錄：Select語法虛擬操作指令碼 33
附錄二: SQLite虛擬機器引擎（SQLite Visual Database Engine,VBDE） 38
附錄三：資料庫資料結構 40

[1]https://developer.nvidia.com/category/zone/cuda-zone
(2013-4)
[2] NVIDIA CUDATM Programming Guide ersion3.0
（2010-2-20）
[3] Jason Sanders and Edward Kandrot：CUDA by Example - An Introduction to General-Purpose GPU Programming
[4]DavidB.KirkandWen-meiW.Hwu：Programming Massively Parallel Processors(2012-8)
[5] Sangjin Han, K. Jang, K.S Park Sue Moon：PacketShader: a GPU-Accelerated Software Router-ACM SIGCOMM , September 2010
[6] http://www.sqlite.org
[7]General SQL Parser User Guide Version 1.0 （2012-9）
[8] Morten ChristiansenandChristianEskeHansenGPGPUDBMS Programming （2009-2-2）。
[9]Jay A. Kreibicb：Using.SQLiteOreilly（2010-8）
[10] Grant Allen and Mike Owens :The.Definitive.Guide.to.SQLite（2010）
[11] Peter Bakkum and Kevin Skadron：Accelerating SQL Database Operations on a GPUwith CUDA Department of Computer ScienceUniversity of Virginia, Charlottesville（2010-8）
[12] JobnR.Levine and Tony Mason & Doug Brown ：Lex&YaccOrelly（1999-12）。
[13] Kevin Loney and Bob Bryla：Oracle database 10G DBA技術手冊，學貫（2005-7）.
[14]周韻寰：資料庫系統之理論與實務，儒林（1996-9）
[15]申建忠：Oracle管理藝術，清華大學（2012-5）
[16]蕭世文：演算法導論-Introduction of Algorithm，松崗（2004-8）