table.go 59 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058
  1. package storage
  2. import (
  3. "errors"
  4. "fmt"
  5. "hash/fnv"
  6. "math"
  7. "strconv"
  8. "strings"
  9. "sync"
  10. "time"
  11. )
  12. // Row represents a database row.
  13. type Row map[string]interface{}
  14. // UniqueViolationError reports a duplicate value on a UNIQUE index. The
  15. // constraint name identifies the violated index so protocol layers can surface a
  16. // machine-detectable error.
  17. type UniqueViolationError struct {
  18. Constraint string
  19. }
  20. func (e *UniqueViolationError) Error() string {
  21. return fmt.Sprintf("UNIQUE constraint failed: %s", e.Constraint)
  22. }
  23. // TableManager manages table data operations.
  24. type TableManager struct {
  25. pool *KVPool
  26. schema *SchemaManager
  27. database string
  28. cacheMu sync.RWMutex
  29. uniqueCache map[string]*uniqueIndexCache
  30. indexRowValues map[string]map[int64]string // index name → rowid → candidate key
  31. keyRowCache map[string]map[string]int64 // table name → primary key → rowid
  32. indexCache map[string]map[string][]int64 // index name → indexed value → rowids
  33. indexTable map[string]string // index name → table name
  34. rowKeyCache map[string]map[int64]string // table name → rowid → primary key
  35. // disabledIndexes prevents a concurrent lookup from rebuilding an index
  36. // after DROP has cleared it but before the schema entry is removed.
  37. disabledIndexes map[string]bool
  38. // counts holds exact per-table row counts for the COUNT(*) fast path.
  39. // It is derived lazily from durable rows on first use and maintained
  40. // incrementally by Insert/InsertBulk/Delete thereafter.
  41. counts map[string]int
  42. countsInit map[string]bool
  43. countGeneration map[string]time.Time
  44. // stripes are deterministic per-key locks used by point operations
  45. // (GetByPK/Insert/UpdateByPK/DeleteByPK). They replace the table-wide lock
  46. // so point operations on different keys of the same table proceed
  47. // concurrently. Index is derived from the full data key (database+table+pk).
  48. stripes [64]sync.Mutex
  49. // foreignKeyMu serializes writes that touch a table participating in a
  50. // FOREIGN KEY, so a child-side or parent-side validation scan cannot
  51. // interleave with a conflicting write. It is always acquired before any
  52. // table gate.
  53. foreignKeyMu sync.Mutex
  54. // generations tracks full-table scans. predicateGenerations narrows indexed
  55. // equality reads to one index value so unrelated writes do not conflict.
  56. genMu sync.Mutex
  57. generations map[string]uint64
  58. predicateGenerations map[string]uint64
  59. // rowLocks holds optimistic row locks created by SELECT ... FOR UPDATE.
  60. // Ordinary writes only consult it at their commit/batch boundary.
  61. rowLocks *RowLockManager
  62. // exprMu guards exprEval, the pluggable evaluator for expression-index
  63. // columns. It is set by the SQL executor so storage stays independent of
  64. // the SQL front end.
  65. exprMu sync.RWMutex
  66. exprEval ExpressionEvaluator
  67. }
  68. // ExpressionEvaluator computes the value of a persisted index expression for a
  69. // row. The SQL executor registers one so the storage layer can enforce
  70. // expression indexes without importing the parser/executor.
  71. type ExpressionEvaluator func(expression string, row Row) (interface{}, error)
  72. // SetExpressionEvaluator installs the evaluator used to compute expression-index
  73. // values during uniqueness validation and index maintenance.
  74. func (m *TableManager) SetExpressionEvaluator(eval ExpressionEvaluator) {
  75. m.exprMu.Lock()
  76. m.exprEval = eval
  77. m.exprMu.Unlock()
  78. }
  79. func (m *TableManager) expressionEvaluator() ExpressionEvaluator {
  80. m.exprMu.RLock()
  81. defer m.exprMu.RUnlock()
  82. return m.exprEval
  83. }
  84. // NewTableManager creates a new table manager.
  85. func NewTableManager(pool *KVPool, schema *SchemaManager, database string) *TableManager {
  86. return &TableManager{
  87. pool: pool,
  88. schema: schema,
  89. database: database,
  90. uniqueCache: make(map[string]*uniqueIndexCache),
  91. indexRowValues: make(map[string]map[int64]string),
  92. keyRowCache: make(map[string]map[string]int64),
  93. indexCache: make(map[string]map[string][]int64),
  94. indexTable: make(map[string]string),
  95. rowKeyCache: make(map[string]map[int64]string),
  96. disabledIndexes: make(map[string]bool),
  97. counts: make(map[string]int),
  98. countsInit: make(map[string]bool),
  99. countGeneration: make(map[string]time.Time),
  100. generations: make(map[string]uint64),
  101. predicateGenerations: make(map[string]uint64),
  102. rowLocks: NewRowLockManager(),
  103. }
  104. }
  105. // RowLocks returns the manager for locking reads on this table set.
  106. func (m *TableManager) RowLocks() *RowLockManager { return m.rowLocks }
  107. func (m *TableManager) tableLock(key string) *sync.RWMutex {
  108. return m.schema.tableLock(key)
  109. }
  110. // stripeKey returns the deterministic striped lock for a point operation on the
  111. // given full data key. Point operations on different keys therefore serialize
  112. // independently, while operations on the same key are mutually exclusive.
  113. func (m *TableManager) stripeKey(key string) *sync.Mutex {
  114. h := fnv.New32a()
  115. h.Write([]byte(key))
  116. return &m.stripes[h.Sum32()%uint32(len(m.stripes))]
  117. }
  118. // generation returns the current in-process generation for a table. It is
  119. // bumped on every committed write and captured by transaction scans.
  120. func (m *TableManager) generation(table string) uint64 {
  121. key := strings.ToLower(table)
  122. m.genMu.Lock()
  123. g := m.generations[key]
  124. m.genMu.Unlock()
  125. return g
  126. }
  127. // bumpGeneration advances a table's generation. Callers hold the table gate in
  128. // shared mode for point writes or exclusive mode for scan-based writes.
  129. func (m *TableManager) bumpGeneration(table string) {
  130. key := strings.ToLower(table)
  131. m.genMu.Lock()
  132. m.generations[key]++
  133. m.genMu.Unlock()
  134. }
  135. func indexPredicateKey(table, indexName, value string) string {
  136. return strings.ToLower(table) + "\x00" + strings.ToLower(indexName) + "\x00" + value
  137. }
  138. func indexPredicateWildcardKey(table string) string {
  139. return strings.ToLower(table) + "\x00*"
  140. }
  141. func (m *TableManager) predicateSnapshot(table, indexName, value string) (string, uint64, string, uint64) {
  142. valueKey := indexPredicateKey(table, indexName, value)
  143. wildcardKey := indexPredicateWildcardKey(table)
  144. m.genMu.Lock()
  145. valueGen := m.predicateGenerations[valueKey]
  146. wildcardGen := m.predicateGenerations[wildcardKey]
  147. m.genMu.Unlock()
  148. return valueKey, valueGen, wildcardKey, wildcardGen
  149. }
  150. func (m *TableManager) predicateGeneration(key string) uint64 {
  151. m.genMu.Lock()
  152. gen := m.predicateGenerations[key]
  153. m.genMu.Unlock()
  154. return gen
  155. }
  156. func (m *TableManager) bumpIndexPredicates(table string, rows ...Row) error {
  157. indexes, err := m.schema.ListTableIndexes(table)
  158. if err != nil || len(indexes) == 0 {
  159. return err
  160. }
  161. m.genMu.Lock()
  162. defer m.genMu.Unlock()
  163. for _, row := range rows {
  164. if row == nil {
  165. continue
  166. }
  167. for _, index := range indexes {
  168. value, err := m.buildIndexValue(row, index.Columns)
  169. if err != nil {
  170. return err
  171. }
  172. m.predicateGenerations[indexPredicateKey(table, index.Name, value)]++
  173. }
  174. }
  175. return nil
  176. }
  177. func (m *TableManager) bumpIndexPredicateWildcard(table string) {
  178. m.genMu.Lock()
  179. m.predicateGenerations[indexPredicateWildcardKey(table)]++
  180. m.genMu.Unlock()
  181. }
  182. // compareWritePoint issues a single CompareBatchWrite against the pooled KV.
  183. // It returns whether the compare checks held and the ops committed.
  184. func (m *TableManager) compareWritePoint(checks []CompareCheck, ops []BatchOp) (bool, error) {
  185. var committed bool
  186. err := m.pool.WithClient(func(c *KVClient) error {
  187. _, ok, err := c.CompareBatchWrite(checks, ops, nil)
  188. committed = ok
  189. return err
  190. })
  191. return committed, err
  192. }
  193. // invalidateCache removes a table's derived in-memory indexes.
  194. func (m *TableManager) invalidateCache(table string) {
  195. m.cacheMu.Lock()
  196. key := strings.ToLower(table)
  197. delete(m.rowKeyCache, key)
  198. delete(m.keyRowCache, key)
  199. delete(m.counts, key)
  200. delete(m.countsInit, key)
  201. delete(m.countGeneration, key)
  202. for indexName, tableName := range m.indexTable {
  203. if tableName == key {
  204. delete(m.indexCache, indexName)
  205. delete(m.indexRowValues, indexName)
  206. delete(m.indexTable, indexName)
  207. }
  208. }
  209. m.cacheMu.Unlock()
  210. }
  211. // InvalidateCache is the exported version for use by the executor.
  212. func (m *TableManager) InvalidateCache(table string) {
  213. m.invalidateCache(table)
  214. m.cacheMu.Lock()
  215. for name, cache := range m.uniqueCache {
  216. if cache.table == strings.ToLower(table) {
  217. delete(m.uniqueCache, name)
  218. }
  219. }
  220. m.cacheMu.Unlock()
  221. }
  222. // rowVisitFunc is invoked for each decoded row in a streaming scan. Return
  223. // stop=true to end the scan early; a non-nil error aborts the scan.
  224. type rowVisitFunc func(Row) (stop bool, err error)
  225. // scanRows streams the rows of table by scanning durable KV rows one page at a
  226. // time under a single pooled client. Each page is decoded as it arrives and
  227. // passed to fn, which may stop the scan early. The cursor is always closed and
  228. // the client always returned to the pool, even on error.
  229. func (m *TableManager) scanRows(table string, fn rowVisitFunc) error {
  230. return m.scanRowsWithPageSize(table, scanPageSize, fn)
  231. }
  232. func (m *TableManager) scanRowsWithPageSize(table string, pageSize uint32, fn rowVisitFunc) error {
  233. return m.pool.WithClient(func(client *KVClient) (retErr error) {
  234. cursor, err := client.ScanWithLimit([]byte(m.dataPrefix(table)), pageSize)
  235. if err != nil {
  236. return err
  237. }
  238. defer func() {
  239. if err := cursor.Close(); retErr == nil {
  240. retErr = err
  241. }
  242. }()
  243. for {
  244. entries, done, err := cursor.Next()
  245. if err != nil {
  246. return err
  247. }
  248. for _, e := range entries {
  249. row, err := decodeRow(e.Value)
  250. if err != nil {
  251. return err
  252. }
  253. stop, err := fn(row)
  254. if err != nil {
  255. return err
  256. }
  257. if stop {
  258. return nil
  259. }
  260. }
  261. if done {
  262. return nil
  263. }
  264. }
  265. })
  266. }
  267. // rowWithLSNVisitFunc is like rowVisitFunc but also passes the durable row LSN.
  268. type rowWithLSNVisitFunc func(row Row, lsn uint64) (stop bool, err error)
  269. // scanRowsWithLSN streams a table's rows together with their durable LSNs. It
  270. // is used by buffered transactions to capture a per-row read set for
  271. // compare-and-swap validation at commit.
  272. func (m *TableManager) scanRowsWithLSN(table string, fn rowWithLSNVisitFunc) error {
  273. return m.pool.WithClient(func(client *KVClient) (retErr error) {
  274. cursor, err := client.ScanWithLimit([]byte(m.dataPrefix(table)), scanPageSize)
  275. if err != nil {
  276. return err
  277. }
  278. defer func() {
  279. if err := cursor.Close(); retErr == nil {
  280. retErr = err
  281. }
  282. }()
  283. for {
  284. entries, done, err := cursor.Next()
  285. if err != nil {
  286. return err
  287. }
  288. for _, e := range entries {
  289. row, err := decodeRow(e.Value)
  290. if err != nil {
  291. return err
  292. }
  293. stop, err := fn(row, e.LSN)
  294. if err != nil {
  295. return err
  296. }
  297. if stop {
  298. return nil
  299. }
  300. }
  301. if done {
  302. return nil
  303. }
  304. }
  305. })
  306. }
  307. // scanRowsAtPrefix streams the rows under an explicit data prefix together with
  308. // their keys and durable LSNs. A transaction uses it when the rows of a table
  309. // still live under an older name because RENAME TABLE defers moving them to the
  310. // commit.
  311. func (m *TableManager) scanRowsAtPrefix(prefix string, fn func(key string, row Row, lsn uint64) (stop bool, err error)) error {
  312. return m.pool.WithClient(func(client *KVClient) (retErr error) {
  313. cursor, err := client.ScanWithLimit([]byte(prefix), scanPageSize)
  314. if err != nil {
  315. return err
  316. }
  317. defer func() {
  318. if err := cursor.Close(); retErr == nil {
  319. retErr = err
  320. }
  321. }()
  322. for {
  323. entries, done, err := cursor.Next()
  324. if err != nil {
  325. return err
  326. }
  327. for _, e := range entries {
  328. row, err := decodeRow(e.Value)
  329. if err != nil {
  330. return err
  331. }
  332. stop, err := fn(string(e.Key), row, e.LSN)
  333. if err != nil {
  334. return err
  335. }
  336. if stop {
  337. return nil
  338. }
  339. }
  340. if done {
  341. return nil
  342. }
  343. }
  344. })
  345. }
  346. // getKeyWithLSN reads and decodes a row by its explicit durable key.
  347. func (m *TableManager) getKeyWithLSN(key string) (Row, uint64, error) {
  348. var value []byte
  349. var lsn uint64
  350. err := m.pool.WithClient(func(c *KVClient) error {
  351. res, err := c.Get([]byte(key))
  352. if err != nil {
  353. return err
  354. }
  355. value = res.Value
  356. lsn = res.LSN
  357. return nil
  358. })
  359. if err != nil {
  360. if err == ErrKeyNotFound {
  361. return nil, 0, ErrKeyNotFound
  362. }
  363. return nil, 0, err
  364. }
  365. row, err := decodeRow(value)
  366. if err != nil {
  367. return nil, 0, fmt.Errorf("failed to parse row: %w", err)
  368. }
  369. return row, lsn, nil
  370. }
  371. // scanCountKeys counts the durable rows of table using a key-only scan so row
  372. // values are never pulled across the wire. It is used for first-time COUNT(*)
  373. // derivation.
  374. func (m *TableManager) scanCountKeys(table string) (int, error) {
  375. count := 0
  376. err := m.pool.WithClient(func(client *KVClient) (retErr error) {
  377. cursor, err := client.ScanKeys([]byte(m.dataPrefix(table)))
  378. if err != nil {
  379. return err
  380. }
  381. defer func() {
  382. if err := cursor.Close(); retErr == nil {
  383. retErr = err
  384. }
  385. }()
  386. for {
  387. entries, done, err := cursor.Next()
  388. if err != nil {
  389. return err
  390. }
  391. count += len(entries)
  392. if done {
  393. return nil
  394. }
  395. }
  396. })
  397. return count, err
  398. }
  399. // CountFast returns the exact number of rows in a table. The count is derived
  400. // from durable rows on first use (recovering across restarts) and then
  401. // maintained incrementally by the write paths, so repeated COUNT(*) queries
  402. // avoid a full table scan. It intentionally does not persist a counter to KV:
  403. // the KV layer has no atomic increment primitive, and a durable counter that
  404. // could diverge from the rows on crash would be worse than a lazily-derived,
  405. // always-exact value. The cost is one key-only scan the first time COUNT(*) is
  406. // issued after startup.
  407. func (m *TableManager) CountFast(table string) (int, error) {
  408. key := strings.ToLower(table)
  409. tableSchema, err := m.schema.GetSchema(table)
  410. if err != nil {
  411. return 0, err
  412. }
  413. // Cached read path: if the count is initialized for the current table
  414. // generation, return it without taking any table lock.
  415. m.cacheMu.Lock()
  416. if m.countGeneration[key].Equal(tableSchema.CreatedAt) {
  417. if m.countsInit[key] {
  418. n := m.counts[key]
  419. m.cacheMu.Unlock()
  420. return n, nil
  421. }
  422. } else {
  423. delete(m.counts, key)
  424. delete(m.countsInit, key)
  425. m.countGeneration[key] = tableSchema.CreatedAt
  426. }
  427. m.cacheMu.Unlock()
  428. // First derivation: hold the table write lock so the key-only scan is
  429. // exact against concurrent writes.
  430. tl := m.tableLock(key)
  431. tl.Lock()
  432. defer tl.Unlock()
  433. m.cacheMu.Lock()
  434. if !m.countGeneration[key].Equal(tableSchema.CreatedAt) {
  435. delete(m.counts, key)
  436. delete(m.countsInit, key)
  437. m.countGeneration[key] = tableSchema.CreatedAt
  438. }
  439. if m.countsInit[key] {
  440. n := m.counts[key]
  441. m.cacheMu.Unlock()
  442. return n, nil
  443. }
  444. m.cacheMu.Unlock()
  445. count, err := m.scanCountKeys(table)
  446. if err != nil {
  447. return 0, err
  448. }
  449. m.cacheMu.Lock()
  450. m.counts[key] = count
  451. m.countsInit[key] = true
  452. m.cacheMu.Unlock()
  453. return count, nil
  454. }
  455. // countInitialized reports whether the derived count cache is initialized for
  456. // the table at this instant. Write paths capture it before their KV write so a
  457. // concurrent first derivation does not double-count the just-written row.
  458. func (m *TableManager) countInitialized(table string) bool {
  459. key := strings.ToLower(table)
  460. m.cacheMu.Lock()
  461. init := m.countsInit[key]
  462. m.cacheMu.Unlock()
  463. return init
  464. }
  465. // incrCount adjusts the derived per-table row count. wasInit reports whether
  466. // the count was already initialized before the corresponding write, so a count
  467. // that was not yet initialized is left to be re-derived from durable rows
  468. // (which already reflect the write) on next use.
  469. func (m *TableManager) incrCount(table string, generation time.Time, delta int, wasInit bool) {
  470. key := strings.ToLower(table)
  471. m.cacheMu.Lock()
  472. if !m.countGeneration[key].Equal(generation) {
  473. delete(m.counts, key)
  474. delete(m.countsInit, key)
  475. m.countGeneration[key] = generation
  476. }
  477. if wasInit && m.countsInit[key] {
  478. m.counts[key] += delta
  479. }
  480. if !wasInit {
  481. // The count was not initialized before the write, so a concurrent first
  482. // derivation may have missed the just-written row. Invalidate to force
  483. // an exact re-derivation on the next COUNT(*).
  484. delete(m.countsInit, key)
  485. }
  486. m.cacheMu.Unlock()
  487. }
  488. // dataKey returns the key for a row.
  489. func (m *TableManager) dataKey(table, pk string) string {
  490. return fmt.Sprintf("%s:_data:%s:%s", m.database, strings.ToLower(table), pk)
  491. }
  492. // dataPrefix returns the prefix for all rows in a table.
  493. func (m *TableManager) dataPrefix(table string) string {
  494. return fmt.Sprintf("%s:_data:%s:", m.database, strings.ToLower(table))
  495. }
  496. // prepareInsert validates and normalizes an insert row, generating the ROWID
  497. // when required. It returns the normalized row and the full data key without
  498. // writing anything, so both the autocommit path (compare-and-swap) and the
  499. // buffered transaction path (staging) can share it.
  500. func (m *TableManager) prepareInsert(table string, row Row) (Row, string, error) {
  501. schema, err := m.schema.GetSchema(table)
  502. if err != nil {
  503. return nil, "", err
  504. }
  505. return m.prepareInsertWithSchema(table, schema, row)
  506. }
  507. // prepareInsertWithSchema is prepareInsert against a caller-supplied schema, so
  508. // a transaction normalizes rows with the catalog it can see, including a table
  509. // it created or altered in the open transaction.
  510. func (m *TableManager) prepareInsertWithSchema(table string, schema *Schema, row Row) (Row, string, error) {
  511. normalizedRow, key, _, err := m.normalizeInsertRow(table, schema, row)
  512. if err != nil {
  513. return nil, "", err
  514. }
  515. return normalizedRow, key, nil
  516. }
  517. // normalizeInsertRow completes a row image for an insert: it copies the caller's
  518. // columns case-insensitively, applies catalog defaults, assigns the ROWID (or
  519. // the INTEGER PRIMARY KEY rowid alias), encodes the primary key, and validates
  520. // the row constraints. It is shared by the point insert and bulk insert paths so
  521. // both key rows identically. The returned rowid is the row's ROWID alias, or 0
  522. // when the caller must not treat the primary key as a rowid.
  523. func (m *TableManager) normalizeInsertRow(table string, schema *Schema, row Row) (Row, string, int64, error) {
  524. normalizedRow := make(Row)
  525. for _, col := range schema.Columns {
  526. for k, v := range row {
  527. if strings.EqualFold(k, col.Name) {
  528. normalizedRow[col.Name] = v
  529. break
  530. }
  531. }
  532. }
  533. for _, col := range schema.Columns {
  534. if _, ok := normalizedRow[col.Name]; ok {
  535. continue
  536. }
  537. value, hasDefault, err := m.schema.columnDefaultValue(col, m.schema.defaultNow())
  538. if err != nil {
  539. return nil, "", 0, err
  540. }
  541. if hasDefault {
  542. normalizedRow[col.Name] = value
  543. }
  544. }
  545. // Only a single-column INTEGER PRIMARY KEY is a ROWID alias. A composite key
  546. // is never an alias, so its rows always carry an engine-assigned _rowid_.
  547. var rowid int64
  548. if schema.IsSingleColumnPrimaryKey() && !schema.UsesSyntheticRowID() {
  549. pkColumn := schema.PrimaryKey
  550. pkCol, _ := schema.GetColumn(pkColumn)
  551. if pkCol != nil && isIntegerType(pkCol.Type) {
  552. pkValue := normalizedRow[pkColumn]
  553. if pkValue == nil {
  554. nextRowID, err := m.schema.GetNextRowID(table)
  555. if err != nil {
  556. return nil, "", 0, err
  557. }
  558. rowid = nextRowID
  559. normalizedRow[pkColumn] = rowid
  560. } else {
  561. switch v := pkValue.(type) {
  562. case int64:
  563. rowid = v
  564. case float64:
  565. if math.Trunc(v) != v {
  566. return nil, "", 0, fmt.Errorf("invalid integer primary key: %v", v)
  567. }
  568. rowid = int64(v)
  569. case int:
  570. rowid = int64(v)
  571. default:
  572. rowid = 0
  573. }
  574. if rowid > 0 {
  575. if err := m.schema.UpdateMaxRowID(table, rowid); err != nil {
  576. return nil, "", 0, err
  577. }
  578. }
  579. }
  580. }
  581. }
  582. if rowid > 0 {
  583. normalizedRow["_rowid_"] = rowid
  584. } else {
  585. newRowID, err := m.schema.GetNextRowID(table)
  586. if err != nil {
  587. return nil, "", 0, err
  588. }
  589. normalizedRow["_rowid_"] = newRowID
  590. }
  591. key, err := schema.PrimaryKeyForRow(normalizedRow)
  592. if err != nil {
  593. return nil, "", 0, err
  594. }
  595. if err := m.schema.validateRowConstraints(schema, normalizedRow); err != nil {
  596. return nil, "", 0, err
  597. }
  598. // Callers read the resolved key back from the row they passed in: RETURNING
  599. // needs an auto-assigned INTEGER PRIMARY KEY, and a composite table needs key
  600. // components that came from a catalog DEFAULT because the conflict-matching
  601. // and fetch paths run before the next storage call.
  602. for _, column := range schema.PrimaryKeyList() {
  603. if value, ok := normalizedRow[column]; ok {
  604. row[column] = value
  605. }
  606. }
  607. return normalizedRow, m.dataKey(table, key), rowid, nil
  608. }
  609. // Insert inserts a new row. The duplicate check and write are one atomic
  610. // compare-and-swap so concurrent inserts of the same primary key cannot both
  611. // persist. The shared table gate is acquired before the key's striped lock so
  612. // a queued scan writer cannot invert the lock order with point operations.
  613. func (m *TableManager) Insert(table string, row Row) error {
  614. _, err := m.InsertWithRowID(table, row)
  615. return err
  616. }
  617. // InsertWithRowID returns the actual row identifier, never a concurrent counter.
  618. func (m *TableManager) InsertWithRowID(table string, row Row) (int64, error) {
  619. nr, key, err := m.prepareInsert(table, row)
  620. if err != nil {
  621. return 0, err
  622. }
  623. rowid, _ := rowIDFromRow(nr)
  624. wasInit := m.countInitialized(table)
  625. // Foreign-key validation scans the parent (and, for a parent change, the
  626. // child) rows. Take the foreign-key write gate before the table gate so a
  627. // concurrent write on the other side of the constraint cannot interleave and
  628. // so the lock order stays foreign-key gate -> table gate everywhere.
  629. unlockFK, err := m.lockForeignKeyWrites(table)
  630. if err != nil {
  631. return 0, err
  632. }
  633. defer unlockFK()
  634. // Point writers share this gate with each other. Transaction commits and
  635. // scan-based writes take it exclusively, so generation validation and cache
  636. // publication are ordered without serializing writes to different keys.
  637. // A UNIQUE index forces the exclusive gate so the validating scan below
  638. // cannot race another writer (or a concurrent CREATE UNIQUE INDEX).
  639. unlock, uniq, err := m.lockForWrite(table)
  640. if err != nil {
  641. return 0, err
  642. }
  643. defer unlock()
  644. // prepareInsert normalized the row before this gate was held, so a
  645. // concurrent ADD COLUMN may have published a column the row image predates.
  646. // Re-apply the schema that is current under the gate; schema DDL needs the
  647. // exclusive form of this gate, so it cannot change again before the write.
  648. schema, err := m.schema.GetSchema(table)
  649. if err != nil {
  650. return 0, err
  651. }
  652. if err := m.schema.applySchemaDefaults(schema, nr); err != nil {
  653. return 0, err
  654. }
  655. if err := m.schema.validateChecks(schema, nr); err != nil {
  656. return 0, err
  657. }
  658. if err := m.validateInsertForeignKeys(schema, []Row{nr}); err != nil {
  659. return 0, err
  660. }
  661. data, err := encodeRow(nr)
  662. if err != nil {
  663. return 0, fmt.Errorf("failed to serialize row: %w", err)
  664. }
  665. var uniquePlan uniqueCachePlan
  666. if uniq {
  667. uniquePlan, err = m.prepareUniqueRows(table, map[string]*overlayEntry{key: {row: nr}})
  668. if err != nil {
  669. return 0, err
  670. }
  671. }
  672. st := m.stripeKey(key)
  673. st.Lock()
  674. defer st.Unlock()
  675. committed, err := m.compareWritePoint(
  676. []CompareCheck{{Key: []byte(key), LSN: 0}},
  677. []BatchOp{{Op: batchPut, Key: []byte(key), Value: data}},
  678. )
  679. if err != nil {
  680. m.invalidateWriteFailure(table)
  681. return 0, err
  682. }
  683. if !committed {
  684. return 0, newPrimaryKeyViolation(table, schema, nr)
  685. }
  686. m.applyUniquePlan(uniquePlan, nil)
  687. if err := m.updateIndexesForRow(table, nr, true, key); err != nil {
  688. return 0, err
  689. }
  690. // Publish derived index state before its generations. A reader that races
  691. // with publication either sees the old generation and aborts or sees the
  692. // complete new state.
  693. if err := m.bumpIndexPredicates(table, nr); err != nil {
  694. return 0, err
  695. }
  696. m.bumpGeneration(table)
  697. m.incrCount(table, schema.CreatedAt, 1, wasInit)
  698. return rowid, nil
  699. }
  700. // bulkBatchByteBudget bounds a single atomic BATCH_WRITE payload below the
  701. // PKBFI frame limit so a bulk insert never emits a frame the server rejects.
  702. // Each op contributes 12 header bytes plus its key and value.
  703. const bulkBatchByteBudget = 60 * 1024 * 1024
  704. // chunkBatchOps splits ops into atomic BATCH_WRITE chunks bounded by both the
  705. // PKBFI operation-count limit and the frame-size limit. Each chunk is a slice
  706. // of the backing array, valid until the next append to ops.
  707. func chunkBatchOps(ops []BatchOp) [][]BatchOp {
  708. var chunks [][]BatchOp
  709. for i := 0; i < len(ops); {
  710. end := i + maxOperations
  711. if end > len(ops) {
  712. end = len(ops)
  713. }
  714. bytes := 0
  715. j := i
  716. for j < end {
  717. sz := 12 + len(ops[j].Key) + len(ops[j].Value)
  718. if j > i && bytes+sz > bulkBatchByteBudget {
  719. break
  720. }
  721. bytes += sz
  722. j++
  723. }
  724. if j == i {
  725. j = i + 1
  726. }
  727. chunks = append(chunks, ops[i:j])
  728. i = j
  729. }
  730. return chunks
  731. }
  732. // InsertBulk inserts multiple rows efficiently using atomic BATCH_WRITE chunks
  733. // bounded by the PKBFI operation-count and frame-size limits. Skips per-row
  734. // duplicate checks (caller must ensure uniqueness). Used by INSERT ... SELECT.
  735. func (m *TableManager) InsertBulk(table string, rows []Row) (int, error) {
  736. count, _, err := m.InsertBulkWithLastRowID(table, rows)
  737. return count, err
  738. }
  739. // InsertBulkWithLastRowID is InsertBulk, additionally returning the ROWID of the
  740. // last persisted row (0 when nothing persisted).
  741. func (m *TableManager) InsertBulkWithLastRowID(table string, rows []Row) (int, int64, error) {
  742. if len(rows) == 0 {
  743. return 0, 0, nil
  744. }
  745. unlockFK, err := m.lockForeignKeyWrites(table)
  746. if err != nil {
  747. return 0, 0, err
  748. }
  749. defer unlockFK()
  750. tl := m.tableLock(table)
  751. tl.Lock()
  752. defer tl.Unlock()
  753. schema, err := m.schema.GetSchema(table)
  754. if err != nil {
  755. return 0, 0, err
  756. }
  757. wasInit := m.countInitialized(table)
  758. // Normalize rows, assigning the ROWID and encoding the primary key exactly as
  759. // the point insert path does.
  760. normalized := make([]Row, 0, len(rows))
  761. dataKeys := make([]string, 0, len(rows))
  762. for _, row := range rows {
  763. nr, key, _, err := m.normalizeInsertRow(table, schema, row)
  764. if err != nil {
  765. return 0, 0, err
  766. }
  767. normalized = append(normalized, nr)
  768. dataKeys = append(dataKeys, key)
  769. }
  770. // Every row of the batch is visible to the others, so a self-referential
  771. // multi-row insert may reference a sibling that is written in the same
  772. // atomic batch.
  773. if err := m.validateInsertForeignKeys(schema, normalized); err != nil {
  774. return 0, 0, err
  775. }
  776. // Serialize all rows into batch operations. A parallel slice keeps the
  777. // normalized Row for each op for index maintenance after the write.
  778. ops := make([]BatchOp, 0, len(normalized))
  779. encoded := make([]Row, 0, len(normalized))
  780. for i, nr := range normalized {
  781. data, err := encodeRow(nr)
  782. if err != nil {
  783. return 0, 0, err
  784. }
  785. ops = append(ops, BatchOp{Op: batchPut, Key: []byte(dataKeys[i]), Value: data})
  786. encoded = append(encoded, nr)
  787. }
  788. keys := make([][]byte, len(ops))
  789. seen := make(map[string]struct{}, len(ops))
  790. for i, op := range ops {
  791. key := string(op.Key)
  792. if _, duplicate := seen[key]; duplicate {
  793. return 0, 0, newPrimaryKeyViolation(table, schema, normalized[i])
  794. }
  795. seen[key] = struct{}{}
  796. keys[i] = op.Key
  797. }
  798. existing := make([]bool, len(keys))
  799. if err := m.pool.WithClient(func(client *KVClient) error {
  800. for start := 0; start < len(keys); start += maxOperations {
  801. end := start + maxOperations
  802. if end > len(keys) {
  803. end = len(keys)
  804. }
  805. found, err := client.ExistsMany(keys[start:end])
  806. if err != nil {
  807. return err
  808. }
  809. copy(existing[start:end], found)
  810. }
  811. return nil
  812. }); err != nil {
  813. return 0, 0, err
  814. }
  815. for i, found := range existing {
  816. if found {
  817. return 0, 0, newPrimaryKeyViolation(table, schema, normalized[i])
  818. }
  819. }
  820. var uniquePlan uniqueCachePlan
  821. unique, err := m.hasUniqueIndex(table)
  822. if err != nil {
  823. return 0, 0, err
  824. }
  825. if unique {
  826. uniqueEntries := make(map[string]*overlayEntry, len(encoded))
  827. for i, row := range encoded {
  828. uniqueEntries[string(ops[i].Key)] = &overlayEntry{row: row}
  829. }
  830. uniquePlan, err = m.prepareUniqueRows(table, uniqueEntries)
  831. if err != nil {
  832. return 0, 0, err
  833. }
  834. }
  835. // Write rows in atomic BATCH_WRITE chunks. Maintain in-memory indexes only
  836. // for rows that actually persisted, so a partial failure cannot leave an
  837. // already-built index stale.
  838. var firstErr error
  839. numOK := 0
  840. for _, chunk := range chunkBatchOps(ops) {
  841. err := m.pool.WithClient(func(c *KVClient) error {
  842. _, err := c.BatchWrite(chunk, nil)
  843. return err
  844. })
  845. if err != nil {
  846. if firstErr == nil {
  847. firstErr = err
  848. }
  849. break
  850. }
  851. numOK += len(chunk)
  852. }
  853. // Maintain indexes for the rows that persisted (the first numOK ops).
  854. if len(uniquePlan) != 0 {
  855. accepted := make(map[string]bool, numOK)
  856. for i := 0; i < numOK; i++ {
  857. accepted[string(ops[i].Key)] = true
  858. }
  859. m.applyUniquePlan(uniquePlan, accepted)
  860. }
  861. for i := 0; i < numOK; i++ {
  862. if err := m.updateIndexesForRow(table, encoded[i], true, string(ops[i].Key)); err != nil {
  863. return numOK, 0, err
  864. }
  865. }
  866. if numOK > 0 {
  867. m.bumpGeneration(table)
  868. if err := m.bumpIndexPredicates(table, encoded[:numOK]...); err != nil {
  869. return numOK, 0, err
  870. }
  871. }
  872. m.incrCount(table, schema.CreatedAt, numOK, wasInit)
  873. if firstErr != nil {
  874. m.invalidateWriteFailure(table)
  875. }
  876. var lastRowID int64
  877. if numOK > 0 {
  878. lastRowID, _ = rowIDFromRow(encoded[numOK-1])
  879. }
  880. return numOK, lastRowID, firstErr
  881. }
  882. // updateIndexesForRow adds or removes entries from already-built in-memory
  883. // indexes. Index entries are rebuildable from durable row data, so this method
  884. // intentionally does not write idx:* keys to KV.
  885. func (m *TableManager) updateIndexesForRow(table string, row Row, add bool, actualKey string) error {
  886. indexes, err := m.schema.ListTableIndexes(table)
  887. if err != nil || len(indexes) == 0 {
  888. return err
  889. }
  890. rowid, ok := rowIDFromRow(row)
  891. if !ok {
  892. return nil
  893. }
  894. tableKey := strings.ToLower(table)
  895. m.cacheMu.Lock()
  896. if keys, initialized := m.rowKeyCache[tableKey]; initialized {
  897. pk := strings.TrimPrefix(actualKey, m.dataPrefix(table))
  898. reverse := m.keyRowCache[tableKey]
  899. if add {
  900. keys[rowid] = pk
  901. reverse[pk] = rowid
  902. } else {
  903. delete(keys, rowid)
  904. delete(reverse, pk)
  905. }
  906. }
  907. m.cacheMu.Unlock()
  908. for _, idx := range indexes {
  909. indexName := strings.ToLower(idx.Name)
  910. m.cacheMu.RLock()
  911. _, initialized := m.indexCache[indexName]
  912. m.cacheMu.RUnlock()
  913. if !initialized {
  914. continue
  915. }
  916. colValue, err := m.buildIndexValue(row, idx.Columns)
  917. if err != nil {
  918. return err
  919. }
  920. if add {
  921. m.AddIndexEntry(idx.Name, colValue, rowid)
  922. } else {
  923. m.RemoveIndexEntry(idx.Name, colValue, rowid)
  924. }
  925. }
  926. return nil
  927. }
  928. // Select retrieves rows from a table by scanning durable rows and collecting
  929. // only matching rows.
  930. func (m *TableManager) Select(table string, filter func(Row) bool) ([]Row, error) {
  931. tl := m.tableLock(table)
  932. tl.RLock()
  933. defer tl.RUnlock()
  934. return m.selectRows(table, filter)
  935. }
  936. // selectRows scans a table while the caller holds its shared or exclusive gate.
  937. func (m *TableManager) selectRows(table string, filter func(Row) bool) ([]Row, error) {
  938. if !m.schema.TableExists(table) {
  939. return nil, fmt.Errorf("table not found: %s", table)
  940. }
  941. rows := make([]Row, 0)
  942. err := m.scanRows(table, func(row Row) (bool, error) {
  943. if filter == nil || filter(row) {
  944. rows = append(rows, row)
  945. }
  946. return false, nil
  947. })
  948. if err != nil {
  949. return nil, err
  950. }
  951. return rows, nil
  952. }
  953. func cloneRow(row Row) Row {
  954. if row == nil {
  955. return nil
  956. }
  957. cloned := make(Row, len(row))
  958. for k, v := range row {
  959. cloned[k] = v
  960. }
  961. return cloned
  962. }
  963. // SelectWithLimit retrieves rows with limit and offset, applying filter/offset
  964. // while scanning and closing the scan early once the limit is reached.
  965. func (m *TableManager) SelectWithLimit(table string, filter func(Row) bool, limit, offset int) ([]Row, error) {
  966. tl := m.tableLock(table)
  967. tl.RLock()
  968. defer tl.RUnlock()
  969. if !m.schema.TableExists(table) {
  970. return nil, fmt.Errorf("table not found: %s", table)
  971. }
  972. rows := make([]Row, 0)
  973. skipped := 0
  974. pageSize := scanPageSize
  975. if limit > 0 {
  976. desired := limit
  977. if offset > 0 {
  978. if offset >= scanPageSize-desired {
  979. desired = scanPageSize
  980. } else {
  981. desired += offset
  982. }
  983. }
  984. if desired < 1 {
  985. desired = 1
  986. }
  987. if desired < pageSize {
  988. pageSize = desired
  989. }
  990. }
  991. err := m.scanRowsWithPageSize(table, uint32(pageSize), func(row Row) (bool, error) {
  992. if filter != nil && !filter(row) {
  993. return false, nil
  994. }
  995. if skipped < offset {
  996. skipped++
  997. return false, nil
  998. }
  999. rows = append(rows, row)
  1000. return limit > 0 && len(rows) >= limit, nil
  1001. })
  1002. if err != nil {
  1003. return nil, err
  1004. }
  1005. return rows, nil
  1006. }
  1007. // Update updates rows matching the filter.
  1008. func (m *TableManager) Update(table string, updates Row, filter func(Row) bool) (int, error) {
  1009. return m.updateLocked(table, func(Row) (Row, error) { return updates, nil }, filter)
  1010. }
  1011. // UpdateFunc updates rows matching the filter using a function to compute new values.
  1012. // The updateFn receives the current row and returns the updates to apply.
  1013. func (m *TableManager) UpdateFunc(table string, updateFn func(Row) (Row, error), filter func(Row) bool) (int, error) {
  1014. return m.updateLocked(table, updateFn, filter)
  1015. }
  1016. // updateLocked stages the complete update before one compare-batch publication.
  1017. // Evaluation, encoding, validation or I/O errors must never leave earlier rows
  1018. // committed, including when a primary key moves to a different durable key.
  1019. func (m *TableManager) updateLocked(table string, updateFn func(Row) (Row, error), filter func(Row) bool) (int, error) {
  1020. session := NewSession(m.schema, m)
  1021. if err := session.Begin(); err != nil {
  1022. return 0, err
  1023. }
  1024. defer session.Rollback()
  1025. count, err := session.UpdateFunc(table, updateFn, filter)
  1026. if err != nil {
  1027. return 0, err
  1028. }
  1029. if err := session.Commit(); err != nil {
  1030. return 0, err
  1031. }
  1032. return count, nil
  1033. }
  1034. // UpdateByPK updates one row without scanning the table. It uses the key's
  1035. // striped lock and a compare-and-swap write so a concurrent modification of the
  1036. // same row fails with a serialization error instead of being silently lost.
  1037. func (m *TableManager) UpdateByPK(table, pk string, updateFn func(Row) (Row, error)) (Row, bool, error) {
  1038. key := m.dataKey(table, pk)
  1039. unlockFK, err := m.lockForeignKeyWrites(table)
  1040. if err != nil {
  1041. return nil, false, err
  1042. }
  1043. defer unlockFK()
  1044. unlock, uniq, err := m.lockForWrite(table)
  1045. if err != nil {
  1046. return nil, false, err
  1047. }
  1048. defer unlock()
  1049. // Read the schema under the gate so validation sees every column a
  1050. // concurrent ADD COLUMN has published; the row itself is read below, also
  1051. // under the gate.
  1052. schema, err := m.schema.GetSchema(table)
  1053. if err != nil {
  1054. return nil, false, err
  1055. }
  1056. st := m.stripeKey(key)
  1057. st.Lock()
  1058. defer st.Unlock()
  1059. row, lsn, err := m.getByPKWithLSN(table, pk)
  1060. if err == ErrKeyNotFound {
  1061. return nil, false, nil
  1062. }
  1063. if err != nil {
  1064. return nil, false, err
  1065. }
  1066. oldRow := cloneRow(row)
  1067. updates, err := updateFn(row)
  1068. if err != nil {
  1069. return nil, false, err
  1070. }
  1071. for name, value := range updates {
  1072. for _, column := range schema.Columns {
  1073. if strings.EqualFold(name, column.Name) {
  1074. row[column.Name] = value
  1075. break
  1076. }
  1077. }
  1078. }
  1079. if err := m.schema.applySchemaDefaults(schema, row); err != nil {
  1080. return nil, false, err
  1081. }
  1082. if err := m.schema.validateChecks(schema, row); err != nil {
  1083. return nil, false, err
  1084. }
  1085. if err := m.validateInsertForeignKeys(schema, []Row{row}); err != nil {
  1086. return nil, false, err
  1087. }
  1088. if err := m.validateParentKeyRemoval(table, oldRow, row); err != nil {
  1089. return nil, false, err
  1090. }
  1091. data, err := encodeRow(row)
  1092. if err != nil {
  1093. return nil, false, err
  1094. }
  1095. var uniquePlan uniqueCachePlan
  1096. if uniq {
  1097. uniquePlan, err = m.prepareUniqueRows(table, map[string]*overlayEntry{key: {row: row}})
  1098. if err != nil {
  1099. return nil, false, err
  1100. }
  1101. }
  1102. committed, err := m.compareWritePoint(
  1103. []CompareCheck{{Key: []byte(key), LSN: lsn}},
  1104. []BatchOp{{Op: batchPut, Key: []byte(key), Value: data}},
  1105. )
  1106. if err != nil {
  1107. m.invalidateWriteFailure(table)
  1108. return nil, false, err
  1109. }
  1110. if !committed {
  1111. return nil, false, ErrSerialization
  1112. }
  1113. m.applyUniquePlan(uniquePlan, nil)
  1114. if err := m.updateIndexesForRow(table, oldRow, false, key); err != nil {
  1115. return nil, false, err
  1116. }
  1117. if err := m.updateIndexesForRow(table, row, true, key); err != nil {
  1118. return nil, false, err
  1119. }
  1120. if err := m.bumpIndexPredicates(table, oldRow, row); err != nil {
  1121. return nil, false, err
  1122. }
  1123. m.bumpGeneration(table)
  1124. return oldRow, true, nil
  1125. }
  1126. // Delete deletes rows matching the filter.
  1127. func (m *TableManager) Delete(table string, filter func(Row) bool) (int, error) {
  1128. session := NewSession(m.schema, m)
  1129. if err := session.Begin(); err != nil {
  1130. return 0, err
  1131. }
  1132. defer session.Rollback()
  1133. count, err := session.Delete(table, filter)
  1134. if err != nil {
  1135. return 0, err
  1136. }
  1137. if err := session.Commit(); err != nil {
  1138. return 0, err
  1139. }
  1140. return count, nil
  1141. }
  1142. // DeleteByPK deletes one row without scanning the table, using the key's
  1143. // striped lock and a compare-and-swap delete.
  1144. func (m *TableManager) DeleteByPK(table, pk string) (Row, bool, error) {
  1145. schema, err := m.schema.GetSchema(table)
  1146. if err != nil {
  1147. return nil, false, err
  1148. }
  1149. unlockFK, err := m.lockForeignKeyWrites(table)
  1150. if err != nil {
  1151. return nil, false, err
  1152. }
  1153. defer unlockFK()
  1154. key := m.dataKey(table, pk)
  1155. tl := m.tableLock(table)
  1156. tl.RLock()
  1157. defer tl.RUnlock()
  1158. st := m.stripeKey(key)
  1159. st.Lock()
  1160. defer st.Unlock()
  1161. wasInit := m.countInitialized(table)
  1162. row, lsn, err := m.getByPKWithLSN(table, pk)
  1163. if err == ErrKeyNotFound {
  1164. return nil, false, nil
  1165. }
  1166. if err != nil {
  1167. return nil, false, err
  1168. }
  1169. if err := m.validateParentKeyRemoval(table, row, nil); err != nil {
  1170. return nil, false, err
  1171. }
  1172. committed, err := m.compareWritePoint(
  1173. []CompareCheck{{Key: []byte(key), LSN: lsn}},
  1174. []BatchOp{{Op: batchDelete, Key: []byte(key)}},
  1175. )
  1176. if err != nil {
  1177. m.invalidateWriteFailure(table)
  1178. return nil, false, err
  1179. }
  1180. if !committed {
  1181. return nil, false, ErrSerialization
  1182. }
  1183. m.removeUniqueKey(table, key)
  1184. if err := m.updateIndexesForRow(table, row, false, key); err != nil {
  1185. return nil, false, err
  1186. }
  1187. if err := m.bumpIndexPredicates(table, row); err != nil {
  1188. return nil, false, err
  1189. }
  1190. m.bumpGeneration(table)
  1191. m.incrCount(table, schema.CreatedAt, -1, wasInit)
  1192. return row, true, nil
  1193. }
  1194. // GetByPK retrieves a row by primary key. Point reads take only the key's
  1195. // striped lock so reads of different keys progress concurrently.
  1196. func (m *TableManager) GetByPK(table string, pk string) (Row, error) {
  1197. key := m.dataKey(table, pk)
  1198. st := m.stripeKey(key)
  1199. st.Lock()
  1200. defer st.Unlock()
  1201. if !m.schema.TableExists(table) {
  1202. return nil, fmt.Errorf("table not found: %s", table)
  1203. }
  1204. row, _, err := m.getByPKWithLSN(table, pk)
  1205. return row, err
  1206. }
  1207. // getByPKWithLSN reads a row by primary key and returns its KV LSN (0 when
  1208. // absent). It performs no locking; callers must hold the appropriate striped
  1209. // or table lock.
  1210. func (m *TableManager) getByPKWithLSN(table, pk string) (Row, uint64, error) {
  1211. key := m.dataKey(table, pk)
  1212. var value []byte
  1213. var lsn uint64
  1214. err := m.pool.WithClient(func(c *KVClient) error {
  1215. res, err := c.Get([]byte(key))
  1216. if err != nil {
  1217. return err
  1218. }
  1219. value = res.Value
  1220. lsn = res.LSN
  1221. return nil
  1222. })
  1223. if err != nil {
  1224. if err == ErrKeyNotFound {
  1225. return nil, 0, ErrKeyNotFound
  1226. }
  1227. return nil, 0, err
  1228. }
  1229. row, err := decodeRow(value)
  1230. if err != nil {
  1231. return nil, 0, fmt.Errorf("failed to parse row: %w", err)
  1232. }
  1233. return row, lsn, nil
  1234. }
  1235. // Count returns the number of rows in a table matching the filter.
  1236. func (m *TableManager) Count(table string, filter func(Row) bool) (int, error) {
  1237. tl := m.tableLock(table)
  1238. tl.RLock()
  1239. defer tl.RUnlock()
  1240. if !m.schema.TableExists(table) {
  1241. return 0, fmt.Errorf("table not found: %s", table)
  1242. }
  1243. count := 0
  1244. err := m.scanRows(table, func(row Row) (bool, error) {
  1245. if filter == nil || filter(row) {
  1246. count++
  1247. }
  1248. return false, nil
  1249. })
  1250. if err != nil {
  1251. return 0, err
  1252. }
  1253. return count, nil
  1254. }
  1255. // Truncate removes all rows from a table.
  1256. func (m *TableManager) Truncate(table string) (int, error) {
  1257. return m.Delete(table, nil)
  1258. }
  1259. // isIntegerType checks if a type name is an integer type.
  1260. func isIntegerType(typeName string) bool {
  1261. t := strings.ToUpper(typeName)
  1262. switch t {
  1263. case "INTEGER", "INT", "SMALLINT", "BIGINT", "TINYINT", "MEDIUMINT":
  1264. return true
  1265. }
  1266. return false
  1267. }
  1268. // IsRowIDColumn checks if a column name is a ROWID alias.
  1269. func IsRowIDColumn(name string) bool {
  1270. n := strings.ToLower(name)
  1271. return n == "rowid" || n == "oid" || n == "_rowid_"
  1272. }
  1273. // Index entry methods - leveraging radix trie for prefix-based lookups
  1274. // Format: {database}:idx:{index_name}:{column_value} → JSON array of rowids
  1275. // indexEntryKey returns the key for an index entry.
  1276. func (m *TableManager) indexEntryKey(indexName string, colValue interface{}) string {
  1277. return fmt.Sprintf("%s:idx:%s:%s", m.database, strings.ToLower(indexName), formatIndexValue(colValue))
  1278. }
  1279. // indexPrefix returns the prefix for all entries of an index.
  1280. func (m *TableManager) indexPrefix(indexName string) string {
  1281. return fmt.Sprintf("%s:idx:%s:", m.database, strings.ToLower(indexName))
  1282. }
  1283. func formatIndexValue(value interface{}) string {
  1284. // Equality predicates compare numeric values (including numeric text) as
  1285. // float64. Use the same equivalence classes without decimal rounding.
  1286. // Index hits are candidates: the executor still evaluates the predicate.
  1287. var number float64
  1288. switch v := value.(type) {
  1289. case float64:
  1290. number = v
  1291. case int64:
  1292. number = float64(v)
  1293. case int:
  1294. number = float64(v)
  1295. case bool:
  1296. if v {
  1297. return "1"
  1298. }
  1299. return "0"
  1300. case []byte:
  1301. return formatIndexValue(string(v))
  1302. case string:
  1303. parsed, err := strconv.ParseFloat(v, 64)
  1304. if err != nil {
  1305. return v
  1306. }
  1307. number = parsed
  1308. default:
  1309. return fmt.Sprintf("%v", v)
  1310. }
  1311. if number == 0 {
  1312. return "0"
  1313. }
  1314. return strconv.FormatFloat(number, 'g', -1, 64)
  1315. }
  1316. func rowIDFromRow(row Row) (int64, bool) {
  1317. switch v := row["_rowid_"].(type) {
  1318. case int64:
  1319. return v, true
  1320. case int:
  1321. return int64(v), true
  1322. case float64:
  1323. return int64(v), true
  1324. default:
  1325. return 0, false
  1326. }
  1327. }
  1328. func (m *TableManager) ensureIndex(index *Index) error {
  1329. indexKey := strings.ToLower(index.Name)
  1330. m.cacheMu.RLock()
  1331. disabled := m.disabledIndexes[indexKey]
  1332. _, initialized := m.indexCache[indexKey]
  1333. m.cacheMu.RUnlock()
  1334. if disabled {
  1335. return nil
  1336. }
  1337. if initialized {
  1338. return nil
  1339. }
  1340. // Serialize index build against writes to the same table so the derived
  1341. // entries cannot miss a concurrently-inserted row.
  1342. table := index.Table
  1343. key := strings.ToLower(table)
  1344. tl := m.tableLock(key)
  1345. tl.Lock()
  1346. defer tl.Unlock()
  1347. m.cacheMu.RLock()
  1348. disabled = m.disabledIndexes[indexKey]
  1349. _, initialized = m.indexCache[indexKey]
  1350. m.cacheMu.RUnlock()
  1351. if disabled {
  1352. return nil
  1353. }
  1354. if initialized {
  1355. return nil
  1356. }
  1357. tableSchema, err := m.schema.GetSchema(table)
  1358. if err != nil {
  1359. return err
  1360. }
  1361. values := make(map[string][]int64)
  1362. rowKeys := make(map[int64]string)
  1363. if err := m.scanRows(table, func(row Row) (bool, error) {
  1364. rowid, ok := rowIDFromRow(row)
  1365. if !ok {
  1366. return false, nil
  1367. }
  1368. colValue, err := m.buildIndexValue(row, index.Columns)
  1369. if err != nil {
  1370. return true, err
  1371. }
  1372. valueKey := formatIndexValue(colValue)
  1373. pk, err := tableSchema.PrimaryKeyForRow(row)
  1374. if err != nil {
  1375. return true, err
  1376. }
  1377. values[valueKey] = append(values[valueKey], rowid)
  1378. rowKeys[rowid] = pk
  1379. return false, nil
  1380. }); err != nil {
  1381. return err
  1382. }
  1383. m.cacheMu.Lock()
  1384. if _, initialized := m.indexCache[indexKey]; !initialized {
  1385. m.installIndexCacheLocked(indexKey, key, values, rowKeys)
  1386. }
  1387. m.cacheMu.Unlock()
  1388. return nil
  1389. }
  1390. // AddIndexEntry adds a rowid to an in-memory index entry.
  1391. func (m *TableManager) AddIndexEntry(indexName string, colValue interface{}, rowid int64) error {
  1392. indexKey := strings.ToLower(indexName)
  1393. valueKey := formatIndexValue(colValue)
  1394. m.cacheMu.Lock()
  1395. defer m.cacheMu.Unlock()
  1396. values, ok := m.indexCache[indexKey]
  1397. if !ok {
  1398. return nil
  1399. }
  1400. rowids := values[valueKey]
  1401. for _, r := range rowids {
  1402. if r == rowid {
  1403. return nil
  1404. }
  1405. }
  1406. values[valueKey] = append(rowids, rowid)
  1407. if m.indexRowValues[indexKey] == nil {
  1408. m.indexRowValues[indexKey] = make(map[int64]string)
  1409. }
  1410. m.indexRowValues[indexKey][rowid] = valueKey
  1411. return nil
  1412. }
  1413. // RemoveIndexEntry removes a rowid from an in-memory index entry.
  1414. func (m *TableManager) RemoveIndexEntry(indexName string, colValue interface{}, rowid int64) error {
  1415. indexKey := strings.ToLower(indexName)
  1416. valueKey := formatIndexValue(colValue)
  1417. m.cacheMu.Lock()
  1418. defer m.cacheMu.Unlock()
  1419. m.removeIndexEntryLocked(indexKey, valueKey, rowid)
  1420. return nil
  1421. }
  1422. // LookupIndex returns rowids matching a column value using the index.
  1423. func (m *TableManager) LookupIndex(indexName string, colValue interface{}) ([]int64, error) {
  1424. index, err := m.schema.GetIndex(indexName)
  1425. if err != nil {
  1426. return nil, err
  1427. }
  1428. indexKey := strings.ToLower(indexName)
  1429. valueKey := formatIndexValue(colValue)
  1430. for {
  1431. if err := m.ensureIndex(index); err != nil {
  1432. return nil, err
  1433. }
  1434. m.cacheMu.RLock()
  1435. values, initialized := m.indexCache[indexKey]
  1436. disabled := m.disabledIndexes[indexKey]
  1437. rowids := append([]int64(nil), values[valueKey]...)
  1438. m.cacheMu.RUnlock()
  1439. if disabled {
  1440. return nil, fmt.Errorf("%w: %s is disabled", ErrIndexNotFound, indexName)
  1441. }
  1442. if initialized {
  1443. return rowids, nil
  1444. }
  1445. // A shared-gate commit invalidated the cache after ensureIndex.
  1446. }
  1447. }
  1448. // ClearIndex removes an index's in-memory entries and marks it disabled so a
  1449. // concurrent lookup cannot rebuild it after DROP but before the schema entry
  1450. // is removed. Index entries are derived from durable rows, so there is nothing
  1451. // durable to delete here.
  1452. func (m *TableManager) ClearIndex(indexName, tableName string, columns []string) error {
  1453. indexKey := strings.ToLower(indexName)
  1454. tableKey := strings.ToLower(tableName)
  1455. m.cacheMu.Lock()
  1456. delete(m.indexCache, indexKey)
  1457. delete(m.indexRowValues, indexKey)
  1458. delete(m.indexTable, indexKey)
  1459. delete(m.uniqueCache, indexKey)
  1460. m.disabledIndexes[indexKey] = true
  1461. rowKeysNeeded := false
  1462. for _, indexedTable := range m.indexTable {
  1463. if indexedTable == tableKey {
  1464. rowKeysNeeded = true
  1465. break
  1466. }
  1467. }
  1468. if !rowKeysNeeded {
  1469. delete(m.rowKeyCache, tableKey)
  1470. delete(m.keyRowCache, tableKey)
  1471. }
  1472. m.cacheMu.Unlock()
  1473. return nil
  1474. }
  1475. // BuildIndex builds index entries for all existing rows in a table.
  1476. func (m *TableManager) BuildIndex(indexName, tableName string, columns []string) error {
  1477. indexKey := strings.ToLower(indexName)
  1478. m.cacheMu.Lock()
  1479. delete(m.disabledIndexes, indexKey)
  1480. delete(m.indexCache, indexKey)
  1481. delete(m.indexRowValues, indexKey)
  1482. delete(m.indexTable, indexKey)
  1483. m.cacheMu.Unlock()
  1484. index, err := m.schema.GetIndex(indexName)
  1485. if err == nil {
  1486. return m.ensureIndex(index)
  1487. }
  1488. if !errors.Is(err, ErrIndexNotFound) {
  1489. return err
  1490. }
  1491. tableSchema, schemaErr := m.schema.GetSchema(tableName)
  1492. if schemaErr != nil {
  1493. return schemaErr
  1494. }
  1495. indexCols := make([]IndexColumn, len(columns))
  1496. for i, name := range columns {
  1497. indexCols[i] = IndexColumn{Name: name}
  1498. }
  1499. values := make(map[string][]int64)
  1500. rowKeys := make(map[int64]string)
  1501. if err := m.scanRows(tableName, func(row Row) (bool, error) {
  1502. rowid, ok := rowIDFromRow(row)
  1503. if !ok {
  1504. return false, nil
  1505. }
  1506. colValue, err := m.buildIndexValue(row, indexCols)
  1507. if err != nil {
  1508. return true, err
  1509. }
  1510. pk, err := tableSchema.PrimaryKeyForRow(row)
  1511. if err != nil {
  1512. return true, err
  1513. }
  1514. values[formatIndexValue(colValue)] = append(values[formatIndexValue(colValue)], rowid)
  1515. rowKeys[rowid] = pk
  1516. return false, nil
  1517. }); err != nil {
  1518. return err
  1519. }
  1520. m.cacheMu.Lock()
  1521. m.installIndexCacheLocked(indexKey, strings.ToLower(tableName), values, rowKeys)
  1522. m.cacheMu.Unlock()
  1523. return nil
  1524. }
  1525. // indexColumnValue resolves a single index column's value for a row. A plain
  1526. // column is looked up case-insensitively; an expression column is evaluated
  1527. // through the registered expression evaluator.
  1528. func (m *TableManager) indexColumnValue(row Row, col IndexColumn) (interface{}, error) {
  1529. if col.Expression != "" {
  1530. eval := m.expressionEvaluator()
  1531. if eval == nil {
  1532. return nil, fmt.Errorf("expression index column %q requires an expression evaluator", col.Expression)
  1533. }
  1534. return eval(col.Expression, row)
  1535. }
  1536. if v, ok := row[col.Name]; ok {
  1537. return v, nil
  1538. }
  1539. for k, v := range row {
  1540. if strings.EqualFold(k, col.Name) {
  1541. return v, nil
  1542. }
  1543. }
  1544. return nil, nil
  1545. }
  1546. // buildIndexValue creates the index key value from an index's columns. Single
  1547. // column values are formatted directly; composite values are joined with a NUL
  1548. // separator.
  1549. func (m *TableManager) buildIndexValue(row Row, columns []IndexColumn) (string, error) {
  1550. if len(columns) == 1 {
  1551. v, err := m.indexColumnValue(row, columns[0])
  1552. if err != nil {
  1553. return "", err
  1554. }
  1555. return formatIndexValue(v), nil
  1556. }
  1557. parts := make([]string, 0, len(columns))
  1558. for _, col := range columns {
  1559. v, err := m.indexColumnValue(row, col)
  1560. if err != nil {
  1561. return "", err
  1562. }
  1563. parts = append(parts, formatIndexValue(v))
  1564. }
  1565. return strings.Join(parts, "\x00"), nil
  1566. }
  1567. // ── UNIQUE index enforcement ────────────────────────────────────────────────
  1568. //
  1569. // Uniqueness is enforced by scanning durable rows rather than by persisting a
  1570. // separate claim key. There is therefore no storage migration and no new durable
  1571. // state: a table with a UNIQUE index takes its exclusive table gate for writes so
  1572. // a validating scan can never race a concurrent writer. NULL values are exempt
  1573. // (SQLite permits multiple NULLs in a unique index), and composite values are
  1574. // encoded with length prefixes so "a\x00b" in one column can never collide with
  1575. // "a", "b" across two columns.
  1576. // uniqueIndexes returns the UNIQUE indexes defined on a table.
  1577. func (m *TableManager) uniqueIndexes(table string) ([]*Index, error) {
  1578. indexes, err := m.schema.ListTableIndexes(table)
  1579. if err != nil {
  1580. return nil, err
  1581. }
  1582. var uniq []*Index
  1583. for _, idx := range indexes {
  1584. if idx.Unique {
  1585. uniq = append(uniq, idx)
  1586. }
  1587. }
  1588. return uniq, nil
  1589. }
  1590. // hasUniqueIndex reports whether the table has any UNIQUE index. An IO error is
  1591. // surfaced so callers never silently skip uniqueness enforcement.
  1592. func (m *TableManager) hasUniqueIndex(table string) (bool, error) {
  1593. indexes, err := m.uniqueIndexes(table)
  1594. if err != nil {
  1595. return false, err
  1596. }
  1597. return len(indexes) > 0, nil
  1598. }
  1599. // HasUniqueIndex reports whether the table has any UNIQUE index, surfacing IO
  1600. // errors. It is the exported form used by the executor to decide whether to run a
  1601. // DML statement inside an implicit transaction for statement-level atomicity.
  1602. func (m *TableManager) HasUniqueIndex(table string) (bool, error) {
  1603. return m.hasUniqueIndex(table)
  1604. }
  1605. // encodeUniqueValue encodes the indexed value of a row with per-column type tags
  1606. // and length prefixes. It returns isNull=true when any indexed column is NULL, in
  1607. // which case the row is exempt from uniqueness. The length prefix makes composite
  1608. // encodings collision-free. Expression columns are evaluated through the
  1609. // registered evaluator.
  1610. func (m *TableManager) encodeUniqueValue(row Row, columns []IndexColumn) (string, bool, error) {
  1611. var sb strings.Builder
  1612. for _, col := range columns {
  1613. v, err := m.indexColumnValue(row, col)
  1614. if err != nil {
  1615. return "", false, err
  1616. }
  1617. if v == nil {
  1618. return "", true, nil
  1619. }
  1620. s := encodeUniqueScalar(v)
  1621. sb.WriteString(strconv.Itoa(len(s)))
  1622. sb.WriteByte(':')
  1623. sb.WriteString(s)
  1624. }
  1625. return sb.String(), false, nil
  1626. }
  1627. // encodeUniqueScalar encodes a scalar for uniqueness comparison. Integral
  1628. // numerics are canonicalized across their integer/float/unsigned Go
  1629. // representations so a computed value such as 1.5-0.5 (float64) collides with
  1630. // the literal 1 (int64) the same way SQLite's numeric affinity does. Non-integral
  1631. // reals keep a full-precision tag so no distinct value is lost. TEXT and BLOB
  1632. // remain distinct from numbers.
  1633. func encodeUniqueScalar(v interface{}) string {
  1634. switch t := v.(type) {
  1635. case bool:
  1636. if t {
  1637. return "b1"
  1638. }
  1639. return "b0"
  1640. case int:
  1641. return "i" + strconv.FormatInt(int64(t), 10)
  1642. case int64:
  1643. return "i" + strconv.FormatInt(t, 10)
  1644. case uint:
  1645. return "i" + strconv.FormatUint(uint64(t), 10)
  1646. case uint8:
  1647. return "i" + strconv.FormatUint(uint64(t), 10)
  1648. case uint16:
  1649. return "i" + strconv.FormatUint(uint64(t), 10)
  1650. case uint32:
  1651. return "i" + strconv.FormatUint(uint64(t), 10)
  1652. case uint64:
  1653. return "i" + strconv.FormatUint(t, 10)
  1654. case uintptr:
  1655. return "i" + strconv.FormatUint(uint64(t), 10)
  1656. case float64:
  1657. if s, ok := encodeIntegralFloat(t); ok {
  1658. return s
  1659. }
  1660. return "r" + strconv.FormatFloat(t, 'g', -1, 64)
  1661. case string:
  1662. return "s" + t
  1663. case []byte:
  1664. return "x" + string(t)
  1665. default:
  1666. return "s" + fmt.Sprintf("%v", t)
  1667. }
  1668. }
  1669. // encodeIntegralFloat canonicalizes a whole float64 to the same "i" encoding used
  1670. // by integer values, without precision loss, so integral reals and integers are
  1671. // not treated as distinct under a unique index. It reports false (and returns
  1672. // nothing) for non-integral values or values outside the int64 range.
  1673. func encodeIntegralFloat(v float64) (string, bool) {
  1674. if v != math.Trunc(v) {
  1675. return "", false
  1676. }
  1677. if v < -9223372036854775808.0 || v >= 9223372036854775808.0 {
  1678. return "", false
  1679. }
  1680. return "i" + strconv.FormatInt(int64(v), 10), true
  1681. }
  1682. // lockForWrite acquires the table gate appropriate for a point write: exclusive
  1683. // when the table has a UNIQUE index (so the validating scan cannot race another
  1684. // writer), shared otherwise. The uniqueness decision is re-checked under the lock
  1685. // so a concurrent CREATE UNIQUE INDEX cannot slip in between the unlocked probe
  1686. // and the lock acquisition; the returned unlock closes the gate.
  1687. func (m *TableManager) lockForWrite(table string) (unlock func(), unique bool, err error) {
  1688. tl := m.tableLock(table)
  1689. for {
  1690. uniq, err := m.hasUniqueIndex(table)
  1691. if err != nil {
  1692. return nil, false, err
  1693. }
  1694. if uniq {
  1695. tl.Lock()
  1696. // Re-check under the exclusive gate (authoritative): CreateUniqueIndex
  1697. // also takes the exclusive gate, so it cannot run while we hold it.
  1698. uniq, err = m.hasUniqueIndex(table)
  1699. if err != nil {
  1700. tl.Unlock()
  1701. return nil, false, err
  1702. }
  1703. if uniq {
  1704. return tl.Unlock, true, nil
  1705. }
  1706. tl.Unlock()
  1707. continue
  1708. }
  1709. tl.RLock()
  1710. // A unique index could have appeared before we acquired the shared gate;
  1711. // re-check and escalate if so.
  1712. uniq, err = m.hasUniqueIndex(table)
  1713. if err != nil {
  1714. tl.RUnlock()
  1715. return nil, false, err
  1716. }
  1717. if uniq {
  1718. tl.RUnlock()
  1719. continue
  1720. }
  1721. return tl.RUnlock, false, nil
  1722. }
  1723. }
  1724. // ValidateUniqueIndex rejects a UNIQUE index definition if existing rows already
  1725. // contain duplicate non-NULL values for the indexed columns.
  1726. func (m *TableManager) ValidateUniqueIndex(index *Index) error {
  1727. seen := make(map[string]bool)
  1728. return m.scanRows(index.Table, func(row Row) (bool, error) {
  1729. encoded, isNull, err := m.encodeUniqueValue(row, index.Columns)
  1730. if err != nil {
  1731. return true, err
  1732. }
  1733. if isNull {
  1734. return false, nil
  1735. }
  1736. if seen[encoded] {
  1737. return true, &UniqueViolationError{Constraint: index.Name}
  1738. }
  1739. seen[encoded] = true
  1740. return false, nil
  1741. })
  1742. }
  1743. // CreateUniqueIndex validates existing rows and registers the index while
  1744. // holding the table's exclusive gate, so a concurrent writer cannot insert a
  1745. // conflicting value between validation and registration.
  1746. func (m *TableManager) CreateUniqueIndex(index *Index) error {
  1747. tl := m.tableLock(index.Table)
  1748. tl.Lock()
  1749. defer tl.Unlock()
  1750. if err := m.ValidateUniqueIndex(index); err != nil {
  1751. return err
  1752. }
  1753. return m.schema.CreateIndex(index)
  1754. }
  1755. type indexedRowVersion struct {
  1756. row Row
  1757. key string
  1758. lsn uint64
  1759. }
  1760. type indexPredicateSnapshot struct {
  1761. valueKey string
  1762. valueGen uint64
  1763. wildcardKey string
  1764. wildcardGen uint64
  1765. }
  1766. // selectByIndexWithLSN retrieves indexed rows and their durable versions. The
  1767. // transaction layer uses the versions for optimistic commit validation.
  1768. func (m *TableManager) selectByIndexWithLSN(table, indexName string, colValue interface{}) ([]indexedRowVersion, indexPredicateSnapshot, error) {
  1769. return m.selectByIndexKeyWithLSN(table, indexName, formatIndexValue(colValue))
  1770. }
  1771. // IndexRowKey computes the formatted in-memory index key a row maps to for an
  1772. // index. Expression columns are evaluated through the same registered evaluator
  1773. // used by uniqueness enforcement, so the key matches both durable index entries
  1774. // and staged overlay rows.
  1775. func (m *TableManager) IndexRowKey(idx *Index, row Row) (string, error) {
  1776. value, err := m.buildIndexValue(row, idx.Columns)
  1777. if err != nil {
  1778. return "", err
  1779. }
  1780. return formatIndexValue(value), nil
  1781. }
  1782. // IndexValueContainsNull reports whether any column contributing to an index
  1783. // key evaluates to NULL. UNIQUE indexes exempt such rows from conflicts under
  1784. // SQLite semantics.
  1785. func (m *TableManager) IndexValueContainsNull(idx *Index, row Row) (bool, error) {
  1786. _, isNull, err := m.encodeUniqueValue(row, idx.Columns)
  1787. return isNull, err
  1788. }
  1789. // selectByIndexKeyWithLSN is selectByIndexWithLSN with an already-computed
  1790. // formatted index key, so callers can look up composite and expression indexes
  1791. // without re-deriving the key from a single column value.
  1792. func (m *TableManager) selectByIndexKeyWithLSN(table, indexName, valueKey string) ([]indexedRowVersion, indexPredicateSnapshot, error) {
  1793. index, err := m.schema.GetIndex(indexName)
  1794. if err != nil {
  1795. return nil, indexPredicateSnapshot{}, err
  1796. }
  1797. tableKey := strings.ToLower(table)
  1798. tl := m.tableLock(tableKey)
  1799. indexKey := strings.ToLower(indexName)
  1800. for {
  1801. if err := m.ensureIndex(index); err != nil {
  1802. return nil, indexPredicateSnapshot{}, err
  1803. }
  1804. tl.RLock()
  1805. if !m.schema.TableExists(table) {
  1806. tl.RUnlock()
  1807. return nil, indexPredicateSnapshot{}, fmt.Errorf("table not found: %s", table)
  1808. }
  1809. m.cacheMu.RLock()
  1810. if m.disabledIndexes[indexKey] {
  1811. m.cacheMu.RUnlock()
  1812. tl.RUnlock()
  1813. return nil, indexPredicateSnapshot{}, fmt.Errorf("%w: %s is disabled", ErrIndexNotFound, indexName)
  1814. }
  1815. if _, initialized := m.indexCache[indexKey]; initialized {
  1816. break // Keep cacheMu through the complete candidate/key snapshot.
  1817. }
  1818. m.cacheMu.RUnlock()
  1819. tl.RUnlock()
  1820. // Commits can invalidate under a shared table gate. Retry the build,
  1821. // never interpret a missing cache as a legitimately empty index.
  1822. }
  1823. defer tl.RUnlock()
  1824. predicateKey, predicateGen, wildcardKey, wildcardGen := m.predicateSnapshot(table, indexName, valueKey)
  1825. snapshot := indexPredicateSnapshot{
  1826. valueKey: predicateKey, valueGen: predicateGen,
  1827. wildcardKey: wildcardKey, wildcardGen: wildcardGen,
  1828. }
  1829. rowids := append([]int64(nil), m.indexCache[indexKey][valueKey]...)
  1830. primaryKeys := make([]string, 0, len(rowids))
  1831. missingRowID := int64(0)
  1832. missingRowKey := false
  1833. for _, rowid := range rowids {
  1834. if primaryKey, ok := m.rowKeyCache[tableKey][rowid]; ok {
  1835. primaryKeys = append(primaryKeys, primaryKey)
  1836. } else {
  1837. missingRowID = rowid
  1838. missingRowKey = true
  1839. break
  1840. }
  1841. }
  1842. m.cacheMu.RUnlock()
  1843. if missingRowKey {
  1844. return nil, indexPredicateSnapshot{}, fmt.Errorf("index %s is missing rowid %d", indexName, missingRowID)
  1845. }
  1846. // If no rowids found, return empty result
  1847. if len(rowids) == 0 {
  1848. return []indexedRowVersion{}, snapshot, nil
  1849. }
  1850. rows := make([]indexedRowVersion, 0, len(primaryKeys))
  1851. err = m.pool.WithClient(func(client *KVClient) error {
  1852. keys := make([][]byte, len(primaryKeys))
  1853. for i, primaryKey := range primaryKeys {
  1854. keys[i] = []byte(m.dataKey(table, primaryKey))
  1855. }
  1856. results, err := client.MultiGet(keys)
  1857. if err != nil {
  1858. return err
  1859. }
  1860. for i, result := range results {
  1861. if !result.Found {
  1862. primaryKey := primaryKeys[i]
  1863. return fmt.Errorf("index %s references missing primary key %s", indexName, primaryKey)
  1864. }
  1865. row, err := decodeRow(result.Value)
  1866. if err != nil {
  1867. return err
  1868. }
  1869. rows = append(rows, indexedRowVersion{
  1870. row: row,
  1871. key: m.dataKey(table, primaryKeys[i]),
  1872. lsn: result.LSN,
  1873. })
  1874. }
  1875. return nil
  1876. })
  1877. if err != nil {
  1878. return nil, indexPredicateSnapshot{}, err
  1879. }
  1880. return rows, snapshot, nil
  1881. }
  1882. // SelectByIndex retrieves rows using an in-memory equality index followed by a
  1883. // single MultiGet for the matching primary keys.
  1884. func (m *TableManager) SelectByIndex(table, indexName string, colValue interface{}) ([]Row, error) {
  1885. versions, _, err := m.selectByIndexWithLSN(table, indexName, colValue)
  1886. if err != nil {
  1887. return nil, err
  1888. }
  1889. rows := make([]Row, len(versions))
  1890. for i := range versions {
  1891. rows[i] = versions[i].row
  1892. }
  1893. return rows, nil
  1894. }