Patrick O'Neil

{{Short description|American computer scientist (1942–2019)}}

{{about||the Scottish footballer|Patrick O'Neil (footballer)|those of a similar name|Patrick O'Neal (disambiguation)|and|Patrick O'Neill (disambiguation)}}

{{Infobox scientist

| name = Patrick Eugene O'Neil

| image =

| birth_date = 1942

| birth_place = Mineola, New York

| death_date = {{death date and age |2019|9|20 |1942|7}}

| death_place = Cambridge, Massachusetts

| fields = Computer Science

| workplaces = University of Massachusetts Boston

| doctoral_advisor = Gian-Carlo Rota

| known_for = Distributed Database, SQL Isolation, LRU-K, Log-Structured Merge Tree, Escrow Transaction,{{citation

| last1 = O'Neil | first1 = Patrick

| contribution = The Escrow transactional method

| doi = 10.1145/7239.7265

| title = ACM Transactions on Database Systems (TODS 1986)

| year = 1986

| volume = 11

| issue = 4

| pages = 405–430

| citeseerx = 10.1.1.77.3821

| s2cid = 10945351

}} C-Store

| mother = Elizabeth O'Neil{{Cite web|title=Remembering the life of Elizabeth|url=https://obituaries.alliednews.com/obituary/elizabeth-betty-o-neil-1072262411/|access-date=2021-10-24|website=obituaries.alliednews.com|language=en}}

| spouse = Elizabeth O'Neil{{citation|url=https://www.legacy.com/amp/obituaries/bostonglobe/194016278|title=Obituary:Patrick O'Neil|newspaper=Boston Globe|via=Legacy.com}}

}}

Patrick Eugene O'Neil (1942 – September 20, 2019){{citation|url=https://www.legacy.com/amp/obituaries/bostonglobe/194016278|title=Obituary:Patrick O'Neil|newspaper=Boston Globe|via=Legacy.com}} was an American computer scientist, an expert on databases, and a professor of computer science at the University of Massachusetts Boston.[http://www.cs.umb.edu/~poneil/currvitae.html Curriculum vitae], retrieved 2010-11-26. He is of Irish descent.

O'Neil did his undergraduate studies at the Massachusetts Institute of Technology, receiving a B.S. in mathematics in 1963. After earning a master's degree at the University of Chicago, he moved to Rockefeller University, where he earned a Ph.D. in combinatorial mathematics in 1969 under the supervision of Gian-Carlo Rota.{{mathgenealogy|name=Patrick Eugene O'Neil|id=17990}}.

He was an assistant professor at MIT from 1970 to 1972, but then left academia for industry, returning in 1988 as a member of the UMass/Boston faculty. He became a full professor in 1996.

He wrote highly cited papers on replication in distributed databases,{{citation

| last1 = Gray | first1 = Jim | author1-link = Jim Gray (computer scientist)

| last2 = Helland | first2 = Pat

| last3 = O'Neil | first3 = Patrick

| last4 = Shasha | first4 = Dennis | author4-link = Dennis Shasha

| contribution = The dangers of replication and a solution

| doi = 10.1145/233269.233330

| pages = 173–182

| title = Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data (SIGMOD '96)

| year = 1996| isbn = 0-89791-794-4 | s2cid = 237855 }}. page replacement strategies for databases,{{citation

| last1 = O'Neil | first1 = Elizabeth J. | author1-link = Elizabeth O'Neil

| last2 = O'Neil | first2 = Patrick E.

| last3 = Weikum | first3 = Gerhard | author3-link = Gerhard Weikum

| contribution = The LRU-K page replacement algorithm for database disk buffering

| doi = 10.1145/170035.170081

| pages = 297–306

| title = Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (SIGMOD '93)

| year = 1993| isbn = 0-89791-592-5 | s2cid = 207177617 }}. SQL isolation,{{citation

| last1 = Berenson | first1 = Hal

| last2 = Bernstein | first2 = Phil

| last3 = Gray | first3 = Jim | author3-link = Jim Gray (computer scientist)

| last4 = Melton | first4 = Jim

| last5 = O'Neil | first5 = Elizabeth | author5-link = Elizabeth O'Neil

| last6 = O'Neil | first6 = Patrick

| contribution = A critique of ANSI SQL isolation levels

| doi = 10.1145/223784.223785

| pages = 1–10

| title = Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data (SIGMOD '95)

| year = 1995| arxiv = cs/0701157| isbn = 0-89791-731-6

| s2cid = 2316540

}}. and database indexing strategies.{{citation

| last1 = O'Neil | first1 = Patrick

| last2 = Quass | first2 = Dallan

| contribution = Improved query performance with variant indexes

| doi = 10.1145/253260.253268

| pages = 38–49

| title = Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data (SIGMOD '97)

| year = 1997| isbn = 0-89791-911-4

| s2cid = 468585

| url = http://ilpubs.stanford.edu:8090/137/1/1996-12.pdf

}}. With Elizabeth O'Neil, he is the author of the database textbook Database Principles, Programming, and Performance (Morgan Kaufmann, 2nd ed., 2000).

O'Neil published the algorithms of the bitmap indices he found working in the CCA Model 204 DBMS in the mid-1980s, and implemented B-tree for that database. This work was first published in 1987.{{cite conference | last = O'Neil | first = Patrick | title = Model 204 Architecture and Performance | book-title = Proceedings of the 2nd International Workshop on High Performance Transaction Systems | pages = 40–59 | publisher = Springer-Verlag | year = 1987 | location = London, UK | editor = Dieter Gawlick |editor2=Mark N. Haynie |editor3=Andreas Reuter }}

O’Neil invented the Log-Structured Merge Tree (LSM Tree) along with Dieter Gawlick and Edward Cheng in 1991 while spending the summer at Gawlick's database research group at Digital Equipment Corporation in California. The resulting paper,

{{Cite journal

| last1 = O'Neil | first1 = Patrick E.

| last2 = Cheng | first2 = Edward

| last3 = Gawlick | first3 = Dieter

| last4 = O'Neil | first4 = Elizabeth

|author4-link=Elizabeth O'Neil

| title = The log-structured merge-tree (LSM-tree)

| doi = 10.1007/s002360050048

| journal = Acta Informatica

| volume = 33| issue = 4| pages = 351–385| date=June 1996

| citeseerx = 10.1.1.44.2782| s2cid = 12627452

}} published in 1996, also included a performance analysis by Elizabeth O'Neil. This access method supports very fast inserts without hobbling lookup times, and now underlies many NoSQL data stores, such as Bigtable, HBase, LevelDB, SQLite4,{{cite web |title=SQLite4 with LSM Wiki |url=https://sqlite.org/src4/doc/trunk/www/index.wiki |publisher=SQLite}} Tarantool,{{cite web |url=https://tarantool.org/en/doc/1.9/intro.html |title=An application server together with a database manager |access-date= April 3, 2018|quote=Tarantool’s disk-based storage engine is a fusion of ideas from modern filesystems, log-structured merge trees and classical B-trees.}} RocksDB, WiredTiger,{{Cite web|url=https://github.com/wiredtiger/wiredtiger/wiki/LSMTrees|title=LSMTrees · wiredtiger/Wiredtiger Wiki|website=GitHub }} Apache Cassandra, InfluxDB,{{Cite web|url=https://influxdb.com/blog/2015/10/07/the_new_influxdb_storage_engine_a_time_structured_merge_tree.html|title=[New] InfluxDB Storage Engine | Time Structured Merge Tree|date=7 October 2015}} and ScyllaDB.