흑백과 디지털

 sqlite3 에서 소스를 수정하지 않고 sqlite3 동작을 수정할 수 있는 방법이 여러가지 있다. 

sqlite3 에 함수를 추가하는 방법(https://www.sqlite.org/c3ref/create_function.html ) , Virtual Table 을 구현하는 방법(https://www.sqlite.org/vtab.html), Virtual FileSystem을 구현하는 방법(https://www.sqlite.org/vfs.html)이있다.(더있는지는 모르겠다.)

어째든 이 방법 중 virtual table 을 구현하는 방법에 대해 공부 중이다. 내 목표는 rust 를 이용해서 vtab을 이용해서 apache arrow parquet 와 연동하고 싶다. (이미 C로 된 것은 https://github.com/cldellow/sqlite-parquet-vtable 이 있다. ). 그래서 vtab 연동하는 인터페이스에 대해 정리해 봤다. ( https://www.sqlite.org/vtab.html )

우선 vtab 을 사용하는 대표적인 경우가 csv 파일을 읽는 csv virtual table(https://www.sqlite.org/csv.html) 이다. 이것을 이용해서 csv 파일을 읽어서 table 처럼 query 를 보낼 수 있다. 

vtab 을 연동하기 위해서는 sqlite3_module  의 struct 를 모듈 생성 함수에 넘겨야 한다. sqlite3_module  구조체가 여러 함수들의 callback 함수로 구성되어 있기 때문에 이 callback 함수를 구현해야 한다. 필수 구현함수가 아닌 경우 null 을 넣는 경우수도 있다. 
함수 원형은 아래와 같이 생겼다. 

struct sqlite3_module {
  int iVersion;
  int (*xCreate)(sqlite3*, void *pAux,
               int argc, char *const*argv,
               sqlite3_vtab **ppVTab,
               char **pzErr);
  int (*xConnect)(sqlite3*, void *pAux,
               int argc, char *const*argv,
               sqlite3_vtab **ppVTab,
               char **pzErr);
  int (*xBestIndex)(sqlite3_vtab *pVTab, sqlite3_index_info*);
  int (*xDisconnect)(sqlite3_vtab *pVTab);
  int (*xDestroy)(sqlite3_vtab *pVTab);
  int (*xOpen)(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor);
  int (*xClose)(sqlite3_vtab_cursor*);
  int (*xFilter)(sqlite3_vtab_cursor*, int idxNum, const char *idxStr,
                int argc, sqlite3_value **argv);
  int (*xNext)(sqlite3_vtab_cursor*);
  int (*xEof)(sqlite3_vtab_cursor*);
  int (*xColumn)(sqlite3_vtab_cursor*, sqlite3_context*, int);
  int (*xRowid)(sqlite3_vtab_cursor*, sqlite_int64 *pRowid);
  int (*xUpdate)(sqlite3_vtab *, int, sqlite3_value **, sqlite_int64 *);
  int (*xBegin)(sqlite3_vtab *pVTab);
  int (*xSync)(sqlite3_vtab *pVTab);
  int (*xCommit)(sqlite3_vtab *pVTab);
  int (*xRollback)(sqlite3_vtab *pVTab);
  int (*xFindFunction)(sqlite3_vtab *pVtab, int nArg, const char *zName,
                     void (**pxFunc)(sqlite3_context*,int,sqlite3_value**),
                     void **ppArg);
  int (*Rename)(sqlite3_vtab *pVtab, const char *zNew);
  /* The methods above are in version 1 of the sqlite_module object. Those 
  ** below are for version 2 and greater. */
  int (*xSavepoint)(sqlite3_vtab *pVTab, int);
  int (*xRelease)(sqlite3_vtab *pVTab, int);
  int (*xRollbackTo)(sqlite3_vtab *pVTab, int);
  /* The methods above are in versions 1 and 2 of the sqlite_module object.
  ** Those below are for version 3 and greater. */
  int (*xShadowName)(const char*);
};

xCreate : int (*xCreate)(sqlite3 *db, void *pAux, int argc, char *const*argv, sqlite3_vtab **ppVTab, char **pzErr);
xConnect : int (*xConnect)(sqlite3*, void *pAux, int argc, char *const*argv, sqlite3_vtab **ppVTab, char **pzErr);
* xCreate  는 생성함수로 vtab 이 생성될 때 호출된다. SQL 구문  CREATE VIRTUAL TABLE 테이블명 ....     형식이다. 
xCreate와 xConnect 는 유사하다. xCrete 는 생성될 때 이용되고, xConnect 는 생성된 가상테이블에 대해 불러올 때 사용된다. xCrete 와 xConnect 를 동일한 callback 함수(동일한 함수포인터)를 넣을 수도 있는데, 이렇게 하면 Eponymous virtual tables(CREATE VIRTUAL TABLE 문 없이 미리 로딩된 경우) 이 된다. xCreate 가 null pointer 이면 eponymous-only virtual table(CREATE VIRTUAL TABLE 문을 사용할 수 없고, table-valued functions 전용, table-valued functions 은 table 을 return 하는 sql 함수로 generate_series 함수 같이 일반 함수인데, table row 를 리턴해서 테이블 처럼 SELECT value FROM generate_series(5,50); 으로 사용 가능 )
csv virtual table 경우 xCrete 내부적으로 xConnect 를 호출하고 있다. 
* 꼭 이들 함수 안에서 sqlite3_declare_vtab 를 호출해서 가상테이블의 column 과 datatype 을 알려야 한다. 일반 database 의 table 을 create 하듯이 sql 쿼리를 전달해야한다. 필수 구현 사항이다.
* 또 sqlite3_vtab_config 를 호출해서 SQLITE_VTAB_CONSTRAINT_SUPPORT , SQLITE_VTAB_INNOCUOUS, SQLITE_VTAB_DIRECTONLY  중 하나를 선택해서 가상 테이블에 대한 환경설정을 할 수도 있다. 이것은 옵션이라서 호출 안해도 상관 없어 보인다. SQLITE_VTAB_INNOCUOUS(trigger 와 view를 악의적으로 사용되더라도 피해를 줄 수 없음),   SQLITE_VTAB_DIRECTONLY(trigger 와 view를 사용금지), SQLITE_VTAB_CONSTRAINT_SUPPORT(2번째 argument 도 활용해서 좀 복잡하다. )

xBestIndex  (int (*xBestIndex)(sqlite3_vtab *pVTab, sqlite3_index_info*);)
* 연산에 대해 처리 cost 를 계산해서 효율적인 접근 방법을 계산할 때 이용한다. sqlite3_prepare 또는 유사한 기능(아마 쿼리를 직접 호출하는 경우를 말하는 것 같다.)을 이용할 때, 이 callback 함수가 호출되며, 여러번 호출될 수 있다. 그러면서 최적의 속도를 얻을 수 있는 방법을 계산한다. 이 함수가 구현의 핵심부분이라 더 자세히 찾아볼 필요가 있다. 

xDisconnect : int (*xDisconnect)(sqlite3_vtab *pVTab);

xDestroy : int (*xDestroy)(sqlite3_vtab *pVTab);
* xDisconnect 는 삭제가 아닌 연결만을 해제합니다. xDisconnect 는 DB연결이 close 될 때 호출되고, xDestroy 는  DROP TABLE 구문이 실행될 때, 호출된다. csv virtual table 경우 둘 다 동일한 callback point 이다. 

xOpen : int (*xOpen)(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor);
xClose : int (*xClose)(sqlite3_vtab_cursor*);
* xOpen는 virtual table 에 접근하는(read / write) 하는 cursor를 생성한다. xClose는 이 cursor 를 close 한다. xOpen 은 모든 virtual table 에 필수적으로 필요한 callback 이다. 이렇게 해서 생성된 cursor는 cursor의 위치를 지정하거(file seek의 의미인듯) read 하기 전에 xFilter 를 호출한다. 

xEof : int (*xEof)(sqlite3_vtab_cursor*);
* 현재 cursor 가 유효한 레코드를 가리키고 false, 아니면 true 를 리턴한다. xEof 는 xNext 나 xFilter 호출후에 호출된다.

xFilter : int (*xFilter)(sqlite3_vtab_cursor*, int idxNum, const char *idxStr, int argc, sqlite3_value **argv);
* xOpen에 의해 열린 cursor 에 대해 검색을 함. 필터 기준에 만족하는 레코드가 있으면 커서를 해당 레코드에 위치시킨다. 검색 조건은 argc, argv에 의해 전달되는데, 이 값은 xBestIndex  함수가 호출될 때, 설정된 값으로 전달되는 것 같다. (정확히 어떻게 전달되는지 확인필요). 

xNext : int (*xNext)(sqlite3_vtab_cursor*);
* xFilter 에 의해 cursor 가 세팅된 이후, 값이 불리고 나서 다음 record가 호출될 때, xNext 가 불러지는 것 같다. 

xColumn : int (*xColumn)(sqlite3_vtab_cursor*, sqlite3_context*, int N);
* 현재 행의 N번째 열에 대한 값을 찾기 위해 이 메서드를 호출합니다

xRowid : int (*xRowid)(sqlite3_vtab_cursor *pCur, sqlite_int64 *pRowid);
* 현재 cursor에 대한 rowID 를 pRowid 로 전달한다. 

xUpdate : int (*xUpdate)(sqlite3_vtab *pVTab, int argc, sqlite3_value **argv, sqlite_int64 *pRowid);
* 가상테이블에 대해 delete, insert, update 쿼리를 보낼 때, 호출된다. 가상테이블에 대한 수정을 지원하지 않는 경우 구현하지 않아도 된다. 

xFindFunction : int (*xFindFunction)(sqlite3_vtab *pVtab, int nArg, const char *zName,
  void (**pxFunc)(sqlite3_context*,int,sqlite3_value**), void **ppArg);
* sqlite3_prepare 호출될 때, 가상 테이블 구현에 대해 함수를 overload 할 기회를 제공한다. 여기서는 virtual table 에 대해서만 생각했지만, sqlite 에서 모듈을 이용해서 SQL 함수를 구현할 수 있다. 이렇게 구현한 SQL 함수에 대해 다시 재 정의가 가능한 것 같다. 

xBegin : int (*xBegin)(sqlite3_vtab *pVTab);
xSync : int (*xSync)(sqlite3_vtab *pVTab);
xCommit : int (*xCommit)(sqlite3_vtab *pVTab);
xRollback : int (*xRollback)(sqlite3_vtab *pVTab);
* 가상 테이블에 대해 transaction을 구현할 때, callback 이 호출됨

xSavepoint : int (*xSavepoint)(sqlite3_vtab *pVtab, int);
xRelease : int (*xRelease)(sqlite3_vtab *pVtab, int);
xRollbackTo : int (*xRollbackTo)(sqlite3_vtab *pVtab, int);
* transaction 에서 더 나가 savepoint 기능을 구현할 때 필요

xRename : int (*xRename)(sqlite3_vtab *pVtab, const char *zNew);
* alter table 을 구현할 때 필요

요즘이라고 적었지만 내 기준으로 학교에서 배우지 못한 sorting 을 정리한다. 

  Bitonic sorter(https://en.wikipedia.org/wiki/Bitonic_sorter)
 * 우선 이 sort 는 병렬 처리에 최적화된 sort 이다. 이 sort 에 대해 이해하려면 Sorting network(https://en.wikipedia.org/wiki/Sorting_network) 을 이해해야한다. Sorting Network 는 N개의 항목에 대해 비교연산을 최적화해서 sorting 하는 방법이다. 

왼쪽은 input 된 인자의 array 이고 오른쪽은 output의 array 라고 생각하면된다. sorting network 에서 위에서 위, 아래를 잇는 수직선은 두 element 끼리 비교연산을 해서 위치를 유지하거나 swap 한다고 생각하면된다. 대충 함수로 나타나면 아래와 같다. (함수에 오류가 있을 수 있다. 대충 작성했다.)

def cmp_swap(arr, idx_0, idx_1):
    if arr[idx_0] < arr[idx_1]:
        temp = arr[idx_0]
        arr[idx_1] = temp
        return arr
    return arr

def sortnetwork_desc(a):  // 내림차순
    a = cmp_swap(a, 0, 2)
    a = cmp_swap(a, 1, 3)
    a = cmp_swap(a, 0, 1)
    a = cmp_swap(a, 1, 2)
    return a

증명은  [1,2,3,4], [1,3,2,4], ....  [4, 3, 2, 1] ( 24개: 4*3*2*1 :  4! ) 같은 데이터 조합에 대해 모두 정렬이 된다면 잘 동작한다고 생각 할 수 있다. 좀 많이 무식하게 구현하면 프로스포츠 경기의 리그전 같이 하나의 element 가 모든 다른 element 와 비교하게 할 수도 있다. (아래에 position-counting-sort 이라고 정말 리그전 같은 알고리즘도 설명해 두었다.) 물론 sorting network 는 그 것보다는 좀 더 비교 연산이 적게 되어 있다. 

이 sorting network 를 예쁘게 만들면 아래처럼 된다. 

위 그림을 보면 4개의 비교 연산을 한 번에 하면 빠르게 동작 할 수 있겠다고 보여진다. 
1회   (a0,a1),  (a2,a3), (a4, a5), (a6, a7)
2회   (a0, a3), (a2, a3), (a4, a7), (a5, a6)
.....
6회  (a0,a1),  (a2,a3), (a4, a5), (a6, a7) 
로 계산할 수도 있다. 
그래픽 카드를 이용해서 병렬계산하거나 Simd(https://ko.wikipedia.org/wiki/SIMD) 명령어를 이용하면 고정적인 횟수로 빠르게 정렬을 할 수 있다. 

Timsort( https://en.wikipedia.org/wiki/Timsort )
* 기본 아이디어는 Insertion sort와 Merge sort를 결합한 알고리즘이다.  https://d2.naver.com/helloworld/0315536  여기에 너무 설명이 잘 되어 있다. 추가 설명이 필요 없을 것 같다.

pdqsort(https://github.com/orlp/pdqsort)
* golang 에서 이 sort 을 기본으로 사용 하겠다고 한다.  (https://github.com/golang/go/commit/72e77a7f41bbf45d466119444307fd3ae996e257 ) 
딱히 이 sort 에 대해 쉽게 설명이 잘 되어있는 곳을 찾지 못했다. 의도는 quick sort 와 quick sort 의 worst case 에 heap sort 를 하겠다는 발상이다. 


position-counting-sort(https://github.com/stgatilov/position-counting-sort) 
* 딱히 유명한 sort 방법은 아닌데, 요즘 개인적으로 관심을 가지는 방법이다. 위에서 설명한 Bitonic sorter 보다 더 무식하게 비교 연산을 한다.   a0, a1, a2, a3 이렇게 데이터가 있을 때,  a0 정렬 순위(정렬을 했을 때의 순위)계산하기 위해 싹 다 비교 연산을 한다. (마치 스포츠경기의 리그전 같이 한 팀이 나머지 팀을 모두 경기를 갖는 것이다. 거기에 따라서 순서가 정해진다. )

def position_counting_sort(a):  # 내림차순(높은 값에서 낮은 값으로)으로 정렬한다.
    ranks = [0] * len(a)
    for i in range(len(a)):
        ranking = 0
        for j in range(len(a)):
            # 무식하게 a[i] 보다 작은 것들의 개수를 센다. (구현이 귀찮아 자신도 포함해서 계산했다.)
            # 그 수 만큼 순위가 결정된다. 
            # a[i] 보다 큰 값이 하나도 없으면 ranking 은 0이다.
            if a[i] < a[j]:     
                ranking +=1
        # rank에 저장되는 값은 정렬된 순서가 아니라 각 위치별 순위이다.
        ranks[i] = ranking

    # rank 배열에 저장된 값에 따라 다시 한 번 여기서 순서대로 배열한다.
    out = [0] * len(a)
    for i in range(len(a)):
        out[ranks[i]] = a[i]
   return out

각 원소 하나에 대해 다른 원소들을 모두 비교한다. 일반적인 경우라면 당연히 매우 느릴 것이다. 그런데 simd 같이 한 번에 여러 비교 연산을 할 수 있다면 정렬 속도가 고정적인 괜찮은 알고리즘이 될 수 있다. 실용적인 관점에서 본다면 simd 같은 병렬처리를 사용하고 작은 그룹을 지어서 position-counting-sort 한 다음에 이 그룹끼리 merge 연산을 사용하는 hybrid 방식을 추구 해 볼 수 있다. 
물론 Bitonic sorter 보다 비교 연산이 많아서 불리 한 것 같지만 배열간의 이동이 거의 없다. 그리고 결과값으로 정렬된 데이터 뿐만 아니라 정렬순서표(위 소스에서 ranks 변수) 를 얻을 수 있다. 보통 key, value 가 하나의 set 로 정렬되는 경우도 많인데, 이 때 value 값에 정렬하면서 key 값을 얻을 수 있는 장점도 있다. 



 

 전에 HTTP/2 Server Push 사용하기(https://yiunsr.tistory.com/852)  라는 글을 적은 적 있다. 이 때 나는 Nginx 의 http2_push 만을 이용한 방법을 이야기 했다.
 우선 http2 server push 는 html 페이지가 전달될 때, 해당 html 페이지에서 사용하는 css, js, img 등을 같이 한 번에 보내는 방법이다. http2_push 의 경우는 nginx 설정에 들어가기 때문에 고정적인 asset 만 가능하다. (HTTP/2 Server Push 사용하기(https://yiunsr.tistory.com/852)  를 참고할 것) 그런데 이번에 알게된 http2_push_preload 의 경우 flask 에서 Reponse 하는 Header 에 따라서 동적으로 nginx 에게 http2 sesrver push 리소스를 알려줄 수 있다. 이렇게 하면 nginx 에서 알아서 해당 리소스를 같이 http2 server push 해서 보내가 된다. 
내 경우 Flask-Assets 이라는 것을 이용해서 js, css 파일을 번들링해서 하는 파일이름에 hash된 이름이 들어간다.  (app_common.js?7a0733ee 이런 식으로 파일의 hash 가 생성되어 추가된다. ). 이 때마다 nginx 설정을 변경하는 것은 너무 불편하다. 이런 것을 자동으로 구현 할 수 있게 된다. 
예를 flask 만을 들었는데, django 의 경우도 가능할 것 같다. reponse header 를 수정할 수 있는 모든 플러그인은 가능할 것 같다. (그래서 PHP 같은 것도 가능할 것 같다. ) 

 사용하기 위해서는 nginx  에서 설정하는 방법은 아래와 같이 on 시키면 된다. 

location  = / {
        include uwsgi_params;
        uwsgi_pass .............
        ............
        http2_push_preload on;
        ............
    }

 여기서 중요한 것은 Flask 서버쪽에서도 설정이 필요하다. 일반적으로 Request Header 를 이용하는 경우는 있어도 Response Header 를 이용하는 경우는 거의 없을 것이다. 크롬 DevTools 을 통해 네트워크를 보면 Response Header도  볼 수있다. 

이 Response Header 에 link 키에 </static/js/script.js>; rel=preload; as=script    같은 것을 넣어주면 된다. 이러면 Nginx 가 자동으로 html 전달되는 동안 /app/script.js 파일도 같이 전달한다. css 의 경우 </static/css/common.css>; as=style; rel=preload 같은 형태로 넣으면 된다. 2개 이상일 경우 이것을 ,(콤마) 로 구별해서 넣을 수 있다. </static/js/script.js>; rel=preload; as=script,</static/css/common.css>; as=style; rel=preload   당연히 이 경로는 해당도메인/static/js/script.js 가 접근가능하도록 설정되어 있어야 한다. 

Flask 에서는 Reponse Header 는 https://stackoverflow.com/a/25860353/6652082  에서 나타난 것처럼 할 수도 있고 https://stackoverflow.com/a/63691704/6652082 에서 처럼 return 할 때 지정할 수도 있다. 
대략 아래와 같은 형태가 될 것이다. 

from flask import make_response

@main.route('/', methods=['GET'])
def index():
    resp = make_response(render_template('main/index.html'))
    resp.headers["link"] = "</static/js/script.js>; rel=preload; as=script,</static/css/common.css>; as=style; rel=preload"
    return resp

당연히 HTML 코드는 아래 처럼 되어 있을 것이다. 

<html>
    <link href="/static/css/common.css" rel="stylesheet">
    <body>
        Hello, World
    	<script src="/static/js/script.js"></script>
    </body>

</html>

만약 HTTP/2 를 지원하지 않는다면  기존과 같이 HTML 을 랜더링 할 때 common.css, script.js 파일을 서버로 요청할게 될 것이다. 

여기에 더 나가서 cookies 를 잘 이용하면 이미 해당 리소스가 있는 경우(최근에 해당 페이지에 접근해서 리소스를 받은 경우) http2 server push 가 필요없는 경우 굳이 보내지 않도록 설정할 수도 있다. 내 경우에는 Flask-Assets 때문에 좀 더 고민을 해봐야 한다. 어느정도 코드가 정리되면 올리도록 하겠다.